一種改進(jìn)的K-means算法在異常檢測(cè)中的應(yīng)用

陳　莊，羅告成（重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶400054）

一種改進(jìn)的K-means算法在異常檢測(cè)中的應(yīng)用

陳莊，羅告成
（重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶400054）

為提高K-means聚類算法在異常檢測(cè)中的效果，給出一種改進(jìn)的K-means聚類算法?；谧畲缶嚯x選取初始聚類中心，并引入信息熵計(jì)算各個(gè)屬性的權(quán)重，用改進(jìn)后的加權(quán)歐氏距離公式計(jì)算數(shù)據(jù)集中樣本點(diǎn)間的距離。選取KDD CUP99數(shù)據(jù)集測(cè)試算法的性能。實(shí)驗(yàn)結(jié)果表明，本算法有助于提高異常檢測(cè)的檢測(cè)率和降低誤報(bào)率。

異常檢測(cè)；數(shù)據(jù)挖掘；K-mean聚類算法；初始聚類中心；加權(quán)歐式距離

入侵檢測(cè)是一種保護(hù)計(jì)算機(jī)和網(wǎng)絡(luò)的主動(dòng)防御策略，異常檢測(cè)則是入侵檢測(cè)的重要組成部分。將數(shù)據(jù)挖掘技術(shù)應(yīng)用到異常檢測(cè)領(lǐng)域，從海量數(shù)據(jù)中提取網(wǎng)絡(luò)正常行為模式，有助于解決傳統(tǒng)的基于誤用檢測(cè)的入侵檢測(cè)系統(tǒng)檢測(cè)率低和誤報(bào)率高的問(wèn)題。

異常檢測(cè)方法構(gòu)建正常行為模式時(shí)基于以下兩個(gè)前提［1］：①網(wǎng)絡(luò)中正常數(shù)據(jù)的數(shù)量遠(yuǎn)大于入侵?jǐn)?shù)據(jù)；②入侵?jǐn)?shù)據(jù)與正常數(shù)據(jù)之間存在很大的差異。

本文將信息熵理論引入無(wú)監(jiān)督的聚類算法，提出一種相似度計(jì)算和初始聚類中心選擇都更為優(yōu)化的K-means聚類算法應(yīng)用于異常檢測(cè)。該方法首先過(guò)濾數(shù)據(jù)集中的離群點(diǎn)或孤立點(diǎn)，以減少這些點(diǎn)對(duì)聚類的負(fù)面影響；其次使用一種基于最大距離選取的方法選擇初始聚類中心，同時(shí)引入信息熵的方法定義一種屬性加權(quán)的歐式距離，并將此加權(quán)歐式距離應(yīng)用到整個(gè)聚類的相似度計(jì)算中；之后進(jìn)行迭代計(jì)算，并將記錄劃分到不同的聚類中。本文使用KDD CUP 99數(shù)據(jù)集來(lái)測(cè)試算法的性能。結(jié)果表明，此方法具有較高的檢測(cè)率和較低的誤報(bào)率，達(dá)到了預(yù)期的目標(biāo)。

1　聚類算法應(yīng)用于異常檢測(cè)相關(guān)研究

異常檢測(cè)作為當(dāng)前入侵檢測(cè)研究領(lǐng)域的熱點(diǎn)，其普遍的思想是以大量的審計(jì)數(shù)據(jù)為背景來(lái)刻畫系統(tǒng)或用戶的正常使用模式，建立正?；顒?dòng)模型，然后通過(guò)檢查當(dāng)前活動(dòng)和正常模型之間的偏離度來(lái)確認(rèn)入侵行為［2］。數(shù)據(jù)挖掘中的聚類算法便是基于以上思想的典型算法。為更好地發(fā)現(xiàn)網(wǎng)絡(luò)攻擊行為，相關(guān)研究人員提出了很多改進(jìn)的方法［3-4］。而在聚類算法中，對(duì)K-means算法的改進(jìn)研究最為廣泛。

