改進(jìn)麻雀搜索算法的入侵檢測特征選擇

劉 濤，蒙學(xué)強(qiáng)

(1.西安科技大學(xué) 通信與信息工程學(xué)院，陜西 西安 710600；2.西安科技大學(xué) 西安市網(wǎng)絡(luò)融合通信重點實驗室，陜西 西安 710600)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，網(wǎng)絡(luò)威脅也在逐步增加，為了提高網(wǎng)絡(luò)的安全性，入侵檢測技術(shù)一直是網(wǎng)絡(luò)安全研究的熱點。由于入侵檢測數(shù)據(jù)集特征數(shù)量大，存在冗余特征，其不僅降低了分類的準(zhǔn)確率并且增加了計算時間[1]。近年來，受自然現(xiàn)象啟發(fā)的群智能優(yōu)化方法為解決特征選擇問題提供了一種新方法。網(wǎng)絡(luò)入侵檢測的特征選擇問題可以轉(zhuǎn)化為優(yōu)化問題，利用優(yōu)化算法獲取特征子集進(jìn)行入侵檢測[2]。Alzub等[1]提出了二進(jìn)制灰狼優(yōu)化結(jié)合SVM的特征選擇算法。Singh等[3]使用混沌花朵授粉算法進(jìn)行相關(guān)性特征選擇。Alsaleh等[4]將樽海鞘群算法結(jié)合XGBoost和Na?ve Bayes進(jìn)行特征選擇。Liu等[5]使用并行計算的改進(jìn)群集蜘蛛優(yōu)化算法進(jìn)行特征選擇。

Xue等[6]提出了麻雀搜索算法(SSA)，該算法具有求解精度高、收斂速度快的優(yōu)勢，但也存在容易陷入局部最優(yōu)的缺陷，對此眾多學(xué)者提出了不同的改進(jìn)方法。呂鑫等[7]利用改進(jìn)Tent映射和高斯變異提升算法的全局尋優(yōu)性能。Yang等[8]利用佳點集初始化種群，提出一種博弈掠奪機(jī)制和自毀機(jī)制的更新方式，充分利用種群最優(yōu)個體的信息。Yuan等[9]使用重心反向?qū)W習(xí)初始化種群，加入可變學(xué)習(xí)系數(shù)和突變因子進(jìn)行位置更新，增強(qiáng)了全局搜索能力。Ma等[10]提出了統(tǒng)一多樣化定向策略初始化種群，使用危險轉(zhuǎn)移策略和動態(tài)進(jìn)化策略增強(qiáng)全局探索能力。

以上文獻(xiàn)從多個方面對SSA進(jìn)行了改進(jìn)，但針對不同優(yōu)化問題存在收斂精度低，收斂速度慢等不足，本文提出一種混合策略改進(jìn)的麻雀搜索算法(HISSA)，將其應(yīng)用于入侵檢測的特征選擇問題中，在CIC-IDS2017數(shù)據(jù)集上進(jìn)行實驗，對原有的77個特征進(jìn)行提取，平均保留了7.6個特征，并且準(zhǔn)確率平均達(dá)到了99.5%，驗證了改進(jìn)算法更好的尋優(yōu)能力。

1 原始麻雀搜索算法

麻雀搜索算法是根據(jù)麻雀群居行為提出的智能優(yōu)化算法，通過模擬麻雀捕食和被捕食行為建立模型。根據(jù)分工的不同將麻雀分成發(fā)現(xiàn)者、跟隨者和警戒者。

假設(shè)由N只麻雀組成的空間為X=[x(1，i)，x(2，i)，…，x(N，i)]T， 其中，i=1，2，…，d，d為維度。

發(fā)現(xiàn)者位置更新描述如式(1)所示

(1)

跟隨者位置更新描述如式(2)所示

(2)

警戒者位置更新描述如式(3)所示

(3)

2 改進(jìn)麻雀搜索算法

2.1 改進(jìn)的Circle映射初始化種群

