基于特征分組和PSO 的特征選擇算法*

余肖生 江 川 陳 鵬

（三峽大學(xué)計(jì)算機(jī)與信息學(xué)院 宜昌 443002）

1 引言

特征選擇，即從一個(gè)特征集中選擇出一部分重要的特征，是數(shù)據(jù)處理中的關(guān)鍵步驟之一，其能起到降維，減少數(shù)據(jù)存儲空間的效果［1］。若數(shù)據(jù)集中存在n維特征，使用特征選擇進(jìn)行搜索存在著2n種結(jié)果［2］。每一種結(jié)果都會(huì)耗費(fèi)大量的時(shí)間和計(jì)算成本，對后面數(shù)據(jù)分析等步驟造成不利的影響，若選擇出部分重要特征再進(jìn)行分析，可以大大降低時(shí)間和計(jì)算成本。特征選擇方法總體可以分為過濾式、封裝式和嵌入式方法［3～4］。近年來，針對高維數(shù)據(jù)的特征選擇，有不少研究者使用了演化算法來進(jìn)行，如遺傳算法、蟻群算法和粒子群算法等［5～8］。演化算法每迭代一次，便可以得到一組解，不需要多次進(jìn)行全局搜索，花費(fèi)時(shí)間和計(jì)算量較小。因演化算法是通過迭代實(shí)現(xiàn)特征選擇，每一次得到的結(jié)果建立在上一次的結(jié)果上，容易陷入局部最優(yōu)化。Zhu 等局部搜索方法和遺傳算法進(jìn)行結(jié)合，添加了包裹式方法，減少了因搜索需要的大量時(shí)間［9～10］。Xue 等提出了基于粒子群優(yōu)化的特征選擇算法PSO，在多個(gè)目標(biāo)下達(dá)到最優(yōu)［11～12］。Tabakhi等使用蟻群算法的無監(jiān)督特征選擇方法，搜索空間使用無向加權(quán)圖來表示，使搜索空間減小了［13］。這些方法主要從演化算法的角度出發(fā)，針對特征選擇出來的結(jié)果進(jìn)行一次次的迭代，不斷得到更好的特征選擇結(jié)果，針對演化算法迭代時(shí)容易陷入局部最優(yōu)的特點(diǎn)，加入了其他的方法進(jìn)行了改進(jìn)，從而使結(jié)果有了一定的進(jìn)步。由于方法使用較多，使算法的復(fù)雜性明顯上升，考慮的指標(biāo)也只有樣本分類的精確度，忽略了特征選擇穩(wěn)定性。從而導(dǎo)致每次選出的特征子集出現(xiàn)較大變化，以致影響了結(jié)果的魯棒性。而在基因標(biāo)記等應(yīng)用中，特征選擇結(jié)果的穩(wěn)定性要求要遠(yuǎn)遠(yuǎn)高于精確度的要求［14～15］，所以選擇出的特征子集的穩(wěn)定性也是至關(guān)重要的［16］。

為了提升特征選擇的穩(wěn)定性和降低特征子集的冗余度，筆者提出了基于特征分組和PSO的特征選擇算法，即以特征間的關(guān)聯(lián)性對原始特征進(jìn)行了分組，對分組后的特征使用PSO 算法進(jìn)行選擇，在選擇過程中，為了避免算法陷入局部最優(yōu)，對部分粒子的值進(jìn)行了隨機(jī)擾動(dòng)，最后對選取的特征進(jìn)行集成。以特征間的關(guān)聯(lián)性分組，減小了特征選擇的維度，也降低了每組特征的冗余，使PSO 算法進(jìn)行特征選擇時(shí)提高了初始化種群質(zhì)量，最終選擇出更穩(wěn)定的特征子集。

2 相關(guān)理論知識

2.1 互信息

互信息是信息論中的一種信息度量方式，用于測量變量間相互依賴的程度。通過互信息，可以從一個(gè)變量中了解到另一變量的具體信息量，當(dāng)互信息的值變大時(shí)，說明從一個(gè)特征了解另一特征的信息越多。對于兩個(gè)離散隨機(jī)變量X 和Y，它們的互信息可以定義為

