基于粒子群優化的入侵特征選擇算法

吳慶濤，曹繼邦，鄭瑞娟，張聚偉

基于粒子群優化的入侵特征選擇算法

吳慶濤，曹繼邦，鄭瑞娟，張聚偉

針對高維數入侵檢測數據集中信息冗余導致入侵檢測算法處理速度慢的問題，提出了一種基于粒子群優化的入侵特征選擇算法，通過分析網絡入侵數據特征之間的相關性，可使粒子群優化算法在所有特征空間中優化搜索，自主選擇有效特征子集，降低數據維度。實驗結果表明該算法能夠有效去除冗余特征，減少特征選擇時間，在保證檢測準確率的前提下，有效地提高了系統的檢測速度。

入侵檢測；粒子群優化；特征選擇；優化搜索；特征關聯性

1 引言

入侵檢測技術是網絡安全的一個重要研究方向。該技術通過分析網絡流量或系統審計記錄等方式來發現網絡或系統中是否有違反安全策略的攻擊行為，以便制定相應策略，彌補系統漏洞和填補系統功能。但是，在入侵檢測中，探測器收集到的數據量龐大且提取出來的特征繁多，其中有些特征與檢測無關，這些特征一方面降低了分類或聚類的精度，另一方面大大增加了學習及訓練的時間和空間復雜度，影響算法運行效率。因此，在保證檢測正確率的前提下，如何提高系統的檢測速度已經成為當前的一個研究熱點。研究發現，特征選擇可以在保持原有網絡數據信息完整性的基礎上去除其中的冗余特征，達到提高系統檢測速度的目的。從現有特征選擇算法來看，文獻[1-3]中有諸如正向搜索（forward searching）、反向搜索（backward searching）、順序搜索（sequential searching）等啟發式搜索策略（heuristic searching strategies）；文獻[4]中采用了擴張矩陣理論和遺傳算法（genetic algorithm）相結合的方法等。

對于大規模數據集上的特征選擇，這些搜索策略的計算資源耗用大，收斂速度慢，時間復雜度較高。而在文獻[5]中提出的非搜索性策略，雖然其時間復雜度相對較低，但是所得到的特征子集中有較多冗余特征，影響了分類準確率。針對現有算法中所存在的缺點，本文提出一種基于粒子群優化的入侵特征選擇算法（Intrusion Feature Selection Algorithm，IFSA）。該方法引入相關性分析特征之間的關聯度，指導收斂速度較快的粒子群算法在特征空間里搜索，實現入侵特征選擇的自適應和自優化。

2 特征相關性分析

關聯度[6]被廣泛地應用在機器學習和統計相關性分析中，用來評價特征之間的相關性，關聯度的選取在很大程度上影響著特征選擇的效率。兩個隨機變量之間的關聯度通常以基于信息論中定義的熵[7]來量度。

定義1（熵）對于一個數據集中的離散特征X，它的可能取值為{x1，x2，…，xn}，對應的概率分布為{p(x1)，p(x2)，…，p(xn)}，則X的熵定義為：

熵表達了特征 X所包含信息量的多少，熵越小，表明X中的數據在取值上分布越不均勻，X取某個值或某幾個值的數據較多，則取其他值的數據就較少，如果X的所有數據都取同一個值，那么X的熵就為0，此時該特征所包含的信息為0，即該特征在數據集合中不存在對數據有用的信息；反之，X的熵越大，說明數據在取值上分布越均勻，其蘊含的信息越多。

定義2（聯合熵）一個數據集中的離散特征X和Y，若它們的取xi和 yj的值的聯合概率為 p(xi，yj)，則 X和Y聯合熵定義為：

聯合熵的概念是從熵引申出來的，刻畫的是兩個隨機變量之間共有的信息量，其值越大，說明兩個變量之間的相關性越大。如果兩個變量之間的聯合熵為0，則說明兩個變量是是獨立的。

3 入侵特征選擇算法

入侵特征選擇算法（IFSA）采用收斂速度較快的粒子群算法進行特征空間搜索，引入相關性分析指導算法的搜索，實現特征選擇的自適應和自優化。

3.1 特征選擇定義及原則

定義3（特征子集）特征子集是將輸入屬性集合中不相關和冗余的屬性刪除后得到的新屬性集合。

