面向特征選擇問(wèn)題的協(xié)同演化方法

滕旭陽(yáng)，董紅斌，孫靜

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

面向特征選擇問(wèn)題的協(xié)同演化方法

滕旭陽(yáng)，董紅斌，孫靜

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

特征選擇技術(shù)是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘任務(wù)的關(guān)鍵預(yù)處理技術(shù)。傳統(tǒng)貪婪式特征選擇方法僅考慮本輪最佳特征，從而導(dǎo)致獲取的特征子集僅為局部最優(yōu)，無(wú)法獲得最優(yōu)或者近似最優(yōu)的特征集合。進(jìn)化搜索方式則有效地對(duì)特征空間進(jìn)行搜索，然而不同的進(jìn)化算法在搜索過(guò)程中存在自身的局限。本文吸取遺傳算法(GA)和粒子群優(yōu)化算法(PSO)的進(jìn)化優(yōu)勢(shì)，以信息熵度量為評(píng)價(jià)，通過(guò)協(xié)同演化的方式獲取最終特征子集。并提出適用于特征選擇問(wèn)題特有的比特率交叉算子和信息交換策略。實(shí)驗(yàn)結(jié)果顯示，遺傳算法和粒子群協(xié)同進(jìn)化(GA-PSO)在進(jìn)化搜索特征子集的能力和具體分類(lèi)學(xué)習(xí)任務(wù)上都優(yōu)于單獨(dú)的演化搜索方式。進(jìn)化搜索提供的組合判斷能力優(yōu)于貪婪式特征選擇方法。

特征選擇；遺傳算法；粒子群優(yōu)化；協(xié)同演化：比特率交叉

特征選擇在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中不僅可以減少數(shù)據(jù)的維度，降低所需處理的數(shù)據(jù)量，而且還可以提升某些學(xué)習(xí)算法的表現(xiàn)[1]，比如：分類(lèi)學(xué)習(xí)、聚類(lèi)、回歸問(wèn)題和時(shí)間序列預(yù)測(cè)等。然而維數(shù)據(jù)特征選擇面臨著特別龐大的搜索空間等，當(dāng)存在n維特征時(shí)解的搜索空間為2n，因此窮舉搜索是不可行的[2]。特征選擇方法大致可分為3類(lèi)：過(guò)濾式(filter)、包裹式(wrapper)和嵌入式(embedding)[3]。過(guò)濾式方法與具體學(xué)習(xí)方法無(wú)關(guān)，主要依據(jù)數(shù)據(jù)的內(nèi)在屬性對(duì)特征進(jìn)行過(guò)濾，再用選擇出的特征訓(xùn)練模型。包裹式方法將最終要使用的學(xué)習(xí)器的學(xué)習(xí)性能作為評(píng)價(jià)子集評(píng)價(jià)標(biāo)準(zhǔn)。嵌入式方法將特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程融為一體，兩者在同一過(guò)程中優(yōu)化。wrapper方法對(duì)于具體學(xué)習(xí)器效果好，但其計(jì)算代價(jià)高，泛化能力差。filter方法雖然在具體學(xué)習(xí)方法中精度低于wrapper方法，但其泛化能力強(qiáng)，計(jì)算效率高，在大規(guī)模數(shù)據(jù)集上更加適用。因此，本文選用基于信息熵度量的filter評(píng)價(jià)方式。

為了保證搜索的高效，許多學(xué)者選擇了貪婪式搜索方法來(lái)選擇子集，代表性方法有基于信息增益的方法(IG)[4]和基于信息比率的方法(GR)[5]。然而貪婪方法無(wú)可避免地導(dǎo)致其結(jié)果為局部最優(yōu)，因?yàn)槠湓谶x擇過(guò)程中僅考慮當(dāng)前輪的單個(gè)最佳或最差特征[6]。為了解決上述問(wèn)題，全局搜索的方式則成為特征選擇問(wèn)題中一種有效的尋優(yōu)方式。演化計(jì)算作為一種具有良好全局搜索能力的代表技術(shù)近年來(lái)被越來(lái)越多地使用在特征選擇技術(shù)中[7]。隨著各個(gè)領(lǐng)域內(nèi)數(shù)據(jù)維度不斷地增加，自2007后遺傳算法(genetic algorithm,GA)與粒子群優(yōu)化(particle swarm optimization，PSO)成為特征選擇進(jìn)化搜索策略中兩個(gè)主流的全局搜索方法，特別是PSO方法因其搜索速度得到了廣泛的使用。Peng等[8]在2005年提出了最大相關(guān)最小冗余的特征選擇方法(mRmR)，該方法使用了貪婪式搜索方式。在2011年和2012年學(xué)者們驗(yàn)證了使用mRmR進(jìn)行度量并采取群智能進(jìn)化搜索的方式可以獲得更優(yōu)的特征子集[9,10]。

