基于差分進(jìn)化和森林優(yōu)化混合的特征選擇

林達(dá)坤，黃世國(guó)，林燕紅，洪銘淋

1(福建農(nóng)林大學(xué) 智慧農(nóng)林褔建省高校重點(diǎn)實(shí)驗(yàn)室，福州 350002)2(生態(tài)公益林重大有害生物防控福建省高校重點(diǎn)實(shí)驗(yàn)室，福州 350002)

1 引 言

特征選擇在機(jī)器學(xué)習(xí)中扮演重要角色.通過(guò)特征選擇可以提高模型預(yù)測(cè)精度、減少計(jì)算時(shí)間.但選擇最優(yōu)特征子集是一個(gè)NP-hard問(wèn)題.當(dāng)特征的數(shù)量為n時(shí)，其特征子集的數(shù)量為2n.應(yīng)用窮舉方法評(píng)價(jià)每個(gè)特征子集的效果將產(chǎn)生大量計(jì)算，現(xiàn)有計(jì)算能力一般難以滿足計(jì)算需求.因此，許多學(xué)者提出眾多特征選擇算法旨在尋找近似最優(yōu)解.特征選擇方法一般分為嵌入式、過(guò)濾式和封裝式.過(guò)濾式特征選擇只考慮數(shù)據(jù)集的內(nèi)在性質(zhì)，在選擇過(guò)程中不考慮目標(biāo)評(píng)價(jià)問(wèn)題.封裝式特征選擇通過(guò)評(píng)價(jià)不同特征子集尋找近似最優(yōu)的集合.嵌入式特征選擇則是將特征選擇作為組成部分嵌入到學(xué)習(xí)算法.由于封裝式特征選擇一般比過(guò)濾式特征選擇具有更優(yōu)的評(píng)價(jià)結(jié)果[1]，因此，基于元啟發(fā)機(jī)制的特征選擇方法一般采用封裝式特征選擇.

與傳統(tǒng)特征選擇方法(如序列向前算法和序列向后算法)易陷入局部最優(yōu)相比[2]，基于元啟發(fā)機(jī)制的算法，特別是群智能計(jì)算方法由于其很強(qiáng)的全局搜索能力，在特征選擇中得到廣泛研究.目前，許多群體智能優(yōu)化算法都已被成功應(yīng)用到特征選擇中.Babatunde等[3]在2014年提出一種基于二進(jìn)制遺傳算法的特征選擇，結(jié)果表明該算法能夠有效剔除無(wú)用特征并提高分類精度.但遺傳算法的局部搜索能力較差，在進(jìn)化后期搜索效率較低.Kennedy和Eberhart在1997年提出粒子群優(yōu)化(Particle swarm optimization，PSO)的二進(jìn)制版本[4].Emary等在2015年提出二進(jìn)制灰狼優(yōu)化(Binary grey wolf optimization，BGWO)，結(jié)果表明該算法能夠在特征空間中搜索到合適的特征組合[5].但該算法存在著收斂速度快，易早熟等缺點(diǎn).Mirjalili在2015年提出基于蜻蜓算法(Dragonfly algorithm，DA)的特征選擇[6].該算法在特征選擇過(guò)程中也存在早熟、求解精度不高等問(wèn)題.Ghaemi等在2014年提出森林優(yōu)化算法(Forest optimization algorithm，F(xiàn)OA)[7]，在2015年將其應(yīng)用于特征選擇中，結(jié)果表明森林優(yōu)化算法具有較好的性能[8].但該算法的局部搜索方式趨向于窮舉式搜索，存在著計(jì)算量大、收斂速度慢等問(wèn)題.

由于各種群體智能優(yōu)化算法有其優(yōu)點(diǎn)也有不足，采用單一的算法有時(shí)難以獲得滿意的效果.近年來(lái)，一些學(xué)者綜合多種群智能優(yōu)化算法的優(yōu)缺點(diǎn)，將其混合用于特征選擇，取得了較好的效果.李虹等將遺傳算法與粒子群優(yōu)化算法結(jié)合，提出了混合粒子群優(yōu)化算法，結(jié)果表明該算法具有較強(qiáng)的全局搜索能力，能夠有效避免粒子群優(yōu)化算法早熟收斂的問(wèn)題[9].Khushaba等將蟻群算法與差分進(jìn)化算法結(jié)合，進(jìn)一步提升了蟻群算法的開(kāi)發(fā)與探索能力，實(shí)驗(yàn)結(jié)果表明該算法能夠取得較高的分類精度[10].Zawbaa等將灰狼優(yōu)化算法與蟻獅優(yōu)化算法結(jié)合，且將其用于小樣本高維數(shù)據(jù)集的特征選擇，結(jié)果表明該算法具有良好的降維效果與分類精度[11].

