基于改進的K-means入侵檢測算法*

季賽花 黃樹成

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

隨著互聯網的飛速發展與快速普及，網絡已經成為人們在生活中不可缺少的部分。互聯網固有的開放性與共享性在給人們帶來便利的同時，伴隨而來的是現今人們極為關注的相關網絡信息安全問題［1］。基于信息加密技術、防火墻等靜態安全防御技術已經無法適應動態變化的網絡，入侵檢測作為一種積極主動的安全防護技術，彌補了靜態安全技術的缺陷［2］，提供了對內部攻擊、外部攻擊和誤操作的實時保護。

數據挖掘技術能從海量數據中挖掘出有用的知識，進而應用于入侵檢測中，識別正常或異常行為，能有效提高入侵檢測效率。而聚類分析是數據挖掘重要的一部分。它能通過分析數據的屬性特征，將特征相近或相似的數據劃分到同一個類中。K-means算法是一種典型的聚類算法，具有快速簡單，具有較高的大數據集運算效率［3］。將K-means算法運用于入侵檢測中，在數據處理和分析方面有明顯的優勢，但是K-means算法也有一些缺點，比如聚類數目需要事先給定，聚類結果對初始中心點和數據集中的噪聲點以及孤立點敏感，且聚類結果易陷入局部最優［4］。近年來，很多學者對傳統的K-means算法進行改進，并將其應用于入侵檢測中。徐超［5］等在基于最大最小距離算法的思想和有效性指標基礎上，迭代計算出最優聚類數和其對應的聚類中心，并用于構建正常行為模式庫，入侵檢測性能有所改善。李鵬［6］等將K-means與決策樹結合，根據信息增益比差異將樣本數據先分類再建立決策樹，提升了算法的檢測率，但對未知攻擊的檢測能力較低，因此，傳統K-means算法在入侵檢測應用上仍存在不足。

為此，文中提出了一種改進的K-means算法，基于類內和類間的聚類有效性指標的確定聚類數目，在聚類過程中對距離進行特征加權，并結合三支決策聚類思想，擴展了K-means算法使之適用于不確定性聚類，進而提高入侵檢測的檢測率，降低誤檢率。

2 傳統K-means聚類算法

2.1 算法過程

K-means算法是1967年由J.B.MacQueen首先提出的一種無監督聚類算法［7］。其算法思想比較簡單，即在無類標簽的數據集中，將N個對象劃分到K個簇中，使得相似度較高的在一個類中，差異較大的在不同的類中，其算法流程［8］如下：

1）從給定的數據集中選擇K個點作為初始聚類中心點；

2）對每個樣本點，計算樣本點到各個聚類中心點的距離，選出最小距離對應的聚類中心點，并將其劃分到該聚類中心點對應的聚類中；

3）計算每個聚類中所有點的均值，將此均值點作為新的聚類中心；

4）循環2）、3），直到每個聚類的中心點不再發生變化，目標函數收斂，算法結束。

其中，一般采用歐式距離去計算樣本點到各個聚類中心點的距離，見式（1）；采用均方差作為目標函數，見式（2）。

2.2 算法在入侵檢測應用中的不足

K-means算法操作簡單、運算速度快，將其應用于入侵檢測中具有重要的研究價值。但同時也存在一些不足之處。其中，聚類的數目難以估計，不確定的K值會導致聚類質量下降［9］。入侵檢測中從網絡中抓取的數據包都是實時的，所以難以確定聚類數，致使聚類效果不穩定，從而影響入侵檢測的性能［10］。

3 算法的改進

3.1 特征加權

網絡數據呈現多維性，而每條數據的每個特征對聚類的作用都不盡相同，所以需要對不同特征進行權值分配［11］。本文兼顧類內和類間對象的關系，利用前次迭代中產生的均值、方差等確定權重。

設數據集X中有N個D維數據為第k類的第d維上的均值為當前第k類的方差在第d維上的取值，如式（3）所示。

整個數據集X在第d維特征上所有的聚類均值總和（式（4））與方差總和（式（5））為表示第d維特征在各類別中心的間距表示第d維特征的類內離散度大小。為了達到理想的聚類效果，類間距離越大越好，類內離散度越小越好。所以，可以設一個第d維特征類間距離與類內離散度的比值作為第d維特征的聚類效果的指標，如式（6）所示。

那么第d維特征在聚類過程中的權重，即為第d維特征的聚類效果指標與各維特征聚類效果指標之和的比值。如式（7）所示。

即求得各維特征的權重。繼而得到數據集中任意xi至聚類中心uj的距離特征加權公式，如式（8）所示。

3.2 K值有效性指標

本文算法K值有效性指標利用上述的特征加權距離綜合考慮類內緊密性與類間分離性。

