基于改進K均值聚類的入侵檢測算法研究

何明亮陳澤茂黃相靜

（1.海軍工程大學信息安全系武漢430033）（2.91681部隊寧波315731）

基于改進K均值聚類的入侵檢測算法研究

何明亮1陳澤茂1黃相靜2

（1.海軍工程大學信息安全系武漢430033）（2.91681部隊寧波315731）

為解決現有入侵檢測系統規則庫維護管理復雜，系統檢測效率不足等問題，設計了一種基于改進K均值聚類的規則挖掘算法。首先針對傳統k-means算法聚類數目不確定的問題，通過分析聚類數目與簇間距離、簇內距離的關系，引入動態函數確定最佳聚類數目；然后通過尋找數據密集區域避開離群點，優化了初始聚類中心的選擇，提高了算法效率。采用改進k-means聚類的入侵規則挖掘算法能夠快速有效的對大數據集進行聚類分析，解決了傳統入侵檢測系統規則庫維護復雜、難于檢測未知攻擊等問題。

入侵檢測；數據挖掘；k-means算法；聚類分析；規則庫

Class NumberTP393

1 引言

傳統入侵檢測系統（Intrusion Detection System，IDS）主要依據入侵模式和攻擊特點提取攻擊特征庫，在檢測效率和智能性上明顯不足。而隨著網絡技術的不斷發展，網絡帶寬快速提高，攻擊手段高超多樣，攻擊特征很難捕捉。因此采用傳統的網絡入侵檢測技術，難以有效檢測各種網絡滲透和攻擊。我們認為：一方面隨著網絡帶寬的提高，網絡數據具有數量大、流速快、類型多等特點，具有典型的大數據特征；另一方面一種新型的網絡攻擊技術，極可能是某種已知攻擊技術的發展，或者是若干已知攻擊技術的創新性的組合運用。因此，可以采用數據挖掘（Data Mining，DM）技術，對網絡數據流進行分析，分別建立正常行為規則庫和攻擊行為規則庫，從而對入侵行為進行檢測和預警。目前，國內外學者都在致力于將數據挖掘應用于入侵檢測系統，主要涉及基于數據挖掘的入侵檢測模型［1］和入侵檢測方法［2～4］。DM+IDS已成為入侵檢測領域的一個重要研究方向［5～11］。本文通過對傳統k-means算法聚類數目不確定和隨機選擇初始聚類中心等缺陷進行改進；然后利用改進的k-means聚類算法進行規則挖掘。有效解決了傳統入侵檢測系統規則庫維護復雜、難于檢測未知攻擊等問題。

2 傳統K均值算法缺陷分析

K均值算法是1967年由J.B.MacQueen提出的一種基于劃分的聚類方法。由于該算法簡單、高效、適用于大數據的處理，被廣泛應用于各個領域。K均值算法只需要輸入聚類個數k一個參數，就可以自行將Rd空間上的數據集X=｛x1，…，xi，…，xn｝劃分到K個不同類或簇之中，使得聚類結果中簇間相似度盡可能小，簇內相似度盡可能大。

K均值算法的處理流程：首先從給定的數據集X中隨機指定K個數據點作為初始聚類中心，即初始簇中心；對于數據集中其它數據點通過計算其與各個初始聚類中心的距離，將其劃分到與之最近的聚類中心所屬的簇中；然后通過計算各簇中所有數據對象的平均值，調整各簇的聚類中心，更新其它點的所屬簇，如此反復迭代，直至目標函數收斂。

一般采用均方差作為目標函數，其具體定義如下：

其中，x為數據集中的一個對象，Ci為一個簇，為Ci的中心，即Ci中所有對象的均值。

k-means算法描述，如下。

輸入：數據集x，簇個數k；

輸出：目標函數收斂的k個簇；

Step1：從給定的數據集X中隨機指定k個數據點作為初始聚類中心；

Step2：將剩下的數據對象劃分到與之最近的簇Ci中；，其中||ci是第i個簇中包含的數據個數；

Step4：循環Step2到Step3直到目標函數收斂。

Step3：計算新的簇中心：

K均值算法雖然簡單高效，但也有其本身的缺陷：

1）聚類個數k需要手動輸入。在聚類分析之前，k-means算法假定聚類數目k是已知的，但實際上很難確定k值。

2）初始聚類中心的選擇是隨機的。傳統的k均值算法隨機選擇初始中心，然后進行迭代；選擇不同的迭代起點，對應的搜索路徑各不相同。致使最終的聚類結果容易陷入局部最優而非全局最優。

