基于一種改進K-means算法的入侵檢測系統研究

謝霖銓 張思潔

（1.江西理工大學應用科學學院，江西 贛州 341000；2.江西理工大學理學院，江西贛州 341000）

當今社會是一個網絡化的信息時代，但隨著網絡應用范圍的不斷擴大，對網絡的各類攻擊與破壞也隨之而來。當前，國際信息安全領域的一種重要手段就是入侵檢測。入侵檢測技術由異常檢測和誤用檢測［1］組成，誤用檢測通常需要設定好檢測模型，具有高的檢測率，但是只能檢測已知類型。對于異常檢測，由于人們主要依賴于他們的直覺和經驗選擇統計特性，因此具有較高的誤報率［2］。

數據挖掘技術在融合不同領域方法的基礎上，利用分析工具從大量復雜數據中獲取對用戶有用的信息［3］。通過數據挖掘的方法可以構建自動的檢測模型用以降低數據分析的難度和復雜度［4］。由于K-means算法運用的廣泛性且由于該算法收斂速度快并可用于較大型的數據，因此選取該算法為基礎。將最大距離積法的K-means算法用于入侵檢測是削弱隨機初始化聚類中心所帶來的影響。對已知類型的訓練集進行分析和選取，用于整個系統的運行。實驗結果表明，該方法用于入侵檢測系統達到了良好的結果。

1 聚類分析算法

根據事物間的某種相似性對事物進行劃分和歸類的過程稱之為聚類，結果能得到一組具有較高相似度的對象［5］。

根據聚類算法所采用的基本思想將聚類分成幾類［6］。其中基于分割的K-means算法是實用性強、應用比較廣泛的一類。

標準測度函數［7］，定義為

傳統的K-means算法描述如下：

1.1 隨機初始化K個簇中心；

1.2 計算每個數據對象到K個簇中心的距離，根據相似度將該數據對象放入對應的簇中。

1.3 重新計算所有聚類的均值，并且計算出此時的測度函數值。

1.4 如果達到maxStep或滿足：

其中ε是一個極小數。式（2）表示當簇成員不再更改時聚類結束，否則，返回（2）。

K-means算法的使用范圍非常廣泛，算法簡單又易于操作，復雜度低，處理數據非?？旖?。但是由于原始的K-means本身的一切缺陷，會產生以下一些問題［6-8］：①初始聚類中心選取的不確定性影響著聚類的結果；②如果選擇了不正確的初始值，算法可能陷入局部最小值；③方法不適合處理形狀延展性較強的簇；④對K值的選取需要用戶適當調節；⑤對異常數據很敏感。針對缺陷① ②，將最大距離積法改進于K-means算法并用于入侵檢測。

2 基于一種改進K-means算法的入侵檢測系統

受到文獻［8］的啟發，把融合了最大距離積的K-means算法用于入侵檢測領域，盡可能地稀疏聚類中心［9］，代替傳統K-means算法中隨機初始化K個聚類中心這一步驟。

具體的算法描述如下：

2.1計算d（Xi，Xj）。

2.2 通過密度參數MinPts和ε，得到處于高密度點的數據對象集合D。

2.3 D中選取一個數據對象作為第1個聚類中心Z1，計入到集合Z中，并從D刪除；在集合D距離Z1最遠的一個高密度點作為第2個聚類中心Z2，并將其加入到Z中，在集合D中刪除。

2.4 計算D中所有數據對象到集合Z中每個聚類中心的距離d（Xi，Z），（Z=Z1，Z2…Z（tt＜k）），選擇滿足max（d（Xi，Z1）×d（Xi，Z2）×…×d（Xi，Z）t），（i=1，2，3…n），將找到點最為新的聚類中心加入到Z中。

2.5 直到Z中的聚類中心數目達到K個，則不必再進行上一步驟。

2.6 得到全部初始聚類中心。

基于最大距離積法的K-means算法可以降低聚類結果對于初始中心的敏感性產生的影響，避免由于中心對象選取稠密而導致的聚類沖突，并且能夠體現數據集的分布狀態［10］。

