張治斌，譚 靜

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

0 引 言

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

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

1 決策樹分類模型

1.1 模型原理

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

式中：p（Xi）＝｜Xi｜／｜X｜，｜Xi｜為第i類的網(wǎng)絡(luò)流個數(shù)，｜X｜為網(wǎng)絡(luò)流總數(shù)。對其中一個屬性Qm進(jìn)行測試，設(shè)Qm的值域?yàn)椋鹮1，q2，……，qt｝，數(shù)據(jù)集對Qm的條件熵為M（X，Qm＝qj）log2p（Xi｜Qm＝qj）），其中p（Xi｜Qm＝qj）＝｜Cij｜／｜Yj｜為在測試屬性Qm＝qj時(shí)屬于第i類的決策概率，｜Cij｜為當(dāng)Qm＝qj時(shí)屬于第i類的網(wǎng)絡(luò)流個數(shù)，｜Yj｜為Qm＝qj情況下網(wǎng)絡(luò)流總個數(shù)。選擇屬性Qm進(jìn)行劃分后的對分類的信息熵為

屬性Qm的信息增益為

屬性Qm的信息增益率為

1.2 決策樹構(gòu)建過程

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

1.2.1 決策樹模型的生成

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

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

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

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

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

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

（6）for each A＝Ai

（7）返回（3）

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

圖1 分類模型構(gòu)造過程

1.2.2 分類模型的評估

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

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

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

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

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

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

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

（3）建立簇與標(biāo)簽間的映射關(guān)系，假設(shè)在一個簇內(nèi)的所有樣本的類別都是相同的，簇Ck內(nèi)屬于Yi的樣本概率表示為P（Yi｜Ck），計(jì)算公式為

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

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

2.2 識別模型

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

圖2 流量識別模型

流量采集模塊：此模塊的功能是采集用作離線訓(xùn)練和實(shí)時(shí)識別的網(wǎng)絡(luò)流量。

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

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

識別模塊：用訓(xùn)練好的分類模型對實(shí)時(shí)網(wǎng)絡(luò)流量進(jìn)行在線識別。

2.3 算法描述

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

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

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

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

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

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

步驟7 用新樣本集D1訓(xùn)練決策樹分類模型，并采用十折交叉驗(yàn)證法對分類模型進(jìn)行測試。

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

3.1 實(shí)驗(yàn)準(zhǔn)備

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

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

表1 流特征及描述

3.2 結(jié)果分析

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

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

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

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

從圖3中可以看出，當(dāng)標(biāo)簽樣本數(shù)較少時(shí)，K 值設(shè)置過高反而會影響識別精確率，這是因?yàn)榫垲愡^程中標(biāo)簽樣本過少造成分布信息的反映不全面。隨著標(biāo)簽樣本數(shù)的增多，模型識別準(zhǔn)確率隨之增高，當(dāng)標(biāo)簽樣本數(shù)大于500時(shí)，K 值越大識別精確度越高。在實(shí)際情況中，可以根據(jù)訓(xùn)練集中標(biāo)簽樣本的數(shù)量來設(shè)置K 值大小。

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

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

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

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

4 結(jié)束語

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

［1］LU Gang，ZHANG Hongli，YE Lin.P2Ptraffic identification［J］.Journal of Software，2011，22 （6）：1281－1298 （in Chinese）.［魯剛，張宏莉，葉麟.P2P流量識別 ［J］.軟件學(xué)報(bào)，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）.［劉瓊，劉珍，黃敏.基于機(jī)器學(xué)習(xí)的IP 流量分類研究 ［J］.計(jì)算機(jī)科學(xué)，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ī)器學(xué)習(xí)分類下網(wǎng)絡(luò)流量的特征選取 ［J］.廣西大學(xué)學(xué)報(bào)，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］.軟件學(xué)報(bào)，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）.［盤善榮，傅明，史長瓊.支持向量機(jī)在P2P 流量識別中的應(yīng)用 ［J］.計(jì)算機(jī)工程與科學(xué)，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］.計(jì)算機(jī)科學(xué)，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 的網(wǎng)絡(luò)流量分類方法 ［J］.計(jì)算機(jī)工程，2011，37 （12）：101－103.］