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)營(yíng)管理、網(wǎng)絡(luò)發(fā)展規(guī)劃的依據(jù)，也是網(wǎng)絡(luò)攻擊與惡意代碼檢測(cè)的重要手段^[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)端口匹配、基于深度包檢測(cè)(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ì)涉及到侵犯?jìng)€(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)威的測(cè)試數(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é)長(zhǎng)度統(tǒng)計(jì)量、包字節(jié)長(zhǎng)度統(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%]，測(cè)試數(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] 柏駿，夏靖波，鹿傳國(guó)，等.基于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].電子測(cè)量與儀器學(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.