張治斌，譚 靜

（1.河南理工大學 現(xiàn)代教育技術中心，河南 焦作454003；2.河南理工大學 計算機科學與技術學院，河南 焦作454003）

0 引 言

在P2P網絡管理中，P2P 流量識別已經成為網絡領域需要研究的一個核心課題［1］。早期的流量識別技術通過端口號和應用層載荷特征進行識別。但是P2P在后來的發(fā)展中采用了隨機動態(tài)端口，端口偽裝以及應用層數(shù)據(jù)加密等技術，使得它們的識別準確度無法保證，因此基于機器學習的識別方法成為了目前研究的熱點［2］。文獻［3］使用KMeans算法識別不同網絡流，Erman等人［4］用EM 算法來分類網絡流量，并與貝葉斯方法進行比較。此類無監(jiān)督學習方法可以直接聚類沒有類別標記的訓練樣本，因此可以發(fā)現(xiàn)新的網絡應用，但是具有穩(wěn)定性差，計算資源耗費大的缺點。徐鵬等人［5］提出了基于決策樹的流量識別方法，文獻［6］使用支持向量機對P2P流量進行識別。該類有監(jiān)督學習方法在分類精度和時間方面展現(xiàn)出很好的性能，但是用來建立分類器的大量高品質標簽樣本難以獲取。文獻［7］提出了基于K－Means的半監(jiān)督流量分類方法，利用少量標記樣本和大量無標記樣本進行聚類，具有較好的分類效果，但其分類準確率一般低于有監(jiān)督學習方法。

本文針對這些不足提出了一種基于K 均值與決策樹的P2P流量分類模型，該模型首先利用基于K 均值的半監(jiān)督分類算法對數(shù)據(jù)樣本進行預處理，然后用處理過的樣本訓練決策樹識別模型。在標記樣本較少的情況下，對P2P 流量具有較高的識別精度。

1 決策樹分類模型

1.1 模型原理

決策樹是一種有監(jiān)督學習的方法，它是利用歸納的方法通過對建立的屬性葉子節(jié)點進行測試從而形成的一種樹形結構的學習規(guī)則。本文采用的是決策樹中最經典的C4.5算法，在屬性的選擇上，它采用信息增益率作為標準，選擇信息增益率大的屬性產生節(jié)點，進而再根據(jù)屬性的不同取值建立不同的分支，在分支上通過重復該方法再建立分支，直到一個分支僅包含同一類別的數(shù)據(jù)。在流量識別問題上，設網絡流訓練樣本數(shù)據(jù)集X＝｛X1，X2，……，Xn｝，它的屬性集Q＝｛Q1，Q2，……，Qm｝，通過訓練，將網絡流劃分為不同類別的信息熵為

式中：p（Xi）＝｜Xi｜／｜X｜，｜Xi｜為第i類的網絡流個數(shù)，｜X｜為網絡流總數(shù)。對其中一個屬性Qm進行測試，設Qm的值域為｛q1，q2，……，qt｝，數(shù)據(jù)集對Qm的條件熵為M（X，Qm＝qj）log2p（Xi｜Qm＝qj）），其中p（Xi｜Qm＝qj）＝｜Cij｜／｜Yj｜為在測試屬性Qm＝qj時屬于第i類的決策概率，｜Cij｜為當Qm＝qj時屬于第i類的網絡流個數(shù)，｜Yj｜為Qm＝qj情況下網絡流總個數(shù)。選擇屬性Qm進行劃分后的對分類的信息熵為

屬性Qm的信息增益為

屬性Qm的信息增益率為

1.2 決策樹構建過程

構建決策樹模型包括分類器的訓練和分類器的測試兩個階段。在分類器的訓練階段，首先通過訓練生成一棵初始決策樹，然后通過剪枝處理對決策樹進行簡化，最后提取分類規(guī)則建立分類器。分類器建立后，為了評估分類模型的準確性，在第二階段需要用測試數(shù)據(jù)集對其進行測試。

1.2.1 決策樹模型的生成

在C4.5算法中，生成初始決策樹的關鍵在于根據(jù)信息增益率選擇每個節(jié)點的最佳測試屬性。構建C4.5決策樹的算法過程如下：

（1）對樣本集的連續(xù)特征進行離散化處理。

