基于改進(jìn)K-Means的網(wǎng)絡(luò)異常檢測(cè)

徐 翔

（廣東海洋大學(xué) 教育信息中心，廣東 湛江 524088）

0 引 言

隨著互聯(lián)網(wǎng)普及范圍的擴(kuò)大、網(wǎng)絡(luò)技術(shù)的優(yōu)化以及計(jì)算機(jī)硬件成本的降低，網(wǎng)絡(luò)用戶量劇增。網(wǎng)絡(luò)是為了方便現(xiàn)代社會(huì)運(yùn)行與發(fā)展而誕生的，但是在其提供諸多方便的同時(shí)攜帶較多安全隱患也是不可忽視的事實(shí)[1]。互聯(lián)網(wǎng)運(yùn)行過程中難免存在一些混淆正常安全數(shù)據(jù)傳輸?shù)姆欠ú僮鳎瑢惓Ｈ肭謹(jǐn)?shù)據(jù)與正常數(shù)據(jù)流量混為一談，通過DDoS攻擊或各類病毒攻擊威脅網(wǎng)絡(luò)安全，嚴(yán)重影響正常網(wǎng)絡(luò)的使用和網(wǎng)絡(luò)業(yè)務(wù)的有效開展[2,3]。因此，精準(zhǔn)高效識(shí)別網(wǎng)絡(luò)異常情況、檢測(cè)互聯(lián)網(wǎng)流量異常特征以及發(fā)現(xiàn)潛在攻擊威脅成為網(wǎng)絡(luò)健康運(yùn)行的基本要求。本次研究對(duì)K-Means聚類算法進(jìn)行優(yōu)化與改進(jìn)，在海量網(wǎng)絡(luò)信息流中識(shí)別異常特征信息，及早發(fā)現(xiàn)并阻止異常信息的傳播，營(yíng)造安全綠色的網(wǎng)絡(luò)環(huán)境。

1 基于改進(jìn)K-Means的分布式網(wǎng)絡(luò)異常檢測(cè)方法

1.1 MapReduce分布式計(jì)算環(huán)境構(gòu)建

大數(shù)據(jù)時(shí)代互聯(lián)網(wǎng)每分每秒都在產(chǎn)生海量信息數(shù)據(jù)，網(wǎng)絡(luò)異常流量規(guī)模不容小覷，為了提高海量網(wǎng)絡(luò)異常流量檢測(cè)效率，本次研究首先搭建MapReduce分布式計(jì)算環(huán)境，基于MapReduce分布式計(jì)算模型進(jìn)行并行化K-Means的網(wǎng)絡(luò)異常聚類挖掘[4]。

MapReduce計(jì)算模型以Map和Reduce函數(shù)為工具進(jìn)行并行化計(jì)算，二者集成并行編程接口，為海量網(wǎng)絡(luò)流量數(shù)據(jù)處理運(yùn)算提供便利條件。圖1描述了MapReduce模型執(zhí)行K-Means挖掘算法的分布式原理。

圖1 MapReduce模型執(zhí)行K-Means挖掘算法的分布式原理

基于MapReduce模型的K-Means算法實(shí)現(xiàn)并行化計(jì)算任務(wù)時(shí)，Map函數(shù)通過運(yùn)算獲得K-Means算法聚類結(jié)果，求取各個(gè)對(duì)象與聚類中心之間的距離，同時(shí)更新此對(duì)象所屬的聚類類別。Reduce函數(shù)將結(jié)果按照類別進(jìn)行劃分，相同類別數(shù)據(jù)歸類為一個(gè)簇，同時(shí)利用K-Means算法獲取網(wǎng)絡(luò)異常樣本數(shù)據(jù)聚類中心，將此結(jié)果作為下一次Map函數(shù)迭代運(yùn)算的輸入值，采用形式表述[5]。此過程中，Reduce任務(wù)負(fù)責(zé)接收全部key一致的數(shù)據(jù)，求取累計(jì)的key一致數(shù)據(jù)均值，然后獲取K-Means算法新的聚類中心，以此類推進(jìn)行迭代運(yùn)算，最終輸出結(jié)果采用形式表述。

