基于特征選擇和聚類的分類算法

郭凱文, 潘宏亮, 侯阿臨

(長春工業大學 計算機科學與工程學院, 長春 130012)

特征信息分析是進行樣本分類的依據, 而特征維數的增高導致特征中的冗余和無效信息也相應增多, 使樣本分類更困難[1]. 本文利用特征選擇算法選擇出相關性最大的特征, 刪除無效和冗余的特征, 降低特征維數. 先通過對樣本進行聚類, 獲取可靠的訓練樣本, 再對測試集進行支持向量機(SVM)分類, 從而提高分類準確率.

1 基于互信息的特征選擇

1.1 最大相關最小冗余準則 特征選擇就是從大量的信息特征中, 找出最有效的分類特征. 特征選擇算法以相關性分析為基礎, 將特征的相關性和冗余性相結合進行研究[2], 目的是通過根據選擇出的特征對分類結果的貢獻程度, 加入權重因子提高分類的準確率.

設兩個隨機變量x和y, 其邊際分布函數分別為p(x)和p(y), 聯合分布為p(x,y), 互信息I(x,y)是聯合分布p(x,y)與乘積分布p(x)p(y)的相對熵, 即

(1)

互信息是指特征與類別之間的相關性, 最小冗余是指特征之間的依賴關系[3], 即每個特征屬性之間的相關性最小, 則最小冗余的測度指標定義為

(2)

其中:W1表示特征與特征之間的互信息值； |S|表示特征集的個數；i和j分別表示特征. 最大相關是特征子集與相應類別的依賴程度, 要求特征子集與類別具有最大相關性, 最大相關的測度指標定義為

(3)

其中:V1表示特征與相應類別之間的互信息值;h表示數據集的類別;i表示特征.

最大相關最小冗余算法是結合特征與類別間最大相關性的選擇標準和特征間最小冗余的選擇標準, 將其定義為一種新的選擇標準:

φ=max{V1-W1}.

(4)

新標準φ將特征最大相關與最小冗余相結合, 并對兩種算法同時進行優化, 然后通過這種新標準對特征進行篩選.

1.2 對最大相關最小冗余算法的改進 為更好地篩選特征, 本文引入權重因子λ作為特征選擇的冗余性度量[4], 通過賦予λ對冗余性貢獻程度進行調整, 以求得最好的分類結果, 修正準則為

max{λV1-(1-λ)W1}.

(5)

通過引入權值λ可改變特征的排列順序, 不同權值有不同的特征排序, 因此, 最大相關和最小冗余這兩個評估標準的權重對特征排序有較大影響. 本文通過權值的劃分針對不同特征排序對特征進行選擇處理.

2 K-means聚類算法

K-means聚類算法首先要確定聚類的個數, 使同一聚類的樣本距離聚類中心的距離更小. 算法過程如下：

1) 聚類中心為從數據集中隨機選取的k個樣本, 計算聚類中心與其他樣本的歐氏距離， 選取距離最小的樣本歸類于聚類中心所在的類, 得到初始的聚類結果;

2) 計算初始聚類中所有樣本的均值, 確定新的聚類中心, 然后再重復1)中的步驟;

3) 通過多次迭代, 直到聚類中心不再移動為止.

在實際應用中, 有許多對訓練樣本選擇不當導致分類結果不理想[5-7]的情況, 而SVM分類的結果對訓練樣本有很高的要求[8], 所以通過K-means算法對數據進行聚類很有必要, 將獲取的初始聚類樣本作為學習樣本, 然后對這些學習樣本進行訓練; 再采用訓練好的SVM對所選取的測試集進行分類, 充分利用聚類和SVM分類的優點, 提高分類效果.

3 支持向量機

支持向量機是一種機器學習算法, 其能有效確定兩組不同數據的分類邊界, 從而使分類效率顯著提高[9-10]. 支持向量機分類過程主要分為訓練和測試兩個階段. 在訓練階段, 算法得到訓練數據的最優分類決策邊界, 通過Leave-One-Out方法[11]對多次訓練和計算取均值, 確定交叉驗證的準確率； 測試階段, 對無標記樣本進行分類決策. 核函數的選擇對測試集分類有重要作用, 本文采用徑向基(RBF)核函數, 即

K(x,xi)=exp{-γ‖x-xi‖2},γ>0,

(6)

其中:γ表示RBF核函數的系數;x表示樣本集;xi表示單個樣本. 核函數K表示樣本對整個分類超平面的影響, 通過正則化參數c和核參數g分別在[2-2,25]和[2-4,25]范圍內搜索, 避免出現過擬合情況. 支持向量機首先要選定訓練集, 其他作為測試集, 算法流程如圖1所示.

圖1 支持向量機算法流程Fig.1 Flow chart of support vector machine algorithm

4 實驗結果與分析

實驗采用CPU為Intel(R)Core, 內存1 GB的PC機; 軟件平臺為MATLAB2013a； 操作系統為Windows7旗艦版, 實驗數據采集于一組心臟病患者, 由UCI機器學習數據庫提供, 其記錄了心臟病患者的各項身體指標, 該數據集的屬性列于表1.

