組合聚類算法在異常檢測(cè)中的應(yīng)用研究

盧揚(yáng)

摘要：該文結(jié)合當(dāng)前網(wǎng)絡(luò)異常檢測(cè)的要求，在分析以往算法不足的基礎(chǔ)上，提出了一種組合聚類算法，并應(yīng)用到異常檢測(cè)中。該算法先后使用蟻群聚類算法和K-means算法對(duì)數(shù)據(jù)進(jìn)行聚類。通過兩種聚類算法的有效組合，解決了原有聚類算法聚類結(jié)果受初始聚類中心選取的影響，實(shí)驗(yàn)證明該算法在保證較低誤報(bào)率水平的前提下，提高了系統(tǒng)的的檢測(cè)率。

關(guān)鍵詞：入侵檢測(cè)；異常檢測(cè)；聚類分析；K-means算法；蟻群算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）33-8010-04

近年來隨著Internet的快速發(fā)展，眾多信息利用網(wǎng)絡(luò)平臺(tái)進(jìn)行傳輸存儲(chǔ)，隨之而來的信息安全問題亦日顯突出。入侵檢測(cè)技術(shù)因能及時(shí)發(fā)現(xiàn)并報(bào)告系統(tǒng)中未授權(quán)或異?，F(xiàn)象，越來越多的被用于動(dòng)態(tài)檢測(cè)網(wǎng)絡(luò)，確保網(wǎng)絡(luò)安全。入侵檢測(cè)主要有誤用檢測(cè)和異常檢測(cè)兩種方法。異常檢測(cè)是一種基于行為的檢測(cè)，通過將過去觀察到的正常行為與受到攻擊時(shí)的行為相比較，根據(jù)使用者的異常行為或資源的異常使用狀況來判斷是否發(fā)生入侵活動(dòng)。美國哥倫比亞大學(xué)WenkeLee教授最早提出將數(shù)據(jù)挖掘技術(shù)應(yīng)用到入侵檢測(cè)系統(tǒng)中。國內(nèi)向繼等人將聚類算法應(yīng)用到異常檢測(cè)中。目前，通過對(duì)各類聚類算法在異常檢測(cè)應(yīng)用中的改進(jìn)，可以檢測(cè)出不同攻擊類型，從而大大提高系統(tǒng)的檢測(cè)率，因此該工作已成為入侵檢測(cè)領(lǐng)域研究的一大熱點(diǎn)。

該文結(jié)合當(dāng)前網(wǎng)絡(luò)異常檢測(cè)的要求，在分析以往算法不足的基礎(chǔ)上，提出了一種組合聚類算法，并應(yīng)用到異常檢測(cè)中，以提高系統(tǒng)的檢測(cè)性能。

1聚類算法介紹

聚類分析能發(fā)現(xiàn)新型的和未知的入侵類型，它是一種無監(jiān)督的學(xué)習(xí)方法，其將一些未知模式分成若干類，若特征向量之間的距離在一定誤差范圍內(nèi)相等，則認(rèn)為它們是同一類型。下面將介紹入侵檢測(cè)中兩種常見的聚類算法。

1.1基于K-means的聚類算法

K-means算法是由MacQueen提出的一種經(jīng)典的聚類算法。其算法思想是通過迭代過程將數(shù)據(jù)集劃分為不同的類別，使得評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立。算法首先從n個(gè)數(shù)據(jù)對(duì)象任意選擇K個(gè)對(duì)象作為初始聚類中心；剩下其它對(duì)象根據(jù)它們與這些聚類中心的距離，分別將它們歸類最相似的簇中；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對(duì)象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測(cè)度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測(cè)度函數(shù)該算法使用誤差平方和準(zhǔn)側(cè)函數(shù)來評(píng)價(jià)聚類的性能。假設(shè)X包含K個(gè)聚類子集X1，X2，…，Xk；則誤差平方和[E=i=1kp∈Xip-mi2]準(zhǔn)則函數(shù)公式為：

E表示所有數(shù)據(jù)的均方差之和，P為對(duì)象中的一個(gè)點(diǎn)，mi為聚類中心值。各個(gè)聚類自己種的樣本數(shù)量分別為n1，n2，…，nk各個(gè)聚類子集的平均值代表點(diǎn)分別是m1，m2，…，mk。

數(shù)據(jù)與聚類中心的距離由歐式距離公式計(jì)算而得。樣本Xi與Xj之間的歐式距離公式為：

