基于近鄰信息和PSO算法的集成特征選取

劉全金，趙志敏，李穎新，俞曉磊

（1.南京航空航天大學(xué)理學(xué)院，江蘇南京210016；2.安慶師范學(xué)院物理與電氣工程學(xué)院，安徽安慶246011；3.北京經(jīng)緯紡機(jī)新技術(shù)有限公司，北京100176；4.北京市輕紡機(jī)械機(jī)器視覺工程技術(shù)研究中心，北京100176；5.江蘇省標(biāo)準(zhǔn)化研究院，江蘇南京210029）

基于近鄰信息和PSO算法的集成特征選取

劉全金1，2，趙志敏1，李穎新3，4，俞曉磊5

（1.南京航空航天大學(xué)理學(xué)院，江蘇南京210016；2.安慶師范學(xué)院物理與電氣工程學(xué)院，安徽安慶246011；3.北京經(jīng)緯紡機(jī)新技術(shù)有限公司，北京100176；4.北京市輕紡機(jī)械機(jī)器視覺工程技術(shù)研究中心，北京100176；5.江蘇省標(biāo)準(zhǔn)化研究院，江蘇南京210029）

提出了一種新的PSO特征選取方法.以粒子對(duì)應(yīng)特征組合的同類近鄰樣本和異類近鄰樣本間的距離關(guān)系作為類別可分性和粒子適應(yīng)度函數(shù).以適應(yīng)度函數(shù)加權(quán)的群體歷史最佳、粒子歷史最佳和粒子鄰域內(nèi)最佳個(gè)體信息共同指導(dǎo)粒子運(yùn)動(dòng)方向，搜索類內(nèi)緊密、類間分離的最佳特征組合；同時(shí)，利用加權(quán)集成方法對(duì)PSO特征選取方法進(jìn)行集成，以提高特征選取方法的穩(wěn)定性和魯棒性.在5個(gè)高維數(shù)據(jù)集上的特征選取實(shí)驗(yàn)結(jié)果表明集成PSO特征選取方法的有效性和可行性.

特征選取；PSO；集成方法；分類

1 引言

利用機(jī)器學(xué)習(xí)技術(shù)對(duì)高維數(shù)據(jù)降維，使降維后的數(shù)據(jù)仍承載初始數(shù)據(jù)中有效信息［1，2］.特征選取方法根據(jù)特征評(píng)價(jià)函數(shù)，從原始數(shù)據(jù)中選取代表原始數(shù)據(jù)特性的關(guān)鍵特征［3，4］.特征選取方法分為特征權(quán)重選取方法和特征子集選取方法.特征權(quán)重選取方法根據(jù)特征在不同類別樣本中的分布選取分類特征［5］，或基于分類模型推算特征對(duì)分類的影響進(jìn)而選取分類特征［6］.特征子集選取方法包括窮舉法、啟發(fā)法和隨機(jī)法等.高維數(shù)據(jù)集的窮舉法特征選取是NP問題；啟發(fā)法為次優(yōu)搜索算法，在迭代的過程中產(chǎn)生維數(shù)遞增或遞減的特征子集，能得到近似最優(yōu)解［7］，如順序后向選擇法（Sequential Backward Selection，SBS）；隨機(jī)法基于隨機(jī)性從特征空間中選取特征子集，主要包括基于進(jìn)化思想的遺傳算法和粒子群算法等優(yōu)化算法.

Kennedy等人［8］提出粒子群（Particle Swarm Optimization，PSO）算法.粒子群粒子通過與個(gè)體歷史最佳和群體歷史最佳的信息交流實(shí)現(xiàn)種群進(jìn)化［9］.二進(jìn)制 PSO算法［10］被用于解決0-1整數(shù)規(guī)劃問題，也適于特征選取問題研究.文獻(xiàn)［11，12］提出基于分類器的二進(jìn)制PSO特征選取算法（簡(jiǎn)稱BPSO方法），以粒子個(gè)體對(duì)應(yīng)特征組合分類結(jié)果為適應(yīng)度函數(shù)進(jìn)行分類特征選取研究.適應(yīng)度函數(shù)的特征組合分類交叉校驗(yàn)需要較大的計(jì)算量，選取的特征組合亦可能過擬合于適應(yīng)度函數(shù)所用的分類模型.另外，僅考慮粒子群群體歷史最佳的全局模型雖然算法收斂速度快，但算法易于早熟.