雖然在特征選擇問(wèn)題中演化算法的搜索能力優(yōu)于貪婪式搜索，但不同的演化算法自身也存在局限性。因此更多的學(xué)者開(kāi)始研究協(xié)同演化的方法，其中包括策略的協(xié)同[11]和種群的協(xié)同[12]。本文選用GA與PSO兩種進(jìn)化種群的協(xié)同。PSO 的優(yōu)勢(shì)在于對(duì)解的記憶能力強(qiáng)及高效的收斂速度，但該方法極容易陷入到局部最優(yōu)解，表現(xiàn)出極強(qiáng)的趨同性和較低的種群多樣性。GA方法中染色體之間共享信息，種群較為均勻地移動(dòng)并保持多樣性，但其收斂速度相對(duì)較慢。因此，本文提出了一種面向特征選擇問(wèn)題的協(xié)同演化方法(GA-PSO)，演化過(guò)程中既保證了全局搜索能力以防止陷入局部最優(yōu)，又提升了演化速度。

1 基礎(chǔ)知識(shí)

1.1 特征選擇

數(shù)據(jù)集D中含有k個(gè)樣本D={x1,x2,…,xk}，并且D中的每個(gè)樣本都有特征集合F，F(xiàn)包含n維特征，xi∈Rn。對(duì)于分類(lèi)問(wèn)題，可將D中樣本劃分為目標(biāo)向量C中的m個(gè)不同的類(lèi)C={C1,C2,…,Cm}。特征選擇的目的，是在原始特征集合N中尋找到一個(gè)最佳特征子集P，其中含有p維特征(p

特征選擇處理包括4個(gè)組件：特征子集生成、子集評(píng)估、終止條件和結(jié)果驗(yàn)證。如圖1所示，在階段1中根據(jù)一個(gè)確定的搜索策略特征子集生成組件會(huì)預(yù)先產(chǎn)生候選特征子集。每一個(gè)候選特征子集都會(huì)被一個(gè)確定的評(píng)估方式所度量，并與之前最佳的候選特征子集做比較，如果新的特征子集表現(xiàn)得更加優(yōu)越，那么替換原有的最佳特征子集。當(dāng)滿足設(shè)定的終止條件時(shí)，生成和評(píng)估這兩個(gè)過(guò)程將不再循環(huán)。在階段2中，最終所選的特征子集需要被一些給定的學(xué)習(xí)算法進(jìn)行結(jié)果驗(yàn)證，其中ACC為學(xué)習(xí)正確率[3]。

圖1 特征選擇處理的統(tǒng)一視角Fig.1 A unified view of feature selection process

1.2 遺傳算法基本原理

遺傳算法作為一種自適應(yīng)全局優(yōu)化搜索算法，其選擇、交叉與變異的3個(gè)算子成為種群尋優(yōu)和保持解多樣性的關(guān)鍵。其基本執(zhí)行過(guò)程如下。

1) 初始化：確定種群規(guī)模N、交叉概率Pcross、變異概率Pmutation和終止進(jìn)化準(zhǔn)則。

2) 個(gè)體評(píng)價(jià)：計(jì)算每個(gè)個(gè)體的適應(yīng)度。

3) 種群進(jìn)化：

①選擇算子：個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。

②交叉算子：根據(jù)交叉概率Pcross對(duì)2條染色體交換部分基因，構(gòu)造下一代新的染色體。

③變異算子：根據(jù)概率Pmutation對(duì)群體中的不同個(gè)體指定的基因位進(jìn)行改造。

④終止檢驗(yàn)：如已滿足終止準(zhǔn)則，則輸出最優(yōu)解；否則轉(zhuǎn)到2)。

1.3 二元粒子群優(yōu)化基本原理

粒子群優(yōu)化算法，源于對(duì)鳥(niǎo)群捕食的行為研究，是由Kennedy和Eberhart等[13]開(kāi)發(fā)的一種新的進(jìn)化算法。粒子在搜索空間內(nèi)尋優(yōu)，并定位當(dāng)前路徑中的最佳位置。每一個(gè)粒子都需要考慮自身當(dāng)前的位置和速度，記錄它們自己的最優(yōu)解(最佳位置)pbset，并根據(jù)粒子群體內(nèi)全局最優(yōu)解gbest調(diào)整當(dāng)前自身位置，粒子的具體更新如下：