在連續(xù)隨機(jī)變量中，其中的互信息可以變換成：

其中，聯(lián)合概率密度函數(shù)表示為p（x，y），x 和y 的邊緣概率密度函數(shù)表示為p（x）和p（y）。

通過式（1）、（2）可得，若X 和Y 相互獨(dú)立，則X對Y 不提供任何信息，所得的互信息值為零，當(dāng)X和Y 關(guān)系越密切時(shí)，所得的值越大。當(dāng)X 與Y 表示特征和標(biāo)簽之間的聯(lián)系時(shí)，互信息值越大，則特征和標(biāo)簽的關(guān)聯(lián)性越強(qiáng)；當(dāng)X 與Y 同時(shí)表示特征時(shí)，互信息值越大，則特征間的冗余性越強(qiáng)。

2.2 PSO

PSO 算法模仿鳥群，鳥群以合作的方式來尋找食物。其尋找過程是通過一次次的迭代得到目前最優(yōu)的速度和位置，進(jìn)而得到整個(gè)種群中食物的位置。在PSO模型中，優(yōu)化問題的解作為解空間的一個(gè)粒子，粒子的位置和速度決定著它們下次迭代的方向，根據(jù)當(dāng)前最優(yōu)的粒子來不斷調(diào)整自己的狀態(tài)。在t+1代粒子i的速度根據(jù)式（3）進(jìn)行更新：

在t+1代粒子i的位置根據(jù)式（4）進(jìn)行更新：

其中，w 表示慣性權(quán)重，第t+1代粒子的具體運(yùn)動(dòng)情況由第t 代的值來決定，參數(shù)c1和c2為粒子的學(xué)習(xí)因子，rand1和rand2是位于［0，1］的值，實(shí)驗(yàn)時(shí)由具體的情況進(jìn)行設(shè)定。

2.3 穩(wěn)定性提升方法

近年來，隨著研究的不斷深入，研究人員根據(jù)不同的問題，提出了一些穩(wěn)定性提升算法。Zhou使用Bootstrap方法抽樣數(shù)據(jù)得到多個(gè)特征子集，隨機(jī)移除特征子集中的特征，使用Relief 特征選擇方法對特征進(jìn)行排序，通過移除不同特征，使用算法得到排序不變的特征，并篩選出這些不變的特征［17］。Yang 對原始數(shù)據(jù)特征使用不同規(guī)模的采樣，生成不同的訓(xùn)練樣本，最后集成特征選擇的結(jié)果，來提高特征選擇的穩(wěn)定性［18］。Aldehim 使用集成的方法，集成不同方法得到的結(jié)果，提升特征子集的穩(wěn)定性［19～20］。這些方法使用了多種特征選擇方法，對特征選擇出來的結(jié)果進(jìn)行了集成，提高了特征選擇的穩(wěn)定性，但是采用方法過多，導(dǎo)致復(fù)雜性上升，每一種方法考慮其自身的優(yōu)點(diǎn)，卻沒有考慮方法之間的聯(lián)系和特征之間的前后關(guān)聯(lián)，也較少考慮精確度和高維小樣本問題。

3 基于特征分組和PSO 的特征選擇算法

從穩(wěn)定性角度看，傳統(tǒng)算法和演化特征選擇算法具有一定的效果。在特征選擇中，針對傳統(tǒng)方法時(shí)間復(fù)雜度較高等不足，筆者將特征進(jìn)行分組，對原始特征進(jìn)行降維，降低時(shí)間復(fù)雜度。針對演化算法沒有考慮特征間的關(guān)聯(lián)性，導(dǎo)致選出的特征存在部分冗余，在分組時(shí)考慮特征間的關(guān)聯(lián)性，使特征子集間的耦合度降低，并對少部分粒子進(jìn)行隨機(jī)擾動(dòng)，避免了算法陷入局部最優(yōu)，對最后的特征子集進(jìn)行集成，得到穩(wěn)定的特征子集，具體流程圖如圖1所示。

