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

摘 要：針對現(xiàn)有流量分類方法存在的準(zhǔn)確率低、應(yīng)用范圍受限、計算復(fù)雜度高等問題，提出使用支持向量機方法來解決流量分類問題。使用公開的人工標(biāo)注數(shù)據(jù)集作為訓(xùn)練集和測試集，通過有監(jiān)督學(xué)習(xí)構(gòu)建支持向量機流量分類器。此外，通過實驗進(jìn)一步分析了訓(xùn)練集大小、核函數(shù)、懲罰因子等因素對支持向量機分類性能的影響。實驗結(jié)果表明支持向量機分類器可以達(dá)到98%以上的流分類準(zhǔn)確率。

關(guān)鍵詞：流量分類； 支持向量機； 流量識別

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：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 相關(guān)研究

本文討論的流量分類問題是指按應(yīng)用類型將網(wǎng)絡(luò)流量分類，是網(wǎng)絡(luò)管理的基礎(chǔ)功能。準(zhǔn)確的流量分類對于網(wǎng)絡(luò)領(lǐng)域很多相關(guān)研究都很重要。例如入侵檢測、流量調(diào)度、服務(wù)質(zhì)量保證（QoS）、構(gòu)建符合實際的流量模型、準(zhǔn)確預(yù)測未來流量規(guī)模和需求等。目前，已有的流量分類方法主要分為以下四類：

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

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

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

d）基于統(tǒng)計學(xué)的分類方法。根據(jù)傳輸層的統(tǒng)計特征來劃分流量。其中，貝葉斯神經(jīng)網(wǎng)絡(luò)方法的準(zhǔn)確率達(dá)到99%以上，但該方法計算復(fù)雜度很高^[5]。目前關(guān)于統(tǒng)計學(xué)方法已有很多深入研究，并且有許多成熟的算法實現(xiàn)。統(tǒng)計學(xué)方法被廣泛應(yīng)用于許多領(lǐng)域中的數(shù)據(jù)分析和處理，取得很多成果。在網(wǎng)絡(luò)流量分類領(lǐng)域，這類方法的應(yīng)用研究正在興起。

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

2 原理

2.1 簡介

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

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

2.2 支持向量機

假設(shè)訓(xùn)練樣本集為

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

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

SVM分類算法的原始形式可歸結(jié)為下列二次規(guī)劃問題：

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

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

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

上述二次規(guī)劃的對偶形式為

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乘子。根據(jù)最優(yōu)化理論中的KKT條件，只有少量樣本（判決函數(shù)值等于±1的樣本和錯分樣本）的αi值不為零。Vapnik等人稱之為支持向量。

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

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

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

3 實驗設(shè)置

3.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集統(tǒng)計信息

類別流數(shù)目百分比/%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、目的端口四元組惟一標(biāo)志 。每條流由249個屬性表示，其中第249號屬性表示類別。參考文獻(xiàn)[11]列出了各屬性的定義和完整說明。需要說明的是，這249個屬性中前兩個屬性分別表示源端口號、目的端口號，為了避免對應(yīng)用端口信息的依賴，在實驗中并未使用這兩個屬性。表2列出了分類類別及其代表應(yīng)用。

表2 類別及其部分代表應(yīng)用

類別應(yīng)用舉例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 數(shù)據(jù)集預(yù)處理

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

3.3.2 參數(shù)選擇

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

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

b）核類型：默認(rèn)使用徑向基核

（a）線性核  μ·v

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

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

c）核函數(shù)中的參數(shù)

（a）γ:需要實驗調(diào)整

（b）coef：默認(rèn)值取0

（c）degree:默認(rèn)值取3

d）停機條件，默認(rèn)值取0.001

經(jīng)過實驗得，當(dāng)C=512，γ=0.031 25 時，分類準(zhǔn)確率較高；后續(xù)實驗中如未加特殊說明，將C=512，γ=0.031 25作為默認(rèn)值使用。

3.3.3 實驗

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

3.4 實驗結(jié)果

本文使用評價標(biāo)準(zhǔn)定義如下：

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

表3表明支持向量機的平均準(zhǔn)確率為98.50%，比改進(jìn)的貝葉斯算法^[6] 74.80%的準(zhǔn)確率高，比貝葉斯神經(jīng)網(wǎng)絡(luò)^[5]99.26%的準(zhǔn)確率略低，但是訓(xùn)練時間遠(yuǎn)小于貝葉斯神經(jīng)網(wǎng)絡(luò)。當(dāng)訓(xùn)練集為50%的trace時，即訓(xùn)練集大小為188 763，支持向量機的訓(xùn)練時間約為2 h，貝葉斯神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間約為39 h。支持向量機方法平均準(zhǔn)確率標(biāo)準(zhǔn)差為0.01%，遠(yuǎn)小于另外兩種方法，說明該方法有很好的穩(wěn)定性。

表3 不同算法分類準(zhǔn)確率、訓(xùn)練時間比較

算法準(zhǔn)確率/%訓(xùn)練時間改進(jìn)的貝葉斯算法74.80±1.72 h 30 min貝葉斯神經(jīng)網(wǎng)絡(luò)99.26±0.438 h 48 min支持向量機98.50±0.012 h4 討論

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

4.1 不同大小的訓(xùn)練集

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

表4 不同大小訓(xùn)練集的實驗結(jié)果

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

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

表5 不同核函數(shù)的實驗結(jié)果

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

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

懲罰因子準(zhǔn)確率/%C197.82±0.07C298.16±0.06C397.37±0.02

5 結(jié)束語

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

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

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

c）對目前新出現(xiàn)并且發(fā)展迅速的新應(yīng)用的分類，特別是P2P應(yīng)用作更深入的研究。

參考文獻(xiàn):

[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] 張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機[J]. 自動化學(xué)報，2000， 26(1):32-42.

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

[9]鄧乃揚， 田英杰. 數(shù)據(jù)挖掘中的新方法:支持向量機[M]. 北京：科學(xué)出版社， 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.

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