林輝

（渭南師范學(xué)院 信息與教育技術(shù)中心，陜西 渭南　714000）

基于粒子群和模糊數(shù)學(xué)的入侵檢測(cè)系統(tǒng)的研究

林輝

（渭南師范學(xué)院 信息與教育技術(shù)中心，陜西 渭南714000）

模糊C-均值算法是一種無(wú)監(jiān)督的數(shù)據(jù)分類方法。基于FCM算法對(duì)隨機(jī)初始值敏感，易陷入局部極致點(diǎn)這個(gè)問(wèn)題，引入粒子群優(yōu)化算法。粒子群算法的核心思想是讓每個(gè)粒子根據(jù)自身和周圍粒子的信息共享，實(shí)現(xiàn)全局搜索最優(yōu)值。收斂速度快，全局搜索能力很強(qiáng)。利用粒子群算法的全局搜索能力，對(duì)FCM算法性能進(jìn)行改進(jìn)，將粒子群優(yōu)化算法和FCM算法結(jié)合，用KDD99數(shù)據(jù)集進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法具有較高檢測(cè)率和降低誤報(bào)率。

模糊；聚類；無(wú)監(jiān)督；粒子群；KDD99

聚類分析算法是多元統(tǒng)計(jì)分析的重要方法之一，它也是統(tǒng)計(jì)模式識(shí)別中無(wú)監(jiān)督模式識(shí)別的重要學(xué)科之一，聚類分析也常叫做無(wú)督導(dǎo)學(xué)習(xí)，希望將數(shù)據(jù)分為若干子類，在同一類的數(shù)據(jù)盡量相似，不同類的數(shù)據(jù)盡量不相似。從技術(shù)上劃分分，聚類算法可分為硬聚類算法和模糊聚類算法。

1　FCM算法介紹

Zadeh提出的模糊集理論對(duì)數(shù)據(jù)的軟化分提供了有利的工具，人們開(kāi)始用模糊的方法來(lái)處理聚類問(wèn)題，實(shí)際中受到普遍歡迎的是基于目標(biāo)函數(shù)的聚類方法，該方法設(shè)計(jì)簡(jiǎn)單，解決問(wèn)題應(yīng)用范圍廣，最終可轉(zhuǎn)化為優(yōu)化問(wèn)題而用經(jīng)典的非線性規(guī)劃理論求解，易于用計(jì)算機(jī)編程［1］。

2　粒子群算法介紹

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

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

3　基于粒子群的FCM優(yōu)化

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

在使用粒子群算法進(jìn)行優(yōu)化FCM時(shí)，主要包括3部分：1）編碼；2）適應(yīng)度函數(shù)的確定；3）如何更新速度和位移公示。

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

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

算法的結(jié)束條件:

1）最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值之差小于給定的閾值的持續(xù)迭代次數(shù)達(dá)到設(shè)定值；

2）達(dá)到最大迭代次數(shù)。

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

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

2）在屬性值的范圍內(nèi)，隨機(jī)生成初始種群，每個(gè)粒子代表各類的聚類中心。

3）求適應(yīng)值；

4）根據(jù)（1）（2）式計(jì)算粒子的速度和位移；

5）計(jì)算種群中的個(gè)體適應(yīng)值，若滿足中止條件，則結(jié)束，否則轉(zhuǎn)第四步。

實(shí)驗(yàn)：實(shí)驗(yàn)采用UCI數(shù)據(jù)庫(kù)中著名的數(shù)據(jù)集Iris、Wine以及BreastCancer作為測(cè)試數(shù)據(jù)進(jìn)行驗(yàn)證。Iris數(shù)據(jù)具有5個(gè)屬性，前4個(gè)屬性用來(lái)對(duì)特征進(jìn)行描述，第5維屬性用來(lái)說(shuō)明所屬的類別。Wine是來(lái)自3個(gè)不同品種的葡萄酒化學(xué)分析結(jié)果記錄組成的葡萄酒辨識(shí)數(shù)據(jù)，有178個(gè)數(shù)據(jù)記錄，每個(gè)記錄有13個(gè)屬性，它的樣本可分為3類。不同數(shù)據(jù)集下的聚類準(zhǔn)確率和執(zhí)行時(shí)間如表1所示。

