基于支持向量機的流量分類方法

摘 要：針對現有流量分類方法存在的準確率低、應用范圍受限、計算復雜度高等問題，提出使用支持向量機方法來解決流量分類問題。使用公開的人工標注數據集作為訓練集和測試集，通過有監督學習構建支持向量機流量分類器。此外，通過實驗進一步分析了訓練集大小、核函數、懲罰因子等因素對支持向量機分類性能的影響。實驗結果表明支持向量機分類器可以達到98%以上的流分類準確率。

關鍵詞：流量分類； 支持向量機； 流量識別

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2488-03

Traffic classification based on support vector machine

LIN Sena，b，XU Penga，b，LIU Qionga，b

(a.Institute of Software， b.Graduate School，Chinese Academy of Sciences， Beijing 100190， China)

Abstract:In order to solve the problems in current work， such as low accuracy， limited application region or high computation complexity， support vector machine (SVM) was applied to categorize traffic by application. The work capitalized on public hand-classified network dataset and used it to train and tested the supervised SVM traffic classifier.The improved accuracy of refined variants of this classifier was further illustrated， and the variants included the size of training dataset， kernel functions and penalty factors. The results indicate that it can achieve over 98% accuracy on per-flow classification with the SVM classifier.

Key words:traffic classification; support vector machine(SVM); traffic identification

1 相關研究

本文討論的流量分類問題是指按應用類型將網絡流量分類，是網絡管理的基礎功能。準確的流量分類對于網絡領域很多相關研究都很重要。例如入侵檢測、流量調度、服務質量保證（QoS）、構建符合實際的流量模型、準確預測未來流量規模和需求等。目前，已有的流量分類方法主要分為以下四類：

a）基于固定端口號的分類方法。根據不同應用使用不同的傳輸層端口號來劃分流量，通常只有50%~70%的準確率^[1，2]。這種方法僅對使用傳統固定端口的應用有效，如Web、DNS、mail等。但是這類方法無法分類使用隨機端口的應用，或者錯誤分類使用傳統固定端口的非傳統應用。例如，近幾年來涌現出的P2P應用大量使用隨機端口，使基于固定端口流量分類方法失效。

b）基于應用層內容的分類方法。根據不同應用具有不同的應用層特征字段來劃分流量。該方法在加入人工干預的基礎上能達到99%以上的準確率^[3]。其準確率雖然遠遠高于基于固定端口號的流量分類方法，但是該方法需要獲取完整的應用層負載內容，其應用范圍受到三個因素限制：（a）涉嫌侵犯用戶隱私；（b）無法識別應用層加密的應用；（c）無法識別特征字段未知的應用。

c）基于傳輸層行為的分類方法。根據傳輸層不同級別的行為特征來劃分流量，準確率約為80%~90%^[4]。該方法不依賴應用層內容，不受基于應用層內容的分類方法三個限制因素的影響。但是傳輸層行為通常與網絡環境密切相關，相同應用在不同網絡環境下的傳輸層行為很可能存在較大差異，這種相關性限制了該方法的應用范圍。

d）基于統計學的分類方法。根據傳輸層的統計特征來劃分流量。其中，貝葉斯神經網絡方法的準確率達到99%以上，但該方法計算復雜度很高^[5]。目前關于統計學方法已有很多深入研究，并且有許多成熟的算法實現。統計學方法被廣泛應用于許多領域中的數據分析和處理，取得很多成果。在網絡流量分類領域，這類方法的應用研究正在興起。

基于統計學的分類方法可以有效克服前三種流量分類方法存在的問題，因此成為當前流量分類的主要研究方向。特別是近兩年來，越來越多的機器學習方法被用于流量分類，如貝葉斯算法^[6]、貝葉斯神經網絡^[5]等，都取得了很好的效果。盡管如此，已有機器學習分類方法還是存在一些問題。例如貝葉斯算法^[6]依賴樣本分布，而且屬性的相關性和冗余性會大幅度降低分類準確率；貝葉斯神經網絡^[5]同樣依賴樣本分布，且存在過擬合、計算復雜度高等問題。SVM方法有效地降低了樣本分布、相關屬性、冗余屬性、過擬合以及計算復雜度高等因素的影響，具有很好的泛化能力。本文提出利用支持向量機研究流量分類問題，并在人工標注的公開數據集上進行模型訓練和測試，結果表明分類準確率能達到98%以上。

2 原理

2.1 簡介

