基于自適應(yīng)遺傳算法的混合特征選擇方法

裴作飛 李兆玉 王云鋒 姚立霜

(重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065)

0 引 言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，有許多新興的應(yīng)用出現(xiàn)，如社交媒體服務(wù)、高分辨圖像、文檔數(shù)據(jù)分析等。這些大數(shù)據(jù)應(yīng)用不僅包含冗余數(shù)據(jù)和低相關(guān)性的特征，并且維度過(guò)高導(dǎo)致維度災(zāi)難使得數(shù)據(jù)處理的復(fù)雜程度急劇增加，嚴(yán)重影響和限制數(shù)據(jù)分析和挖掘的性能[1]。為了解決上述問(wèn)題，特征選擇在不降低預(yù)測(cè)模型性能的前提下，按一定的選擇標(biāo)準(zhǔn)從輸入特征中選擇相關(guān)特征子集，減少數(shù)據(jù)維度，消除分類性能差的特征，提高學(xué)習(xí)算法的性能[2]。

特征子集選擇方法可分為過(guò)濾式、封裝式和嵌入式。過(guò)濾式方法是在分類算法訓(xùn)練之前根據(jù)數(shù)據(jù)集自身的特性選擇一個(gè)最優(yōu)的特征子集，去除不必要的特征[3]。封裝式方法利用分類算法的分類結(jié)果作為評(píng)價(jià)特征子集的指標(biāo)，選擇特征子集[4]。嵌入式方法將特征選擇的過(guò)程作為分類算法的一部分，例如分類與回歸樹算法[5]。此外通過(guò)結(jié)合遺傳算法(GA)[6-8]、蟻群算法(ACO)[9]、人工蜂群算法(ABC)[10]和模擬退火算法[11]等搜索策略，加快搜索進(jìn)程選擇最優(yōu)特征子集。Sheen等[12]利用決策樹作為分類算法，對(duì)比了三種過(guò)濾方法(CS、IG和Relief-F)選擇出來(lái)的不同特征子集在KDDCUP99上的分類正確率，實(shí)驗(yàn)表明三種算法將KDDCUP99數(shù)據(jù)集的特征約減到15維度時(shí)檢測(cè)率最好。陳友等[13]比較了過(guò)濾方法和封裝方法，實(shí)驗(yàn)表明采用基于SVM分類器作為封裝方法在TPR、FPR上的性能優(yōu)于基于CFS的Filter特征選擇方法。CFS過(guò)濾方法則在模型構(gòu)建時(shí)間上更短，耗用更少的計(jì)算資源與存儲(chǔ)資源。Schenkel等[14]提出將互信息與基于貝葉斯分類算法的封裝方法組成混合特征選擇算法，該方法對(duì)于復(fù)雜模式效果較好，在分類性能和對(duì)特征數(shù)目約減能力上有較好表現(xiàn)。

基于上述研究背景，針對(duì)數(shù)據(jù)中冗余和相關(guān)度低的特征，首先通過(guò)卡方統(tǒng)計(jì)方法對(duì)數(shù)據(jù)集進(jìn)行過(guò)濾。其次采用LightGBM分類器結(jié)合自適應(yīng)遺傳算法的封裝方法，搜索分類效果好的特征子集，提高入侵檢測(cè)的檢測(cè)效果并縮短SVM分類算法檢測(cè)時(shí)間。CS-GA混合特征選擇算法如圖1所示。

圖1 基于CS-GA的混合特征選擇流程

1 CS-GA混合特征選擇算法

1.1 基于CS過(guò)濾算法

在CS過(guò)濾算法特征選擇之前，對(duì)入侵檢測(cè)數(shù)據(jù)集中離散型特征進(jìn)行one-hot編碼，對(duì)連續(xù)型特征進(jìn)行標(biāo)準(zhǔn)化處理，即每個(gè)特征值featurei減去每個(gè)特征的平均值μi再除以特征值的標(biāo)準(zhǔn)差σi，計(jì)算公式如下：

(1)

數(shù)據(jù)預(yù)處理之后，采用CS算法對(duì)數(shù)據(jù)特征進(jìn)行過(guò)濾。針對(duì)入侵檢測(cè)問(wèn)題,通過(guò)χ2檢驗(yàn)每個(gè)特征與類別之間的獨(dú)立性并將入侵檢測(cè)中每個(gè)特征按χ2的統(tǒng)計(jì)值進(jìn)行降序排列，每個(gè)特征所得到的χ2統(tǒng)計(jì)值越大，說(shuō)明該特征在入侵檢測(cè)中分類效果越好且與類的相關(guān)性越強(qiáng)。因此，將每個(gè)特征與類別c之間的卡方公式表示為：

