邱 婧， 夏靖波， 柏 駿

(空軍工程大學(xué)電訊工程學(xué)院，西安 710077)

0 前言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，許多新的網(wǎng)絡(luò)服務(wù)(如P2P、在線游戲等)采用動(dòng)態(tài)端口、協(xié)議加密以及其他方面的原因，使得傳統(tǒng)的基于端口和基于有效載荷分析的流量分類方法已不能保證完全精確的網(wǎng)絡(luò)流量分類和統(tǒng)計(jì)。近年來(lái)，一些學(xué)者使用機(jī)器學(xué)習(xí)的方法來(lái)進(jìn)行流量分類的研究。對(duì)網(wǎng)絡(luò)流量分類使用機(jī)器學(xué)習(xí)技術(shù)的思想在入侵檢測(cè)的研究中被首次提出［1］;文獻(xiàn)［2］提出一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法來(lái)識(shí)別不同網(wǎng)絡(luò)應(yīng)用的框架，用流的統(tǒng)計(jì)特性作為流的特征來(lái)進(jìn)行網(wǎng)絡(luò)流量自動(dòng)分類研究;文獻(xiàn)［3］和文獻(xiàn)［4］使用基于貝葉斯分類器和大量的流屬性來(lái)進(jìn)行網(wǎng)絡(luò)流量的分類研究。

支持向量機(jī)(SVM)方法是一種建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)之上的機(jī)器學(xué)習(xí)方法，該方法一方面利用非線性變換將樣本空間的分類問(wèn)題轉(zhuǎn)化為高維特征空間的分類問(wèn)題，有效避免冗余屬性和無(wú)關(guān)屬性對(duì)分類結(jié)果的影響;另一方面又根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，將分類問(wèn)題轉(zhuǎn)化為在特定約束條件下尋找最優(yōu)超平面的二次尋優(yōu)問(wèn)題，從而避免分類模型對(duì)樣本先驗(yàn)概率的依賴，可以有效提高分類模型在小樣本情況下的分類準(zhǔn)確率和穩(wěn)定性。目前已有學(xué)者將SVM用于網(wǎng)絡(luò)流量分類，并取得了較好的分類效果［5-6］。但是SVM在網(wǎng)絡(luò)流量分類中還存在以下問(wèn)題。1)SVM本質(zhì)上是2值分類，而流量分類是多類分類問(wèn)題，目前基于支持向量機(jī)的多類分類算法主要是通過(guò)建立多個(gè)兩類分類器的方法，主要有“一對(duì)一”算法、“一對(duì)多”算法。但“一對(duì)一”和“一對(duì)多”算法在求解時(shí)，由于本身的算法機(jī)理問(wèn)題，往往會(huì)出現(xiàn)無(wú)法識(shí)別區(qū)域，即在這個(gè)區(qū)域中的數(shù)據(jù)樣本，要么無(wú)法確定它們的類別，要么屬于多個(gè)類別?？傊瑹o(wú)法將其唯一判至某類，從而出現(xiàn)拒識(shí)。2)由于是通過(guò)將多類問(wèn)題轉(zhuǎn)為兩類問(wèn)題解決，“一對(duì)一”算法和“一對(duì)多”算法分別需要構(gòu)造k(k-1)/2和k個(gè)支持向量機(jī)子分類器，從而造成樣本訓(xùn)練時(shí)間長(zhǎng)，計(jì)算復(fù)雜，決策時(shí)間慢，影響了分類效率。

本文提出了一種基于SVM決策樹(shù)的網(wǎng)絡(luò)流量分類方法，該方法充分利用SVM決策樹(shù)方法代價(jià)低、速度快、精度高等優(yōu)點(diǎn)，可以有效提高分類模型的整體性能。

1 原理與方法

1.1 SVM決策樹(shù)主要思想

在多類分類問(wèn)題中，類間分布會(huì)出現(xiàn)“類簇”的情況。所謂“類簇”是指多類樣本空間分布局部集中可以將其看作一個(gè)新集合類，即形成所謂的“簇”。在訓(xùn)練初期每一個(gè)樣本都看作一個(gè)類簇，通過(guò)不斷合并樣本類更新類蔟。例如圖1a四類樣本兩簇，Class3和Class4的空間分布出現(xiàn)局部集中的現(xiàn)象，則可以將Class3和Class4看作一個(gè)簇，同理Class2和Class1也出現(xiàn)空間分布局部集中的現(xiàn)象，則同樣也可以將Class2和 Class1看作一個(gè)簇;圖1b四類樣本先把Class3和Class4看作一個(gè)簇，因?yàn)镃lass3和Class4相對(duì)整體來(lái)講是局部集中的，即Class3和Class4形成一個(gè)新簇Cluster5，然后新簇Cluster5與Class1合并為一個(gè)新簇Cluster6。

