0 引言

　　聚類分析是將海量的數據劃分為有意義或者有用的組（簇）。在同一簇中的數據相似度較高，不同的簇中數據差別比較大。聚類分析主要基于距離進行分析，它是一種無監視的學習訓練方式。

　　K-means聚類算法是基于劃分的經典算法，但存在難以確定初始聚類中心值、受噪聲及孤立點影響較大的缺點[1]。基于此，很多學者研究提出了不同的改進K-means聚類算法的方法。參考文獻[2]把相互距離最遠的K個高密度區域的點作為初始聚類中心點；參考文獻[3]利用密度指針初始化聚類中心，從而從真實聚類中心中選取數據庫初始化聚類中心；參考文獻[4]利用密度和最近鄰的思想來尋找初始聚類中心；參考文獻[5]基于最優劃分初始聚類中心，該算法首先對數據樣本進行劃分，根據劃分樣本的分布特點確定初始聚類中心；參考文獻[6]利用偽隨機數產生初始聚類中心，但聚類數據龐大時，聚類效果不容樂觀。參考文獻[7]通過對樣本數據進行閾值分層快速確定K-means算法的聚類數搜索范圍及其上限，利用新的聚類有效性指標評價聚類后類內與類間的相似性程度，從而在聚類數搜索范圍內獲得最佳聚類數。

1 聚類分析的相似性度量和準則函數

　　1.1 相似性度量

　　聚類分析是依據對象兩兩之間的相似(或差異)程度來劃分類的，而這相似程度通常是用距離來衡量的[8]。最廣泛使用的距離計算公式是歐氏距離：

　　其中，i=(xi1，xi2，…，xip)，j=(xj1，xj2，…，xjp)。

　　1.2 準則函數

　　聚類結果的質量可以由聚類準則函數來判斷，若準則函數選的好，質量就會高；反之，質量達不到要求時，則須反復運行聚類過程[9]。一般的聚類準則函數有以下3種：(1)誤差平方和準則；(2)加權平均平方距離和準則；(3)加權類間距離和準則。

2 K-means聚類算法分析

　　2.1 K-means算法過程

　　K-means聚類的算法流程如下：

　　輸入：含有n個對象的數據集X={xi|xi∈Rd，i=1，2，…，n}，聚類的個數k。

　　輸出：k個類W1，W2，…，Wk。

　　(1)從數據集X中隨機選取k個初始聚類中心c1，c2，…，ck。

　　(2)依據初始聚類中心c1，c2，…，ck對數據集進行劃分，劃分根據以下原則：若dij(xi，cj)<dim(xi，cm)，其中dij(xi，cj)是xi與cj的歐式距離，m=1，2，…，k，j=1，2，…，k，j≠m，i=1，2，…，n，則將xi劃分到類cj。

　　(3)依據公式，ni為以聚類Ci為中心數據對象的個數，重新計算類的質心。

　　(5)輸出聚類結果。

　　K-means聚類算法的流程如圖1所示。

　　2.2 K-means算法缺點

　　(1)K-means算法需要首先設定K值，而算法運算中K是一個敏感值，不同的K值可能會造成不同的運算結果。

　　(2)對于一些噪聲和孤立的數據較為敏感。

　　(3)簇的平均值只有被定義才能使用，這不利于處理一些有特殊屬性的數據。

　　2.3 K-means算法的改進

　　(1)改進初始值K，盡量減少人工干預

　　利用類間相異度與類內相異度來確定最終的K值，具體分3步來實現：首先，選取數據集合的中間點即所有數據集合的平均值，利用歐幾里得距離計算公式，計算出距離中間點最遠距離的對象N1，再計算出與N1距離最遠的對象N2，篩選出初始聚類中心。其次計算剩余數據對象與數據中心集合間的距離，取最小距離D，計算聚類中心之間的距離，找出最小距離C，如果D<C，則將對象放入到最小距離的聚合中，否則將其納入初始聚合中心，生成新的聚合中心，后面的數據依次與聚合中心間最小距離與D對比，循環所有數據，最終形成聚類中心集。最后，采用類間相異度與類內相異度來確定最終的聚類個數K值。

