基于重復(fù)度分析的森林優(yōu)化特征選擇算法

冀若含，董紅斌

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

大數(shù)據(jù)和物聯(lián)網(wǎng)技術(shù)的發(fā)展，使得越來越多 的數(shù)據(jù)被采集、存儲(chǔ)和分析[1]。目前的數(shù)據(jù)不僅數(shù)量巨大，而且維度高，但并不是全部的數(shù)據(jù)都是有用的。數(shù)據(jù)的規(guī)模在變大的同時(shí)也包含了大量的冗余、不相關(guān)或者弱相關(guān)特征，這些特征與數(shù)據(jù)的主要基本結(jié)構(gòu)沒有關(guān)聯(lián)，或者只有松散的弱關(guān)聯(lián)。如果特征不進(jìn)行處理就輸入機(jī)器學(xué)習(xí)模型，不僅會(huì)增大模型的時(shí)間開銷，而且干擾特征的存在還會(huì)降低算法的預(yù)測(cè)精度。通過對(duì)數(shù)據(jù)原特征空間分析，過濾掉冗余和不相關(guān)特征，保留相關(guān)特征，這就是特征選擇。特征選擇以提高模型精度和減少模型運(yùn)算時(shí)間為目標(biāo)，以保持模型原始精度為底線，選擇極小特征子集。此外，大量的特征也會(huì)導(dǎo)致模型過擬合，在項(xiàng)目實(shí)施時(shí)模型性能不佳，特征選擇可以預(yù)防這種現(xiàn)象的發(fā)生，使模型更加適應(yīng)現(xiàn)實(shí)環(huán)境[2]。

特征選擇是一個(gè)復(fù)雜的組合優(yōu)化問題，這是因?yàn)殡S著特征維度的增加特征搜索空間將會(huì)呈指數(shù)型增加，一個(gè)具有n維特征的數(shù)據(jù)集，特征子集(不包含空集)的總數(shù)為2n-1[3]。因此采用完全搜索策略的計(jì)算成本巨大。近幾年基于演化算法的啟發(fā)式搜索策略常用于特征選擇領(lǐng)域，因?yàn)槠洳恍枰嘘P(guān)領(lǐng)域?qū)I(yè)知識(shí)、強(qiáng)大尋優(yōu)能力和較為理想的時(shí)間成本。森林優(yōu)化算法(forest optimization algorithm，F(xiàn)OA)[4]，是一種基于森林中樹木播種的演化算法。Ghaemi 等[5]于2016 年，通過改變局部播種和全局播種兩個(gè)算子，使FOA 適應(yīng)于離散向量，并應(yīng)用于特征選擇，驗(yàn)證了 FSFOA (feature selection using forest optimization algorithm)在特征選擇領(lǐng)域的可行性。對(duì)比粒子群算法(particle swarm optimization,PSO)和蟻群算法(ant colony optimization,ACO)，F(xiàn)SFOA 更容易實(shí)現(xiàn)，而且需要更少的時(shí)間代價(jià)就能得出使學(xué)習(xí)模型性能更好的特征子集。雖然FSFOA 已經(jīng)在低、中、高3 個(gè)特征維度的數(shù)據(jù)集中進(jìn)行了實(shí)驗(yàn)取得了較好的效果，但仍然存在以下問題：

1）FSFOA 在初始化森林的階段采用隨機(jī)初始化的策略進(jìn)行盲目特征選擇，特征被選中的概率均為1/n，n為總特征數(shù)[6]。因此森林樹木初始質(zhì)量較差，森林收斂速度較慢。而且對(duì)高維數(shù)據(jù)集的適應(yīng)度較差。

2）FSFOA 未對(duì)候選種群的數(shù)量進(jìn)行限制。隨著演化過程的進(jìn)行，候選種群的數(shù)量將過于龐大，算法空間成本過高。

3）隨著演化的進(jìn)行種群趨于收斂，森林中會(huì)出現(xiàn)大量相同的樹木(特征選擇向量相同的樹木)。重復(fù)樹木的適應(yīng)度計(jì)算增加了時(shí)間成本，降低了算法的搜索能力。