集成特征選取方法通過集成來自不同特征選取算法、不同樣本組成或不同特征選取范圍選取的特征，從中確定最佳分類特征［13］.Abeel［14］和Saeys［15］通過實(shí)驗(yàn)證明集成方法有助于提高特征選取方法魯棒性和穩(wěn)定性.

本文提出基于近鄰信息的BPSO特征選取方法（以下簡(jiǎn)稱NBPSO方法）.基于同類近鄰樣本和異類近鄰樣本信息定義粒子個(gè)體對(duì)應(yīng)特征組合的類別可分性和粒子適應(yīng)度函數(shù)，以保證特征組合類內(nèi)緊密、類間分離；同時(shí)，引入粒子近鄰信息，提出以類別可分性加權(quán)的群體歷史最佳位置、粒子個(gè)體歷史最佳位置和粒子鄰域內(nèi)最佳位置共同指導(dǎo)粒子個(gè)體運(yùn)動(dòng)方向，在特征空間中搜索最佳特征組合，研究高維數(shù)據(jù)的特征降維問題.另外，本文提出基于加權(quán)集成方法對(duì)并行NBPSO方法所選特征集成，以提高NBPSO方法的穩(wěn)定性和魯棒性.

在5個(gè)高維數(shù)據(jù)集上進(jìn)行的特征選取實(shí)驗(yàn)結(jié)果表明NBPSO方法在特征組合分類、算法復(fù)雜度和穩(wěn)定度等方面優(yōu)于基于分類器的BPSO特征選取方法，并證實(shí)了加權(quán)集成方法對(duì)NBPSO方法的促進(jìn)作用.這說明本文所提特征選取方法的有效性和可行性.

2 基于BPSO算法的特征選取方法

PSO算法中每個(gè)粒子代表解空間中一個(gè)解.初始階段，群體粒子隨機(jī)分布于解空間；進(jìn)化過程中，粒子基于適應(yīng)度函數(shù)，根據(jù)個(gè)體和群體歷史最佳粒子位置更新速度和位置，逐漸收斂于解空間的最佳位置.

式中，速度慣性因子ω＞0；速度權(quán)重c1＞0和c2＞0；隨機(jī)參數(shù)r1∈［0，1］和r2∈［0，1］；以最大速度vmax和最小速度vmin限制粒子移動(dòng)速度范圍.

基于二進(jìn)制 PSO算法的BPSO特征選取方法將所有備選特征作為特征選取搜索空間，搜索空間中不同位置粒子對(duì)應(yīng)的特征組合.對(duì)于訓(xùn)練集TrainD∈Rm xn（n個(gè)樣本、m個(gè)特征），在m維二值解空間中粒子位置分量∈｛0，1｝決定第d個(gè)特征的選擇狀態(tài)，分量值1或0表征特征被選取或被舍棄.用S型函數(shù)將速度分量壓縮至（0，1）之間，根據(jù)式（2）確定該粒子最新位置：

式中，rand是0到1之間的隨機(jī)數(shù)值.

粒子適應(yīng)度函數(shù)f（Xik）以粒子對(duì)應(yīng)特征組合的類別可分性為主要參數(shù)，很多文獻(xiàn)定義特征組合分類正確率為類別可分性，同時(shí)，將特征組合維數(shù)作為適應(yīng)度函數(shù)另一個(gè)參數(shù)，使之向低維特征組合進(jìn)化.進(jìn)化終止時(shí)，Pg為特征解空間最佳解向量，其非零元素Pg d對(duì)應(yīng)的特征組成分類特征集合.

3 基于近鄰信息的集成NBPSO特征選取方法

3.1NBPSO特征選取方法

本文提出基于近鄰信息的BPSO特征選取方法（簡(jiǎn)稱NBPSO方法）.綜合運(yùn)用全局搜索和局部搜索優(yōu)勢(shì)，將粒子鄰域內(nèi)最佳個(gè)體粒子信息納入BPSO特征選取方法的粒子速度更新中，并以粒子對(duì)特征組合在同類近鄰樣本和異類同類樣本間的距離關(guān)系作為粒子適應(yīng)度函數(shù)，通過粒子適應(yīng)度函數(shù)施加對(duì)粒子運(yùn)動(dòng)方向的影響.

