巫紅霞 謝 強

1(鎮(zhèn)江市高等?？茖W校裝備制造學院 江蘇 鎮(zhèn)江 212000)2(南京航空航天大學計算機科學與技術學院 江蘇 南京 210016)

0 引 言

特征選擇是數據處理與模式識別領域的基礎性研究，其性能直接影響分類器、模式匹配等應用的分類精度與泛化性能[1]。特征選擇的目標是從特征集中選出判別性高、冗余度低的特征子集，降低數據集的維度，并降低不相關特征對數據分析的干擾，從而提高數據分析的效果與效率[2]。目前已存在大量有效的特征選擇算法，并且已經成功地應用于低維數據領域[3]，但許多特征選擇方法在高維海量或高維小樣本數據集的處理過程中，存在計算開銷過大或過學習的問題[4]。

在生物信息學、基因表達譜微陣列和圖像識別等領域中，高維小樣本數據容易引發(fā)“維數災難”和過擬合問題，成為了亟待解決的難題。高維度導致計算復雜度高且分類器性能差，樣本少則導致分類器學習效果差[5]。許多研究人員針對高維小樣本數據提出了有效的解決方案，包括結合隨機森林和鄰域粗糙集的特征選擇[6]、基于文化基因算法和最小二乘支持向量機的特征選擇[7]、基于協方差估計多元回歸的特征選擇[8]等。為了提高特征選擇的效果，文獻[6]引入了隨機森林分類與粗糙集計算，文獻[7]引入了文化基因與最小二乘SVM，文獻[8]則引入了多元回歸模型等。這些算法對所有的特征進行高復雜度的運算，導致計算成本極高，難以運用于實際的工程應用。文獻[9]的GCACO算法是一種性能較好的高維數據特征選擇算法，該算法將特征分類，然后采用ACO(Ant Colony Optimization)算法對每個特征分類進行尋優(yōu)處理。該算法將特征子集建模為完全圖，導致模型復雜度較高。

減少冗余特征與不相關特征是特征選擇的兩個目標，許多研究將減少不相關特征作為目標，而忽略了冗余特征對分類性能的干擾[10]。特征選擇主要可分為3類：過濾式、封裝式和嵌入式，過濾式方法具有結構簡單、訓練速度快、獨立于具體訓練模型的優(yōu)點。過濾式方法對于高維數據的計算速度快，因此本文采用過濾式方法。此外，本文算法同時將減少不相關特征與冗余特征作為研究目標，提出了無監(jiān)督的高維數據特征選擇算法。在特征選擇過程中采用人工蟻群算法對特征進行了高效的尋優(yōu)處理，提取出最優(yōu)的特征子集。

1 特征選擇的問題模型

常規(guī)的ACO算法一般基于完全圖進行搜索處理，但文獻[9]將特征選擇建模為完全圖，其算法復雜度較高。此外，因為特征選擇問題的搜索空間有限，所以ACO算法容易陷入局部最優(yōu)。許多高維特征選擇算法并未考慮特征之間的冗余度。針對上述問題，本文設計了新的特征選擇模型。

1.1 ACO的搜索空間表示

圖1 特征選擇問題的循環(huán)無向加權圖

1.2 特征相似性評價

采用Pearson相關系數的絕對值評估特征之間的相似性：

(1)

(2)

(3)

1.3 刪除冗余特征

許多研究[12]通過計算當前特征集與之前特征集之間的相似性來選擇冗余特征，但在一些特殊情況下，少量變化劇烈的特征導致當前特征集與之前特征集的平均相似性較低。為了避免該問題，從當前特征集中選出q個相關性最高的特征，計算q個特征與之前特征集的平均相似性。最終的平均相似性定義為：

(4)

式中:Γk為q個相似性最大的特征集；k為之前選擇的特征集大??；l為之前選擇的特征集。上述的每個特征集對應人工蟻群算法每次迭代所選擇的網絡節(jié)點集。

2 增強的蟻群優(yōu)化算法與高維特征選擇

2.1 增強蟻群算法的局部開發(fā)能力

