基于K 均值與決策樹(shù)的P2P流量識(shí)別研究

張治斌，譚 靜

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

0 引 言

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

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

1 決策樹(shù)分類模型

1.1 模型原理

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

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

屬性Qm的信息增益為

屬性Qm的信息增益率為

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

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

1.2.1 決策樹(shù)模型的生成

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

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

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

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

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

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

（6）for each A＝Ai

（7）返回（3）

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

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

1.2.2 分類模型的評(píng)估

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

2 基于K－Means與決策樹(shù)的P2P流量識(shí)別模型

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

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

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

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

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

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

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

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

2.2 識(shí)別模型

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

圖2 流量識(shí)別模型

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

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

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

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

2.3 算法描述

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

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

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

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

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

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

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

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種不同的特征屬性，通過(guò)隨機(jī)抽樣從數(shù)據(jù)集中抽取代表非P2P應(yīng)用的數(shù)據(jù)流與P2P應(yīng)用的數(shù)據(jù)流。實(shí)驗(yàn)使用一臺(tái)普通PC（雙核CPU，2G 內(nèi)存，Windows 7操作系統(tǒng)），采用Matlab7.1作為仿真工具。

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

表1 流特征及描述

3.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

［1］LU Gang，ZHANG Hongli，YE Lin.P2Ptraffic identification［J］.Journal of Software，2011，22 （6）：1281－1298 （in Chinese）.［魯剛，張宏莉，葉麟.P2P流量識(shí)別 ［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決策樹(shù)的流量分類方法 ［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）.［盤(pán)善榮，傅明，史長(zhǎng)瓊.支持向量機(jī)在P2P 流量識(shí)別中的應(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流量識(shí)別研究 ［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.］