4）實(shí)驗(yàn)表明，在僅考慮準(zhǔn)確率作為適應(yīng)度的情況下，會(huì)出現(xiàn)多個(gè)適應(yīng)度相同的最優(yōu)樹。而且只考慮分類準(zhǔn)確率為優(yōu)化目標(biāo)過于單一，不利于提高維度縮減率。

因此，為了提升森林整體的收斂速度、增強(qiáng)森林整體的空間搜索尋優(yōu)能力，本文提出了基于重復(fù)度分析的森林優(yōu)化特征選擇算法(feature selection using forest optimization algorithm based on duplication analysis，DAFSFOA) 。

近年來，信息論與演化算法相結(jié)合的研究工作越來越多[7-10]，信息增益(information gain，IG) 可用于初步衡量特征的重要性。通過應(yīng)用IG，可以提高森林樹木的初始質(zhì)量，過濾掉與分類毫無關(guān)系的特征，有利于加速森林整體的演化進(jìn)程。Xu 等[11]于2021 年提出重復(fù)度分析的概念，旨在增加種群多樣性，調(diào)高算法的全局尋優(yōu)能力和減少重復(fù)計(jì)算。受以上內(nèi)容啟發(fā)，本文設(shè)計(jì)了基于信息增益和特征維度的自適應(yīng)森林初始化策略，加快了森林的收斂速度，且適應(yīng)于不同類型的數(shù)據(jù)。同時(shí)加入了森林樹木分析去重機(jī)制、森林種群重啟機(jī)制、候選森林規(guī)模限制和候選最優(yōu)樹生成策略，降低了算法的空間和時(shí)間成本，并且增強(qiáng)了算法的空間搜索能力。最后改進(jìn)適應(yīng)度函數(shù)，提升了算法對(duì)于高維數(shù)據(jù)集的尋優(yōu)能力。在11 個(gè)數(shù)據(jù)集上測(cè)試DAFSFOA 的性能，對(duì)比經(jīng)典的和近幾年提出的特征選擇算法，DAFSFOA 在分類準(zhǔn)確率和特征維度縮減率上都具有很強(qiáng)的競(jìng)爭(zhēng)力，同時(shí)對(duì)高維小樣本數(shù)據(jù)也有很好的適應(yīng)力。

1 相關(guān)工作

特征選擇作為一種數(shù)據(jù)降維手段，能在不改變?cè)继卣魑锢硇畔⒌那闆r下選擇盡量小的特征子集。特征選擇常作為數(shù)據(jù)處理工具，去除干擾特征和選擇核心特征。因此許多學(xué)者已經(jīng)對(duì)特征選擇進(jìn)行了系統(tǒng)的研究。通常將特征選擇方法分為3 種類型:過濾式 (filter)、包裹式 (wrapper)和嵌入式 (embedding)[1]。對(duì)于過濾式特征選擇算法，特征子集的選擇與機(jī)器學(xué)習(xí)模型之間沒有交互，模型的輸出結(jié)果不會(huì)影響特征子集的選擇。在包裹式特征選擇算法中，模型的結(jié)果例如分類準(zhǔn)確率，會(huì)直接作為特征子集的適應(yīng)度函數(shù)，評(píng)價(jià)特征子集的優(yōu)劣。嵌入式特征選擇算法將分類算法或者回歸算法的學(xué)習(xí)過程與特征選擇過程合并同時(shí)進(jìn)行，算法學(xué)習(xí)過程結(jié)束的同時(shí)產(chǎn)生特征選擇結(jié)果。包裹式方法往往能取得比過濾式方法更好的效果，但同時(shí)也需要付出更大的計(jì)算代價(jià)。而過濾式方法的計(jì)算成本較低，而且通用性更好[12]。隨著研究的進(jìn)展，也產(chǎn)生了越來越多的混合式特征選擇算法(hybrid method)，混合式特征選擇方式結(jié)合了過濾式和包裹式方法的優(yōu)點(diǎn)。

