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

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

0 引 言

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

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

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

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

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

1.1 基于CS過濾算法

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

(1)

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

(2)

(3)

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

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

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

1.2.1 種群個體編碼

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

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

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

(4)

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

1.2.3 選擇算子

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

1.2.4 交叉和變異算子

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

(5)

(6)

式中：Pc1、Pc2是交叉率；Pm1、Pm2是變異率；fmax和favg為每代群體中最大適應(yīng)度值和平均適應(yīng)度值；f′為2個交叉?zhèn)€體中較大的適應(yīng)度值；f為變異個體的適應(yīng)度值。由式(5)-式(6)可知當(dāng)f和f′小于favg時，使用取值大的Pc1和Pc2提高遺傳算法的搜索能力。當(dāng)遺傳算法到后期和f大于favg時通過自適應(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時，算法終止。

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

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

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

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ù)特征維度個數(shù)均取41。如圖2所示，最大進(jìn)化代數(shù)選擇80時，種群評價適應(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é)果及性能對比

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語

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