(2)

(3)

式中：f表示入侵檢測(cè)中某一個(gè)特征的有或無(wú)；c表示類別，c等于0表示正常類型，1表示異常類型；N是觀察值，例如在入侵檢測(cè)數(shù)據(jù)集中N11表示選擇該特征且為異常類型的樣本數(shù)量；E是期望值，假設(shè)在入侵檢測(cè)數(shù)據(jù)中的特征與類別c互相獨(dú)立；Rf是其特征f在數(shù)據(jù)集中的樣本數(shù)；Ic是特征f在類別c中的樣本數(shù)。式(2)-式(3)只支持入侵檢測(cè)正常和異常的2分類研究。

CS算法可以去除相關(guān)性低的特征，但沒有考慮特征之間的交互作用，為了進(jìn)一步降低特征維度，提高算法的性能，將過(guò)濾后的特征子集采用LightGBM作為封裝方法進(jìn)一步約減特征。

1.2 基于LightGBM結(jié)合自適應(yīng)遺傳算法的封裝方法

1.2.1 種群個(gè)體編碼

通過(guò)CS過(guò)濾算法對(duì)入侵檢測(cè)相關(guān)性低的特征過(guò)濾之后，對(duì)剩余特征數(shù)據(jù)集進(jìn)行隨機(jī)初始化種群，采用二進(jìn)制編碼對(duì)種群個(gè)體進(jìn)行編碼。入侵檢測(cè)數(shù)據(jù)中有41個(gè)特征，所以染色體的大小為41。其中染色體上的每個(gè)基因值可以為0或1。0表示染色體中該基因不存在，沒有選擇該基因?qū)?yīng)的特征；1表示染色體中該基因存在，即表示選擇該基因?qū)?yīng)的特征。如一條染色體g=[1,0,1,0,1,0,…,0]，表示選擇第一個(gè)、第三個(gè)和第五個(gè)特征。

1.2.2 適應(yīng)度函數(shù)計(jì)算

遺傳算法本身就可以作為一種特征選擇算法，能夠發(fā)現(xiàn)并消除冗余特征，但遺傳算法性能的好壞往往取決于適應(yīng)度函數(shù)的定義。為了更大化減少特征，獲得分類效果更好的特征，可以采用LightGBM算法作為GA的適應(yīng)度函數(shù)計(jì)算。LightGBM分類算法在入侵檢測(cè)問(wèn)題上不需要注重特征值的大小，只需要將字符映射成數(shù)值型就可以進(jìn)行訓(xùn)練[15]。因此該算法作為封裝算法具有更快的訓(xùn)練效率和更好的準(zhǔn)確率。為了在獲得較高分類效果的同時(shí)降低特征維度，改進(jìn)的適應(yīng)度函數(shù)定義如下：

(4)

式中：L(x)為L(zhǎng)ightGBM分類算法對(duì)于所選特征向量x的分類準(zhǔn)確率；Fn表示特征維度個(gè)數(shù)；α∈[0,1]，當(dāng)α等于1時(shí)表明適應(yīng)度函數(shù)值取決于L(x)，當(dāng)α等于0時(shí)適應(yīng)度函數(shù)值取決于Fn。因此可以調(diào)節(jié)α的值來(lái)獲得L(x)與Fn之間的平衡，選擇分類效果好并且維度相對(duì)較低的特征子集。

1.2.3 選擇算子

傳統(tǒng)遺傳算法選擇算子采用輪盤賭策略，該策略有一定概率選擇到分類效果差的種群個(gè)體，導(dǎo)致選擇的特征子集不好，影響遺傳算法性能。因此，采用錦標(biāo)賽選擇策略，選擇適應(yīng)度好的種群個(gè)體。該策略從種群中一次選擇出3個(gè)個(gè)體，選擇最優(yōu)的1個(gè)種群個(gè)體進(jìn)入后代種群。重復(fù)此操作，直到新的種群大小達(dá)到原始種群大小。

1.2.4 交叉和變異算子

