基于粒子群和模糊數學的入侵檢測系統的研究

林輝

（渭南師范學院 信息與教育技術中心，陜西 渭南　714000）

基于粒子群和模糊數學的入侵檢測系統的研究

林輝

（渭南師范學院 信息與教育技術中心，陜西 渭南714000）

模糊C-均值算法是一種無監督的數據分類方法。基于FCM算法對隨機初始值敏感，易陷入局部極致點這個問題，引入粒子群優化算法。粒子群算法的核心思想是讓每個粒子根據自身和周圍粒子的信息共享，實現全局搜索最優值。收斂速度快，全局搜索能力很強。利用粒子群算法的全局搜索能力，對FCM算法性能進行改進，將粒子群優化算法和FCM算法結合，用KDD99數據集進行測試，實驗結果表明，改進算法具有較高檢測率和降低誤報率。

模糊；聚類；無監督；粒子群；KDD99

聚類分析算法是多元統計分析的重要方法之一，它也是統計模式識別中無監督模式識別的重要學科之一，聚類分析也常叫做無督導學習，希望將數據分為若干子類，在同一類的數據盡量相似，不同類的數據盡量不相似。從技術上劃分分，聚類算法可分為硬聚類算法和模糊聚類算法。

1　FCM算法介紹

Zadeh提出的模糊集理論對數據的軟化分提供了有利的工具，人們開始用模糊的方法來處理聚類問題，實際中受到普遍歡迎的是基于目標函數的聚類方法，該方法設計簡單，解決問題應用范圍廣，最終可轉化為優化問題而用經典的非線性規劃理論求解，易于用計算機編程［1］。

2　粒子群算法介紹

粒子群算法產生于對簡化的社會模型模擬，它是在鳥群，魚群和人類社會的行為規律的啟發下提出的［2］。它的基本思想是隨機初始化一群沒有體積沒有質量的粒子，將每個粒子視為問題的一個可行解，解的好壞由適應度函數來確定。每個粒子可以在可行解的空間中運動，采用速度參數決定它的方向和距離。通常粒子在追隨目前的最優粒子，并經過多次迭代后找到最優解。在每一代的粒子中，粒子將追蹤兩個極值，一個是粒子現階段找到的最好解，另一個是整個群體現階段找到的最優解。假設在一個D維的目標搜索空間中，由c個粒子組成一個群落，其中第i個粒子為一個D維的向量Xi=（xi1，xi2，L，xiD），i=1，2，L，N。第i個粒子的“飛行 ”速度也是一個D維的向量，第i個粒子目前搜索到的最優位置稱為個體極值，記為pbest=（pi1，pi2，L，piD），i=1，2，L，N。整個粒子群現階段搜索到的最優位置為全局極值，記為gbest=（pg1，pg2，L，pgD）。粒子根據如下的公式（1）和（2）來調整自己的速度和位置：

其中c1和c2為加速常數，r1和r2為［0，1］范圍內的均勻隨機數。式（1）右邊由三部分共同組成，第一部分為“慣性”部分，反映了粒子的運動固有屬性，代表粒子有維持自己以前速度的趨勢；第二部分為“認知”部分，反映了粒子對自身歷史經驗的回憶（remembrance），代表粒子自己優化；第三部分為“社會（social）”部分，反映了粒子間協作的經驗，代表粒子向群體最優值發展，一般取c1=c2=2。i=1，2，Λ，D。vid是粒子的速度，vid∈［-vmax，vmax］，vmax是常數，由用戶設定用來限制速度。r1和r2是介于［0，1］之間的隨機數。

3　基于粒子群的FCM優化

雖然FCM算法的每步都沿著好的方向前進，但是這種梯度下降的算法是一種局部尋優算法，易陷入局部極小值點。對于數量大時，這種情況更明顯，FCM算法所能找到的最優解對和初始值關系很大。而基于群體思想的粒子群算法初始為均勻分布解空間中的若干可能解，具有很好的全局搜索能力，不易陷入局部極值點。利用粒子群算法的優點對FCM算法改進，能減慢局部搜索，增加隸屬度矩陣的多樣性，使算法在全局范圍內找到最優點。

