改進(jìn)的遺傳模糊聚類算法及其在入侵檢測中的應(yīng)用

（湖南第一師范學(xué)院 外語系外語教學(xué)綜合實驗中心，長沙 410205）

摘 要：本文提出了基于改進(jìn)遺傳算法的特征加權(quán)模糊聚類算法（IG-WFCM），通過對樣本數(shù)據(jù)集進(jìn)行聚類劃分，以此來確定數(shù)據(jù)所屬的類別。并通過入侵檢測仿真實驗對該算法進(jìn)行了測試，結(jié)果表明本文的算法是可行的，在一定程度上提高了入侵檢測算法的性能和效率。

關(guān)鍵詞：遺傳算法；模糊聚類算法；入侵檢測

中圖分類號：TP393.08 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599 （2013） 09-0000-02

模糊C-均值聚類是利用模糊理論進(jìn)行數(shù)據(jù)分析的經(jīng)典聚類算法，由于其能比較客觀地反映現(xiàn)實模型，所以在數(shù)據(jù)挖掘、入侵檢測等很多領(lǐng)域都獲得了有效的應(yīng)用[1，2]。遺傳算法（GA）是一種模擬自然進(jìn)化過程來進(jìn)行查找最優(yōu)解的高效全局優(yōu)化搜索算法[3]，應(yīng)用非常廣泛。本文結(jié)合這兩種算法的特點(diǎn)，提出了一種基于遺傳算法的模糊聚類算法，并通過仿真實驗對其在入侵檢測中的表現(xiàn)進(jìn)行研究。

1 模糊C-均值聚類算法基本原理

模糊C-均值聚類（FCM）算法基本原理：通過優(yōu)化目標(biāo)函數(shù)計算每個樣本點(diǎn)對所有類別中心的隸屬度，從而自動將樣本分成c個模糊類別。

設(shè)樣本集，X={X1，X2，…，Xn}則特征向量樣本，Xi=（Xi1，Xi2，…，Xim），xik為樣本xi的第k個屬性值。樣本集X的c個模糊子類別為X1，X2，…XC，V=（V1，V2，…VC），Vj為類別Xj的聚類中心，隸屬度矩陣U=（uij），xi對于Xj的隸屬關(guān)系為uij。

（1-1）

（1-2）

Jm為目標(biāo)函數(shù)，表示樣本到類別中心的距離平方和，dik=ㄧㄧXi-Vkㄧㄧ即樣本xi到第k個類別中心Vk之間的歐式距離，模糊加權(quán)指數(shù)m∈（1，∞），其用來控制隸屬度矩陣U的模糊程度，根據(jù)大量實驗可知，m值一般取[1.5，2.5]。利用拉格朗日乘數(shù)法，結(jié)合條件∑ck=1Uik=1，Uik∈[0，1]，i=1，2，∧，n，k=1，2，..，c

可得：

Uik=[∑cj=1（dik/dij）2/（m-1）]-1 （1-3）

Vk=∑ni=1（Uik）mxi/∑ni=1（Uik）m （1-4）

設(shè)置終止條件 ，通過式（1.3）和式（1.4）迭代計算，使目標(biāo)函數(shù)Jm趨向最小，達(dá)到收斂的目的。

2 屬性處理及初始化聚類中心

鑒于網(wǎng)絡(luò)數(shù)據(jù)屬性值之間的度量單位存在較大差異，為了減少對聚類結(jié)果的影響，需要對數(shù)據(jù)的屬性進(jìn)行預(yù)處理[5]。若X={x1，x2，...，xn}為樣本集，則容量為n，維數(shù)為m，Xif表示第i個樣本第f個屬性值。xi包含r個連續(xù)型屬性C1，C2，…，Cr和s個離散型屬性T1，T2，…，Ts

本文對于離散型屬性值采用基于不同狀態(tài)的實數(shù)編碼方式。N（tik）、N（tjk）分別表示屬性Tk在樣本集X中取值為tik和tjk的數(shù)量，dt（i，j）即樣本xi和xj之間的離散型屬性距離。

dt（i，j）=∑sk=1（N（tik））/N（tik）N（tjk）*λ（tik，tjk） （1-5）