粒子群進(jìn)化過程中補(bǔ)充粒子鄰域內(nèi)最佳粒子信息，有助于BPSO算法利用粒子的局部信息提高全局搜索能力；用適應(yīng)度函數(shù)加權(quán)粒子間“位置差異”，引導(dǎo)粒子向適應(yīng)度函數(shù)更大的位置移動(dòng)；對(duì)適應(yīng)度函數(shù)值歸一化，既有助于均衡之間關(guān)系，又有助于平衡粒子之間“位置差異”與粒子速度之間的數(shù)值關(guān)系（見算法1）.

算法1 NBPSO 特征選取方法

式中，n是TrainD的樣本個(gè)數(shù)，Dj是第 j個(gè)樣本，nearHit表示離Dj最近的同類樣本個(gè)數(shù)，nearMiss表示離樣本Dj最近的異類樣本個(gè)數(shù)；表示基于粒子對(duì)應(yīng)特征組合樣本Dj與同類近鄰樣本間的歐氏距離，表示基于粒子對(duì)應(yīng)特征組合樣本Dj與異類近鄰樣本間的歐氏距離，表示粒子對(duì)應(yīng)特征組合中的特征個(gè)數(shù).

適應(yīng)度函數(shù)以樣本與異類近鄰樣本間平均距離和樣本與同類近鄰樣本間平均距離的差值度量特征組合的類別可分性，旨在搜索類內(nèi)緊密、類間分離的特征組合.適應(yīng)度函數(shù)兼顧特征組合的類別可分性與特征組合維數(shù)，有利于NBPSO方法選取類間差異性大、類內(nèi)相似度高的低維分類特征集合.

計(jì)算樣本間距復(fù)雜度比樣本分類交叉校驗(yàn)復(fù)雜度低，故NBPSO方法的算法復(fù)雜度比基于分類結(jié)果構(gòu)建適應(yīng)度函數(shù)的BPSO方法的算法復(fù)雜度低，消耗時(shí)間少.

3.2集成NBPSO特征選取方法

利用NBPSO方法進(jìn)行集成特征選取研究（簡(jiǎn)稱ENBPSO方法）.首先，多個(gè)NBPSO特征選取過程并行進(jìn)行；然后，對(duì)所選特征做加權(quán)集成，通過特征的集成權(quán)值高低確定分類特征.

如圖1，在特征選取范圍內(nèi)并行進(jìn)行N個(gè)NBPSO特征選取過程.每個(gè)NBPSO過程基于隨機(jī)產(chǎn)生的粒子群初始群體確定各自的特征搜索范圍，通過粒子與群體歷史最佳、個(gè)體鄰域內(nèi)最佳和個(gè)體歷史最佳的信息交換，調(diào)整進(jìn)化速度和方向，進(jìn)而獲取群體歷史最佳粒子對(duì)應(yīng)特征組合.通過特征組合集成確定特征的集成權(quán)值，選取權(quán)值高的特征作為分類特征.

粒子群隨機(jī)初始化使每個(gè)NBPSO過程的特征搜索范圍各不相同，滿足集成方法特征選取范圍多樣性條件，有利于提高特征選取方法魯棒性和所選分類特征的分類性能.

粒子適應(yīng)度函數(shù)式（4）前半段是粒子對(duì)應(yīng)特征組合在訓(xùn)練集樣本中異類樣本之間差異性和同類樣本之間相似性的差值，定義其為NBPSO過程最佳粒子對(duì)應(yīng)特征組合Soptimal的類別可分性Div（Soptimal）.根據(jù)特征組合類別可分性對(duì)N次NBPSO所得特征組合進(jìn)行加權(quán)集成，集成公式為：

以類別可分性指標(biāo)加權(quán)特征組合的特征，集成后的特征權(quán)值能體現(xiàn)特征被選頻次，又反映特征在異類樣本和同類樣本間的相對(duì)差異程度，權(quán)值高的特征對(duì)分類貢獻(xiàn)大.然而，如何根據(jù)特征權(quán)值確定選取閾值進(jìn)而選取分類特征集合目前尚無普適性標(biāo)準(zhǔn).

利用順序后向選取（SBS）方法，一次僅剔除一個(gè)特征形成嵌套的候選特征子集，然后根據(jù)特征子集評(píng)價(jià)函數(shù)從中找出尋找最佳特征集合.這種方式選取效果較好，但對(duì)于高維數(shù)據(jù)特征選取問題，這種方式計(jì)算量太大，不易現(xiàn)實(shí).文獻(xiàn)［6］提出一種折中辦法，在遞歸特征剔除過程（RFE，Recursive Featrue Elimination）中，兼顧特征選取方法有效性和可行性，每次按比例選擇一部分特征作為候選特征子集.