為了防止蟻群在搜索過程中陷入局部最優(yōu)，為蟻群算法引入兩個隨機算子與一個變異算子：(1) 隨機位置(隨機決定螞蟻開始移動的節(jié)點)；(2) 隨機方向(隨機決定螞蟻的移動方向)；(3) 節(jié)點變異。

受遺傳算法的啟發(fā)，設計了變異算子來增加搜索空間的狀態(tài)數量，以防止發(fā)生早熟收斂。隨機性算子與變異算子的實現方法為：ACO的第一次迭代將蟻群隨機分布于圖中各個節(jié)點；在每次迭代中，基于變異算子的條件交叉圖中的指定節(jié)點，蟻群在新的圖模型中游走。通過評估連續(xù)兩次迭代的信息素改變率來決定是否應用變異算子，歸一化的信息素改變率定義為：

(5)

變異率決定了變異的發(fā)生概率，人工蟻群算法在早期階段具有很強的全局搜索能力，在迭代過程中局部開發(fā)能力與收斂性逐漸提高。所以本文算法在第一次迭代的變異率設為最大值0.2，在迭代過程中逐漸降低變異率，從而在全局搜索與局部開發(fā)之間尋求平衡。

2.2 增強的蟻群優(yōu)化算法

基于增強的蟻群優(yōu)化算法(Enhanced Ant Colony Optimization,EACO)的特征選擇算法如算法1所示。EACO的每次迭代中，將一個螞蟻隨機置于圖中，然后，隨機決定螞蟻的移動方向(順時針或者逆時針方向)。隨后螞蟻在循環(huán)圖中游走，直至返回起點位置。一般情況下，信息方差大的特征包含的信息更為豐富，因此選擇方差最高的特征進行狀態(tài)切換。每個節(jié)點被蟻群選擇與刪除的次數定義為特征的狀態(tài)計數器，每次迭代的結束階段更新節(jié)點的信息素值(特征狀態(tài)計數器)。在達到結束條件之后，選擇信息素最高的特征作為最終的特征集。

算法1基于EACO的特征選擇算法

輸出：基于信息素排列的特征集

2. 計算啟發(fā)式信息；

/*式(3)、式(4)*/

3. 節(jié)點的信息素初始化為常量τ0；

4. 創(chuàng)建startnodes與finalnodes兩個列表；

5. foreachtfrom 1 toIter

6.mutationrate=0.2；

/*變異率初始化為1*/

7.mutationcondition=Phr(t)-Phr(t-1)；

8. ifmutationcondition>0

9. 圖中的startnodes與finalnodes應用變異算子；

/*隨機選擇30%的節(jié)點，切換其狀態(tài)*/

10.mutationrate=mutationrate-(0.2/Iter)；

/*變異率遞減*/

11.FSCil=0；

/*初始化為0*/

12. 將蟻群隨機分布于變異圖上；

13. foreachjfrom 1 toAntsdo

14. 隨機決定螞蟻的方向；

15. 蟻群保持移動；

16. 蟻群根據狀態(tài)切換規(guī)則選擇或者取消一個節(jié)點

/*式(6)*/

17.FSCis=FSCis+1；

18. 計算信息素改變率；

/*式(5)*/

19. 更新信息素值；

/*式(9)*/

20. 基于FSC將startnodes與finalnodes兩個列表分別設為最優(yōu)節(jié)點與最差節(jié)點；

21. 特征集按信息素降序排列。

2.3 特征的狀態(tài)切換規(guī)則

特征的狀態(tài)切換規(guī)則定義為：

(6)

(7)

如果γ大于θ，那么應用概率規(guī)則：

(8)

式中:γ0為一個隨機值。

2.4 EACO的信息素更新策略

每次迭代需更新每條邊的信息素，EACO的信息素更新策略定義為：

(9)

3 基于社區(qū)檢測的并行特征選擇方法

