改進(jìn)粒子群聯(lián)合禁忌搜索的特征選擇算法

張震，魏鵬，李玉峰，蘭巨龍，徐萍，陳博

（1. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州450002；2. 中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，河南 鄭州 450002）

1 引言

入侵檢測技術(shù)利用數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等方法對審計(jì)日志、安全日志或者網(wǎng)絡(luò)上獲取的信息進(jìn)行分析處理，實(shí)現(xiàn)對入侵行為的檢測[1]。瞬息萬變的海量網(wǎng)絡(luò)數(shù)據(jù)使入侵檢測系統(tǒng)（IDS，intrusion detection system）面臨巨大挑戰(zhàn)，如檢測速度低、檢測效果差、計(jì)算負(fù)荷大等。其中，檢測速度是入侵檢測系統(tǒng)實(shí)時(shí)性要求的重要指標(biāo)，如何在保證檢測準(zhǔn)確率的前提下提升入侵檢測速度，成為當(dāng)前入侵檢測的研究熱點(diǎn)。

特征選擇是入侵檢測中數(shù)據(jù)預(yù)處理的關(guān)鍵環(huán)節(jié)，能夠在入侵檢測數(shù)據(jù)集中篩選出對分類器的分類性能影響最重要的一組特征[2]。良好的特征選擇算法能夠降低網(wǎng)絡(luò)數(shù)據(jù)的維度，減輕入侵檢測系統(tǒng)的計(jì)算負(fù)荷，提高入侵檢測系統(tǒng)的檢測速度。本文針對原始數(shù)據(jù)集數(shù)據(jù)維度高的問題，提出了一種改進(jìn)粒子群聯(lián)合禁忌搜索（IPSO-TS, improved particle swarm optimization taboo search）的特征選擇方法，通過降低入侵?jǐn)?shù)據(jù)的維度，有效地提升了入侵檢測效率。

2 研究現(xiàn)狀

特征選擇算法根據(jù)是否獨(dú)立于分類算法可分為Filter方法和Wrapper方法。Filter方法獨(dú)立于分類算法，首先衡量每個(gè)特征的重要性，然后根據(jù)重要性對所有特征進(jìn)行排序，最后將前N個(gè)重要的特征作為特征子集。這種方法的優(yōu)點(diǎn)是計(jì)算量較低，可以有效去除噪聲特征，缺點(diǎn)是忽略了選擇出的特征子集整體對分類效果的影響程度[3]。Wrapper方法通過分類算法的準(zhǔn)確率評估特征子集的優(yōu)劣，優(yōu)點(diǎn)是考慮了整個(gè)特征子集對分類效果的影響，分類準(zhǔn)確率較高，缺點(diǎn)是計(jì)算量較大[4]。從分類性能方面考慮，Wrapper方法比Filter方法更適合于網(wǎng)絡(luò)數(shù)據(jù)的特征選擇，故本文采用Wrapper方法。

