優(yōu)化的聚類算法在異常檢測中的應(yīng)用

李建國

（淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000）

優(yōu)化的聚類算法在異常檢測中的應(yīng)用

李建國

（淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000）

分析原有k-means聚類算法在異常檢測應(yīng)用中的不足，并對其進(jìn)行優(yōu)化，將優(yōu)化后的聚類算法應(yīng)用到異常檢測中.實(shí)驗(yàn)表明，優(yōu)化后的算法在入侵檢測率和抗干擾能力方面有很大的提高.

異常檢測；誤用檢測；聚類分析；k-means算法

0 引言

入侵檢測［1-2］（Intrusion Detection）技術(shù)作為新一代、動(dòng)態(tài)的網(wǎng)絡(luò)檢測技術(shù)，主要用來識(shí)別對計(jì)算機(jī)和網(wǎng)絡(luò)資源的惡意使用行為，包含外部和內(nèi)部的各種非法授權(quán)行為.根據(jù)入侵行為的屬性，入侵檢測一般分為異常檢測和誤用檢測兩種方式［3］.異常檢測（Anormaly Detection）是一種在不需要操作系統(tǒng)及其安全性缺陷的專門知識(shí)情況下，就可以檢測入侵者的方法，采用定量的方式描述可以接受的行為特征，以區(qū)分異常的、潛在的入侵行為，通過該方式可以發(fā)現(xiàn)未知的新型攻擊.誤用檢測（Misuse Detection）通過檢測用戶行為中的那些與某些已知的入侵行為模式類似的行為，或那些利用系統(tǒng)中缺陷實(shí)施攻擊的行為，以判斷是否屬于入侵行為，通過該方式只能檢測出已知攻擊.目前，為提高對網(wǎng)絡(luò)攻擊的檢測水平，通過引入聚類分析技術(shù)聯(lián)合異常檢測技術(shù)，已成為廣大學(xué)者研究的熱點(diǎn)領(lǐng)域.

本文研究當(dāng)前網(wǎng)絡(luò)攻擊的多種形式結(jié)合異常檢測的要求，對傳統(tǒng)k-means聚類算法在實(shí)際應(yīng)用中的缺陷進(jìn)行認(rèn)真總結(jié)，并結(jié)合實(shí)際應(yīng)用對算法進(jìn)行優(yōu)化，通過實(shí)驗(yàn)證明，優(yōu)化后的算法在入侵檢測率和抗干擾能力方面都有很大的提高.

1 傳統(tǒng)聚類算法分析

1.1 算法概述

聚類分析算法中最常用的算法是基于劃分的k-means算法，該算法根據(jù)最終聚類的個(gè)數(shù)k隨機(jī)地選取k個(gè)初始聚類中心，不停地迭代，當(dāng)達(dá)到目標(biāo)函數(shù)的最小值時(shí)結(jié)束，即得到最終的聚類結(jié)果［4］.其中，目標(biāo)函數(shù)通常采用平方誤差準(zhǔn)則.定義如式（1）所示：

1.2 算法應(yīng)用不足

實(shí)際應(yīng)用時(shí)，由于網(wǎng)絡(luò)環(huán)境十分復(fù)雜，網(wǎng)絡(luò)數(shù)據(jù)屬性較多，難以精確度量等因素，使得該聚類算法應(yīng)用在異常檢測中有如下不足：

（1）要先給出聚類的最終個(gè)數(shù)，并以此作為初始聚類中心的個(gè)數(shù)，然后迭代掃描數(shù)據(jù)簇，同時(shí)持續(xù)修改聚類中心和數(shù)據(jù)項(xiàng)所屬的簇，直到聚類中心穩(wěn)定.因此，聚類結(jié)果與聚類個(gè)數(shù)聯(lián)系緊密，聚類個(gè)數(shù)不同聚類結(jié)果差異較大，這使得在具體應(yīng)用中很難把握.

（2）算法執(zhí)行結(jié)束后將會(huì)產(chǎn)生空聚類（即沒有記錄與聚類中心的值匹配），這將嚴(yán)重影響聚類效果；

（3）由于算法執(zhí)行時(shí)，初始聚類中心的選取方式是任意的，并且該算法對初值敏感，對于不同的初值，容易導(dǎo)致不同的聚類結(jié)果.

2 優(yōu)化聚類算法的設(shè)計(jì)

現(xiàn)針對傳統(tǒng)聚類算法在異常檢測中存在的缺陷，對其進(jìn)行如下優(yōu)化：

（1）首先假定一距離聚類中心值S作為參數(shù)，接著計(jì)算當(dāng)前數(shù)據(jù)項(xiàng)到該中心的距離，若此值大于S，則以該數(shù)據(jù)項(xiàng)產(chǎn)生新的聚類中心.因此，最終聚類的個(gè)數(shù)可以隨時(shí)調(diào)整.另外，對于異常數(shù)據(jù)項(xiàng)又可以被劃分到新的聚類中去，聚類效果較好.

