基于改進K-Means的網絡異常檢測

徐 翔

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

0 引 言

隨著互聯網普及范圍的擴大、網絡技術的優化以及計算機硬件成本的降低，網絡用戶量劇增。網絡是為了方便現代社會運行與發展而誕生的，但是在其提供諸多方便的同時攜帶較多安全隱患也是不可忽視的事實[1]。互聯網運行過程中難免存在一些混淆正常安全數據傳輸的非法操作，將異常入侵數據與正常數據流量混為一談，通過DDoS攻擊或各類病毒攻擊威脅網絡安全，嚴重影響正常網絡的使用和網絡業務的有效開展[2,3]。因此，精準高效識別網絡異常情況、檢測互聯網流量異常特征以及發現潛在攻擊威脅成為網絡健康運行的基本要求。本次研究對K-Means聚類算法進行優化與改進，在海量網絡信息流中識別異常特征信息，及早發現并阻止異常信息的傳播，營造安全綠色的網絡環境。

1 基于改進K-Means的分布式網絡異常檢測方法

1.1 MapReduce分布式計算環境構建

大數據時代互聯網每分每秒都在產生海量信息數據，網絡異常流量規模不容小覷，為了提高海量網絡異常流量檢測效率，本次研究首先搭建MapReduce分布式計算環境，基于MapReduce分布式計算模型進行并行化K-Means的網絡異常聚類挖掘[4]。

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

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

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

1.2 改進K-Means算法的網絡異常數據聚類

K-Means算法以原型目標函數為基礎進行硬聚類，在此類聚類算法中極具代表性，具體方式是確定原始聚類中心，通過數學方法運算原始聚類中心與聚類對象樣本，從而得到新的聚類中心，完成精準的數據樣本聚類[6]。MapReduce模型保障了K-Means挖掘算法的聚類效率，在此基礎上改進傳統K-Means算法，基于最小生成樹確定K-Means算法的聚類中心，優化K-Means挖掘網絡異常流量的精度。

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

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

K-Means算法聚類過程中的目標函數定義為：

在K-Means算法中，網絡流量樣本各類別全部點與聚類中心的距離平方和通過上述目標函數求取，算法聚類終止的條件是目標函數達到最小值，即均方差達到最小值。

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

定義最小生成樹邊集數據集為Q={q1,q2,…,qn}，用權重形容邊的長度，即求取歐氏距離為：

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

一幅完全圖的最小連通子圖即為最小生成樹，完全圖的全部點均包含在最小生成樹算法之內[8]。根據此定義確定聚類中心，需要將網絡異常流量數據視為完全圖的連接點，由此建立的帶權完全圖表達為：

式中，H表示完全圖的頂點集合；Q表示完全圖的邊，即連接點之間的長度；K表示邊的權重。

基于上述公式原理，通過Kruskal算法生成最小生成樹，由此確定K-Means算法聚類中心，進而得到網絡異常流量聚類結果。

2 實驗結果分析

搭建云計算環境下K-Means算法聚類實驗平臺，檢測網絡運行中的異常數據。實驗采用64位操作系統，使用Hadoop2.7.3版本的Hadoop集群運行環境，Java工具為64位JDKL.8.0_181版本。Hadoop集群由6個次要節點與1個主節點構成，網絡數據流量樣本來自某互聯網公司，其中異常部分數據為網絡攻擊行為數據。基于比例分配測試集規模，得到如表1描述的測試集構成，數據集由Pro He攻擊和U2R攻擊兩種異常數據構成。

表1 測試集構成

為了對比本方法在檢測網絡異常數據方面的優勢，引入傳統K-Means算法和蜂群K-Means算法進行同步測試。測試中主要計算各檢測方法的檢測率與誤檢率，以描述檢測方法的有效性。誤檢率計算主要基于兩個變量，一是被認為是異常數據中正常數據條數，二是正常數據記錄的總數，二者的商即為誤檢率，檢測率則是求取異常數據記錄數量與異常數據總數量的商[9,10]。

不同類型攻擊行為的檢測結果如圖2和圖3所示。

圖2 3種方法的網絡異常檢測率

圖3 3種方法的網絡異常誤檢率

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

綜合以上實驗結果，本文方法檢測率和誤檢率均取得了較優的結果，相比同類型的網絡異常檢測方法而言具有更好的可靠性。

3 結 論

通過實驗結果可知，本文提出的改進K-Means算法在網絡異常檢測中取得了較好的效果。該方法存在兩點主要優勢，一是在MapReduce模型環境下運行K-Means算法減少了數據檢測排隊問題，使算法更加精準的識別異常數據，二是使用最小生成樹確定K-Means算法的聚類中心。傳統K-Means算法選取聚類具有較大的隨機性與不確定性，該改進措施解決了傳統K-Means算法聚類中心不精準的問題，大大降低了異常數據檢測的誤差，為準確識別網絡中的異常流量和檢測異常行為數據提供了可行性方案。