搜索機(jī)制是Wrapper方法的核心，用來生成候選特征子集[5]?？紤]到對龐大而復(fù)雜的搜索空間中的所有可能特征子集進(jìn)行窮舉搜索很難實(shí)現(xiàn)，粒子群算法（PSO, particle swarm optimization）為代表的演化計(jì)算[6]具有自然進(jìn)化的屬性，在特征選擇中有利于優(yōu)化搜索機(jī)制，提高搜索效率，故常被用來尋優(yōu)特征子集。近年來，有許多結(jié)合改進(jìn)粒子群進(jìn)行特征選擇的方法，本文從優(yōu)化粒子群算法參數(shù)、優(yōu)化粒子群表示方法、優(yōu)化離散型或連續(xù)型特征、優(yōu)化評價(jià)指標(biāo)等方面引用相關(guān)參考文獻(xiàn)進(jìn)行分析。董躍華等[7]提出一種自適應(yīng)粒子群聯(lián)合禁忌搜索的特征選擇算法，在PSO搜索過程中，對每一代全局優(yōu)化粒子進(jìn)行禁忌搜索，有利于保持粒子活力，增強(qiáng)搜索優(yōu)化解的能力，但該方法中粒子群缺乏多樣性且對每一代全局優(yōu)化粒子進(jìn)行禁忌搜索會極大增加算法的時(shí)間復(fù)雜度。Tran等[8]提出了基于勢粒子群優(yōu)化的特征選擇方法，設(shè)計(jì)了一種新的粒子群表示方法，通過選取切點(diǎn)離散化原始特征，然后篩選出性能較好的優(yōu)化特征子集，該方法僅適用于離散型特征，無法篩選出連續(xù)型特征中的優(yōu)化特征。Nguyen等[9]提出了一種遺傳算子優(yōu)化 PSO的連續(xù)型特征選擇算法，利用交叉、變異等遺傳算子提高PSO的搜索能力，但該方法受群落初始分布影響較大，且遺傳算子中交叉、變異概率固定不變，不利于搜尋到全局優(yōu)化解。翟俊海等[10]提出了一種將粗糙集相對分類信息熵和粒子群算法相結(jié)合的特征選擇方法，將分類信息熵作為適應(yīng)度函數(shù)，結(jié)合改進(jìn)粒子群算法得到優(yōu)化的特征子集，但該方法的適應(yīng)度評價(jià)指標(biāo)結(jié)構(gòu)較為單一，不利于選出分類性能較好的特征子集。

綜上所述，目前大多數(shù)特征選擇算法都有各自的局限性，例如，文獻(xiàn)[8]中方法無法篩選出連續(xù)型特征中的優(yōu)化特征；文獻(xiàn)[9]中算法尋優(yōu)效果受群落初始分布影響較大；文獻(xiàn)[10]中方法的評價(jià)指標(biāo)結(jié)構(gòu)較為單一。本文以特征維度和分類準(zhǔn)確率的優(yōu)化配置為目標(biāo)設(shè)計(jì)出評價(jià)標(biāo)準(zhǔn)，基于該標(biāo)準(zhǔn)提出了一種遺傳算子改進(jìn)粒子群聯(lián)合禁忌搜索的特征選擇（IPSO-TS）算法，通過遺傳算子優(yōu)化粒子群算法尋優(yōu)特征子集，以期望生成更好的初始最優(yōu)解。在此基礎(chǔ)上，聯(lián)合禁忌搜索（TS, taboo search）算法找到全局優(yōu)化解。其中，粒子群算法具有快速收斂的特點(diǎn)；遺傳算法增加了粒子群落多樣性；TS算法有利于跳過局部最優(yōu)值，實(shí)現(xiàn)全局優(yōu)化搜索，提高特征子集搜索效率。

3 IPSO-TS特征選擇算法

IPSO-TS特征選擇算法的流程如圖1所示，其中，搜索模塊應(yīng)用本文提出的改進(jìn)粒子群聯(lián)合 TS算法，實(shí)現(xiàn)搜尋候選特征子集的功能；評價(jià)模塊應(yīng)用本文提出的適應(yīng)度函數(shù)，完成對候選特征子集的性能評價(jià)；判決模塊根據(jù)判決條件選擇數(shù)據(jù)集的最優(yōu)特征子集，結(jié)束循環(huán)，并將該子集作為結(jié)果輸出。

圖1 IPSO-TS特征選擇算法流程

針對圖1中的評價(jià)模塊，本文提出了一種新的適應(yīng)度評價(jià)函數(shù)，如式(1)所示。

其中，fsnum表示特征選擇后的特征數(shù)量，afsnum表示總特征數(shù)量，accuracy表示分類準(zhǔn)確率，alpha和(1-alpha)都是權(quán)重參數(shù)。本文的目標(biāo)是在保障分類準(zhǔn)確率的條件下，降低特征維數(shù)，因此，選擇了較高的accuracy權(quán)重參數(shù)，即accuracy=0.98，相應(yīng)的alpha=0.02。