（2）對于空聚類，可以將距離聚類中心最遠(yuǎn)的數(shù)據(jù)項(xiàng)移除其所屬的集合，并以該數(shù)據(jù)項(xiàng)作為另外一個(gè)新聚類的聚類中心.這樣新的聚類就代替了空聚類.

（3）關(guān)于初始聚類中心選取的問題，可通過以下方法解決：從原始數(shù)據(jù)集中選取樣本集A，計(jì)算出k個(gè)聚類中心.先計(jì)算樣本集中數(shù)據(jù)之間的距離，以距離最近的兩點(diǎn)組成樣本集A1，并將此從A中刪除，然后將A1中的樣本與樣本集中的數(shù)據(jù)比較，找出樣本集中與A1最近的點(diǎn)，將它們并入A1，并從A中刪除.直到A1中數(shù)據(jù)的個(gè)數(shù)達(dá)到預(yù)定的閾值.再從A中找到樣本兩兩距離最近的樣本組成A2，重復(fù)上述操作得到k個(gè)點(diǎn)集，再對k個(gè)點(diǎn)集分別取平均值，進(jìn)而得到k個(gè)初始聚類中心，有效地避免了“孤立點(diǎn)”帶來的不良影響，同時(shí)加強(qiáng)初始聚類中心的代表性.

優(yōu)化后的算法如下（假定數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)的個(gè)數(shù)為M，聚類參數(shù)為S，初始聚類個(gè)數(shù)為n）：

7）若出現(xiàn)空聚類，則剔除出距離聚類中心最遠(yuǎn)的數(shù)據(jù)項(xiàng)，以此作為新產(chǎn)生的聚類中心；

8）直到聚類中心穩(wěn)定，算法結(jié)束，并輸出新的聚類.

3 優(yōu)化算法在異常檢測中的應(yīng)用分析

本實(shí)驗(yàn)環(huán)境基本配置如下：Intel Dual-Core E5500，4GB內(nèi)存，Windows2000操作系統(tǒng)，Visual C++ 6.0，采用KDD Cup 99數(shù)據(jù)集［8-9］作為實(shí)驗(yàn)數(shù)據(jù).

實(shí)驗(yàn)從數(shù)據(jù)集中選取包含PROBE端口掃描攻擊的記錄21 396條，包含Dos拒絕服務(wù)攻擊的記錄20 832條.其中分別包含了397條PROBE攻擊記錄和370條DoS攻擊記錄.從每條記錄的41個(gè)屬性中選取14個(gè)屬性作為測試樣本，通過本文提出的優(yōu)化聚類算法將數(shù)據(jù)劃分成不同的集合，進(jìn)而將正常數(shù)據(jù)與異常數(shù)據(jù)隔離.

3.1 網(wǎng)絡(luò)檢測數(shù)據(jù)的預(yù)處理

由于從網(wǎng)絡(luò)中得到的檢測數(shù)據(jù)，數(shù)據(jù)屬性種類繁多，并且其屬性的度量單位差異較大，因此在應(yīng)用本算法之前要用無單位的值替換原屬性的值［10］.先通過以下公式計(jì)算出檢測數(shù)據(jù)中各屬性的平均絕對誤差及平均值，分別用s、m表示，如式（3）和式（4）所示.

其中，第 f個(gè)屬性的平均絕對誤差用sf表示，第 f個(gè)屬性的平均值用mf表示，xif表示第i條記錄的第f個(gè)屬性.用zf表示預(yù)處理后的第 f個(gè)屬性的值.

在對檢測數(shù)據(jù)完成以上處理之后，接著對數(shù)據(jù)屬性的值進(jìn)行相似性計(jì)算，相似類的劃分是以對象間的距離為依據(jù)的.檢測數(shù)據(jù)的屬性分為離散型符號(hào)屬性和連續(xù)型數(shù)值屬性兩類.用歐幾里德距離來度量連續(xù)型數(shù)值屬性之間的距離，如式（6）所示；對于離散型符號(hào)屬性之間的距離則以數(shù)據(jù)對象間不同符號(hào)特征的離散屬性的個(gè)數(shù)來表示.假設(shè)在檢測數(shù)據(jù)集中有兩個(gè)數(shù)據(jù)對象xi和xj，其中連續(xù)型數(shù)值屬性有p個(gè)，離散型符號(hào)屬性有m個(gè)，兩對象之間的距離可用式（7）來表示.其中，dm(xi,xj)表示數(shù)據(jù)xi與xj的離散型符號(hào)屬性之間的距離，dp(χi,χj)表示對象xi與xj的連續(xù)型數(shù)值屬性之間的歐幾里得距離.δ表示離散型符號(hào)屬性之間的距離在計(jì)算記錄間距離中所占的權(quán)重［11］.

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