基于統計學習理論的支持向量機模型，自20世紀90年代中期提出以來，已經成為國際上機器學習領域的研究熱點^[7]。支持向量機模型的基本思想主要有兩個，即最大間隔原則和核技巧。最大間隔原則指通過尋求最優超平面，使產生的決策函數能夠承受盡可能大的擾動；核技巧指通過核函數變換，將原輸入空間需要用超平面劃分的分類問題，轉換為Hilbert空間中用超平面劃分的分類問題，可以將非線性問題轉換為線性問題，從而大大降低問題的復雜度。

支持向量機分類算法具有四個顯著特點：a)利用大間隔的思想降低分類器的VC維，實現結構風險最小化原則，控制分類器的推廣能力；b)利用Mercer核實現線性算法的非線性化；c)稀疏性，即少量樣本(支持向量)的系數不為零（就推廣性而言，較少的支持向量數在統計意義上對應好的推廣能力；從計算角度看，支持向量減少了核形式判別式的計算量）；d)算法設計成凸二次規劃問題，避免了多解性^[8]。

2.2 支持向量機

假設訓練樣本集為

(x1，y1)，(x2，y2)，…，（xl，yl）(1)

其中：xi∈Rn（i=1，2，…，l）(R 為實數域)；對于兩類的分類問題，yi∈{+1，-1}。

SVM分類算法的原始形式可歸結為下列二次規劃問題：

min 1/2(ω，ω)+Cli=1ξi 

s.t.yi((ω，xi)+b)-1+ξi≥0 (2)

其中：(·，·)為兩向量之間的內積；ξi≥0為松弛項，表示錯分樣本的懲罰程度；C是懲罰因子，為常數，用于控制對錯分樣本懲罰的程度，實現在錯分樣本數與模型復雜性之間的折中；ω和b為判決函數f(x)=(ω，x)+b中的權向量和閾值。當無錯分樣本時，最小化目標函數的第一項等價于最大化兩類間的間隔，可降低分類器的VC維，實現結構風險最小化原則。

上述二次規劃的對偶形式為

maxli=1αi-1/2li，j=1αiαj yiyj(xi，xj)

s.t.li=1αiyi=0；0≤αi≤C；i=1，2，…，l(3)

其中:αi為Lagrange乘子。根據最優化理論中的KKT條件，只有少量樣本（判決函數值等于±1的樣本和錯分樣本）的αi值不為零。Vapnik等人稱之為支持向量。

由于對偶式(3)中只出現兩向量間的內積運算，Vapnik等人用滿足Mercer條件的核函數k(xi，xj)來代替內積運算 (xi，xj)，實現線性算法的非線性化。常用的核函數包括多項式核、徑向基核以及二層神經網絡。核形式的判別函數為

f(x)=li=1αiyik(xi，x)+b (4)

上面討論是兩類的分類問題，對于多類分類問題通常有如下幾種方法：一類對余類、成對分類、糾錯輸出編碼方法、確定多類目標函數方法等^[9]。

3 實驗設置

3.1 數據集

本實驗使用一套通過實際監測采集的數據集^[10]。該數據集監測了一個名為Genome Campus的研究機構，大約有1 000名研究人員、管理人員和技術人員。監測點位于該機構的網絡出口，監測持續24 h的雙向流量。原始數據集較大，因此最終使用的數據集是對原始數據集的抽樣。表1展示了該數據集中各類流的數目和百分比。

表1 數據集統計信息

類別流數目百分比/%WWW328 09186.91MAIL28 5677.567BULK11 5393.056SERV2 0990.556DB2 6480.701INT1100.029P2P2 0940.555ATTACK1 7930.475MMEDIA1 1520.305GAMES80.002合計377 5261003.2 分類對象、屬性和類別

分類對象是完整的TCP雙向流。每條流用源IP、源端口、目的IP、目的端口四元組惟一標志 。每條流由249個屬性表示，其中第249號屬性表示類別。參考文獻[11]列出了各屬性的定義和完整說明。需要說明的是，這249個屬性中前兩個屬性分別表示源端口號、目的端口號，為了避免對應用端口信息的依賴，在實驗中并未使用這兩個屬性。表2列出了分類類別及其代表應用。

表2 類別及其部分代表應用

類別應用舉例BULKftpDBpostgres， sqlnet， oracle， ingresINTssh， klogin， rlogin， telnetMAILimap，pop2/3，smtpSERVX11，dns，ident，ldap，ntpWWWwwwP2PKaZaA， BitTorrent， GnuTellaATTACKInternet worm and virus attacksGAMESHalf-LifeMMEDIAWindows Media Player， Real3.3 實驗過程

3.3.1 數據集預處理

