基于多目標骨架粒子群優(yōu)化的特征選擇算法

張翠軍，陳貝貝，周 沖，尹心歌

(1.河北地質(zhì)大學 信息工程學院，石家莊 050031； 2.天津工業(yè)大學 管理學院，天津 300387)(*通信作者電子郵箱zc0315@foxmail.com)

0 引言

特征選擇是數(shù)據(jù)挖掘以及模式識別中一種重要的數(shù)據(jù)預處理步驟[1-2]。高維數(shù)據(jù)特征往往包含大量冗余特征、不相關的和噪聲特征。在數(shù)據(jù)分類問題中，分類性能常常被冗余的、不相關的和噪聲特征影響，并增加了計算成本。特征選擇的目的是選擇出最少的、相關的和有用的特征，以便提高分類性能和降低計算成本。

根據(jù)特征子集的選擇策略，特征選擇方法可以分為兩類：過濾式特征選擇方法[3]和封裝式特征選擇方法[4-5]。過濾式特征選擇的評價標準從數(shù)據(jù)集本身的內(nèi)部特性獲得，與學習算法無關，通常選擇與類別相關度大的特征或特征子集；封裝式特征選擇方法是利用分類算法的性能來評價特征子集的優(yōu)劣，采用搜索策略來尋找最優(yōu)子集。過濾式特征選擇方法由于特征選擇的標準與學習算法無關，不需要分類器的訓練步驟，因此其通用性比封裝式特征選擇方法強，復雜度比封裝式特征選擇方法低，但是過濾式特征子集在分類準確率方面比封裝式特征選擇方法低。

優(yōu)化技術(shù)，像進化算法(Evolutionary Algorithm, EA)、遺傳算法(Genetic Algorithm, GA)、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法、人工蜂群(Artificial Bee Colony, ABC)算法和差分進化 (Differential Evolution, DE)算法等，有很多已經(jīng)成功應用到各種應用領域的特征選擇問題[6-12]中。

大多數(shù)特征選擇問題都是針對單目標來解決的，僅考慮了算法的分類準確率，沒有考慮選擇特征子集的大小。雖然在一些單目標特征選擇研究[13-16]中，通過聚合函數(shù)形成一個目標，達到同時考慮分類性能和選擇的特征子集大小的目的，但是這樣引入了新的聚合參數(shù)，導致算法不靈活、設置參數(shù)等問題，因此，本文將特征選擇作為多目標優(yōu)化問題。特征選擇有兩個主要目標，即最大化分類準確率(最小化分類錯誤率)和最小化特征選擇的個數(shù)，由此，特征選擇問題可以表示為兩個目標的最小化問題。一般來說，這兩個目標函數(shù)是相互矛盾的，需要在它們之間進行折中來尋找最優(yōu)策略。Xue等[17]首次將改進的多目標PSO算法應用到特征選擇中，提出了一種基于PSO算法的帕累托(Pareto)前沿面特征選擇方法，并通過擁擠距離、變異操作以及支配集尋找Pareto前沿面。實驗結(jié)果表明，該方法分類性能優(yōu)于其他特征選擇方法。Xue等的算法中將融合多種策略的多目標PSO算法應用到特征選擇中，提高了算法的性能，但其存在著大量需要調(diào)節(jié)的參數(shù)，導致收斂速度過慢、計算時間長的問題，使算法的性能下降。

為了達到選擇的特征子集個數(shù)最小，且算法的分類錯誤率最小的目的，本文設計了一種基于多目標骨架粒子群(Multi-Objective Bare-bones Partivle Swarm Optimization, MOBPSO)算法用于特征選擇方法中，并通過約束機制和變異算子來提高BPSO算法的搜索能力，在算法的執(zhí)行過程中，通過外部集合記錄與維護Pareto最優(yōu)解，并通過K最近鄰(KNearest Neighbor,KNN)(K=3)方法來評估粒子的適應度值。

1 骨架粒子群算法

2003年Kennedy[18]提出了一種變異的骨架粒子群(Bare-bones Particle Swarm Optimization,BPSO)算法，它移除了速度更新公式，在搜索過程中僅使用粒子的位置信息。BPSO更新位置信息時，所有的粒子都從粒子個體歷史最優(yōu)值和全局最優(yōu)值進行學習。BPSO位置信息更新公式如式(1)所示：

(1)

其中，位置信息根據(jù)高斯分布隨機產(chǎn)生，高斯分布的均值為(Pbest+Gbest)/2，方差為|Pbest-Gbest|。Kennedy還提出了一種BPSO的變異版本BPSOE(Exploiting Bare-bones PSO), 這種方法更傾向于搜索到歷史最優(yōu)位置。位置信息更新公式如式(2)所示:

(2)

其中R是[0,1]區(qū)間的隨機數(shù)。在BPSOE中粒子有50%的機會跳到自己的最優(yōu)位置。