圖1 類間類簇示意圖Fig.1 Schematic diagram of between-class clusters

SVM決策樹(shù)的多類分類算法是基于類簇展開(kāi)的，該方法的基本思想是:首先將所有類別分成兩個(gè)子類，再將子類進(jìn)一步分成兩個(gè)次級(jí)子類，如此循環(huán)下去，直到得到一個(gè)單獨(dú)的類別為止，這樣就得到一棵倒立的二叉樹(shù)，然后對(duì)每個(gè)決策節(jié)點(diǎn)的兩類分類問(wèn)題用SVM解決，該方法的特點(diǎn)是逐步把某一類從其他類分開(kāi)［7］。SVM決策樹(shù)有兩種實(shí)現(xiàn)類型(以4個(gè)類別為例)。1)正態(tài)樹(shù)。從頂層開(kāi)始，每個(gè)節(jié)點(diǎn)分類器將類的集合劃分成兩個(gè)類的子集合，直到底層的節(jié)點(diǎn)分類器將某一類或某兩類劃分開(kāi)來(lái)。2)偏態(tài)樹(shù)。每一節(jié)點(diǎn)分類器將某一類與其他類別分開(kāi)，最底層的節(jié)點(diǎn)分類器將最后剩下的兩類分開(kāi)。如圖2所示，這兩種分類器的構(gòu)造代價(jià)相當(dāng)。

圖2 SVM決策樹(shù)構(gòu)型Fig.2 SVM decision tree configuration

對(duì)于N類問(wèn)題構(gòu)造一棵二叉決策樹(shù)，則樹(shù)的每一個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一種類別，每一個(gè)度為2的非葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)子SVM分類器，所以決策樹(shù)共有2k-1節(jié)點(diǎn)，葉節(jié)點(diǎn)個(gè)數(shù)為k，只需構(gòu)造k-1個(gè)SVM分類決策函數(shù)，具有較高的分類效率，也不存在拒識(shí)區(qū)域。

1.2 類間分離測(cè)度

在設(shè)計(jì)SVM決策樹(shù)時(shí)，可以考慮將容易分(不易產(chǎn)生錯(cuò)分)的類先分離出來(lái)，然后再分不容易分的類，這樣就能夠使可能出現(xiàn)的錯(cuò)分盡可能地遠(yuǎn)離樹(shù)根。要使每個(gè)決策節(jié)點(diǎn)的類間隔盡可能大，首先要根據(jù)訓(xùn)練樣本集估計(jì)各類間的分離測(cè)度［8］。所謂類間的分離測(cè)度，是對(duì)類與類之間的可分程度大小的一個(gè)度量，它表示類與類的遠(yuǎn)離程度。分離測(cè)度大，說(shuō)明這兩類比較容易分開(kāi)。一般情況下，將類i與其余各類間的最小分離測(cè)度作為類i的分離測(cè)度)，即類的分離測(cè)度，其中，sij表示類 i與類j之間的分離測(cè)度。

其中，dij(i=1，2，…，k)表示類 i和類 j中心距離

ci是根據(jù)訓(xùn)練樣本計(jì)算出的類中心，表示為

其中:ni為類Xi中的樣本個(gè)數(shù);σi表示類i的標(biāo)準(zhǔn)差;σj表示類j的標(biāo)準(zhǔn)差，其表示類的分布情況。

而對(duì)于非線性的訓(xùn)練樣本集，經(jīng)非線性映射Φ作用后，在特定空間H中類i和類j間的分離性測(cè)度為

其中:K(·，·)為核函數(shù);dH(Z1，Z2)為經(jīng)非線性映射作用后，在特征空間H中訓(xùn)練樣本間的歐氏距離;同時(shí)輸入空間樣本的中心經(jīng)映射后得到不再是特征空間中樣本的中心，特征空間樣本的中心向量為mΦ，n為樣本的個(gè)數(shù);σH為特征空間中的類方差。

當(dāng)i≠j，sij表示類i與其他類之間的分離性測(cè)度，sij數(shù)值越大，則類i和類j間的分離性越好。當(dāng) i=j，max(sij)對(duì)應(yīng)的類i為最易分的類。相反，min(sij)對(duì)應(yīng)的類i為最難分的類。SVM決策樹(shù)將類間分離度測(cè)度引入，更精確地評(píng)定類間分離難易程度。

1.3 算法步驟

SVM決策樹(shù)在具體算法實(shí)現(xiàn)上分為訓(xùn)練和分類兩個(gè)過(guò)程。訓(xùn)練過(guò)程借助類間分離測(cè)度的概念，逐層合并類簇，進(jìn)行訓(xùn)練建模。而SVM決策樹(shù)分類過(guò)程是訓(xùn)練建模的逆過(guò)程，結(jié)合決策樹(shù)的方法，從決策數(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)逐層判斷最終獲取測(cè)試數(shù)據(jù)所屬類別。