在算法結(jié)合方面，文獻(xiàn)［5］結(jié)合K-means算法和Apriori算法的優(yōu)點(diǎn)，提出一種混合入侵檢測(cè)模型；文獻(xiàn)［6］將模擬退火算法和聚類算法相結(jié)合對(duì)聚類算法進(jìn)行優(yōu)化；文獻(xiàn)［7］將K-means算法與分支界定算法結(jié)合建立網(wǎng)絡(luò)異常檢測(cè)模型。這些研究提升了K-means算法檢測(cè)的精度，但結(jié)合后的算法較為復(fù)雜，在實(shí)際應(yīng)用中具有一定的局限性。在對(duì)K-means算法本身的優(yōu)化方面，為克服傳統(tǒng)K-means聚類算法對(duì)初始聚類中心選擇敏感的問(wèn)題，文獻(xiàn)［8］提出基于一種動(dòng)態(tài)迭代過(guò)程計(jì)算K-means聚類中心的算法（MDKM），文獻(xiàn)［9］提出基于數(shù)據(jù)樣本分布選取初始聚類中心的算法。這些研究分別從不同角度對(duì)初始聚類中心的選擇進(jìn)行了優(yōu)化，取得了一定的效果。然而無(wú)論是否將K-means算法與其他算法相結(jié)合，以上研究均未考慮數(shù)據(jù)中各維屬性對(duì)聚類的影響。將K-means算法運(yùn)用于異常檢測(cè)，考慮數(shù)據(jù)集中各特征屬性對(duì)聚類的不同貢獻(xiàn)是非常有意義的［10-11］。

本文在考慮初始聚類中心的選擇對(duì)聚類的過(guò)程及結(jié)果有重大影響的同時(shí)，也權(quán)衡了數(shù)據(jù)對(duì)象中各個(gè)屬性對(duì)聚類所發(fā)揮的作用，提出一種基于最大距離選擇初始聚類中心并結(jié)合信息熵屬性加權(quán)距離公式計(jì)算數(shù)據(jù)對(duì)象間距離的改進(jìn)K-means聚類算法，并將其應(yīng)用于異常檢測(cè)中。

2　算法相關(guān)定義與運(yùn)算

2.1信息熵屬性權(quán)值引入及加權(quán)歐氏距離計(jì)算

傳統(tǒng)K-means算法隨機(jī)選取初始聚類中心，并未考慮數(shù)據(jù)對(duì)象的各個(gè)屬性對(duì)聚類效果的作用是不一樣的，這會(huì)導(dǎo)致算法難以獲得穩(wěn)定且精確的聚類效果。

通常，信息論中的熵被用來(lái)衡量一個(gè)事物的“有序”程度。事物信息熵值越大，表明它所處的狀態(tài)越穩(wěn)定；相反，信息熵的值越小，表明事物所處的狀態(tài)越無(wú)序［12］?；谶@一點(diǎn)，本文將信息熵的方法引入到聚類方法中，根據(jù)各屬性的變動(dòng)程度，通過(guò)計(jì)算信息熵給出各屬性的權(quán)重，為數(shù)據(jù)對(duì)象根據(jù)屬性更好地聚類提供支持。

使用信息熵值法計(jì)算屬性權(quán)重的過(guò)程如下［13］：

1）設(shè)待聚類的數(shù)據(jù)集A由n個(gè)m維的數(shù)據(jù)對(duì)象構(gòu)成，于是構(gòu)造屬性值矩陣：

A中第i個(gè)數(shù)據(jù)對(duì)象表示為ai=（xi1，xi2，…，xij，…，xim），xij表示數(shù)據(jù)集中第i個(gè)數(shù)據(jù)對(duì)象第j維屬性的取值。i=1，2，…，n；j=1，2，…，m。

2）計(jì)算第i個(gè)數(shù)據(jù)對(duì)象的第j維屬性值的比重：

3）計(jì)算第j維屬性信息熵：

其中：Ej是屬性j的熵值；p=1/ln n。

4）計(jì)算第j維屬性值的波動(dòng)系數(shù)：qj=1-Ej。Ej越大，說(shuō)明數(shù)據(jù)集A中n個(gè)數(shù)據(jù)對(duì)象的第j維屬性所有取值情況差異越小，則該屬性的聚類作用越??；反之，Ej越小，第j維屬性取值情況差異越大，則該屬性的聚類作用越大；當(dāng)?shù)趈維屬性都取相同值時(shí)，Ej=1，此時(shí)該屬性的聚類作用為0。綜上所述，qj越大則說(shuō)明屬性越重要。

5）計(jì)算各維屬性的權(quán)重：

其中：0≤wj≤1j=1，j=1，2，…，m。

在計(jì)算出各維屬性的權(quán)重之后，給出賦權(quán)歐式距離的計(jì)算公式。假設(shè)數(shù)據(jù)集A有m個(gè)屬性，則兩個(gè)樣本點(diǎn)a與b之間的加權(quán)歐式距離為