1.2基于蟻群的聚類算法

蟻群聚類算法是蟻群在覓食過程中，螞蟻依據(jù)一定的概率選擇覓食路徑原理研究而得出的一種智能算法。研究發(fā)現(xiàn)，螞蟻在此過程中，會(huì)在所經(jīng)過的路徑上不斷釋放一種信息素用于和其他螞蟻進(jìn)行信息的傳遞，這種物質(zhì)能夠被同類感知，并指導(dǎo)同類選擇運(yùn)動(dòng)方向，因此有大量螞蟻組成的蟻群集體行為便呈現(xiàn)出一種信息正反饋現(xiàn)象，即某一路經(jīng)上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。在整個(gè)覓食尋徑中，由于信息素的作用使得整個(gè)蟻群集體的行為具有了很高的自組性。因此，在入侵檢測(cè)中，可以將檢測(cè)數(shù)據(jù)視作螞蟻，而聚類中心就是螞蟻所要尋找的食物源。

設(shè)X={Xi|X=（xi1，xi2，…，xin），i=1，2，…，n}是待聚類的數(shù)據(jù)集合；[vj]為聚類中心；預(yù)設(shè)聚類半徑為R，統(tǒng)計(jì)誤差為[ε]，信息數(shù)量為[τij]。

t時(shí)刻，數(shù)據(jù)Xi到[vj]路徑上的殘留的信息素[τij]（t）為：當(dāng)[dij]<=R時(shí)[τij]（t） =1；當(dāng)[dij]>=R，[τij]（t）=0。其中[dij]表示數(shù)據(jù)Xi到[vj]之間的歐式距離。

t時(shí)刻，數(shù)據(jù)Xi是否屬于聚類中心的概率計(jì)算方式為：[pij（t）=ταij（t）ηβij（t）s∈Sταsj（t）ηβij（t）]

其中S={Xs|[dsj]<=R，s=1，2，…，n}，它表示分布在聚類中心[vj]內(nèi)的數(shù)據(jù)集合。[ηij]為1/[dij]，[α，β]是為了防止數(shù)據(jù)的沿相同路徑得到相同聚類造成停滯搜索結(jié)果而設(shè)置的調(diào)節(jié)因子，

令VSj={Xk|[dkj]<=R，s=1，2，…，j}，式中VSj表示Vj 中的數(shù)據(jù)集合，j為Vj中的數(shù)據(jù)個(gè)數(shù)。那么理想的聚類中心由[v-=1jk=1jXk]公式計(jì)算得出。其中[Xk∈VSj]。

計(jì)算每個(gè)聚類的偏離誤差公式為[εj=k=1ji=1m（xki-xji）2]，所有聚類的總偏差[ε=j=1kεj]

該算法具體描述：

2組合聚類算法的研究與實(shí)現(xiàn)

2.1組合聚類算法的研究

在該文所提到兩種聚類算法中，K-means算法是數(shù)據(jù)挖掘中一種經(jīng)典的劃分聚類算法。它具有簡單且收斂速度快的特點(diǎn)。其缺點(diǎn)在于聚類結(jié)果與初始聚類中心的選擇有較大關(guān)系，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果。與此相比，遺傳聚類算法的優(yōu)勢(shì)主要體現(xiàn)在其具有自組織、可伸縮性、魯棒性等特性，但自身易出現(xiàn)早熟停滯的現(xiàn)象。由于現(xiàn)在網(wǎng)絡(luò)中攻擊方法呈現(xiàn)出多樣化，且檢測(cè)環(huán)境也在不斷發(fā)生變化；而聚類算法都存在著自身的缺點(diǎn)，單一采用某種算法進(jìn)行入侵檢測(cè)，有一定的局限性，會(huì)影響檢測(cè)效果?；谏鲜銮闆r，該文提出了一種組合聚類算法，將以上提供的兩種算法應(yīng)用到適合自己特點(diǎn)的挖掘步驟中，以達(dá)到提高入侵檢測(cè)系統(tǒng)檢測(cè)效果的目的。該算法可以分為兩步。第一步：蟻群聚類算法的聚類過程。為了克服K-means對(duì)聚類中心以及聚類的數(shù)目有著比較強(qiáng)的依賴性的缺點(diǎn)，首先采用傳統(tǒng)的蟻群聚類算法進(jìn)行聚類。將初始化后數(shù)據(jù)作為不同屬性的螞蟻，螞蟻所要尋找的食物源表示為聚類中心。利用蟻群聚類算法有較強(qiáng)的魯棒性，能夠得到比較優(yōu)越滿足精度條件聚類結(jié)果的特點(diǎn)，得到相對(duì)可靠的聚類個(gè)數(shù)和聚類中心。第二步：K-means算法的聚類參數(shù)更新過程。將第一步得到的聚類結(jié)果作為此階段的初始值，這樣既克服K-means對(duì)聚類算法對(duì)初始聚類中心的要求的缺點(diǎn)，又能結(jié)合了其動(dòng)態(tài)的搜索自適應(yīng)特點(diǎn)，從而使得聚類結(jié)果更加合理可靠。