基于上述研究，學(xué)者Kennedy調(diào)整了連續(xù)PSO方法中速度和位置的更新方式，提出了適用于解決離散問(wèn)題的二元粒子群算法(binary particle swarm optimization，BPSO)[14]。該思想中的粒子僅可以在二元空間中進(jìn)行搜索，粒子的位置向量?jī)H可以用0或1表示。BPSO方法中影響其尋優(yōu)能力的關(guān)鍵之一就是轉(zhuǎn)換函數(shù)，利用該函數(shù)將連續(xù)的速度值轉(zhuǎn)化為離散的位置。在最初的研究中使用式(3)中的sigmoid函數(shù)作為轉(zhuǎn)換函數(shù)將實(shí)值的速度映射為[0,1]之間的值。

2 求解特征子集的協(xié)同演化方法

2.1 編碼方式

本文使用了二進(jìn)制比特串的編碼方式，該編碼方式通用于遺傳算法和二元粒子群方法，如圖2所示。將每個(gè)二進(jìn)制串作為一個(gè)個(gè)體(粒子)，個(gè)體(粒子)中的每一維(每一比特)都代表一個(gè)候選特征，當(dāng)該位為1時(shí)表示該特征被選中，并添加到候選的特征子集中；當(dāng)該位為0時(shí)表示該特征未被選中。依據(jù)此編碼方式將特征選擇問(wèn)題轉(zhuǎn)換為尋找最佳個(gè)體(粒子)的問(wèn)題。

圖2 二元粒子群的編碼方式Fig.2 Coding scheme of BPSO

2.2 適應(yīng)度函數(shù)

本文使用互信息熵理論對(duì)特征子集進(jìn)行整體評(píng)估，兩個(gè)變量的互信息值越大，則意味著兩個(gè)變量相關(guān)程度越緊密；當(dāng)互信息為零時(shí)，則意味著兩個(gè)變量完全不相關(guān)。特征集合F={f1,f2,…,fn}中某一特征fi與類(lèi)別的互信息度量如下：

式中：H為變量的熵值，用以度量隨機(jī)變量信息的不確定性。以類(lèi)別向量為例，H(C)通常用作描述離散隨機(jī)變量C={c1,c2,…,cn}熵值，ci是變量C的可能取值，p(ci)為概率密度函數(shù)。

當(dāng)已知特征變量和類(lèi)別變量fi和C的聯(lián)合概率密度時(shí)(對(duì)于離散數(shù)據(jù)意味著兩個(gè)變量對(duì)應(yīng)的屬性值聯(lián)合出現(xiàn)的頻度)，兩者的聯(lián)合熵為

基于特征與類(lèi)別向量的信息熵度量構(gòu)建適應(yīng)度函數(shù)，適應(yīng)度函數(shù)的度量體現(xiàn)了進(jìn)化過(guò)程對(duì)優(yōu)良個(gè)體的保留，對(duì)低劣個(gè)體的淘汰。本文在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)不僅考慮了特征與類(lèi)別的相關(guān)性，而且將特征子集規(guī)模也作為影響個(gè)體(粒子)適應(yīng)度的一部分，適應(yīng)度函數(shù)的設(shè)計(jì)試圖找出子集規(guī)模小，并且特征與類(lèi)別高度相關(guān)的特征集合。具體適應(yīng)度函數(shù)設(shè)計(jì)如下：

式中：MI部分為特征與類(lèi)別關(guān)聯(lián)性度量；S部分為特征子集規(guī)?？刂?。假設(shè)當(dāng)前候選特征子集為在全部n維特征中選出的p維特征：

本文設(shè)計(jì)式(8)和式(9)兩個(gè)適應(yīng)度函數(shù)，在尋優(yōu)過(guò)程中試圖尋找最大值。其原理在于，小規(guī)模數(shù)據(jù)集特征維度較少，在進(jìn)化過(guò)程中對(duì)特征空間搜索較為全面。采用式(8)重點(diǎn)考察特征與類(lèi)別的相關(guān)性。而對(duì)于大規(guī)模數(shù)據(jù)集，特征維度較大，進(jìn)化搜索特征空間的過(guò)程中很難控制特征子集規(guī)模，并且容易在候選特征較多時(shí)形成局部最優(yōu)，所以在式(9)中增大了對(duì)特征子集規(guī)模的懲罰系數(shù)。假設(shè)式(8)和式(9)獲得相同的適應(yīng)度函數(shù)值，式(9)需要盡量減小k值，使得選擇特征盡量少以取得關(guān)聯(lián)性度量和子集規(guī)模的平衡。