原始數據集中每個屬性的取值范圍不同。為了賦予每個屬性同等的重要性，筆者通過變換將每個屬性的取值范圍映射到[-1，1]。本文采用線性變換映射，也可以嘗試其他的映射方式。經過線性形映射后的數據集簡稱為trace。

3.3.2 參數選擇

支持向量機的參數選擇不同取值，對最終模型的分類準確率有顯著影響，所以在實驗之前，先在較小的訓練集上通過實驗得到較好的參數取值，然后在較大的數據集上驗證，通過驗證的參數取值被用于后續實驗。本文采用LibSVM^[12]中的支持向量機分類算法C-SVC。其中參數主要包括：

a）C：錯分類懲罰因子，見式（2）（3），需要實驗調整

b）核類型：默認使用徑向基核

（a）線性核  μ·v

（b）多項式核 （γ*（μ·v）+coef）degree

（c）徑向基核 e(-γ｜μ-v｜2)

c）核函數中的參數

（a）γ:需要實驗調整

（b）coef：默認值取0

（c）degree:默認值取3

d）停機條件，默認值取0.001

經過實驗得，當C=512，γ=0.031 25 時，分類準確率較高；后續實驗中如未加特殊說明，將C=512，γ=0.031 25作為默認值使用。

3.3.3 實驗

將數據集trace隨機平均分為兩個子集(各占50%)，分別記為trace1、trace2。Trace1作為訓練集，trace2作為測試集。為了保證數據集中每類至少包含一個樣例，采用按類別比例隨機抽樣，抽樣后的數據集trace1、trace2與原數據集trace具有近似相同的類別比例。用訓練集trace1訓練分類器，測試集trace2測試分類器性能。為了使實驗結果更可靠，重復以上抽樣、訓練、測試過程五次，實驗結果取平均值。

3.4 實驗結果

本文使用評價標準定義如下：

定義1 準確率表示分類的準確性。其中平均準確率定義為正確分類的流的個數與流的總個數之比；某類的準確率定義為該類流中正確分類的個數與該類流的總個數之比。

表3表明支持向量機的平均準確率為98.50%，比改進的貝葉斯算法^[6] 74.80%的準確率高，比貝葉斯神經網絡^[5]99.26%的準確率略低，但是訓練時間遠小于貝葉斯神經網絡。當訓練集為50%的trace時，即訓練集大小為188 763，支持向量機的訓練時間約為2 h，貝葉斯神經網絡的訓練時間約為39 h。支持向量機方法平均準確率標準差為0.01%，遠小于另外兩種方法，說明該方法有很好的穩定性。

表3 不同算法分類準確率、訓練時間比較

算法準確率/%訓練時間改進的貝葉斯算法74.80±1.72 h 30 min貝葉斯神經網絡99.26±0.438 h 48 min支持向量機98.50±0.012 h4 討論

本章將討論訓練集大小、核函數、懲罰因子等因素對支持向量機分類性能的影響。在本章的實驗中如果沒有特別說明，實驗的參數值使用3.3.2節中的默認值。

4.1 不同大小的訓練集

支持向量機適合于處理小樣本情況下的學習問題，在訓練集較小的情況下也能取得不錯的性能。表4表明訓練集大小為191時，準確率超過90%；訓練集大小為1 894時，準確率接近95%。說明支持向量機使用很小的訓練集，就能達到很高的準確率。增大訓練集，準確率會相應提高。使用較小訓練集訓練，訓練時間較短，支持向量個數也較少，可以減少計算量，提高分類速度。

表4 不同大小訓練集的實驗結果

訓練集大小測試集大小準確率/%訓練時間/s支持向量個數191188 15790.33<1911 894188 15794.91433118 936188 15796.851061 88494 684188 15797.441 8007 1534.2 不同的核函數

支持向量機的分類準確率很大程度上取決于屬性空間通過核函數變換后線性可分的程度，選取適當的核函數可以提高準確率。另外核函數的復雜度會影響支持向量機的推廣能力。分別采用線性核、多項式核和徑向基核(核函數的形式見3.3.2)，比較不同核函數條件下的準確率、訓練時間、迭代次數和支持向量個數。在實驗中使用20%的數據作為訓練集，80%的數據作為測試集。從表5列出的實驗結果可知在三種核函數中，分類準確率都在97%以上，其中多項式核略高，徑向基核訓練時間最短，訓練過程中迭代次數遠小于其他兩種核。對于支持向量個數，多項式核<徑向基核<線性核，與準確率的高低順序相反，說明較少的支持向量有較好的泛化能力。

表5 不同核函數的實驗結果

