李建國

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

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

李建國

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

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

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

0 引言

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

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

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

1.1 算法概述

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

1.2 算法應用不足

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

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

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

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

2 優(yōu)化聚類算法的設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實驗結(jié)果分析

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

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

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

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

4 結(jié)束語

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

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

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

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

［4］HAN Jiawei，KAMBER Micheline.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京：機械工業(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］.合肥：中國科學技術(shù)大學，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］.計算機系統(tǒng)應用，2008（9）：2-5.

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

［11］孫士保，秦克云.改進的k-平均聚類算法研究［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

淮北市科技局基金項目（20120308）

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