基于遺傳算法的封裝式特征選擇研究

張照碩 侯能

摘要：在機器學習中，特征選擇在數據預處理階段被用來剔除數據集中的冗余特征。特征選擇分為嵌入式、過濾式、封裝式。其中，封裝式特征選擇在監督學習中應用廣泛。本文主要研究將遺傳算法用于封裝式特征選擇時，不同的個體選擇策略與種群更新策略的結合對監督學習算法預測準確率的影響。實驗結果表明，錦標賽選擇法與精英個體參與遺傳操作的精英保留策略相結合的方式，能夠得到最好的效果。通過在所有數據集上的計算總平均準確率發現，這種結合方式比將所有特征用于學習的平均準確率高出1.2%。

關鍵詞： 特征選擇; 遺傳算法; 個體選擇; 精英保留; 預測準確率

中圖分類號：TP311? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）19-0094-03

1? 引言

現如今，機器學習已廣泛應用在大數據分析、無人駕駛、人臉識別、自然語言處理等領域。作為人工智能研究的主要方向之一，機器學習將大量數據樣本與目標算法模型相結合，使計算機處理問題的能力能夠隨著樣本數量，即學習經驗的增加而增強。根據學習模式的不同，機器學習的定義也有所區別。其中，監督學習是最基礎，也是最重要的任務。監督學習中，數據集的樣本包含特征和標簽兩部分。已知監督學習算法的前提下，監督學習就是通過訓練樣本構造出與具體算法對應的模型，該模型隨后用于預測未知標簽值的樣本對應的標簽。預測準確率是評價模型預測能力的主要指標。為了構造預測能力更強的模型，除了需要更強的學習算法外，數據集的樣本數量和特征數量也是影響模型性能的主要因素。需要注意的是，模型的預測能力并不會隨著特征的增多而提高。相反過多的特征會引發“維度災難”現象。這一現象反而會使模型過擬合導致模型的預測能力下降。

為了緩解樣本的“維度災難”，如何剔除樣本中的冗余特征是數據預處理階段關注的主要問題。關于樣本的特征降維，特征選擇是一種重要的技術[1]。特征選擇有過濾式、選擇式、封裝式三大類。其中，過濾式特征選擇較簡單，對數據的理解有較好的表現，但對于特征優化、提升分類模型的泛化能力方面表現普通;嵌入式特征選擇將特征選擇算法嵌入學習算法中，學習結束時特征選擇算法也隨之結束;封裝式特征選擇從數據集的初始特征中不斷選擇子集，利用樣本的特征子集訓練目標學習器，然后根據學習器的性能評價特征子集的優劣。整個過程以不斷迭代的方式找到和目標學習算法最匹配的特征子集。三類特征選擇方法中，封裝式特征選擇是被廣泛使用的一種，也是目前的主要研究方法。

假設樣本的特征有M個，每個特征有被選擇、不被選擇兩種可能，特征子集的可能組合方式可達2M種。封裝式特征選擇就是從可能的2M組合中找到最優的特征子集組合的過程。這是一個NP難問題[2]。求解封裝式特征選擇問題的方法主要有窮舉法、啟發式方法、元啟發式方法。其中，窮舉法會評價所有的特征子集。然而，這種方式會導致計算開銷隨著特征數量的增加而非線性增加，因此僅適用于特征數量較少的數據集;啟發式通過人工制定的規則，從空特征子集開始逐步添加新未被選中的特征，或從全部特征開始逐步刪除一個特征，或者兩種方式結合。停止添加或刪除特征的依據都是監督算法的預測準確率不再提高為止。啟發式方法的特點是能高效地找到一個特征子集，但找到的特征子集距最優子集的評價指標較遠。元啟發式特征選擇利用進化算法或群體智能算法（如遺傳算法[3]、模擬退火[4]、蟻群算法[5]、粒子群算法[6]）搜索最優解的框架，通過將機器學習算法的預測能力作為評價指標，來引導最優子集的搜索。相對于啟發式方法，元啟發式方法能得到更好的近似最優解。