1.2 改進(jìn)K-Means算法的網(wǎng)絡(luò)異常數(shù)據(jù)聚類

K-Means算法以原型目標(biāo)函數(shù)為基礎(chǔ)進(jìn)行硬聚類，在此類聚類算法中極具代表性，具體方式是確定原始聚類中心，通過數(shù)學(xué)方法運(yùn)算原始聚類中心與聚類對(duì)象樣本，從而得到新的聚類中心，完成精準(zhǔn)的數(shù)據(jù)樣本聚類[6]。MapReduce模型保障了K-Means挖掘算法的聚類效率，在此基礎(chǔ)上改進(jìn)傳統(tǒng)K-Means算法，基于最小生成樹確定K-Means算法的聚類中心，優(yōu)化K-Means挖掘網(wǎng)絡(luò)異常流量的精度。

K-Means算法基本思想包括3個(gè)部分。第一，任意選取l個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心；第二，一一求取其他對(duì)象同原始聚類中心間的歐氏距離，若干個(gè)對(duì)象與聚類中心最為接近，那么這些對(duì)象將劃分為同一類別；第三，更新算法的聚類中心，以此類推進(jìn)行數(shù)據(jù)迭代聚類，終止條件是不再生成新的聚類中心。K-Means算法挖掘數(shù)據(jù)過程中將聚類樣本及聚類的類別定義為：

式中，X表示樣本數(shù)據(jù)；n表示樣本的總數(shù)量；l表示類別的數(shù)量；w1表示第l類樣本的數(shù)量。

K-Means算法聚類過程中的目標(biāo)函數(shù)定義為：

在K-Means算法中，網(wǎng)絡(luò)流量樣本各類別全部點(diǎn)與聚類中心的距離平方和通過上述目標(biāo)函數(shù)求取，算法聚類終止的條件是目標(biāo)函數(shù)達(dá)到最小值，即均方差達(dá)到最小值。

在K-Means算法基本定義的基礎(chǔ)上，使用最小生成樹確定其聚類中心，具體采用最小生成樹中的Kruskal算法[7]。

定義最小生成樹邊集數(shù)據(jù)集為Q={q1,q2,…,qn}，用權(quán)重形容邊的長(zhǎng)度，即求取歐氏距離為：

此外，用C={β1,β2,…,βl}表示改進(jìn)K-means算法的聚類中心。

一幅完全圖的最小連通子圖即為最小生成樹，完全圖的全部點(diǎn)均包含在最小生成樹算法之內(nèi)[8]。根據(jù)此定義確定聚類中心，需要將網(wǎng)絡(luò)異常流量數(shù)據(jù)視為完全圖的連接點(diǎn)，由此建立的帶權(quán)完全圖表達(dá)為：

式中，H表示完全圖的頂點(diǎn)集合；Q表示完全圖的邊，即連接點(diǎn)之間的長(zhǎng)度；K表示邊的權(quán)重。

基于上述公式原理，通過Kruskal算法生成最小生成樹，由此確定K-Means算法聚類中心，進(jìn)而得到網(wǎng)絡(luò)異常流量聚類結(jié)果。

2 實(shí)驗(yàn)結(jié)果分析

搭建云計(jì)算環(huán)境下K-Means算法聚類實(shí)驗(yàn)平臺(tái)，檢測(cè)網(wǎng)絡(luò)運(yùn)行中的異常數(shù)據(jù)。實(shí)驗(yàn)采用64位操作系統(tǒng)，使用Hadoop2.7.3版本的Hadoop集群運(yùn)行環(huán)境，Java工具為64位JDKL.8.0_181版本。Hadoop集群由6個(gè)次要節(jié)點(diǎn)與1個(gè)主節(jié)點(diǎn)構(gòu)成，網(wǎng)絡(luò)數(shù)據(jù)流量樣本來自某互聯(lián)網(wǎng)公司，其中異常部分?jǐn)?shù)據(jù)為網(wǎng)絡(luò)攻擊行為數(shù)據(jù)。基于比例分配測(cè)試集規(guī)模，得到如表1描述的測(cè)試集構(gòu)成，數(shù)據(jù)集由Pro He攻擊和U2R攻擊兩種異常數(shù)據(jù)構(gòu)成。