λ（tik，tjk）={0（tik=tjk；）1（tik≠tjk） （1-6）

式（1-7）中Xif即為標(biāo)準(zhǔn)化后的連續(xù)型屬性值，設(shè)R1，R2，…，Rr分別是連續(xù)型屬性C1，C2，…，Cr的取值范圍。mf=1/n∑ni=1xif，sf=1/n∑ni=1（Xif-mf）。

xif=xif-mf/sf （1-7）

dc（i，j）=ω1（x`i1-x`j1）2+ω2（x`i2-x`j2）2+∧+ωr（x`ir-x`jr）2 （1-8）

ωf=Rf/∑rk=1Rk，對連續(xù)型屬性距離值dc（i，j）進(jìn)行歸一化處理如下：

d`c（i，j）=dc（i，j）/max{dc（i，j）} （1-9）

最后，樣本xi和xj的混合屬性距離即為DH（i，j）。

DH（i，j）=r/（r+s）*d`c（i，j）+s/（r+s）*dt（i，j） （1-10）

本文初始化聚類中心的確定采取文獻(xiàn)5的方法，預(yù)先不設(shè)定聚類數(shù)目C，而是通過啟發(fā)式聚類來自動確定聚類數(shù)目，從而劃分聚類類別。網(wǎng)絡(luò)數(shù)據(jù)樣本集第一個聚類中心的計算可以采用屬性算術(shù)平均值和屬性最高頻率取值的方法[5]。

令第一個聚類中心V1的連續(xù)型屬性向量A=（a1，a2，…，ak，…，ar），離散型屬性向量B=（b1，b2，...，bk，…，bs）。ak為連續(xù)型屬性Ck的算術(shù)平均值，bk為離散型屬性Tk的最高頻率值。

ak=1/n∑nj=1xjk， k=1，2，…，r （1-11）

v1=A+B=（a1，a2，∧，ar，b1，b2，∧，bs） （1-12）

3 IG-WFCM算法在入侵檢測中的應(yīng)用

本文針對模糊聚類算法的特點(diǎn)，提出了基于改進(jìn)遺傳算法的特征加權(quán)模糊聚類（IG-WFCM）算法，并通過在入侵檢測系統(tǒng)進(jìn)行測試，對訓(xùn)練數(shù)據(jù)集劃分聚類，計算待測數(shù)據(jù)與聚類中心Vi的最小距離di，若di大于聚類寬度閾值，則為異常數(shù)據(jù)。

Step1.對輸入的訓(xùn)練數(shù)據(jù)集初始化；將原始樣本集劃分成Cmax-1種不同的聚類，聚類數(shù)目為Ck，并找出對應(yīng)的Ck個初始聚類中心；

Step2.對Ck個初始聚類中心進(jìn)行染色體編碼，形成初始種群。

Step3.針對種群中的個體進(jìn)行FCM聚類運(yùn)算，計算UCk和VCk，由此迭代，最后得出目標(biāo)函數(shù)Jm；

Step4.對第t-1代種群進(jìn)行選擇操作，形成種群P'（t-1）；對于種群P'（t-1）進(jìn)行交叉操作，形成種群P''（t-1）；對種群P''（t-1）的個體進(jìn)行變異操作，形成第t代種群P（t）。

Step5.根據(jù)其聚類中心矩陣計算出群體中個體的隸屬度矩陣，再計算對應(yīng)的目標(biāo)函數(shù)Jm，求出目標(biāo)函數(shù)的平均值Jm=1/n∑nk=1Jm（k），若t=0，則t=t+1且返回Step3，如果t≥Gmax或者︱Jm（t）-Jm（t-1）︳<ε，則轉(zhuǎn)下一步Step6，否則t=t+1，返回Step3繼續(xù)迭代。

Step6.選取最優(yōu)個體，并對其進(jìn)行聚類的評價。

Step7.如果Ck

Step8.利用評價函數(shù)選取最優(yōu)聚類數(shù)，輸出訓(xùn)練數(shù)據(jù)集的最優(yōu)聚類結(jié)果。

Step9.計算聚類的寬度閾值，對測試數(shù)據(jù)進(jìn)行檢測。

4 仿真實驗

4.1 樣本數(shù)據(jù)集的選取

本文實驗選用的樣本數(shù)據(jù)是KDD CUP 1999入侵?jǐn)?shù)據(jù)集中的數(shù)據(jù)，它是目前入侵檢測領(lǐng)域權(quán)威的測試數(shù)據(jù)[6]。數(shù)據(jù)集中的入侵類型可分為：R2L、DoS、U2R、Probing四類。本文訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)皆為正常數(shù)據(jù)，測試數(shù)據(jù)集通過隨機(jī)無回放的方式采樣得到。本文分別采用基于IG-WFCM算法與基于傳統(tǒng)FCM算法的方法對表1中的5個測試數(shù)據(jù)集進(jìn)行了仿真對比檢測實驗。

表1 測試數(shù)據(jù)集

4.2 實驗結(jié)果

本文模糊加權(quán)系數(shù)m設(shè)置為2，F(xiàn)CM的目標(biāo)函數(shù)收斂誤差為10-5，遺傳算法種群規(guī)模N=30，遺傳迭代終止閾值為10-4，最大遺傳代數(shù)Gmax=100，交叉概率Pc=0.8，變異概率Pm=0.01。圖1為基于IG-WFCM算法和基于FCM算法的檢測率（detection rate）和誤警率（false Positive rate）的對比曲線圖。

圖1 算法檢測率和誤警率對比曲線

通過實驗表明本文的IG-WFCM算法具有可行性，其平均檢測率達(dá)到80.1%，平均誤警率保持為1.605%左右，而FCM算法平均檢測率為56.8%，平均誤警率為2.32%。

5 結(jié)束語

本文提出了基于改進(jìn)遺傳算法的特征加權(quán)模糊聚類算法（IG-WFCM），通過仿真實驗表明，基于IG-WFCM的入侵檢測算法能夠有效地降低誤警率，提高檢測率，對入侵檢測系統(tǒng)性能的提高有一定的意義。

參考文獻(xiàn)：

[1]戴文華.基于遺傳算法的文本分類及聚類研究[M].北京：科學(xué)出版社，2008.

[2]周世兵，徐振源，唐旭清.新的K-均值算法最佳聚類數(shù)確定方法[J].計算機(jī)工程與應(yīng)用，2010，46（16）：27-31.

[3]Maulik U，Bandyopadhyay S.Genetic algorithm-based clustering techn-ique[J].Pattern Recognition.2000，33（9）：1455-1465.

[4]黃敏明，林柏鋼.基于遺傳算法的模糊聚類入侵檢測研究[J].通信學(xué)報，2009，30（11）：140-145.

[5]周鐵軍，李新宇.基于加權(quán)特征的無監(jiān)督模糊聚類入侵檢測研究[J]，湘潭大學(xué)自然科學(xué)學(xué)報，2011，33：01，98-102.

[6]胡昌振.網(wǎng)絡(luò)入侵檢測原理與技術(shù)[M].北京：北京理工大學(xué)出版社，2006.

作者簡介：李新宇（1984-），男，湖南益陽人，湖南第一師范學(xué)院助教，碩士，主要從事網(wǎng)絡(luò)與信息安全，數(shù)字圖像處理研究。