設在數據集U中，Ci表示其中被劃分的一個類，定義類內距離Intra（Ci）為類Ci中任意兩個數據x，y的距離平方和，如式（9）所示；定義類間距離Inter（Ci，Cj）為類Ci到其他類Cj的距離，如式（10）所示。其中，k、p分別是類Ci和類Cj中數據樣本點的個數。

3.3 三支決策聚類

三支決策（Three-way Decisions）最早由Yao［12］在粗糙集理論的基礎上提出的。在人們實際決策中，由于對事件信息了解程度不同，往往會做出三種類型的決策：接受、拒絕和延遲。對于那些有充分把握的事件，人們很容易做出接受或拒絕的決策，但是對不確定事件，人們往往不能立馬做出決策，需要延遲決策［13］。該理論與傳統的二支決策相比，更有實際意義。基于此，將三支決策引入到聚類分析中，考察對象與類之間的關系，可劃分為對象屬于這個類，對象不屬于這個類以及對象可能屬于這個類。

結合三支決策思想，在一個數據集U中，針對一個類C，與其有關聯的有三個互不相交的區域：CI、CB和CO，又稱I域，B域和O域［14］。I域中的對象確定屬于這個類，O域中的對象確定不屬于這個類，B域中的對象可能屬于也可能不屬于這個類，即類C的構成為C={CI，CB}。為保證有實際的意義，需 滿 足1）

3.4 改進的K-means算法

圖1 改進的算法流程圖

具體的步驟如下：

輸入：數據集X=｛x1，x2，…，xn｝，初始聚類數目k=2。

輸出：聚類結果C。

1）在數據集中，隨機選取k個初始聚類中心點U=｛u1，u2，…，uk｝；

2）計算數據集中除了聚類中心點外剩余數據對象xi到每個聚類中心uj的特征加權距離dist(xi，uj)，并把他們劃分到距離最近的簇Cj中；

4）如果聚類中心不發生變化，轉至5），否則轉至2）；

5）計算k=arg［S］，如果，那么，轉至1），否則轉至6）；

6）k'=argmin［S］，最終輸出新的二支聚類結果集C'；

7）遍歷C'，對于每一個類若則若，且，則，否則

4 仿真實驗及分析

4.1 實驗環境及數據說明

本文實驗借助的硬件平臺是Intel（R）Core（TM）i5-3230 CPU@2.60Hz，4GBRAM的計算機，并在Win7系統上采用在Python編譯器上實現程序設計。

本實驗使用KDD Cup99數據集中的corrected.data作為訓練集，使用10%的數據樣本作為測試集。KDD Cup99數據集中的每條數據由41個特征屬性和1個決策標簽組成［16］。其中決策標簽分為正常（Normal）和攻擊類型，攻擊類型有四大類：DOS，R2L，U2R，Probe。數據格式如下例所示：2，tcp，smtp，SF，1684，363，0，0，0，0，0，1，0，0，0，0，0，0，0，0，0，0，1，1，0.00，0.00，0.00，0.00，1.00，0.00，0.00，104，66，0.63，0.03，0.01，0.00，0.00，0.00，0.00，0.00，normal。

由于數據集中含有符號型數據屬性，不適合聚類測試，同時也為了避免“大數吃小數”現象，故對先要對數據進行數值化和歸一化處理。

4.2 結果分析

本改進模型的實驗結果評估指標主要有兩項：檢測率（Detection Rate，DR）和誤報率（False Posi?tive Rate，FPR）。

檢測率DR的公式如式（12）所示：

誤報率FPR的公式見式（13）：

由上述公式可以看出，誤報率越小，檢測率越大，入侵檢測性能越好。

改進前后的算法應用到入侵檢測中所得到的檢測率和誤報率見表1。

表1 實驗測試結果對比

如圖2所示，以誤報率為橫坐標，以檢測率為縱坐標畫出改進前后的入侵檢測算法的ROC曲線對比圖，由此可以很直觀地看出本文的入侵檢測算法的面積大于未改進的K-means算法的面積，可以說明本文的入侵檢測算法性能更好，檢測效率更佳。

圖2 ROC曲線

5 結語

針對傳統的K-means算法無法準確確定聚類數目而導致聚類質量下降的問題，本文提出了基于改進的K-means入侵檢測算法，一方面考慮數據的各維特征屬性對聚類作用不一，提出對聚類過程中所涉及的數據點到聚類中心點的距離進行特征加權；另一方面，基于類內和類間的聚類效果有效性指標來確定聚類數目；最后結合三支決策聚類思想，劃分確定域和模糊域，對模糊域中的數據延遲決策，進而提高了聚類的檢測率，降低了誤報率。