0 引言

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

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

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

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

1 算法描述

1.1 相關(guān)定義

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

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

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

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

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

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

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

    本文采用最大似然估計(jì)實(shí)現(xiàn)映射f,?；谧畲笏迫还烙?jì)，定義映射f的概率模型為：

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

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

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

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

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

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

2.1 實(shí)驗(yàn)工具,、數(shù)據(jù)集與特征選擇

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)

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

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

[3] 柏駿，夏靖波,，鹿傳國,，等.基于RVM的網(wǎng)絡(luò)流量分類研究[J].電子科技大學(xué)學(xué)報(bào)，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ò)流量分類識(shí)別算法[J].電子測量與儀器學(xué)報(bào),，2014,，28(4)：381-386.

[6] 袁梅宇.數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)：WEKA應(yīng)用技術(shù)與實(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.