0 引言

    網絡流量分類是指將混合有各種應用的流量，按產生這些流量的應用協議進行分類。網絡流量分類既是高性能網絡協議設計的基礎，又是網絡運營管理、網絡發展規劃的依據，也是網絡攻擊與惡意代碼檢測的重要手段^[1]。

    自互聯網誕生之日起，學術界和產業界就一直對網絡流量分類進行研究。就目前的研究進展來說，網絡流量分類主要可以歸為四類方法：基于標準端口匹配、基于深度包檢測(Deep Packet Inspection，DPI)、基于網絡協議解析和基于統計學習算法。

    當今互聯網的發展規模造成了端口與應用之間的映射不再固定，因此基于端口的流量分類方法一般用于粗粒度的流量篩選；基于DPI的分類方法的一個主要弱點是無法適用于加密流量，另外也會涉及到侵犯個人隱私等法律問題；基于網絡協議解析的網絡流量分類方法是指通過對協議流量或行為的分析，利用流量特征或行為特征實現流量分類；基于統計學習的網絡流量分類方法先定義一組流（Flow，一般以源IP地址、目的IP地址、源端口號、目的端口號和協議五元組定義）統計特征，再利用機器學習算法訓練出分類模型，然后利用該模型進行后續的網絡流量分類。目前后兩種分類方法在學術界得到廣泛關注。文獻[2]利用支持向量機（Support Vector Machine，SVM）決策樹在多類分類方面的優勢，提出一種用SVM決策樹來對網絡流量進行分類的方法，公開數據集上的實驗結果顯示該方法的分類準確率達到了98.8%。文獻[3]將相關向量機(Relevance Vector Machine，RVM)分類模型應用于網絡流量分類中，提出了一種混合流量分類方法，并在準確性等3方面性能指標上優于SVM。ERMAN J等人在文獻[4]中介紹了一種利用基于K-means的半監督學習分類算法對數據流進行分類的方法，實驗結果表明該方法能夠達到70%~90%的總體識別準確率，但算法中初始聚類中心的選取仍然是隨機選取的方式。文獻[5]對K-means算法中初始聚類中心的選取進行了改進，通過基于密度因子的相似性函數來滿足聚類數據的全局一致性要求以獲取更合適的初始聚類中心，但仍然需要事先確定聚類個數k。

    在當前應用于網絡流量分類的眾多機器學習算法中，K-means算法是應用最為廣泛的算法。但是K-means算法也存在兩個主要的缺點：(1)需要事先確定聚類個數k的大小；(2)標準算法中初始聚類中心選擇的隨機性導致算法對異常數據敏感，對分類準確度有較大影響。本文結合之前學者的研究，針對K-means算法的兩個主要缺點對算法進行全面優化，通過基于密度的思想對數據區域進行劃分，從高密度區域產生初始聚類中心；引入聚類有效性判別準則函數，以確定最佳的聚類個數k。實驗結果表明，優化后的算法提升了網絡流量分類的準確率，提高了分類穩定性。

1 算法描述

1.1 相關定義

    傳統的K-means算法需要事先確定聚類個數k，并隨機選取k個初始聚類中心，但這種選擇的隨機性往往導致聚類結果有很大的波動性。根據網絡流量的行為特征和統計特性可知，同一應用類型的流量數據往往分布在一個相對比較密集的區域，不同的密集區域會被一些稀疏區域隔離開來。所以在選擇初始聚類中心時，考慮數據對象的密度，將高密度區域作為產生聚類中心的候選集合。同時為了確定最佳的聚類數目k，避免人為設定對分類準確率造成影響，定義聚類有效性判別準則函數，將準則函數取得最小值時的聚類數作為最佳聚類數。

    設數據集合S={x_i|x_i∈R^p，i=1，2，3,…,n}，其中n為集合中數據對象個數，p為數據空間維數。

    定義1 數據集合S中任意兩個數據對象x_i、x_j間的距離為歐式距離，即：

其中，k為聚類個數且k>2，|C_i|為簇C_i中數據對象的個數，x_i、x_j分別為簇C_i、C_j的數據對象均值中心。di(k)、db(k)分別表示數據集合S的簇內距離和簇間距離，用于描述同一類型數據之間的相似性和不同類型數據之間的相異性。

    由式(6)～式(9)可知，簇內距離定義為簇中每個數據對象與同一個簇中所有其他對象之間平均距離的最小值，數據集合S的簇內距離為k個簇內距離中的最大值；數據集合S的簇間距離定義為k個簇的數據對象均值中心之間距離的最小值。由式(5)可知，di(k)越小，db(k)越大，判別準則函數J(k)的值越小，當J(k)取最小值時，表示數據集合S的簇內數據對象之間相似性最高，簇間數據對象之間相異性最高。所以選擇使J(k)取值最小時的k作為最佳聚類個數。

1.2 基于改進K-means的網絡流量分類方法

    令C={c₁，c₂，c₃，…，c_k}表示網絡流量聚類后的類簇集合，k為簇數。M={m₁，m₂，m₃，…，m_r}為網絡中流量的應用類型集合，r為應用種類個數，r≤k，則網絡流量分類中存在映射f:C→M。

    本文采用最大似然估計實現映射f。基于最大似然估計，定義映射f的概率模型為：

    對于沒有包含任何被標記網絡流的類簇，其所對應的網絡流量被認定為未知應用類型。

    網絡流量分類方法詳細描述如下：

    輸入：網絡流量(traffic)的流(flow)統計特征屬性表征集合S={x₁，x₂，…，x_n}，x_i=(t₁，t₂，…，t_p)，x_i表示為一個包含p項網絡流特征屬性的特征向量。

    輸出：網絡流量應用類型集合M。

    分類過程可以抽象為構造分類模型g:S→C和映射模型f:C→M。