特征子集搜索技術(shù)是特征選擇的核心，搜索技術(shù)的選擇往往會(huì)直接影響特征選擇算法的效果。子集搜索技術(shù)一般分為3 種：完全搜索、啟發(fā)式搜索、基于演化算法的搜索[13]。完全搜索能夠保證尋找到最優(yōu)特征子集，但是特征選擇是個(gè) NP難問題，當(dāng)面對(duì)高維數(shù)據(jù)時(shí)，完全搜索需要的時(shí)間代價(jià)過大，因此特征選擇中較少采用完全搜索策略[14]。啟發(fā)式搜索常用于特征選擇，例如貪婪搜索。貪婪搜索的典型例子是：序列正向選擇(sequential forward selection,SFS)[15]、序列反向選擇(sequential backward selection,SBS)[16]。但是這兩種搜索方式都存在明顯的局限，都存在“嵌套效應(yīng)”，缺少搜索的靈活性，之前添加或者去除的特征，在之后步驟中不能從特征子集中去除或者重新加入特征子集。為了克服這個(gè)問題，提出了加L減R法[17]、順序反向浮動(dòng)選擇(sequential backward floating selection,SBFS)[18]和順序正向浮動(dòng)選擇(sequential forward floating selection,SFFS)[18]等。加L減R法通過運(yùn)行L次SFS 算法，R次SBS來達(dá)到平衡，但是很難確定L和R的值。演化算法的靈感來源于自然演化中的生物智慧、群體智慧和群體行為，其具有強(qiáng)大的搜索能力。近年來，以粒子群算法(PSO)、遺傳算法(genetic algorithm,GA)、蟻群算法(ACO)等經(jīng)典演化算法為基礎(chǔ)的變種算法廣泛應(yīng)用于超參數(shù)優(yōu)化[19]、特征選擇[20]和路徑規(guī)劃[21]等領(lǐng)域。同時(shí)也出現(xiàn)了大量新型演化算法，如模擬座頭鯨氣泡網(wǎng)狩獵的鯨魚算法(whale optimization algorithm,WOA)[22]、受森林中樹木播種啟發(fā)的森林優(yōu)化算法(FOA)[4]。雖然演化算法的應(yīng)用領(lǐng)域廣泛，但要應(yīng)用于特征選擇也必須進(jìn)行一系列的改進(jìn)，形成針對(duì)特征選擇領(lǐng)域的演化算法。Dong 等[23]結(jié)合信息論知識(shí)和粒子群算法，并舍棄粒子群更新公式中的速度參數(shù)，提出了一種混合特征選擇方法：基于PSO 的雙全局最優(yōu)的高維特征選擇方法。Agrawal 等[24]結(jié)合量子計(jì)算的概念提出了基于量子的鯨魚優(yōu)化算法(quantum based whale optimization algorithm,QWOA)進(jìn)行特征選擇。該方法利用種群個(gè)體的量子位表示法和量子旋轉(zhuǎn)門算子，提高了經(jīng)典WOA 的特征空間探索和利用能力，全局尋優(yōu)能力更強(qiáng)、種群多樣性更高。Li 等[25]提出了一種改進(jìn)的黏性二進(jìn)制粒子群算法(improved binary particle swarm optimization,ISBPSO)。ISBPSO 采用了基于互信息(MI)種群初始化策略獲得優(yōu)質(zhì)初始種群，并將遺傳算法作為PSO 的子算子用于交換種群信息避免種群過早收斂，提高了算法跳出局部最優(yōu)的能力。

本文提出的DAFSFOA 主要目標(biāo)為增加森林中樹木的多樣性，擴(kuò)大森林對(duì)特征空間的覆蓋，同時(shí)降低算法的計(jì)算成本。為達(dá)到以上目的，DAFSFOA 添加了基于信息增益的自適應(yīng)森林初始化策略、森林去重和重啟機(jī)制、候選森林規(guī)模限制策略、候選最優(yōu)樹生成策略，并改進(jìn)了適應(yīng)度函數(shù)。

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