　　類內的相異程度DOC：

　　類間相異度DAC：

　　其中，nc表示聚類的數目，mi表示類Cj中心，xkj表示Cj中的第k個數據對象的第j個屬性值，d(mi，mj)表示Ci與Cj間的歐幾里得距離，表示類中第j個屬性值。

　　改進后的計算方法如下：

　　輸入：含有n個對象的數據集X={xi|xi∈Rd，i=1，2，…，n}。

　　輸出：k個類W1，W2，…，Wk。

　　①對聚類中心進行初始化，獲得3個聚類中心。根據公式計算出第1個聚類中心m0，再根據歐幾里得距離計算出與m0最遠的數據對象作為第2個聚類中心m1，最后計算出與m1距離最遠的數據對象當成第3個聚類中心m2。

　　②根據歐幾里得公式計算數據集和聚類中心的距離，歸類所有數據，重新計算聚類中心。

　　③計算剩余數據對象與聚類中心的最小距離D及聚類中心之間的最小距離C， 計算出此時的類內相異度DOC_old 和此時的類間相異度DAC_old。

　　④如果D>C，則把這個數據對象作為新的聚類中心，并且計算新的類內相異度DOC_new和新的類間相異度DAC_new，運行步驟⑤；否則轉到步驟⑥。

　　⑤如果DOC_new<DOC_old且DAC_new>DAC_old則產生新類，轉到步驟②重復步驟②～⑤；否則恢復狀態，執行步驟⑥。

　　⑥取下一個類Wi，如果沒有新的類，則轉到步驟⑦；否則反復執行步驟②～⑤。

　　⑦輸出聚類結果。

　　(2)對噪聲和孤立點處理能力的改進

　　有時孤立點或噪聲具有入侵特征，容易干擾 K-means算法的聚類結果，這里改進原始算法來消弱噪聲和孤立點的影響。對于數據集中的所有點i，計算出每一點與剩余點的距離和Si，同時計算出距離均和H，當Si>H時，則點i被當做孤立點處理。其中n為樣本數據，d為數據維數。計算如下：

　　算法描述如下：

　　①輸入數據集，利用上述公式計算每一Si和H；

　　②對于每一點i，如果Si>H，則將i作為孤立點；

　　③刪除孤立點，獲得新的數據集。

3 改進算法在入侵檢測系統中的應用及仿真分析

　　針對于入侵檢測系統的缺陷,給出了基于改進算法的入侵檢測模型流程，如圖2所示。

　　系統檢測的對象是網絡日志中的數據。先做標準化處理，再進行聚類分析。通過篩選孤立點和改進聚類中心從而提高聚類的準確性。接著進入決策報警分析系統。根據聚類的結果甄別具有攻擊特征的記錄，一旦發現潛在威脅馬上啟動報警系統，阻止相關攻擊的進一步操作，并報告網絡管理者，與此同時挖掘其他的潛在特征，為以后判斷攻擊提供必要的依據。若沒有發現攻擊行為則繼續監視網絡動態。對網絡日志文件進行標準化的同時，也將其存入歷史數據庫中。并進行標準化處理和特征挖掘，進而數據匹配分類，構建成分類器。在分類器的反復訓練下可從這些記錄中挖掘出正常和非正常行為，并存入到規則庫中，作為今后判斷入侵行為的決策機構。

　　表1列出的是20條網絡連接記錄的特征數據。其中，count表示目標主機與當前連接相同的次數；SY_error表示SYN錯誤連接所占的百分數；same_srv表示目標端口相同連接的百分數；Dif_srv表示目標端口不同連接的百分數；Srv_count表示目標主機與當前連接相同的次數；Srv_serror表示SYN連接錯誤的百分數；Rv_dif_host表示目標端口不同連接的百分數[10]。本文主要對三維數組（count，Srv_serror，Srv_count）進行分析。三組特征數據的空間分布圖如圖3所示。