由于BPSO算法無需調(diào)解參數(shù)，比PSO算法更簡單，而且目前還沒有將多目標BPSO算法應用到特征選擇問題中，因此，本文提出將多目標BPSO算法應用到特征選擇方法中。

2 基于多目標骨架粒子群的特征選擇算法

本文提出了一種基于多目標骨架粒子群算法特征選擇算法，該算法結(jié)合KNN(K=3)分類器在12個數(shù)據(jù)集上進行測試。

2.1 種群的編碼、解碼與評價

種群中每個粒子對應特征選擇的一個解，粒子采用實數(shù)編碼，如式(3)所示，每個解X中包含n個實數(shù)，n為對應數(shù)據(jù)集特征的總特征數(shù)，其中每一維xi代表是否選擇該特征。

X=[x1,x2,…,xn]

(3)

為了形成特征子集，需要在解碼前進行解碼處理。粒子的位置可以轉(zhuǎn)換成如下的特征子集：

其中，Ad代表從每個解第d維解碼出來的特征子集。Ad可以根據(jù)粒子第d維特征的值xd選擇其值為0或者是1: 如果Ad=1，代表第d維特征被選擇；否則，該維特征不被選擇。

將每個粒子解碼轉(zhuǎn)換為數(shù)據(jù)集中所有特征的選擇方案，然后采用KNN(K=3)分類器對每個粒子對應的選擇方案的分類性能進行測試，并按照式(4)計算該種選擇方案對應的分類錯誤率：

(4)

其中:TP表示正樣例被分類正確的個數(shù)，TN表示負樣例被分類正確的個數(shù)，F(xiàn)P表示正樣例被分類錯誤的個數(shù)，F(xiàn)N表示負樣例被分類錯誤的個數(shù)。ER越小，表示當前特征子集的選擇方案對應的錯誤率越小。將分類錯誤率結(jié)合每個粒子的選擇的特征數(shù)作為衡量每個粒子適應度值的兩個指標。

2.2 更新外部存檔

外部存檔的作用是保存搜索過程中發(fā)現(xiàn)的所有Pareto最優(yōu)解。在每次迭代過程中，都會產(chǎn)生非支配解，這些新產(chǎn)生的非支配解將會與外部存檔中的解進行比較：如果外部存檔是空的，當前所有的非支配解都會加入到外部存檔中；如果外部存檔中存在一個個體，能夠支配當前新產(chǎn)生的非支配解，則將會丟棄這個新產(chǎn)生的非支配解，否則，將當前新產(chǎn)生的非支配解存儲到外部存檔中；如果外部存檔中存在一個個體，由新產(chǎn)生的非支配解支配，則將該個體從外部存檔中刪除；如果外部存檔中的個體數(shù)量超過最大允許的容量，則調(diào)用自適應網(wǎng)格搜索，根據(jù)粒子的密度信息選擇外部存檔中的個體。粒子所在網(wǎng)格中包含的粒子數(shù)越多，則粒子的密度值越大; 反之越小。為了保證解的多樣性，粒子的密度值越小，選擇當前粒子的概率就越大；反之概率越小。

2.3 更新Pbest和Gbest

個體最優(yōu)位置Pbest保存的是到目前為止粒子本身在搜索空間中找到的最優(yōu)解。本文采用基于支配的策略更新每個粒子Pbest的位置信息：如果一個粒子在迭代過程中的解受歷史保存的粒子最優(yōu)解支配，則保存Pbest的位置信息不變；否則，將Pbest的位置信息修改為當前的解。

全局最優(yōu)位置Gbest保存的是到目前為止種群在搜索空間中找到的最優(yōu)位置。在單目標問題中，種群只有一個Gbest；而對于多目標問題，由于各個目標之間是相互矛盾的，Gbest有很多個，但是每個粒子只能選擇一個作為Gbest，然后對粒子的位置信息進行更新。為了解決這個問題，本文應用自適應網(wǎng)格法，根據(jù)粒子的密度信息從外部存檔中隨機選擇一個作為Gbest，粒子的密度值越小，選擇該粒子作為Gbest的概率就越大。

2.4 變異操作

本文采用的變異率計算公式如式(5)所示:

(5)

其中:it為當前的迭代次數(shù)，MaxIt為最大迭代次數(shù)，mu為給定的[0,1]區(qū)間的值。

在執(zhí)行變異操作時，隨機產(chǎn)生一個[0,1]的數(shù)，如果小于變異率，則進行變異操作；否則，不進行變異操作。在粒子進行變異時，會根據(jù)新產(chǎn)生的粒子與當前粒子的支配關系進行選擇：若新產(chǎn)生的粒子受當前粒子支配時，則粒子不變；若當前粒子受新產(chǎn)生的粒子支配時，則修改為新產(chǎn)生的粒子；若兩個粒子互相非支配，則隨機選擇一個粒子。