在初始化階段，麻雀個體隨機(jī)生成，種群分布不均勻，容易在某一區(qū)域出現(xiàn)聚集現(xiàn)象，導(dǎo)致彼此間麻雀個體差異較小，加入混沌映射初始化可以使該問題得到改善。常見的映射方法包括Logistic混沌映射、Tent混沌映射、Sine映射、Circle映射等。由于Logistic映射在(0，1)區(qū)間內(nèi)呈切比雪夫分布[11]，在(0.9，1)區(qū)間內(nèi)分布密集，在整個空間內(nèi)分布不均勻。Tent映射雖然在(0，1)區(qū)間內(nèi)分布均勻，但是存在小周期和不穩(wěn)定周期點[12]。Sine映射在(0，1)區(qū)間內(nèi)集中分布在(0，0.1)和(0.9，1)內(nèi)，其處于混沌狀態(tài)的參數(shù)空間較窄[13]。Circle映射相對而言更加穩(wěn)定，且均勻性也較好。

傳統(tǒng)的Circle映射主要集中分布在(0.2，0.5)內(nèi)，如圖所示，在此對Circle映射稍作改進(jìn)，使其分布更為均勻。

原Circle映射表達(dá)式如式(4)所示

(4)

改進(jìn)后的Circle映射如式(5)所示

(5)

式中：n為解的維度，取n=2000，原始Circle映射和改進(jìn)Circle映射解維度分布圖如圖1所示。

由圖1可知，改進(jìn)后的Circle映射分布更為均勻，使用改進(jìn)Circle映射初始化麻雀種群，能夠使種群分布更為均勻，增加種群分布差異性的同時減少了陷入局部最優(yōu)的概率。

2.2 發(fā)現(xiàn)者位置更新的改進(jìn)

原始麻雀搜索算法中，隨著迭代次數(shù)的增加，搜索范圍不斷減小，發(fā)現(xiàn)者在每一維上都在變小，在搜索初期容易陷入局部最優(yōu)。

本文結(jié)合禿鷹搜索算法中搜索階段鷹的移動模型[14]，采用螺旋飛行的方式對發(fā)現(xiàn)者位置進(jìn)行更新。如式(6)所示

(6)

改進(jìn)后的公式如式(7)所示

(7)

其中，γ為動態(tài)自適應(yīng)權(quán)重，其隨著迭代次數(shù)的增加不斷增加。通過不斷迭代對發(fā)現(xiàn)者位置更新算子進(jìn)行調(diào)節(jié)，在搜索前期γ值較小，位置更新較慢，便于全局搜索；在后期γ值變大，算子下降速率變快，搜索精度得到提升。并且加入螺旋移動方式，增加發(fā)現(xiàn)者在每次位置更新時的搜索路徑，提升算法的全局尋優(yōu)能力。

2.3 單純形法

單純形法是一種直接、快速的求解最優(yōu)值的方法，具有收斂速度快，適用范圍廣的優(yōu)點。基本思想是在一個搜索域內(nèi)尋找一個點，判斷是否為最優(yōu)解，如果不是則由當(dāng)前解生成一個新解，再進(jìn)行判斷，不斷迭代直到找到最優(yōu)值。

用單純形法對麻雀位置進(jìn)行優(yōu)化，能夠進(jìn)一步提升麻雀算法的搜索能力[15]。首先按適應(yīng)度值對麻雀種群進(jìn)行排序，選擇最優(yōu)位置和次優(yōu)位置Xbest和Xnext，計算其中點位置Xmedium。同時記錄對應(yīng)位置的適應(yīng)度值fbest和fnext，其中Xmedium=((Xbest+Xnext))/2。

其次記錄適應(yīng)度最差的n個麻雀的位置Xworst，進(jìn)行反射操作，讓其向相反方向移動，增大搜索范圍。反射點的位置為Xreflex，適應(yīng)度為freflex

Xreflex=Xmedium+α·(Xbest-Xworst)

(8)

其中，α為反射系數(shù)，這里設(shè)為1。

對反射點的適應(yīng)度值進(jìn)行判斷，分為以下3種情況：

(1)如果freflex

Xexpand=Xmedium+γ·(Xreflex-Xmedium)

(9)

其中，γ為擴(kuò)張系數(shù)，這里設(shè)為2。

如果fexpand

(2)如果freflex>fworst， 說明反射方向不正確，對該位置麻雀進(jìn)行外收縮，讓較差位置的麻雀更接近最優(yōu)位置，增強(qiáng)局部探索能力。記外收縮后麻雀的位置為Xec，適應(yīng)度為fec

Xec=Xmedium+β·(Xworst-Xmedium)

(10)

其中，β為收縮系數(shù)，這里設(shè)為0.5。

如果fec

(3)如果fbest

Xic=Xmedium+β·(Xreflex-Xmedium)

(11)

其中，β為收縮系數(shù)，這里設(shè)為0.5。

