0 引言

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

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

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

　　1.1 相似性度量

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

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

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

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

2 K-means聚類(lèi)算法分析

　　2.1 K-means算法過(guò)程

　　K-means聚類(lèi)的算法流程如下：

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

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

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

　　(2)依據(jù)初始聚類(lèi)中心c1，c2，…，ck對(duì)數(shù)據(jù)集進(jìn)行劃分，劃分根據(jù)以下原則：若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劃分到類(lèi)cj。

　　(3)依據(jù)公式，ni為以聚類(lèi)Ci為中心數(shù)據(jù)對(duì)象的個(gè)數(shù)，重新計(jì)算類(lèi)的質(zhì)心。

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

　　K-means聚類(lèi)算法的流程如圖1所示。

　　2.2 K-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.3 K-means算法的改進(jìn)

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

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

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

　　類(lèi)間相異度DAC：

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

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

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

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

　　①對(duì)聚類(lèi)中心進(jìn)行初始化，獲得3個(gè)聚類(lèi)中心。根據(jù)公式計(jì)算出第1個(gè)聚類(lèi)中心m0，再根據(jù)歐幾里得距離計(jì)算出與m0最遠(yuǎn)的數(shù)據(jù)對(duì)象作為第2個(gè)聚類(lèi)中心m1，最后計(jì)算出與m1距離最遠(yuǎn)的數(shù)據(jù)對(duì)象當(dāng)成第3個(gè)聚類(lèi)中心m2。

　?、诟鶕?jù)歐幾里得公式計(jì)算數(shù)據(jù)集和聚類(lèi)中心的距離，歸類(lèi)所有數(shù)據(jù)，重新計(jì)算聚類(lèi)中心。

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

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

　?、萑绻鸇OC_new<DOC_old且DAC_new>DAC_old則產(chǎn)生新類(lèi)，轉(zhuǎn)到步驟②重復(fù)步驟②～⑤；否則恢復(fù)狀態(tài)，執(zhí)行步驟⑥。

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

　?、咻敵鼍垲?lèi)結(jié)果。

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

　　有時(shí)孤立點(diǎn)或噪聲具有入侵特征，容易干擾 K-means算法的聚類(lèi)結(jié)果，這里改進(jìn)原始算法來(lái)消弱噪聲和孤立點(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)；

　?、蹌h除孤立點(diǎn)，獲得新的數(shù)據(jù)集。

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

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

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

　　這個(gè)三維數(shù)組基本顯示了數(shù)據(jù)是否具有攻擊特征。通過(guò)分析這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 算法聚類(lèi)分析3組數(shù)據(jù)后將20條數(shù)據(jù)信息分為3類(lèi)：記錄3為攻擊行為(即圖4中圓形區(qū)域)；記錄4，5，6，12，13，19，20為異常行為(即圖4中橢圓區(qū)域)；其余的記錄為正常行為(即圖4中矩形區(qū)域)。根據(jù)上述3種行為的特征，可以將攻擊、異常和正常行為區(qū)分開(kāi)來(lái)。傳統(tǒng)K-means 算法卻不能進(jìn)一步分析異常行為是否有攻擊特征。傳統(tǒng)K-means 算法對(duì)實(shí)驗(yàn)數(shù)據(jù)聚類(lèi)分析的空間結(jié)果如圖4所示。

　　改進(jìn)算法會(huì)分離出記錄3（孤立點(diǎn)），并判斷其為攻擊行為，如圖5中圓形區(qū)域。改進(jìn)的K-means 算法將剩余的19條記錄聚類(lèi)為三部分，記錄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ù)聚類(lèi)分析的空間結(jié)果如圖5所示。

4 總結(jié)

　　本文簡(jiǎn)單介紹了K-means算法，詳細(xì)闡述了對(duì)算法的改進(jìn)，針對(duì)聚類(lèi)算法中心個(gè)數(shù)難以確定的問(wèn)題，本文改進(jìn)了傳統(tǒng)K-means聚類(lèi)算法中心個(gè)數(shù)確定的方法，提出了一種新的中心個(gè)數(shù)確定算法。同時(shí)對(duì)傳統(tǒng)K-means算法進(jìn)行進(jìn)一步的改進(jìn)，以減少數(shù)據(jù)中噪聲點(diǎn)和孤立點(diǎn)對(duì)聚類(lèi)精度的影響。并將傳統(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è)率，降低了誤檢率。

參考文獻(xiàn)

　　[1] 曹永春，蔡正琦，邵亞斌.基于K-means的改進(jìn)人工蜂群聚類(lèi)算法[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)格密度的聚類(lèi)中心初始化方案[J]．北京郵電大學(xué)學(xué)報(bào)，2007，30(2)：6-10．

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

　　[5] 崔斌，盧陽(yáng).基于不確定數(shù)據(jù)的查詢(xún)處理綜述[J]．計(jì)算機(jī)應(yīng)用，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最佳聚類(lèi)數(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)性的高效聚類(lèi)算法[J]．軟件學(xué)報(bào)，2008，19(7)：1683-1692.

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