基于決策樹的流量分類方法

摘 要：近年來，利用機器學習方法處理流量分類問題已成為網絡測量領域一個新興的研究方向。在目前研究中應用較多的是樸素貝葉斯方法及其改進算法，但這些基于貝葉斯定理的分類方法過于依賴樣本空間的分布，具有潛在的不穩定性。為此，引入C4.5決策樹方法來處理流量分類問題。C4.5決策樹方法利用信息熵來構建分類模型，無須假設先驗概率的穩定。實驗結果表明C4.5決策樹方法可以有效避免網絡流分布變化所帶來的影響。

關鍵詞：流量分類; 網絡測量; 網絡流; 決策樹; 統計屬性

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

Internet traffic classification using decision tree

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

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

Abstract:In recent years， Internet traffic classification using machine learning has been a new direction in network measurement.Nave Bayes method and its improved algorithms have been widely used in this area， because they are simple and efficient. The methods based on Bayesian theorem depend on probability distribution of sample spacing， so they have connatural instability. In order to handle this problem， this paper proposed a new method based on C4.5 decision tree. The C4.5 method used information entropy to build the classification model without assuming prior probability was stable. The test result indicates that the C4.5 method can avoid the affection of the flow distribution change.

Key words: traffic classification; network measurement; flow; decision tree; statistical attribute

隨著互聯網用戶規模的日益增大，互聯網的擁塞狀況也日益加劇。為了解決這些問題，網絡研究人員提出了容量規劃、流量調度等一系列策略來提高網絡的運營效率。然而，無論是根據用戶需求對網絡資源進行QoS調度，還是根據網絡應用的發展趨勢對現有網絡進行擴容改造，都必須對網絡流量中各種應用進行準確分類與識別。此外，在網絡安全、流量計費、應用趨勢分析等領域，準確的流量分類也具有極其重要的意義。

為了適應Internet流量數據龐大和應用屬性動態變化的特點，利用機器學習方法處理流量分類問題成為當前網絡測量領域內一個新興的研究熱點。在使用機器學習方法處理流量分類問題時，研究對象是一組具有相同五元組(源IP、目的IP、源端口、目的端口、傳輸層協議)取值的分組序列，即網絡流(flow)。研究人員通過提取網絡流的統計屬性，將網絡流抽象為由一組統計屬性值構成的屬性向量，實現由流量分類向機器學習問題的轉換。因此，在機器學習方法中，流量分類問題可以抽象為：在已知流量類型集合T＝{T1，T2，…，Tk}和類型已知的網絡流集合X={X1，…，Xn}(其中，網絡流Xi是一個由網絡流屬性集合構成的屬性向量(A1，…，Am) T)的情況下，如何在這個網絡流集合上，利用機器學習方法構建流量分類模型f:X→T，并以此模型對類型未知的網絡流集合進行分類。

從現有研究成果來看，利用改進的樸素貝葉斯方法進行流量識別的效果最好。然而樸素貝葉斯方法是一種基于概率的學習方法，需要已知待分類樣本的分布形式，而在實際的流量分類問題中，建立分類器時所獲得訓練樣本數量相對于海量的未知數據則顯得非常有限，難以模擬未知樣本的空間分布，從而無法保證分類結果的穩定性。為此，本文引入決策樹方法處理流量分類問題，該方法不依賴于樣本空間的分布，具有良好的分類穩定性。

1 研究現狀

近年來，隨著互聯網技術的不斷發展，網絡應用的快速增長和變化給流量分類帶來了一系列挑戰。最初的流量分類方法是根據互聯網地址指派機構 (Internet Assigned Numbers Authority，IANA)規定的端口映射表，將特定端口的網絡流量劃分到相應的網絡應用。然而，隨著P2P和被動FTP等新型網絡應用的日益流行，大量的隨機端口被用于數據傳輸，從而導致這種基于端口的流量分類方法被迅速淘汰^[1]。

2005年劍橋大學的Moore等人^[2]提出了基于特征字段的流量分類方法。該方法能夠有效識別現有的互聯網應用。但是隨著負載加密技術的廣泛應用和新型應用的不斷涌現，該方法的有效性正在逐步下降。

針對負載加密問題，加州大學河濱分校的Karagiannis等人^[3]提出了基于傳輸層行為的流量分類方法BLINC(blind classification)。該方法利用不同網絡應用在傳輸層連接模式的差異來劃分網絡流量，不依賴于報文負載的內容，具有良好的可擴展性。但是該方法是利用應用流量的行為屬性，不僅容易隨著網絡應用自身的改進而逐步失效，而且也會因為網絡環境的不同而導致分類性能發生顯著的變化。