如果fic

本文通過單純形法對適應(yīng)度較差的麻雀個體進(jìn)行優(yōu)化，避免其陷入停滯狀態(tài)，提升了搜索性能，增強(qiáng)算法的全局尋優(yōu)能力。

2.4 小孔成像反向?qū)W習(xí)策略

為了解決多數(shù)群智能優(yōu)化算法容易陷入局部最優(yōu)的問題，有學(xué)者提出了反向?qū)W習(xí)的方法。對于當(dāng)前解取其反向解，在已有解決方案的同時，又考慮到了相反的解決方案。本文選用一種小孔成像的反向?qū)W習(xí)策略[16]，求得當(dāng)前最優(yōu)解的反向解，增大解空間的范圍，增強(qiáng)算法逃離局部最優(yōu)的能力。

小孔成像反向?qū)W習(xí)的原理如圖2所示。

圖2 小孔成像原理

由小孔成像的原理可得

(12)

(13)

通過調(diào)整小孔屏與接收屏之間的距離，改變n的大小，可以得到位置更優(yōu)的解，逃離局部最優(yōu)。

通過小孔成像反向?qū)W習(xí)策略，對每次迭代后產(chǎn)生的最優(yōu)個體麻雀位置進(jìn)行更新，不僅擴(kuò)大了最優(yōu)個體的搜索區(qū)域，同時也減小了陷入局部最優(yōu)的問題。

2.5 HISSA算法流程

步驟1 利用改進(jìn)的Circle映射初始化種群，設(shè)置種群數(shù)量N，發(fā)現(xiàn)者比例PD，警戒者比例SD，最大迭代次數(shù)itermax，預(yù)警值ST，搜索上界ub，搜索下界lb，維度d。

步驟2 計算麻雀個體適應(yīng)度，并進(jìn)行排序，記錄最優(yōu)位置、次優(yōu)位置和最差位置的麻雀分Xbest、Xnext和Xworst，其適應(yīng)度分別為fbest、fnext和fworst。

步驟3 根據(jù)式(7)更新發(fā)現(xiàn)者位置。

步驟4 根據(jù)式(2)更新跟隨者位置。

步驟5 根據(jù)式(3)更新警戒者位置。

步驟6 進(jìn)行單純形法操作。首先記錄最優(yōu)和次優(yōu)的中點位置Xmedium及其適應(yīng)度值，選擇適應(yīng)度較差的n個麻雀，按照式(8)進(jìn)行反射操作，記錄適應(yīng)度freflex。

步驟7 比較fbest、fnext、fworst和freflex的大小，如果freflexfworst，按照式(10)進(jìn)行外收縮操作；如果fbest

步驟9 計算更新后的適應(yīng)度值，如果優(yōu)于當(dāng)前位置，則進(jìn)行替換。

步驟10 判斷是否達(dá)到最大迭代循環(huán)次數(shù)，如果是則進(jìn)行下一步，否則跳轉(zhuǎn)到步驟2。

步驟11 算法結(jié)束，輸出并記錄最優(yōu)結(jié)果。

2.6 時間復(fù)雜度分析

時間復(fù)雜度是衡量算法性能和計算成本的重要指標(biāo)之一。假設(shè)空間維度為d，求解適應(yīng)度函數(shù)所需時間為f(d)， 則SSA的時間復(fù)雜度為O(f(d)×d)。 HISSA的時間復(fù)雜度分析如下：

(1)假設(shè)麻雀種群數(shù)量為N，初始化參數(shù)的時間為t1，在每個維度中生成混沌值的時間為t2，時間復(fù)雜度為：O1=O(t1+N×(f(d)+t2×d))。

(2)發(fā)現(xiàn)者比例為PD，每個維度位置更新所需時間為t3，改進(jìn)發(fā)現(xiàn)者位置更新方式的時間復(fù)雜度為：O2=O(PD×N×t3×d)。

(3)跟隨者和警戒者更新方式未做更改，因此時間復(fù)雜度與SSA相同，分別為O3和O4。

(4)假設(shè)每個維度的反射、擴(kuò)張、外收縮和內(nèi)收縮所需的時間是t4、t5、t6、t7，單純形優(yōu)化后的時間復(fù)雜度為：O5=O(N×(t4+t5+t6+t7)×d)。

(5)假設(shè)為每個維度生成反向解所需的時間為t8，小孔成像反向?qū)W習(xí)策略優(yōu)化后的時間復(fù)雜度為：O6=O(N×t8×d)。

