文獻標(biāo)識碼: A
文章編號: 0258-7998(2015)01-0125-04
0 引言
聚類分析是將海量的數(shù)據(jù)劃分為有意義或者有用的組(簇)。在同一簇中的數(shù)據(jù)相似度較高,不同的簇中數(shù)據(jù)差別比較大。聚類分析主要基于距離進行分析,它是一種無監(jiān)視的學(xué)習(xí)訓(xùn)練方式。
K-means聚類算法是基于劃分的經(jīng)典算法,但存在難以確定初始聚類中心值、受噪聲及孤立點影響較大的缺點[1]?;诖?,很多學(xué)者研究提出了不同的改進K-means聚類算法的方法。參考文獻[2]把相互距離最遠的K個高密度區(qū)域的點作為初始聚類中心點;參考文獻[3]利用密度指針初始化聚類中心,從而從真實聚類中心中選取數(shù)據(jù)庫初始化聚類中心;參考文獻[4]利用密度和最近鄰的思想來尋找初始聚類中心;參考文獻[5]基于最優(yōu)劃分初始聚類中心,該算法首先對數(shù)據(jù)樣本進行劃分,根據(jù)劃分樣本的分布特點確定初始聚類中心;參考文獻[6]利用偽隨機數(shù)產(chǎn)生初始聚類中心,但聚類數(shù)據(jù)龐大時,聚類效果不容樂觀。參考文獻[7]通過對樣本數(shù)據(jù)進行閾值分層快速確定K-means算法的聚類數(shù)搜索范圍及其上限,利用新的聚類有效性指標(biāo)評價聚類后類內(nèi)與類間的相似性程度,從而在聚類數(shù)搜索范圍內(nèi)獲得最佳聚類數(shù)。
1 聚類分析的相似性度量和準(zhǔn)則函數(shù)
1.1 相似性度量
聚類分析是依據(jù)對象兩兩之間的相似(或差異)程度來劃分類的,而這相似程度通常是用距離來衡量的[8]。最廣泛使用的距離計算公式是歐氏距離:
其中,i=(xi1,xi2,…,xip),j=(xj1,xj2,…,xjp)。
1.2 準(zhǔn)則函數(shù)
聚類結(jié)果的質(zhì)量可以由聚類準(zhǔn)則函數(shù)來判斷,若準(zhǔn)則函數(shù)選的好,質(zhì)量就會高;反之,質(zhì)量達不到要求時,則須反復(fù)運行聚類過程[9]。一般的聚類準(zhǔn)則函數(shù)有以下3種:(1)誤差平方和準(zhǔn)則;(2)加權(quán)平均平方距離和準(zhǔn)則;(3)加權(quán)類間距離和準(zhǔn)則。
2 K-means聚類算法分析
2.1 K-means算法過程
K-means聚類的算法流程如下:
輸入:含有n個對象的數(shù)據(jù)集X={xi|xi∈Rd,i=1,2,…,n},聚類的個數(shù)k。
輸出:k個類W1,W2,…,Wk。
(1)從數(shù)據(jù)集X中隨機選取k個初始聚類中心c1,c2,…,ck。
(2)依據(jù)初始聚類中心c1,c2,…,ck對數(shù)據(jù)集進行劃分,劃分根據(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劃分到類cj。
(3)依據(jù)公式,ni為以聚類Ci為中心數(shù)據(jù)對象的個數(shù),重新計算類的質(zhì)心
。
(5)輸出聚類結(jié)果。
K-means聚類算法的流程如圖1所示。
2.2 K-means算法缺點
(1)K-means算法需要首先設(shè)定K值,而算法運算中K是一個敏感值,不同的K值可能會造成不同的運算結(jié)果。
(2)對于一些噪聲和孤立的數(shù)據(jù)較為敏感。
(3)簇的平均值只有被定義才能使用,這不利于處理一些有特殊屬性的數(shù)據(jù)。
2.3 K-means算法的改進
(1)改進初始值K,盡量減少人工干預(yù)
利用類間相異度與類內(nèi)相異度來確定最終的K值,具體分3步來實現(xiàn):首先,選取數(shù)據(jù)集合的中間點即所有數(shù)據(jù)集合的平均值,利用歐幾里得距離計算公式,計算出距離中間點最遠距離的對象N1,再計算出與N1距離最遠的對象N2,篩選出初始聚類中心。其次計算剩余數(shù)據(jù)對象與數(shù)據(jù)中心集合間的距離,取最小距離D,計算聚類中心之間的距離,找出最小距離C,如果D<C,則將對象放入到最小距離的聚合中,否則將其納入初始聚合中心,生成新的聚合中心,后面的數(shù)據(jù)依次與聚合中心間最小距離與D對比,循環(huán)所有數(shù)據(jù),最終形成聚類中心集。最后,采用類間相異度與類內(nèi)相異度來確定最終的聚類個數(shù)K值。
類內(nèi)的相異程度DOC:
類間相異度DAC:
其中,nc表示聚類的數(shù)目,mi表示類Cj中心,xkj表示Cj中的第k個數(shù)據(jù)對象的第j個屬性值,d(mi,mj)表示Ci與Cj間的歐幾里得距離,表示類中第j個屬性值。
改進后的計算方法如下:
輸入:含有n個對象的數(shù)據(jù)集X={xi|xi∈Rd,i=1,2,…,n}。
輸出:k個類W1,W2,…,Wk。
?、賹垲愔行倪M行初始化,獲得3個聚類中心。根據(jù)公式計算出第1個聚類中心m0,再根據(jù)歐幾里得距離計算出與m0最遠的數(shù)據(jù)對象作為第2個聚類中心m1,最后計算出與m1距離最遠的數(shù)據(jù)對象當(dāng)成第3個聚類中心m2。
②根據(jù)歐幾里得公式計算數(shù)據(jù)集和聚類中心的距離,歸類所有數(shù)據(jù),重新計算聚類中心。
?、塾嬎闶S鄶?shù)據(jù)對象與聚類中心的最小距離D及聚類中心之間的最小距離C, 計算出此時的類內(nèi)相異度DOC_old 和此時的類間相異度DAC_old。
?、苋绻鸇>C,則把這個數(shù)據(jù)對象作為新的聚類中心,并且計算新的類內(nèi)相異度DOC_new和新的類間相異度DAC_new,運行步驟⑤;否則轉(zhuǎn)到步驟⑥。
?、萑绻鸇OC_new<DOC_old且DAC_new>DAC_old則產(chǎn)生新類,轉(zhuǎn)到步驟②重復(fù)步驟②~⑤;否則恢復(fù)狀態(tài),執(zhí)行步驟⑥。
?、奕∠乱粋€類Wi,如果沒有新的類,則轉(zhuǎn)到步驟⑦;否則反復(fù)執(zhí)行步驟②~⑤。
⑦輸出聚類結(jié)果。
(2)對噪聲和孤立點處理能力的改進
有時孤立點或噪聲具有入侵特征,容易干擾 K-means算法的聚類結(jié)果,這里改進原始算法來消弱噪聲和孤立點的影響。對于數(shù)據(jù)集中的所有點i,計算出每一點與剩余點的距離和Si,同時計算出距離均和H,當(dāng)Si>H時,則點i被當(dāng)做孤立點處理。其中n為樣本數(shù)據(jù),d為數(shù)據(jù)維數(shù)。計算如下:
算法描述如下:
?、佥斎霐?shù)據(jù)集,利用上述公式計算每一Si和H;
?、趯τ诿恳稽ci,如果Si>H,則將i作為孤立點;
?、蹌h除孤立點,獲得新的數(shù)據(jù)集。
3 改進算法在入侵檢測系統(tǒng)中的應(yīng)用及仿真分析
針對于入侵檢測系統(tǒng)的缺陷,給出了基于改進算法的入侵檢測模型流程,如圖2所示。
系統(tǒng)檢測的對象是網(wǎng)絡(luò)日志中的數(shù)據(jù)。先做標(biāo)準(zhǔn)化處理,再進行聚類分析。通過篩選孤立點和改進聚類中心從而提高聚類的準(zhǔn)確性。接著進入決策報警分析系統(tǒng)。根據(jù)聚類的結(jié)果甄別具有攻擊特征的記錄,一旦發(fā)現(xiàn)潛在威脅馬上啟動報警系統(tǒng),阻止相關(guān)攻擊的進一步操作,并報告網(wǎng)絡(luò)管理者,與此同時挖掘其他的潛在特征,為以后判斷攻擊提供必要的依據(jù)。若沒有發(fā)現(xiàn)攻擊行為則繼續(xù)監(jiān)視網(wǎng)絡(luò)動態(tài)。對網(wǎng)絡(luò)日志文件進行標(biāo)準(zhǔn)化的同時,也將其存入歷史數(shù)據(jù)庫中。并進行標(biāo)準(zhǔn)化處理和特征挖掘,進而數(shù)據(jù)匹配分類,構(gòu)建成分類器。在分類器的反復(fù)訓(xùn)練下可從這些記錄中挖掘出正常和非正常行為,并存入到規(guī)則庫中,作為今后判斷入侵行為的決策機構(gòu)。
表1列出的是20條網(wǎng)絡(luò)連接記錄的特征數(shù)據(jù)。其中,count表示目標(biāo)主機與當(dāng)前連接相同的次數(shù);SY_error表示SYN錯誤連接所占的百分?jǐn)?shù);same_srv表示目標(biāo)端口相同連接的百分?jǐn)?shù);Dif_srv表示目標(biāo)端口不同連接的百分?jǐn)?shù);Srv_count表示目標(biāo)主機與當(dāng)前連接相同的次數(shù);Srv_serror表示SYN連接錯誤的百分?jǐn)?shù);Rv_dif_host表示目標(biāo)端口不同連接的百分?jǐn)?shù)[10]。本文主要對三維數(shù)組(count,Srv_serror,Srv_count)進行分析。三組特征數(shù)據(jù)的空間分布圖如圖3所示。
這個三維數(shù)組基本顯示了數(shù)據(jù)是否具有攻擊特征。通過分析這3個參數(shù)可以區(qū)分攻擊行為、異常行為和正常行為。當(dāng)目標(biāo)端口與當(dāng)前連接相同的次數(shù)大于15次,并且主機出現(xiàn)錯誤SYN連接的百分?jǐn)?shù)大于85%,目標(biāo)端口與當(dāng)前連接相同次數(shù)大于25次時認為是攻擊行為;若目標(biāo)端口與當(dāng)前連接相同的次數(shù)大于6次,并且主機出現(xiàn)錯誤SYN連接的百分?jǐn)?shù)大于75%,目標(biāo)端口與當(dāng)前連接相同次數(shù)大于6次時認為是異常行為;其他則認為是正常行為。
采用傳統(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 算法卻不能進一步分析異常行為是否有攻擊特征。傳統(tǒng)K-means 算法對實驗數(shù)據(jù)聚類分析的空間結(jié)果如圖4所示。
改進算法會分離出記錄3(孤立點),并判斷其為攻擊行為,如圖5中圓形區(qū)域。改進的K-means 算法將剩余的19條記錄聚類為三部分,記錄4,5,6,12,13,19,20為異常行為(如圖5中橢圓區(qū)域),其中5,19接近于攻擊行為(如圖5中正方形區(qū)域)。其余的記錄為正常行為。改進算法有效地提高了檢測的準(zhǔn)確率。改進的K-means 算法對實驗數(shù)據(jù)聚類分析的空間結(jié)果如圖5所示。
4 總結(jié)
本文簡單介紹了K-means算法,詳細闡述了對算法的改進,針對聚類算法中心個數(shù)難以確定的問題,本文改進了傳統(tǒng)K-means聚類算法中心個數(shù)確定的方法,提出了一種新的中心個數(shù)確定算法。同時對傳統(tǒng)K-means算法進行進一步的改進,以減少數(shù)據(jù)中噪聲點和孤立點對聚類精度的影響。并將傳統(tǒng)K-means算法和改進的K-means算法應(yīng)用于入侵檢測系統(tǒng)中。實驗結(jié)果發(fā)現(xiàn),基于改進的K-means算法的入侵檢測系統(tǒng)具有更好的入侵檢測效果,改進算法不僅降低了關(guān)鍵參數(shù)的敏感性,提高了區(qū)分精度,還在一定程度上提高了網(wǎng)絡(luò)入侵檢測的檢測率,降低了誤檢率。
參考文獻
[1] 曹永春,蔡正琦,邵亞斌.基于K-means的改進人工蜂群聚類算法[J].計算機應(yīng)用,2014,34(1):204-207.
[2] 傅德勝,周辰.基于密度的改進K均值算法及實現(xiàn)[J].計算機應(yīng)用,2011,31(2):432-434.
[3] 牛琨,張舒博,陳俊亮.融合網(wǎng)格密度的聚類中心初始化方案[J].北京郵電大學(xué)學(xué)報,2007,30(2):6-10.
[4] 張文明,吳江,袁小蛟.基于密度和最近鄰的K-means文本聚類算法[J].計算機應(yīng)用,2010,30(7):1933-1935.
[5] 崔斌,盧陽.基于不確定數(shù)據(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最佳聚類數(shù)確定算法[J].計算機應(yīng)用,2014,34(5):1331-1335.
[8] 呂明磊,劉東梅,曾智勇.基于改進的K-means算法的圖像檢索算法[J].計算機應(yīng)用,2013,33(S1):195-198.
[9] 雷小鋒,謝昆青,林帆,等.一種基于K-means局部最優(yōu)性的高效聚類算法[J].軟件學(xué)報,2008,19(7):1683-1692.
[10] 高紅艷,劉飛.基于局部相似性的K-means譜聚類算法[J].小型微型計算機系統(tǒng),2014,35(5):1133-1134.