0 引言

    網(wǎng)絡(luò)流量分類是指將混合有各種應(yīng)用的流量，按產(chǎn)生這些流量的應(yīng)用協(xié)議進行分類,。網(wǎng)絡(luò)流量分類既是高性能網(wǎng)絡(luò)協(xié)議設(shè)計的基礎(chǔ),，又是網(wǎng)絡(luò)運營管理、網(wǎng)絡(luò)發(fā)展規(guī)劃的依據(jù),，也是網(wǎng)絡(luò)攻擊與惡意代碼檢測的重要手段^[1],。

    自互聯(lián)網(wǎng)誕生之日起，學(xué)術(shù)界和產(chǎn)業(yè)界就一直對網(wǎng)絡(luò)流量分類進行研究,。就目前的研究進展來說,，網(wǎng)絡(luò)流量分類主要可以歸為四類方法：基于標(biāo)準(zhǔn)端口匹配、基于深度包檢測(Deep Packet Inspection,，DPI),、基于網(wǎng)絡(luò)協(xié)議解析和基于統(tǒng)計學(xué)習(xí)算法。

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

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

1 算法描述

1.1 相關(guān)定義

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

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

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

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

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

1.2 基于改進K-means的網(wǎng)絡(luò)流量分類方法

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

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

    對于沒有包含任何被標(biāo)記網(wǎng)絡(luò)流的類簇,，其所對應(yīng)的網(wǎng)絡(luò)流量被認(rèn)定為未知應(yīng)用類型。

    網(wǎng)絡(luò)流量分類方法詳細描述如下：

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

    輸出：網(wǎng)絡(luò)流量應(yīng)用類型集合M,。

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

2 實驗與結(jié)果分析

2.1 實驗工具、數(shù)據(jù)集與特征選擇

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

    實驗利用MOORE A W等人在文獻[7]中所使用的實驗數(shù)據(jù)集Moore_set作為源數(shù)據(jù)集，這是目前網(wǎng)絡(luò)流量分類研究中最為權(quán)威的測試數(shù)據(jù)集,。Moore_set中包含378 101個網(wǎng)絡(luò)流樣本,，共10種應(yīng)用類型，統(tǒng)計信息如表1所示。

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

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

    目前基于統(tǒng)計學(xué)習(xí)方法的流量分類研究中,，一般只從上述248個特征中選擇10~20個特征,。這是因為上述248個特征中存在很多冗余特征和無關(guān)特征，如果全部采用不僅會大大增加流量分類系統(tǒng)的負(fù)載,，甚至還會降低分類準(zhǔn)確率?？紤]到K-means算法固有的特點,，本文選擇了11項具有代表性的特征屬性用于表征網(wǎng)絡(luò)流，具體信息如表3所示,，其中標(biāo)識符參照文獻[8]中的定義,。

2.2 實驗結(jié)果分析

    設(shè)定實驗數(shù)據(jù)集Moore_subset中每種應(yīng)用類型各自所包含網(wǎng)絡(luò)流中被標(biāo)記為該類型的流數(shù)量所占比例均為γ。在基于密度的聚類算法中，密度的定義因?qū)嶒灁?shù)據(jù)集的不同而有所不同,，根據(jù)經(jīng)驗,，實驗令半徑系數(shù)ρ=1。

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

    令γ∈[5%,，7%，9%,，11%,，13%，15%],，測試數(shù)據(jù)集中被標(biāo)記網(wǎng)絡(luò)流數(shù)量的大小對分類識別結(jié)果的影響,。在γ不同取值情況下的網(wǎng)絡(luò)流量分類識別總體準(zhǔn)確率如圖2所示。從圖中可以看出,，已標(biāo)記網(wǎng)絡(luò)流所占比例越大,，即數(shù)量越多，分類識別的總體準(zhǔn)確率越高,。

    總體上,，經(jīng)過改進后的網(wǎng)絡(luò)流量分類方法在準(zhǔn)確率方面具有更好的穩(wěn)定性，網(wǎng)絡(luò)流量分類識別總體準(zhǔn)確率可以達到90%以上,，能夠滿足一定的網(wǎng)絡(luò)應(yīng)用分類識別需求,。

3 結(jié)論

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

參考文獻

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

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

[3] 柏駿,，夏靖波,，鹿傳國，等.基于RVM的網(wǎng)絡(luò)流量分類研究[J].電子科技大學(xué)學(xué)報,，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] 周文剛，陳雷霆,，董仕,，等.基于半監(jiān)督的網(wǎng)絡(luò)流量分類識別算法[J].電子測量與儀器學(xué)報，2014,，28(4)：381-386.

[6] 袁梅宇.數(shù)據(jù)挖掘與機器學(xué)習(xí)：WEKA應(yīng)用技術(shù)與實踐[M].北京：清華大學(xué)出版社,，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.