在RFE過程中用ENBPSO方法獲取特征集成權(quán)值，基于特征集成權(quán)值生成候選特征子集，以候選特征子集分類結(jié)果為評(píng)價(jià)函數(shù)從中選取最佳特征集合（見算法2）.

算法2 ENBPSO特征選取方法

數(shù)據(jù)集被分為訓(xùn)練集和校驗(yàn)集.RFE過程中，對(duì)每個(gè)新生成候選特征子集重新并行N次NBPSO特征選取，特征的動(dòng)態(tài)集成權(quán)值能客觀反映特征之間的相對(duì)重要性，有利于提高特征選取質(zhì)量.

SVM（Support Vector Machine）分類器是Vapnik等人［6］基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理，運(yùn)用統(tǒng)計(jì)學(xué)習(xí)理論推導(dǎo)出的分類模型.KNN（K-Nearest Neighbor）分類器是基于近鄰思想演化而來的較為簡(jiǎn)單分類算法［4］.分類正確率體現(xiàn)基于特征子集建立的分類器對(duì)樣本的識(shí)別能力；分類AUC（Area Under roc Curve）值表示ROC（Receiver Operating Characteristics）曲線下面積［16］，能客觀反映異類樣本數(shù)量不均勻時(shí)的分類結(jié)果.

4 特征選取實(shí)驗(yàn)

將NBPSO方法、ENBPSO方法和基于SVM的BPSO方法以及SVM-RFE方法同時(shí)進(jìn)行特征選取實(shí)驗(yàn)，通過實(shí)驗(yàn)比較4種方法在高維特征數(shù)據(jù)集上的特征選取性能. SVM-RFE方法基于SVM分類模型在RFE過程中分析特征對(duì)分類模型的影響，進(jìn)而選取分類特征集合［6］.為不失一般性，在5個(gè)兩類數(shù)據(jù)集上進(jìn)行特征選取實(shí)驗(yàn).表1列出了DLBCL、Acute Leukemia、Multiple Myeloma、Colon和Prostate等5個(gè)基因表達(dá)譜數(shù)據(jù)集的相關(guān)參數(shù).

表1　基因表達(dá)譜數(shù)據(jù)集

4.1特征選取實(shí)驗(yàn)參數(shù)設(shè)置

鑒于高維數(shù)據(jù)中存在大量與類別無關(guān)的噪聲特征，在特征選取之前利用Bhattacharyya距離過濾噪聲特征.Bhattacharyya距離不但體現(xiàn)特征在不同類別樣本間的差異，還反映特征在各類樣本中的變化情況［22］.

為客觀比較4種特征選取方法性能，將數(shù)據(jù)集按3∶1∶1隨機(jī)分割為訓(xùn)練集、校驗(yàn)集和獨(dú)立測(cè)試集.如圖2所示，首先，根據(jù)Bhattacharyya距離過濾噪聲特征，縮小特征選取范圍：在Colon訓(xùn)練集里選擇Bhattacharyya距離較大的前500個(gè)基因作為特征選取范圍；在其他4個(gè)數(shù)據(jù)集的訓(xùn)練集里均以Bhattacharyya距離較大的前1000個(gè)基因?yàn)樘卣鬟x取范圍.然后，4種方法基于相同訓(xùn)練集、相同特征選取范圍在 RFE過程中產(chǎn)生候選特征子集：SVM-RFE方法基于特征對(duì)SVM模型的影響對(duì)特征排序，生成候選特征子集；BPSO方法以 SVM分類器在訓(xùn)練集中5倍交叉校驗(yàn)的分類AUC值和正確率及特征組合維數(shù)倒數(shù)為粒子個(gè)體適應(yīng)度函數(shù)值；NBPSO 和ENBPSO方法通過式（4）計(jì)算粒子個(gè)體適應(yīng)度函數(shù)值；將BPSO方法和NBPSO方法選取的特征集合作為各自下一輪特征選取過程的候選特征子集，ENBPSO方法根據(jù)算法2生成候選特征基因子集.

4種方法以SVM和KNN分類器對(duì)相同校驗(yàn)集的分類結(jié)果為評(píng)價(jià)函數(shù)從候選特征子集中選擇最佳特征集合（即分類特征集合），再以相同的獨(dú)立測(cè)試集測(cè)試分類特征集合分類能力.每種方法重復(fù)進(jìn)行20次，得到20個(gè)分類特征集合，以這些特征集合在獨(dú)立測(cè)試集上分類測(cè)試的統(tǒng)計(jì)結(jié)果比較4種特征選取方法的性能.