FSFOA 是在FOA 的基礎(chǔ)上改進(jìn)而來的，可以看作二進(jìn)制離散向量的森林優(yōu)化算法。FOA 的靈感來自于森林中樹木種群的演化過程。在森林中，參天大樹往往在水源和陽光充足的地方。樹木種子尋找最佳棲息地的過程，也正是一個(gè)搜索尋優(yōu)的過程。通過對(duì)這一過程的建模，最終Ghaemi[4]等于2014 年提出了FOA。之后，Ghaemi等[5]提出了針對(duì)離散空間搜索的FOA，并應(yīng)于特征選擇。FSFOA 主要由初始化森林、局部播種、森林規(guī)模限制候選森林生成、全局播種、更新全局最優(yōu)樹五部分組成。FSFOA 采用Xi=(xi0,xi1,xi2,···,xiD)，表示森林中索引值為i的樹木。其中xi0≥0，xi,j＞0∈{1,0}，D表示數(shù)據(jù)集的維度。樹木向量的第0 維表示樹木的年齡，第1～D維表示特征選擇情況，0 代表未選中該特征，1 代表選中。FSFOA 的主要流程如圖1 所示。

圖1 FSFOA 流程Fig.1 Flowchart of FSFOA

2.1 初始化森林

在FSFOA 中，森林中每一棵樹木都被表示為如圖2 所示的長(zhǎng)度為D+1的離散向量。與常規(guī)特征選擇算法中選擇結(jié)果表示方法不同的是，F(xiàn)SFOA 中添加了年齡Aage這一維。樹木的年齡這一重要的參數(shù)在后續(xù)局部播種和森林規(guī)模限制階段有重要的作用。初始化森林就是生成一定數(shù)目的初始樹木向量，樹木年齡全部設(shè)置為0，其余位置隨機(jī)初始化為0 或1。因此，在初始化森林的階段每個(gè)特征被選中和被刪除的概率相同。對(duì)于中低維數(shù)據(jù)集，這種隨機(jī)的初始化策略s 缺點(diǎn)并不明顯，但對(duì)于高維數(shù)據(jù)集，完全隨機(jī)初始化森林將給后續(xù)種群尋優(yōu)帶來極大困難。

圖2 Nlsc=2 時(shí)局部播種實(shí)例Fig.2 Example of local seeding at Nlsc=2

2.2 局部播種

局部播種代表了FSFOA 對(duì)特征空間的深度搜索，模擬了樹木在自身附近播種的行為。局部播種算子只針對(duì)Aage=0 的樹木。Nlsc參數(shù)代表了Aage=0 的父代樹木可產(chǎn)生的子樹數(shù)目。進(jìn)行局部播種的樹木隨機(jī)選中Nlsc個(gè)不同的位置進(jìn)行單點(diǎn)翻轉(zhuǎn)突變，也即對(duì)選中的位置進(jìn)行取反操作，選中位置為0 的置為1，為1 的置為0。每進(jìn)行1 次單點(diǎn)取反將產(chǎn)生1 棵子樹，并重置父樹繼續(xù)下次單點(diǎn)突變。Nlsc個(gè)突變位置將產(chǎn)生Nlsc棵子樹，子樹Aage=0，森林中其他所有樹木的Aage增加1。具體過程如圖2 所示。圖2 中代表了選中的突變位置。

2.3 森林規(guī)模限制

隨著演化的進(jìn)行，森林中樹木會(huì)越來越多。因此需要對(duì)森林中的總?cè)萘窟M(jìn)行限制，森林的容量為Sarea。Aage＞Tlife(年齡限制)的樹木將會(huì)老死，被森林淘汰，移除到候選森林。如果森林中樹木總數(shù)仍大于Sarea，F(xiàn)SFOA 將會(huì)根據(jù)適應(yīng)度值對(duì)森林中的樹木進(jìn)行降序排序，排名超過Sarea的樹木也將移除到候選森林。FSFOA 中的適應(yīng)度值為分類器的分類準(zhǔn)確率，也即樹木選擇的特征子集的分類能力。