式(1)中適應(yīng)度函數(shù)與傳統(tǒng)特征選擇方法相比，引入了分類準(zhǔn)確率accuracy和特征選擇后的特征數(shù)量fsnum作為參數(shù)，能夠更準(zhǔn)確對特征子集性能進(jìn)行評估。其中，分類準(zhǔn)確率越高，特征維數(shù)減少的比例越大，則適應(yīng)度值越大，表明提取的特征子集性能越好。

本文通過K最近鄰(KNN，k-nearest neighbor)分類算法得到分類準(zhǔn)確率accuracy，如式(2)所示。

其中，TP和TN表示入侵檢測中正確分類的正常數(shù)據(jù)和異常數(shù)據(jù)，F(xiàn)P和FN表示入侵檢測中錯(cuò)誤分類的正常數(shù)據(jù)和異常數(shù)據(jù)。

3.1 改進(jìn)的PSO算法

3.1.1 PSO算法

PSO算法是根據(jù)鳥群捕食行為設(shè)計(jì)的一種群智能算法，基本思想是通過粒子群中粒子之間的協(xié)作和信息共享來搜尋最優(yōu)解。PSO算法可以分為二進(jìn)制PSO算法和連續(xù)PSO算法。連續(xù)PSO算法指為粒子賦值實(shí)數(shù)，二進(jìn)制PSO算法則是為粒子賦值二進(jìn)制數(shù)。由于連續(xù)PSO具有更廣闊的應(yīng)用前景，本文使用連續(xù)PSO算法進(jìn)行特征選擇，根據(jù)粒子個(gè)體極值和群體最優(yōu)解進(jìn)行尋優(yōu)，尋優(yōu)計(jì)算式如式(3)和式(4)所示。

其中，t表示迭代次數(shù)，i=1,2,…,m(m表示所有粒子個(gè)數(shù))，d=1,2,…,n(n表示粒子總維數(shù))，randi1和randi2為[0,1]之間的隨機(jī)數(shù)，表示粒子i的歷史極值在第t次迭代中第d維最優(yōu)位置，表示群體最優(yōu)粒子在第t次迭代中第d維最優(yōu)位置，c1和c2表示學(xué)習(xí)因子，表示粒子i在第t次迭代中第d維位置，表示粒子i在第t次迭代中第d維移動(dòng)速度。

劉楊等[11]研究了線性函數(shù)、凹凸函數(shù)遞減等4種PSO算法慣性權(quán)重w后發(fā)現(xiàn)，多峰函數(shù)尋優(yōu)中凸函數(shù)遞減慣性權(quán)重法收斂速度最快，效果最好。因此本文的慣性權(quán)重取值如式(5)所示。

其中，wmax和wmin分別表示慣性權(quán)重的最大值和最小值，iter表示迭代次數(shù)，maxiter表示最大迭代次數(shù)。

在PSO算法中，c1體現(xiàn)了粒子對自身的學(xué)習(xí)能力，c2體現(xiàn)了粒子對群體的學(xué)習(xí)能力[12]，c1數(shù)值遞減和c2數(shù)值遞增有利于發(fā)揮粒子初期探索和后期對群體的認(rèn)知能力。因此本文學(xué)習(xí)因子c1和c2的賦值如式(6)和式(7)所示。

其中，c3和c4是常數(shù)，且c3＞c4。

3.1.2 基于遺傳算法對粒子群的改進(jìn)

遺傳算法是一種通過模擬自然進(jìn)化過程尋找最優(yōu)解的隨機(jī)化搜索方法。遺傳算法中的遺傳算法交叉和突變對于PSO算法作用很大，可以增加粒子群落變化的多樣性，產(chǎn)生出代表新解集的種群，克服粒子群易于陷入局部最優(yōu)的問題。