本研究針對(duì)森林優(yōu)化算法收斂速度慢的問(wèn)題，采用智能算法混合策略，提出基于差分進(jìn)化和森林優(yōu)化混合的特征選擇.利用差分進(jìn)化算法較快收斂的特點(diǎn)，在森林優(yōu)化算法前期引入差分進(jìn)化算法使其加快收斂.同時(shí)，針對(duì)森林優(yōu)化算法局部搜索計(jì)算量大的問(wèn)題，利用局部搜索中每棵樹(shù)的取值僅改變一位的特點(diǎn)，給出了更有效的距離計(jì)算方法，進(jìn)一步提高了算法的性能.

2 基于森林優(yōu)化算法的特征選擇

特征選擇是指從已有的M個(gè)特征中選擇N個(gè)特征使得系統(tǒng)的特定指標(biāo)最優(yōu)化.針對(duì)分類問(wèn)題的特征選擇，通常是產(chǎn)生一條二進(jìn)制編碼.“1”代表選擇相應(yīng)特征，“0”代表去除相應(yīng)特征.

森林優(yōu)化算法是模擬利用種子傳播找到生存條件優(yōu)越的棲息地來(lái)搜索問(wèn)題的最優(yōu)解.一棵樹(shù)代表問(wèn)題的一個(gè)可能解，由所有樹(shù)構(gòu)成的森林則代表問(wèn)題所有解.該算法有5個(gè)步驟：初始化森林、局部播種、種群限制、全局播種、更新最優(yōu)樹(shù).具體步驟如下.

Step1.初始化森林：產(chǎn)生n棵樹(shù)，每棵樹(shù)都以一維數(shù)組[v1,v2，…，vD,Age,Fitness]表示，其中D為問(wèn)題的維數(shù)，變量V的取值為1或0，Age代表樹(shù)的年齡，其初始值為0，F(xiàn)itness為適應(yīng)度值(評(píng)價(jià)樹(shù)的好壞).

Step2.局部播種(Local seeding)：每棵年齡為0的樹(shù)產(chǎn)生LSC棵與父代完全相同的樹(shù)，然后隨機(jī)選中每棵新樹(shù)的某一維(不包括Age與Fitness)，將其值取反.將森林中的老樹(shù)的年齡加1且新樹(shù)的年齡設(shè)為0.

Step3.種群限制：森林中當(dāng)樹(shù)的年齡大于最大年齡數(shù)(Life time)將該樹(shù)從森林中剔除并放入候選種群.當(dāng)森林中保留下來(lái)的樹(shù)的數(shù)量超過(guò)區(qū)域限制時(shí)，則剔除適應(yīng)度值較差的樹(shù)并將其也放入候選種群.

Step4.全局播種：從候選種群中隨機(jī)選出一定數(shù)量的樹(shù).對(duì)每棵被選中的樹(shù)隨機(jī)選中GSC維，將其值取反.

Step5.更新最優(yōu)樹(shù)：將森林中適應(yīng)度值最大的樹(shù)作為最優(yōu)樹(shù)，并將該樹(shù)的年齡設(shè)為0，以便于最優(yōu)樹(shù)能在下次迭代中進(jìn)行局部播種.

3 基于差分進(jìn)化和森林優(yōu)化混合的特征選擇

具有反饋機(jī)制的二進(jìn)制差分進(jìn)化(Binary Differential Evolution with Feedback Strategy，BFDE)[12]是二進(jìn)制差分進(jìn)化算法的變種，能獲得更好的降維和分類效果.森林優(yōu)化算法中的局部播種方式是一種精細(xì)搜索方法，計(jì)算量大，算法收斂速度慢，同時(shí)，差分進(jìn)化具有較快的收斂速度，因此本研究在森林優(yōu)化算法早期迭代階段利用BFDE算法進(jìn)行特征選擇，后期則繼續(xù)利用森林優(yōu)化算法進(jìn)行特征選擇，以充分發(fā)揮森林優(yōu)化算法局部搜索的優(yōu)勢(shì).我們提出的新算法命名為差分進(jìn)化和森林優(yōu)化混合的算法(Differential Evolution Based Forest Optimization Algorithm，DEFOA).

3.1 具有反饋機(jī)制的二進(jìn)制差分進(jìn)化

BFDE的具體步驟如下：

(1)

S(xi,j,t)=1/(1+e-xi,j,t)

(2)

BFDE的變異操作方式為DE/current-to-best/1，具體操作如公式(3)所示.

(3)

算法 1.

輸入：種群大小N，最大迭代次數(shù)T.

2.評(píng)價(jià)二進(jìn)制種群Pbt.

fori=1 to N