3 實驗與結果分析

在KDD CUP99提供的10%數據集中，包含了特征比較明顯的4大類網絡攻擊［11］：DOS、Probe、U2R、R2L。

其中訓練數據集包括23種攻擊行為，測試數據集包含38種攻擊行為。由于U2R和R2L兩種攻擊的特殊性，因此需要選取較多與內容特征有關的屬性。文章只選取service，flag，hot等15個特征屬性作為研究的特征屬性值。

表1 文獻［4］的入侵檢測結果

表2 基于改進的K-means算法的入侵檢測結果

為了營造一個與現實入侵檢測相差不大的環境，從10%數據集中隨機抽取100 000條數據共分成5組，其中入侵數據占1.5%共1 500條。這樣的目的是希望可以檢測出改進算法對于不同種類入侵數據的檢測效果，并且由于每個數據集中入侵數據明顯低于正常數據的數量，也符合現實網絡入侵行為的特性。兩個算法均在閾值q=0.4，K-means算法中K=5的條件下進行。實驗是在CPU：2.70GHZ，內存2GB，Window7的平臺上，開發環境為VC++6.0的環境下實現預處理和改進的K-means算法數據處理。

實驗是在算法能正常進行的基礎上通過得到的檢測率和誤報率來判斷系統性能的優劣。表1和表2對比可以明顯看出該算法檢測率方面優于文獻［4］，同時誤報率也更低。但是由表中也可以看出，改進算法在R2L、U2R攻擊方面的檢測率偏低，這是由于這兩種攻擊的比率在訓練集和測試集相差過大，并且由于網絡數據文段的非結構化信息中特征不易提取，因此R2L和U2R的檢測率相比于DOS和Probe兩種攻擊更低，對此，需要進行更加深刻的特征描繪。對于DOS和Probe兩種攻擊而言，檢測率和誤報率都處于相對比較理想的狀態，這兩種攻擊在某些屬性的變化與正常數據相差過大，過大的差異性利于檢測率的提高。

4 結論

本文融合了最大距離積法的聚類分析在基于密度的思想上的應用，充分體現了數據的自然分布，將該算法全新地應用于入侵檢測系統中除了保證檢測的有效性之外，還可以對于攻擊取得較高的檢測率和較低的誤報率。在接下來的研究中可以根據R2L和U2R攻擊本身存在的問題進行屬性特征的提取，以便在今后的研究中取得更好的效果。

［1］楊智君，田地，馬駿驍，等.入侵檢測技術研究綜述［J］.計算機工程與設計，2006，27（12）：2119-2123.

［2］薛靜鋒，曹元大.基于數據挖掘的入侵檢測［J］.計算機工程，2003，29（9）：17-18.

［3］梁煜.數據挖掘技術在網絡入侵檢測中的應用研究［J］.電腦編程技巧與維護，2014（2）：93-94.

［4］杜強，孫敏.基于改進聚類分析算法的入侵檢測系統研究［J］.計算機工程與應用，2011，47（11）：106-108.

［5］王令劍，滕少華.聚類和時間序列分析在入侵檢測中的應用［J］.計算機應用，2010，30（3）：699-701.

［6］賀玲，吳玲達，蔡益朝.數據挖掘中的聚類算法綜述［J］.計算機應用研究，2007，24（1）：10-13.

［7］熊忠陽，陳若田，張玉芳.一種有效的K-means聚類中心初始化方法［J］.計算機應用研究，2011，28（11）：4188-4190.

［8］周涓，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法［J］.計算機應用，2006，26（6）：1425-1427.

［9］樊曉光，路釗，王久崇，等.基于密度和距離積的聚類中心選取方法［J］.測控技術，2013，32（10）：152-154.

［10］Zhang X Y，Zeng H S，Jia L.Research of intrusion detection system dataset-KDD CUP99［J］.Computer Engineering&Design，2010，31（22）：4809-4805.

［11］王潔松，張小飛.KDDCup99網絡入侵檢測數據的分析和預處理［J］.科技信息：科學教研，2008（15）：407-408.