一種基于最優(yōu)特征選擇改進(jìn)的遺傳算法*

辛 宇,童孟軍*,華宇婷

(1.浙江農(nóng)林大學(xué)信息工程學(xué)院,浙江 臨安 311300;2.浙江省林業(yè)智能監(jiān)測與信息技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,浙江 臨安 311300)

1 遺傳算法概述

1969年美國大學(xué)Michigan的Holland教授提出了遺傳算法,其核心理論融合了達(dá)爾文進(jìn)化論和物種選擇的思想[9～10]。遺傳算法具有堅(jiān)實(shí)的生物學(xué)基礎(chǔ),通過選擇(Selection)、交叉(Crossover)以及變異(Mutation)等機(jī)制模擬了在不同的自然環(huán)境、不同的生存條件下某一種群物競天擇的過程,從而將原始問題轉(zhuǎn)變?yōu)樽顑?yōu)結(jié)果的隨機(jī)搜索問題。算法中適應(yīng)性函數(shù)具有很強(qiáng)的廣泛性,根據(jù)設(shè)計(jì)可以表征各類實(shí)際問題,再加之算法本身利于并行化、領(lǐng)域無關(guān)等特性常用于商業(yè)金融[10]、模式識(shí)別、計(jì)算科學(xué)[12-13]等最優(yōu)解搜索領(lǐng)域。隨著人工智能的興起,機(jī)器學(xué)習(xí)模型中的特征選擇便可以借助遺傳算法表示為在龐大復(fù)雜的特征空間中搜索最優(yōu)特征子集的過程。

遺傳算法作為一種自適應(yīng)的搜索算法,其核心思想在于將原始問題進(jìn)行編碼以轉(zhuǎn)變?yōu)樽匀环N群的基因序列參與進(jìn)化過程。其中原始問題解的子集可看作種群中的每個(gè)個(gè)體;定義適應(yīng)性函數(shù)表征種群進(jìn)化環(huán)境的難易程度,同時(shí)將原始問題進(jìn)行編碼作為每個(gè)個(gè)體的基因參與每輪進(jìn)化的適應(yīng)性衡量得到適應(yīng)值;定義選擇算子表征種群進(jìn)化中的優(yōu)勝劣汰過程,再一次進(jìn)化中根據(jù)個(gè)體的適應(yīng)值選擇進(jìn)入下一輪進(jìn)化的優(yōu)良個(gè)體;定義交叉算子表征種群在進(jìn)化中由母本父本交叉形成新個(gè)體的過程;定義變異算子表征種群在進(jìn)化過程中個(gè)體基因序列的突變現(xiàn)象。遺傳算法的基礎(chǔ)框架如圖1所示。

圖1 遺傳算法的基礎(chǔ)框架

2 基于特征選擇的遺傳算法

2.1 種群個(gè)體的編碼

遺傳算法將原始問題所有可行解模擬為種群中的個(gè)體,種群規(guī)模表示了算法搜索空間的大小,在初始化種群時(shí),若種群規(guī)模過大或過小算法都難以有效的收斂到全局最優(yōu)。所以種群初始化大小M一般為50～100,并且根據(jù)問題的難易、類型不同進(jìn)行調(diào)整。

其中種群個(gè)體代表了每一種可能的特征組合,通常對(duì)個(gè)體基因采用二進(jìn)制進(jìn)行編碼,使用0,1標(biāo)記每個(gè)特征是否被選中,即進(jìn)化個(gè)體的基因由一個(gè)二進(jìn)制串表示。那么維度為N的特征空間編碼后對(duì)應(yīng)長度為N的二進(jìn)制基因串,其中Ni為1表示該特征被選中,否則Ni為0,例如[1,1,1,0,…,1]。

本文中在對(duì)種群個(gè)體編碼前,引入了一個(gè)方差閾值,然后將每個(gè)特征的方差值與閾值進(jìn)行對(duì)比,根據(jù)是否大于閾值對(duì)原始特征空間進(jìn)行初次過濾,目的在于利用統(tǒng)計(jì)學(xué)原理剔除那些變化幅度不太,沒有區(qū)分度的特征。認(rèn)為這些特征在模型對(duì)目標(biāo)變量的區(qū)分上起到了很小的甚至為零的效果。并且經(jīng)過最大方差的篩選,削減了種群個(gè)體基因串的規(guī)模,進(jìn)而減小了遺傳算法搜索的范圍,提高了算法中的迭代速度。方差篩選算法如下:

N:原始特征空間的維度;

V:預(yù)先設(shè)置的方差閾值;

SetV

LoopitoN:

If Variance(Ni)<=V:

RemoveNi

2.2 適應(yīng)性函數(shù)