利用公式(4)、(6)對(duì)種群Pt進(jìn)行交叉變異操作產(chǎn)生新向量Gi,t，同時(shí)將界限控制在[xmin,xmax]之間.

End fori

利用公式(1)、(2)更新并評(píng)價(jià)二進(jìn)制種群Pbt.

利用公式(5)進(jìn)行反饋操作.

End for t

4.將二進(jìn)制種群Pbt的每個(gè)個(gè)體xbi,t看作森林優(yōu)化算法中的樹(shù)，額外增加一維Age，Age初始值全為0.

fori=1 to N

對(duì)Age為0的xbi,t進(jìn)行局部播種產(chǎn)生LSC棵Age為0的新樹(shù)，xbi,t老化Age值加1.

評(píng)價(jià)每棵新樹(shù).

End fori

進(jìn)行種群限制，清除前次迭代產(chǎn)生的候選種群，形成新的候選種群.

利用公式(7)、(8)對(duì)候選種群進(jìn)行反饋調(diào)節(jié).

對(duì)候選種群進(jìn)行全局播種，評(píng)價(jià)新樹(shù)并加入到二進(jìn)制種群Pbt中.

為維持種群大小N，再次進(jìn)行種群限制.

更新最優(yōu)樹(shù).

End for t

(4)

BFDE在原有差分進(jìn)化的基礎(chǔ)上引入了反饋操作，利用公式(5)將二進(jìn)制種群Pbt的信息反饋到原始種群Pt中.

(5)

3.2 差分進(jìn)化和森林優(yōu)化混合的特征選擇

(6)

(7)

(8)

i=1，…，N，j=1，…，D.DEFOA的偽代碼如算法1所示.

3.3 針對(duì)局部搜索階段改進(jìn)的K最近鄰算法

在基于智能計(jì)算的封裝式特征選擇算法的更新迭代過(guò)程中，每更新產(chǎn)生一個(gè)新粒子需要對(duì)其進(jìn)行評(píng)價(jià).該評(píng)價(jià)過(guò)程計(jì)算量大，增加了算法的計(jì)算時(shí)間.特別是在DEFOA和FSFOA[8]的局部播種階段會(huì)產(chǎn)生大量相似的粒子(新樹(shù)與老樹(shù)只有一維不同).若為了評(píng)價(jià)這些相似粒子，均利用分類算法重新訓(xùn)練，必將顯著增加算法的計(jì)算量.

針對(duì)局部播種階段這一特殊情況，本研究引入一種改進(jìn)的K最近鄰算法(K Nearest Neighbor,KNN)[13]，以降低DEFOA算法的計(jì)算量，提高運(yùn)行速度.該KNN用于森林優(yōu)化時(shí)作如下改進(jìn)：1)在局部播種時(shí)，Age為0的樹(shù)所對(duì)應(yīng)的樣本距離被保留.2)評(píng)價(jià)新樹(shù)時(shí)，只需計(jì)算值發(fā)生改變的維數(shù)所對(duì)應(yīng)的樣本距離.

改進(jìn)的KNN的優(yōu)點(diǎn)在于老樹(shù)進(jìn)行局部播種時(shí)無(wú)需重新計(jì)算新樹(shù)所對(duì)應(yīng)樣本總距離，只需計(jì)算值發(fā)生改變的一維所對(duì)應(yīng)樣本距離與老樹(shù)相加減即可，大大地減少了原本的計(jì)算量.

4 實(shí)驗(yàn)與結(jié)果

4.1 數(shù)據(jù)集

為了評(píng)價(jià)DEFOA的性能，使用不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).所使用數(shù)據(jù)集的具體信息如表1所示，共10個(gè)數(shù)據(jù)集.除SRBCT來(lái)自http：//www.gems-system.org.外，其它數(shù)據(jù)集均來(lái)自UCI machine learning repository(http：//archive.ics.uci.edu/ml/datasets.html).其中，Wine、Zoo、Dermatology的特征維度較低，Sonar、Movement、HilVally_noisetrain屬于中維度數(shù)據(jù)集，Musk1、Arrhythmia、LSVT和 SRBCT屬于高維度數(shù)據(jù)集.

表1 數(shù)據(jù)集Table 1 Datasets

4.2 參數(shù)設(shè)置

為了評(píng)估DEFOA的性能，DEFOA和現(xiàn)有的特征選擇方法進(jìn)行比較.本研究主要選擇了6種算法：BFDE、FSFOA、BGWO、GA、BPSO和BDA.實(shí)驗(yàn)采用的是K作為分類器，K值設(shè)為5.10折交叉驗(yàn)證的分類錯(cuò)誤率的平均值A(chǔ)E將作為適應(yīng)度值，具體計(jì)算過(guò)程如公式(9)、公式(10)所示.