人工蟻群算法的求解效果較好，但是計算成本較高，因此設計了基于社區(qū)檢測的并行特征選擇方法。通過加權社區(qū)檢測技術將特征集分類，對每個分類分別采用EACO并行地選擇特征集，然后設計了全局的競爭機制處理所有分類的最優(yōu)特征，選出全局最優(yōu)的特征集。本方法同時提高了特征選擇的性能與計算效率。

3.1 基于加權社區(qū)檢測的特征分類

社區(qū)檢測算法通過最大化模塊化函數實現對節(jié)點的分類處理，社區(qū)檢測算法的實現簡單、性能較好，但是并未考慮特征子集之間的判別能力差異，因此本文設計了加權的社區(qū)檢測算法。圖2為特征集的社區(qū)檢測示意圖。

圖2 社區(qū)檢測的示意圖

(1) 模塊度函數。模塊度函數評估社區(qū)劃分的質量，定義為社區(qū)內部的總邊數與網絡中總邊數的比例減去一個期望值。該期望值是將網絡設定為隨機網絡同樣的社區(qū)劃分所形成的社區(qū)內部總邊數和網絡總邊數的比例。假設一個加權網絡共有N個節(jié)點與L條邊，若將網絡分為c個社區(qū)，那么模塊度函數Q定義為：

(10)

式中:A為鄰接矩陣，Axy={0,1}，1表示節(jié)點x與y之間存在一條邊。Pxy為x與y之間邊的期望值，Cx與Cy分別為x與y的社區(qū)，δ函數定義為：

(11)

一般通過配置模型計算邊的期望值，定義為Pxy=kxky/2L，kx與ky分別為節(jié)點x與y的度。據此將式(10)改寫為：

(12)

網絡的總模塊度定義為節(jié)點對每個社區(qū)的模塊度之和：

(13)

式中：li為社區(qū)i中邊的總數量；di為社區(qū)i中節(jié)點度的總和。因此eii=li/L為社區(qū)i中邊的分數，ai=di/2L為至少一個端點在社區(qū)i中的邊分數。

(2) 加權的模塊化函數。通過最大化模塊度的社區(qū)檢測算法存在分辨率的問題，傳統(tǒng)的模塊度方法計算所有社區(qū)的模塊度qi之和，將所有社區(qū)的貢獻度視為相等。該方法傾向于將小社區(qū)組成大社區(qū)，從而實現較高的模塊度。而在高維數據特征分類的應用場景中，基于相似性將特征分類，但相似性并未反映特征的判別能力，因此傳統(tǒng)的模塊度社區(qū)檢測算法無法直接處理特征分類問題。

為了解決上述問題，通過為模塊度函數引入一個權重項來區(qū)分強弱社區(qū)。加權的模塊度函數定義為：

(14)

(15)

式中：Qw為網絡的加權模塊度；ni為社區(qū)i的節(jié)點數量。權重λi反映了社區(qū)的強度，即社區(qū)中邊與最大值的比例，λiqi表示社區(qū)之間的相似度。權重λ的作用是確保強連接社區(qū)的貢獻度被分配較高的權重，而弱連接社區(qū)的貢獻度被分配較低的權重。

(3) 最大化加權模塊度的社區(qū)檢測。首先，將網絡的各個節(jié)點設置一個社區(qū)，網絡節(jié)點總數量為N則設置N個社區(qū)。然后，采用貪婪策略遍歷每個社區(qū)，將兩個社區(qū)合并，如果合并后的加權模塊度提高，那么產生新的社區(qū)劃分結果。重復該迭代過程直至獲得最大的加權模塊度。

如果社區(qū)i與社區(qū)j合并，合并后的加權模塊度增益表示為：

ΔQw(i,j)=λcom×qcom-[λi×qi+λj×qj]

(7)

式中：qcom與λcom分別為合并后新社區(qū)的模塊度與權重。每次迭代的社區(qū)節(jié)點總數量ncom、總度數dcom、邊數lcom、總權重λcom、模塊度qcom的計算公式為：

(8)

在每次迭代的結束階段，將矩陣的第i行替換為更新后的指標值，即ni=ncom、li=lcom、di=dcom、qi=qcom、λi=λcom。算法2為基于貪婪加權模塊度的社區(qū)檢測算法。