2.4 全局播種

全局播種代表了FSFOA 對(duì)特征空間的廣度搜索。對(duì)比局部播種，全局播種產(chǎn)生的子樹與父樹的差距更大。全局播種操作可在森林陷入局部最優(yōu)的時(shí)候，使森林跳出局部最優(yōu)。候選森林中的樹木以Ptransfer的概率被選中進(jìn)行全局播種。1 棵父樹只產(chǎn)生1 棵子樹，父樹隨機(jī)選擇Ngsc個(gè)位置進(jìn)行多點(diǎn)取反，并置Aage=0，加入森林中參與演化，具體如圖3 所示。

圖3 Ngsc=4 時(shí)全局播種實(shí)例Fig.3 Example of global seeding at Ngsc=4

2.5 更新最優(yōu)樹

根據(jù)適應(yīng)度值對(duì)森林中的樹木進(jìn)行降序排列，適應(yīng)度最高的樹被選為最優(yōu)樹，并將該樹的Aage字段置為0，參與后續(xù)的森林演化。將最優(yōu)樹的Aage每次都重置為0，也即優(yōu)秀的樹木不會(huì)被淘汰，保證了森林中優(yōu)秀的樹木能夠一直參與森林的演化。

3 DAFSFOA 算法

針對(duì)引言中提出的FSFOA 的缺陷，以提升森林的收斂速度和算法的搜索能力為目標(biāo)，本文提出了DAFSFOA 算法。為了加快森林收斂速度，DAFSFOA 引入了信息增益對(duì)特征進(jìn)行初篩，提升了初始種群的質(zhì)量，而且針對(duì)不同維度的數(shù)據(jù)集采用了不同的初始化策略縮小了高維數(shù)據(jù)集的搜索空間。同時(shí)，采用森林樹木重復(fù)度分析機(jī)制和候選森林規(guī)模限制策略降低了算法的時(shí)間與空間成本。為了提升算法的搜索能力，DAFSFOA設(shè)計(jì)了森林重啟機(jī)制，防止森林過早收斂陷入局部最優(yōu)，同時(shí)提出了候選最優(yōu)解生成策略進(jìn)一步提升樹木多樣性，并且改進(jìn)了適應(yīng)度函數(shù)，大大提高了算法的尋優(yōu)能力。

3.1 基于信息增益的自適應(yīng)初始化策略

近年來，特征選擇領(lǐng)域常用信息論知識(shí)對(duì)特征進(jìn)行初步篩選。信息增益(IG)能夠反應(yīng)特征與分類標(biāo)簽的相關(guān)度。信息增益越大，該特征對(duì)于分類的幫助越大。信息增益的定義如式(1)～(4)所示：

H(X)為隨機(jī)變量的熵，H(Y|X)為條件熵，兩者之差就是信息增益。但信息增益并不能反應(yīng)特征與特征之間的關(guān)系，因此不能全憑信息增益選擇特征。本文提出增1 減1 法來初始化森林樹木。在計(jì)算數(shù)據(jù)集中每個(gè)特征的IG 后，對(duì)森林進(jìn)行隨機(jī)初始化，對(duì)初始化后的初代森林中前50%的樹木，添加信息增益最大的特征,并刪除信息增益最小的特征。并且對(duì)于高緯度小樣本的數(shù)據(jù)集采用不同的初始化策略。當(dāng)D(特征維度)?N(樣本數(shù)量)時(shí)，無法覆蓋整個(gè)特征空間，因?yàn)闃颖緮?shù)量太少此時(shí)在初始化森林時(shí)選擇較少的特征更利于后續(xù)收斂。當(dāng)D＞3N時(shí)，初始森林中的樹木選擇的特征數(shù)目應(yīng)小于等于3N。

3.2 候選森林規(guī)模的限制策略