2.2組合聚類算法實(shí)現(xiàn)流程

聚類算法的挖掘過程可以概括為：初始化階段、聚類算法實(shí)現(xiàn)階段、聚類結(jié)果的輸出階段。

該組合聚類算法的流程描述如下：

1）組合聚類算法的參數(shù)初始化階段

① 設(shè)置聚類包含的最小數(shù)據(jù)對(duì)象個(gè)數(shù)K，[α]，[β]，預(yù)設(shè)聚類半徑R，初始概率P0、初始統(tǒng)計(jì)誤差[ε0]等。

② 數(shù)據(jù)預(yù)處理，既選取數(shù)據(jù)中適當(dāng)?shù)膶傩圆⑦M(jìn)行標(biāo)準(zhǔn)化。

③ 將待聚類的數(shù)據(jù)對(duì)象隨機(jī)分布于二維區(qū)域中，賦予其一對(duì)坐標(biāo)（[xi，yi]），其中[xi和yi]均屬于整個(gè)對(duì)象集合所在區(qū)域，i=1，2，…，n。

2）組合聚類算法實(shí)現(xiàn)階段

①蟻群聚類算法的聚類過程

a）設(shè)置所有螞蟻初始狀態(tài)值，選取K個(gè)螞蟻放置在預(yù)先設(shè)置的K個(gè)聚類的聚類中心上。

b） 計(jì)算每個(gè)聚類中心的平均值和轉(zhuǎn)移概率，并完成歸類。

c） 計(jì)算每類聚類的偏離誤差和所有聚類總偏差，更新聚類中心和信息素。

d） 程序直至總偏差小于等于初始偏差結(jié)束。

②利用K-means算法聚類，更新優(yōu)化聚類結(jié)果

a） 將遺傳算法獲得的聚類中心作為K-means算法的初始聚類中心。

b） 以數(shù)據(jù)與聚類中心值的距離最近為標(biāo)準(zhǔn)，對(duì)每個(gè)數(shù)據(jù)進(jìn)行聚類劃分。

c） 通過K-means算法中定義的目標(biāo)函數(shù)的再聚類，迭代優(yōu)化，更新聚類中心值，直到聚類劃分不再發(fā)生變化。

3）組合聚類算法聚類結(jié)果輸出。

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

為了評(píng)價(jià)組合聚類算法應(yīng)用到異常檢測(cè)中的效率，選用目前入侵檢測(cè)領(lǐng)域比較權(quán)威KDDCUP1999網(wǎng)絡(luò)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)，可從http：//kdd.ics.uci.edu下載。實(shí)驗(yàn)平臺(tái)基本配置為Intel PentiumDual–Core的CPU，2GB內(nèi)存；Windows2000的操作系統(tǒng)，VC++6.0編程語言。

在仿真試驗(yàn)中，從KDDCUP1999數(shù)據(jù)集中隨機(jī)選取5組具有2100個(gè)數(shù)據(jù)的樣本集，其中包含2000個(gè)正常連接記錄和100個(gè)異常連接記錄。為了便于觀察實(shí)驗(yàn)結(jié)果進(jìn)行分析，在表1中匯總了蟻群、K-means和組合聚類算法三種算法的五組實(shí)驗(yàn)數(shù)據(jù)。該實(shí)驗(yàn)數(shù)據(jù)中列出了檢測(cè)到的異常事件個(gè)數(shù)、漏報(bào)事件個(gè)數(shù)、誤報(bào)事件個(gè)數(shù)，并對(duì)檢測(cè)率、漏報(bào)率、誤報(bào)率和檢測(cè)正確率進(jìn)行了統(tǒng)計(jì)。