2004年澳大利亞阿德萊德大學的Roughan等人^[4]率先引入了k近鄰(k nearest neighbor， k-NN)和線性判別式分析(linear discriminant analysis， LDA)這兩種最簡單的機器學習(machine learning)方法來處理流量分類問題。然而k近鄰方法是在處理測試樣本時，需要逐個計算測試樣本和訓練樣本之間的相似度。這種處理方法不僅會導致較大的處理開銷，而且分類性能極易受到噪聲數據干擾。

2005年牛津大學Zuev等人^[5]引入了基于概率模型的樸素貝葉斯方法(nave Bayes，NB)來處理流量分類問題。該方法要求參與分類的各項屬性條件獨立而且遵循高斯分布，然而在流量分類問題中原始的網絡流屬性集合很難滿足上述條件，因此該方法的整體準確率只有65%左右。為了克服條件獨立假設和高斯分布假設帶來的消極影響，Moore等人采用FCBF(fast correlation-based filter)算法對屬性集合進行了過濾，并使用核估計(kernel estimation)技術對原始的樸素貝葉斯方法進行了改進^[6]。從他們的實驗結果來看，改進后的平均分類準確率達到了95%左右。

為了進一步提高分類模型的實時性，2006年澳大利亞斯溫伯恩大學的Nguyen等人^[7]提出了多子流模型(multiple sub-flows model)。該方法首先將網絡流按通信的不同階段劃分為若干條子流，然后分別為每條子流構造屬性向量，并以此作為基本單元構造訓練數據集。該方法通過子流屬性提取擺脫了對網絡流進行處理時必須等待網絡流結束的限制，大大提高了分類模型的實時性。但他們的研究主要集中在如何提取網絡流屬性方面，對機器學習算法的選擇沒有進行深入的分析。

2006年加拿大卡爾加里大學的Erman等人^[8]引入了聚類方法來處理流量分類問題。這些方法在聚類過程中無須使用訓練樣本的類型，因而能夠識別部分類型未定義的新型網絡流量，但在聚類結束后必須進行大量手工操作以實現網絡流量的分類。

國內方面，2006年北京航空航天大學的Li Ning等人^[9]提出了一種基于粗糙集理論和遺傳算法的流量分類方法。但他們僅在包含2 254條流的數據集上進行了小規模驗證，并且沒有給出與現有方法的進一步比較和分析。

2 流量分類方法

2.1 樸素貝葉斯方法的不足

樸素貝葉斯方法是一種利用貝葉斯定理對屬性集合和類型變量之間概率關系進行建模的方法。因此使用樸素貝葉斯方法處理流量分類問題^[5]時，對于任意網絡流X，其屬于類型Y的概率為

P（Y｜X)=[P(X｜Y)P(Y)]/P(X)(1)

其中：先驗概率P（Y）表示在網絡流集合中類型為Y的網絡流所占的比例；類條件(class-conditional)概率P（X｜Y）表示在類型為Y的網絡流中出現網絡流X的概率；P(X)表示網絡流X出現的概率。在比較不同Y值的后驗概率P(Y｜X)時，分母P(X)總是相等，因此可以忽略。

由于網絡流X被抽象為屬性向量(A1，…，Am)T，式(1)可以進一步擴展為

P（Y｜A1，…，Am) =[P(A1，…，Am｜Y)P(Y)]/P(X) (2)

為了簡化式(2)的計算，原始的NB方法提出了條件獨立假設和高斯分布假設：假定屬性A1，…，Am相互獨立而且遵循高斯分布，由此可得

P（Y｜A1，…，Am) =[P（Y）ml=1P(Al｜Y)]/P(X)(3)

在實際的流量分類問題中，條件獨立假設和高斯分布假設通常難以滿足。以包頭長度和分組長度的統計值為例，整個分組的長度等于包頭長度加上分組負載長度，兩者之間具有明顯的加法關系，無法實現相互獨立。此外，網絡流統計屬性通常符合多重模態分布 (multi-modal distribution)^[6]，直接使用高斯分布假設將無法有效擬合網絡流屬性的統計分布。因此，直接使用原始的NB方法來處理流量分類問題，將無法保證分類模型的準確率，必須對原始的NB方法進行改進。