假設(shè)本實(shí)驗(yàn)記錄總數(shù)為N，Q代表異常記錄的比例，若數(shù)據(jù)集中數(shù)據(jù)項(xiàng)的數(shù)目小于QN，則把其當(dāng)作異常聚類.假設(shè)Q值為0.02，初始聚類中心的個(gè)數(shù)為2.通過采用本文提出的優(yōu)化聚類算法分別對上文中提取的兩類數(shù)據(jù)集進(jìn)行檢測，得出關(guān)于 DoS與PROBE攻擊的檢測率和誤檢率的變化情況如圖1和圖2所示.

圖1 DoS攻擊的檢測率和誤檢率

圖2 PROBE攻擊的檢測率和誤檢率

由以上檢測結(jié)果可以看出，通常情況下初始聚類中心個(gè)數(shù)和異常數(shù)據(jù)所占比例固定時(shí)，檢測率會(huì)隨著聚類參數(shù)的減小而增大；同時(shí)檢測率和誤檢率也隨著聚類個(gè)數(shù)的增加而增加，因此選擇一個(gè)較小的聚類參數(shù)就可以達(dá)到很好的聚類效果.通過圖1和圖2得知，當(dāng)聚類參數(shù)為15時(shí)，檢測率達(dá)到較高的水平，同時(shí)也保持相對低的誤檢率，系統(tǒng)狀態(tài)最佳.

4 結(jié)束語

本文所提出優(yōu)化后的聚類算法有效地解決原算法中聚類中心個(gè)數(shù)對聚類結(jié)果影響較大的問題，同時(shí)也把空聚類和孤立點(diǎn)對聚類結(jié)果的影響降到較低的水平.實(shí)驗(yàn)證明，聚類算法在異常檢測中的應(yīng)用有著重大的研究意義，下一步研究的目標(biāo)和方向，應(yīng)該結(jié)合其它的異常檢測技術(shù)，繼續(xù)優(yōu)化算法，以更大程度地提高系統(tǒng)的有效性.

［1］史美林，錢俊，董永樂.入侵檢測技術(shù)與發(fā)展趨勢［J］.信息安全與通信保密，2002（5）：45-57.

［2］崔錦法，李甦，王偉平.入侵檢測系統(tǒng)研究［J］.云南大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，28（SI）.128-132.

［3］宋世杰，胡華平，胡笑蕾，等.數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)型誤用入侵檢測系統(tǒng)中的應(yīng)用［J］.計(jì)算機(jī)工程，2004，34（4）：126-127.

［4］HAN Jiawei，KAMBER Micheline.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2001：223-225.

［5］OZGUR D，MURAT T，MIN A，et al.An intelligent intrusion detection system（IDS）for anomaly and misuse detection in computer networks［J］.Expert Systems with Applications，2005（29）：713-722.

［6］連一峰.分布式入侵檢測系統(tǒng)研究［D］.合肥：中國科學(xué)技術(shù)大學(xué)，2002.

［7］RICHARD F，SUE R，LEE B，et al.Intrusion detection inter-component adaptive negotiation［J］.Computer Networks，2001（34）：605-621.

［8］STOLFO S J,FAN W，LEE W.KDD-CUP-99 Task Description［EB/OL］.［1999-06-19］.http：//kdd.ics.uci.edu/data?bases/kddcup99/task.html.

［9］趙悅，陳凌暉.基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2008（9）：2-5.

［10］李衛(wèi)平.k-means算法研究［J］.中西部科技，2011，7（8）：51-53.

［11］孫士保，秦克云.改進(jìn)的k-平均聚類算法研究［J］.計(jì)算機(jī)工程，2007（13）：200-201.

Application of Optimized Clustering Algorithm in Anomaly Detection

LI Jian-guo
（Department of Computer Science and Technology，Huaibei Normal University，235000，Huaibei，Anhui，China）

By analyzing the deficiency of the original k-means algorithm in intrusion detection，the k-means algorithm was optimized.The optimized algorithm was used in anomaly detection.Experiments show that the optimized algorithm can get better cluster result and progress was made in the rate of intrusion detection and anti-interference technique.

anomaly detection；misused detection；cluster analysis；k-means algorithm

TP 393.08

A

2095-0691（2013）04-0052-04

2013-10-08

淮北市科技局基金項(xiàng)目（20120308）

李建國（1975- ），男，安徽碭山人，副教授，主要研究方向：網(wǎng)絡(luò)安全、數(shù)據(jù)挖掘.