張　杰，卓　靈，朱韻攸

(國(guó)家電網(wǎng)重慶市電力公司信息通信分公司，重慶401121)

一種K-means聚類算法的改進(jìn)與應(yīng)用

張杰，卓靈，朱韻攸

(國(guó)家電網(wǎng)重慶市電力公司信息通信分公司，重慶401121)

K-means算法是基于距離作為相似性度量的聚類算法，傳統(tǒng)的K-means算法存在難以確定中心值個(gè)數(shù)、受噪聲及孤立點(diǎn)影響較大的缺點(diǎn)。對(duì)此，利用類間相異度與類內(nèi)相異度改進(jìn)初始值K，以盡量減少人工干預(yù)；同時(shí)計(jì)算數(shù)據(jù)庫中每一點(diǎn)與剩余點(diǎn)的距離和距離均和，將兩者的大小比較作為識(shí)別孤立點(diǎn)和噪聲點(diǎn)的依據(jù)，從而刪除孤立點(diǎn)，減少對(duì)數(shù)據(jù)聚類劃分的影響。最后將改進(jìn)后的K-means算法應(yīng)用于入侵檢測(cè)系統(tǒng)并進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，基于改進(jìn)的K-means算法的入侵檢測(cè)系統(tǒng)一定程度上降低了誤報(bào)率及誤檢率，提高了檢測(cè)的準(zhǔn)確率。

數(shù)據(jù)挖掘；聚類算法；K-means；入侵檢測(cè)

0　引言

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

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

1　聚類分析的相似性度量和準(zhǔn)則函數(shù)

1.1相似性度量

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

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

1.2準(zhǔn)則函數(shù)

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

2　K-means聚類算法分析

2.1K-means算法過程

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

輸入：含有 n個(gè)對(duì)象的數(shù)據(jù)集 X={xi|xi∈Rd，i=1，2，…，n}，聚類的個(gè)數(shù)k。

輸出：k個(gè)類W1，W2，…，Wk。

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

(2)依據(jù)初始聚類中心 c1，c2，…，ck對(duì)數(shù)據(jù)集進(jìn)行劃分，劃分根據(jù)以下原則：若 dij(xi，cj)

(5)輸出聚類結(jié)果。

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

圖1　K-means聚類算法流程圖

2.2K-means算法缺點(diǎn)

(1)K-means算法需要首先設(shè)定K值，而算法運(yùn)算中K是一個(gè)敏感值，不同的K值可能會(huì)造成不同的運(yùn)算結(jié)果。

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

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

2.3K-means算法的改進(jìn)

(1)改進(jìn)初始值 K，盡量減少人工干預(yù)

利用類間相異度與類內(nèi)相異度來確定最終的K值，具體分3步來實(shí)現(xiàn)：首先，選取數(shù)據(jù)集合的中間點(diǎn)即所有數(shù)據(jù)集合的平均值，利用歐幾里得距離計(jì)算公式，計(jì)算出距離中間點(diǎn)最遠(yuǎn)距離的對(duì)象N1，再計(jì)算出與N1距離最遠(yuǎn)的對(duì)象N2，篩選出初始聚類中心。其次計(jì)算剩余數(shù)據(jù)對(duì)象與數(shù)據(jù)中心集合間的距離，取最小距離D，計(jì)算聚類中心之間的距離，找出最小距離C，如果D

類內(nèi)的相異程度DOC：

類間相異度DAC：

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

改進(jìn)后的計(jì)算方法如下：

輸入：含有 n 個(gè)對(duì)象的數(shù)據(jù)集X={xi|xi∈Rd，i=1，2，…，n}。

輸出：k個(gè)類W1，W2，…，Wk。

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

③計(jì)算剩余數(shù)據(jù)對(duì)象與聚類中心的最小距離D及聚類中心之間的最小距離C，計(jì)算出此時(shí)的類內(nèi)相異度DOC_old和此時(shí)的類間相異度DAC_old。