圖1 算法流程圖

3.1 特征分組

在高維特征選擇方面，演化算法所選出的最終特征容易出現(xiàn)不穩(wěn)定。針對這一不足，筆者將原始的數(shù)據(jù)特征進(jìn)行分組，相較于原始的高維特征，分組后的每組特征維度降低。為了選取更有效的特征，分組特征所使用的算法是互信息與隨機(jī)森林。首先通過隨機(jī)森林算法對特征的重要性進(jìn)行排序，能識別出分類結(jié)果的排在前面。根據(jù)排序的結(jié)果，選出最前列的四個(gè)特征與其他特征進(jìn)行互信息計(jì)算，得到特征間的互信息值，其余的每個(gè)特征與前四個(gè)特征中互信息值最大的分為一組，可得到四個(gè)特征組。

分組完成后，相較于原始特征集，特征維度降低，特征組間的冗余信息較少。特征組內(nèi)的關(guān)聯(lián)度較高，在使用PSO 算法做特征選擇時(shí)，粒子的搜索空間減小，時(shí)間的復(fù)雜度降低。因每組特征內(nèi)的關(guān)聯(lián)度高，提升了粒子初始化種群的質(zhì)量，進(jìn)而每組特征能選擇出更重要的特征。

3.2 PSO進(jìn)行特征選擇

根據(jù)第一步得到的特征分組后，筆者使用了粒子群算法對分組后的特征進(jìn)行了選擇。

3.2.1 種群的初始化

速度和位置兩個(gè)參數(shù)決定了粒子運(yùn)動(dòng)的具體情況，位置決定了距離最優(yōu)值的距離，速度迭代時(shí)變化的大小。在粒子群算法中。粒子的特征值每一維中只能取1或者0，1預(yù)示著該維特征在本輪迭代中被選擇，0 則預(yù)示在本輪迭代中被舍棄，針對整個(gè)粒子的種群，可得到本輪迭代時(shí)的一種特征選擇結(jié)果。在粒子群算法開始時(shí)，針對所有的粒子賦初始值。具體的初始區(qū)間為［0，1］，為了便于統(tǒng)計(jì)和觀察，當(dāng)初始值大于0.5 時(shí)，則賦值為1，當(dāng)初始值小于等于0.5 時(shí)，則賦值為0，通過x（i，j）來進(jìn)行記錄，i 代表第i 行的樣本，j 代表第j 維特征。可以得到，在初始化過程中，所選出的特征總數(shù)占原始特征的50%，滿足一般的特征選擇要求。具體公式如（5）所示：

個(gè)體粒子初始pbest 為其粒子的本身，初始化gbest隨機(jī)記錄為某一粒子。

3.2.2 迭代的過程及結(jié)果

在迭代過程中粒子的速度和位置更新按照式（3）和式（4）進(jìn)行更新。每次迭代之后得到的結(jié)果，從實(shí)際情況出發(fā)，特征選擇不僅僅需要考慮的是特征最后選出的維數(shù)，還需要考慮樣本分類的精確度，筆者使用這兩種目標(biāo)進(jìn)行聯(lián)合判定粒子所選出的優(yōu)劣程度，所立的適應(yīng)度函數(shù)精確度占比為0.8，特征維數(shù)為0.2，具體公式如式（6）所示：

其中，fit 為適應(yīng)度值，err 為錯(cuò)誤率，來源于分類的結(jié)果，dimension 為所選的特征數(shù)，D 為原始的總特征數(shù)。

為了避免因粒子陷入局部而使結(jié)果存現(xiàn)偏差，在粒子選擇的過程中，筆者對粒子進(jìn)行了隨機(jī)擾動(dòng)，避免粒子陷入局部最優(yōu)化，具體的過程為，對x（i，j）的值進(jìn)行更改，更改的總數(shù)占整個(gè)矩陣的5%，更改的位置為迭代總數(shù)的60%。具體的更改公式如式（7）所示：

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

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