為了避免粒子群過早收斂問題，本文中的粒子群算法每次迭代的時(shí)候?qū)Χ鄬αＷ舆M(jìn)行交叉操作，利用基于適應(yīng)度值的輪盤賭算法選擇出多對母本粒子，將其進(jìn)行交叉產(chǎn)生出多對下一代粒子，選擇其中優(yōu)良的下一代粒子替換群落中母本粒子和歷史極值。其中交叉操作主要是將第 1個(gè)母本粒子與第 2個(gè)母本粒子維位置互相交換，其中，L表示粒子總維數(shù)。每次迭代進(jìn)行交叉操作粒子的個(gè)數(shù)Pi如式(8)所示。其中，swarmsize表示所有粒子個(gè)數(shù)。根據(jù)粒子群的特性，遺傳算法在搜索初期時(shí)粒子群的種類更加隨機(jī)和多樣，到了搜索后期，粒子群逐漸收斂，相似度增加，故交叉操作在前期作用大于后期作用。所以隨著迭代次數(shù)增加，每次迭代的交叉操作粒子個(gè)數(shù)應(yīng)該隨之減少，且交叉概率應(yīng)該隨之降低，這樣有利于減少計(jì)算成本。交叉概率更新如式(9)所示。

其中，pcmin和pcmax分別表示最小和最大交叉概率。

雖然交叉操作初期可以很好地探索搜索空間，但在粒子群后期收斂后作用較小[13]。變異操作和交叉操作恰好相反，在搜索初期效果不明顯，但是在搜索后期有較好的搜索效果，于是引入變異操作以進(jìn)一步提高空間搜索能力，且隨著迭代次數(shù)增加變異概率隨之提高，有利于進(jìn)一步尋找到更優(yōu)粒子。變異概率更新如式(10)所示，粒子中第d維位置的選擇概率如式(11)所示。

其中，pmmin和pmmax分別表示最小和最大變異概率，gbestd表示全局最優(yōu)粒子第d維位置，θ表示選擇閾值。當(dāng)gbest第d維位置的值大于閾值θ時(shí)，若gbestd值越大，則CRd越大，否則CRd越小。當(dāng)gbest第d維位置的值小于閾值θ時(shí)，若gbestd值越小，則CRd越大，否則CRd越小。然后生成[0,1]之間的隨機(jī)數(shù)r，若r＞CRd，執(zhí)行相應(yīng)的變異操作，如式(12)所示，否則將新粒子第d維位置childd賦值為gbestd。

其中，若gbestd的值小于或等于選擇閾值θ，則將childd的值映射到[θ,1]之間的實(shí)數(shù)，否則將childd的值映射到(0,θ]之間的實(shí)數(shù)，這有利于改變特征的選擇屬性。

本文中改進(jìn)PSO算法通過不斷進(jìn)化，后期粒子群逐漸收斂，粒子群相似度大大增加，這導(dǎo)致很難搜尋到更好的優(yōu)化解。由于TS算法不僅可以接受優(yōu)解，還可以接受劣解，比PSO算法能獲得更優(yōu)解，因此本文通過引入TS算法解決了該問題。

3.2 TS算法

TS算法是一種亞啟發(fā)式隨機(jī)搜索全局尋優(yōu)算法，主要包含初始解、鄰域函數(shù)、禁忌表屬性、候選集藐視準(zhǔn)則等基本參數(shù)[14]，以局部鄰域搜索算法為基礎(chǔ)，通過設(shè)置禁忌表停止已經(jīng)進(jìn)行過的操作或變換，再利用相應(yīng)的藐視準(zhǔn)則釋放禁忌表中符合條件的元素[15]。

本文建立長度為L的禁忌表 (L表示總特征個(gè)數(shù))，設(shè)置迭代次數(shù)為，將通過改進(jìn)粒子群算法得到的初始最優(yōu)解作為TS算法的初始解。改變初始解2個(gè)隨機(jī)位置特征元素的值，保持其他特征元素的值不變，將該過程作為鄰域函數(shù)：設(shè)初始最優(yōu)解為R={Ti,i=1,2,··,L}，隨機(jī)生成 2個(gè)不同整數(shù)隨機(jī)數(shù)x和y，利用式(13)更新初始最優(yōu)解中Tx和Ty的值，得到新的候選最優(yōu)解。通過隨機(jī)生成組不同隨機(jī)數(shù)對x和y，對初始特征集進(jìn)行變換，得到組候選解當(dāng)作初始候選解集合。

