一種改進的K-means算法在異常檢測中的應用

陳　莊，羅告成（重慶理工大學計算機科學與工程學院，重慶400054）

一種改進的K-means算法在異常檢測中的應用

陳莊，羅告成
（重慶理工大學計算機科學與工程學院，重慶400054）

為提高K-means聚類算法在異常檢測中的效果，給出一種改進的K-means聚類算法。基于最大距離選取初始聚類中心，并引入信息熵計算各個屬性的權重，用改進后的加權歐氏距離公式計算數據集中樣本點間的距離。選取KDD CUP99數據集測試算法的性能。實驗結果表明，本算法有助于提高異常檢測的檢測率和降低誤報率。

異常檢測；數據挖掘；K-mean聚類算法；初始聚類中心；加權歐式距離

入侵檢測是一種保護計算機和網絡的主動防御策略，異常檢測則是入侵檢測的重要組成部分。將數據挖掘技術應用到異常檢測領域，從海量數據中提取網絡正常行為模式，有助于解決傳統的基于誤用檢測的入侵檢測系統檢測率低和誤報率高的問題。

異常檢測方法構建正常行為模式時基于以下兩個前提［1］：①網絡中正常數據的數量遠大于入侵數據；②入侵數據與正常數據之間存在很大的差異。

本文將信息熵理論引入無監督的聚類算法，提出一種相似度計算和初始聚類中心選擇都更為優化的K-means聚類算法應用于異常檢測。該方法首先過濾數據集中的離群點或孤立點，以減少這些點對聚類的負面影響；其次使用一種基于最大距離選取的方法選擇初始聚類中心，同時引入信息熵的方法定義一種屬性加權的歐式距離，并將此加權歐式距離應用到整個聚類的相似度計算中；之后進行迭代計算，并將記錄劃分到不同的聚類中。本文使用KDD CUP 99數據集來測試算法的性能。結果表明，此方法具有較高的檢測率和較低的誤報率，達到了預期的目標。

1　聚類算法應用于異常檢測相關研究

異常檢測作為當前入侵檢測研究領域的熱點，其普遍的思想是以大量的審計數據為背景來刻畫系統或用戶的正常使用模式，建立正常活動模型，然后通過檢查當前活動和正常模型之間的偏離度來確認入侵行為［2］。數據挖掘中的聚類算法便是基于以上思想的典型算法。為更好地發現網絡攻擊行為，相關研究人員提出了很多改進的方法［3-4］。而在聚類算法中，對K-means算法的改進研究最為廣泛。

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

本文在考慮初始聚類中心的選擇對聚類的過程及結果有重大影響的同時，也權衡了數據對象中各個屬性對聚類所發揮的作用，提出一種基于最大距離選擇初始聚類中心并結合信息熵屬性加權距離公式計算數據對象間距離的改進K-means聚類算法，并將其應用于異常檢測中。

2　算法相關定義與運算

2.1信息熵屬性權值引入及加權歐氏距離計算

傳統K-means算法隨機選取初始聚類中心，并未考慮數據對象的各個屬性對聚類效果的作用是不一樣的，這會導致算法難以獲得穩定且精確的聚類效果。

通常，信息論中的熵被用來衡量一個事物的“有序”程度。事物信息熵值越大，表明它所處的狀態越穩定；相反，信息熵的值越小，表明事物所處的狀態越無序［12］。基于這一點，本文將信息熵的方法引入到聚類方法中，根據各屬性的變動程度，通過計算信息熵給出各屬性的權重，為數據對象根據屬性更好地聚類提供支持。

使用信息熵值法計算屬性權重的過程如下［13］：

1）設待聚類的數據集A由n個m維的數據對象構成，于是構造屬性值矩陣：

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

2）計算第i個數據對象的第j維屬性值的比重：

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

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

4）計算第j維屬性值的波動系數：qj=1-Ej。Ej越大，說明數據集A中n個數據對象的第j維屬性所有取值情況差異越小，則該屬性的聚類作用越小；反之，Ej越小，第j維屬性取值情況差異越大，則該屬性的聚類作用越大；當第j維屬性都取相同值時，Ej=1，此時該屬性的聚類作用為0。綜上所述，qj越大則說明屬性越重要。

5）計算各維屬性的權重：

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

在計算出各維屬性的權重之后，給出賦權歐式距離的計算公式。假設數據集A有m個屬性，則兩個樣本點a與b之間的加權歐式距離為

其中xaj和xbj分別表示數據對象a和b對應的第j個屬性值。

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

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

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

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

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

4）依次類推，直到找出數據集中剩余的k-4個初始聚類中心。

1.5 統計學處理 采用SPSS18.0軟件進行數據分析。計數資料用百分率表示，比較采用χ2檢驗，以P<0.05為差異有統計學意義。

3　改進算法介紹及分析