所有的實(shí)驗(yàn)均是在內(nèi)存8.00GB，處理器為Intel 上運(yùn)行的，運(yùn)行環(huán)境為MatlabR2016。在算法運(yùn)算過程中，為了更具有代表性，分類器的使用中，選擇了KNN（K=5）算法和SVM 算法。粒子群的參數(shù)設(shè)置中，種群大小N=30，最大迭代次數(shù)T=100，慣性權(quán)重隨迭代次數(shù)的增加而更改，最大ω（max）=0.8，最小ω（min）=0.4。學(xué)習(xí)因子c1=c2=2，粒子的最大速度V（max）=10，最小速度V（min）=-10。表1 為本文所采用的5 個(gè)公開數(shù)據(jù)集。數(shù)據(jù)集來源于UCI 學(xué)習(xí)網(wǎng)站和http：//featureselection.asu.edu/datasets.php兩個(gè)網(wǎng)站。

表1 數(shù)據(jù)集信息

4.2 常用的穩(wěn)定性度量方法

穩(wěn)定性度量指標(biāo)是對特征選擇結(jié)果的一種評判。根據(jù)現(xiàn)有研究，不同的評價(jià)指標(biāo)往往決定了不同的特征選擇穩(wěn)定性結(jié)果。根據(jù)特征選擇不同的度量方法，具體可以分為權(quán)重法、子集法和排序法。其中排序法通過對部分排序列表進(jìn)行度量，考察排序向量的相似性。子集法通過子集間同一特征的距離度量來評判特征間的相似性［21～22］。每一種方法都可以從一方面或一些方面來度量特征選擇的穩(wěn)定性。

本文使用的穩(wěn)定性度量方法主要有兩種，其一為特征的重復(fù)率，在兩個(gè)特征子集中，存在相同的特征越多，說明穩(wěn)定性越高，如式（8）所示。

S 和S'為實(shí)驗(yàn)中的兩個(gè)特征子集，S∩S′表示選出兩個(gè)子集共有的特征。

其二為斯皮爾曼排序相關(guān)系數(shù)。針對共有的特征進(jìn)行度量不夠深入，因特征間的排列順序和重要性不一樣，排列順序往往影響著特征的重要性。因此引入度量指標(biāo)斯皮爾曼排序相關(guān)系數(shù)，如式（9）所示。

其中，ri和ri'是共有的特征i 在向量r 和r'中的位置，一共有c個(gè)共同的項(xiàng)。

4.3 實(shí)驗(yàn)穩(wěn)定性分析

從相關(guān)網(wǎng)站上采取了數(shù)據(jù)集后，筆者利用所提出的方法完成了相關(guān)的實(shí)驗(yàn)。在高維小樣本中，樣本的變化導(dǎo)致選出的特征出現(xiàn)變化，本實(shí)驗(yàn)隨機(jī)刪除5 個(gè)樣本和增加5 個(gè)原始中存在的樣本，分析原始樣本和增刪樣本的特征子集變化情況。為了驗(yàn)證方法的有效性，本方法記作DGBPSO（divide group about BPSO）并和原始的BPSO 方法以及遺傳算法GA進(jìn)行了結(jié)果對比。特征子集穩(wěn)定性評判標(biāo)準(zhǔn)采用式（8）和式（9）。所得到的結(jié)果如圖2～圖5所示，為記作簡便，橫坐標(biāo)為每個(gè)數(shù)據(jù)集的第一個(gè)字母，如ALLAML記作A。

圖2 隨機(jī)減少5個(gè)樣本對數(shù)據(jù)集進(jìn)行運(yùn)算并使用特征重復(fù)率評判準(zhǔn)則得到的穩(wěn)定性結(jié)果

圖5 增加5個(gè)樣本對數(shù)據(jù)集進(jìn)行運(yùn)算使用斯皮爾曼系數(shù)得到的穩(wěn)定性結(jié)果