其中，t表示x或y。

本文中禁忌表使用隊(duì)列結(jié)構(gòu)，每次迭代時(shí)，添加禁忌對象到隊(duì)首，隊(duì)列溢出時(shí)，刪除排在隊(duì)尾的禁忌元素。藐視準(zhǔn)則要滿足2個(gè)要求：1) 將要解禁的解必須優(yōu)于當(dāng)前解[16]；2) 為了避免陷入死循環(huán)，禁忌表隊(duì)首的元素不能被解禁。

4 IPSO-TS特征選擇方法的IDS應(yīng)用實(shí)例

IDS流程如圖2所示，其中，數(shù)據(jù)獲取模塊通過監(jiān)控目標(biāo)網(wǎng)絡(luò)或系統(tǒng)來采集數(shù)據(jù)；數(shù)據(jù)預(yù)處理模塊是對采集的數(shù)據(jù)進(jìn)行數(shù)值化、標(biāo)準(zhǔn)化、特征選擇等處理，本文IPSO-TS群算法用于選擇入侵檢測數(shù)據(jù)的特征子集；入侵檢測模塊利用訓(xùn)練數(shù)據(jù)來訓(xùn)練分類器，采用分類器對待檢測的數(shù)據(jù)集進(jìn)行分析，獲得入侵檢測的結(jié)果，通過檢測指標(biāo)評價(jià)結(jié)果，本文中的分類器由KNN算法構(gòu)建；響應(yīng)模塊是IDS對檢測結(jié)果的決策。

圖2 IDS流程

在IPSO-TS算法中，若粒子位置元素大于閾值，表示選擇該特征，否則放棄該特征。通過粒子群的移動(dòng)產(chǎn)生不同位置向量，記錄粒子搜索期間所有粒子歷史極值和群落最優(yōu)粒子，將收斂后的群落最優(yōu)粒子當(dāng)作TS算法的初始解。IPSO-TS算法的特征選擇方法基本流程如圖3所示，具體實(shí)現(xiàn)步驟如下。

步驟 1 設(shè)置相關(guān)參數(shù)。改進(jìn)粒子群最大循環(huán)次數(shù)maxiter1=50，禁忌搜索次數(shù)maxiter2=30，粒子群規(guī)模swarmsize=30，最大適應(yīng)度maxfit=0.9999，pcmin=0.7，pcmax=0.8，pmmin=0.02，pmmax=0.1。設(shè)置慣性權(quán)重w=0.7928，閾值threshold=0.7等推薦參數(shù)[4]。文中入侵檢測數(shù)據(jù)集特征賦值為在[0,1]之間的不同實(shí)數(shù)，構(gòu)成粒子位置向量，隨機(jī)初始化粒子群位置和速度，求解適應(yīng)度，初始化粒子群swarm、粒子歷史極值pbest、群體最優(yōu)解gbest及它們的適應(yīng)度fswarm、fpbest、fgbest。其中，選擇閾值threshold設(shè)置為0.7，目的是大概率篩選出30%的特征子集；

圖3 IPSO-TS算法在IDS中應(yīng)用流程

步驟 2判斷是否滿足iter＞maxiter1或fgbest＞maxfit，滿足則執(zhí)行步驟6，否則執(zhí)行步驟3。

步驟3評估粒子群體適應(yīng)度值，根據(jù)式(5)～式(7)更新慣性權(quán)重w、學(xué)習(xí)因子c1、c2，如式(9)和式(10)更新交叉、變異概率。第iter次迭代中，根據(jù) 3.1.2節(jié)對群落中粒子對執(zhí)行交叉操作、對所有pbest執(zhí)行隨機(jī)亂序操作以及對gbest執(zhí)行突變操作分別得到各自后代粒子，若后代粒子更優(yōu)，則將父母粒子替換為后代粒子。其中，對pbest執(zhí)行隨機(jī)亂序操作目的是通過隨機(jī)打亂所有粒子歷史極值位置的順序，以找到更優(yōu)的粒子個(gè)體極值，有利于避免粒子個(gè)體極值過快陷入局部最優(yōu)解。