設(shè)置RFE過程的特征剔除率為50%，SVM核函數(shù)為線性核函數(shù)，KNN分類器的K=5，即5近鄰分類.

PSO參數(shù)是基于經(jīng)驗(yàn)值基礎(chǔ)上，經(jīng)過多次試驗(yàn)調(diào)試確定的.BPSO方法中PSO算法種群規(guī)模L=100，kmax=200，vmax=2，vmin=-2，c1=c2=4，ω在進(jìn)化過程中從1逐漸減小至0.7.NBPSO方法中PSO算法vmax=4，vmin=-4，nearMiss=nearHit=5，其他參數(shù)與BPSO方法參數(shù)相同. ENBPSO方法設(shè)置集成規(guī)模N=20，其中NBPSO方法中PSO算法kmax=100，其他參數(shù)與單次NBPSO參數(shù)相同.

4.2分類特征集合分類結(jié)果

SVM-RFE方法、BPSO方法、NBPSO方法和ENBPSO方法在5個(gè)數(shù)據(jù)集上選出20個(gè)分類特征集合，它們?cè)讵?dú)立測(cè)試集里的分類AUC值和正確率的平均值和標(biāo)準(zhǔn)差如表2所示.

由表2知，在Multiple Myeloma數(shù)據(jù)集上，NBPSO和ENBPSO方法所選特征均正確識(shí)別所有獨(dú)立測(cè)試集樣本類別.比較4種方法所選分類特征集合的分類AUC值，在除Colon數(shù)據(jù)集外的其他4個(gè)數(shù)據(jù)集上，NBPSO和ENBPSO方法均優(yōu)于 BPSO方法和SVM-RFE方法；在DLBCL和Prostate數(shù)據(jù)集上，ENBPSO方法優(yōu)于NBPSO方法；在A-cute Leukemia和Colon數(shù)據(jù)集上，NBPSO和ENBPSO方法選取的分類特征集合的分類AUC值互有高低.比較4種方法所選分類特征集合的分類正確率，在5個(gè)數(shù)據(jù)集上，NBPSO和ENBPSO方法都優(yōu)于BPSO方法和SVM-RFE方法；在DLBCL、Colon和Prostate數(shù)據(jù)集上，ENBPSO方法優(yōu)于NBPSO方法；在Acute Leukemia數(shù)據(jù)集上，NBPSO和ENBPSO方法選取的分類特征集合的分類正確率互有高低.

表2　分類特征集合在獨(dú)立測(cè)試集上的分類結(jié)果統(tǒng)計(jì)表

5 特征選取方法性能比較

5.1分類特征集合的分類性能顯著性檢驗(yàn)

基于單因素非參數(shù)方差分析Kruskal-Walls檢驗(yàn)方法［23］，利用MATLAB工具箱的kruskalwallis函數(shù)對(duì)4種方法所選20個(gè)分類特征集合在獨(dú)立測(cè)試集上的分類測(cè)試結(jié)果進(jìn)行顯著性差異分析，以進(jìn)一步比較四者性能.每個(gè)方法在每個(gè)數(shù)據(jù)集上80個(gè)獨(dú)立分類測(cè)試數(shù)據(jù)（20個(gè)SVM分類正確率、20個(gè)SVM分類AUC值、20個(gè)KNN分類正確率和20個(gè)KNN分類AUC值）組成一組. Kruskal-Walls檢驗(yàn)結(jié)果如表3所示.

表3　分類特征集合的分類性能差異性比較表

綜合表2和表3數(shù)據(jù)可知，NBPSO方法和ENBPSO方法在5個(gè)數(shù)據(jù)集上選出的特征集合比BPSO方法和SVM-RFE方法選出的特征集合分類能力強(qiáng)；同時(shí)，ENBPSO方法選出的特征集合分類能力比NBPSO方法選出的特征集合分類能力略強(qiáng).

5.2特征選取方法的時(shí)間復(fù)雜度

特征選取方法的算法復(fù)雜度決定于訓(xùn)練集樣本數(shù)、特征選取范圍、評(píng)價(jià)函數(shù)等因素.粒子群算法復(fù)雜度決定于種群規(guī)模、終止條件和適應(yīng)度函數(shù)等因素.因?yàn)樗惴ㄟ\(yùn)行時(shí)間與算法復(fù)雜度成線性關(guān)系，所以相同實(shí)驗(yàn)條件下不同算法消耗的時(shí)間長短可用于比較算法間的復(fù)雜度關(guān)系.表4列出4種特征選取方法從5個(gè)數(shù)據(jù)集選取20個(gè)分類特征集合所用平均時(shí)間.