結合以上研究，給出改進的K-means聚類算法步驟：

1）確定初始聚類中心個數k。

2）根據式（3）計算數據集A中各個屬性的權重。

3）根據式（4）計算樣本點之間的距離。

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

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

改進后的K-means算法流程如圖1所示。

圖1　改進后的K-means算法流程

另外，考慮到異常檢測中描述一個數據樣本的特征屬性以連續型數值為主，例如數據包的報文長度、數據包生存期、TCP窗口大小、UDP數據報長度等，所以本文的改進算法以數據集A的數據對象各屬性均為連續型數值為前提。

4　實驗結果與分析

本文將傳統K-means算法與改進的算法進行對比實驗，以驗證算法的效果。實驗使用KDD CUP99數據集。KDD CUP99數據集是目前主要的入侵檢測方法測評樣本庫之一［15］，針對入侵檢測算法研究的文章大多采用這一數據集進行實驗。本數據集包括4 898 431條記錄，每條記錄都被標記為正常或異常，其中異常記錄3 925 650條，包含22種攻擊類型。這22種攻擊類型可以分為DOS攻擊、R2L攻擊、U2R攻擊及probing攻擊四大類。

KDD CUP99數據集中的樣本由41個特征屬性來描述。其中7個離散值屬性在實驗中被忽略，剩余34個連續型數值屬性作為判斷樣本數據是否異常的依據。

為評估算法的準確性，本文選擇以下兩個指標：檢測率和誤報率。檢測率等于正確檢測出為異常記錄的數目與總的異常記錄數目之比；誤報率等于檢測出為異常但實際為正常記錄的數目與總的正常記錄數目之比。

首先選擇只包含DOS攻擊的樣本數據集，在聚類中心k取不同數值的情況下測試算法，與傳統的K-means算法進行對比實驗。實驗結果見表1。

表1　不同k值情況下檢測DOS攻擊對比實驗

實驗結果表明：改進后的K-means算法在檢測DOS攻擊時比傳統的K-means算法具有更高的檢測率和更低的誤報率。

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

表2　相同k值情況下檢測不同攻擊對比實驗

實驗結果表明：在聚類中心k值確定的情況下檢測不同類型的攻擊時，改進后的K-means算法在檢測率和誤報率方面效果好于傳統的K-means算法。

5　結束語

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

本文使用KDD CUP99數據集測試算法的性能。實驗結果表明，改進后的K-means算法與傳統的K-means算法相比，具有更高的檢測率和更低的誤報率，達到了預期的目標。算法的不足之處是聚類中心k值的確定需要經過多次嘗試才能找到一個合適的范圍，并且改進后的算法計算量較大。如何更有效地確定k值并減少算法的計算量是下一步研究的重點。

［1］劉濤，馬曉宇，胡景.一種K-means算法在網絡異常檢測中的應用［J］.微電子學與計算機，2012，29（5）：42 -45.

［2］蘇艷君，沈剛，劉昕.基于網絡聚合行為的異常檢測方法研究［J］.計算機工程與科學，2010，3（32）：38-41.

［3］袁遇晴，況湘玲，凌利軍.基于數據挖掘的網絡入侵檢測研究［J］.計算機安全，2014，7（17）：14-17.

［4］梁飛，閆宏印.基于聚類分析的動態自適應入侵檢測模式研究［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均值聚類的入侵檢測算法［J］.計算機科學，2010，6（6）：122 -124.

［7］楊宇舟，張鳳荔，王勇.基于K-means聚類的分支界定算法在網絡異常檢測中的應用［J］.計算機科學，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］仝雪嬌，孟凡榮，王志曉.對K-means初始聚類中心的優化［J］.計算機工程與設計，2011，1（32）：2718 -2724.

［10］于海濤，賈美娟，王慧強.基于人工魚群的優化K-means聚類算法［J］.計算機科學，2012，12（39）：60 -64.

［11］許曉東，楊燕，李剛.基于K-means聚類的網絡流量異常檢測［J］.無線通信技術，2013，4（1）：21-26.

［12］孟洋，趙方.基于信息熵理論的動態規劃特征選取算法［J］.計算機工程與設計，2010，31（17）：3879-3881.

［13］原福永，張曉彩，羅思標.基于信息熵的精確屬性賦權K-means聚類算法［J］.計算機應用，2011，31（6）：1675 -1678.

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

［15］唐菀，馬杰，曾廣平.評測智能化入侵檢測方法的樣本庫分析［J］.中南民族大學學報，2010，29（2）：84-87.

（責任編輯楊黎麗）

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

信息安全國家標準項目（2013bzyj—WG5—002）

陳莊（1964—），男，博士，教授，主要從事企業信息化管理、網絡與信息安全研究。

陳莊，羅告成.一種改進的K-means算法在異常檢測中的應用［J］.重慶理工大學學報：自然科學版，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.