對每個(gè)數(shù)據(jù)集隨機(jī)減少5 個(gè)樣本，根據(jù)圖2 可得，在DLBCL、CLL_SUB_111、Prosate_GE 和GLI_85四個(gè)數(shù)據(jù)集上，DGBPSO算法都比BPSO和GC算法特征重復(fù)率高，在數(shù)據(jù)集ALLAML 上，DGBPSO算法比不上BPSO 算法。在DLBCL 數(shù)據(jù)集上，特征重復(fù)率相較于BPSO 提高了7.4%；CLL_SUB_111 提高了0.48%；Prosate_GE 提高了3.8%；GLI_85 提高了16.2%。相較于BPSO 和GC 算法，DGBPSO 算法優(yōu)點(diǎn)在于根據(jù)特征分組，縮小了特征維度，粒子所尋找到的特征則有更大的相似性，進(jìn)而穩(wěn)定性更高，算法得到了改進(jìn)。

在上述減少5 個(gè)樣本得到的特征子集上，筆者也選取了斯皮爾曼系數(shù)進(jìn)行了評判，根據(jù)圖3 可得，在ALLAML、CLL_SUB_111、Prostate_GE、GLI_85 數(shù)據(jù)集上，DGBPSO 方法比BPSO 和GC 方法要好，在DLBCL 數(shù)據(jù)集上比GC 方法好，沒有BPSO 方法優(yōu)秀。相較于傳統(tǒng)的BPSO 方法，在ALLAML 數(shù)據(jù)集上，DGBPSO 提高了8.7%，CLL_SUB_111 提高了3.9%，Prosate_GE 提高了13.1%，GLI_85 提高了0.9%，可以看出在ALLAML 和Prosate_GE 數(shù)據(jù)集上，提升得比較明顯。

圖3 隨機(jī)減少5個(gè)樣本對數(shù)據(jù)集進(jìn)行運(yùn)算使用斯皮爾曼系數(shù)得到的穩(wěn)定性結(jié)果

在增加5 個(gè)樣本的條件下，根據(jù)圖4 可得，在ALLAML、DLBCL、Prosate_GE、GLI_85 數(shù)據(jù)集上，相較于GC和BPSO算法，本文的DGBPSO算法有較大提升，在CLL_SUB_111 數(shù)據(jù)集上，表現(xiàn)略差于BPSO 算法。其中數(shù)據(jù)集ALLAML提升了1%；數(shù)據(jù)集DLBCL 提升了2.3%，數(shù)據(jù)集Prosate_GE 提升了7.1%，數(shù)據(jù)集GLI_85 提升了17.2%。根據(jù)現(xiàn)有的研究理論，增加樣本可以提高特征選擇的穩(wěn)定性，結(jié)合圖3和圖4可以看出，在相差10個(gè)樣本中，DGBPSO 算法在增加樣本的情況下，表現(xiàn)的比減少樣本的實(shí)驗(yàn)好。

圖4 增加5個(gè)樣本對數(shù)據(jù)集進(jìn)行運(yùn)算使用特征重復(fù)率準(zhǔn)則得到的穩(wěn)定性結(jié)果

在增加5個(gè)樣本的基礎(chǔ)上，根據(jù)圖5可得，在數(shù)據(jù)集ALLAML、CLL_SUB_111、Prosate_GE 上，DGBPSO算法得出的結(jié)果要優(yōu)于GC和BPSO算法，數(shù)據(jù)集CLI_85 和DLBCL 上，DGBPSO 算法要略差于BPSO 算法。相較于傳統(tǒng)的BPSO 算法，在數(shù)據(jù)集ALLAML 上，提升了5.9%；在數(shù)據(jù)集CLL_SUB_111上，提升了6.4%，在數(shù)據(jù)集Prosate_GE 上提升了7.1%。