交叉的目的是將父代種群個(gè)體中的優(yōu)秀基因遺傳給子代保證遺傳算法的搜索能力和穩(wěn)定性，變異的目的是防止遺傳算法過(guò)早收斂并且可以讓遺傳算法在局部的隨機(jī)搜索能力更強(qiáng)。在CS-GA中使用單點(diǎn)操作方法對(duì)種群個(gè)體進(jìn)行交叉和變異。GA交叉率和變異率往往根據(jù)實(shí)際情況和經(jīng)驗(yàn)取值，但問(wèn)題是交叉率和變異率取值過(guò)大，會(huì)導(dǎo)致個(gè)體適應(yīng)度波動(dòng)較大。交叉率和變異率取值小，會(huì)導(dǎo)致搜索緩慢早熟收斂。因此，采用自適應(yīng)的思想對(duì)交叉算子與變異算子進(jìn)行改進(jìn)：

(5)

(6)

式中：Pc1、Pc2是交叉率；Pm1、Pm2是變異率；fmax和favg為每代群體中最大適應(yīng)度值和平均適應(yīng)度值；f′為2個(gè)交叉?zhèn)€體中較大的適應(yīng)度值；f為變異個(gè)體的適應(yīng)度值。由式(5)-式(6)可知當(dāng)f和f′小于favg時(shí)，使用取值大的Pc1和Pc2提高遺傳算法的搜索能力。當(dāng)遺傳算法到后期和f大于favg時(shí)通過(guò)自適應(yīng)方法降低交叉率和變異率，保證遺傳算法的穩(wěn)定性并逐漸向最優(yōu)解靠近。因此，采用自適應(yīng)的思想改進(jìn)交叉和變異算子可以使遺傳算法具有更好的適應(yīng)度和全局收斂性。

1.2.5 算法終止條件

當(dāng)CS-GA達(dá)到最大迭代次數(shù)，或者當(dāng)前種群適應(yīng)度值達(dá)到0.999 9時(shí)，算法終止。

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

2.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)使用KDDCUP99 10%數(shù)據(jù)集，在入侵檢測(cè)數(shù)據(jù)中將類標(biāo)識(shí)屬于正常記錄的數(shù)據(jù)設(shè)置為0，其他攻擊類型數(shù)據(jù)設(shè)置為1。訓(xùn)練樣本與測(cè)試樣本分別提取自訓(xùn)練數(shù)據(jù)集kddcup.data_10_percent_corrected.gz和測(cè)試數(shù)據(jù)集corrected.gz。將全部訓(xùn)練數(shù)據(jù)集作為輸入數(shù)據(jù)用于三種算法進(jìn)行特征選擇，此外在訓(xùn)練數(shù)據(jù)集與測(cè)試數(shù)據(jù)集中隨機(jī)抽樣出2組10 000條訓(xùn)練數(shù)據(jù)和6組6 000條測(cè)試數(shù)據(jù)用于測(cè)試特征子集的性能。

2.2 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)的編程環(huán)境為Ipython Notebook，硬件環(huán)境為Intel Core i5-7500@3.40 GHz，RAM 8 GB，Windows 10 64位操作系統(tǒng)， CS-GA算法的參數(shù)設(shè)置如表1所示。

表1 CS-GA算法的參數(shù)設(shè)置

表1中遺傳算法種群大小一般在20～50之間，這里根據(jù)數(shù)據(jù)集的大小取50，染色體基因數(shù)與數(shù)據(jù)特征維度個(gè)數(shù)均取41。如圖2所示，最大進(jìn)化代數(shù)選擇80時(shí)，種群評(píng)價(jià)適應(yīng)度值最好。自適應(yīng)遺傳算法的交叉率和變異率根據(jù)經(jīng)驗(yàn)數(shù)據(jù)設(shè)定，在前期Pc1和Pm1取值大一些，保證算法搜索能力，在后期Pc2和Pm2小一些，保證算法穩(wěn)定性。

圖2 CS-GA算法進(jìn)化曲線

2.3 實(shí)驗(yàn)結(jié)果及性能對(duì)比

2.3.1 CS-GA、GA、Gini-GA選擇結(jié)果對(duì)比

為了驗(yàn)證CS-GA在特征選擇上的優(yōu)勢(shì)，首先將全部訓(xùn)練數(shù)據(jù)集作為輸入數(shù)據(jù)，用于CS-GA、GA、Gini-GA進(jìn)行特征選擇實(shí)驗(yàn)。GA采用未改進(jìn)的自適應(yīng)遺傳算法用作特征選擇，Gini-GA采用Gini(基尼系數(shù))對(duì)全部特征過(guò)濾，然后通過(guò)未改進(jìn)的自適應(yīng)遺傳算法搜索特征子集，未改進(jìn)的自適應(yīng)遺傳算法的參數(shù)和CS-GA一致。由于遺傳算法為不確定搜索算法，所以對(duì)3種算法進(jìn)行20次選擇實(shí)驗(yàn)，并將得到的特征子集保存。最后，將第一組訓(xùn)練數(shù)據(jù)和第一組測(cè)試數(shù)據(jù)作為輸入數(shù)據(jù)，通過(guò)SVM分類器測(cè)量特征子集的檢測(cè)率、誤報(bào)率和測(cè)試時(shí)間。表2給出了3種算法20次特征選擇結(jié)果的平均性能參數(shù)。

