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

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

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

0 引言

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

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

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

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

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

1 骨架粒子群算法

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

(1)

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

(2)

其中R是[0,1]區間的隨機數。在BPSOE中粒子有50%的機會跳到自己的最優位置。

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

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

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

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

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

X=[x1,x2,…,xn]

(3)

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

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

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

(4)

其中:TP表示正樣例被分類正確的個數，TN表示負樣例被分類正確的個數，FP表示正樣例被分類錯誤的個數，FN表示負樣例被分類錯誤的個數。ER越小，表示當前特征子集的選擇方案對應的錯誤率越小。將分類錯誤率結合每個粒子的選擇的特征數作為衡量每個粒子適應度值的兩個指標。

2.2 更新外部存檔

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

2.3 更新Pbest和Gbest

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

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

2.4 變異操作

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

(5)

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

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

2.5 MOBPSO算法描述

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

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

1)

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

2)

fori←1 toNdo

3)

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

4)

end

5)

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

6)

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

7)

whilet

8)

fori←1 toNdo

9)

更新粒子的歷史最優位置Pbest；

10)

更新全局最優位置Gbest；

11)

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

12)

end

13)

對每個粒子執行變異操作；

14)

評價粒子群St+1；

15)

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

16)

t←t+1；

17)

end

18)

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

3 性能仿真和分析

3.1 數據集以及實驗參數設置

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

表1 數據集描述

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

3.2 實驗結果分析

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

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

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

圖1 MOBPSO與對比算法在12個數據集上的對比結果

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

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

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

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

4 結語

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