基于重復度分析的森林優化特征選擇算法

冀若含，董紅斌

（哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001）

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

特征選擇是一個復雜的組合優化問題，這是因為隨著特征維度的增加特征搜索空間將會呈指數型增加，一個具有n維特征的數據集，特征子集(不包含空集)的總數為2n-1[3]。因此采用完全搜索策略的計算成本巨大。近幾年基于演化算法的啟發式搜索策略常用于特征選擇領域，因為其不需要有關領域專業知識、強大尋優能力和較為理想的時間成本。森林優化算法(forest optimization algorithm，FOA)[4]，是一種基于森林中樹木播種的演化算法。Ghaemi 等[5]于2016 年，通過改變局部播種和全局播種兩個算子，使FOA 適應于離散向量，并應用于特征選擇，驗證了 FSFOA (feature selection using forest optimization algorithm)在特征選擇領域的可行性。對比粒子群算法(particle swarm optimization,PSO)和蟻群算法(ant colony optimization,ACO)，FSFOA 更容易實現，而且需要更少的時間代價就能得出使學習模型性能更好的特征子集。雖然FSFOA 已經在低、中、高3 個特征維度的數據集中進行了實驗取得了較好的效果，但仍然存在以下問題：

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

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

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

4）實驗表明，在僅考慮準確率作為適應度的情況下，會出現多個適應度相同的最優樹。而且只考慮分類準確率為優化目標過于單一，不利于提高維度縮減率。

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

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

1 相關工作

特征選擇作為一種數據降維手段，能在不改變原始特征物理信息的情況下選擇盡量小的特征子集。特征選擇常作為數據處理工具，去除干擾特征和選擇核心特征。因此許多學者已經對特征選擇進行了系統的研究。通常將特征選擇方法分為3 種類型:過濾式 (filter)、包裹式 (wrapper)和嵌入式 (embedding)[1]。對于過濾式特征選擇算法，特征子集的選擇與機器學習模型之間沒有交互，模型的輸出結果不會影響特征子集的選擇。在包裹式特征選擇算法中，模型的結果例如分類準確率，會直接作為特征子集的適應度函數，評價特征子集的優劣。嵌入式特征選擇算法將分類算法或者回歸算法的學習過程與特征選擇過程合并同時進行，算法學習過程結束的同時產生特征選擇結果。包裹式方法往往能取得比過濾式方法更好的效果，但同時也需要付出更大的計算代價。而過濾式方法的計算成本較低，而且通用性更好[12]。隨著研究的進展，也產生了越來越多的混合式特征選擇算法(hybrid method)，混合式特征選擇方式結合了過濾式和包裹式方法的優點。

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

本文提出的DAFSFOA 主要目標為增加森林中樹木的多樣性，擴大森林對特征空間的覆蓋，同時降低算法的計算成本。為達到以上目的，DAFSFOA 添加了基于信息增益的自適應森林初始化策略、森林去重和重啟機制、候選森林規模限制策略、候選最優樹生成策略，并改進了適應度函數。

2 森林優化特征選擇算法

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

圖1 FSFOA 流程Fig.1 Flowchart of FSFOA

2.1 初始化森林

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

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

2.2 局部播種

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

2.3 森林規模限制

隨著演化的進行，森林中樹木會越來越多。因此需要對森林中的總容量進行限制，森林的容量為Sarea。Aage＞Tlife(年齡限制)的樹木將會老死，被森林淘汰，移除到候選森林。如果森林中樹木總數仍大于Sarea，FSFOA 將會根據適應度值對森林中的樹木進行降序排序，排名超過Sarea的樹木也將移除到候選森林。FSFOA 中的適應度值為分類器的分類準確率，也即樹木選擇的特征子集的分類能力。

2.4 全局播種

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

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

2.5 更新最優樹

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

3 DAFSFOA 算法

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

3.1 基于信息增益的自適應初始化策略

近年來，特征選擇領域常用信息論知識對特征進行初步篩選。信息增益(IG)能夠反應特征與分類標簽的相關度。信息增益越大，該特征對于分類的幫助越大。信息增益的定義如式(1)～(4)所示：

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

3.2 候選森林規模的限制策略

FSFOA 中隨著森林演化的進行，森林中越來越多的樹被轉移到候選森林。候選森林的規模將越來越大，但保存巨大的候選森林會帶來較大的內存開銷，而且劣質樹木對于森林的尋優幫助不大。較大的候選森林也會導致在全局播種階段有過多的新生樹木加入到森林中，也間接加大了算法的計算消耗。因此，在DAFSFOA 中的森林規模限制階段，本文對候選森林同樣進行規模限制。因為候選森林均為較劣質的樹木，所以無需在計算適應度進行排序篩選。本文將候選森林的規模限制設為森林規模限制的兩倍，即2Sarea。當候選森林中樹木數量超過限制時，隨機刪除樹木直到樹木數量等于2Sarea。

3.3 重復度分析及森林重啟機制

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

3.4 候選最優樹生成策略

FSFOA 每輪演化只產生1 棵最優樹，忽略了森林中樹木的統計信息。為了充分利用森林演化過程中的統計信息，在DAFSFOA 中提出候選最優樹概念，即統計目前森林中出現過的全部特征，并根據統計結果生成候選最優樹，將候選最優樹的年齡置為0，并加入森林參與后續的森林演化。候選最優樹的加入不僅增加了森林樹木多樣性，而且充分利用了森林演化過程中的統計信息。

3.5 改進的適應度函數

適應度值表現了算法所選擇的特征子集的好壞。FSFOA 中的適應度函數設計考慮較為片面，僅考慮分類準確率(AC)，AC 的定義如式(5)所示：

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

式中：FnotSelected為對應樹未選擇的特征數；Fall為特征總數。式(7)為DAFSFOA中采用的適應度函數，為AC 和DR 的加權，避免了不同樹適應度值相同的情況。α+β=1而 且 α ?β，因為特征選擇算法的主要目的為提高分類準確率。

3.6 DAFSFOA 流程圖

圖4 為DAFSFOA 的算法流程圖。DAFSFOA的演化終止條件為迭代50 次，當演化次數超過限制，則結束算法，輸出森林中目前的最優樹也即最優特征子集。

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

4 實驗和結果分析

實驗中代碼運行環境為python3.8。硬件環境為CPU Ryzen7 5800H,16 GB 內存。

4.1 數據集及對比算法

FSFOA 中使用了10 個UCI 數據集和1 個高維微陣列數據集。數據集的維度和實例數如表1所示。

表1 數據集簡介及Nlsc 和 NgscTable 1 Dataset introduction and corresponding Nlsc and Ngsc values

為了對比顯示DAFSFOA 算法的性能，本文采用與FSFOA 相同的11 個數據集。除了與FSFOA 進行實驗對比，本文也與幾種經典的特征選擇算法和近年提出的新算法進行了對比。表2 列出了文中對比算法的簡介。

表2 文中對比算法Table 2 Comparative algorithms in the paper

4.2 具體參數設置

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

4.3 分類器和驗證方式

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

4.4 實驗結果分析

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

表3 DAFSFOA 與對比算法的實驗結果Table 3 Experimental results of DAFSFOA and comparison algorithms

續表 3

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

在大部分數據集中，DAFSFOA 的維度縮減率排行第二，并且與第一相差很小，但分類準確率遠超其他算法。通過DAFSFOA 在不同數據集的實驗，可以得出DAFSFOA 在AC 和DR 上對比原始的FSFOA，均有巨大提升，而且在大部分數據集中的表現也超過了其他經典的算法和近年來提出的新型特征選擇算法。

5 結束語

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