適應(yīng)性函數(shù)是遺傳算法中最為關(guān)鍵的部分,它描述了種群在進(jìn)化過程中的環(huán)境難易程度,由于遺傳算法不加入先驗(yàn)知識(shí)的考慮僅依靠適應(yīng)性函數(shù)對(duì)種群質(zhì)量作出調(diào)整,所以優(yōu)秀的適應(yīng)性函數(shù)能夠更好指導(dǎo)算法向全局最優(yōu)點(diǎn)收斂。針對(duì)特征選擇問題本文利用預(yù)測模型的輸出值作為個(gè)體的適應(yīng)值,該值能夠直接反映不同特征以及不同特征組合對(duì)預(yù)測問題的擬合程度和適應(yīng)性,適應(yīng)值越高個(gè)體越優(yōu)良對(duì)應(yīng)的特征組合則越有效。同時(shí)引入了多折交叉驗(yàn)證以減緩個(gè)體對(duì)目標(biāo)的過擬合,保證個(gè)體適應(yīng)性值的魯棒性;使用線性模型和樹模型的結(jié)果融合以增強(qiáng)特征組合的魯棒性。綜上每個(gè)個(gè)體的適應(yīng)性值F(Xi)可表示為:

(1)

式中:M代表種群中個(gè)體的數(shù)量;N代表每個(gè)個(gè)體的基因長度;cv代表每個(gè)模型的交叉驗(yàn)證數(shù);L(x1,…,xn)代表線性模型,本文中其輸出值由線性回歸導(dǎo)出;G(x1,…,xn)代表樹模型,本文中其輸出值由梯度迭代樹導(dǎo)出;

2.3 遺傳算子的設(shè)計(jì)

2.3.1 選擇算子

選擇算子模擬了自然生物進(jìn)化中優(yōu)勝劣汰的過程,該算子在進(jìn)化中根據(jù)種群內(nèi)每個(gè)個(gè)體的適應(yīng)值進(jìn)行判斷,適應(yīng)值高即優(yōu)良的個(gè)體有較大概率進(jìn)入下一輪進(jìn)化,反之適應(yīng)值低的個(gè)體有較小概率被選中;選擇算子保證了優(yōu)良的基因能夠在種群內(nèi)遺傳下去,意味著在預(yù)測模型上表現(xiàn)好的特征組合將會(huì)被保留。本文中的選擇算子采用輪盤賭算法,該算法直接表征了個(gè)體被選中的概率與個(gè)體適應(yīng)值的正比關(guān)系,公式化如下:

(2)

同時(shí)由于本文采用均方誤差(MSE)衡量預(yù)測結(jié)果的準(zhǔn)確性,為了保證輪盤賭選擇算子在選擇最優(yōu)個(gè)體時(shí)與評(píng)測指標(biāo)相一致,對(duì)個(gè)體每一輪進(jìn)化的適應(yīng)值做取倒數(shù)操作,即:

(3)

2.3.2 交叉算子

交叉算子模擬了自然環(huán)境中父本母本通過交叉基因產(chǎn)生新一代的過程,該算子體現(xiàn)了遺傳算法啟發(fā)性搜索的特點(diǎn),同時(shí)它也是每次進(jìn)化獲得優(yōu)良個(gè)體的關(guān)鍵手段。特征選擇中的交叉算子極大程度上改變了原始特征的組合方式,使得算法在每一輪進(jìn)化中考慮了不同交叉特征對(duì)預(yù)測目標(biāo)的影響能力。由于父本母本的基因編碼代表了特征子集,為了防止特征在交叉過程中被大范圍交換丟失了父本母本原有的優(yōu)良特征,本文設(shè)計(jì)了定長基因段交叉算法。該算法描述如下:①隨機(jī)從種群中選擇兩個(gè)個(gè)體作為父本和母本;②定義參與交叉的基因段長度L,L為原始基因長度的三分之一并向上取整;③隨機(jī)選擇交叉起始位點(diǎn)A和終點(diǎn)B,使得|A-B|=L;④遍歷交換基因段,若基因位點(diǎn)取值相同,則認(rèn)為父本母本對(duì)該特征的意見一致,可保留至下一代,否則直接交換父本母本的基因位點(diǎn),例如:

父本:[1,1,1,(1,1,0,1),0,0,1]

母本:[1,0,0,(1,0,1,1),0,0,0]

如上長度為10的父本母本基因組,在某輪進(jìn)化中隨機(jī)選擇了4號(hào)至7號(hào)基因位點(diǎn),則除了4號(hào)基因位點(diǎn)外,其余位點(diǎn)相互交換,形成新的兩個(gè)個(gè)體基因。

2.3.3 變異算子