2.5 MOBPSO算法描述

輸入 粒子群大小N，最大迭代次數(shù)MaxIt；

輸出 非支配的外部存檔解集Archive。

1)

t←0，初始化粒子群S0和外部存檔Archive；

2)

fori←1 toNdo

3)

初始化S0中粒子pi的位置；

4)

end

5)

評價粒子群S0，計算每個粒子的目標值，分類錯誤率和選擇的特征個數(shù)；

6)

計算非支配解，并對外部存檔進行更新；

7)

whilet

8)

fori←1 toNdo

9)

更新粒子的歷史最優(yōu)位置Pbest；

10)

更新全局最優(yōu)位置Gbest；

11)

根據(jù)式(1)更新粒子的位置；

12)

end

13)

對每個粒子執(zhí)行變異操作；

14)

評價粒子群St+1；

15)

計算非支配解，更新外部存檔Archive；

16)

t←t+1；

17)

end

18)

輸出外部存檔Archive中的非支配解。

3 性能仿真和分析

3.1 數(shù)據(jù)集以及實驗參數(shù)設置

本文采用的數(shù)據(jù)集均來自于UCI數(shù)據(jù)集[19]以及基因表達數(shù)據(jù)集[20]，包括zoo、wine、musk1、Ionosphere、lungcancer、parkinsons、dermatology、Alizadeh、wdbc、Hillvalley、Prostate以及9_Tumors數(shù)據(jù)集，這些數(shù)據(jù)集類別數(shù)包括兩類或多類，特征數(shù)從13到10 509，樣本數(shù)從32到1 212。這12個數(shù)據(jù)集具有一定的代表性，不僅能反映算法在特征數(shù)較少或較多情況下去除冗余特征的能力，還能夠檢測算法在樣本數(shù)不足以及樣本數(shù)非常大的情況下的優(yōu)化性能，具體信息如表1所示。實驗仿真在主頻為3.40 GHz，內(nèi)存為8.0 GB的PC機上實現(xiàn)，軟件環(huán)境為 Matlab R2016a。為了驗證算法的性能，將本文算法與兩種經(jīng)典的多目標特征選擇方法在上述數(shù)據(jù)集上進行對比，分別是由Coello等[21]在2004年提出來的多目標粒子群優(yōu)化(Multi-Objective Particle Swarm Optimization, MOPSO)算法和Deb等[22]在2002年提出的快速非支配排序遺傳算法(Non-dominated Sort Genetic Algorithm Ⅱ, NSGAⅡ)。算法的實驗參數(shù)設置如下，種群大小N設置為20，外部存檔的最大容量nrep設置為20，最大的迭代次數(shù)MaxIt設置為30。MOPSO算法中，粒子的最大速度vmax為1.0，慣性權(quán)重w為0.5，加速因子c1為2，c2為1。NSGAⅡ中，變異概率mrate為1/n,n為種群個數(shù)，交叉概率crate設置為0.9。由于采用封裝式的特征選擇方法，在訓練過程中需要一個學習算法來評價分類性能，本文采用最簡單的KNN(K=3)算法當作學習算法。

表1 數(shù)據(jù)集描述

本文實驗中，設置的訓練集為整個數(shù)據(jù)集的70%，測試集為30%，在訓練過程中，根據(jù)粒子的位置，確定選擇特征子集的個數(shù)，通過KNN(K=3)分類器并采用十折交叉驗證，計算特征子集的錯誤率，將得到的特征子集的個數(shù)和錯誤率作為粒子的適應度函數(shù)值；在測試過程中，對選出的每個特征子集進行測試，并將測試結(jié)果作為算法的最終結(jié)果。

3.2 實驗結(jié)果分析

實驗中，分別將MOBPSO算法與MOPSO算法以及NSGAⅡ在12個數(shù)據(jù)集上進行測試。MOBPSO算法與MOPSO算法以及NSGAⅡ三種多目標特征選擇方法運行結(jié)果如圖1所示。為了比較算法的計算時間，這三個算法分別運行了10次，計算了每一個算法的平均運行時間，比較結(jié)果如表2所示。

表2 三種算法在12個數(shù)據(jù)集上運行時間比較 s

