改進粒子群聯合禁忌搜索的特征選擇算法

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

（1. 國家數字交換系統工程技術研究中心，河南 鄭州450002；2. 中國人民解放軍戰略支援部隊信息工程大學，河南 鄭州 450002）

1 引言

入侵檢測技術利用數據挖掘、機器學習等方法對審計日志、安全日志或者網絡上獲取的信息進行分析處理，實現對入侵行為的檢測[1]。瞬息萬變的海量網絡數據使入侵檢測系統（IDS，intrusion detection system）面臨巨大挑戰，如檢測速度低、檢測效果差、計算負荷大等。其中，檢測速度是入侵檢測系統實時性要求的重要指標，如何在保證檢測準確率的前提下提升入侵檢測速度，成為當前入侵檢測的研究熱點。

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

2 研究現狀

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

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

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

3 IPSO-TS特征選擇算法

IPSO-TS特征選擇算法的流程如圖1所示，其中，搜索模塊應用本文提出的改進粒子群聯合 TS算法，實現搜尋候選特征子集的功能；評價模塊應用本文提出的適應度函數，完成對候選特征子集的性能評價；判決模塊根據判決條件選擇數據集的最優特征子集，結束循環，并將該子集作為結果輸出。

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

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

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

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

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

其中，TP和TN表示入侵檢測中正確分類的正常數據和異常數據，FP和FN表示入侵檢測中錯誤分類的正常數據和異常數據。

3.1 改進的PSO算法

3.1.1 PSO算法

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

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

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

其中，wmax和wmin分別表示慣性權重的最大值和最小值，iter表示迭代次數，maxiter表示最大迭代次數。

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

其中，c3和c4是常數，且c3＞c4。

3.1.2 基于遺傳算法對粒子群的改進

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

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

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

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

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

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

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

3.2 TS算法

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

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

其中，t表示x或y。

本文中禁忌表使用隊列結構，每次迭代時，添加禁忌對象到隊首，隊列溢出時，刪除排在隊尾的禁忌元素。藐視準則要滿足2個要求：1) 將要解禁的解必須優于當前解[16]；2) 為了避免陷入死循環，禁忌表隊首的元素不能被解禁。

4 IPSO-TS特征選擇方法的IDS應用實例

IDS流程如圖2所示，其中，數據獲取模塊通過監控目標網絡或系統來采集數據；數據預處理模塊是對采集的數據進行數值化、標準化、特征選擇等處理，本文IPSO-TS群算法用于選擇入侵檢測數據的特征子集；入侵檢測模塊利用訓練數據來訓練分類器，采用分類器對待檢測的數據集進行分析，獲得入侵檢測的結果，通過檢測指標評價結果，本文中的分類器由KNN算法構建；響應模塊是IDS對檢測結果的決策。

圖2 IDS流程

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

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

圖3 IPSO-TS算法在IDS中應用流程

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

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

步驟 4分別更新相應pbest、gbest及它們的適應度。

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

步驟 6根據 3.2節進行禁忌搜索，將經過上述步驟得到的群體最優解gbest作為TS算法的初始解，利用初始解產生相應的鄰域解，得到組不同解當作初始候選集合及其適應度。

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

步驟 8將候選解中非禁忌對象對應的最優候選解作為當前解，然后執行步驟10。

步驟 9將滿足藐視準則中最優解作為當前解，然后執行步驟10。

步驟 10將最早進入禁忌表的禁忌對象作為當前解，更新禁忌表并修改禁忌對象任期。

步驟 11判斷是否滿足最大禁忌搜索次數或當前解適應度是否達到限定值，若滿足則執行步驟8，否則執行步驟12。

步驟 12輸出全局優化解作為入侵檢測數據集全局優化特征子集。

5 IDS實驗結果與分析

5.1 KDD CUP 99數據預處理

本文實驗中使用的是KDD CUP 99數據集，它是網絡入侵檢測領域的標準數據集[17]，選取其提供的10%訓練子集和測試子集（corrected）進行實驗，其中，訓練子集包含 49萬條網絡連接記錄，測試子集包含 31萬條網絡連接記錄。每個網絡連接被標記為正常類型和異常類型，異常類型被分為DoS（拒絕服務攻擊）、Probe（掃描與探測）、R2L（未經授權的遠程訪問）、U2R（對本地超級用戶的非法訪問）等4類，共有39種異常類型。本文實驗中分別針對4類異常類型數據和匯總數據，進行入侵攻擊檢測，樣本數據集如表1所示。

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

表1 KDD CUP 99樣本數據集組成

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

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

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

5.2 實驗結果及分析

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

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

在特征選擇數據集上比較4種特征算法得到特征子集的特征選擇時間和特征選擇維數，如表3所示。其中特征選擇時間指對特征選擇數據集進行特征選擇的總用時，特征維數序號和表2相對應。

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

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

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

表3 4種特征選擇算法的特征選擇時間和特征選擇維數

表4 4種特征選擇算法及所有特征的檢測時間和分類準確率

在表1檢測樣本數據集上比較上述4種特征選擇算法后的漏報率和誤報率，計算式如式(15)和式(16)所示，實驗結果如表5所示。

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

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

表5 4種特征選擇算法的漏報率和誤報率

5.3 實驗結論

綜合上述結果可以發現，本文提出的特征選擇算法相比其他特征選擇方法顯著降低了入侵數據集的維度，提升了在線檢測速度，提高了分類準確率，降低了漏報率和誤報率。本文方法的主要問題是特征選擇時間相比其他特征選擇算法更長，但由于該時間屬于離線訓練階段的處理時間，并不會增加系統的在線檢測時間[19]，反而能在篩選出性能更好的特征子集后，降低系統的在線檢測時延。

6 結束語

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