對(duì)于訓(xùn)練過(guò)程，假設(shè)對(duì)于N類問(wèn)題，訓(xùn)練集合Φ={X1，X2，…，XN}:

1)計(jì)算樣本數(shù)據(jù)中各類的分離測(cè)度si，i=1，2，…，N;

2)將分離測(cè)度按降序排列，設(shè)sm1≥sm2≥…≥smk;

3)設(shè)計(jì)數(shù)器k=1;

4)構(gòu)造子分類器SVMk的訓(xùn)練集Φk=Σ1+Σ2;其中Σ1={(Xmk，+1)}，Σ2={(Y，-1)|y∈{Φ -{Xmk}};按兩類問(wèn)題構(gòu)造分類器SVMk;

5)調(diào)整訓(xùn)練集和計(jì)數(shù)器，Φ=Φ-{Xmk}，k=k+1;

6)重復(fù)步驟4)和步驟5)，直到構(gòu)造完第N-1個(gè)子分類器SVMN-1。

按照此方法構(gòu)造的決策樹(shù)具有層次結(jié)構(gòu)，每個(gè)層次的子SVM最多一個(gè)，且重要性也不同，越靠近樹(shù)根的SVM越重要，訓(xùn)練集合的元素個(gè)數(shù)也越多［9］。

分類過(guò)程則首先在根節(jié)點(diǎn)利用SVM分類測(cè)試樣本，若屬于左節(jié)點(diǎn)，則判斷該節(jié)點(diǎn)是否為葉節(jié)點(diǎn);若是，則對(duì)待分樣本賦以該節(jié)點(diǎn)類別，若不是，則利用該節(jié)點(diǎn)的SVM進(jìn)行判決，確定待分樣本屬于下一級(jí)左節(jié)點(diǎn)還是右節(jié)點(diǎn)，再判斷左節(jié)點(diǎn)或右節(jié)點(diǎn)是否為葉節(jié)點(diǎn)，若是，則將待分樣本賦以左節(jié)點(diǎn)或右節(jié)點(diǎn)類別。直到葉節(jié)點(diǎn)層級(jí)為0，即找到所屬類別。

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

2.1 實(shí)驗(yàn)工具

本文所使用的數(shù)據(jù)分析工具主要是 Weka3.6.1［10］，它是由新西蘭懷卡托大學(xué)Witten教授等人開(kāi)發(fā)的開(kāi)源工作平臺(tái)，是當(dāng)前最著名的數(shù)據(jù)挖掘算法工具集之一，包含決策樹(shù)、支持向量機(jī)、貝葉斯分類器等多種機(jī)器學(xué)習(xí)算法。因?yàn)殚_(kāi)源，用戶可以使用自己的代碼進(jìn)行開(kāi)發(fā)，并提供Java接口，便于用戶編寫新的算法用以驗(yàn)證。

2.2 實(shí)驗(yàn)數(shù)據(jù)

本文采用了Andew Moore等人在參考文獻(xiàn)［3］中所用的實(shí)驗(yàn)數(shù)據(jù)集［11］。數(shù)據(jù)集中包含377526個(gè)網(wǎng)絡(luò)流樣本，分為10種類型。每種類型所包含的應(yīng)用名稱、每類網(wǎng)絡(luò)流的數(shù)量和所占的比例如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息Table 1 Experimental data set

數(shù)據(jù)集利用TCP TRACE等工具提取了不同的TCP屬性特征，其中每個(gè)樣本都是從一條完整的TCP雙向流抽象而來(lái)，包含249項(xiàng)屬性特征，其中最后一項(xiàng)屬性是目標(biāo)屬性，指明了該雙向流的類型，其他248種網(wǎng)絡(luò)流屬性的具體描述可以參見(jiàn)文獻(xiàn)［11］。

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

首先將實(shí)驗(yàn)數(shù)據(jù)集均分為兩個(gè)數(shù)據(jù)子集，分別是Set1和Set2，在這兩個(gè)數(shù)據(jù)子集中每類樣本的比例與原數(shù)據(jù)集保持一致。再?gòu)腟et1中分別抽取每類應(yīng)用10%(至少1個(gè))的樣本構(gòu)成訓(xùn)練集，由于在原數(shù)據(jù)集包含的249項(xiàng)網(wǎng)絡(luò)流屬性中，存在眾多的冗余屬性和無(wú)關(guān)屬性，這些屬性的存在不僅會(huì)降低分類模型的準(zhǔn)確率，而且會(huì)大大加重分類模型的計(jì)算負(fù)載，實(shí)驗(yàn)中首先使用FCBF方法對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行過(guò)濾。然后將SVM決策樹(shù)分類算法編寫到Weka3.6.1中，通過(guò)Weka調(diào)用libSVM中的SVM多類分類算法(“一對(duì)一”和“一對(duì)多”)以及新編入的SVM決策樹(shù)算法分別對(duì)Set1進(jìn)行訓(xùn)練，再用Set2進(jìn)行測(cè)試。測(cè)試包括分類性能和訓(xùn)練時(shí)間，分類性能用召回率和準(zhǔn)確率來(lái)評(píng)價(jià)。其中準(zhǔn)確率刻畫的是分類器給出類別為ki的預(yù)測(cè)中正確結(jié)果的比例;而召回率則代表了本應(yīng)是類別ki的實(shí)例被正確預(yù)測(cè)的比例。表2給出了采用普通SVM多類分類方法和SVM決策樹(shù)方法進(jìn)行流量分類實(shí)驗(yàn)的結(jié)果。

