王　廣，張曉明，徐日華

(1.北京化工大學(xué)，北京 100029；2.北京石油化工學(xué)院，北京 102617)

?

基于改進(jìn)差分進(jìn)化的K均值聚類算法在入侵檢測中的研究

王廣1，2，張曉明1，徐日華1，2

(1.北京化工大學(xué)，北京 100029；2.北京石油化工學(xué)院，北京 102617)

針對K均值算法對初始聚類中心需要人為設(shè)定、對聚類中心敏感并且極易陷入局部最優(yōu)的缺陷，用改進(jìn)的DE算法對K均值算法進(jìn)行優(yōu)化。在DE算法中，采用動態(tài)交叉參數(shù)CR與縮放參數(shù)F，有效地平衡了DE算法的全局尋優(yōu)能力與收斂速度二者的矛盾；利用混沌的隨機(jī)性完成DE算法的種群初始化，利用其遍歷性在DE進(jìn)化后期的最優(yōu)解附近進(jìn)行混沌搜索，有效地提高了DE算法的全局尋優(yōu)能力。最后，使用KDD99數(shù)據(jù)集對CDE-K均值算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，CDE-K均值算法具有較好的聚類能力，在檢驗(yàn)效果方面表現(xiàn)優(yōu)秀。

入侵檢測；K均值算法；混沌搜索；DE算法

網(wǎng)絡(luò)安全已成為全社會性問題。迅速、有效地發(fā)掘各種網(wǎng)絡(luò)攻擊行為，保障網(wǎng)絡(luò)系統(tǒng)和資源的安全，對國家安全和人民權(quán)益有著重大的意義[1]。K均值算法是最常用的聚類算法之一，在入侵檢測(IDS)研究中有著廣泛的應(yīng)用[2]。但是此算法有兩方面的缺陷：一是該算法受初始聚類中心的影響較大，聚類結(jié)果很難確定；二是收斂性能較弱，不易獲取全局最優(yōu)解。前人在研究K均值應(yīng)用于IDS時，對K均值算法做了很多種優(yōu)化：模擬退火算法對K均值聚類算法的優(yōu)化[3]；粒子群算法對K均值聚類算法的優(yōu)化[4]；人工魚群算法對K均值聚類算法的優(yōu)化[5]。

差分進(jìn)化算法(DE算法)是20世紀(jì)90年代提出的一種新的進(jìn)化算法。DE算法全局搜索能力比較優(yōu)秀，經(jīng)過這些年的研究，該算法已經(jīng)成功地應(yīng)用在很多領(lǐng)域[6-8]。但該算法也存在著不足：DE進(jìn)化后期很可能跳不出局部最優(yōu)解的范圍；控制參數(shù)的設(shè)置對差分進(jìn)化算法的影響很大。

基于改進(jìn)差分進(jìn)化的K均值聚類算法(CDE-K均值聚類算法)，筆者用改進(jìn)的DE算法對K均值算法進(jìn)行優(yōu)化。有效地提高了DE算法的全局尋優(yōu)能力。

1　CDE-KM聚類算法

1.1混沌

選用的Logistic混沌方程為[9-11]：

(1)

(1)利用混沌的隨機(jī)性初始化DE算法：令tk的初始值分別取m個[0，1]的混沌數(shù)，產(chǎn)生相應(yīng)的向量tk+1=(t1，k+1，…，tj，k+1，…，tm，k+1)，各分量表示為：

(2)

其中，j=1，2，…，m，k=1，2，…，N-1。將產(chǎn)生的混沌變量映射到初始種群個體的分量中：

(3)

(2)DE算法進(jìn)化后期，在其最優(yōu)解Xb正反兩方向上搜索尋優(yōu)：

(4)

式中，α為調(diào)節(jié)參數(shù)。

(5)

其中，β∈rand(0，1)。

1.2DE算法原理

DE算法主要包括變異、交叉和選擇3大操作[9-10]；設(shè)N為種群規(guī)模的大小，D為個體的維數(shù)，tmax為迭代上限，X0表示初始種群：

(6)

變異操作為：

(7)

其中：r1，r2，r3∈{1，2，…，N}，且r1≠r2≠r3；t是當(dāng)前代數(shù)；F是縮放參數(shù)，筆者所用的是一種動態(tài)的縮放參數(shù)F：

(8)

式中：Fmax=0.9；Fmin=0.4；tmax為迭代上限。

交叉操作為：

(9)

其中：j=1，2，…，D；rand()∈[0， 1]；CR為交叉參數(shù)，筆者所用到的是一種動態(tài)的指數(shù)遞增交叉參數(shù)：

(10)

其中：a=30；b=3；CRmin=0.1;CRmax=0.9。

(3)選擇操作為：

(11)

1.3k均值聚類算法

K均值聚類算法描述如下：

(1)隨機(jī)選定K個初始聚類中心；

(2)計(jì)算數(shù)據(jù)點(diǎn)與各聚類中心距離的大小，依據(jù)數(shù)據(jù)點(diǎn)與各中心點(diǎn)距離的大小進(jìn)行聚類。

