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

張照碩 侯能

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

關(guān)鍵詞： 特征選擇; 遺傳算法; 個體選擇; 精英保留; 預(yù)測準(zhǔn)確率

中圖分類號：TP311? ? ? 文獻(xiàn)標(biāo)識碼：A

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

1? 引言

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

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

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

本文主要研究將遺傳算法用于封裝式特征選擇時，不同的個體選擇策略與種群更新策略的結(jié)合對監(jiān)督學(xué)習(xí)算法預(yù)測準(zhǔn)確率的影響。通過在標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對比，發(fā)現(xiàn)采用錦標(biāo)賽選擇策略和最佳父代參與后代產(chǎn)生的精英保留策略這一組合，能夠得到最好的優(yōu)化效果。

2? 問題描述和算法原理

2.1 問題描述

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

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

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

2.2 遺傳算法原理

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

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

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

2.1 編碼方式

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

2.2 選擇策略

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

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

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

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

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

2.3? 交叉、 變異策略

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

通過交叉操作產(chǎn)生新的個體，使搜索能繼續(xù)進(jìn)行，從而發(fā)現(xiàn)更優(yōu)的個體。

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

2.4? 種群更新

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

2.5? 算法總流程

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

輸入：數(shù)據(jù)集、目標(biāo)監(jiān)督算法

輸出：分類準(zhǔn)確率

Step1：初始化種群。

Step2： 將表示個體的特征子集用于剔除數(shù)據(jù)集中的部分特征。然后將剔除部分特征的數(shù)據(jù)集用于KNN分類器的訓(xùn)練和預(yù)測。采用10折交叉驗(yàn)證計算分類器的平均預(yù)測準(zhǔn)確率?；谠摐?zhǔn)確率和個體被選中的特征數(shù)量，利用公式（1）得到每個體的適應(yīng)度。

Step3： 根據(jù)適應(yīng)度利用選擇策略挑選兩個父代。

Step4： 通過交叉、變異操作產(chǎn)生新的子代。

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

Step6：重復(fù)step2-5，若達(dá)到迭代終止條件，則輸出最優(yōu)個體的分類準(zhǔn)確率。

4? 實(shí)驗(yàn)

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

表1? 算法運(yùn)行時間

[數(shù)據(jù)集名稱 特征數(shù) 樣本數(shù) 類別數(shù) 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 ]

以上選用的數(shù)據(jù)集中，所有特征的取值都是數(shù)值型。為使算法不受樣本特征的數(shù)據(jù)分布的干擾，在特征選擇之前，對每個樣本的特征值都進(jìn)行了零均值規(guī)范化，使得所特征值的均值為0，標(biāo)準(zhǔn)差為1。對于機(jī)器學(xué)習(xí)算法，本文采用的是KNN算法。該算法實(shí)現(xiàn)選用sklearn庫中的實(shí)現(xiàn)，且采用默認(rèn)參數(shù)（鄰域k=5，歐式距離計算樣本間的相似度）。

實(shí)驗(yàn)中，遺傳算法的主要參數(shù)設(shè)置如表2所示：

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

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

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

1）在Sonar數(shù)據(jù)集上，采用GA3對特征組合進(jìn)行優(yōu)化后，比全部特征用于分類的準(zhǔn)確度要高出10%;在Ionosphere數(shù)據(jù)集上，采用GA3對特征組合進(jìn)行優(yōu)化后，比全部特征用于分類的準(zhǔn)確度要高出5.4%。

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

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

從整體上對比三種遺傳算法的表現(xiàn)可以發(fā)現(xiàn)，采用GA3優(yōu)化數(shù)據(jù)集的特征組合，可以使KNN方法在所有數(shù)據(jù)集上的平均預(yù)測準(zhǔn)率，要比完全不使用特征選擇方法高出1.2%。

3 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

[6] 鄧秀勤，李文洲，武繼剛，等.融合Shapley值和粒子群優(yōu)化算法的混合特征選擇算法[J].計算機(jī)應(yīng)用，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] 張鑫源，胡曉敏，林盈.遺傳算法和粒子群優(yōu)化算法的性能對比分析[J].計算機(jī)科學(xué)與探索，2014，8（1）：90-102.

[9] 張青雷，黨文君，段建國.基于自適應(yīng)遺傳算法的大型關(guān)重件車間布局優(yōu)化[J].機(jī)械設(shè)計與制造，2021（1）：236-239.

收稿日期：2022-02-25

基金項(xiàng)目：長江大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目（Yz2020162）

作者簡介：張照碩（2001—），男，河北邢臺人，本科生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)應(yīng)用;侯能，講師，博士。