表2 3種算法20次特征選擇結(jié)果平均性能參數(shù)

可以看出，CS-GA作為一種相關(guān)性過(guò)濾算法，在特征選擇上速度較快，比其他兩種算法具有更短的建模時(shí)間。總的來(lái)說(shuō)，CS-GA作為混合特征選擇算法在特征維度的約減能力上好于GA和Gini-GA，在檢測(cè)率和誤報(bào)率上也比GA和Gini-GA要好。傳統(tǒng)自適應(yīng)GA作為特征選擇算法，選擇出來(lái)的特征子集在檢測(cè)率、誤報(bào)率、維度等性能指標(biāo)上無(wú)明顯優(yōu)勢(shì)。

2.3.2 特征選擇結(jié)果及性能對(duì)比

在CS-GA、GA和Gini-GA 20次特征選擇結(jié)果中結(jié)合檢測(cè)率、誤報(bào)率和維度，選擇出一組綜合性能最好的特征序列用于入侵檢測(cè)問(wèn)題研究，如表3所示。為了充分驗(yàn)證最終選擇的特征子集的好壞，通過(guò)第2組訓(xùn)練數(shù)據(jù)和6組測(cè)試數(shù)據(jù)作為輸入數(shù)據(jù)，采用支持向量機(jī)分類算法分別測(cè)試3種算法特征子集在6組測(cè)試數(shù)據(jù)中的性能。

表3 特征選擇結(jié)果

如圖3、圖4所示，All-SVM表示選擇全部41個(gè)特征，通過(guò)SVM分類器測(cè)量其檢測(cè)率和誤報(bào)率。結(jié)果顯示，入侵檢測(cè)采用全部特征時(shí)其檢測(cè)率和誤報(bào)率效果最差。GA雖然可以對(duì)特征進(jìn)行降維，但是在檢測(cè)率和誤報(bào)率上與All-SVM使用全部特征子集性能相當(dāng)。Gini-GA中基尼系數(shù)對(duì)于入侵檢測(cè)問(wèn)題中處理連續(xù)型數(shù)值特征的約減能力上不如CS-GA，CS-GA在特征約減能力上效果最好。CS-GA選擇出來(lái)的特征子集在6組不同的測(cè)試集上的檢測(cè)率和誤報(bào)率上也明顯優(yōu)于其他對(duì)比算法。

圖3 6組測(cè)試樣本的檢測(cè)率

圖4 6組測(cè)試樣本的誤報(bào)率

圖5比較了4種特征子集在SVM分類器上的測(cè)試時(shí)間。結(jié)果顯示，采用全部特征的All-SVM需要更長(zhǎng)的測(cè)試時(shí)間，而CS-GA將入侵檢測(cè)數(shù)據(jù)集中41個(gè)特征維度約減到5維，極大地降低分類器的訓(xùn)練難度。CS-GA選擇出來(lái)的特征子集相對(duì)于其他算法在基于SVM算法上測(cè)試時(shí)間最短，在一定程度上解決入侵檢測(cè)實(shí)時(shí)性問(wèn)題。

圖5 6組測(cè)試樣本的測(cè)試時(shí)間/s

3 結(jié) 語(yǔ)

本文通過(guò)卡方算法對(duì)入侵檢測(cè)數(shù)據(jù)集中冗余特征進(jìn)行過(guò)濾，采用LightGBM分類器結(jié)合自適應(yīng)遺傳算法構(gòu)成混合特征選擇方法，搜索分類效果好的特征子集。實(shí)驗(yàn)結(jié)果表明：CS-GA能夠縮減SVM分類算法的測(cè)試時(shí)間，有效刪除冗余特征和相關(guān)度低的特征，提高入侵檢測(cè)的檢測(cè)性能，降低誤報(bào)率。后續(xù)會(huì)考慮將CS-GA和其他過(guò)濾算法結(jié)合，處理不同類型數(shù)據(jù)特征，進(jìn)一步提高算法的特征約減能力。