本文主要研究將遺傳算法用于封裝式特征選擇時，不同的個體選擇策略與種群更新策略的結合對監督學習算法預測準確率的影響。通過在標準數據集上進行實驗數據對比，發現采用錦標賽選擇策略和最佳父代參與后代產生的精英保留策略這一組合，能夠得到最好的優化效果。

2? 問題描述和算法原理

2.1 問題描述

特征選擇問題可以描述為：假設某數據集有N個樣本，每個樣本包含M個特征。特征選擇的目標是從M個特征中選擇m個特征（m≤M）的組合，使目標監督學習算法的預測能力達到盡可能最優的同時，m的取值也越小越好（m>0）。因此，在設計用于評價的目標函數時，不僅要考慮模型的預測能力，還要考慮被選中的特征數量。本文的優化目標除了模型的預測誤差率，還包括被選擇特征的數量占總特征數量的比值。具體地，目標函數形式化如下：

f（error， m）=α*error+（1-α）*（m/M）? ? ? ? ? ? ? ? ? ? ? （1）

其中，error表示監督算法的預測誤差率，（1-error）表示預測準確率。m表示被選擇特征的個數，M為樣本數據的特征總數。因此，m/M表示選中的特征數量占總特征數量的比重。α表示誤差率與特征占比之間的權重。本文中，α取值0.99。這意味著，監督學習算法的預測能力仍然主要評價因素[7]。

2.2 遺傳算法原理

遺傳算法是一種基于自然選擇和群體遺傳機理的搜索算法，它模擬了自然界生物中的“適者生存”的進化過程[8-9]。在利用遺傳算法求解問題時，每一個解都被編碼成一個“染色體”，即個體。若干個個體構成了種群（所有可能解的子集）。遺傳算法開始時會先隨機地產生一定數量的個體（即初始解），然后根據預定的目標函數對個體進行評估，給出相應的適應度值?；诖诉m應度值，遺傳算法通過選擇、雜交和突變產生下一代個體。經過每代的進化，使種群中的個體朝著最優解的方向前進。

3 遺傳算法求解封裝式特征選擇

將遺傳算法用于封裝式特征選擇的求解時，個體解的編碼方式，遺傳操作中的個體選擇、交叉、變異和種群更新過程如下所述：

2.1 編碼方式

就本問題而言，每個特征有兩種狀態，即選擇和未被選擇。用1表示被選中，0表示未被選擇，考慮所有M個特征，個體就可被表示成是長度為M的0-1串，該0-1串可代表一種特征選擇方案。每種方案都會對應一個目標函數值，即公式（1）的結果，用以評價方案的優劣。當個體數量為P時，遺傳算法的種群由P個0-1串及對應的目標函數值構成。種群的構成如圖1所示：

2.2 選擇策略

遺傳算法在每代進化時，會先從父代種群中選擇兩個個體。典型的選擇策略包括隨機選擇、輪盤賭選擇和錦標賽選擇。其中：

1）隨機選擇完全不考慮個體的適應度優劣，每個個體被選擇的概率是相等的。雖然公平，但難以保證優勢個體會被傳遞給下一代。

2）輪盤賭選擇法考慮了個體的適應度值，最優的個體，被選中的概率就越大。同時，適應度值較差的個體仍然有機會被選擇。

3）錦標賽選擇法是每次等概率地從種群中抽取一定數量的個體，對于被抽中的個體，再根據適應度值選擇出值最優的個體作為父代。該策略中，參與競賽的個體數量是需要考慮的因素。本文采用2個個體參與競賽的方式。