④如果D>C，則把這個(gè)數(shù)據(jù)對(duì)象作為新的聚類中心，并且計(jì)算新的類內(nèi)相異度DOC_new和新的類間相異度DAC_new，運(yùn)行步驟⑤；否則轉(zhuǎn)到步驟⑥。

⑤如果DOC_newDAC_old則產(chǎn)生新類，轉(zhuǎn)到步驟②重復(fù)步驟②～⑤；否則恢復(fù)狀態(tài)，執(zhí)行步驟⑥。

⑥取下一個(gè)類Wi，如果沒有新的類，則轉(zhuǎn)到步驟⑦；否則反復(fù)執(zhí)行步驟②～⑤。

⑦輸出聚類結(jié)果。

(2)對(duì)噪聲和孤立點(diǎn)處理能力的改進(jìn)

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

算法描述如下：

①輸入數(shù)據(jù)集，利用上述公式計(jì)算每一Si和H；②對(duì)于每一點(diǎn) i，如果Si>H，則將 i作為孤立點(diǎn)；③刪除孤立點(diǎn)，獲得新的數(shù)據(jù)集。

3　改進(jìn)算法在入侵檢測(cè)系統(tǒng)中的應(yīng)用及仿真分析

針對(duì)于入侵檢測(cè)系統(tǒng)的缺陷,給出了基于改進(jìn)算法的入侵檢測(cè)模型流程，如圖2所示。

圖2　基于改進(jìn)K-means算法的入侵檢測(cè)流程圖

系統(tǒng)檢測(cè)的對(duì)象是網(wǎng)絡(luò)日志中的數(shù)據(jù)。先做標(biāo)準(zhǔn)化處理，再進(jìn)行聚類分析。通過篩選孤立點(diǎn)和改進(jìn)聚類中心從而提高聚類的準(zhǔn)確性。接著進(jìn)入決策報(bào)警分析系統(tǒng)。根據(jù)聚類的結(jié)果甄別具有攻擊特征的記錄，一旦發(fā)現(xiàn)潛在威脅馬上啟動(dòng)報(bào)警系統(tǒng)，阻止相關(guān)攻擊的進(jìn)一步操作，并報(bào)告網(wǎng)絡(luò)管理者，與此同時(shí)挖掘其他的潛在特征，為以后判斷攻擊提供必要的依據(jù)。若沒有發(fā)現(xiàn)攻擊行為則繼續(xù)監(jiān)視網(wǎng)絡(luò)動(dòng)態(tài)。對(duì)網(wǎng)絡(luò)日志文件進(jìn)行標(biāo)準(zhǔn)化的同時(shí)，也將其存入歷史數(shù)據(jù)庫中。并進(jìn)行標(biāo)準(zhǔn)化處理和特征挖掘，進(jìn)而數(shù)據(jù)匹配分類，構(gòu)建成分類器。在分類器的反復(fù)訓(xùn)練下可從這些記錄中挖掘出正常和非正常行為，并存入到規(guī)則庫中，作為今后判斷入侵行為的決策機(jī)構(gòu)。

表1列出的是20條網(wǎng)絡(luò)連接記錄的特征數(shù)據(jù)。其中，count表示目標(biāo)主機(jī)與當(dāng)前連接相同的次數(shù)；SY_error表示SYN錯(cuò)誤連接所占的百分?jǐn)?shù)；same_srv表示目標(biāo)端口相同連接的百分?jǐn)?shù)；Dif_srv表示目標(biāo)端口不同連接的百分?jǐn)?shù)；Srv_count表示目標(biāo)主機(jī)與當(dāng)前連接相同的次數(shù)；Srv_serror表示 SYN連接錯(cuò)誤的百分?jǐn)?shù)；Rv_dif_host表示目標(biāo)端口不同連接的百分?jǐn)?shù)[10]。本文主要對(duì)三維數(shù)組（count，Srv_serror，Srv_count）進(jìn)行分析。三組特征數(shù)據(jù)的空間分布圖如圖3所示。