變異算子主要體現(xiàn)了種群在進(jìn)化過程中,基因位點(diǎn)發(fā)生突變的現(xiàn)象,隨著這種變異的發(fā)生個(gè)體的特征也會(huì)改變,它屬于遺傳算法中的輔助算子,為遺傳算法提供了一定程度的多樣性和可能性,大大提高了搜索的隨機(jī)性。根據(jù)自然環(huán)境中基因突變發(fā)生的低概率性和不確定性,本文中采用的變異算子計(jì)算過程描述如下:①定義一個(gè)極小的突變閾值;②隨機(jī)選取若干個(gè)基因位點(diǎn),對(duì)于每個(gè)基因位點(diǎn)產(chǎn)生一個(gè)隨機(jī)數(shù)r;③若隨機(jī)數(shù)大于突變閾值,則對(duì)應(yīng)的基因位點(diǎn)做取反操作。

例如:

M1:[1,1,1,1,1,0,1,0,0,1]

在某輪進(jìn)化中,M1個(gè)體隨機(jī)選擇到4號(hào)和8號(hào)基因位點(diǎn),那么對(duì)每個(gè)位點(diǎn)生成隨機(jī)數(shù)r1、r2后,若r1>,r2<,則變異后的個(gè)體基因?yàn)?

M1:[1,1,1,0,1,0,1,0,0,1]

3.4 算法流程

基于特征選擇的遺傳算法是經(jīng)過特征工程后,在具有一定維度的特征空間上進(jìn)行搜索的過程。對(duì)于原始數(shù)據(jù)本文采用了獨(dú)熱編碼處理類別類型特征,采用交叉組合的方式處理數(shù)值類別的特征,通過這種方法在沒有引入先驗(yàn)知識(shí)的前提下,極大的擴(kuò)充了原始特征空間。然后對(duì)該特征空間進(jìn)行方差過濾構(gòu)造特征候選集,同時(shí)特征候選集二進(jìn)制編碼初始化種群參與遺傳進(jìn)化,在達(dá)到最大迭代次數(shù)后返回最優(yōu)特征子集,最后利用該子集進(jìn)行預(yù)測,并給出評(píng)價(jià)。其基本流程如圖2所示。

圖2 遺傳算法流程圖

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

本文中的實(shí)驗(yàn)環(huán)境使用Python3.6.1版本編寫遺傳算法框架;Sklearn-0.19.1、Pandas-0.22.0、Numpy1.14.2機(jī)器學(xué)習(xí)庫處理數(shù)據(jù)特征和調(diào)用預(yù)測算法模型;開發(fā)編譯器使用Ipython-notebook調(diào)試算法。實(shí)驗(yàn)數(shù)據(jù)使用5種用以數(shù)值型預(yù)測的UCI公開標(biāo)準(zhǔn)測試數(shù)據(jù)集,為方便起見,定義5個(gè)數(shù)據(jù)集分別為D0、D1、D2、D3、D4實(shí)驗(yàn)數(shù)據(jù)集,各個(gè)數(shù)據(jù)集的樣本維數(shù)、原始特征維數(shù)、經(jīng)過特征工程后的維數(shù)如表4.1所示;本文利用以上數(shù)據(jù)集獲得遺傳算法的輸入特征,并構(gòu)建線性回歸模型進(jìn)行預(yù)測。

表1 數(shù)據(jù)集特征信息

(4)

定義實(shí)驗(yàn)中算法模型參數(shù)如下:

種群規(guī)模為20,每個(gè)個(gè)體基因長度為經(jīng)過最大方差篩選后的數(shù)量,種群最大遺傳次數(shù)分別為10、20、30次,用L1～L3表示;最大方差閾值設(shè)定為0.1,適應(yīng)性函數(shù)中使用的線性回歸與GBDT模型均使用默認(rèn)參數(shù),交叉驗(yàn)證次數(shù)為10次,最后使用線性回歸(LR)和進(jìn)行預(yù)測,對(duì)比特征篩選前后不同模型的預(yù)測情況,取MSE較低為優(yōu)。

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

如表2中所示,5個(gè)數(shù)據(jù)集在經(jīng)過最大方差篩選后有效剔除了區(qū)分度較低的特征,其中D0、D1、D3數(shù)據(jù)集縮減了2～3個(gè)維度說明原始特征取值豐富,對(duì)目標(biāo)變量的區(qū)分和識(shí)別度較高;其他數(shù)據(jù)集縮減了半數(shù)以上的維度,去掉了取值較為單一的數(shù)據(jù),很大程度降低了特征空間維度,達(dá)到了縮減搜索范圍大小的目的。

表2 方差篩選

表3中N表示了5個(gè)數(shù)據(jù)集在L3遺傳次數(shù)選擇后剩下的特征即最優(yōu)特征子集的規(guī)模,與選擇前相比選擇后明顯縮減了特征空間大小,特別的D3數(shù)據(jù)集縮減率達(dá)到了50%;MSE2、MSE1分別表示特征選擇前后最終線性回歸模型的MSE值,對(duì)比二者可見5個(gè)數(shù)據(jù)集使用遺傳算法得到的最優(yōu)特征子集后不同程度上提升了預(yù)測的準(zhǔn)確率,其中D1數(shù)據(jù)集準(zhǔn)確率上升幅度最大達(dá)到90%。表明該算法有效的篩選出了與目標(biāo)變量相關(guān)度最大,最能夠區(qū)分目標(biāo)值的特征。