算法2基于貪婪加權模塊度的社區(qū)檢測

/*網絡圖*/

/*最優(yōu)社區(qū)劃分結果*/

2. 計算網絡參數n,d,l,lext,Q,Qw；

4. foreachcfromNto 1 do

5. foreachi,j∈{1,2，…,c} do

6. 式(7)計算u、v的模塊度增益；

7. end for

10.Qw=ΛTQ；

/*Λ為權重向量，Q為模塊度向量*/

13. end if

14. end for

(9)

算法3社區(qū)檢測的局部優(yōu)化程序

/*最優(yōu)社區(qū)劃分結果*/

1. 計算網絡參數n,d,l,lext,Q,Qw；

3. foreachu,v∈{1,2,…,N} do

4. 式(9)計算u、v的模塊度增益；

5. end for

9. goto 第3行；

10. end if

3.2 并行隊列的特征選擇

每次循環(huán)提取每個特征類(隊列)的top-k特征；然后，應用EACO處理所選的特征子集，從中選出K0個最優(yōu)特征。然后對剩余的特征隊列重復該過程，直至選出期望數量的特征子集。雖然該步驟重復了nf/K0次，nf為選擇的特征數量，但其時間成本遠小于處理全部特征的情況，并且蟻群算法對于子圖的處理時間遠小于處理全部特征的初始圖。圖3是并行隊列的特征選擇流程圖。

圖3 并行隊列的特征選擇流程圖(K0=3)

算法4為并行隊列的特征選擇算法。算法的第1、2行為并行的特征選擇處理，通過EACO處理每個分類，獲得特征隊列。第4～8行的循環(huán)體迭代地從每個隊列中選出全局最優(yōu)的特征子集。

算法4并行隊列的特征選擇算法

/*降維的數據集*/

1. 特征分類；

2. EACO處理每個特征分類，獲得特征隊列；

3.k=nf/nc;K=K0；

4. foreachifrom 1 tokdo

5. 從每個隊列中選出top-K特征集FK；

6. 根據信息素從FK中選出top-K特征子集；

7. 更新特征隊列；

8. end for

為了實現全局地特征比較，應當將每個隊列的信息素做歸一化處理：

(13)

式中：τijl為類j中特征i的信息素；l=0與1分別對應該特征被選擇與刪除；LCj為類j的特征數量；n為特征的總數量；nc為分類的數量。

4 仿真實驗與結果分析

實驗的硬件環(huán)境為Intel Xeon CPU E5- 2650 v3@2.3 GHz處理器，軟件環(huán)境為Ubuntu 16.04 LTS操作系統(tǒng)。采用C++語言編程實現相關算法。

4.1 實驗數據集

實驗采用兩組公開數據集，第一組為UCI數據集，表1為UCI數據集的基本屬性。第二組為高維數據集[13]，表2為高維數據集的基本屬性。

表1 UCI數據集的基本屬性

表2 高維數據集的基本屬性

4.2 分類器與性能評價指標

(1) 分類器選擇 本算法是一個過濾式特征選擇算法，一般將過濾式特征選擇算法與分類器結合，通過分類的性能評價特征選擇算法的性能。為了排除不同分類器的影響，采用四種常用的分類器進行實驗，分別為SVM(支持向量機)、DT(決策樹)、KNN(k-近鄰分類器)、RF(隨機森林分類器)。

(2) 性能評價指標 根據文獻[14]，分類誤差率CER是評價特征選擇算法的有效指標，CER值越小表示分類性能越高，CER定義為：

CER=錯誤分類的樣本/樣本總數量

(15)

4.3 仿真參數設置

蟻群算法的最大迭代次數設為50，信息素揮發(fā)率設為0.2，信息素初始值設為0.2，變異特征的概率設為30%，蟻群規(guī)模設為數據的特征數量，如果數據集的特征數量大于100，統(tǒng)一將蟻群規(guī)模設為100。

4.4 分類器性能的結果