表1 心臟病患者的特征屬性

首先對數據集進行特征選擇, 設權重因子為λ, 通過對λ賦值對特征子集進行相關性排序, 表2列出了特征子集的降序排列.

表2 特征子集的降序排列

對選取最優特征集后的數據集進行聚類, 先用K-means算法選擇出5類患者的所有樣本, 并逐一標注, 根據每類數據的稀疏程度和樣本數再次用K-means算法在每類中聚類, 從而得到訓練樣本. 經過特征選擇和聚類后, 采用支持向量機再對測試集進行分類, 得到測試集的分類準確率結果列于表3.

表3 不同權重因子對應的最大分類準確率

由表3可見, 通過比較λ=0.5和λ=0.8, 分類準確率得到了提高, 表明相關度和冗余度的權重影響分類的準確率. 而當λ=0.2和λ=0.8時, 分類效果最好, 表明權重因子的有效性. 實驗結果表明, 在心臟病患者的分類中, 加入權重因子使得分類效率和準確率得到了明顯提升.

[1] 范雪莉, 馮海泓, 原猛. 基于互信息的主成分分析特征選擇算法 [J]. 控制與決策, 2013, 28(6): 915-919. (FAN Xueli, FENG Haihong, YUAN Meng. PCA Based on Mutual Information for Feature Selection [J]. Control and Decision, 2013, 28(6): 915-919.)

[2] 姚旭, 王曉丹, 張玉璽, 等. 基于粒子群優化算法的最大相關最小冗余混合式特征選擇方法 [J]. 控制與決策, 2013, 28(3): 413-417. (YAO Xu, WANG Xiaodan, ZHANG Yuxi, et al. A Maximum Relevance Minimum Redundancy Hybrid Feature Selection Algorithm Based on Particle Swarm Optimization [J]. Control and Decision, 2013, 28(3): 413-417.)

[3] 姚明海, 王娜, 齊妙， 等. 改進的最大相關最小冗余特征選擇方法研究 [J]. 計算機工程與應用, 2014, 50(9): 116-122. (YAO Minghai, WANG Na, QI Miao, et al. The Study of the Maximum Related Minimum Redundant Feature Selection Method for Improvement [J]. Computer Engineering and Application, 2014, 50(9): 116-122.)

[4] 李楊, 顧雪平. 基于改進最大相關最小冗余判據的暫態穩定評估特征選擇 [J]. 中國電機工程學報, 2013, 33(34): 179-186. (LI Yang, GU Xueping. Feature Selection for Transient Stability Assessment Based on Improved Maximal Relevance and Minimal Redundancy Criterion [J]. Proceedings of the CSEE, 2013, 33(34): 179-186.)

[5] 張雪鳳, 張桂珍, 劉鵬. 基于聚類準則函數的改進K-Means算法 [J]. 計算機工程與應用, 2011, 47(11): 123-127. (ZHANG Xuefeng, ZHANG Guizhen, LIU Peng. ImprovedK-Means Algorithm Based on the Clustering Criteria Function [J]. Computer Engineering and Applications, 2011, 47(11): 123-127.)

[6] 楊玉梅. 基于信息熵改進的K-Means動態聚類算法 [J]. 重慶郵電大學學報(自然科學版), 2016, 28(2): 254-259. (YANG Yumei. ImprovedK-Means Dynamic Clustering Algorithm Based on Information Entropy [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2016, 28(2): 254-259.)

[7] 彭長生. 基于Fisher判別的分布式K-Means聚類算法 [J]. 江蘇大學學報(自然科學版), 2014, 35(4): 422-427. (PENG Changsheng. DistributedK-Means Clustering Algorithm Based on Fisher Discriminant Ratio [J]. Journal of Jiangsu University (Natural Science Edition), 2014, 35(4): 422-427.)

[8] 孫丹, 萬里明, 孫延風, 等. 一種改進的RBF神經網絡混合學習算法 [J]. 吉林大學學報(理學版), 2010, 48(5): 818-822. (SUN Dan, WAN Liming, SUN Yanfeng, et al. An Improved Hybrid Learning Algorithm for RBF Neural Network [J]. Journal of Jilin University (Science Edition), 2010, 48(5): 818-822.)

[9] Montejo L D, JIA Jingfei, Kim H K, et al. Computer-Aided Diagnosis of Rheumatoid Arthritis with Optical Tomography, Part 1: Feature Extraction [J]. Journal of Biomedical Optics, 2013, 18(7): 076001.

[10] 周正松, 李瑤, 陶德元. 支持向量機的凸優化求解 [J]. 四川大學學報(自然科學版), 2016, 53(4): 781-787. (ZHOU Zhengsong, LI Yao, TAO Deyuan. Convex Optimization of Support Vector Machines [J]. Journal of Sichuan University (Natural Science Edition), 2016, 53(4): 781-787.)

[11] Montejo L D, JIA Jingfei, Kim H K, et al. Computer-Aided Diagnosis of Rheumatoid Arthritis with Optical Tomography, Part 2: Image Classification [J]. Journal of Biomedical Optics, 2013, 18(7): 076002.