表2 分類性能和訓(xùn)練時(shí)間對(duì)比Table 2 Classification performance and training time

從上面實(shí)驗(yàn)的結(jié)果來(lái)看，SVM決策樹(shù)在分類性能上略高于“一對(duì)一”和“一對(duì)多”算法，在訓(xùn)練時(shí)間上明顯優(yōu)于“一對(duì)一”算法，下面是對(duì)實(shí)驗(yàn)結(jié)果的分析:

1)SVM決策樹(shù)的子分類器采用逐層分類結(jié)構(gòu)，而“一對(duì)一”和“一對(duì)多”算法的各個(gè)子分類器是平級(jí)關(guān)系，這樣SVM決策樹(shù)能夠逐級(jí)將輸入樣本最終劃分到所屬類別，充分回避了分類矛盾，提高了分類性能;

2)訓(xùn)練階段，“一對(duì)一”和“一對(duì)多”算法分別需要產(chǎn)生k(k-1)/2，k個(gè)分類器，SVM決策樹(shù)只需要產(chǎn)生k-1個(gè)分類器，因此SVM決策樹(shù)算法的訓(xùn)練時(shí)間較“一對(duì)一”和“一對(duì)多”算法要短;

3)SVM決策樹(shù)算法中引入了類間分離測(cè)度，最大程度地減少了積累誤差，進(jìn)一步提高了分類準(zhǔn)確性。

3 結(jié)束語(yǔ)

本文提出使用SVM決策樹(shù)研究網(wǎng)絡(luò)流量分類問(wèn)題，通過(guò)在公開(kāi)數(shù)據(jù)集上進(jìn)行訓(xùn)練與測(cè)試，實(shí)驗(yàn)結(jié)果表明SVM決策樹(shù)方法的分類準(zhǔn)確率可以達(dá)到98%以上，訓(xùn)練時(shí)間也較另外兩種SVM多類分類算法短。由于網(wǎng)絡(luò)流量分類是流量管理和控制的前提，所以要求分類具有一定的實(shí)時(shí)性。研究在滿足一定分類準(zhǔn)確率的條件下，如何進(jìn)一步減少子分類器個(gè)數(shù)，以此減少計(jì)算量，提高分類速度，是下一步工作的重點(diǎn)。

［1］FRANK J.Machine learning and intrusion detection:current and future directions［C］//Proceedings of the National 17th Computer Security Conferece,1994:256-270.

［2］ZANDER S,NGUYEN T,ARMITAGE G.Self-learning IP traffic classification based on statistical flow characeristics(poster)［C］//Proceedings of the Passive Active Measurement Workshop,Boston,USA,2005:250-257.

［3］MOORE A W,ZUEV D.Internet traffic classification us in bayesi ananalysis techniques［C］//Proc eding of the 2005 ACM SIGMETRICS.International Conference on Measurement and Modeling of Computer Systems，New York:ACM,2005:50-60.

［4］ZUEV D,MOORE A.Traffic classification using a statistical approach［C］//Proceedings of the 6th International Workshop on Passive and Active Network Measurement,2005:321-324.

［5］林森，徐鵬，劉瓊.基于支持向量機(jī)的流量分類方法［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(8):2488-2490.

［6］徐鵬，劉瓊，林森.基于支持向量機(jī)的Internet流量分類研究［J］.計(jì)算機(jī)研究與發(fā)展，2009，46(3):407-414.

［7］BERURETT K P.Decision tree construction via linear ptogramtning［C］//The Midwest Artificial Intelligence and Cognitive Science Society Conference,Utica,1992:92-101.

［8］夏思宇，潘泓，金立左.非平衡二叉樹(shù)多類支持向量機(jī)分類方法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(17):167-169.

［9］韓家新，何華燦.SVMDT分類器及其在文本分類中的應(yīng)用研究［J］.計(jì)算機(jī)應(yīng)用研究，2004(1):23-24，43.

［10］WITTEN I H,FRANK E.Data mining:practical machine learning tools and techniques［M］.2nd ed.Amsterdam:Elsevier Inc,2005.

［11］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.