定義4（特征選擇）特征選擇（也稱為屬性選擇或特征提取）是指識別和選取一個有效屬性子集，用于描述一個相對較大的通常含有冗余和不相關屬性的數據集中的有效模式。特征子集選擇過程中，算法一般根據以下原則選取有效的、最小規模的屬性集合：（1）保證分類精度不能明顯下降；（2）特征選擇前后，類的分布盡可能一致。

3.2 粒子群優化算法

Kennedy和Eberhart受到鳥群捕食行為的研究結果啟發[8]，于1995年提出粒子群（PSO）算法，PSO算法具有執行速度快，受維數變化影響小等優點，迅速受到了人們的重視，算法描述如下：

假設在一個D維的目標搜索空間中，有m個粒子組成一個群落，其中第i個粒子表示為一個 D維向量，xi= (xi1，xi2，…，xiD)T，i=1，2，…，m，即第i個粒子在D維的搜索空間中的位置是xi，每個粒子的位置就是一個潛在的解。將xi代入一個目標函數就可以計算出其適應值，根據適應度的大小衡量xi的優劣。第i個粒子的“飛翔”速度也是一個D維的向量，記為vi=(vi1，vi2，…，viD)T。第i個粒子迄今為止搜索到的最優位置記為 pg=(pg1，pg2，…，pgD)T。基本PSO就是根據下面的兩個公式對所示的粒子進行操作[12]：

其中，d=1，2，…，D;i=1，2，…，m，m為種群規模；ω為慣性權重，保持原速度的系數；c1是粒子跟蹤自己歷史最優值的權重系數，它表示粒子自身的認識，所以叫“認知”，通常設置為2；c2是粒子跟蹤群體最優值的權重系數，它表示粒子對整個群體知識的認識，所以叫做“社會知識”，經常叫做“社會”，通常設置為2；r1、r2是[0，1]之間的隨機數；η是對位置更新的時候，在速度前面加的一個系數，這個系數叫做約束因子，通常設置為1；n=1，2，…為迭代次數。

3.3 離散二進制PSO算法

1997年Kennedy和Eberhart又提出了PSO算法的離散二進制版本（BPSO）[10]，使這種算法進入了組合優化領域。BPSO采用二進制編碼的形式，在BPSO模型中將每一維xi和 pi限制為1或者為0，而速度vi不作這種限制。用速度的Sigmoid函數表示位置狀態改變的可能性。

二進制版本PSO的速度更新公式沒有改變，還是公式（3）；而位置式（4）變為：

式中，rand()為[0，1]之間的隨機數，可用最大速度Vmax來限制xi為0或者1的可能性。利用粒子群算法解決優化問題的關鍵在于適應度函數選擇，適應度函數體現了實際問題和優化算法之間的聯系。

3.4 編碼模式

特征選擇的實質就是從M個特征中，選出N個特征構成子集。因此可以把每一個特征定義為粒子的一維離散二進制變量，M個特征構成粒子的M維離散二進制空間。對于每一個粒子，如果第i位為1，表示第i個特征被選中，反之表示該特征沒有被選中。因此，每個粒子代表了一個不同的特征子集，也就是一個候選集。比如，粒子i= 100 110，那么表明特征1、特征3和特征5被選中，特征子集為{1，3，5}。

3.5 適應度函數

在特征選擇中，適應度評價函數的選擇至關重要。雖然人們提出了距離評測、相關性評測等幾種不同的建議，但目前還沒有能被一致接納的度量標準。本文采用相關性評測方法，其核心思想在于選擇一個屬性子集，屬性各自與類屬性有較大關聯，但幾乎沒有內部關聯，以此達到消除無關屬性，同時也消除重復屬性的目的。兩屬性A和B之間關系可用對稱不確定性（symmetric uncertainty）來度量：

基于相關性的屬性選擇決定了一個屬性集的優良，用公式（8）度量：

其中，C是類屬性，i和 j包括屬性集里的所有屬性。公式（8）也就是粒子群的適應度函數，顯然值越大，粒子的適應度越高。

3.6 算法描述

根據以上的分析，本文算法的主要步驟如下：

步驟1裝載訓練數據集，設置初始化參數。

步驟2隨機產生初始群體，為每個粒子生成隨機初始化速度，設置粒子的個體極值pbest和群體的全局極值gbest。

步驟3根據公式（8）評價每個粒子的適應值。

步驟4對每個粒子，將其適應值與其經歷過的最好位置pbest進行比較，如果優于pbest，則將其作為當前的最好位置pbest。