針對流量分類問題中原始的網絡流屬性集合難以滿足條件獨立假設和高斯分布假設，Moore 等人采用了FCBF算法來選擇符合條件獨立假設的屬性子集，并采用核估計技術來擬合網絡流屬性的多重模態分布。從他們的實驗結果來看，使用上述兩種改進策略后可以將分類模型的分類準確率從65%提高到95%左右。但是，從式(1)中也明顯可以看出后驗概率P(Y｜X)不僅依賴于類條件概率P(X｜Y)，而且與先驗概率P(Y)相關。先驗概率P(Y)代表類型為Y的網絡流在訓練數據集中的比例，NB方法通常以此來預估類型為Y的網絡流在待測網絡流集合中的比例。然而在實際網絡環境中不同類型的網絡流在網絡流集合中的比例是動態變化的^[1]，NB方法中這種簡單的預估實際上是使用特定條件下的采樣值來預估一個不斷變化的動態值，將無法保證流量分類結果的穩定性。Moore等人的研究雖然優化了類條件概率P(X｜Y)的計算，但他們的改進算法同樣繼承了NB方法對先驗概率的依賴性，同樣具有潛在的不穩定性。

2.2 決策樹方法

決策樹方法是以實例為基礎的歸納學習算法，它從一個無次序、無規則的實例集合中歸納出一組采用樹型結構來表示的分類規則。自20世紀60年代以來，決策樹方法在分類、預測、規則提取等領域得到廣泛應用。利用決策樹處理分類問題通常分為兩步：a）通過訓練集合的學習，形成決策樹分類模型；b）利用生成的決策樹模型對類型未知的樣本進行分類。使用決策樹模型對類型未知樣本進行分類時，從根節點開始逐步對該樣本的屬性進行測試，并沿著相應的分支向下行走，直至到達某個葉節點，此時葉節點所代表的類型即為該樣本的類型^[10]。由此可見，利用決策樹方法進行分類的關鍵是根據訓練集合構建決策樹分類模型，而決策樹分類模型的構建過程又分為以下兩個階段：

a）建樹階段。選取部分訓練樣本，不斷將其進行劃分，每次劃分生成一個節點，每個節點所對應的屬性稱為測試屬性。每次切分都要求分成的組之間差異最大。各種決策樹算法之間的主要區別也就是對這個差異衡量方式的不同。

b）剪枝階段。利用剩余的訓練樣本對生成的決策樹進行檢驗，對不正確的分枝進行調整；通過對決策樹進行剪枝和增加節點，確定最終的決策樹模型。

本文采用了目前廣泛應用于金融、醫療領域的C4.5決策樹算法。該算法根據信息增益率 (information gain ratio)來選擇測試屬性。以實際的流量分類問題為例：已知網絡流樣本集S={X1，X2，…，Xn}。其中，每個樣本可以表示為一個包含m項網絡流屬性的屬性向量(A1，…，Am)T。假設類別屬性Am 具有k個不同的取值，那么根據Am的不同取值可以將樣本集S劃分為C1，C2，…，CK共k個子集，由此可以得出樣本集S對分類的平均信息量：

H(S)=-kp=1P(Cp)log2 P(Cp)(4)

其中：P(Cp)=｜ Cp｜/｜S｜(1≤p≤k)。決策樹的構建過程就是使劃分后不確定性逐漸減小的過程。以任意的離散屬性Ai(1≤i≤m-1)為例，假設Ai存在t個不同的取值aq(1≤q≤t)，那么根據Ai的取值不僅可以將S劃分為S1，S2，…，St共t個子集，還可以將C1，C2，…，Ck這k個子集進一步劃分為k×t個子集，每個子集Cpq表示在Ai=aq的條件下屬于第p類的樣本集合。其中：1≤p≤k，1≤q≤t。由此，選擇離散的非類別屬性Ai進行劃分后，樣本集S對分類的平均信息量為

H（S/Ai）=-tq=1 P(Cq)[-kp=1 P(Cpq)log2P(Cpq)] (5)

其中： P(Cq)=kp=1｜Cpq｜/｜S｜。P(Cpq)=｜Cpq｜/｜S｜，那么利用Ai對S進行劃分的信息增益量(information gain) fG(S，Ai)則等于使用Ai對S進行劃分前后，不確定性下降的程度，即

fG（S，Ai）=H(S)-H(S｜Ai)(6)

由于使用屬性Ai對S進行劃分的信息增益率等于信息增益量與分割信息量(split information)之比，那么可得使用屬性Ai對S進行劃分的信息增益率：

fGR(S，Ai)=fG(S，Ai)/fSP(S，Ai)(7)