其中xaj和xbj分別表示數(shù)據(jù)對(duì)象a和b對(duì)應(yīng)的第j個(gè)屬性值。

2.2基于最大距離選擇初始聚類中心

考慮到距離大的樣本點(diǎn)分到同一個(gè)簇的可能性小，距離小的樣本點(diǎn)分到同一個(gè)簇的可能性大［14］，提出基于最大距離選擇初始聚類中心的方法。該方法首先計(jì)算樣本數(shù)據(jù)集中n個(gè)樣本點(diǎn)兩兩之間的距離，并將距離最遠(yuǎn)的兩個(gè)樣本點(diǎn)作為初始聚類中心。在剩余的n-2個(gè)樣本點(diǎn)中，選取到這兩個(gè)樣本點(diǎn)各自距離乘積最大值的樣本點(diǎn)作為第3個(gè)初始聚類中心。同樣，在剩余的n-3個(gè)樣本點(diǎn)中選取到前3個(gè)初始聚類中心各自距離乘積最大值的樣本點(diǎn)作為第4個(gè)初始聚類中心。依次類推，直到找到k個(gè)初始聚類中心。具體過(guò)程如下：

1）計(jì)算n個(gè)樣本點(diǎn)兩兩之間的距離dw（di，dj），找到滿足條件｛dw（d1，d2）≥dw（di，dj），（i，j= 1，2，…，n）｝的兩個(gè)樣本點(diǎn)d1，d2，并將它們作為兩個(gè)初始聚類中心。

2）在剩余的n-2個(gè)樣本點(diǎn)中，選取滿足dw（d1，d3）×dw（d2，d3）≥dw（d1，di）×dw（d2，d1）｝的點(diǎn)作為第3個(gè)初始聚類中心，其中di是除d1，d2，d3外的任意一個(gè)樣本點(diǎn)。

3）在剩余的n-3個(gè)樣本點(diǎn)中，選取滿足｛dw（d1，d4）×dw（d2，d4）×dw（d3，d4）≥dw（d1，di）×dw（d2，di）×dw（d3，di）｝的點(diǎn)作為第4個(gè)初始聚類中心，其中di是除d1，d2，d3，d4外的任意一個(gè)樣本點(diǎn)；

4）依次類推，直到找出數(shù)據(jù)集中剩余的k-4個(gè)初始聚類中心。

1.5 統(tǒng)計(jì)學(xué)處理 采用SPSS18.0軟件進(jìn)行數(shù)據(jù)分析。計(jì)數(shù)資料用百分率表示，比較采用χ2檢驗(yàn)，以P<0.05為差異有統(tǒng)計(jì)學(xué)意義。

3　改進(jìn)算法介紹及分析

結(jié)合以上研究，給出改進(jìn)的K-means聚類算法步驟：

1）確定初始聚類中心個(gè)數(shù)k。

2）根據(jù)式（3）計(jì)算數(shù)據(jù)集A中各個(gè)屬性的權(quán)重。

3）根據(jù)式（4）計(jì)算樣本點(diǎn)之間的距離。

4）基于最大距離選擇初始聚類中心。

5）迭代計(jì)算，將所有記錄分類到k個(gè)不同簇中。一直迭代，直到簇心的移動(dòng)距離小于某個(gè)給定的閾值為止。

改進(jìn)后的K-means算法流程如圖1所示。

圖1　改進(jìn)后的K-means算法流程

另外，考慮到異常檢測(cè)中描述一個(gè)數(shù)據(jù)樣本的特征屬性以連續(xù)型數(shù)值為主，例如數(shù)據(jù)包的報(bào)文長(zhǎng)度、數(shù)據(jù)包生存期、TCP窗口大小、UDP數(shù)據(jù)報(bào)長(zhǎng)度等，所以本文的改進(jìn)算法以數(shù)據(jù)集A的數(shù)據(jù)對(duì)象各屬性均為連續(xù)型數(shù)值為前提。

4　實(shí)驗(yàn)結(jié)果與分析

本文將傳統(tǒng)K-means算法與改進(jìn)的算法進(jìn)行對(duì)比實(shí)驗(yàn)，以驗(yàn)證算法的效果。實(shí)驗(yàn)使用KDD CUP99數(shù)據(jù)集。KDD CUP99數(shù)據(jù)集是目前主要的入侵檢測(cè)方法測(cè)評(píng)樣本庫(kù)之一［15］，針對(duì)入侵檢測(cè)算法研究的文章大多采用這一數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。本數(shù)據(jù)集包括4 898 431條記錄，每條記錄都被標(biāo)記為正?；虍惓?，其中異常記錄3 925 650條，包含22種攻擊類型。這22種攻擊類型可以分為DOS攻擊、R2L攻擊、U2R攻擊及probing攻擊四大類。