FSFOA 中隨著森林演化的進(jìn)行，森林中越來越多的樹被轉(zhuǎn)移到候選森林。候選森林的規(guī)模將越來越大，但保存巨大的候選森林會(huì)帶來較大的內(nèi)存開銷，而且劣質(zhì)樹木對(duì)于森林的尋優(yōu)幫助不大。較大的候選森林也會(huì)導(dǎo)致在全局播種階段有過多的新生樹木加入到森林中，也間接加大了算法的計(jì)算消耗。因此，在DAFSFOA 中的森林規(guī)模限制階段，本文對(duì)候選森林同樣進(jìn)行規(guī)模限制。因?yàn)楹蜻x森林均為較劣質(zhì)的樹木，所以無需在計(jì)算適應(yīng)度進(jìn)行排序篩選。本文將候選森林的規(guī)模限制設(shè)為森林規(guī)模限制的兩倍，即2Sarea。當(dāng)候選森林中樹木數(shù)量超過限制時(shí)，隨機(jī)刪除樹木直到樹木數(shù)量等于2Sarea。

3.3 重復(fù)度分析及森林重啟機(jī)制

隨著演化的進(jìn)行森林逐漸收斂，森林中產(chǎn)生大量Aage不同，但是所選特征相同的樹木。大量重復(fù)的樹木的存在對(duì)森林演化尋優(yōu)并無幫助，反而因此消耗了大量的計(jì)算資源。因此，我們需要對(duì)森林中的樹木進(jìn)行重復(fù)度分析，每種樹木只保留一個(gè)個(gè)體，極大地提高了森林中樹木的多樣性，有利于算法的全局尋優(yōu)。如果經(jīng)過去重操作森林中剩余的樹的數(shù)量只有森林初始種群數(shù)量Sinitial的一半，此時(shí)認(rèn)為森林種群的多樣性過低不利于后續(xù)搜索尋優(yōu)，因此采用森林重啟機(jī)制，采用初始化森林的方法補(bǔ)充森林中的樹木，使森林樹木的數(shù)量重新達(dá)到Sinitial。

3.4 候選最優(yōu)樹生成策略

FSFOA 每輪演化只產(chǎn)生1 棵最優(yōu)樹，忽略了森林中樹木的統(tǒng)計(jì)信息。為了充分利用森林演化過程中的統(tǒng)計(jì)信息，在DAFSFOA 中提出候選最優(yōu)樹概念，即統(tǒng)計(jì)目前森林中出現(xiàn)過的全部特征，并根據(jù)統(tǒng)計(jì)結(jié)果生成候選最優(yōu)樹，將候選最優(yōu)樹的年齡置為0，并加入森林參與后續(xù)的森林演化。候選最優(yōu)樹的加入不僅增加了森林樹木多樣性，而且充分利用了森林演化過程中的統(tǒng)計(jì)信息。

3.5 改進(jìn)的適應(yīng)度函數(shù)

適應(yīng)度值表現(xiàn)了算法所選擇的特征子集的好壞。FSFOA 中的適應(yīng)度函數(shù)設(shè)計(jì)考慮較為片面，僅考慮分類準(zhǔn)確率(AC)，AC 的定義如式(5)所示：

式中：Nacc為分類正確的實(shí)例數(shù)；M為實(shí)例總數(shù)。在只考慮AC 的情況下實(shí)驗(yàn)結(jié)果中出現(xiàn)了很多適應(yīng)度值相同的樹，不利于最優(yōu)樹的挑選，而且不利于森林朝著增大DR 的方向演化，DR 為維度縮減率，如式(6)所示：

式中：FnotSelected為對(duì)應(yīng)樹未選擇的特征數(shù)；Fall為特征總數(shù)。式(7)為DAFSFOA中采用的適應(yīng)度函數(shù)，為AC 和DR 的加權(quán)，避免了不同樹適應(yīng)度值相同的情況。α+β=1而 且 α ?β，因?yàn)樘卣鬟x擇算法的主要目的為提高分類準(zhǔn)確率。

3.6 DAFSFOA 流程圖

圖4 為DAFSFOA 的算法流程圖。DAFSFOA的演化終止條件為迭代50 次，當(dāng)演化次數(shù)超過限制，則結(jié)束算法，輸出森林中目前的最優(yōu)樹也即最優(yōu)特征子集。