表4　特征選取方法運(yùn)行時(shí)間表

SVM-RFE方法用時(shí)最短，NBPSO方法所用時(shí)間次之，ENBPSO方法耗時(shí)最長.BPSO方法消耗的時(shí)間主要用于粒子個(gè)體適應(yīng)度函數(shù)的5倍SVM分類交叉校驗(yàn)，NBPSO方法粒子個(gè)體適應(yīng)度函數(shù)基于近鄰樣本信息計(jì)算特征組合的可分性，所用計(jì)算量相對(duì)BPSO較小.ENBPSO集成方法增加的多次 NBPOS選取過程提高了特征選取算法的計(jì)算量，使之消耗了更多時(shí)間.由上，NBPSO方法復(fù)雜度比BPSO方法復(fù)雜度低；因?yàn)榧煞椒ㄔ黾拥倪x取過程提高了ENBPSO方法復(fù)雜度.

5.3特征選取方法的穩(wěn)定性

特征選取方法性能包括分類特征集合分類能力、選取方法穩(wěn)定性和消耗時(shí)間等指標(biāo).所謂穩(wěn)定性是指特征選取方法在變化的數(shù)據(jù)環(huán)境中所選分類特征集合的相對(duì)穩(wěn)定度.

基于秩相似系數(shù)的特征選取方法穩(wěn)定度指標(biāo)［15］，根據(jù)4種方法20次特征選取實(shí)驗(yàn)所得特征集合分析特征選取方法穩(wěn)定性.如表5所示，SVM-RFE方法的穩(wěn)定性低于其他3種方法.BPSO方法在DLBCL數(shù)據(jù)集上的穩(wěn)定性優(yōu)于NBPSO方法，而NBPSO方法在其他4個(gè)數(shù)據(jù)集上的穩(wěn)定性優(yōu)于BPSO方法.ENBPSO方法在5個(gè)數(shù)據(jù)集上的穩(wěn)定性都優(yōu)于其他3種方法，這也是集成方法用計(jì)算復(fù)雜度換來穩(wěn)定性.

表5　特征選取方法穩(wěn)定度比較表

隨著計(jì)算機(jī)技術(shù)特別是計(jì)算機(jī)硬件技術(shù)發(fā)展，科學(xué)家們逐漸降低對(duì)特征選取方法計(jì)算復(fù)雜度的要求，越來越關(guān)注于特征集合的分類能力和特征選取方法的穩(wěn)定性.所以，盡管ENBPSO方法在運(yùn)行時(shí)間上比其他3種方法消耗多，但鑒于穩(wěn)定性方面的優(yōu)勢(shì)，ENBPSO方法會(huì)有更大應(yīng)用前景.

6 總結(jié)

針對(duì)高維數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，本文提出基于近鄰信息的二進(jìn)制PSO特征選取方法.將基于同類近鄰樣本和異類近鄰樣本信息定義的特征組合類別可分性作為粒子個(gè)體的適應(yīng)度函數(shù)，用特征組合類別可分性加權(quán)的群體歷史最佳、粒子歷史最佳和粒子鄰域內(nèi)最佳個(gè)體信息共同指導(dǎo)粒子運(yùn)動(dòng)方向，在特征空間里搜索分類特征集合.5個(gè)高維數(shù)據(jù)集上的特征選取實(shí)驗(yàn)表明基于近鄰樣本信息構(gòu)建的粒子個(gè)體適應(yīng)度函數(shù)降低了特征選取算法的復(fù)雜度；粒子鄰域內(nèi)最佳個(gè)體信息的引入提高了特征選取質(zhì)量；基于類別可分性的加權(quán)集成方法有效提高了NBPSO方法的特征選取性能.

NBPSO方法和ENBPSO方法較好地完成了兩類樣本特征選取任務(wù)，今后將通過式（4）、（5）分析多類別特征組合在類間和類內(nèi)的相對(duì)關(guān)系，進(jìn)一步研究?jī)煞N方法在高維特征數(shù)據(jù)集里的多類別特征選取中的應(yīng)用.

［1］Liu H，Sun J，Liu L，et al.Feature selection with dynamic mutual information［J］.Pattern Recognition，2009，42（7）：1330-1339.