在使用粒子群算法進行優化FCM時，主要包括3部分：1）編碼；2）適應度函數的確定；3）如何更新速度和位移公示。

聚類算法的核心步驟是確定聚類中心，所以我們可以選取聚類中心作為種群中的個體。設樣本維數為d，聚類的中心數為c，則每個粒子實際上是一個d*c的矩陣。我們讓粒子采用實數編碼的方式，編碼長度為d*c。對FCM，優化的目的就是使得目標函數取得最小值，我們定義FCM目標函數的倒數為適應度函數。速度-位移更新辦法。定義粒子xi的領域極值是li，把該極值也作為粒子進化的一個信息來源。在優化的初始階段，鄰域定義為每個粒子自身，隨著迭代次數的增加，將鄰域范圍逐步擴展到包含所有粒子，這樣就能避免早熟，更新方法如下：

其中c1和c2的值均為2，r1和r2在（0，1）區間隨機取值，ω較大則算法在較大的范圍進行搜索，ω較小則算法在較小的范圍進行搜索，開始熱ω取值0.9，然后線性減小到0.4。

算法的結束條件:

1）最優解對應的目標函數值之差小于給定的閾值的持續迭代次數達到設定值；

2）達到最大迭代次數。

綜上所述，基于粒子群的FCM算法步驟為：

1）對算法參數賦值：聚類數目c，粒子種群規模，允許的最大速度c，最大迭代次數，閾值和迭代次數閾值。

2）在屬性值的范圍內，隨機生成初始種群，每個粒子代表各類的聚類中心。

3）求適應值；

4）根據（1）（2）式計算粒子的速度和位移；

5）計算種群中的個體適應值，若滿足中止條件，則結束，否則轉第四步。

實驗：實驗采用UCI數據庫中著名的數據集Iris、Wine以及BreastCancer作為測試數據進行驗證。Iris數據具有5個屬性，前4個屬性用來對特征進行描述，第5維屬性用來說明所屬的類別。Wine是來自3個不同品種的葡萄酒化學分析結果記錄組成的葡萄酒辨識數據，有178個數據記錄，每個記錄有13個屬性，它的樣本可分為3類。不同數據集下的聚類準確率和執行時間如表1所示。

表1　實驗結果

可以看出，K均值算法聚類準確率低，聚類結果波動性大，K均值算法對初始聚類中心的選取非常敏感，聚類中心初值不同結構不同，而本文改進后的算法利用了粒子群優秀的全局尋優能力，雖然時間復雜度比K均值稍高，但算法的聚類準確率得到了提高。

4　實驗分析

本實驗在Matlab環境下實現。采用用KDDCUP99入侵檢測數據集作為實驗對象。這個數據集是一個在軍事網絡環境中模擬的廣泛的不同類型的數據，是DARPA（美國國防部）委托林肯實驗室模擬空軍網絡環境所獲取的原始入侵數據。其中訓練數據5百萬個連接記錄，測試數據集包含了2百萬個連接數據。網絡入侵檢測系統是針對網絡上的數據包進行分析，而通常網絡上的數據量非常之大，在網絡入侵檢測中，在對KDD99數據進行分析的時候，由于KDD99數據具有41維數據，其中每一維都有一定的含義，這就使一些方法如數據立方合計、數據塊消減、利用編碼壓縮等方法不方便適用。所以在KDD99中用到的主要是級數消減，即減少或者消除無義數據的維數，常用的方法是采用PCA進行數據的屬性約簡。

1933年，Hotelling提出了主成分分析（Principle Component Analysis，PCA）方法［3］，PCA是一種將多個變量轉換為少數幾個不相關的綜合指標的統計分析方法，由于實測的參數之間存在一定的相關性，因此有可能用較少數的綜合參數分別綜合存在于各變量中的各類信息，而綜合參數之間彼此不相關，也就是說各個指標代表的信息不重疊。對KDD99數據集的41維屬性進行分析，除去第7、8、9、11、14、15、16、17、18、20、21維后的其他屬性的貢獻率仍可達到99.9%［4］，故將第7、8、9、11、14、15、16、17、18、20、21維屬性刪除，從而得到將原來數據集的41維屬性約簡為30維屬性。