圖4 DAFSFOA 流程圖Fig.4 Flowchart of DAFSFOA

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

實(shí)驗(yàn)中代碼運(yùn)行環(huán)境為python3.8。硬件環(huán)境為CPU Ryzen7 5800H,16 GB 內(nèi)存。

4.1 數(shù)據(jù)集及對(duì)比算法

FSFOA 中使用了10 個(gè)UCI 數(shù)據(jù)集和1 個(gè)高維微陣列數(shù)據(jù)集。數(shù)據(jù)集的維度和實(shí)例數(shù)如表1所示。

表1 數(shù)據(jù)集簡(jiǎn)介及Nlsc 和 NgscTable 1 Dataset introduction and corresponding Nlsc and Ngsc values

為了對(duì)比顯示DAFSFOA 算法的性能，本文采用與FSFOA 相同的11 個(gè)數(shù)據(jù)集。除了與FSFOA 進(jìn)行實(shí)驗(yàn)對(duì)比，本文也與幾種經(jīng)典的特征選擇算法和近年提出的新算法進(jìn)行了對(duì)比。表2 列出了文中對(duì)比算法的簡(jiǎn)介。

表2 文中對(duì)比算法Table 2 Comparative algorithms in the paper

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

為了突出DAFSFOA 對(duì)于FSFOA 改進(jìn)的有效性。除了改進(jìn)部分，其他參數(shù)保持與FSFOA 一致。Tlife設(shè)為15，Ptransfer設(shè)為0.05，Sarea設(shè)為50，以上3 個(gè)參數(shù)與FSFOA 的設(shè)置相同，Sinitial在FSFOA 中未提及具體值，本文中設(shè)為50[5]。Nlsc和Ngsc也保持和FSFOA 相同。FSFOA 中指出Nlsc和Ngsc與數(shù)據(jù)集維度有關(guān)，同時(shí)實(shí)驗(yàn)得出當(dāng)Nlsc=D/5,Ngsc=D/2 時(shí)，能達(dá)到計(jì)算成本和尋優(yōu)效果的最佳平衡[5]。參數(shù)設(shè)置具體如表1 所示。

4.3 分類器和驗(yàn)證方式

本文采用KNN、rbf-svm、C4.5 三種分類器計(jì)算AC，其中KNN 采用了n=1、n=3 和n=5 這3 種不同的參數(shù)。C4.5 采用J48 參數(shù)。同時(shí)采用70%～30%的數(shù)據(jù)集劃分、10 折交叉驗(yàn)證、2 折交叉驗(yàn)證這3 種不同的數(shù)據(jù)集劃分方式。實(shí)驗(yàn)中采用相同的實(shí)驗(yàn)條件計(jì)算得出森林中每棵樹的AC 和DR，得出最優(yōu)樹，AC 和DR 的計(jì)算公式如式(5)、(6)所示。

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

DAFSFOA 與其他算法對(duì)比的結(jié)果如表3 所示。對(duì)于最高正確率和最高維度縮減率均加粗處理。在Dermatology、Sonar、Cleveland、Heart-statlog、Hepatitis、SRBCT、Segmentation 這7 個(gè)數(shù)據(jù)集上，采用不同的數(shù)據(jù)集劃分方式和分類器，DAFSFOA 都取得最高的準(zhǔn)確率。

表3 DAFSFOA 與對(duì)比算法的實(shí)驗(yàn)結(jié)果Table 3 Experimental results of DAFSFOA and comparison algorithms

續(xù)表 3