(3)計(jì)算聚類準(zhǔn)則函數(shù)：

(4)判斷聚類準(zhǔn)則函數(shù)是否收斂，若收斂停止并輸出聚類結(jié)果；否則，重新計(jì)算K個聚類中心，返回(2)重新執(zhí)行，直至收斂。

1.4基于CDE-K均值聚類算法

CED-K均值算法是對個體的聚類中心進(jìn)行實(shí)數(shù)編碼，假設(shè)初始聚類中心的數(shù)目為K，數(shù)據(jù)維數(shù)為d，每個個體就是由K個聚類中心組成，且每個聚類中心是d維的向量，編碼方式如下：

X0i(ci1，ci2，…，ciK)(i=1，2，3，…，N)(12)

采用K均值聚類算法中的類內(nèi)距離作為適應(yīng)度函數(shù)：

(13)

其中：x為聚類中的數(shù)據(jù)樣本；mi為聚類中心。

CDE-K均值聚類算法的整體思路是：用改進(jìn)后的DE算法對K均值算法的初始聚類中心進(jìn)行優(yōu)化選擇，然后用選擇的聚類中心生成K個聚類結(jié)果。CDE-K均值聚類算法的具體流程如下：

(1)讀取數(shù)據(jù)；

(2)通過CED-K均值算法確定K個初始聚類中心：

①設(shè)種群規(guī)模N、種群進(jìn)化代數(shù)t、混沌控制參數(shù)μ以及混沌搜索次數(shù)k。

②混沌初始化種群。

③對初始種群評估個體適應(yīng)度值。找出適應(yīng)度最優(yōu)的Xb;記錄Xb的適應(yīng)度Fb；置t=1。

⑥重復(fù)步驟②～⑤，直到最大迭代次數(shù)。

⑦在DE算法的Xb附近進(jìn)行混沌搜索操作，根據(jù)式(1)、式(2)、式(3)，進(jìn)而得到Xk。

⑧找出Xk中適應(yīng)度最好的個體Xkb，若好于f(xkb)優(yōu)于Fb，令Xb=Xkb，F(xiàn)b=f(Xkb)，輸出Xb和Fb。

(3)計(jì)算每個數(shù)據(jù)點(diǎn)xi與初始聚類中心Zk(I)的距離D(xi，Zk(I))。

(4)滿足D(xi，Zk(I))=min{D(xi，Zi(I))}，則有則xi∈Ck。

(5)計(jì)算新的Zk(I)和

(6)判斷是不是|Jc(I)-Jc(I-1)|<ξ，如果是，算法終止并輸出結(jié)果；否則，I=I+1，重新計(jì)算K個聚類中心，跳轉(zhuǎn)③重新執(zhí)行，直到|Jc(I)-Jc(I-1)|<ξ，輸出結(jié)果。

CDE-K均值聚類算法流程如圖1所示。

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

2.1實(shí)驗(yàn)數(shù)據(jù)描述與處理

為評價CDE-K均值聚類算法在入侵檢測上的測試效果，選用KDD99數(shù)據(jù)集對CDE-K均值聚類算法進(jìn)行實(shí)驗(yàn)。此數(shù)據(jù)集過大，一般選用KDD99的10%訓(xùn)練集，其每條記錄都有41個特征屬性，此外還有最后的標(biāo)記(label)，其主要4大類攻擊分別是Dos、Probe、U2R和R2L[12]。41個特征屬性中除了數(shù)值屬性外，還包含了3種符號屬性，所以，需要對這3種符號屬性進(jìn)行符號轉(zhuǎn)換為數(shù)值的處理，然后再對轉(zhuǎn)換后的數(shù)據(jù)進(jìn)行歸一化處理，具體方式如下：

(13)

其中，yij_max和yij_min分別表示屬性j的最大值和最小值。

通過降低數(shù)據(jù)維數(shù)可以減少算法所用的時間，筆者采用PCA降維法，在保證檢測精度的基礎(chǔ)上對數(shù)據(jù)集進(jìn)行降維處理，并選取前12個主成分作為處理結(jié)果[13]。

2.2結(jié)果與分析

分別用K-均值、PCA降維后的K-均值、CDE-K-均值和PCA降維后的CDE-K-均值聚類算法，在檢測率、誤檢率和檢測時間3個方面得出各子集的檢測結(jié)果并進(jìn)行比較。訓(xùn)練子集與測試子集的選取如表1所示。

表1　訓(xùn)練與測試子集

分別從檢測率、誤報率、檢測時間3個方面進(jìn)行綜合分析。結(jié)果如圖2、圖3所示。

從圖2和3中可以看出，經(jīng)過PCA降維后聚類算法在檢測率和誤檢率上與沒有經(jīng)過PCA降維的結(jié)果相差不大，基本上相似，這也驗(yàn)證了基于PCA特征降維后的數(shù)據(jù)檢測，不僅能夠降低運(yùn)算時間上的開銷，同時還很好地維持了算法的檢測精度和準(zhǔn)確率。經(jīng)過CDE算法改進(jìn)后的K均值算法，比K-均值聚類算法的檢測率提高了約20%，誤檢率降低了30%左右，檢測系統(tǒng)的檢測效果得到了大幅度提升。