在Ionosphere數(shù)據(jù)集上，樣本數(shù)為351，本文算法與NSGAⅡ都能夠找到最小的特征個數(shù)，但是應用MOBPSO算法得到的分類錯誤率比NSGAⅡ得到的分類錯誤率小。在得到的所有解中，應用MOBPSO算法特征數(shù)為10時可以得到最小的錯誤率，比整個數(shù)據(jù)集特征的個數(shù)少24個，去除了較多的冗余特征，并且在特征數(shù)為8、9、10、和11時，MOBPSO算法得到的分類錯誤率比MOPSO算法和NSGAⅡ低。在Hillvalley數(shù)據(jù)集上，數(shù)據(jù)集有足夠的樣本，為1 212，在該數(shù)據(jù)集上，本文算法在特征數(shù)為24時，可以找到最小分類錯誤率；在parkinsons數(shù)據(jù)集上，本文算法不能找到使分類錯誤率比其他兩種算法小的特征子集；在wdbc數(shù)據(jù)集上，MOBPSO可以獲得最小的分類錯誤率，需要的特征子集大小為16，其他兩個比較的算法的分類錯誤率較高；在Prostate數(shù)據(jù)集上，特征數(shù)最多，為10 509，MOBPSO可以獲得最小的分類錯誤率，需要的特征子集大小為1 079，其他兩個比較的算法的分類錯誤率較高。

圖1 MOBPSO與對比算法在12個數(shù)據(jù)集上的對比結(jié)果

在wine數(shù)據(jù)集上，該數(shù)據(jù)集的特征數(shù)較少，僅為13個，雖然NSGAⅡ在特征數(shù)為5時，得到的最小分類錯誤率與本文算法的最小分類錯誤率相等，但是本文算法選擇的特征數(shù)為4，且選擇特征數(shù)的分類錯誤率均低于MOPSO算法，但是，特征數(shù)為5以及更多時，分類錯誤率比NSGAⅡ的分類錯誤率高；在musk1數(shù)據(jù)集上，該數(shù)據(jù)集特征數(shù)為166，特征數(shù)較多，本文算法能夠找到最小的特征子集，但是分類錯誤率較高，三個算法均能夠找到使錯誤率最小的特征子集，應用本文算法僅需要32個特征，而另兩個算法分別需要51和56個，說明本文算法去除冗余特征能力比另外兩種算法強，但是，本文算法在其他特征子集上的分類錯誤率較高。因此，本文算法還需要進一步改進。

在多分類數(shù)據(jù)集zoo上，本文算法在特征數(shù)為8時，達到最小錯誤率，且在特征數(shù)為1、2、3和4時，得到的分類錯誤率均小于其他兩種算法；在lungcancer 數(shù)據(jù)集上，本文算法不能找到使分類錯誤率比其他兩種算法小的特征子集；在dermatology 數(shù)據(jù)集上，本文算法在特征數(shù)為8時，可以得到最小分類錯誤率，與其他兩種算法相比，在特征數(shù)為17和20時得到相同的最小錯誤率時，本文算法使用的特征數(shù)更少；在9_Tumors數(shù)據(jù)集上，該數(shù)據(jù)集由9類，特征數(shù)為5 726，MOBPSO可以獲得最小的分類錯誤率，需要的特征子集大小為1 046，其他兩個比較的算法的分類錯誤率較高； 在Alizadeh數(shù)據(jù)集上，MOBPSO算法在7個特征子集上，獲得了最小的分類錯誤率，相比其他兩個算法，該算法有明顯的優(yōu)勢。

對上述12個數(shù)據(jù)集分析可知，本文算法在部分數(shù)據(jù)集上去除冗余特征的能力比其他兩種算法強，但是，還存在一些數(shù)據(jù)集，本文算法不能夠達到很好的分類效果，還需要進一步的改進。表3對應三個算法在12個測試集上的最小錯誤率，其中加粗的代表在每個數(shù)據(jù)集上三種算法得到的最小錯誤率。由表3可知，本文算法在7個數(shù)據(jù)集上可以找到分類最小錯誤率，在其余數(shù)據(jù)集上雖然得到的不是三個算法中的最小錯誤率，但是與另外一種算法得到的最小錯誤率相等。從運行時間上來分析，MOBPSO在8個數(shù)據(jù)集上，計算時間最少，占比67%。因此，本文算法在去除冗余特征，得到最小特征子集，提高分類效果和降低計算時間上，具有顯著優(yōu)勢。

表3 三種算法最小錯誤率比較 %

4 結(jié)語

針對單目標解決特征選擇問題中存在的缺陷，本文把特征選擇問題作為一個多目標優(yōu)化問題，即選擇分類錯誤率和特征子集大小作為兩個目標。針對粒子群算法中調(diào)參問題，多目標骨架粒子群算法是一個少參數(shù)的算法，并且該算法還沒有應用到特征選擇中,針對這些問題，本文提出基于多目標骨架粒子群的特征選擇算法。在12個UCI數(shù)據(jù)集上得到的結(jié)果顯示，本文算法在大多數(shù)數(shù)據(jù)集上可以去除大部分冗余特征，提高算法分類效果和降低計算成本，但是，仍然存在一些數(shù)據(jù)集，不能夠取得最小分類錯誤率，仍需要進一步作改進。