2.3 比特率交叉算子

在遺傳算法中,交叉算子通過(guò)模擬自然界生物的雜交過(guò)程對(duì)個(gè)體進(jìn)行交叉操作，不斷產(chǎn)生新個(gè)體、增加種群的多樣性、擴(kuò)大尋優(yōu)范圍，從而使得遺傳算法具有較強(qiáng)的搜索能力。直觀地講，交叉算子影響了遺傳算法對(duì)求解空間影響的搜索能力，并對(duì)能否找到全局最優(yōu)解發(fā)揮了至關(guān)重要的作用[15]。

傳統(tǒng)的GA算法交叉操作采用的是單點(diǎn)交叉，但是在該交叉操作中很可能出現(xiàn)“近親繁殖”的現(xiàn)象，即進(jìn)行交叉操作的一對(duì)個(gè)體基因型相似，減緩了遺傳算法的搜索速度，或者會(huì)出現(xiàn)局部收斂或早熟收斂，從而影響種群的進(jìn)化方向。因此本文針對(duì)特征選擇問(wèn)題提出了比特概率交叉算子，在基因交叉的過(guò)程中，首先判斷兩個(gè)個(gè)體的基因相似比特率，并將比特率與交叉概率作比較，若小于該概率則進(jìn)行個(gè)體基因交叉操作。具體過(guò)程如算法1所示。

算法1 比特概率交叉算子

輸入 兩個(gè)個(gè)體的二進(jìn)制比特基因信息位f(i,:)和f(j,:)，染色體長(zhǎng)度n，交叉概率Pcross。

輸出 交叉后兩個(gè)個(gè)體的基因型f(i,:)和f(j,:)。

1)m=0。

2)Fork=1:n。

3)若兩個(gè)體的第k位比特位相同則m=m+1。

4)End For。

5)計(jì)算個(gè)體間基因型相似比s=m/n。

6)Ifs

7)隨機(jī)選定基因型個(gè)體的某一位Poscross。

8)Forh=Poscross:n。

9)交換個(gè)體Poscross位到第n位的基因。

10)End For。

11)End If。

通過(guò)比特率交叉算子可以避免基因型相近的個(gè)體進(jìn)行交叉操作，即可以避免產(chǎn)生“隱性致病基因”，防止相近個(gè)體的近親繁殖，并增強(qiáng)種群個(gè)體的多樣性。

2.4 GA-PSO協(xié)同演化方法的實(shí)現(xiàn)

本文提出的GA-PSO算法的主要思想是比特位信息交互。傳統(tǒng)的PSO特征選擇有一定的缺陷，比較容易陷入全局最優(yōu)解并且過(guò)早收斂，進(jìn)化過(guò)程中會(huì)將搜索引向本次迭代的全局和個(gè)體最佳位置，因此進(jìn)化的多樣性差。協(xié)同的思想對(duì)于PSO特征選擇方法的幫助在于，通過(guò)本文提出的最佳個(gè)體比特信息位交換策略，每次進(jìn)化產(chǎn)生最佳個(gè)體的比特信息位不僅僅由PSO決定，事實(shí)上它和GA中的最佳個(gè)體共享那些能夠引起適應(yīng)度值增加的優(yōu)秀比特信息位。將這些優(yōu)秀的比特基因隨機(jī)地插入到粒子群中最佳個(gè)體對(duì)應(yīng)的信息位上。這種方法不僅有可能使最佳個(gè)體變得更優(yōu)秀，還為PSO算法增加了多樣性，避免過(guò)早地陷入局部最優(yōu)解。對(duì)于GA特征選擇方法來(lái)說(shuō)，尋優(yōu)速度較慢，尤其在高維特征下往往不能獲得令人滿意的結(jié)果。從信息共享機(jī)制來(lái)說(shuō)，遺傳算法的信息共享方式主要是通過(guò)兩個(gè)個(gè)體之間的交叉操作，而粒子群算法的信息共享方式是通過(guò)種群中的最優(yōu)個(gè)體傳遞信息給其余個(gè)體。這兩種信息共享機(jī)制就相應(yīng)地決定了兩種算法的表現(xiàn)，粒子群算法每代都選出當(dāng)前最優(yōu)個(gè)體，并進(jìn)行全局范圍的信息共享，使得整個(gè)粒子群能向著最優(yōu)的方向快速趨近；而遺傳算法的交叉操作具有一定的隨機(jī)性，且由于是一對(duì)一進(jìn)行交叉，每一次迭代中作用的范圍相對(duì)較小，使得種群中的優(yōu)秀基因交流較慢，整個(gè)種群的進(jìn)化比較漫長(zhǎng)，所以PSO特征選擇尋優(yōu)速度較快，效率更高。通過(guò)信息交互，在迭代過(guò)程中種群可以獲得更為優(yōu)秀的個(gè)體基因型，這有助于加速GA種群的進(jìn)化過(guò)程，提高收斂速度。同時(shí)，通過(guò)上文的比特率交叉算子可以避免相近的基因型交叉產(chǎn)生不“健康”的后代個(gè)體。具體的GA-PSO協(xié)同演化算法如算法2和算法3所示。