步驟5對每個粒子，將其適應值與群體所經歷過的最好位置gbest進行比較，若優于gbest，則將其作為群體最優位置，并重新設置gbest的索引號。

步驟6根據公式（3）、（5）、（6）更新粒子速度和位置。

步驟7如果迭代次數達到最大，轉步驟8；否則轉步驟3。

步驟8把群體最優位置轉換為對應的特征子集返回。

4 實驗過程與結果分析

4.1 實驗數據集

為了驗證算法的有效性，實驗數據采用KDD99數據集。該測試數據集收集了模擬網絡5個星期的運行數據，其中第1個和第3個星期是沒有攻擊的訓練數據，用來訓練異常檢測系統；第2個星期的數據是含有43個攻擊例子的測試數據（整個測試數據集有64種攻擊方法），用來訓練誤用檢測系統；第4和第5星期是測試數據，所有數據集大約共計500萬條記錄，每條記錄包含41個特征（屬性）。因為KDD99數據集中的數據量非常龐大，為了便于驗證本文算法，需要對數據集進行取樣，使數據量減少。分別對訓練數據集與測試數據集中的數據采取隨機抽樣，然后將隨機抽樣出的數據進行組合，形成實驗用的訓練數據子集和測試數據子集，其中，訓練子集共有21 836條，測試子集共有36 715條。算法參數設置如下：D=41，m=30，ω=0.9，c1=c2=2.0，Vmax=4.0，迭代次數為50次。

4.2 實驗方案

為了可以更清晰準確地驗證入侵特征選擇算法的性能，設計了以下三個實驗。

實驗1比較基于所有41個特征的入侵檢測模型和基于特征選擇后的特征子集的模型在檢測時間，以及檢測準確率方面的性能。首先在隨機抽樣后的數據集上應用本文提出的特征選擇方法，得到對應的特征子集，然后分別在訓練集上，基于所有41個特征和特征選擇后的特征子集建立入侵檢測模型。

實驗2比較采用本文算法的入侵檢測模型與應用遺傳算法（GA算法）和Relief算法的入侵檢測模型在檢測時間和檢測準確率方面的性能。首先在數據集上應用本文所提出的特征選擇算法，得到對應的特征子集，并基于該特征子集建立入侵檢測模型，然后采用GA算法和Relief算法對同一訓練數據集進行特征選擇。

實驗3使用SVM作為分類器，比較方案二在特征選擇后得到的3個特征子集用于樣本分類時所產生的分類錯誤率。

4.3 實驗結果分析

首先在隨機抽樣后的實驗訓練數據集上應用本文的IFSA算法，所產生的特征子集如表1所示。

表1 應用IFSA算法得到的特征子集

從表l中可以看出經過特征選擇后，針對不同的攻擊得到不同的特征子集。接下來針對每一種攻擊類型，分別在未經過特征選擇的數據集以及表1所示的特征選擇后的特征子集上建立入侵檢測模型，并對每個入侵檢測模型在檢測時間以及檢測準確率上的表現進行對比。對比結果如表2所示。

表2 特征選擇前后檢測率以及檢測時間的比較

從表2中可以看出，使用本文提出的算法的入侵檢測模型，在檢測準確率以及檢測時間方面的表現都要明顯優于未經特征選擇的入侵檢測模型。在隨機抽樣后的實驗用訓練數據子集上，分別應用IFSA算法、GA算法和Relief算法，獲得的實驗結果如表3、表4所示。

表3 IFSA、GA、Relief算法分類準確率對比

表4 IFSA、GA、Relief算法分類檢測時間對比

最后，使用SVM作為分類器，將IFSA算法、遺傳算法和Relief算法對實驗訓練數據集進行特征選擇后得到的特征子集作為分類樣本，實驗結果如表5、表6所示。

表5 SVM分類器下IFSA、GA、Relief分類準確率對比

表6 SVM分類器下IFSA、GA、Relief檢測時間對比

從表4中可以看出，由本文提出的IFSA算法和基本遺傳算法所產生的特征子集作為分類樣本的分類準確率差別不大，并且準確率高于Relief算法；而在特征選擇時間方面，本文提出的方法則是表現最好的。

