郭凱文, 潘宏亮, 侯阿臨

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長春 130012)

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

1 基于互信息的特征選擇

1.1 最大相關(guān)最小冗余準(zhǔn)則 特征選擇就是從大量的信息特征中, 找出最有效的分類特征. 特征選擇算法以相關(guān)性分析為基礎(chǔ), 將特征的相關(guān)性和冗余性相結(jié)合進(jìn)行研究[2], 目的是通過根據(jù)選擇出的特征對(duì)分類結(jié)果的貢獻(xiàn)程度, 加入權(quán)重因子提高分類的準(zhǔn)確率.

設(shè)兩個(gè)隨機(jī)變量x和y, 其邊際分布函數(shù)分別為p(x)和p(y), 聯(lián)合分布為p(x,y), 互信息I(x,y)是聯(lián)合分布p(x,y)與乘積分布p(x)p(y)的相對(duì)熵, 即

(1)

互信息是指特征與類別之間的相關(guān)性, 最小冗余是指特征之間的依賴關(guān)系[3], 即每個(gè)特征屬性之間的相關(guān)性最小, 則最小冗余的測(cè)度指標(biāo)定義為

(2)

其中:W1表示特征與特征之間的互信息值； |S|表示特征集的個(gè)數(shù)；i和j分別表示特征. 最大相關(guān)是特征子集與相應(yīng)類別的依賴程度, 要求特征子集與類別具有最大相關(guān)性, 最大相關(guān)的測(cè)度指標(biāo)定義為

(3)

其中:V1表示特征與相應(yīng)類別之間的互信息值;h表示數(shù)據(jù)集的類別;i表示特征.

最大相關(guān)最小冗余算法是結(jié)合特征與類別間最大相關(guān)性的選擇標(biāo)準(zhǔn)和特征間最小冗余的選擇標(biāo)準(zhǔn), 將其定義為一種新的選擇標(biāo)準(zhǔn):

φ=max{V1-W1}.

(4)

新標(biāo)準(zhǔn)φ將特征最大相關(guān)與最小冗余相結(jié)合, 并對(duì)兩種算法同時(shí)進(jìn)行優(yōu)化, 然后通過這種新標(biāo)準(zhǔn)對(duì)特征進(jìn)行篩選.

1.2 對(duì)最大相關(guān)最小冗余算法的改進(jìn) 為更好地篩選特征, 本文引入權(quán)重因子λ作為特征選擇的冗余性度量[4], 通過賦予λ對(duì)冗余性貢獻(xiàn)程度進(jìn)行調(diào)整, 以求得最好的分類結(jié)果, 修正準(zhǔn)則為

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

(5)

通過引入權(quán)值λ可改變特征的排列順序, 不同權(quán)值有不同的特征排序, 因此, 最大相關(guān)和最小冗余這兩個(gè)評(píng)估標(biāo)準(zhǔn)的權(quán)重對(duì)特征排序有較大影響. 本文通過權(quán)值的劃分針對(duì)不同特征排序?qū)μ卣鬟M(jìn)行選擇處理.

2 K-means聚類算法

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

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

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

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

在實(shí)際應(yīng)用中, 有許多對(duì)訓(xùn)練樣本選擇不當(dāng)導(dǎo)致分類結(jié)果不理想[5-7]的情況, 而SVM分類的結(jié)果對(duì)訓(xùn)練樣本有很高的要求[8], 所以通過K-means算法對(duì)數(shù)據(jù)進(jìn)行聚類很有必要, 將獲取的初始聚類樣本作為學(xué)習(xí)樣本, 然后對(duì)這些學(xué)習(xí)樣本進(jìn)行訓(xùn)練; 再采用訓(xùn)練好的SVM對(duì)所選取的測(cè)試集進(jìn)行分類, 充分利用聚類和SVM分類的優(yōu)點(diǎn), 提高分類效果.

3 支持向量機(jī)

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

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

(6)

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

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

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)采用CPU為Intel(R)Core, 內(nèi)存1 GB的PC機(jī); 軟件平臺(tái)為MATLAB2013a； 操作系統(tǒng)為Windows7旗艦版, 實(shí)驗(yàn)數(shù)據(jù)采集于一組心臟病患者, 由UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫提供, 其記錄了心臟病患者的各項(xiàng)身體指標(biāo), 該數(shù)據(jù)集的屬性列于表1.

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

首先對(duì)數(shù)據(jù)集進(jìn)行特征選擇, 設(shè)權(quán)重因子為λ, 通過對(duì)λ賦值對(duì)特征子集進(jìn)行相關(guān)性排序, 表2列出了特征子集的降序排列.

表2 特征子集的降序排列

對(duì)選取最優(yōu)特征集后的數(shù)據(jù)集進(jìn)行聚類, 先用K-means算法選擇出5類患者的所有樣本, 并逐一標(biāo)注, 根據(jù)每類數(shù)據(jù)的稀疏程度和樣本數(shù)再次用K-means算法在每類中聚類, 從而得到訓(xùn)練樣本. 經(jīng)過特征選擇和聚類后, 采用支持向量機(jī)再對(duì)測(cè)試集進(jìn)行分類, 得到測(cè)試集的分類準(zhǔn)確率結(jié)果列于表3.

表3 不同權(quán)重因子對(duì)應(yīng)的最大分類準(zhǔn)確率

由表3可見, 通過比較λ=0.5和λ=0.8, 分類準(zhǔn)確率得到了提高, 表明相關(guān)度和冗余度的權(quán)重影響分類的準(zhǔn)確率. 而當(dāng)λ=0.2和λ=0.8時(shí), 分類效果最好, 表明權(quán)重因子的有效性. 實(shí)驗(yàn)結(jié)果表明, 在心臟病患者的分類中, 加入權(quán)重因子使得分類效率和準(zhǔn)確率得到了明顯提升.

[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] 姚旭, 王曉丹, 張玉璽, 等. 基于粒子群優(yōu)化算法的最大相關(guān)最小冗余混合式特征選擇方法 [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ìn)的最大相關(guān)最小冗余特征選擇方法研究 [J]. 計(jì)算機(jī)工程與應(yīng)用, 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ìn)最大相關(guān)最小冗余判據(jù)的暫態(tài)穩(wěn)定評(píng)估特征選擇 [J]. 中國電機(jī)工程學(xué)報(bào), 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] 張雪鳳, 張桂珍, 劉鵬. 基于聚類準(zhǔn)則函數(shù)的改進(jìn)K-Means算法 [J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 楊玉梅. 基于信息熵改進(jìn)的K-Means動(dòng)態(tài)聚類算法 [J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 孫丹, 萬里明, 孫延風(fēng), 等. 一種改進(jìn)的RBF神經(jīng)網(wǎng)絡(luò)混合學(xué)習(xí)算法 [J]. 吉林大學(xué)學(xué)報(bào)(理學(xué)版), 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ī)的凸優(yōu)化求解 [J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 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.