（2）對決策樹T 進行初始化，使得T 只包含一個根節(jié)點（X，Q），X 為樣本集，Q 為屬性集。

（3）if（葉節(jié)點（X’，Q’）中的X’屬于同一類別或者Q’為空）

（4）任選一個不滿足上述條件的節(jié)點（X’，Q’）

（5）選擇滿足條件max（ratio（X’，Q’m））的屬性A 對節(jié)點（X’，Q’）進行測試。

（6）for each A＝Ai

（7）返回（3）

初始決策樹生成后，為了消除統(tǒng)計噪聲或數(shù)據(jù)波動對決策樹的影響，對決策樹采用后剪枝算法進行修剪，不具有代表性的葉節(jié)點或分支將被從決策樹中剪去，達到簡化決策樹的目的。剪枝完成后，提取算法生成的分類規(guī)則來建立分類器，分類規(guī)則是從決策樹的根節(jié)點到其中任意一個葉節(jié)點的路徑的集合，通常用if－then的形式來表示。分類模型構造過程如圖1所示。

圖1 分類模型構造過程

1.2.2 分類模型的評估

為了評估分類模型的準確性，需要用創(chuàng)建好的分類模型對與訓練集相互獨立的測試集進行預測，然后將結果與實際值進行比對，本文采用十折交叉驗證法對分類模型進行驗證，把數(shù)據(jù)集分為十份，其中一份作為測試集，其余九份輪流作為訓練集，十次測試準確率的平均值即為分類模型的精度。

2 基于K－Means與決策樹的P2P流量識別模型

在機器學習算法中，有監(jiān)督學習比無監(jiān)督學習具有更高的檢測精度和分類速度，而在有監(jiān)督學習中，經過各類研究的對比驗證，決策樹算法在流量分類精度和時間方面，比支持向量機、貝葉斯算法和神經網絡等顯示出了更好的性能，但是，由于使用決策樹算法建立分類模型時，在離線學習階段需要利用大量的高品質標簽樣本進行訓練來提高算法的準確性，而現(xiàn)實中，標簽樣本的獲得隨著P2P 流量的加密變得越來越困難，基于這個問題，本文在使用決策樹算法建立分類模型之前，采用K－Means半監(jiān)督聚類算法對含有大量無標簽樣本和少量標簽樣本的訓練數(shù)據(jù)集進行預處理，利用標簽樣本建立的映射關系得到不同簇的類別，進而獲取無標簽樣本的類別標記，實現(xiàn)在只有少量標簽樣本的情況下，分類模型也能保持較高的識別精度。

2.1 K－Means半監(jiān)督聚類

K－Means聚類一般利用無標簽樣本進行聚類，無法利用標簽樣本提供的有效信息，使得對樣本的聚類精確度受到限制，為提高聚類的準確性，為決策樹訓練提供準確的標簽樣本，本文采用K－Means半監(jiān)督聚類來實現(xiàn)對數(shù)據(jù)集的預處理，算法思想描述如下：

（1）將標簽樣本和無標簽樣本合并為一個樣本集X＝｛X1，X2，……，Xn｝，第i個樣本的類別用Yi表示，標簽樣本的Yi已知，無標簽樣本的Yi未知，任一樣本向量可以表示為（Xi1，Xi2，……，Xij），Xij為第i個樣本的第j個特征。

（2）用K－Means算法［8］進行聚類，將樣本集劃分為K個不同的簇｛C1，C2，……，Ck｝。

（3）建立簇與標簽間的映射關系，假設在一個簇內的所有樣本的類別都是相同的，簇Ck內屬于Yi的樣本概率表示為P（Yi｜Ck），計算公式為

式中：njk——Ck中標記為Yi的樣本數(shù)，nk——Ck中的總樣本數(shù)。

（4）最后通過簇標簽決策函數(shù)來確定Ck中的樣本類別，計算公式為

2.2 識別模型

根據(jù)上述思想描述建立流量識別模型，該模型包含4個模塊，如圖2所示。

圖2 流量識別模型

流量采集模塊：此模塊的功能是采集用作離線訓練和實時識別的網絡流量。

特征提取模塊：對采集的流量的統(tǒng)計特征進行選擇，篩選出對分類有價值的特征，以實現(xiàn)降維，提高分類效率。