［2］鄒濤，張翠.概念級(jí)誤用檢測(cè)系統(tǒng)的認(rèn)知能力研究［J］.電子學(xué)報(bào)，2004，32（10）：1694-1697. Zou Tao，Zhang Cui.A study on apperception ability of concept level misuse detection system［J］.Acta Electronica Sinica，2004，32（10）：1694-1697.（in Chinese）

［3］李穎新，劉全金，阮曉鋼.一種腫瘤基因表達(dá)數(shù)據(jù)的知識(shí)提取方法［J］.電子學(xué)報(bào)，2004，32（9）：1479-1482. LI Ying-Xin，LIU Quan-jin，RUAN Xiao-gang.A method for extracting knowledge from tumor gene expression data ［J］.Acta Electronica Sinica，2004，32（9）：1479-1482. （in Chinese）

［4］邊肇祺，張學(xué)工.模式識(shí)別［M］.北京，清華大學(xué)出版社，2004.176-203. Bian Zhaoqi，Zhang Xuegong.Pattern Recognition［M］. Beijing：Tsinghua University Publisher，2004.176-203. （in Chinese）

［5］Zhang Daoqiang，Chen Songcan，Zhou Zhi-Hua.Constraint score：A new filter method for feature selection with pairwise constraints［J］.Pattern Recognition，2008，41（5）：1440-1451.

［6］Guyon I，Weston J，Barnhil S，et al.Gene selection for cancer classification using support vector machines［J］. Machine learning，2002，46（1-3）：389-422.

［7］王樹林，王戟，陳火旺，等.腫瘤信息基因啟發(fā)式寬度優(yōu)先搜索算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31（4）：636 -649. Wang Shulin，Wang Ji，Chen Huowang，et al.Heuristic breadth-first search algorithm for informative gene selection based on gene expression profiles［J］.Chinese Journal of Computers，2008，31（4）：636-649.（in Chinese）

［8］Kennedy J，Eberhart R C.Particle swarm optimization［A］. Proceedings of International Conference on Neutral Networks IV［C］.Piscataway NJ：IEEE Service Center，1995. 1942-1948.

［9］朱大林，詹騰，張屹，等.多策略差分進(jìn)化的元胞多目標(biāo)粒子群算法［J］.電子學(xué)報(bào)，2014，42（9）：1831-1838. Zhu Da-lin，Zhan Teng，Zhang yi，et al.Cellular multi-objective particle swarm algorithm based on multi-strategy differential evolution［J］.Acta Electronica Sinica，2014，42 （9）：1831-1838.（in Chinese）

［10］Kennedy J，Eberhart RC.A discrete binary version of the particle swarm algorithm［A］.Proceedings of IEEE International Conference on Systems，Man，and Cybernetics ［C］.Washington：IEEE，1997.4104-4109.

［11］Lin SW，Ying KC，Chen SC，et al.Particle swarm optimization for parameter determination and feature selection of support vector machines［J］.Expert Systems with Applications，2008，35（4）：1817-1824.

［12］Sahua B，Mishra D.A novel feature selection algorithm using particle swarm optimization for cancer microarray data［A］.Proceedings of International Conference on Modelling Optimization and Computing［C］.USA：Procedia Engineering，2012，38.27-31.

［13］李霞，張?zhí)镂?，郭?一種基于遞歸分類樹的集成特征基因選取方法［J］.計(jì)算機(jī)學(xué)報(bào)，2004，27（5）：675 -681. Li Xia，Zhang Tianwen，Guo Zheng.A novel ensemble of feature selection based on recursive partition-tree［J］.ChineseJournal of Computers，2004，27（5）：675-681.（in Chinese）

［14］Abeel T，Helleputte T，Van de Peer Y，et al.Robust biomarker identification for cancer diagnosis with ensemble feature selection methods［J］.Bioinformatics，2010，26 （3）：392-298.

［15］Saeys Y，Abeel T，Peer YV.Robust feature selection using ensemble feature selection techniques［A］.Proceedings of ECML PKDD’2008，Part II［C］.LNAI：Springer，2008，5212.313-325.

［16］Provost F，F(xiàn)awcett T.Analysis and visualization of classifier performance：Comparison under imprecise class and cost distributions［A］.Proceedings of 3rd International Conference on Knowledge Discovery and Data Mining ［C］.USA：AAAI Press，1997.43-48.