結合實驗1、實驗2以及實驗3的結果可以看出，本文提出的IFSA算法，有效降低了數據信息的特征維數；在此基礎上所建立的入侵檢測模型在檢測時間及檢測準確率方面，表現均優于未經特征選擇的入侵檢測模型；在同GA算法及Relief算法進行比較后，可以看出本文方法能夠在保證較高的分類準確率的情況下，使特征選擇的時間復雜度降低，較為有效地縮短了特征選擇的時間。

5 總結

提出了一種基于粒子群優化的入侵特征選擇算法，本文方法通過分析網絡入侵數據中所有特征之間的相關性，利用粒子群優化算法在所有特征空間里優化搜索，并依據相關性進行指導搜索，能夠自適應、自優化地選擇有效的特征子集以降低數據維度。通過建立入侵檢測模型對KDD99數據集進行實驗驗證，結果表明，本文提出的特征選擇方法應用于入侵檢測系統后，能夠在保證檢測準確率的前提下，有效地提高系統的檢測性能，并且在檢測時間和分類準確率方面的表現都要優于已有特征選擇方法。

[1]詹勇，聲錫藏，王勇軍.攻擊特征自動提取技術綜述[J].通信學報，2009，30（2）：96-105.

[2]牟永敏，李美貴，粱琦.入侵檢測系統中模式匹配算法的研究[J].電子學報，2006，34（12A）：2488-2490.

[3]Jain A K，ZongKer D.Feature selection：evaluafion，application，and small sample performance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（2）：153-158.

[4]陳志賢，黃皓.應用擴張矩陣理論的攻擊特征提取[J].計算機科學，2010，37（4）：49-51.

[5]Mitra P，Murthy C A，Pal S K.Unsupervised feature selection using feature similarity[J].IEEE Trans on Pattern Recognition and Machine Intelligence，2002，24（3）：301-312．

[6]肖立中，劉云翔.適合于入侵檢測的分步特征選擇算法[J].計算機工程與應用，2010，46（11）：81-84.

[7]饒鮮，楊紹全，魏青.基于熵的入侵檢測特征參數選擇[J].系統工程與電子技術，2006，28（4）：599-601.

[8]Kennedy J，Eberhart R C.Particle swarm optimization[C]// ProcofIEEE Conferenceon NeuralNetworks，1995：1942-1948.

[9]赫然，王永吉，王青，等.一種改進的自適應逃逸微粒群算法及實驗分析[J].軟件學報，2005，16（12）：2036-2044.

[10]Eberhart R C，Kennedy J.A discrete binary version of the particle swarm algorithm[C]//Proceedings of the IEEE Conference on Systems，Man，and Cybernetics.Orlando，FL：IEEE Press，1997：4104-4109.

WU Qingtao,CAO Jibang,ZHENG Ruijuan,ZHANG Juwei

河南科技大學 電子信息工程學院，河南 洛陽 471003

Electronic and Information Engineering College,Henan University of Science and Technology,Luoyang,Henan 471003,China

Intrusion feature selection can improve the correctness and detection rate of the intrusion detection system effectively. A intrusion feature subset selection algorithm based on Particle Swarm Optimization（PSO）is proposed.Depending on the analyses of correlation between all features of network intrusion data,the PSO algorithm is used to search and choose effective feature subset independently to reduce data dimension in the feature space.The experimental results show that the algorithm can effectively remove redundant features,reduce the time of feature selection,ensure detection accuracy and improve detecting speed.

intrusion detection;Particle Swarm Optimization（PSO）;intrusion feature selection;optimization searching; feature relevance

A

TP393.08

10.3778/j.issn.1002-8331.1109-0031

WU Qingtao,CAO Jibang,ZHENG Ruijuan,et al.Intrusion feature selection algorithm based on Particle Swarm Optimization.Computer Engineering and Applications,2013,49（7）：89-92.

國家自然科學基金（No.61003035，No.61040010）；河南省高等學校青年骨干教師資助計劃項目（No.2009GGJS-050）；河南省教育廳自然科學基礎研究資助計劃項目（No.2009A520012，No.2010A520018）。

吳慶濤（1975—），男，博士，副教授，CCF會員，研究方向為計算機系統安全，智能信息處理；曹繼邦（1987—），男，碩士研究生，研究方向為網絡安全；鄭瑞娟（1980—），女，博士，副教授；張聚偉（1980—），男，博士，副教授。E-mail：wqt8921@126.com

2011-09-13

2011-12-23

1002-8331（2013）07-0089-04