表1 測(cè)試集構(gòu)成

為了對(duì)比本方法在檢測(cè)網(wǎng)絡(luò)異常數(shù)據(jù)方面的優(yōu)勢(shì)，引入傳統(tǒng)K-Means算法和蜂群K-Means算法進(jìn)行同步測(cè)試。測(cè)試中主要計(jì)算各檢測(cè)方法的檢測(cè)率與誤檢率，以描述檢測(cè)方法的有效性。誤檢率計(jì)算主要基于兩個(gè)變量，一是被認(rèn)為是異常數(shù)據(jù)中正常數(shù)據(jù)條數(shù)，二是正常數(shù)據(jù)記錄的總數(shù)，二者的商即為誤檢率，檢測(cè)率則是求取異常數(shù)據(jù)記錄數(shù)量與異常數(shù)據(jù)總數(shù)量的商[9,10]。

不同類型攻擊行為的檢測(cè)結(jié)果如圖2和圖3所示。

圖2 3種方法的網(wǎng)絡(luò)異常檢測(cè)率

圖3 3種方法的網(wǎng)絡(luò)異常誤檢率

圖2數(shù)據(jù)顯示，本文方法的檢測(cè)率自實(shí)驗(yàn)開始3.5 s便在90%以上，5.5 s左右達(dá)到95%，之后保持在95%及以上，檢測(cè)效果較為理想且穩(wěn)定。相比之下，傳統(tǒng)K-Means算法檢測(cè)率始終在80%以下，蜂群K-Means算法的檢測(cè)率雖然呈現(xiàn)一路上升態(tài)勢(shì)，但是僅在測(cè)試19 s左右才達(dá)到95%的檢測(cè)率，低于本文方法。因此，本文方法檢測(cè)網(wǎng)絡(luò)異常數(shù)據(jù)的精準(zhǔn)度最高且效果最好。由圖3可知，本文方法誤檢率始終低于1.0%，保持在0.5%左右，將正常數(shù)據(jù)誤認(rèn)為是異常數(shù)據(jù)的概率較低。而傳統(tǒng)K-Means算法實(shí)驗(yàn)后期誤檢率均在10%以上，蜂群K-Means算法誤檢率分為3個(gè)階段，第一階段在0～4%，第二階段在4%～5%，第三階段在5%～10%。上述數(shù)據(jù)明顯可以看出本文方法檢測(cè)網(wǎng)絡(luò)異常的誤檢率最低，具有一定的優(yōu)勢(shì)。

綜合以上實(shí)驗(yàn)結(jié)果，本文方法檢測(cè)率和誤檢率均取得了較優(yōu)的結(jié)果，相比同類型的網(wǎng)絡(luò)異常檢測(cè)方法而言具有更好的可靠性。

3 結(jié) 論

通過實(shí)驗(yàn)結(jié)果可知，本文提出的改進(jìn)K-Means算法在網(wǎng)絡(luò)異常檢測(cè)中取得了較好的效果。該方法存在兩點(diǎn)主要優(yōu)勢(shì)，一是在MapReduce模型環(huán)境下運(yùn)行K-Means算法減少了數(shù)據(jù)檢測(cè)排隊(duì)問題，使算法更加精準(zhǔn)的識(shí)別異常數(shù)據(jù)，二是使用最小生成樹確定K-Means算法的聚類中心。傳統(tǒng)K-Means算法選取聚類具有較大的隨機(jī)性與不確定性，該改進(jìn)措施解決了傳統(tǒng)K-Means算法聚類中心不精準(zhǔn)的問題，大大降低了異常數(shù)據(jù)檢測(cè)的誤差，為準(zhǔn)確識(shí)別網(wǎng)絡(luò)中的異常流量和檢測(cè)異常行為數(shù)據(jù)提供了可行性方案。