KDD CUP99數(shù)據(jù)集中的樣本由41個(gè)特征屬性來(lái)描述。其中7個(gè)離散值屬性在實(shí)驗(yàn)中被忽略，剩余34個(gè)連續(xù)型數(shù)值屬性作為判斷樣本數(shù)據(jù)是否異常的依據(jù)。

為評(píng)估算法的準(zhǔn)確性，本文選擇以下兩個(gè)指標(biāo)：檢測(cè)率和誤報(bào)率。檢測(cè)率等于正確檢測(cè)出為異常記錄的數(shù)目與總的異常記錄數(shù)目之比；誤報(bào)率等于檢測(cè)出為異常但實(shí)際為正常記錄的數(shù)目與總的正常記錄數(shù)目之比。

首先選擇只包含DOS攻擊的樣本數(shù)據(jù)集，在聚類中心k取不同數(shù)值的情況下測(cè)試算法，與傳統(tǒng)的K-means算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1　不同k值情況下檢測(cè)DOS攻擊對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)結(jié)果表明：改進(jìn)后的K-means算法在檢測(cè)DOS攻擊時(shí)比傳統(tǒng)的K-means算法具有更高的檢測(cè)率和更低的誤報(bào)率。

為全面驗(yàn)證算法的有效性，實(shí)驗(yàn)的另一部分是在確定聚類中心k=50的情況下，選擇不同類型的攻擊樣本數(shù)據(jù)集進(jìn)行測(cè)試。從KDD CUP99數(shù)據(jù)集中選擇的不同攻擊類型為neptune，buffer_ overflow，guess_password及portsweep四類典型攻擊。與傳統(tǒng)K-means算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2　相同k值情況下檢測(cè)不同攻擊對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)結(jié)果表明：在聚類中心k值確定的情況下檢測(cè)不同類型的攻擊時(shí)，改進(jìn)后的K-means算法在檢測(cè)率和誤報(bào)率方面效果好于傳統(tǒng)的K-means算法。

5　結(jié)束語(yǔ)

將數(shù)據(jù)挖掘中的聚類思想運(yùn)用于異常檢測(cè)是數(shù)據(jù)挖掘技術(shù)在入侵檢測(cè)中的一個(gè)重要應(yīng)用。K-means聚類算法是異常檢測(cè)中常用到的方法，它能很好地提高異常檢測(cè)的檢測(cè)率，并降低誤報(bào)率。本文針對(duì)傳統(tǒng)K-means算法的不足，提出了兩點(diǎn)改進(jìn)：一是考慮到初始聚類中心的選擇對(duì)聚類效果有重大影響，提出基于最大距離選取初始聚類中心；二是考慮到數(shù)據(jù)對(duì)象各個(gè)屬性對(duì)聚類效果發(fā)揮的作用不同，通過(guò)引入信息熵知識(shí)計(jì)算各數(shù)據(jù)屬性的權(quán)值，并在聚類過(guò)程中使用賦權(quán)歐式距離來(lái)計(jì)算相似度。通過(guò)以上兩點(diǎn)的改進(jìn)，既克服了傳統(tǒng)K-means算法選擇初始聚類中心的隨機(jī)性，又權(quán)衡了數(shù)據(jù)對(duì)象各個(gè)屬性在聚類過(guò)程中所起作用的差異性，得到了更好的聚類效果。

本文使用KDD CUP99數(shù)據(jù)集測(cè)試算法的性能。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的K-means算法與傳統(tǒng)的K-means算法相比，具有更高的檢測(cè)率和更低的誤報(bào)率，達(dá)到了預(yù)期的目標(biāo)。算法的不足之處是聚類中心k值的確定需要經(jīng)過(guò)多次嘗試才能找到一個(gè)合適的范圍，并且改進(jìn)后的算法計(jì)算量較大。如何更有效地確定k值并減少算法的計(jì)算量是下一步研究的重點(diǎn)。

［1］劉濤，馬曉宇，胡景.一種K-means算法在網(wǎng)絡(luò)異常檢測(cè)中的應(yīng)用［J］.微電子學(xué)與計(jì)算機(jī)，2012，29（5）：42 -45.