4種攻擊類型的檢測率如表2所示，同時與GA-K均值、PSO-K均值應(yīng)用于入侵檢測的結(jié)果進(jìn)行了比較[5]。

表2　4種攻擊類型的檢測率結(jié)果

從表2可知，筆者提出的算法比文獻(xiàn)[5]中所述的2種檢測方法的效果更佳，其平均檢測率為89.41%，對比結(jié)果表明，通過CDE-K均值聚類算法找到的最優(yōu)初始聚類中心和K值，可以克服傳統(tǒng)K均值聚類算法存在的缺陷，進(jìn)一步提高網(wǎng)絡(luò)入侵檢測的能力。

3　結(jié)論

針對K均值算法對初始聚類中心需要人為設(shè)定，對聚類中心敏感并且極易陷入局部最優(yōu)的缺陷，提出一種改進(jìn)的DE算法對K均值算法進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明，CDE-K均值聚類算法較好地改進(jìn)了傳統(tǒng)K-均值算法，提升了網(wǎng)絡(luò)入侵的檢測能力，降低了網(wǎng)絡(luò)入侵檢測時間，具有較佳的檢測能力。

[1]肖立中，劉云翔，陳麗瓊.基于改進(jìn)粒子群的加速K均值算法在入侵檢測中的研究[J].系統(tǒng)仿真學(xué)報，2014，26(8):1652-1657.

[2]Saeed Shahrivari， Saeed Jalili. Single-pass andlinear-timek-均值 clustering based on Map Reduce[J] . Information Systems， 2016，60:1-12.

[3]胡艷維，秦拯，張忠志.基于模擬退火與K均值聚類的入侵檢測算法[J].計(jì)算機(jī)科學(xué)，2010，37(6):122-124.

[4]李永忠，楊鴿，徐靜.基于粒子群優(yōu)化的聚類入侵檢測算法[J].江蘇科技大學(xué)學(xué)(自然科學(xué)版)，2009，23(1):51-55.

[5]袁芳芳.人工魚群和K均值算法相融合的網(wǎng)絡(luò)入侵檢測[J].計(jì)算機(jī)仿真，2013，30(9):274-277.

[6]梅振益，楊慧中.基于差分進(jìn)化模糊聚類的多模型建模[J].計(jì)算機(jī)與應(yīng)用化學(xué)，2011，28(3):291-294.

[7]Sudhakar G. Effective image clustering with differential evolution technique[J]. International Journal of Computer and Communication Technology， 2010，2(1):11-19.

[8]Edwin C Shi， Frank H F. Leung Differential Evolution with Adaptive Population Size[C]. Proceedings of the 19th International Conference on Digital Signal Processing, 2014:876-881.

[9]高平，毛力，宋益春.基于改進(jìn)差分進(jìn)化的K-均值聚類算法[J].電腦知識與技術(shù)，2013，9(22):5064-5067.

[10]Guo Zhenyu， Bai Zhifeng， Cao Binggang. Chaotic Immune Differential Evolution Algorithm[C]∥Proceedings of the 2007 IEEE International Conference on Robotics and Biomimetics, 2007:15-18.

[11]Yan PEI. A Chaotic Ergodicity Based Evolutionary Computation Algorithm[C]. 2013 Ninth International Conference on Natural Computation， 2013:454-459.

[12]張新有，曾華燊，賈磊.入侵檢測數(shù)據(jù)集KDD CUP99 研究[J] .計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(22):4809-4816.

[13]王曉霞，孫德才，唐耀庚.改進(jìn)的入侵檢測數(shù)據(jù)降維方法[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47(25):85-88.

Research on K Mean Clustering Algorithm Based on Improved DEAlgorithm in Intrusion Detection

WANG Guang1，2， ZHANG Xiao-ming2， XU Ri-hua1，2

(1.College of Information Science and Technology， Beijing University of Chemical Technology， Beijing 100029， China; 2.School of Information Engineering， Beijing Institute of Petro-Chemical Technology， Beijing 102617， China)

While using theKalgorithm, the mean value ofK-means to the preliminary cluster center needs tobe set artificially, and the cluster center is sensitive, whicheasily leadsto thedefect ofpartial optimum.The researchers adopt the improved DE algorithm to optimizeKalgorithm. Using dynamic cross parameters of CR and the scaling parameter F, can effectively balance the general searching capacity and constriction speed. The chaos randomly completethe population initialization of DE algorithm and reuse characteristics of the ergodicity of the near optimal DEindividuals in chaotic search, which can effectively improve the DEalgorithm with global searching ability. Finally, the KDD99 data set is used to verify the optimization of the K algorithm. The results indicate that the CDE-KM has better clustering capacity and good performance in terms of test results.

intrusion detection;Kalgorithm; chaotic search; DE algorithm

2016-04-24

王廣(1988—)，男，碩士研究生為研究方向 信息安全，E-mail:13811710921@163.com。

TP37

A