算法2 協(xié)同演化算法

輸入 粒子群和種群初始化參數(shù)。

輸出 最佳個(gè)體。

1)初始化粒子群和種群。

2)協(xié)同演化。

①計(jì)算各個(gè)粒子的適應(yīng)度值。

②選擇粒子群算法最佳個(gè)體PSObest。

③選出遺傳算法最佳個(gè)體GAbest。

④最佳個(gè)體比特信息位交換。

⑤PSO：更新粒子速度及位置。

⑥GA: 選擇、比特率交叉(算法1)和變異。

3)判斷終止條件，若不滿足返回2)，滿足進(jìn)入4)。

4)比較GAbest與PSObest，輸出最佳個(gè)體。

算法3 最佳個(gè)體比特信息位交換

輸入 上一代最佳個(gè)體和本輪最佳個(gè)體。

輸出 交換比特信息位后的PSObest及HSbest。

1) 隨機(jī)選取PSO中引起最佳個(gè)體適應(yīng)度值增加的信息位PSObit。

2) 隨機(jī)選取GA中引起最佳個(gè)體適應(yīng)度值增加的信息位GAbit。

3) if PSObest優(yōu)于 GAbest，

將GAbest中對(duì)應(yīng)的信息位改為PSObit;

else

將PSObest中對(duì)應(yīng)的信息位改為GAbit;

end

本文提出的GA-PSO協(xié)同演化算法，通過(guò)協(xié)同共享的思想讓PSO和GA互相彌補(bǔ)各自的弱點(diǎn)，互相協(xié)助從而產(chǎn)生更強(qiáng)的個(gè)體。對(duì)于本文面向的特征選擇問(wèn)題，更好的個(gè)體可以從兩個(gè)角度進(jìn)行判斷：特征與類(lèi)別相關(guān)性越高，個(gè)體適應(yīng)度值越高；特征子集規(guī)模越小，個(gè)體適應(yīng)度值越高。面向特征選擇問(wèn)題的協(xié)同演化方法執(zhí)行流程如圖3所示。

圖3 協(xié)同演化算法的流程圖Fig.3 Flow chart of co-evolution algorithm

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

為了驗(yàn)證本文提出算法的有效性，實(shí)驗(yàn)結(jié)果從兩個(gè)方面進(jìn)行分析：1)分析算法在不同數(shù)據(jù)集下分類(lèi)的準(zhǔn)確率；2)提出的算法與GA和PSO進(jìn)行適應(yīng)度值和收斂性比較。本文實(shí)驗(yàn)特征選擇部分的運(yùn)行環(huán)境為MATLAB 2014a,分類(lèi)準(zhǔn)確率運(yùn)行環(huán)境為weka3.8。對(duì)數(shù)據(jù)的離散化處理采用經(jīng)典的MDL方法。種群規(guī)模為20，迭代次數(shù)為300。GA中交叉概率為0.6，變異概率為0.15；PSO中c1=c2=2，w=0.4。

3.1 算法分類(lèi)準(zhǔn)確率的結(jié)果分析