3）噪聲和離群點對聚類結果有重大影響。由于算法的每次迭代，都會根據各簇中的數據屬性計算該簇的中心點，噪聲和離群點的存在，勢必會干擾簇中心的計算，影響聚類的結果。

3 K均值算法的改進

針對前一節中對k-means算法的缺陷分析，本文主要從聚類數目和初始聚類中心選擇兩個方面進行優化。首先，確定最合適的聚類數目。聚類數目太少，簇內距離太大，各簇劃分的太籠統，看不清楚各數據類的特征；聚類數目太多，簇內距離太小，各簇劃分的太細碎，對數據集的認識只限于各小類，缺乏整體認識。其次，確定初始聚類中心。分析可知，真實的聚類中心應該分布在數據相對集中密集的地方，且每個聚類中心應該有一定的距離。如果初始聚類中心離真實聚類中心越近，迭代的次數越少，目標函數收斂的越快，可以提高聚類算法的效率和準確性。

3.1 相關概念與定義

設X=｛x1，…，xi，…，xn｝是一個包含n個對象的Rd空間上的數據集。

定義1：簇間距離：各簇中心到樣本數據集X中心的距離。

定義2：簇內距離：各簇內所有數據到其中心的距離之和。

其中，Di為第i個簇的簇內距離，為簇Ci的中心，x為其中數據。

定義3：動態函數：簇間距離與加權的簇內距離之和。其中F(k)為動態函數，L、D、k的含義與式（1）、式（2）相同，ni為簇Ci中含數據個數，n為X中數據總個數。

3.2 聚類數目的確定

k-means算法假定聚類數目k是已知的，但實際上很難確定k值，而聚類個數的選取對聚類結果非常關鍵。因此，本文采用動態函數對聚類數目的選取進行優化。動態函數F(k)分為兩個部分，其中L是關于k的增函數；Di是關于k的減函數，F(k)的變化取決于二者的合成。分析可知，當F(k)的值最小時對應的k值即為最佳聚類數目。

首先，聚類數目過多過少都是不合常理的，不能夠清楚表達各簇特征。確定聚類數目k的最佳范圍［kmin，kmax］，就是要確定k的最小值kmin和最大值kmax。若kmin=1，代表樣本均勻分布，無明顯特征差異，則不用進行聚類，所以一般k的最小值kmin=2；對于kmax確定，目前尚沒有明確方法，一般使用經驗規則kmax≤n［12］，韓凌波在k均值算法中聚類個數優化問題研究［13］中也指出該規則是合理的，本文采用上述規則來確定k的取值范圍。

然后，對k∈[] 2，n上所有值分別進行聚類，

計算其動態函數F(k)的值。當F(k)最小時，對應的k值即為最佳聚類數目，記為k*。

3.3 初始聚類中心選擇算法

為了使選取的初始聚類中心更接近真實的聚類中心，改進算法首先計算每個數據點的緊密程度，對較為稀疏的獨立數據點進行標記，同時找出密集程度高的數據點集合。然后在數據密集區域內，選擇一個點，要求它和與之相鄰的t個數據點的距離之和最小，作為第一個初始聚類中心；接著在該區域內選擇距離第一個初始聚類中心最遠的點作為第二個初始聚類中心；依次選擇與已選取的初始聚類中心最小距離中最大的數據點作為下一個初始聚類中心［14］，直到第k個。這樣可以充分保證初始聚類中心的均勻分布。

下面詳細介紹選擇初始聚類中心的改進算法，如下。

輸入：數據集X，聚類個數k，最近鄰個數t；輸出：k個初始聚類中心；

Step1：對于數據集X={x1，…，xi，…，xn}中的每一個數據點xi，求出與之相鄰的t個數據點的距最近鄰數據點集合；

Step3：在N中，取Si最小的xi為第一個初始聚類中心c1；取距離c1最遠的數據點作為第二個初始聚類中心c2；第m（3≤m≤K）個初始聚類中心cm為滿足以下條件的數據點xi，xi∈N，max(Dmin(xi，c1)，Dmin(xi，c2)，…，Dmin(xi，cm-1))其中i=1，2，…，n，即xi為與已選取的初始聚類中心最小距離中最大的數據點。直至得到第K個初始聚類中心。

通過該算法選擇的初始聚類中心，首先，排除了噪聲和離群點的干擾，保證了聚類算法的迭代起點不會過多的偏離真實聚類中心，減少了算法的迭代次數；其次，依據數據的密集程度選擇初始聚類中心，有利于快速找到真實聚類中心，提高算法效率；最后，根據最大距離和原理，保證了初始聚類中心的均勻分布。