步驟 4分別更新相應(yīng)pbest、gbest及它們的適應(yīng)度。

步驟 5更新粒子群體的速度和位置，然后執(zhí)行步驟2。

步驟 6根據(jù) 3.2節(jié)進(jìn)行禁忌搜索，將經(jīng)過上述步驟得到的群體最優(yōu)解gbest作為TS算法的初始解，利用初始解產(chǎn)生相應(yīng)的鄰域解，得到組不同解當(dāng)作初始候選集合及其適應(yīng)度。

步驟 7判斷候選解集中的解是否滿足藐視準(zhǔn)則，若滿足則執(zhí)行步驟8，否則執(zhí)行步驟9。

步驟 8將候選解中非禁忌對象對應(yīng)的最優(yōu)候選解作為當(dāng)前解，然后執(zhí)行步驟10。

步驟 9將滿足藐視準(zhǔn)則中最優(yōu)解作為當(dāng)前解，然后執(zhí)行步驟10。

步驟 10將最早進(jìn)入禁忌表的禁忌對象作為當(dāng)前解，更新禁忌表并修改禁忌對象任期。

步驟 11判斷是否滿足最大禁忌搜索次數(shù)或當(dāng)前解適應(yīng)度是否達(dá)到限定值，若滿足則執(zhí)行步驟8，否則執(zhí)行步驟12。

步驟 12輸出全局優(yōu)化解作為入侵檢測數(shù)據(jù)集全局優(yōu)化特征子集。

5 IDS實(shí)驗(yàn)結(jié)果與分析

5.1 KDD CUP 99數(shù)據(jù)預(yù)處理

本文實(shí)驗(yàn)中使用的是KDD CUP 99數(shù)據(jù)集，它是網(wǎng)絡(luò)入侵檢測領(lǐng)域的標(biāo)準(zhǔn)數(shù)據(jù)集[17]，選取其提供的10%訓(xùn)練子集和測試子集（corrected）進(jìn)行實(shí)驗(yàn)，其中，訓(xùn)練子集包含 49萬條網(wǎng)絡(luò)連接記錄，測試子集包含 31萬條網(wǎng)絡(luò)連接記錄。每個(gè)網(wǎng)絡(luò)連接被標(biāo)記為正常類型和異常類型，異常類型被分為DoS（拒絕服務(wù)攻擊）、Probe（掃描與探測）、R2L（未經(jīng)授權(quán)的遠(yuǎn)程訪問）、U2R（對本地超級用戶的非法訪問）等4類，共有39種異常類型。本文實(shí)驗(yàn)中分別針對4類異常類型數(shù)據(jù)和匯總數(shù)據(jù)，進(jìn)行入侵攻擊檢測，樣本數(shù)據(jù)集如表1所示。

數(shù)據(jù)集中每一條記錄代表一條完整的會話，每條連接記錄由4類特征集組成：基本特征集、內(nèi)容特征集、基于時(shí)間特征集和基于主機(jī)特征集，共有41個(gè)特征，其中包含3個(gè)字符特征和38個(gè)數(shù)值特征，如表2所示。特征選擇前需要對數(shù)據(jù)進(jìn)行預(yù)處理，入侵檢測中數(shù)據(jù)預(yù)處理主要分為字符特征數(shù)值化和數(shù)據(jù)歸一化過程。字符特征數(shù)值化是指將符號特征映射到有序數(shù)字，例如protocol_type類型映射為tcp = 1，協(xié)議類型映射為udp = 2，協(xié)議類型映射為icmp = 3。

表1 KDD CUP 99樣本數(shù)據(jù)集組成

表2 KDD CUP 99連接記錄的特征集

以同樣的方式，將service、flag和數(shù)據(jù)集中的類別特征映射到有序數(shù)字。對經(jīng)過字符特征數(shù)值化后的數(shù)據(jù)進(jìn)行歸一化處理，使特征數(shù)值處于相同數(shù)量級，目的是消除因特征數(shù)值范圍不同造成的影響。本文通過式(14)進(jìn)行數(shù)據(jù)歸一化處理。

