基于自適應遺傳算法的混合特征選擇方法

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

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

0 引 言

隨著大數據時代的到來，有許多新興的應用出現，如社交媒體服務、高分辨圖像、文檔數據分析等。這些大數據應用不僅包含冗余數據和低相關性的特征，并且維度過高導致維度災難使得數據處理的復雜程度急劇增加，嚴重影響和限制數據分析和挖掘的性能[1]。為了解決上述問題，特征選擇在不降低預測模型性能的前提下，按一定的選擇標準從輸入特征中選擇相關特征子集，減少數據維度，消除分類性能差的特征，提高學習算法的性能[2]。

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

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

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

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

1.1 基于CS過濾算法

在CS過濾算法特征選擇之前，對入侵檢測數據集中離散型特征進行one-hot編碼，對連續型特征進行標準化處理，即每個特征值featurei減去每個特征的平均值μi再除以特征值的標準差σi，計算公式如下：

(1)

數據預處理之后，采用CS算法對數據特征進行過濾。針對入侵檢測問題,通過χ2檢驗每個特征與類別之間的獨立性并將入侵檢測中每個特征按χ2的統計值進行降序排列，每個特征所得到的χ2統計值越大，說明該特征在入侵檢測中分類效果越好且與類的相關性越強。因此，將每個特征與類別c之間的卡方公式表示為：

(2)

(3)

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

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

1.2 基于LightGBM結合自適應遺傳算法的封裝方法

1.2.1 種群個體編碼

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

1.2.2 適應度函數計算

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

(4)

式中：L(x)為LightGBM分類算法對于所選特征向量x的分類準確率；Fn表示特征維度個數；α∈[0,1]，當α等于1時表明適應度函數值取決于L(x)，當α等于0時適應度函數值取決于Fn。因此可以調節α的值來獲得L(x)與Fn之間的平衡，選擇分類效果好并且維度相對較低的特征子集。

1.2.3 選擇算子

傳統遺傳算法選擇算子采用輪盤賭策略，該策略有一定概率選擇到分類效果差的種群個體，導致選擇的特征子集不好，影響遺傳算法性能。因此，采用錦標賽選擇策略，選擇適應度好的種群個體。該策略從種群中一次選擇出3個個體，選擇最優的1個種群個體進入后代種群。重復此操作，直到新的種群大小達到原始種群大小。

1.2.4 交叉和變異算子

交叉的目的是將父代種群個體中的優秀基因遺傳給子代保證遺傳算法的搜索能力和穩定性，變異的目的是防止遺傳算法過早收斂并且可以讓遺傳算法在局部的隨機搜索能力更強。在CS-GA中使用單點操作方法對種群個體進行交叉和變異。GA交叉率和變異率往往根據實際情況和經驗取值，但問題是交叉率和變異率取值過大，會導致個體適應度波動較大。交叉率和變異率取值小，會導致搜索緩慢早熟收斂。因此，采用自適應的思想對交叉算子與變異算子進行改進：

(5)

(6)

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

1.2.5 算法終止條件

當CS-GA達到最大迭代次數，或者當前種群適應度值達到0.999 9時，算法終止。

2 實驗及結果分析

2.1 實驗數據

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

2.2 實驗設置

實驗的編程環境為Ipython Notebook，硬件環境為Intel Core i5-7500@3.40 GHz，RAM 8 GB，Windows 10 64位操作系統， CS-GA算法的參數設置如表1所示。

表1 CS-GA算法的參數設置

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

圖2 CS-GA算法進化曲線

2.3 實驗結果及性能對比

2.3.1 CS-GA、GA、Gini-GA選擇結果對比

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

表2 3種算法20次特征選擇結果平均性能參數

可以看出，CS-GA作為一種相關性過濾算法，在特征選擇上速度較快，比其他兩種算法具有更短的建模時間?？偟膩碚f，CS-GA作為混合特征選擇算法在特征維度的約減能力上好于GA和Gini-GA，在檢測率和誤報率上也比GA和Gini-GA要好。傳統自適應GA作為特征選擇算法，選擇出來的特征子集在檢測率、誤報率、維度等性能指標上無明顯優勢。

2.3.2 特征選擇結果及性能對比

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

表3 特征選擇結果

如圖3、圖4所示，All-SVM表示選擇全部41個特征，通過SVM分類器測量其檢測率和誤報率。結果顯示，入侵檢測采用全部特征時其檢測率和誤報率效果最差。GA雖然可以對特征進行降維，但是在檢測率和誤報率上與All-SVM使用全部特征子集性能相當。Gini-GA中基尼系數對于入侵檢測問題中處理連續型數值特征的約減能力上不如CS-GA，CS-GA在特征約減能力上效果最好。CS-GA選擇出來的特征子集在6組不同的測試集上的檢測率和誤報率上也明顯優于其他對比算法。

圖3 6組測試樣本的檢測率

圖4 6組測試樣本的誤報率

圖5比較了4種特征子集在SVM分類器上的測試時間。結果顯示，采用全部特征的All-SVM需要更長的測試時間，而CS-GA將入侵檢測數據集中41個特征維度約減到5維，極大地降低分類器的訓練難度。CS-GA選擇出來的特征子集相對于其他算法在基于SVM算法上測試時間最短，在一定程度上解決入侵檢測實時性問題。

圖5 6組測試樣本的測試時間/s

3 結 語

本文通過卡方算法對入侵檢測數據集中冗余特征進行過濾，采用LightGBM分類器結合自適應遺傳算法構成混合特征選擇方法，搜索分類效果好的特征子集。實驗結果表明：CS-GA能夠縮減SVM分類算法的測試時間，有效刪除冗余特征和相關度低的特征，提高入侵檢測的檢測性能，降低誤報率。后續會考慮將CS-GA和其他過濾算法結合，處理不同類型數據特征，進一步提高算法的特征約減能力。