對比三種選擇策略的特點可以發現，隨機選擇挑選父代是完全盲目的;輪盤賭策略中，如果某個個體的適應度過于優秀，該個體被反復地選擇的概率就會大大增加，這會影響其他相對較優的個體被選中的概率;錦標賽選擇既考慮了個體的平等性，也考慮了適應度值的優劣。本文中的選擇策略主要考慮輪盤賭和2個體錦標賽選擇。

2.3? 交叉、 變異策略

經過選擇策略決定了兩個父代個體后，接下來的交叉和變異策略用于產生新的子代。其中，交叉策略把兩個父代個體的部分基因進行替換、重組，從而產生新的個體，即子代。遺傳算法中的交叉操作有多種不同的做法。本文采用典型的單點交叉，如圖2所示：

通過交叉操作產生新的個體，使搜索能繼續進行，從而發現更優的個體。

然而，當進化過程持續到一定代數后，會使搜索過程停滯，表明搜索過程陷入了局部最優。為避免這種情況，遺傳算法采用變異操作，使個體能以較低概率改變某個位置的狀態。這種策略能在一定程度上使搜索過程跳出局部最優。

2.4? 種群更新

經過前述的選擇、交叉、變異操作后，在當前進化代中，算法產生了與父代個體數量相同的子代種群。接下來的種群更新考慮如何用新個體替換父代個體。常規做法是用新個體完全替換父代個體。然而，這種替換沒有考慮子代個體沒有比父代最優個體更好的情況。相對地，另一種替換策略被稱為精英保留策略。該策略把父代中的最優個體（精英個體）在不經過交叉、變異的情況下直接復制到下一代中。為了保持種群的規模不變，精英個體用于替換新種群中適應度最小的個體。

2.5? 算法總流程

基于前述步驟，遺傳算法求解封裝式特征選擇問題的主要流程如下：

輸入：數據集、目標監督算法

輸出：分類準確率

Step1：初始化種群。

Step2： 將表示個體的特征子集用于剔除數據集中的部分特征。然后將剔除部分特征的數據集用于KNN分類器的訓練和預測。采用10折交叉驗證計算分類器的平均預測準確率。基于該準確率和個體被選中的特征數量，利用公式（1）得到每個體的適應度。

Step3： 根據適應度利用選擇策略挑選兩個父代。

Step4： 通過交叉、變異操作產生新的子代。

Step5： 利用精英保留策略來更新種群。

Step6：重復step2-5，若達到迭代終止條件，則輸出最優個體的分類準確率。

4? 實驗

為了測試遺傳算法在特征選擇問題中的性能，本文選用了UCI數據庫的部分數據集用于測試，數據集的具體參數如表1所示：

表1? 算法運行時間

[數據集名稱 特征數 樣本數 類別數 BreastEW 30 569 2 BreastTissue 9 106 6 Climate 18 540 2 Glass 9 214 7 ionosphere 34 351 2 seeds 7 210 3 sonar 60 208 2 SyntheticControl 60 600 6 waveform 21 5000 3 wine-data 13 178 3 yeast 8 1484 10 ]

以上選用的數據集中，所有特征的取值都是數值型。為使算法不受樣本特征的數據分布的干擾，在特征選擇之前，對每個樣本的特征值都進行了零均值規范化，使得所特征值的均值為0，標準差為1。對于機器學習算法，本文采用的是KNN算法。該算法實現選用sklearn庫中的實現，且采用默認參數（鄰域k=5，歐式距離計算樣本間的相似度）。

實驗中，遺傳算法的主要參數設置如表2所示：

對于遺傳算法，每個環節（種群初始化、選擇、交叉、變異、種群更新）有多種不同的做法，從各種組合中找出最佳組合是一個非常煩瑣且耗時的過程。本次實驗把重點放在了測試遺傳算法的三種選擇策略結合精英保留策略對KNN算法預測準確度的比較上。由于遺傳算法的隨機特性，每次運行的結果都會不同。實驗時，不同的算法在同一個數據集上運行10次，然后計算平均值。