設(shè)最大迭代次數(shù)為itermax，則HISSA的時間復(fù)雜度為：O′=O1+itermax×(O2+O3+O4+O5+O6)=O(f(d)×d)。 因此，HISSA和SSA具有相同的時間復(fù)雜度。

3 實驗與結(jié)果分析

3.1 算法測試

3.1.1 參數(shù)設(shè)置說明

為了驗證HISSA的性能，本文選用基本灰狼優(yōu)化算法(GWO)、鯨魚優(yōu)化算法(WOA)、正余弦優(yōu)化算法(SCA)、粒子群算法(PSO)和麻雀搜索算法(SSA)進(jìn)行對比實驗。將種群規(guī)模N和最大迭代次數(shù)itermax作為每種算法共同的參數(shù)。設(shè)N=30，itermax=500，且每種算法均獨立運行30次。每種算法各自的參數(shù)見表1。

3.1.2 基準(zhǔn)測試函數(shù)介紹

為了驗證改進(jìn)算法的性能，本文選取6個基準(zhǔn)測試函數(shù)進(jìn)行實驗，見表2，其中f1～f4為單峰函數(shù)，f5～f6為多峰函數(shù)。

表2 基準(zhǔn)測試函數(shù)

3.1.3 算法性能結(jié)果對比分析

表3為6種算法在6個基準(zhǔn)測試函數(shù)上30維的尋優(yōu)實驗結(jié)果。

表3 基準(zhǔn)測試函數(shù)優(yōu)化結(jié)果對比

由表3可知，對于單峰函數(shù)f1、f2、f3、f4及多峰函數(shù)f5，HISSA可以達(dá)到理論最優(yōu)解0。對于f1、f2、f3、f4的求解，SSA雖然能夠達(dá)到理論最優(yōu)解，但并不穩(wěn)定，HISSA在保持原算法性能的基礎(chǔ)上極大提高了穩(wěn)定性；對于f5，SSA達(dá)到了理論最優(yōu)解，HISSA僅在收斂速度上有所提升；對于f6，WOA、SSA和HISSA均能夠達(dá)到理論最優(yōu)解，但WOA穩(wěn)定性遜于后兩者。通過分析可知，HISSA在收斂速度，收斂精度和穩(wěn)定性等方面均高于其它算法，因此本文提出的HISSA具有明顯優(yōu)勢。

3.1.4 收斂曲線分析

各算法獨立運行30次的收斂曲線如圖3所示。

圖3 收斂曲線

由圖3可知，對于多數(shù)函數(shù)的求解，SSA的求解精度優(yōu)于其它算法。HISSA在其基礎(chǔ)上大幅提高了收斂速度，且更容易跳出局部最優(yōu)范圍。

3.1.5 Wilcoxon秩和檢驗

本文采用Wilcoxon秩和檢驗對每一次計算結(jié)果進(jìn)行獨立分析，在P=5%的顯著性水平下對比與其它算法的差異。當(dāng)P值小于5%時，拒絕假設(shè)，表明兩種算法之間存在明顯差異；當(dāng)P值大于5%時，接收假設(shè)，表明兩種算法尋優(yōu)能力較為相似。表4為在6個基準(zhǔn)測試函數(shù)下，HISSA與其它算法之間的優(yōu)化結(jié)果對比，如果兩種算法同時得到最優(yōu)值，無法進(jìn)行比較，則使用NaN表示不適用。C表示對比結(jié)果，“+”表示HISSA優(yōu)于其它算法，“=”表示HISSA等同于其它算法，“-”表示HISSA劣于其它算法。

表4 基準(zhǔn)測試函數(shù)優(yōu)化結(jié)果對比

3.2 入侵檢測特征選擇問題

3.2.1 數(shù)據(jù)預(yù)處理

本實驗選用CIC-IDS2017數(shù)據(jù)集，原始文件包含5天的數(shù)據(jù)流量，分為8個文件。首先將其合并為1個文件，文件共計2 830 743條流量數(shù)據(jù)。除去時間戳，端口信息等共包含77個特征，及1個標(biāo)簽列。標(biāo)簽包含正常類型和14種攻擊類別，主要分布情況見表5。

表5 數(shù)據(jù)集分布

(1)由于數(shù)據(jù)集中存在部分NaN值和Infinity值，在訓(xùn)練時會報錯，但其所占比例極小，因此直接刪除進(jìn)行數(shù)據(jù)清洗，處理后的數(shù)據(jù)大小為2 827 876。