通過上述實(shí)驗(yàn)結(jié)果可知，組合聚類算法的平均檢測(cè)率為78.40%和誤報(bào)率為0.64%。與單一算法檢測(cè)結(jié)果相比，檢測(cè)率有了明顯提高，而誤報(bào)率也保持在較低的水平，這充分說明了該組合算法實(shí)現(xiàn)了聚類的優(yōu)化。

4結(jié)束語

該文提出了一種組合聚類算法并應(yīng)用到異常檢測(cè)中。該算法先后使用了蟻群聚類算法和K-means算法對(duì)數(shù)據(jù)進(jìn)行聚類。通過兩種聚類算法的有效組合，解決了原有聚類算法聚類結(jié)果受初始聚類中心選取的影響。實(shí)驗(yàn)證明該算法在保持低水平誤報(bào)率的前提下，具有較高的檢測(cè)率，對(duì)于未知入侵行為檢測(cè)的具有較好的可行性和有效性。

參考文獻(xiàn)：

[1]Barrus，JosephD.IntrusionDetectioninRealTimeinalMulti-NodeMulti-HostEnvironment[D].Master5thesis.NavalPostgraduateSehool，CA，2006：23-34.

[2]阮耀平，易江波，趙戰(zhàn)生.計(jì)算機(jī)系統(tǒng)入侵檢側(cè)模型與方[J].計(jì)算機(jī)工程，2005（9）：224-236.

[3]楊義先，鈕心忻.入侵檢測(cè)理論與技術(shù)[M].北京：高等教育出版社，2006：56-67.

[4]MehmedKantardxie.數(shù)據(jù)挖掘概念、模型、方法和算法[M].北京：清華大學(xué)出版社，2003：170-194.

[5]湯潔.分布式入侵檢測(cè)系統(tǒng)的研究與設(shè)計(jì)[D].南京：南京信息工程大學(xué)，2008：89-96.

[6]熊家軍.基于數(shù)據(jù)挖掘的入侵檢測(cè)關(guān)鍵技術(shù)研究[D].武漢：華中科技大學(xué)，004：2-96.

[7]RumethartD，drowB，LehrM.Thebasicideasinneuralnetworks[J].ununieationsoftheACM，994，7（3）：7-92.

[8]梁紅.利用劃分方法進(jìn)行混合數(shù)據(jù)聚類[J].地理空間信息，011（12）：8-19.

[9]秦姣華，旭宇.據(jù)挖掘在入侵檢測(cè)中的應(yīng)用[J].現(xiàn)代計(jì)算機(jī)，2008（1）：23-26.

[10]耿俊燕，吳灝.數(shù)據(jù)挖掘在入侵檢測(cè)系統(tǒng)中的應(yīng)用研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，26（4）：870-872.

[11]AprespectiveonDatabasesandDataMining，InproceedingsoftheFirstIntemationalConferceonKnowLedgeDiscoveryandDataMining（KDD95）.2009：150-155.

[12]王千.K-means聚類算法研究綜述[J].電子設(shè)計(jì)工程息，2012（7）：21-22.

[13]LaiJZC，Tsung-JenH.FastglobalK-meansclusteringusingclustermembershipandinequality[J].PatternRecognition，2010（43）：1954-1963.

[14]匡青，鮑夢(mèng).改進(jìn)蟻群算法的動(dòng)態(tài)K-均值聚類分析[J].軟件導(dǎo)刊，2008，7（1）：154-155.

[15]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報(bào)，2008，19（1）：48-61.

[16]王英澤.一種數(shù)據(jù)挖掘技術(shù)在入侵檢測(cè)系統(tǒng)中的應(yīng)用[D].哈爾濱：哈爾濱理工大學(xué)，2007：34-43.

[17]夏天揚(yáng).蟻群算法在聚類分析中的應(yīng)用研究[D].武漢：武漢理工大學(xué)，2010：34-45.

[18]陳軍.用一種改進(jìn)的蟻群聚類算法進(jìn)行網(wǎng)絡(luò)入侵檢測(cè)[J].沈陽航空工業(yè)學(xué)院學(xué)報(bào)，2010（2）：72-73.

[19]范治軍.基于數(shù)據(jù)挖掘的入侵檢測(cè)研究[D].大連：大連理工大學(xué)，2012：28-38.

[20]梁君玲.蟻群聚類算法研究及其在聚類中的應(yīng)用[D].廣州：華南理工大學(xué)，2011：30-35.

[21]朱琳.基于數(shù)據(jù)挖掘的入侵檢測(cè)的研究[D].蘭州：蘭州理工大學(xué)，2012：20-40.