離線訓練模塊：該模塊的功能是通過訓練得到分類模型。用K－Means半監(jiān)督算法對訓練樣本集進行聚類，通過計算最大后驗概率來確定簇類別，形成新的訓練樣本集，最后進行決策樹分類模型的訓練。

識別模塊：用訓練好的分類模型對實時網絡流量進行在線識別。

2.3 算法描述

基于K 均值與決策樹的P2P流量識別算法描述如下：

步驟1 將準備的標簽樣本集M＝｛（xi，yi）｜i＝1，2，……，m｝和無標簽樣本集N＝｛xj｜j＝1，2，……，n｝合并為一個樣本集D，對D 進行特征提取。

步驟2 從混合樣本集D 中任意選取K 個對象作為初始聚類中心。

步驟4 分配完畢后，重新計算每個簇中樣本的平均值，作為新的聚類中心。

步驟5 將新的聚類中心與上一次的聚類中心進行比較，如果不同，轉步驟2，如果相同，轉步驟6。

步驟6 通過聚類得到K 個不同的簇C＝｛ci｜i＝1，2，……，k｝，根據(jù)最大后驗概率確定簇類別，對簇中無標簽樣本進行標記，與之前的標簽樣本混合形成新的樣本集D1。

步驟7 用新樣本集D1訓練決策樹分類模型，并采用十折交叉驗證法對分類模型進行測試。

3 實驗與結果分析

3.1 實驗準備

實驗采用Moor數(shù)據(jù)集［9］，Moor數(shù)據(jù)集將網絡應用類型分成了10類，共包含249種不同的特征屬性，通過隨機抽樣從數(shù)據(jù)集中抽取代表非P2P應用的數(shù)據(jù)流與P2P應用的數(shù)據(jù)流。實驗使用一臺普通PC（雙核CPU，2G 內存，Windows 7操作系統(tǒng)），采用Matlab7.1作為仿真工具。

在機器學習流量識別方法中，對流統(tǒng)計特征的選擇往往對識別結果的準確性有非常大的影響，所以在選擇特征時，要盡量剔除無關的特征，留下對分類有價值的特征。本文對Moore提出的249個流特征采用FCBF 算法［10］，從中選擇出8個特征組合成特征子集，如表1所示，特征名＿ab表示客戶端到服務器端，特征名＿ba表示服務器端到客戶端。

表1 流特征及描述

3.2 結果分析

實驗從兩個方面對識別模型的性能進行了分析：標簽樣本數(shù)與K 值對識別模型精度的影響以及不同標簽樣本數(shù)對兩種識別模型的準確率影響。

（1）標簽樣本數(shù)與K 值對識別模型精度的影響

由于模型采用k－means半監(jiān)督聚類對訓練樣本集進行預處理，聚類效果與K 值的選擇有很大關系，而標簽樣本為聚類提供了有效的樣本分布信息，所以K 值的大小以及標簽樣本的多少對識別模型的精度都有一定的影響。為了對比標簽樣本數(shù)、K 值與識別精度的關系，實驗設置3組不同K 值（K＝10，20，30），在標簽樣本數(shù)變化的情況下，對識別準確率的影響如圖3所示。

圖3 標簽樣本數(shù)、K 值大小與識別精度的關系

從圖3中可以看出，當標簽樣本數(shù)較少時，K 值設置過高反而會影響識別精確率，這是因為聚類過程中標簽樣本過少造成分布信息的反映不全面。隨著標簽樣本數(shù)的增多，模型識別準確率隨之增高，當標簽樣本數(shù)大于500時，K 值越大識別精確度越高。在實際情況中，可以根據(jù)訓練集中標簽樣本的數(shù)量來設置K 值大小。

（2）不同標簽樣本數(shù)對兩種識別模型的準確率影響

為了進一步測試識別模型的準確率，分別在訓練集中標簽樣本數(shù)為50、100、200、500、1000、2000的情況下，使用本文識別模型與決策樹識別模型進行分類實驗，結果如圖4所示。

圖4 兩種模型識別精度與標注樣本數(shù)的關系