(2)為了方便模型分類，將所有的Dos攻擊、Web攻擊和暴力攻擊歸為一類，按0～9進(jìn)行編碼。

(3)由于不同特征之間數(shù)據(jù)差值較大，容易造成特征空間內(nèi)部分樣本點受較大特征值的影響，將特征數(shù)值按式(14)歸一化到[0，1]區(qū)間內(nèi)

(14)

其中，x′i表示歸一化后的值，xi表示初始值，xmin表示該特征的最小值，xmax表示該特征的最大值。

(4)由于數(shù)據(jù)集存在不平衡現(xiàn)象，正常數(shù)據(jù)達(dá)到了200多萬條，而最少的攻擊類型僅為11條。直接訓(xùn)練時容易過度擬合多數(shù)類樣本忽略少數(shù)類樣本的特征，從而導(dǎo)致分類器性能不佳。因此本文使用隨機(jī)欠采樣抽取多數(shù)類樣本，使用SMOTE過采樣生成少數(shù)類樣本，最終抽取50 000條數(shù)據(jù)進(jìn)行實驗。

3.2.2 特征選取標(biāo)準(zhǔn)

在改進(jìn)麻雀算法的特征選擇方法中，麻雀種群初始化位置對應(yīng)一個隨機(jī)的特征，麻雀個體在特征空間內(nèi)隨機(jī)搜索，對獲得的特征子集進(jìn)行評估。如果原始位置的值大于0.5，則選擇該特征，表示為“1”；否則放棄該特征，表示為“0”。如果所有值都小于0.5，則選擇值最大的麻雀位置。將特征數(shù)量與F1分?jǐn)?shù)相結(jié)合做為適應(yīng)度函數(shù)，在保證F1分?jǐn)?shù)高的情況下，特征數(shù)量盡量少。最后將選擇的特征子集使用CatBoost進(jìn)行分類，得到最終的分類結(jié)果。

3.2.3 CatBoost算法

CatBoost算法是繼XGBoost、LightGBM之后第三個基于GBDT改進(jìn)的算法，其訓(xùn)練參數(shù)少且準(zhǔn)確率較高，并且能夠高效合理地處理類別型特征，充分利用特征之間的聯(lián)系，并且使用對稱樹結(jié)構(gòu)，有效的減少了過擬合現(xiàn)象，具有較好的魯棒性。

參數(shù)設(shè)置見表6。

表6 CatBoost參數(shù)

3.2.4 實驗結(jié)果分析

SSA特征選擇結(jié)果和HISSA特征選擇結(jié)果見表7和表8，圖4為兩種算法選擇的特征對比。

表7 SSA特征選擇結(jié)果

表8 HISSA特征選擇結(jié)果

圖4 兩種算法特征選擇對比

從表7和表8可知，SSA算法平均保留了13.3個特征，平均準(zhǔn)確率為97.97%，平均F1分?jǐn)?shù)為97.14%；HISSA算法平均保留了7.6個特征，準(zhǔn)確率達(dá)到了99.5%，F(xiàn)1分?jǐn)?shù)達(dá)到了98.48%，與原算法相比減少了5.7個特征，提升了1.53%的準(zhǔn)確率與1.34%的F1分?jǐn)?shù)。綜合上述指標(biāo)來看，改進(jìn)算法在模型中能夠取得更優(yōu)的目標(biāo)函數(shù)值，加快了分類效率，在減少特征維度的同時進(jìn)一步提高了準(zhǔn)確率。

4 結(jié)束語

本文針對入侵檢測中數(shù)據(jù)特征維度高的問題，提出了一種改進(jìn)麻雀算法的特征選擇方法。利用改進(jìn)的Circle映射初始化種群；在位置更新機(jī)制中引入螺旋探索更新方式；最后使用單純形法及小孔成像法分別更新較差和最優(yōu)麻雀位置，有效改善了原算法收斂速度慢、精度低、容易陷入局部最優(yōu)等問題。通過與其它5種算法的對比測試，表明改進(jìn)算法的收斂性能更佳，魯棒性更強(qiáng)。在CIC-IDS2017數(shù)據(jù)集上進(jìn)行特征選擇實驗，結(jié)果表明該算法極大減少了特征維度，并且達(dá)到了極高的準(zhǔn)確率，驗證了算法的可行性，對特征選擇問題有著重要的參考價值。