由于KDD99原始數據是包含混合型屬性的數據，它有離散型屬性的數據和連續型的特征參數，各參數的量綱也不同，或者雖然量綱相同，但是數量級不同，如果我們直接用原始數據進行運算，會出現大數吃小數的問題，因此在計算之前，應對指標進行標準化處理。

在KDD99數據集中，共有9個離散型特征屬性，為每一個特征屬性的狀態創建一個新的二元變量，用非對稱的二元變量編碼來表示狀態信息。如分別賦予 UDP=（1，0，0），ICMP=（0，0，1），TCP=（0，1，0），該方法優點是可保障每條記錄之間的同一離散特征屬性之間的距離相等，在計算中彼此不會產生偏差。

由于原始數據量過于龐大，而且其中的入侵數據所占比例多大，和實際的網絡環境相差很大，故我們選擇部分數據進行測試［5-6］，結果如表2所示。

表2　實驗結果

對于上表的實驗結果，我們可以看到對于的neptune、Buffer_overflow、ftp_write、Nmap、Sendmail Waremaster Ipsweep 、Imap等入侵數據，算法能夠較好地檢查出來，但是也有Xterm、Loadmodule入侵的檢測效果不是很好，我們估計檢測率低的可能由于正常連接記錄的數目相對來說太少，還有可能就是某些正常的數據非常接近于入侵數據。這種數據在大數據量的情況下所占的比例是很少的，但是在這里卻在正常的數據中占據一定的比例，所以使得誤報率較高。

5　結　論

模糊聚類算法是目前廣泛使用的一種聚類算法，但是該算法也有它的一些局限性，它對初始值很敏感，且已陷入局部極致點，聚類結果隨初始聚類中心的不同而波動，從而導致聚類結構穩定性差，本文提出的算法時將粒子群優化算法引入到模糊聚類算法中。該算法能較好的搜索全局極致點，仿真實驗表明，該算法能有效解決聚類算法對初始值敏感和已陷入局部極致點的缺點，具有較好的聚類精度，算法有很強的全局尋優能力，用KDD99數據進行仿真實驗，能有效檢測出入侵數據。顯然這對改進入侵檢測系統的性能具有重要意義。

［1］何清.模糊聚類分析理論與應用研究進展［J］.模糊系統與數學，1998，12（2）：89-94.

［2］魏秀業，潘虹俠.粒子群優化及智能故障診斷［D］.北京：國防工業出版社，2010.

［3］黃偉如.基于聚類的入侵檢測方法研究［D］.武漢：華中科技大學，2006.

［4］羅敏.基于聚類和支持向量機的網絡入侵檢測研究［D］.武漢：武漢大學，2003.

［5］左瑞娟，武永華.基于克隆選擇的模糊分類規則提取算法［J］.智能系統學報，2007，2（4）：74-77.

［6］劉福榮，高曉智，王常虹，等.基于免疫克隆選擇的模糊聚類分析［J］.傳感器與維系統，2008，27（3）：26-56.

Research on intrusion detection system based on particle swarm optimization and fuzzy mathematics

LIN Hui
（Center of Information and Education Technology，Weinan Normal University，Weinan 714000，China）

Fuzzy C-means algorithm is an unsupervised classification method.Based on the FCM algorithm for random initial value sensitive，easy to fall into local extreme point of this problem，introduce particle swarm optimization algorithm to FCM. the core idea of particle swarm algorithm is to let each particle according to its own and the surrounding particles of information sharing，to achieve global search optimal value，convergence speed，global search ability is very strong.Using the global search ability of particle swarm optimization，to improve the performance of FCM algorithm.The particle swarm optimization algorithm and FCM algorithm are combined.Test using KDD99 data sets，The experimental results show that the improved algorithm has higher detection rate and lower false positive rate.

fuzzy；clustering；unsupervised；particle swarm；KDD99

TN391

A

1674-6236（2016）14-0024-03

2015-07-28稿件編號：201507184

渭南師范學院科研重點項目（14ykf005）

林 輝（1982—），男，陜西西安人，碩士，工程師。研究方向:網絡安全。