本文實(shí)驗(yàn)部分選用了UCI(UC Irvine machine learning repository)數(shù)據(jù)庫(kù)中的5個(gè)高維多類(lèi)別數(shù)據(jù)集，特征維度從14維升至240維，不同數(shù)據(jù)集中樣本的類(lèi)別數(shù)目最少為2類(lèi)，最多為10類(lèi)。其中,Australian與Credit Approval為兩個(gè)信用卡申請(qǐng)類(lèi)數(shù)據(jù)集，Dermatology為皮膚病數(shù)據(jù)集，Synthetic Control是名為合成控制圖數(shù)據(jù)集，Multi-Feature Pixel是名為Multi-feature “0”到“9” 手寫(xiě)圖數(shù)據(jù)集中的一個(gè)子集合。各數(shù)據(jù)集的詳細(xì)信息如表1所示。

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

實(shí)驗(yàn)對(duì)比的特征選擇算法有GA、PSO、IG以及GR。為了驗(yàn)證算法性能，選取SVM、1-NN和Na?ve Bayes 三個(gè)分類(lèi)器，并且使用十折交叉驗(yàn)證的方法測(cè)試在不同數(shù)據(jù)集下各個(gè)算法所選擇特征子集的分類(lèi)。對(duì)于GA,PSO和GA-PSO三種進(jìn)化搜索的方法，實(shí)驗(yàn)得出每個(gè)算法連續(xù)運(yùn)行20次時(shí)的平均分類(lèi)準(zhǔn)確率。而IG(information gain)信息增益和GR(gain ratio)增益比率都是以互信息為基礎(chǔ)的經(jīng)典的排序特征選擇算法，因此在實(shí)驗(yàn)中分別對(duì)每個(gè)數(shù)據(jù)集的特征進(jìn)行排序，并且手動(dòng)地選擇與進(jìn)化算法規(guī)模相近的排名前p個(gè)特征，p為選擇的特征數(shù)量。具體的分類(lèi)結(jié)果如表2～4所示。表2～4中數(shù)值表示各特征選擇算法選擇的特征子集在相應(yīng)的數(shù)據(jù)集下使用分類(lèi)器得到的分類(lèi)準(zhǔn)確率。Avg表示平均分類(lèi)準(zhǔn)確率，括號(hào)內(nèi)數(shù)字為平均選擇的子集規(guī)模。

從表2中可以看出，本文提出的方法在5個(gè)數(shù)據(jù)集上均取得了最好的結(jié)果，比如在Synthetic Control數(shù)據(jù)集中，在選出相近的特征子集下，提出的方法的平均分類(lèi)準(zhǔn)確率比其他算法的平均分類(lèi)準(zhǔn)確率高出了平均2.98%。同樣如表3和表4所示，在1-NN和Na?ve Bayes分類(lèi)器中，對(duì)于每個(gè)數(shù)據(jù)集本文提出的方法的平均分類(lèi)準(zhǔn)確率都比其他的算法具有優(yōu)勢(shì)，在保證特征子集近似的情況下，能夠得到較好的分類(lèi)效果。

表2 1-NN分類(lèi)器的分類(lèi)準(zhǔn)確率

表3 SVM分類(lèi)器的分類(lèi)準(zhǔn)確率

表4 Na?ve Bayes分類(lèi)器的分類(lèi)準(zhǔn)確率

綜合GA-PSO在SVM、KNN和Na?ve Bayes 三個(gè)分類(lèi)器下的表現(xiàn)，本實(shí)驗(yàn)結(jié)果驗(yàn)證了GA-PSO算法在不同規(guī)模數(shù)據(jù)集下分類(lèi)性能的有效性，從分類(lèi)準(zhǔn)確率的角度評(píng)定本文提出的GA-PSO算法優(yōu)于傳統(tǒng)的GA和PSO進(jìn)化算法，也優(yōu)于經(jīng)典的特征選擇排序算法，平均分類(lèi)精度有明顯提升。

3.2 算法適應(yīng)度值的分析

在進(jìn)化算法中，對(duì)于求最大化的目標(biāo)函數(shù)而言，適應(yīng)度值高的個(gè)體能夠在最大的程度上得到保留。適應(yīng)度值高的個(gè)體的基因型對(duì)種群的進(jìn)化方向起著指導(dǎo)作用。因此對(duì)于不同的演化方法，另一個(gè)評(píng)定的角度是在同一個(gè)適應(yīng)度函數(shù)作用下比較哪種算法能夠得到更高的適應(yīng)度值的個(gè)體。為了分析比較提出算法在進(jìn)化過(guò)程中適應(yīng)度值的變化情況，分別畫(huà)出了GA-PSO、GA和PSO算法在Synthetic Control、Dermatology和Multi-Feature Pixel數(shù)據(jù)集下單次迭代過(guò)程中適應(yīng)度函數(shù)值的折線圖，如圖4～6所示。