表3 篩選后特征數(shù)量與MSE

如圖3～圖7所示,在不同的遺傳次數(shù)下,5個(gè)數(shù)據(jù)集經(jīng)過特征選擇后的MSE值均得到了提升,并且隨著遺傳次數(shù)的增加,其最優(yōu)特征子集特征得到的準(zhǔn)確率在不斷提升,表明算法具有一定的隨機(jī)穩(wěn)定性;主要因?yàn)檫z傳次數(shù)的增加,算法包含的隨機(jī)性隨之增大,其考慮的特征組合也越多從而能夠產(chǎn)生較為優(yōu)秀的特征子集。

圖3 D0數(shù)據(jù)集MSE變化

圖4 D1數(shù)據(jù)集MSE變化

圖5 D2數(shù)據(jù)集MSE變化

圖6 D3數(shù)據(jù)集MSE變化

圖7 D4數(shù)據(jù)集MSE變化

另外如圖8所示,以D0數(shù)據(jù)集為例,隨著遺傳次數(shù)的增加遺傳算法運(yùn)行的時(shí)間也隨之提高,然而得到的特征組合所帶來準(zhǔn)確率的提升卻不足以彌補(bǔ)算法運(yùn)行效率的降低,所以將遺傳次數(shù)控制在適合的范圍才能夠從效率和準(zhǔn)確率優(yōu)化上充分發(fā)揮遺傳算法的優(yōu)點(diǎn)。

圖8 D0數(shù)據(jù)集遺傳算法時(shí)間

L3遺傳次數(shù)選擇特征后與選擇前的預(yù)測模型運(yùn)行時(shí)間如圖9所示,其中T1代表特征選擇前的模型運(yùn)行時(shí)間,T2代表特征選擇后的運(yùn)行時(shí)間。易見特征維數(shù)的降低能夠減少預(yù)測算法的運(yùn)行時(shí)間,主要由于直接降低了模型復(fù)雜度,使得模型對(duì)每個(gè)特征的遍歷次數(shù)大大降低,表明該遺傳算法能夠在提高預(yù)測準(zhǔn)確率的同時(shí)優(yōu)化預(yù)測效率。

圖9 各數(shù)據(jù)集運(yùn)行效率

圖11 D1數(shù)據(jù)集MSE對(duì)比

如圖10～圖14所示,MSE3表示單一模型作為適應(yīng)性函數(shù)的遺傳算法下最終的預(yù)測準(zhǔn)確率,可見在不同的遺傳次數(shù)下,使用適應(yīng)性函數(shù)為單一模型的遺傳算法產(chǎn)生的特征,其預(yù)測結(jié)果的精確度均低于本文使用復(fù)合適應(yīng)性函數(shù)的遺傳算法,其中D1數(shù)據(jù)集上預(yù)測準(zhǔn)確率的差值超過了100,主要原因在于更復(fù)雜的適應(yīng)性函數(shù)趨向于選擇更為強(qiáng)健的特征,并且交叉算子中產(chǎn)生了更加豐富多樣的特征組合,提高了候選特征的質(zhì)量。

圖10 D0數(shù)據(jù)集MSE對(duì)比

圖12 D2數(shù)據(jù)集MSE對(duì)比

圖13 D3數(shù)據(jù)集MSE對(duì)比

圖14 D4數(shù)據(jù)集MSE對(duì)比

5 總結(jié)

本文主要研究了機(jī)器學(xué)習(xí)中模型特征篩選的過程。針對(duì)原始特征空間維度過大、適應(yīng)性函數(shù)評(píng)價(jià)方式單一、多特征組合優(yōu)化搜索問題引入了一種改進(jìn)的啟發(fā)式遺傳算法,并且利用多個(gè)標(biāo)準(zhǔn)測試數(shù)據(jù)集在該遺傳算法上的表現(xiàn),分析特征篩選后的模型預(yù)測準(zhǔn)確率和篩選的特征數(shù)量,驗(yàn)證了該算法在數(shù)值型預(yù)測問題上對(duì)于原始特征能夠在篩選出較優(yōu)特征組合的同時(shí)達(dá)到降維的效果,最終提高預(yù)測精度。本文對(duì)數(shù)值型預(yù)測中特征選擇問題的解決提供了一定的可行性和可靠性。未來將會(huì)繼續(xù)在特征工程優(yōu)化、遺傳算法各算子優(yōu)化上進(jìn)一步研究,使算法泛化性、魯棒性更加強(qiáng)健。