4 基于改進K均值聚類的規則挖掘算法

4.1 數據預處理

由于每條數據的數據值型屬性的波動范圍較大，往往會出現“大數”吃“小數”的現象，所以要對數值型數據進行標準化和歸一化處理；對于符號型屬性，不能直接進行比較，必須先對其進行賦值，然后進行標準化和歸一化。對于d維數據集X={x1，x2，…，xn}，數據預處理步驟如下［6］：

1）數值規范化處理

其中Averj是指第j個特征的平均值，是指第j個特征的平均絕對偏

2）數值的歸一化處理

歸一化處理就是將數據值變換到［0，1］區間上來，設x''ij為經歸一化處理之后的數值：，其中?i，xmin是j屬性的最小值，xmax是j屬性的最大值。

4.2 規則挖掘算法

k均值算法的最大特點就是能夠方便快捷地處理大數據集，由于正常網絡數據量明顯大于攻擊數據量，而且正常網絡數據與攻擊數據在某些屬性上的不同，因此可以將捕獲的網絡數據劃分為不同的類，通過設置閾值來檢測攻擊數據。然后分別將正常數據和攻擊數據增加到正常行為規則庫和攻擊行為規則庫。但k均值算法本身有許多不足之處，并不能直接應用［14-16］。本文通過分析該算法的特點，設計了一種基于改進k-means聚類的入侵規則挖掘算法，算法描述如下。

輸入：d維數據集X={x1，x2，…，xn}，聚類收斂精度ε，最近鄰個數t；

輸出：k個數據簇中心C={c1，…，cj，…，ck}，異常規則庫U，正常規則庫N；

Step1：令初始聚類準則函數值J0=0，每個數據點xi的異常度Axi=0，i=1，2，…，n；

Step2：對于數據集X={x1，…，xi，…，xn}中的每一個數據點xi，求出與之相鄰的t個數據點的距離之和，其中Gt(xi)為xi的t個最近鄰數據點集合；

Step4：在N中，取Si最小的xi為第一個初始聚類中心c1；取距離c1最遠的數據點作為第二個初始聚類中心c2；第m（3≤m≤K）個初始聚類中心cm為滿足以下條件的數據點xi，xi∈N，（i=1，2，…，n）：max(Dmin(xi，c1)，Dmin(xi，c2)，…，Dmin(xi，cm-1))，即xi為與已選取的初始聚類中心最小距離中最大的數據點。直至得到第K個初始聚類中心；

Step7：在形成的K個簇的過程中，若屬于該簇的數據點與該簇聚類中心距離的大于平均距離，即是第j個簇中包含的數據個數，則Axi++；

Step8：若Ax≥3，則判斷x為異常點，將其從集合N中刪除，并入集合U中；

5 結語

本文通過分析傳統k-means算法聚類數目不確定，隨機選擇初始聚類中心等不足。首先通過分析聚類數目與簇間距離和簇內距離的關系，引入動態函數找出了最佳聚類數目。然后通過尋找數據密集區域避開離群點區域，優化了k均值算法的初始聚類中心選擇。最后設計了一種基于改進K均值聚類的入侵規則挖掘算法，該算法能夠快速有效的對大數據集進行聚類分析，解決了傳統入侵檢測系統規則庫維護管理困難的問題。

［1］Li Y，Li J L，Yue S J，et al.Research of Intrusion Detection Based on Ensemble Learning Model［J］.Applied Mechanics and Materials，2013，336：2376-2380.

［2］Fatma H，Mohamed L.A two-stage technique to improve intrusion detection systems based on data mining algorithms［C］//5th International Conference on Modeling，Simulation and Applied Optimization（ICMSAO）.IEEE，2013：1-6.

［3］Kim G，Lee S，Kim S.A novel hybrid intrusion detection method integrating anomaly detection with misuse detection［J］.Expert Systems with Applications，2014，41（4）：1690-1700.

［4］Khor K C，Ting C Y，Phon-Amnuaisuk S.A cascaded classifier approach for improving detection rates on rare attack categories in network intrusion detection［J］.Applied Intelligence，2012，36（2）：320-329.

［5］劉華春，候向寧，楊忠.基于改進K均值算法的入侵檢測系統設計［J］.計算機技術與發展，2016，26（1）：101-106.

LIU Huachun，HOU Xiangning，YANG Zhong.Design of Intrusion Detection System based on Improved K Algorithm［J］.Computer Technology and Development，2016，26（1）：101-106.