(9)

(10)

所有算法由美國(guó)MathWorks公司出品的MATLAB(R2014b)編程實(shí)現(xiàn).所有實(shí)驗(yàn)均在3.6 GHz CPU和8GB RAM的Intel Core i5機(jī)器上獨(dú)立運(yùn)行10次.所有算法的迭代次數(shù)設(shè)為100，種群大小為50.在DEFOA中，F(xiàn)值設(shè)為0.9，CR值設(shè)為0.6.對(duì)于DEFOA與FSFOA的共有參數(shù)，“Life time”為15，“Transfer rate”為5%，LSC與GSC依賴于問(wèn)題的維數(shù)，一般LSC為數(shù)據(jù)集維數(shù)的20%，GSC為數(shù)據(jù)集維數(shù)的40%.GA的交叉概率為0.8，變異概率為0.1.BPSO的學(xué)習(xí)因子c1和c2值都為2，其慣性權(quán)重區(qū)間為[0.4，0.9].

為進(jìn)一步提升所有算法的性能，在進(jìn)行實(shí)驗(yàn)前對(duì)數(shù)據(jù)集進(jìn)行0-1標(biāo)準(zhǔn)化.具體如公式(11)所示，其中X代表原始變量值，X*代表標(biāo)準(zhǔn)化后的變量值，max是變量的最大值，min是變量的最小值.

(11)

4.3 結(jié)果與分析

圖1表明FSFOA與DEFOA使用改進(jìn)的KNN作為分類器后的運(yùn)行時(shí)間減少率，易看出改進(jìn)的KNN能夠顯著降低算法的運(yùn)行時(shí)間.這也進(jìn)一步證明引進(jìn)的KNN能夠有效解決森林優(yōu)化算法局部播種計(jì)算量大的問(wèn)題.

表2展示了DEFOA與其它算法的分類性能對(duì)比結(jié)果.Mean代表算法獨(dú)立運(yùn)行10次結(jié)果的平均值，Std代表其標(biāo)準(zhǔn)差.Rank是對(duì)算法在不同數(shù)據(jù)集上的性能對(duì)比排序結(jié)果，Mean值越小則排名越前，若Mean值相同，則Std值小的排前.從表2可看出DEFOA除在數(shù)據(jù)集Wine的排名在第2位外，其它數(shù)據(jù)集排名均在第1位，且其對(duì)應(yīng)的標(biāo)準(zhǔn)差相對(duì)較小，說(shuō)明DEFOA的分類性能較為穩(wěn)定.Average Rank是對(duì)算法在不同數(shù)據(jù)集上排序值總和的平均值，根據(jù)Average Rank可得出每個(gè)算法的總排名.從表2易得出DEFOA的分類性能比其他6種算法好.

圖1 新型KNN的計(jì)算效率Fig.1 Computational efficiency of new KNN

表2 算法分類性能對(duì)比Table 2 Comparison of classification performance in algorithms

為進(jìn)一步驗(yàn)證DEFOA對(duì)分類性能的影響，將DEFOA與其它特征選擇算法進(jìn)行t檢驗(yàn)，結(jié)果如表3所示.其中“+”表示DEFOA性能顯著大于其它算法，“=”表示兩者相似.易看出DEFOA除在數(shù)據(jù)集Wine、Zoo、Dermatology上與其它特征算法性能相似外，在其它數(shù)據(jù)集上的性能皆顯著高于其它算法.因此，DEFOA在中維度和高維度數(shù)據(jù)集上具有良好的分類性能.

表3 DEFOA分類性能的t檢驗(yàn)Table 3 T test for classification performance of DEFOA

圖2 算法收斂圖Fig.2 Convergence diagram of algorithms

圖2是不同算法在不同數(shù)據(jù)集上的收斂圖.易看出DEFOA在各數(shù)據(jù)集上均能獲得較好適應(yīng)度值且具有更穩(wěn)定的收斂速度.

5 結(jié) 語(yǔ)

本研究針對(duì)森林優(yōu)化算法的局部播種計(jì)算量過(guò)大的問(wèn)題，在森林優(yōu)化算法的前期迭代中使用差分進(jìn)化算法代替局部播種，提出差分進(jìn)化和森林優(yōu)化混合的算法.經(jīng)實(shí)驗(yàn)驗(yàn)證，該算法具有良好的分類性能與穩(wěn)定的收斂速度.此外，還引入一種改進(jìn)的KNN代替?zhèn)鹘y(tǒng)的KNN作為分類器，實(shí)驗(yàn)結(jié)果表明改進(jìn)的K最近鄰算法能極大降低所提出的混合算法與森林優(yōu)化算法的運(yùn)行時(shí)間.