實驗分別對比了不采用特征選擇，即全部特征用于學習的分類準確率，以及采用遺傳算法進行特征選擇后的分類準確率之間的優劣。其中，遺傳算法又分為基本遺傳算法GA1（隨機選擇，完全替換父代種群）、GA2（輪盤賭，精英保留）、GA3（錦標賽，精英保留）三種。根據不同的選擇策略，GA2的精英保留中的最優父代個體沒有參與后代產生的選擇、交叉和變異;而GA3的精英保留中的最優父代參與了后代產生的選擇、交叉和變異。GA2和GA3的精英保留策略有所區別的原因是輪盤賭會導致高質量個體被重復選擇的概率增大，這會導致種群多樣性的喪失。

測試結果如表3所示，采用基于GA3的特征選擇，KNN算法能在4個數據集上取得最好的預測準確率。比較突出的結果總結如下：

1）在Sonar數據集上，采用GA3對特征組合進行優化后，比全部特征用于分類的準確度要高出10%;在Ionosphere數據集上，采用GA3對特征組合進行優化后，比全部特征用于分類的準確度要高出5.4%。

2）對于GA2，比較突出的是在Sonar數據集上，比使用全部特征分類準確度高出5.6%;在Ionosphere數據集上比使用全部特征分類準確度高出3.5%;

3）對于GA1，在Sonar數據集上比使用全部特征分類準確度高出3.7%;在Ionosphere數據集上比使用全部特征分類準確度高出2.9%，Seeds數據集上比使用全部特征分類準確度高出2.1%。

從整體上對比三種遺傳算法的表現可以發現，采用GA3優化數據集的特征組合，可以使KNN方法在所有數據集上的平均預測準率，要比完全不使用特征選擇方法高出1.2%。

3 結論

本文對遺傳算法用于特征選擇問題時，不同的個體選擇策略和種群更新策略的組合展開了研究。在11個數據集上測試了不同結合方式的性能。實驗結果表明，錦標賽選擇法與精英父代個體參與遺傳算子操作的精英保留策略在總體上表現最好。在今后的工作中，將繼續對其他的智能算法在特征選擇的應用展開研究。

參考文獻：

[1] 李郅琴，杜建強，聶斌，等.特征選擇方法綜述[J].計算機工程與應用，2019，55（24）：10-19.

[2] 劉飛飛.特征選擇算法及應用綜述[J].辦公自動化，2018，23（21）：47-49.

[3] 陳倩茹，李雅麗，許科全，等.自調優自適應遺傳算法的WKNN特征選擇方法[J].計算機工程與應用，2021，57（20）：164-171.

[4] 王晗，劉維生，李輝，等.基于模擬退火算法特征選擇軟件的設計與實現[J].電子元器件與信息技術，2021，5（3）：144-146.

[5] 周金容，羅建.基于聚類和二元螞蟻系統的高維數據特征選擇算法[J].計算機應用與軟件，2021，38（10）：304-309，349.

[6] 鄧秀勤，李文洲，武繼剛，等.融合Shapley值和粒子群優化算法的混合特征選擇算法[J].計算機應用，2018，38（5）：1245-1249.

[7] Mafarja M M，Mirjalili S.Hybrid Whale Optimization Algorithm with simulated annealing for feature selection[J].Neurocomputing，2017，260：302-312.

[8] 張鑫源，胡曉敏，林盈.遺傳算法和粒子群優化算法的性能對比分析[J].計算機科學與探索，2014，8（1）：90-102.

[9] 張青雷，黨文君，段建國.基于自適應遺傳算法的大型關重件車間布局優化[J].機械設計與制造，2021（1）：236-239.

收稿日期：2022-02-25

基金項目：長江大學大學生創新創業訓練項目（Yz2020162）

作者簡介：張照碩（2001—），男，河北邢臺人，本科生，主要研究方向為機器學習應用;侯能，講師，博士。