［6］程曉旭，于海濤，李梓.改進的k-means網絡入侵檢測算法［J］.智能計算機與應用，2012，2（2）：21-23.

CHENG Xiaoxu，YU Haitao，LI Zi.Improved K-means Network Intrusion Detection Algorithm［J］.Intelligent computer and Application，2012，2（2）：21-23.

［7］劉長騫.K均值算法改進及在網絡入侵檢測中的應用［J］.計算機仿真，2011，28（3）：190-193.

LIU Changqian.Improvement of K mean Algorithm and its Application in Network Intrusion Detection［J］.Computer Simulation，2011，28（3）：190-193.

［8］儲澤楠，李世揚.基于節點生長馬氏距離K均值和HMM的網絡入侵檢測方法設計［J］.計算機測量與控制，2014，22（10）：3406-3410.

CHU Zenan，LI Shiyang.Design of Network Intrusion Detection Method based on the K Mean Value and HMM of the Node Growth Markov Distance［J］.Computer Measurement and Control，2014，22（10）：3406-3410.

［9］易倩，騰長華，張巍.基于馬氏距離的K均值聚類算法的入侵檢測［J］.江西師范大學學報，2012，36（3）：284-288.

YI Qian，TENG Changhua，ZHANG Wei.Intrusion Detection Based on K mean Clustering Algorithm based on Markov Distance［J］.Journal of Jiangxi Normal University， 2012，36（3）：284-288.

［10］郭春.基于數據挖掘的網絡入侵檢測［D］.北京：北京郵電大學，2014.

GUO Chun.Network Intrusion Detection based on Data Mining［D］.Beijing：Beijing University of Posts and Telecommunications，2014.

［11］韓占柱.改進k-means算法的網絡數據庫入侵檢測［J］.微電子學與計算機，2012，29（3）：144-150.

HAN Zhanzhu.Intrusion Detection of Network Database based on Improved K-means Algorithm［J］.Microellectronics&Computer，2012，29（3）：144-150.

［12］Ramze R M，Lelieveldt B P F，Reiber J H C.A new cluster validity indexes for the fuzzy c-means.Pattern Recognition Letters，1998，19（1）：237-246.

［13］韓凌波.K均值算法中聚類個數優化問題研究［J］.四川理工學院學報，2012，25（2）：77-80.

HAN Lingbo.Research on Clustering Number Optimization in K mean Algorithm［J］.Journal of Sichuan University of Science and Engineering，2012，25（2）：77-80.

［14］TZORTZIS G，LIKAS A.The minmax k-means clustering algorithm［J］.Pattern Recognition，2011，44（4）：866-876.

［15］蔣大宇.快速有效的并行二分K均值算法［D］.哈爾濱：哈爾濱工程大學，2013.

JIANG Dayu.Fast Efficient Parallel Two K mean Algorithm［D］.Harbin：Harbin Engineering University，2013.

［16］朱建宇.K均值算法研究及其應用［D］.大連：大連理工大學，2013.

JIANG Dayu.Research and application of K mean algorithm［D］.Dalian：Dalian University of Technology，2013.

Intrusion Detection Algorithm Based on Improved K-means Clustering

HE Mingliang1CHEN Zemao1HUANG Xiangjing2
（1.Information Security Department，Naval University of Engineering，Wuhan430033）（2.No.91681 Troops of PLA，Ningbo315731）

In order to solve the problems of the existing intrusion detection system，such as the complexity of the maintenance and management of the rule base，the lack of the detection efficiency of the system，an intrusion rule mining algorithm based on improved K mean clustering algorithm is designed.Firstly，according to the problem that the traditional K-means algorithm is not sure of the number of clusters，by analyzing the relationship between the number of clusters and the distance between clusters and inter clusters，the dynamic function is introduced to determine the optimal number of clusters.Then，the selection of initial cluster centers is optimized by finding the data intensive regions to avoid outliers，which improves the efficiency of the algorithm.The intrusion rule mining algorithm based on improved k-means clustering algorithm can quickly and effectively do cluster analysis on large data sets，and solve the problems of traditional intrusion detection system，such as the complexity of rule base and difficulty of detecting unknown attacks.

intrusion detection，data mining，k-means algorithm，clustering analysis，rule base

TP393

10.3969/j.issn.1672-9722.2017.06.028

2016年12月7日，

2017年1月18日

湖北省自然科學基金資助項目（編號：2015CF867）資助。

何明亮，男，碩士，研究方向：信息安全。陳澤茂，男，博士，教授，研究方向：網絡安全。黃相靜，男，研究方向：信息安全。