本文采用K-折交叉檢驗評估分類器的性能。本算法與其他無監(jiān)督的過濾式特征選擇算法比較，分別為HGSA[15]、FSHD[16]和BGWOFS[17]。其中：HGSA也采用了與本文算法相似的人工蟻群優(yōu)化；FSHD是一種新穎的高維數據特征選擇算法，采用正則化機制對高維度冗余做懲罰處理，通過反饋機制學習優(yōu)質的特征子集；BGWOFS則是一種基于灰狼優(yōu)化算法的特征選擇算法。

圖4-圖7分別為SVM、DT、KNN、RF四個分類器的特征選擇結果，每組實驗獨立地重復10次，計算10次CER值的平均值與標準偏差作為統(tǒng)計結果。從圖中可看出，本算法對于SpamBase、Madelon兩個模式數量較多的數據集實現了較好的分類性能，其結果優(yōu)于其他三種算法。此外，本算法那對于特征規(guī)模較大的Leukemia數據集表現出了較高的分類性能，明顯地優(yōu)于其他三個算法。最終，本文算法對于四個不同的分類器均表現出較好的分類效果，說明本算法選擇的特征集具有較好的判別能力、較低的冗余度與不相關性，并且具有較高的穩(wěn)定性。

圖6 KNN分類器的結果

圖7 RF分類器的結果

4.5 算法的時間效率

每組實驗獨立地重復10次，計算10次算法處理時間的平均值作為統(tǒng)計結果。表3是4個算法處理各個數據集的平均時間。HGSA與BGWOFS是兩個基于種群的特征選擇算法，這兩個算法的計算時間隨著特征規(guī)模的增加而劇烈增加。FSHD則是一種分布式的特征選擇算法，其計算時間隨著特征規(guī)模的增加呈現緩慢增長的趨勢。本文算法是并行算法，即使對于大規(guī)模的特征集，本文算法也能分為若干的特征子集，并行地處理每個特征子集，而人工蟻群算法分別處理每個小規(guī)模的循環(huán)無向圖，實現了合理的計算成本。

表3 4個算法處理各個數據集的平均時間 s

4.6 對高維數據集的分類器性能

上述實驗評估了本算法對于低維數據集的性能，本算法的優(yōu)勢主要在于對高維數據集的處理效果。選擇另外兩個高維數據特征選擇算法與本算法比較，分別為：BKHAFS[18]、TSSLR[19]。BKHAFS是一種新型的基于二元磷蝦群的高維數據特征選擇算法，TSSLR則是一種基于兩階段稀疏Logistic回歸的高維數據特征選擇算法。

圖8-圖11所示分別為三個高維數據特征選擇算法與SVM、DT、KNN和RF四個分類器的性能結果。每組實驗獨立地重復10次，計算10次CER值的平均值與標準偏差作為統(tǒng)計結果。從圖中可看出，本算法對于文本數據集與微陣列數據集的處理性能均優(yōu)于其他兩個算法。主要原因在于BKHAFS與TSSLR均將減少不相關特征作為目標，而忽略了冗余特征對分類性能的干擾，導致特征集中包含噪聲與冗余特征，影響了分類器的分類性能。本算法則同時將減少不相關特征與減少冗余度作為目標，實現了較好的特征提取結果。

圖8 SVM分類器的結果

圖9 NB分類器的結果

圖10 DT分類器的結果

圖11 RF分類器的結果

5 結 語

許多研究將減少不相關特征作為目標，而忽略了冗余特征對分類性能的干擾，本文將減少冗余特征與不相關特征作為特征選擇的兩個目標。人工蟻群算法的求解效果較好，但是計算成本較高，為此設計了基于社區(qū)檢測的并行特征選擇方法。通過加權社區(qū)檢測技術將特征集分類，對每個分類分別采用EACO并行地選擇特征集，然后設計了全局的競爭機制處理所有分類的最優(yōu)特征，選出全局最優(yōu)的特征集。本方法提高了特征選擇的性能，實現了合理的計算效率。

本算法采用Pearson相關系數作為特征相似性的度量指標，未來將重點研究針對特定數據類型的相似性度量方法，從而提高特定應用問題的特征選擇效果。