［17］Shipp MA，Ross KN，Tamayo P，et al.Diffuse large B-cell lymphoma outcome prediction by gene-expression profiling and supervised machine learning［J］.Nat Med，2002，8（1）：68-74.

［18］Golub TR，Slonim DK，Tamayo P，et al.Molecular classification of cancer class discovery and class prediction by gene expression monitoring［J］.Science，1999，286 （5439）：531-537.

［19］Zhan F，Hardin J，Kordsmeier B，et al.Global gene expression profiling of multiple myeloma，monoclonal gammopathy of undetermined significance，and normal bone marrow plasma cells［J］.Blood，2002，99（5）：1745 -1757.

［20］Alon U，Barkai N，Notterman DA，et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays ［J］.PNAS USA，1999，96（12）：6745-6750.

［21］Singh D，F(xiàn)ebbo PG，Ross K，et al.Gene expression correlates of clinical prostate cancer behavior［J］.Cancer Cell，2002，1（2）：203-209.

［22］Liu QJ，Zhao ZM，Li YX，et al.Feature selection based on sensitivity analysis of fuzzy ISODATA［J］.Neuro Computing，2012，85（1）：29-37.

［23］周品.MATLAB概率與數(shù)理統(tǒng)計(jì)［M］.北京：清華大學(xué)出版社，2012.267-270. Zhou Pin.MATLAB Probability and Mathematical Statistics［M］.Beijing：Tsinghua University Publisher，2012. 267-270.（in Chinese）

劉全金 男，1971年12月生于安徽六安，南京航空航天大學(xué)理學(xué)院博士研究生，安慶師范學(xué)院教授，主要研究方向：機(jī)器學(xué)習(xí)、信息處理.

E-mail：liuquanjing666@126.com

趙志敏（通信作者） 女，1955年3月生于遼寧沈陽，南京航空航天大學(xué)理學(xué)院教授，主要研究方向：現(xiàn)代測(cè)量與控制技術(shù)、智能計(jì)算.

E-mail：nuaazhzhm@126.com

李穎新 男，1972年9月生于河北遷安，北京經(jīng)緯紡機(jī)新技術(shù)有限公司高級(jí)工程師，博士，主要研究方向：機(jī)器視覺、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘、生物信息學(xué).

E-mail：linterlee@126.com

俞曉磊 男，1981年10月生于江蘇南京，江蘇省標(biāo)準(zhǔn)化研究院高級(jí)工程師、南京理工大學(xué)博士后，主要研究方向：通信與射頻信號(hào)處理、電子信號(hào)檢測(cè)技術(shù).

E-mail：nuaaxiaoleiyu@126.com

Ensemble Feature Selection Method Based on Neighborhood Information and PSO Algorithm

LIU Quan-jin1，2，ZHAO Zhi-min1，LI Ying-xin3，4，YU Xiao-lei5

（1.College of Science，Nanjing University of Aeronautics and Astronautics，Nanjing，Jiangsu 210016，China；2.Department of Physics，Anqing Normal College，Anqing，Anhui 246011，China；3.Beijing Jingwei Textile Machinery New Technology Co Ltd，Beijing 100176，China；4.Beijing Light Industry and Textile Machinery Engineering Research Center for Machine Vision，Beijing 100176，China；5.Jiangsu Institute of Standardization，Nanjing，Jiangsu 210029，China）

A new PSO algorithm is proposed in this paper for feature selection.Distances within the same class and between different classes are used as the index for distinguishing different classes，and thus can be used to construct the fitness function of particles in PSO.The direction of particles for searching optimal features which can result in close intra-class distance and far inter-class distance is determined by the current best solution of the particle and the optimal individual in particle neighborhood，weighted by the fitness function.Meanwhile，the PSO algorithm is aggregated by the weighted voting method to improve its stability and robustness.The experiment results on 5 high dimensional datasets show that the ensemble PSO algorithm is effective and feasible.

feature selection；PSO（particle swarm optimization）；ensemble method；classification

TP391

A

0372-2112（2016）04-0995-08

電子學(xué)報(bào)URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.034

2014-10-24；

2014-12-16；責(zé)任編輯：孫瑤

國家自然科學(xué)基金（No.61475071，No.61173068，No.10172043）；教育部博士點(diǎn)基金（No.20093218110024）；江蘇省自然科學(xué)基金青年基金（No.BK20141032）；國家質(zhì)檢總局科技項(xiàng)目（No.2013QK194）；安徽省自然科學(xué)基金（No.1608085QF157）