其中：分割信息量fSP(S，Ai)=-tl=1(｜Sl｜/｜S｜)log2(Sl｜/｜S｜)。

對于非離散的網絡流屬性，C4.5算法采用離散化其取值空間的策略，將其轉換為離散屬性進行計算。通過選擇具有最大信息增益率的屬性作為測試屬性，C4.5算法自上而下完成決策樹的建樹。為了去除噪聲點和孤立點引起的分枝異常，C4.5采用后剪枝算法對生成的初始決策樹進行剪枝。

從C4.5算法的建樹過程可以看出，訓練數據集中各類樣本的先驗概率對樣本分類結果并無直接影響，因此使用C4.5算法處理流量分類問題時可以有效回避樣本分布動態變化所帶來的影響，其分類穩定性將優于以貝葉斯定理為基礎的NB方法及其采用核估計技術改進的算法(nave Bayes using kernel density estimation，NBK)。

3 實驗環境

3.1 實驗數據

為了便于對比和驗證，本文采用了Moore 等人在參考文獻[6]中所使用的實驗數據集。為了描述方便，稱之為Moore_set。在Moore_set 中包含377 526個網絡流樣本，分為10種類型。每種類型所包含的應用名稱、每類網絡流的數量以及在Moore_set 中所占的比例，如表1所示。Moore_set 中每個樣本都是從一條完整的TCP 雙向流抽象而來，包含249項網絡流屬性。其中最后一項屬性是目標屬性，指明該雙向流的類型；第一和第二項屬性則分別是該TCP 流的源端口號和目的端口號。為了避免對應用端口信息的依賴，本文的所有實驗均未使用這兩個屬性。剩余246種網絡流屬性的描述可參見Moore的技術報告^[11]。

表 1 Moore_set數據集的統計信息

類型應用舉例流數目比例/%WWWwww328 09186.91MAILimap， pop2/3， smtp28 5677.567BULKftp11 5393.056DBpostgres， sqlnet， oracle， ingres2 6480.701SERVX11， dns， ident， ldap， ntp2 0990.556P2PKaZaA， BitTorrent， GnuTella2 0940.555ATTInternet worm and virus attacks1 7930.475MULTWindows Media Player， Real1 1520.305INTssh， klogin， rlogin， telnet1100.029GAMEHalf-Life80.002總計包含25種常見應用377 5261003.2 實驗工具

本文所使用的數據分析工具主要是Weka-3.5.6^[12]。該工具是由新西蘭懷卡托大學Witten 教授等人開發的開源工作平臺，包含決策樹、貝葉斯分類器等多種機器學習方法。該軟件包可以通過互聯網直接從相關的網站上獲取。

4 實驗結果與分析

4.1 分層抽樣

為了對比分析決策樹和樸素貝葉斯方法的分類穩定性，首先將Moore_set數據集均分為兩個數據子集，分別是set1和set2，在這兩個數據子集中每類樣本的比例與Moore_set保持一致。再從set1中分別抽取每類應用0.1%(至少1個)的樣本構成訓練集。在Moore_set包含的249項網絡流屬性中，存在眾多的冗余屬性(redundant attribute)和無關屬性(irrelevant attribute)，這些屬性的存在不僅會降低分類模型的準確率，而且會大大加重分類模型的計算負載。因此，首先使用FCBF方法對訓練數據集進行過濾，然后在完成過濾訓練數據集上分別運行NB、NBK、C4.5三種機器學習算法獲得相應的流量分類模型，并使用這些模型在測試數據集set2上進行驗證。隨后再將訓練數據集的規模逐步提高到1%、10%、50%的set1。重復上述實驗10次，所得實驗結果如圖1所示。

圖1中X軸采用對數坐標表示訓練數據集中樣本的數量；Y軸表示分類模型的準確率；三條曲線分別表示訓練樣本集從191開始逐步增加到1 889、18 876、94 382時，NB、NBK和C4.5算法在10次實驗中的平均分類準確度。

從圖1中可以看出，NB方法由于直接使用高斯分布假設無法有效擬合網絡流屬性分布，導致分類結果明顯較差；而NBK和C4.5方法在這種先驗概率保持不變的情況下，雖然均能夠保持較高的分類準確率，但分類模型的準確率卻隨著訓練數據集的增大而出現輕微抖動。這主要是因為FCBF算法是根據訓練數據集的局部信息對樣本屬性進行過濾，無法從全局角度對分類屬性集合進行優化，必然會導致屬性選擇的局部最優性，進導致分類結果的不穩定。由此可見，NBK和C4.5方法既需要使用屬性過濾機制來滿足條件獨立假設，而又會因為屬性過濾機制的局部最優性而導致分類結果不穩定。因此如何優化網絡流屬性子集的選擇，避免由于局部最優性帶來的分類模型抖動，這將是一個需要進一步深入研究的問題。