圖4結果表明，在訓練集中標簽樣本數(shù)較少時，本文識別模型表現(xiàn)出了較高的識別精度，隨著標簽樣本數(shù)的增加，兩種識別模型的精度逐漸增高，標簽樣本數(shù)大于1000時，兩者的識別精度幾乎相同。實驗表明，在現(xiàn)實大量標簽樣本難獲得的情況下，基于K 均值與決策樹的識別模型能保持較高的識別準確率。

4 結束語

現(xiàn)階段針對有監(jiān)督學習的流量識別方法的研究很多，但是隨著越來越多的P2P流量使用加密技術，訓練分類器需要的標注樣本變得更加難以獲得，從而大大限制了識別的準確度。本文引入一種基于K 均值與決策樹的P2P流量識別模型，該模型首先利用基于K 均值的半監(jiān)督聚類算法對包含少量標記樣本和大量未標記樣本的數(shù)據(jù)集進行預處理，利用已標記樣本建立映射關系，從而獲得未標記樣本的類別信息，最后利用標記過的樣本集訓練決策樹分類模型，實驗結果表明，在標簽樣本較少的情況下，這種方法能保持較高的識別精度。下一步將利用更多的流量特征對識別模型進行改進以提高識別性能。

［1］LU Gang，ZHANG Hongli，YE Lin.P2Ptraffic identification［J］.Journal of Software，2011，22 （6）：1281－1298 （in Chinese）.［魯剛，張宏莉，葉麟.P2P流量識別 ［J］.軟件學報，2011，22 （6）：1281－1298.］

［2］LIU Qiong，LIU Zhen，HUANG Min.Study on internet traffic classification using machine learning ［J］.Computer Science，2010，37 （12）：35－66 （in Chinese）.［劉瓊，劉珍，黃敏.基于機器學習的IP 流量分類研究 ［J］.計算機科學，2010，37 （12）：35－66.］

［3］ZHANG Longcan，LIU Bin，LI Zhitang.Characteristics selection of network traffic under machine learning classification［J］.Journal of Guangxi University，2011，36 （z1）：6－10 （in Chinese）.［張龍璨，柳斌，李芝棠.機器學習分類下網絡流量的特征選取 ［J］.廣西大學學報，2011，36 （z1）：6－10.］

［4］Erman J，Mahanti A，Arlitt M.Internet traffic identification using machine learning techniques［C］／／San Francisco，USA：Proc of 49th IEEE Global Telecommunications Conference，2006.

［5］XU Peng，LIN Sen.Internet traffic classification using C4.5 decision tree［J］.Journal of Software，2009，20 （10）：2692－2704 （in Chinese）.［徐鵬，林森.基于C4.5決策樹的流量分類方法 ［J］.軟件學報，2009，20 （10）：2692－2704.］

［6］PAN Shanrong，F(xiàn)U Ming，SHI Changqiong.Application of the supporting vector machine in P2Ptraffic identification ［J］.Computer Engineering and Science，2010，32 （2）：38－113 （in Chinese）.［盤善榮，傅明，史長瓊.支持向量機在P2P 流量識別中的應用 ［J］.計算機工程與科學，2010，32 （2）：38－113.］

［7］Kritchman S，Nadler B.Non－parametric detection of the number of signals：Hypothesis testing and random matrix theory［J］.IEEE Transactions on Signal Processing，2009，57（10）：3930－3941.

［8］LIU Sanmin，SUN Zhixin，LIU Yuxia.Research on P2Ptraffic identification based on K－means ensemble and SVM ［J］.Computer Science，2012，39 （4）：46－74 （in Chinese）.［劉三民，孫知信，劉余霞.基于K 均值集成和SVM 的P2P流量識別研究 ［J］.計算機科學，2012，39 （4）：46－74.］

［9］Li Wei，Canini M，Moore W.Efficient application identification and the temporal and spatial stability of classification schema［J］.Computer Networks，2009，53 （1）：790－809.

［10］ZHU Xin，ZHAO Lei，YANG Jiwen.Network traffic classification method based on concept－adapting very fast decision tree［J］.Computer Engineering，2011，37 （12）：101－103（in Chinese）.［朱欣，趙雷，楊季文.基于CVFDT 的網絡流量分類方法 ［J］.計算機工程，2011，37 （12）：101－103.］