核函數準確率/%訓練時間/s迭代次數/M支持向量個數線性97.034 770266 339多項式97.992 293124 392徑向基97.371 0780.155 8064.3 不同的懲罰因子

進一步的實驗為每個類施加不同的懲罰因子，對訓練集中樣例較少的類別使用較大的懲罰因子可以間接增大小類別的權重，從而減輕訓練數據的不均衡性帶來的不利影響。使用20%的數據作為訓練集，80%的數據作為測試集，并且使用表6中列出的為不同類別選配的三組懲罰因子進行實驗。表7列出了使用不同懲罰因子訓練模型的分類準確率。C2與C1相比使用較大的懲罰因子，準確率從97.82%提高到98.16%。C2與C3相比，C2對不同類別使用不同的懲罰因子，即訓練樣例較少的類別使用較大的懲罰因子，變相地改變各類別訓練樣例的權重，使訓練集中各類別的樣例數更均衡，準確率從97.37%提高到98.16%。

表6 不同的懲罰因子

CWWWMAILBULKSERVDBINTP2PATTMULTGAMEC11002003005005001 0005005005001 000C25121 0241 5362 5602 5605 1202 5602 5602 5605 120C3512512512512512512512512512512表7 不同懲罰因子的準確率

懲罰因子準確率/%C197.82±0.07C298.16±0.06C397.37±0.02

5 結束語

本文提出使用支持向量機研究流量分類問題。通過在手工標注的公開數據集上訓練與測試，評估和分析了支持向量機模型進行流量分類的準確率等性能。實驗結果表明支持向量機方法的分類準確率可以達到98％以上。本文進一步討論了訓練集大小、核函數、懲罰因子等因素對支持向量機分類性能的影響，結果表明支持向量機在較小的訓練集上也能達到較高的準確率，并且通過調整不同類別的懲罰因子可以降低訓練集不均衡帶來的不利影響。此外，使用線性核、多項式核、徑向基核等核函數均能得到較好的分類性能。在以后的工作可以考慮從下述幾個方面展開進一步的研究：

為了滿足特定情況下分類的實時性要求，研究在滿足一定準確率的條件下，如何減少支持向量個數，以此減少計算量，提高分類速度。

b）深入研究不同屬性對不同類別間的區分能力，考慮對不同類別的區分使用不同的屬性集。

c）對目前新出現并且發展迅速的新應用的分類，特別是P2P應用作更深入的研究。

參考文獻:

[1]MOORE D， KEYS K， KOGA R ，et al. The CoralReef software suite as a tool for system and network administrators[C]//Proc of the 15th USENIX Conference on System Administration. California: USENIX Association， 2001: 133-144.

[2]LOGG C， COTTRELL L. Characterization of the traffic between SLAC and the Internet[EB/OL].(2003-07-15).http://www.slac.stanford.edu/comp/net/slac-netflow/html/SLAC-netflow.html.

[3]MOORE A W， PAPAGIANNAKI D. Toward the accurate identification of network applications[C]//Proc of the 6th Passive and Active Measurement Workshop. Berlin: Springer，2005:41-54.

[4]KARAGIANNIS T， PAPAGIANNAKI K， FALOUTSOS M. BLINC:multilevel traffic classification in the dark[C]//Proc of ACM SIGCOMM Computer Communication. New York:ACM Press， 2005: 229-240.

[5]AULD T， MOORE A， GULL S. Bayesian neural networks for Internet traffic classification[J]. IEEE Trans on Neural Networks， 2007，18(1): 223-239.

[6]MOORE A W，ZUEV D.Internet traffic classification usingBayesian analysis techniques[C]//Proc of ACM SIGMETRICS. New York: ACM Press， 2005: 50-60.

[7] 張學工.關于統計學習理論與支持向量機[J]. 自動化學報，2000， 26(1):32-42.

[8]許建華，張學工，李衍達.支持向量機的新發展[J]. 控制與決策， 2004， 19(5):481-485.

[9]鄧乃揚， 田英杰. 數據挖掘中的新方法:支持向量機[M]. 北京：科學出版社， 2004.

[10]MOORE A W，HALL J， KREIBICH C， et al. Architecture of a network monitor[C]//Proc of the 4th Passive and Active Measurement Workshop. Berlin: Springer，2003:257-267.

[11]MOORE A W，ZUEV D.Discriminators for use in flow-based classification[R]. Cambridge: Intel Research， 2005.

[12]CHANG C C，LIN C J.LIBSVM: a library for support vector machines[EB/OL].(2007-04-10)[ 2007-05-20]. http://www.csie.ntu.edu.tw/-cjlin/libsvm.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文