其中，在入侵檢測數(shù)據(jù)集的同一維數(shù)據(jù)列中，Yoriginal表示該列原始數(shù)值，Ymin表示數(shù)據(jù)列中最小值，Ymax表示數(shù)據(jù)列中最大值。

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

本文實(shí)驗(yàn)數(shù)據(jù)集主要分為檢測樣本數(shù)據(jù)集和特征選擇數(shù)據(jù)集。入侵檢測樣本數(shù)據(jù)集采用表1中的訓(xùn)練和測試數(shù)據(jù)集。為了縮短尋優(yōu)特征子集的時(shí)間，從表1的DoS、Probe、R2L和U2R的訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集中分別隨機(jī)抽取10%、20%、20%和 100%的數(shù)據(jù)作為各自特征選擇數(shù)據(jù)集中的訓(xùn)練和測試數(shù)據(jù)，并將上述特征選擇數(shù)據(jù)集合并作為匯總數(shù)據(jù)的特征選擇數(shù)據(jù)集。

本文實(shí)驗(yàn)的計(jì)算機(jī)操作系統(tǒng)為Windows 10，處理器為Intel(R) Core(TM) i5-3230M 2.60 GHz，內(nèi)存為4 GB，測試環(huán)境為Matlab 2014b。本文所提IPSO-TS算法從特征選擇時(shí)間和特征選擇維數(shù)，檢測時(shí)間和分類準(zhǔn)確率，漏報(bào)率和誤報(bào)率這6個(gè)方面，對比了PSO-TS算法[7]、PSO算法和CMPSO（co-evolutionary particle swarm optimization）算法[9]，得到如下實(shí)驗(yàn)結(jié)果。

在特征選擇數(shù)據(jù)集上比較4種特征算法得到特征子集的特征選擇時(shí)間和特征選擇維數(shù)，如表3所示。其中特征選擇時(shí)間指對特征選擇數(shù)據(jù)集進(jìn)行特征選擇的總用時(shí)，特征維數(shù)序號和表2相對應(yīng)。

從表3中可以得到，通過與PSO-TS算法、CMPSO算法和 PSO算法得到的各個(gè)檢測模型平均特征選擇維數(shù)比較發(fā)現(xiàn)，本文所提IPSO-TS算法比其他特征選擇方法減少了至少29.2%的特征。本文方法的特征選擇時(shí)間比其他特征選擇算法要長，主要是由于pbest隨機(jī)亂序過程和TS過程增加了特征選擇時(shí)間。

在表1檢測樣本數(shù)據(jù)集上比較所有特征情況下和上述4種特征選擇算法后的入侵檢測時(shí)間和分類準(zhǔn)確率，其中入侵檢測時(shí)間是指利用KNN算法[18]對表1檢測樣本數(shù)據(jù)集中的測試數(shù)據(jù)集進(jìn)行分類預(yù)測的總用時(shí)，K取值為5。實(shí)驗(yàn)結(jié)果如下表4。

從表 4中可以得到，通過與 PSO-TS算法、CMPSO算法和PSO算法得到的特征子集作為分類樣本的平均分類準(zhǔn)確率比較發(fā)現(xiàn)，本文方法比其他特征選擇方法提高了至少2.96%的平均分類準(zhǔn)確率，縮短了至少 15%的平均檢測時(shí)間；比所有特征情況提高了 0.27%的平均分類準(zhǔn)確率，縮短了至少42.32%的平均檢測時(shí)間。其中，本文方法特征選擇時(shí)間相比其他特征選擇算法更長，該時(shí)間主要耗費(fèi)在特征選擇算法尋優(yōu)特征選擇數(shù)據(jù)集的特征子集，而檢測階段僅指搜尋到特征子集后分類算法 KNN對檢測樣本數(shù)據(jù)集的檢測時(shí)間，不包含尋優(yōu)特征子集的時(shí)間。本文方法尋優(yōu)到的特征子集維度更低、準(zhǔn)確率更高，對檢測樣本數(shù)據(jù)集分類時(shí)處理的數(shù)據(jù)量也會更低，故可以降低分類算法的分類檢測時(shí)間。