4.2 均勻抽樣

為了進一步分析樸素貝葉斯和決策樹兩類方法對樣本先驗概率的依賴程度，本文從set1的網絡流中抽取每種應用的100條隨機樣本(由于MMEDIA、INT、GAMES三種類型的樣本數相對較少，在本實驗中去除這三種類型的樣本)，合成一個各類樣本均等的訓練集。同樣事先采用FCBF算法對訓練數據集進行過濾，再分別運行NB、NBK和C4.5三種機器學習算法獲得相應的流量分類模型，并以此模型在測試數據集set2上進行驗證。依次將訓練數據集中每類樣本的個數提高到300、500、700和897(由于在set1中ATT類型的網絡流樣本只有897個)。重復上述實驗10次，所得實驗結果如圖2所示。

圖2的X軸代表訓練集合中每類樣本的數量；Y軸表示分類模型的準確率；三條曲線分別表示訓練數據集中各類樣本數量從100開始逐步增加到300、500、700、897時，NB、NBK和C4.5算法在10次實驗中的平均分類準確度。

從圖2可以看出，在上述三種機器學習方法的分類結果中，只有C4.5算法隨著訓練集合的逐步增加；分類準確率保持相對穩定的增加，而NB和NBK方法的分類準確率不僅沒有隨著訓練數據集的增大而提高，相反卻出現顯著下降。這不僅是由于FCBF方法的局部最優性所帶來的抖動，更主要是因為訓練數據集和測試數據集中各類樣本分布存在較大差異，而基于貝葉斯定理的NB和NBK方法都是假設先驗概率保持不變。當這一假設條件無法滿足時，NB和NBK方法也就隨之而失效。

在實際網絡流集合中，各種網絡應用所占的比例通常會隨著時間的變化而出現較大差異，因此在運用機器學習方法分類實際網絡流量時，使用依賴于先驗概率的分類算法將無法保證分類結果的穩定性。

5 結束語

利用機器學習方法處理流量分類問題是近年來網絡流量分類領域一個新的研究熱點，其中NB方法及其改進算法以實現簡單、分類速度快而被大多數研究人員所接受。本文通過系統分析NB方法的原理，從理論上證明了以貝葉斯定理為基礎的機器學習方法在處理流量分類問題時具有潛在的不穩定性，并提出一種基于C4.5決策樹的流量分類方法。通過在分層抽樣子集和均勻抽樣子集的對比實驗，可以看出C4.5決策樹方法與NB和NBK方法相比，能夠有效避免樣本分布變化所帶來的不穩定性，在處理流量分類問題時具有明顯的優勢。

參考文獻:

[1]MADHUKAR A， WILLLIAMSON C. A longitudinal study of P2P traffic classification[C]//Proc of the 14th IEEE International Symposium on Modeling， Analysis， and Simulation.2006.

[2]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.

[3]KARAGIANNIS T， PAPAGIANNAKI K， FALOUTSOS M. BLINC: multilevel traffic classification in the dark[C]//Proc of ACM SIGCOMM. 2005.

[4]ROUGHAN M， SEN S， SPATSCHECK O， et al. Class-of -service mapping for QoS: a statistical signature-based approach to IP traffic classification[C]//Proc of ACM SIGCOMM Internet Measurement Conference. 2004.

[5]ZUEV D， MOORE A W. Traffic classification using a statistical approach[C]Proc of the 6th Passive and Active Measurement Workshop. Berlin: Springer，2005:321-324.

[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]NGUYEN T， ARMITAGE G. Training on multiple sub-flows to optimise the use of machine learning classifiers in real-world IP networks[C]//Procof the 31st IEEE LCN. 2006.

[8]ERMAN J， MAHANTI A， ARLITT M. Internet traffic identification using machine learning techniques[C]//Proc of the 49th IEEE GLOBECOM.2006.

[9]LI Ning， CHEN Zi-long， ZHOU Gang.Network traffic classification using rough set theory and genetic algorithm[C]//Proc of ICIC. 2006.

[10]關曉薔.基于決策樹的分類算法研究[D].太原：山西大學，2006.

[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.

[12]WITTEN I H， FRANK E. Data mining: practical machine learning tools and techniques [M].2nd ed.[S.l.]:Elsevier Inc，2005.

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