針對選擇出來的特征，在穩(wěn)定性方面有了一定的提升，如果選出的特征，卻對分類的準(zhǔn)確率沒有提高的話，實(shí)際應(yīng)用方面則受到很大的限制。為了驗(yàn)證本方法存在的有效性，筆者對上述幾種方法所得到的準(zhǔn)確率進(jìn)行了總結(jié)和概括。對于演化算法容易陷入局部最優(yōu)的特點(diǎn)，本文所提出的對數(shù)據(jù)進(jìn)行擾動(dòng)存在的可行性，只對粒子群算法進(jìn)行分組，不進(jìn)行數(shù)據(jù)擾動(dòng)的算法記作IBPSO 算法，可以所得到的結(jié)果如圖6和圖7。

圖6 使用KNN分類器對數(shù)據(jù)集進(jìn)行測試所得到的準(zhǔn)確率

圖7 使用SVM分類器對數(shù)據(jù)集進(jìn)行測試所得到的準(zhǔn)確率

根據(jù)圖6 的數(shù)據(jù)可得，DGBPSO 算法在數(shù)據(jù)集ALLAML、DLBCL、CLL_SUB_111 表現(xiàn)比GC 和BPSO 算法好。相較于BPSO 算法，數(shù)據(jù)集ALLAML 提升了5.1%，數(shù)據(jù)集DLBCL 提升了1.1%，數(shù)據(jù)集CLL_SUB_111 提升了6.3%。五個(gè)數(shù)據(jù)集中有三個(gè)數(shù)據(jù)集有較明顯提升，取得了比較好的效果。對于沒有加入數(shù)據(jù)擾動(dòng)部分的IBPSO 算法，可以看出，在數(shù)據(jù)集CLL_SUB_111 和Prosate_GE 中陷入了局部最優(yōu)化，加入數(shù)據(jù)擾動(dòng)，有了一定的提升，數(shù)據(jù)集Prosate_GE 雖沒有BPSO 效果好，但比沒有加入時(shí)提升了1.0%。

因SVM 分類器常用于二分類問題，使用SVM分類器對四個(gè)數(shù)據(jù)集進(jìn)行了分析，根據(jù)圖7 可得，在數(shù)據(jù)集ALLAML、DLBCL、Prosate_GE 中有了一定的提升。相較于BPSO 算法，DGBPSO 算法在數(shù)據(jù)集ALLAML 提升了2.5%，數(shù)據(jù)集DLBCL 提升了2.4%，Prosate_GE 數(shù)據(jù)集提升了1.2%，而在GLI_85數(shù)據(jù)集中，結(jié)合圖6，可以看到GC 算法所得到的準(zhǔn)確率更高，說明GLI_85 數(shù)據(jù)集更適合于GC 算法。對于沒有加入擾動(dòng)的IBPSO 算法，在數(shù)據(jù)集Prosate_GE 中有了一定的提升，提升效果為0.3%，其余數(shù)據(jù)集均沒有變化。說明加入擾動(dòng)部分能夠一定程度地避免算法陷入局部最優(yōu)過程中。

5 結(jié)語

為了提高高維小樣本數(shù)據(jù)特征選擇的穩(wěn)定性，筆者提出了基于特征分組和PSO的特征選擇模型，即先通過互信息對特征進(jìn)行分組，根據(jù)特征關(guān)聯(lián)性強(qiáng)弱分為不同組，待分組后，利用PSO 算法對特征進(jìn)行了選擇。為了避免粒子陷入局部最優(yōu)，在選擇過程中對少部分粒子進(jìn)行隨機(jī)擾動(dòng)。最后利用兩種穩(wěn)定性度量指標(biāo)評判所選擇特征的穩(wěn)定性。與現(xiàn)有方法相比，本算法提高了特征選擇的穩(wěn)定性，在分類精度方面，其中部分?jǐn)?shù)據(jù)集也取得更好的結(jié)果，同時(shí)滿足了特征選擇的穩(wěn)定性和分類精度，拓寬了算法的應(yīng)用范圍。