表1　網(wǎng)絡(luò)連接記錄

圖3　三組特征數(shù)據(jù)的空間分布圖

這個(gè)三維數(shù)組基本顯示了數(shù)據(jù)是否具有攻擊特征。通過分析這3個(gè)參數(shù)可以區(qū)分攻擊行為、異常行為和正常行為。當(dāng)目標(biāo)端口與當(dāng)前連接相同的次數(shù)大于15次，并且主機(jī)出現(xiàn)錯(cuò)誤SYN連接的百分?jǐn)?shù)大于85%，目標(biāo)端口與當(dāng)前連接相同次數(shù)大于25次時(shí)認(rèn)為是攻擊行為；若目標(biāo)端口與當(dāng)前連接相同的次數(shù)大于6次，并且主機(jī)出現(xiàn)錯(cuò)誤SYN連接的百分?jǐn)?shù)大于75%，目標(biāo)端口與當(dāng)前連接相同次數(shù)大于6次時(shí)認(rèn)為是異常行為；其他則認(rèn)為是正常行為。

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

圖4　傳統(tǒng)K-means算法聚類空間結(jié)果

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

圖5　改進(jìn)K-means算法聚類分析的空間結(jié)果

4　總結(jié)

本文簡(jiǎn)單介紹了K-means算法，詳細(xì)闡述了對(duì)算法的改進(jìn)，針對(duì)聚類算法中心個(gè)數(shù)難以確定的問題，本文改進(jìn)了傳統(tǒng)K-means聚類算法中心個(gè)數(shù)確定的方法，提出了一種新的中心個(gè)數(shù)確定算法。同時(shí)對(duì)傳統(tǒng)K-means算法進(jìn)行進(jìn)一步的改進(jìn)，以減少數(shù)據(jù)中噪聲點(diǎn)和孤立點(diǎn)對(duì)聚類精度的影響。并將傳統(tǒng) K-means算法和改進(jìn)的K-means算法應(yīng)用于入侵檢測(cè)系統(tǒng)中。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，基于改進(jìn)的K-means算法的入侵檢測(cè)系統(tǒng)具有更好的入侵檢測(cè)效果，改進(jìn)算法不僅降低了關(guān)鍵參數(shù)的敏感性，提高了區(qū)分精度，還在一定程度上提高了網(wǎng)絡(luò)入侵檢測(cè)的檢測(cè)率，降低了誤檢率。

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

[2]傅德勝，周辰.基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2011，31(2)：432-434．

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

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

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

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

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

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

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

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

The improvement and application of a K-means clustering algorithm

Zhang Jie，Zhuo Ling，Zhu Yunyou
(Information&Communication Branch of State Grid Chongqing Electric Power Company，Chongqing 401121，China)

K-means algorithm is the clustering algorithm based on the distance as the similarity measure.But the traditional K-means algorithm are difficult to determine the center number,and greatly influenced by the noise and outliers.This paper uses the between class and within class dissimilarity to improve initial value K,so as to reduce the manual intervention.At the of same time,the distances between every point and the remaining points and the average in the database are calculated,which are the recognition gist of an isolated point and noise point to remove outliers and reduce the impact on data clustering partition.Finally, using the improved K-means algorithm in intrusion detection system and doing simulation experiments,the results show that based on the improved K-means algorithm，the detection system can decrease the false alarm rate and false detection rate,and improve the accuracy of detection.

data mining；clustering algorithm；K-means；intrusion detection

TP301

A

0258-7998(2015)01-0125-04

10.16157/j.cnki.0258-7998.2014071602638

2014-09-04)

張杰（1977-），男，博士，工程師，主要研究方向：通訊自動(dòng)化、計(jì)算機(jī)網(wǎng)絡(luò)。

卓靈（1985-），女，工程師，主要研究方向：信息設(shè)備與檢修管理。

朱韻攸（1985-），女，助理工程師，主要研究方向：信息系統(tǒng)運(yùn)行與安全。