2 實驗與結果分析

2.1 實驗工具、數據集與特征選擇

    本文使用的主要實驗工具是MATLAB 8.1和Weka 3.8。Weka是新西蘭懷卡托大學開發的一個基于JAVA環境的開源機器學習以及數據挖掘軟件，軟件包含多種機器學習算法，并提供JAVA接口，便于用戶自己編寫代碼進行算法開發^[6]。

    實驗利用MOORE A W等人在文獻[7]中所使用的實驗數據集Moore_set作為源數據集，這是目前網絡流量分類研究中最為權威的測試數據集。Moore_set中包含378 101個網絡流樣本，共10種應用類型，統計信息如表1所示。

    由于Moore_set中網絡流樣本數量總量較大，但INT和GAMES兩種類型應用的樣本數量相對過少，不具有代表性，所以本文選取Moore_set的一個數據子集Moore_subset作為實驗數據集，并刪除INT和GAMES兩種應用類型。實驗數據集統計信息如表2所示。

    MOORE A W等人在文獻[8]中提出了249個可用于流量分類的統計特征屬性（最后一個特征屬性是目標屬性，即指出網絡流所屬的應用類型，所以真正的特征屬性共248個），涵蓋了當前流量分類研究中使用的絕大多數特征。這些特征大致可分為雙向特征和單向特征，雙向特征包括服務器和客戶機所用端口號、包到達時間間隔統計量、以太幀字節長度統計量、包字節長度統計量等；單向特征包括傳輸的字節總數、發送的各類數據包計數(包括ACK包、純ACK包、SACK包、PUSH包、SYN包等)、TCP數據載荷包計數、重傳包計數、窗口參數相關統計、數據傳輸時間、空閑時間、吞吐量等。

    目前基于統計學習方法的流量分類研究中，一般只從上述248個特征中選擇10~20個特征。這是因為上述248個特征中存在很多冗余特征和無關特征，如果全部采用不僅會大大增加流量分類系統的負載，甚至還會降低分類準確率。考慮到K-means算法固有的特點，本文選擇了11項具有代表性的特征屬性用于表征網絡流，具體信息如表3所示，其中標識符參照文獻[8]中的定義。

2.2 實驗結果分析

    設定實驗數據集Moore_subset中每種應用類型各自所包含網絡流中被標記為該類型的流數量所占比例均為γ。在基于密度的聚類算法中，密度的定義因實驗數據集的不同而有所不同，根據經驗，實驗令半徑系數ρ=1。

    在γ=5%、ρ=1的情況下，運行K-means算法(k=8)和本文改進的K-means算法，分別得到每種應用的分類識別準確率，如圖1所示。從圖中可以看出，即使在提前給出最優的聚類個數的情況下，改進的K-means算法網絡流量分類識別準確率仍然比標準K-means算法高，這是因為初始聚類中心的選取直接影響聚類結果，而改進算法對其進行了優化。

    令γ∈[5%，7%，9%，11%，13%，15%]，測試數據集中被標記網絡流數量的大小對分類識別結果的影響。在γ不同取值情況下的網絡流量分類識別總體準確率如圖2所示。從圖中可以看出，已標記網絡流所占比例越大，即數量越多，分類識別的總體準確率越高。

    總體上，經過改進后的網絡流量分類方法在準確率方面具有更好的穩定性，網絡流量分類識別總體準確率可以達到90%以上，能夠滿足一定的網絡應用分類識別需求。

3 結論

    首先針對標準K-means算法的兩個主要缺陷，通過基于密度的思想改進初始聚類中心的選取以及引入聚類有效性判別準則函數確定最優的聚類個數對算法進行全面優化，然后據此提出一種基于改進K-means算法的網絡流量分類方法。在權威數據集Moore_set上的實驗表明，該分類方法可以取得較好的分類效果，能夠滿足一定的網絡應用分類識別需求。但同時也應該看到，隨著技術的發展，網絡新應用層出不窮，網絡架構設計不斷優化演進，使得網絡流量分類問題不斷面臨新的巨大挑戰，諸如高帶寬帶來的數據實時無損采集的挑戰，應用多樣化和協議私有化給應用協議特征分析帶來的挑戰，分類器在線部署面臨的挑戰等。這些都是今后繼續努力研究的方向。

參考文獻

[1] 汪立東，錢麗萍，王大偉，等.網絡流量分類方法與實踐[M].北京：人民郵電出版社，2013.

[2] 邱婧，夏靖波，柏駿.基于SVM決策樹的網絡流量分類[J].電光與控制，2012，19(6)：13-16.

[3] 柏駿，夏靖波，鹿傳國，等.基于RVM的網絡流量分類研究[J].電子科技大學學報，2014，43(2)：241-246.

[4] ERMAN J，MAHATI A，ARLITT，M.Semi-supervised network traffic classification[C].Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems，New York，USA，2007：369-371.

[5] 周文剛，陳雷霆，董仕，等.基于半監督的網絡流量分類識別算法[J].電子測量與儀器學報，2014，28(4)：381-386.

[6] 袁梅宇.數據挖掘與機器學習：WEKA應用技術與實踐[M].北京：清華大學出版社，2014.

[7] MOORE A W，ZUEV D.Internet traffic classification using Bayesian analysis techniques[C].Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems，Banff，Canada，2005：50-60.

[8] MOORE A W，ZUEV D，CROGAN M.Discriminators for use in flow-based classification，RR-05-13[R].London：Queen Mary University of London，2005.