圖4 Dermatology 數(shù)據(jù)集中的對(duì)比Fig.4 Comparison on Dermatology

圖5 Synthetic Control數(shù)據(jù)集中的對(duì)比Fig.5 Comparison on Synthetic Control

圖6 Multi-Feature Pixel數(shù)據(jù)集中的對(duì)比Fig.6 Comparison on Multi-Feature Pixel

對(duì)適應(yīng)度值的分析：通過(guò)圖4可以看出,在0～150代GA-PSO保持著GA近似水平的適應(yīng)度值，PSO的適應(yīng)度值稍高，在150代以后GA-PSO和GA適應(yīng)度值逐步提升，超過(guò)PSO，最終GA-PSO得到最高的適應(yīng)度值;在圖5中，在240代后GA-PSO超過(guò)GA和PSO，最終GA-PSO取得最高的適應(yīng)度值；在圖6的超高維數(shù)據(jù)集中，GA-PSO的尋優(yōu)優(yōu)勢(shì)更加明顯。GA-PSO比傳統(tǒng)的進(jìn)化算法PSO和GA具有更強(qiáng)的搜索能力，在相同條件下總是能保持進(jìn)化以找到更優(yōu)的個(gè)體。

對(duì)收斂性的分析：隨著特征規(guī)模的增大，PSO總是過(guò)早收斂，這說(shuō)明PSO算法容易陷入局部最優(yōu)解，尤其對(duì)于高維特征數(shù)目的數(shù)據(jù)集，PSO不能保證良好的全局搜索；GA的全局搜索能力要優(yōu)于PSO；GA-PSO則一直保持著良好的搜索能力，尤其在大規(guī)模數(shù)據(jù)集中，GA-PSO的表現(xiàn)更為突出，在300代以內(nèi)，適應(yīng)度值一直保持著提升，能夠有效地避免陷入全局最優(yōu)解。

綜上所述，本文所提出的算法在進(jìn)化過(guò)程中能夠產(chǎn)生比較優(yōu)秀的個(gè)體，獲得比較高的適應(yīng)度值，從而可以取得更好的分類(lèi)準(zhǔn)確率。這證明了，GA-PSO算法在進(jìn)化過(guò)程中逐步尋優(yōu)的能力，能夠找出相對(duì)優(yōu)秀的特征子集。

4 結(jié)束語(yǔ)

本文提出了面向特征選擇問(wèn)題的協(xié)同演化算法GA-PSO。為了保證種群多樣性，提出了一種基于比特率的交叉算子。針對(duì)GA和PSO尋優(yōu)的不同特點(diǎn)進(jìn)行共同演化，并將影響最佳個(gè)體形成的比特基因位作為公共信息實(shí)現(xiàn)共享。通過(guò)實(shí)驗(yàn)對(duì)比驗(yàn)證了協(xié)同演化的方法要優(yōu)于單一進(jìn)化的方法，并且驗(yàn)證了全局搜索的特征選擇方法優(yōu)于傳統(tǒng)的貪婪式特征選擇方法。本文的研究不僅可以有效地解決特征選擇問(wèn)題，在其他的組合優(yōu)化離散問(wèn)題中也可以使用該思路進(jìn)行協(xié)同演化。未來(lái)將進(jìn)一步研究子集規(guī)模的自適應(yīng)控制以及其他適應(yīng)度評(píng)價(jià)方法。

[1]DASH M, LIU H. Feature selection for classification[J]. Intelligent data analysis, 1997, 1(1/2/3/4): 131-156.

[2]GUYON I, ELISSEEFF A. An introduction to variable and feature selection[J]. The journal of machine learning research, 2002, 3(6): 1157-1182.

[3]ZHAO Zheng, MORSTATTER F, SHARMA S, et al. Advancing feature selection research. ASU feature selection repository[R]. Phoenix: School of Computing, Informatics, and Decision Systems Engineering, Arizona State University, Tempe, 2010.

[4]BATTITI R. Using mutual information for selecting features in supervised neural net learning[J]. IEEE transactions on neural networks, 1994, 5(4): 537-550.

[5]YANG Yiming, PEDEREN J O. A comparative study on feature selection in text categorization[C]//Proceedings of the 14th International Conference on Machine Learning. San Francisco, CA, USA 1997: 412-420.