［2］蘇艷君，沈剛，劉昕.基于網(wǎng)絡(luò)聚合行為的異常檢測(cè)方法研究［J］.計(jì)算機(jī)工程與科學(xué)，2010，3（32）：38-41.

［3］袁遇晴，況湘玲，凌利軍.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測(cè)研究［J］.計(jì)算機(jī)安全，2014，7（17）：14-17.

［4］梁飛，閆宏印.基于聚類分析的動(dòng)態(tài)自適應(yīng)入侵檢測(cè)模式研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（3）：814 -820.

［5］Zhao Yanjun.Realization of Intrusion Detection System Based on the Improved Data Mining Technology［C］// 2013 International Conference on Computer Science and Education.Colombo USA：［s.n.］，2013：982-987.

［6］胡艷維，秦拯，張忠志.基于模擬退火與K均值聚類的入侵檢測(cè)算法［J］.計(jì)算機(jī)科學(xué)，2010，6（6）：122 -124.

［7］楊宇舟，張鳳荔，王勇.基于K-means聚類的分支界定算法在網(wǎng)絡(luò)異常檢測(cè)中的應(yīng)用［J］.計(jì)算機(jī)科學(xué)，2012，4（39）：60-63.

［8］Li Han.Using a Dynamic K-means Algorithm to Detect Anomaly Activities［C］//2011 International Conference on Computational Intelligence and Security.Sanya China：［s.n.］，2011：1049-1052.

［9］仝雪嬌，孟凡榮，王志曉.對(duì)K-means初始聚類中心的優(yōu)化［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，1（32）：2718 -2724.

［10］于海濤，賈美娟，王慧強(qiáng).基于人工魚群的優(yōu)化K-means聚類算法［J］.計(jì)算機(jī)科學(xué)，2012，12（39）：60 -64.

［11］許曉東，楊燕，李剛.基于K-means聚類的網(wǎng)絡(luò)流量異常檢測(cè)［J］.無(wú)線通信技術(shù)，2013，4（1）：21-26.

［12］孟洋，趙方.基于信息熵理論的動(dòng)態(tài)規(guī)劃特征選取算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（17）：3879-3881.

［13］原福永，張曉彩，羅思標(biāo).基于信息熵的精確屬性賦權(quán)K-means聚類算法［J］.計(jì)算機(jī)應(yīng)用，2011，31（6）：1675 -1678.

［14］翟東海，魚江，高飛.最大距離法選取初始簇中心的K-means文本聚類算法的研究［J］.計(jì)算機(jī)應(yīng)用研究，2014，31（3）：713-716.

［15］唐菀，馬杰，曾廣平.評(píng)測(cè)智能化入侵檢測(cè)方法的樣本庫(kù)分析［J］.中南民族大學(xué)學(xué)報(bào)，2010，29（2）：84-87.

（責(zé)任編輯楊黎麗）

Improved K-M eans A lgorithm Using in Anomaly Detection

CHEN Zhuang，LUO Gao-cheng
（College of Computer Science and Engineering，Chongqing University of Technology，Chongqing 400054，China）

In order to increase the performance of the K-means algorithm in anomaly detection，an improved K-means algorithm was proposed.The algorithm selected the initial cluster centers according tomaximum distance，and the information entropy was introduced to calculate the weight of every attribute，and then the improved weighted Euclidean distance formulawas used to calculate the distance between sample points in dataset.The performance of the improved algorithm was tested by KDD CUP99 dataset.The experimental results show that thisalgorithm will be helpful to increase the detection rate and decrease the false alarm rate in anomaly detection.

anomaly detection；datamining；K-means；initial clustering centers；weighted Euclidean distance

TP305

A

1674-8425（2015）05-0066-05

10.3969/j.issn.1674-8425（z）.2015.05.012

2015-03-06

信息安全國(guó)家標(biāo)準(zhǔn)項(xiàng)目（2013bzyj—WG5—002）

陳莊（1964—），男，博士，教授，主要從事企業(yè)信息化管理、網(wǎng)絡(luò)與信息安全研究。

陳莊，羅告成.一種改進(jìn)的K-means算法在異常檢測(cè)中的應(yīng)用［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2015（5）：66-70.

format：CHEN Zhuang，LUO Gao-cheng.Improved K-Means Algorithm Using in Anomaly Detection［J］.Journal of Chongqing University of Technology：Natural Science，2015（5）：66-70.