DAFSFOA 在高維數(shù)據(jù)集SRBCT 上算法性能有巨大的提升，對(duì)比FSFOA，其準(zhǔn)確率提升了5.26%，而且維度縮減率的提升更為巨大。FSFOA 在對(duì)應(yīng)數(shù)據(jù)集上的準(zhǔn)確率高達(dá)94.73%，但是維度縮減率只有49.06%，而SRBCT 數(shù)據(jù)集的特征維度有2 308 維，F(xiàn)SFOA 得到的最優(yōu)樹仍然包含了大量特征。而DAFSFOA 得到的最優(yōu)樹維度縮減率高達(dá)92.33%。對(duì)比FSFOA，DAFSFOA 能夠更好地處理高維特征選擇問題，這得益于DAFSFOA 特殊設(shè)計(jì)的高維數(shù)據(jù)集初始化策略。對(duì)于同樣是高維數(shù)據(jù)集的Sonar，DAFSFOA 的表現(xiàn)也要遠(yuǎn)遠(yuǎn)好于FSFOA，平均AC 為93.57%，最高AC 為98.33%，而FSFOA 的平均AC 為80.24%，其最高AC 為86.98%，也低于DAFSFOA 的平均值。當(dāng)采用rbf-svm 分類器并采用2-fold 驗(yàn)證的時(shí)候，DAFSFOA 的準(zhǔn)確率比FSFOA 高了22%，同時(shí)維度縮減率提高了8%。同時(shí)，對(duì)比2020 年提出的NFSFOA，DAFSFOA 也具有明顯的優(yōu)勢(shì)，在同樣條件下，DAFSFOA 得出的最優(yōu)特征子集分類準(zhǔn)確率最高達(dá)98.33%，而相應(yīng)的NFSFOA 只有74.6%，但NFSFOA 產(chǎn)生的最優(yōu)樹的維度縮減率只高出DAFSFOA 算法0.09%，DAFSFOA 只犧牲了0.09%的DR，就達(dá)到了98.33%的準(zhǔn)確率，可見DAFSFOA 的性能優(yōu)勢(shì)。在維度縮減率方面，DAFSFOA 并不像在分類正確率上表現(xiàn)得如此出眾，但對(duì)于大部分?jǐn)?shù)據(jù)集DAFSFOA 都優(yōu)于FSFOA。對(duì)于一部分?jǐn)?shù)據(jù)集，雖然DAFSFOA 沒有取得最高的維度縮減率，但在分類準(zhǔn)確率上仍有較大優(yōu)勢(shì)。例如，NSM 算法在Ionosphere 數(shù)據(jù)集上，采用10 折交叉驗(yàn)證和KNN(k=1)分類器取得了88.23%的維度縮減率，高于DAFSFOA。但是NSM 算法的分類準(zhǔn)確率比DAFSFOA 低了3.2%。

在大部分?jǐn)?shù)據(jù)集中，DAFSFOA 的維度縮減率排行第二，并且與第一相差很小，但分類準(zhǔn)確率遠(yuǎn)超其他算法。通過DAFSFOA 在不同數(shù)據(jù)集的實(shí)驗(yàn)，可以得出DAFSFOA 在AC 和DR 上對(duì)比原始的FSFOA，均有巨大提升，而且在大部分?jǐn)?shù)據(jù)集中的表現(xiàn)也超過了其他經(jīng)典的算法和近年來提出的新型特征選擇算法。

5 結(jié)束語

本文通過對(duì)FSFOA 的深入分析，提出了FSFOA 的4 處不足。以提高森林中個(gè)體的多樣性、降低樹木重復(fù)度和提高算法的全局尋優(yōu)能力為目的，本文對(duì)FSFOA 算法提出了5 點(diǎn)改進(jìn)意見，即基于信息增益的自適應(yīng)初始化策略、候選森林規(guī)模限制策略、森林重復(fù)度分析及重啟機(jī)制、候選最優(yōu)樹生成策略、結(jié)合維度縮減率的適應(yīng)度函數(shù)，最終形成了基于重復(fù)度分析的森林優(yōu)化特征選擇算法。并通過實(shí)驗(yàn)在不同維度的數(shù)據(jù)集上驗(yàn)證了DAFSFOA 改進(jìn)的有效性。DAFSFOA 在AC 和DR 兩個(gè)方面的表現(xiàn)普遍超過了FSFOA，尤其是對(duì)于高維數(shù)據(jù)集，DAFSFOA 的表現(xiàn)優(yōu)于FSFOA。