[6]周志華. 機(jī)器學(xué)習(xí)[M]. 北京: 清華大學(xué)出版社, 2016: 247-266.

[7]XUE Bing, ZHANG Mengjie, BROWNE W N, et al. A survey on evolutionary computation approaches to feature selection[J]. IEEE transactions on evolutionary computation, 2016, 20(4): 606-626.

[8]PENG Hanchuan, LONG Fuhui, DING C. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 27(8): 1226-1238.

[9]UNLER A, MURAT A, CHINNAM R B. Mr2PSO: a maximum relevance minimum redundancy feature selection method based on swarm intelligence for support vector machine classification[J]. Information sciences, 2011, 181(20): 4625-4641.

[10]CERVANTE L, XUE Bing, ZHANG Mengjie, et al. Binary particle swarm optimisation for feature selection: a filter based approach[C]//Proceedings of 2012 IEEE Congress on Evolutionary Computation. Piscataway. Brisbane, Australia, 2012: 1-8.

[11]DONG Hongbin, TENG Xuyang, ZHOU Yang, et al. Feature subset selection using dynamic mixed strategy[C]// Proceedings of 2015 IEEE Congress on Evolutionary Computation. Sendai, Japan, 2015: 672-679.

[12]NEMATI S, BASIRI M E, GHASEM-AGHAEE N, et al. A novel ACO-GA hybrid algorithm for feature selection in protein function prediction[J]. Expert systems with applications, 2009, 36(10): 12086-12094.

[13]KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of 1995 IEEE International Conference on Neural Networks. Perth, Australia, 1995: 1942-1948.

[14]KENNEDY J, EBERHART R. A discrete binary version of the particle swarm algorithm[C]//Proceedings of 1997 IEEE International Systems, Man, and Cybernetics. Orlando, USA, 1997: 4104-4108.

[15]李書(shū)全, 孫雪, 孫德輝, 等. 遺傳算法中的交叉算子的述評(píng)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(1): 36-39. LI Shuquan, SUN Xue, SUN Dehui, et al. Summary of crossover operator of genetic algorithm[J]. Computer engineering and applications, 2012, 48(1): 36-39.

Co-evolutionary algorithm for feature selection

TENG Xuyang， DONG Hongbin， SUN Jing

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Feature selection is a key preprocessing technology of machine learning and data mining. The traditional greed type of feature selection methods only considers the best feature of the current round, thereby leading to the feature subset that is only locally optimal. Realizing an optimal or nearly optimal feature set is difficult. Evolutionary search means can effectively search for a feature space, but different evolutionary algorithms have their own limitations in search processes. The evolutionary advantages of genetic algorithms (GA) and particle swarm optimization (PSO) are absorbed in this study. The final feature subset is obtained by co-evolution, with the information entropy measure as an assessment function. A specific bit rate cross operator and an information exchange strategy applicable for a feature selection problem are proposed. The experimental results show that the co-evolutionary method (GA-PSO) is superior to the single evolutionary search method in the search ability of the feature subsets and classification learning. In conclusion, the ability of combined evaluation, which is provided by an evolutionary search, is better than that of the traditional greedy feature selection method.

feature selection; genetic algorithm (GA); particle swarm optimization (PSO); co-evolution; bit rate cross

滕旭陽(yáng)，男，1987年生，博士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、智能優(yōu)化算法。

董紅斌，男，1963年生，教授，博士生導(dǎo)師，主要研究方向?yàn)槎嘀悄荏w系統(tǒng)、機(jī)器學(xué)習(xí)。

孫靜，女，1993年生，碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘。

10.1992/tis.201611029

http://kns.cnki.net/kcms/detail/23.1538.TP.20170302.1522.002.html

2016-11-19.

日期：2017-03-02.

國(guó)家自然科學(xué)基金項(xiàng)目(61472095，61502116)；黑龍江省教育廳智能教育與信息工程重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目.

孫靜. E-mail：sunjing@hrbeu.edu.cn.

TP301

A

1673-4785(2017)01-0024-08

滕旭陽(yáng)，董紅斌，孫靜.面向特征選擇問(wèn)題的協(xié)同演化方法[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(1): 24-31.

英文引用格式：TENG Xuyang，DONG Hongbin，SUN Jing.Co-evolutionary algorithm for feature selection[J]. CAAI transactions on intelligent systems, 2017, 12(1): 24-31.