表3 4種特征選擇算法的特征選擇時(shí)間和特征選擇維數(shù)

表4 4種特征選擇算法及所有特征的檢測時(shí)間和分類準(zhǔn)確率

在表1檢測樣本數(shù)據(jù)集上比較上述4種特征選擇算法后的漏報(bào)率和誤報(bào)率，計(jì)算式如式(15)和式(16)所示，實(shí)驗(yàn)結(jié)果如表5所示。

從表 5中可以得到，通過與 PSO-TS算法、CMPSO算法和PSO算法得到的特征子集作為分類樣本的平均漏報(bào)率和誤報(bào)率相比，本文所提IPSO-TS算法比CMPSO降低了0.79%的平均漏報(bào)率，降低了0.67%的平均誤報(bào)率；比PSO-TS方法降低了1.74%的平均漏報(bào)率，降低了0.83%的平均誤報(bào)率；比PSO方法降低了1.97%的平均漏報(bào)率，降低了1.72%的平均誤報(bào)率。

本文方法以特征維數(shù)聯(lián)合分類準(zhǔn)確率構(gòu)建的適應(yīng)度函數(shù)作為特征篩選的評價(jià)指標(biāo)，通過基于改進(jìn)粒子群和禁忌搜索的二次特征選擇找到全局優(yōu)化特征子集。相比基于PSO算法或CMPSO算法的特征選擇，本文方法首先利用改進(jìn)粒子群特征選擇方法找到初始優(yōu)化特征子集，然后利用禁忌搜索的特征選擇算法再次篩選特征子集，保證了所篩選出來的特征子集具備更高分類性能；而相比基于PSO-TS的特征選擇方法，本文算法利用遺傳算子改進(jìn)了PSO算法，設(shè)計(jì)了適用于特征子集搜索的交叉和變異算子，實(shí)現(xiàn)了交叉概率和變異概率的自適應(yīng)變化，有效提高了搜尋全局優(yōu)化特征子集的效率。表3～表5的測試結(jié)果表明，在同樣的測試環(huán)境下，相比其他算法，本文方法得到的特征子集具備更低的特征維數(shù)、誤報(bào)率、漏報(bào)率和檢測時(shí)間，及更高的分類準(zhǔn)確率。

表5 4種特征選擇算法的漏報(bào)率和誤報(bào)率

5.3 實(shí)驗(yàn)結(jié)論

綜合上述結(jié)果可以發(fā)現(xiàn)，本文提出的特征選擇算法相比其他特征選擇方法顯著降低了入侵?jǐn)?shù)據(jù)集的維度，提升了在線檢測速度，提高了分類準(zhǔn)確率，降低了漏報(bào)率和誤報(bào)率。本文方法的主要問題是特征選擇時(shí)間相比其他特征選擇算法更長，但由于該時(shí)間屬于離線訓(xùn)練階段的處理時(shí)間，并不會增加系統(tǒng)的在線檢測時(shí)間[19]，反而能在篩選出性能更好的特征子集后，降低系統(tǒng)的在線檢測時(shí)延。

6 結(jié)束語

針對入侵檢測中數(shù)據(jù)維度高的問題，本文所提方法通過采用遺傳算子對粒子群算法進(jìn)行了改進(jìn)，得到了特征選擇初始最優(yōu)解，進(jìn)一步對該解進(jìn)行禁忌搜索得到了特征子集的全局優(yōu)化解。該方法不僅適用于入侵檢測系統(tǒng)，還適應(yīng)于其他類似系統(tǒng)，例如文本分類系統(tǒng)，基因數(shù)據(jù)分析系統(tǒng)等[20]，在這些系統(tǒng)中，都存在對數(shù)據(jù)集進(jìn)行離線特征降維和在線檢測數(shù)據(jù)的需求，因此，本文方法具有一定的普適性。