表1　實(shí)驗(yàn)結(jié)果

可以看出，K均值算法聚類準(zhǔn)確率低，聚類結(jié)果波動(dòng)性大，K均值算法對(duì)初始聚類中心的選取非常敏感，聚類中心初值不同結(jié)構(gòu)不同，而本文改進(jìn)后的算法利用了粒子群優(yōu)秀的全局尋優(yōu)能力，雖然時(shí)間復(fù)雜度比K均值稍高，但算法的聚類準(zhǔn)確率得到了提高。

4　實(shí)驗(yàn)分析

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

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

由于KDD99原始數(shù)據(jù)是包含混合型屬性的數(shù)據(jù)，它有離散型屬性的數(shù)據(jù)和連續(xù)型的特征參數(shù)，各參數(shù)的量綱也不同，或者雖然量綱相同，但是數(shù)量級(jí)不同，如果我們直接用原始數(shù)據(jù)進(jìn)行運(yùn)算，會(huì)出現(xiàn)大數(shù)吃小數(shù)的問(wèn)題，因此在計(jì)算之前，應(yīng)對(duì)指標(biāo)進(jìn)行標(biāo)準(zhǔn)化處理。

在KDD99數(shù)據(jù)集中，共有9個(gè)離散型特征屬性，為每一個(gè)特征屬性的狀態(tài)創(chuàng)建一個(gè)新的二元變量，用非對(duì)稱的二元變量編碼來(lái)表示狀態(tài)信息。如分別賦予 UDP=（1，0，0），ICMP=（0，0，1），TCP=（0，1，0），該方法優(yōu)點(diǎn)是可保障每條記錄之間的同一離散特征屬性之間的距離相等，在計(jì)算中彼此不會(huì)產(chǎn)生偏差。

由于原始數(shù)據(jù)量過(guò)于龐大，而且其中的入侵?jǐn)?shù)據(jù)所占比例多大，和實(shí)際的網(wǎng)絡(luò)環(huán)境相差很大，故我們選擇部分?jǐn)?shù)據(jù)進(jìn)行測(cè)試［5-6］，結(jié)果如表2所示。

表2　實(shí)驗(yàn)結(jié)果

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

5　結(jié)　論

模糊聚類算法是目前廣泛使用的一種聚類算法，但是該算法也有它的一些局限性，它對(duì)初始值很敏感，且已陷入局部極致點(diǎn)，聚類結(jié)果隨初始聚類中心的不同而波動(dòng)，從而導(dǎo)致聚類結(jié)構(gòu)穩(wěn)定性差，本文提出的算法時(shí)將粒子群優(yōu)化算法引入到模糊聚類算法中。該算法能較好的搜索全局極致點(diǎn)，仿真實(shí)驗(yàn)表明，該算法能有效解決聚類算法對(duì)初始值敏感和已陷入局部極致點(diǎn)的缺點(diǎn)，具有較好的聚類精度，算法有很強(qiáng)的全局尋優(yōu)能力，用KDD99數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，能有效檢測(cè)出入侵?jǐn)?shù)據(jù)。顯然這對(duì)改進(jìn)入侵檢測(cè)系統(tǒng)的性能具有重要意義。

［1］何清.模糊聚類分析理論與應(yīng)用研究進(jìn)展［J］.模糊系統(tǒng)與數(shù)學(xué)，1998，12（2）：89-94.

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

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

［4］羅敏.基于聚類和支持向量機(jī)的網(wǎng)絡(luò)入侵檢測(cè)研究［D］.武漢：武漢大學(xué)，2003.

［5］左瑞娟，武永華.基于克隆選擇的模糊分類規(guī)則提取算法［J］.智能系統(tǒng)學(xué)報(bào)，2007，2（4）：74-77.

［6］劉福榮，高曉智，王常虹，等.基于免疫克隆選擇的模糊聚類分析［J］.傳感器與維系統(tǒng)，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稿件編號(hào)：201507184

渭南師范學(xué)院科研重點(diǎn)項(xiàng)目（14ykf005）

林 輝（1982—），男，陜西西安人，碩士，工程師。研究方向:網(wǎng)絡(luò)安全。