　　這個三維數組基本顯示了數據是否具有攻擊特征。通過分析這3個參數可以區分攻擊行為、異常行為和正常行為。當目標端口與當前連接相同的次數大于15次，并且主機出現錯誤SYN連接的百分數大于85％，目標端口與當前連接相同次數大于25次時認為是攻擊行為；若目標端口與當前連接相同的次數大于6次，并且主機出現錯誤SYN連接的百分數大于75％，目標端口與當前連接相同次數大于6次時認為是異常行為；其他則認為是正常行為。

　　采用傳統的 K-means 算法聚類分析3組數據后將20條數據信息分為3類：記錄3為攻擊行為(即圖4中圓形區域)；記錄4，5，6，12，13，19，20為異常行為(即圖4中橢圓區域)；其余的記錄為正常行為(即圖4中矩形區域)。根據上述3種行為的特征，可以將攻擊、異常和正常行為區分開來。傳統K-means 算法卻不能進一步分析異常行為是否有攻擊特征。傳統K-means 算法對實驗數據聚類分析的空間結果如圖4所示。

　　改進算法會分離出記錄3（孤立點），并判斷其為攻擊行為，如圖5中圓形區域。改進的K-means 算法將剩余的19條記錄聚類為三部分，記錄4，5，6，12，13，19，20為異常行為(如圖5中橢圓區域)，其中5，19接近于攻擊行為(如圖5中正方形區域)。其余的記錄為正常行為。改進算法有效地提高了檢測的準確率。改進的K-means 算法對實驗數據聚類分析的空間結果如圖5所示。

4 總結

　　本文簡單介紹了K-means算法，詳細闡述了對算法的改進，針對聚類算法中心個數難以確定的問題，本文改進了傳統K-means聚類算法中心個數確定的方法，提出了一種新的中心個數確定算法。同時對傳統K-means算法進行進一步的改進，以減少數據中噪聲點和孤立點對聚類精度的影響。并將傳統K-means算法和改進的K-means算法應用于入侵檢測系統中。實驗結果發現，基于改進的K-means算法的入侵檢測系統具有更好的入侵檢測效果，改進算法不僅降低了關鍵參數的敏感性，提高了區分精度，還在一定程度上提高了網絡入侵檢測的檢測率，降低了誤檢率。

參考文獻

　　[1] 曹永春，蔡正琦，邵亞斌.基于K-means的改進人工蜂群聚類算法[J]．計算機應用，2014，34(1)：204-207.

　　[2] 傅德勝，周辰.基于密度的改進K均值算法及實現[J].計算機應用，2011，31(2)：432-434．

　　[3] 牛琨，張舒博，陳俊亮．融合網格密度的聚類中心初始化方案[J]．北京郵電大學學報，2007，30(2)：6-10．

　　[4] 張文明，吳江，袁小蛟.基于密度和最近鄰的K-means文本聚類算法[J].計算機應用，2010，30(7)：1933-1935.

　　[5] 崔斌，盧陽.基于不確定數據的查詢處理綜述[J]．計算機應用，2008，28(11)：2729-2731.

　　[6] KOLEN J F，HNTCHESON T.Redneing the time complexityof the fuzzy c-means algorithm[J]．IEEE Transactions on Fuzzy Systems，2002，10(2)：263-267.

　　[7] 王勇，唐靖，饒勤菲，等.高效率的K-means最佳聚類數確定算法[J]．計算機應用，2014，34(5)：1331-1335.

　　[8] 呂明磊，劉東梅，曾智勇.基于改進的K-means算法的圖像檢索算法[J]．計算機應用，2013，33(S1)：195-198.

　　[9] 雷小鋒，謝昆青，林帆，等.一種基于K-means局部最優性的高效聚類算法[J]．軟件學報，2008，19(7)：1683-1692.

　　[10] 高紅艷，劉飛.基于局部相似性的K-means譜聚類算法[J]．小型微型計算機系統，2014，35(5)：1133-1134.