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

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

0 引言

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

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

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

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

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

1 骨架粒子群算法

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

(1)

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

(2)

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

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

2 基于多目標(biāo)骨架粒子群的特征選擇算法

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

2.1 種群的編碼、解碼與評價(jià)

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

X=[x1,x2,…,xn]

(3)

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

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

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

(4)

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

2.2 更新外部存檔

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

2.3 更新Pbest和Gbest

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

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

2.4 變異操作

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

(5)

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

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

2.5 MOBPSO算法描述

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

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

1)

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

2)

fori←1 toNdo

3)

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

4)

end

5)

評價(jià)粒子群S0，計(jì)算每個(gè)粒子的目標(biāo)值，分類錯(cuò)誤率和選擇的特征個(gè)數(shù)；

6)

計(jì)算非支配解，并對外部存檔進(jìn)行更新；

7)

whilet

8)

fori←1 toNdo

9)

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

10)

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

11)

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

12)

end

13)

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

14)

評價(jià)粒子群St+1；

15)

計(jì)算非支配解，更新外部存檔Archive；

16)

t←t+1；

17)

end

18)

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

3 性能仿真和分析

3.1 數(shù)據(jù)集以及實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

表3 三種算法最小錯(cuò)誤率比較 %

4 結(jié)語

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