基于成對(duì)約束擴(kuò)展的半監(jiān)督網(wǎng)絡(luò)流量特征選擇算法*

李平紅，王 勇，陶曉玲

（桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西桂林 541004）

0 引言

網(wǎng)絡(luò)流量分類是指在基于TCP/IP協(xié)議的Internet中，按照網(wǎng)絡(luò)的應(yīng)用類型（例如:WWW，F(xiàn)TP，SMTP，P2P等），將網(wǎng)絡(luò)通信產(chǎn)生的雙向TCP流或UDP流進(jìn)行分類［1］。準(zhǔn)確的網(wǎng)絡(luò)流量分類是網(wǎng)絡(luò)流量監(jiān)控、網(wǎng)絡(luò)入侵檢測(cè)和用戶行為分析等研究工作的基礎(chǔ)。網(wǎng)絡(luò)流量特征選擇是流量分類的關(guān)鍵，它從大量候選特征中刪除無關(guān)或者冗余的特征，降低候選特征維數(shù)，加速分類器建立，直接影響分類的速度和精度。

根據(jù)是否使用標(biāo)記樣本作為監(jiān)督信息，網(wǎng)絡(luò)流量特征選擇算法可以分為有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)［2］，許多特征選擇算法需要大量的標(biāo)記樣本，但已標(biāo)記樣本的獲得往往需要專業(yè)人士的手工勞動(dòng)，數(shù)量少，提供的信息有限。事實(shí)上，監(jiān)督信息除了類標(biāo)記樣本，還可以是樣本間的成對(duì)約束［3］。與類標(biāo)記信息相比，成對(duì)約束獲取代價(jià)小，更容易獲得［4］，成對(duì)約束可由類標(biāo)記產(chǎn)生;反之，則不行。因此，研究成對(duì)約束下的半監(jiān)督特征選擇算法具有一定的實(shí)用價(jià)值。

本文基于 RSC（relevant set correlation）模型［5］，提出一種基于成對(duì)約束擴(kuò)展的半監(jiān)督網(wǎng)絡(luò)流量特征選擇PCFRSC（pairwise constraints feature selection based on RSC model）算法，通過尋找成對(duì)約束樣本點(diǎn)的最相關(guān)鄰居節(jié)點(diǎn)，并將其擴(kuò)展到大量未標(biāo)記的樣本點(diǎn)上，通過少量的成對(duì)約束和大量的無標(biāo)記樣本有效地進(jìn)行流量特征選擇，解決網(wǎng)絡(luò)流量分類中監(jiān)督信息有限的問題。

1 相關(guān)理論

到目前為止，成對(duì)約束下的特征選擇的方法研究比較少見，最具代表性的是張道強(qiáng)教授等人提出的基于成對(duì)約束的特征選擇算法Constraint Score［6］，首次嘗試使用成對(duì)約束作為監(jiān)督信息進(jìn)行特征選擇，但他只使用了少量的監(jiān)督信息而忽略了大量無標(biāo)記數(shù)據(jù)可能隱藏的重要信息。文獻(xiàn)［7］提出的特征選擇算法能同時(shí)利用正約束和負(fù)約束信息，但沒有利用在未標(biāo)記樣本中隱藏的潛在信息來實(shí)現(xiàn)半監(jiān)督特征選擇。Zhang D Q等人提出一種半監(jiān)督維數(shù)約減（SSDR）算法［8］，該算法能同時(shí)保持成對(duì)約束的結(jié)構(gòu)和未標(biāo)記數(shù)據(jù)在低維流形的結(jié)構(gòu)，其缺點(diǎn)是沒有考慮低維流形的局部結(jié)構(gòu)。文獻(xiàn)［9］提出將類標(biāo)號(hào)從少量的訓(xùn)練樣本集擴(kuò)展到大量的未標(biāo)記樣本的框架，實(shí)驗(yàn)證明其有一定的有效性，但仍未能充分利用大量未標(biāo)記樣本。王博［10］針對(duì)半監(jiān)督信息缺乏的情況，提出一種半監(jiān)督的特征選擇算法SFRSC，對(duì)少量的已標(biāo)記樣本進(jìn)行了擴(kuò)展，但其假設(shè)初始的已標(biāo)記樣本集中包含了所有的類別信息，也沒有考慮容易獲得的樣本間的成對(duì)約束關(guān)系。

2 基于成對(duì)約束擴(kuò)展的半監(jiān)督網(wǎng)絡(luò)流量特征選擇算法

2．1 RSC 模型

學(xué)者Houle M E首次提出RSC模型，隨后將RSC模型運(yùn)用于無監(jiān)督特征選擇，提出了RSCF算法［11］。本文的研究與之類似，但不同的是:RSCF算法僅利用了未標(biāo)記樣本的無監(jiān)督算法，而本文的算法是同時(shí)利用了成對(duì)約束和未標(biāo)記樣本的半監(jiān)督學(xué)習(xí)方法。

樣本集間的相關(guān)度和樣本集的自相關(guān)度的定義如下:

定義1 設(shè)A，B?S，|S|表示結(jié)合中元素的個(gè)數(shù)，則集合A與B的相關(guān)度可表示為

定義2 集合A在全集S上的自相關(guān)度定義為

式中Q（v，|A|表示由v的|A|個(gè)近鄰組成的樣本序列，A的相關(guān)度由集合A中所有元素決定，對(duì)任意v∈A，如果v與所有的v∈A/v都是強(qiáng)相關(guān)的，而v與所有的v'∈S/A都是弱相關(guān)的，則S中與v相似度高的樣本都屬于A。

2．2 擴(kuò)展成對(duì)約束

原始的成對(duì)約束集稱為初始約束集，它包括正約束（must-link，ML）和負(fù)約束（cannot-link，CL）。ML表示 2 個(gè)樣本屬于同一類，CL表示2個(gè)樣本不屬于同一類。為達(dá)到擴(kuò)充訓(xùn)練集的目的，需從初始成對(duì)約束集擴(kuò)展出新的成對(duì)約束ML＇和CL＇，這些新擴(kuò)展的樣本又可以作為核心點(diǎn)繼續(xù)向四周擴(kuò)展。成對(duì)約束雖然包括正約束和負(fù)約束，由于在實(shí)際計(jì)算過程中，正約束只能擴(kuò)展出正約束，負(fù)約束卻可以同時(shí)擴(kuò)展出正約束和負(fù)約束，因此，為提高算法性能，算法只使原始約束集中的負(fù)約束進(jìn)行擴(kuò)展。

對(duì)任意一個(gè)負(fù)約束（x，y）∈CL，首先利用式（3）得到K1，那么在訓(xùn)練集S中，包含x的具有最大的內(nèi)相關(guān)性樣本集就是A=Q（x，k1），這表明A中的樣本相關(guān)性強(qiáng)，因此，它們應(yīng)該屬于同一類

同理，可求得y的同類樣本集合B。利用集合A和B，可得到新的正約束集合ML＇和新的負(fù)約束集合CL＇分別是

以圖1～圖3為例來形象地說明約束擴(kuò)展的過程。如圖1所示，空心圓表示未知類型樣本，實(shí)心的形狀表示成對(duì)約束，不同形狀的實(shí)心形狀表示不同的類別，相同形狀的實(shí)心圓表示同種類別。圖1表示的是初始情況，表示有4種不同的類別樣本。以圖1為核心，根據(jù)式（3）得各自的集合A。在A中，未標(biāo)記的樣本點(diǎn)和實(shí)心的樣本所屬的類別相同，經(jīng)過第一步的擴(kuò)展得到圖2。圖3又把圖2作為起始點(diǎn)重復(fù)第一步的過程進(jìn)行擴(kuò)展。直到所有的樣本點(diǎn)都被預(yù)測(cè)，擴(kuò)展才結(jié)束。但該擴(kuò)展中存在一個(gè)問題，在最后的劃分結(jié)果中可能出現(xiàn)約束違反問題（即劃分重疊），如圖3中的點(diǎn)P同時(shí)屬于實(shí)心圓和實(shí)心五邊形兩類，原因在于用于劃分的式（3）得到的是局部最優(yōu)。圖3中的P點(diǎn)同時(shí)屬于多類別的劃分是應(yīng)該避免的，將在3．3節(jié)中給出詳細(xì)的解決方案。

圖1 約束擴(kuò)展過程（1）Fig 1 Constraints extension process（1）

圖2 約束擴(kuò)展過程（2）Fig 2 Constraints extension process（2）

圖3 約束擴(kuò)展過程（3）Fig 3 Constraints extension process（3）

2．3 消除違法約束

由圖1～圖3可知，在把負(fù)約束（x，y）∈CL擴(kuò)展出集合A和B的過程中，可能存在樣本v∈A∩B，由它擴(kuò)展出新成對(duì)約束（x，v）∈ML'，（y，v）∈ML'，，由傳遞性可知（x，y）∈ML'，即x，y屬于正約束對(duì)，這與（x，y）∈CL相矛盾，此時(shí)便產(chǎn)生了成對(duì)約束違反問題。解決這個(gè)問題的方法就是將v劃分給一個(gè)集合A或者B，劃分依據(jù)是通過分別計(jì)算v對(duì)集合A或者B的自相關(guān)度貢獻(xiàn)來判斷其歸屬，貢獻(xiàn)大小由式（4）中的IR1評(píng)估，值越大表示貢獻(xiàn)越大

計(jì)算IR1（v|A）和IR2（v|B），若IR1（v|A）＞IR2（v|B），表明v對(duì)集合A的貢獻(xiàn)越大，因此，把v劃分給集合A;反之，則把v劃分給集合B。如果IR1（v|A）=IR2（v|B），則隨機(jī)選擇類型。

注意到，式（4）中，只考慮了樣本v對(duì)單個(gè)集合自相關(guān)度的貢獻(xiàn)，而未考慮劃分v后對(duì)集合A，B產(chǎn)生的影響。式（5）基于這樣的思想:同時(shí)考慮v對(duì)單個(gè)集合的自相關(guān)度的影響和v劃分后對(duì)2個(gè)集合的相關(guān)度的影響。把v劃分給A，當(dāng)且僅當(dāng)v對(duì)A的自相關(guān)度高，且把v劃給A后的集合與集合B的相關(guān)度弱。通過利用式（5）計(jì)算比較IR2（v|A，B）和IR2（v|B，A），當(dāng)IR2（v|A，B）＞IR2（v|B，A）時(shí)，把v劃分給A;否則，把v劃分給B

2．4 PCFRSC 算法描述

Input:training data setX={xi}，Must-link setML，Cannot-link setCL

Output:Extended set of constraintsML'andCL'

1）InitializingML'=ML，CL'=CL

2）foreach Cannot-link（x，y）inCL

b．A=Q（x，k1），B=Q（y，k2）

c．If there isv∈A∩B，dividevto eliminate the constraint violation by the formula（5），if there is no，jump to 2．4

d．Extending pairwise constraints．

3）returnMLandCL＇．

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

3．1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用劍橋大學(xué)計(jì)算機(jī)系Moore A W教授等人在文獻(xiàn)［12］中所用的實(shí)驗(yàn)數(shù)據(jù)集，本文簡(jiǎn)稱Moore-set。Mooreset共有377526條數(shù)據(jù)，是目前最權(quán)威的網(wǎng)絡(luò)流量數(shù)據(jù)集，它包含10個(gè)數(shù)據(jù)子集，每一個(gè)數(shù)據(jù)子集均包含數(shù)萬條數(shù)據(jù)。每條流包含249項(xiàng)屬性，由端口號(hào)等網(wǎng)絡(luò)屬性和平均間隔時(shí)間等統(tǒng)計(jì)屬性組成。最后一項(xiàng)屬性為分類目標(biāo)屬性，表明該樣本的流量類型，如WWW，F(xiàn)TP，P2P等。

實(shí)驗(yàn)過程中，選用已有的成對(duì)約束特征選擇算法Constraints-Score1（Cs1）和 Constraints-Score2（Cs2）［6］，且設(shè)定Cs2的參數(shù)=0．1，與本文提出的PCFRSC算法相比較。分類器使用Weka軟件中的3-nearest-neighbor分類器（3nn）。實(shí)驗(yàn)所用的數(shù)據(jù)處理和分析工具是Matlab 7．1和Weka 3．7。Moore-set總體流量數(shù)據(jù)統(tǒng)計(jì)信息如表1所示。

表1 Moore-setTab 1 Moore-set

3．2 在分層抽樣子集上的分類效果

從10個(gè)Moore-set數(shù)據(jù)子集中隨機(jī)抽出2個(gè)子集，分別稱作set-u和set-t，這2個(gè)樣本中每類樣本的比例與Mooreset保持一致，從set-u中抽取每類應(yīng)用的1%的樣本作為訓(xùn)練集，用PCFRSC，Cs1和Cs2在此訓(xùn)練集上訓(xùn)練獲得相應(yīng)的網(wǎng)絡(luò)流量分類器，并用測(cè)試數(shù)據(jù)集set-t對(duì)訓(xùn)練出的分類器進(jìn)行驗(yàn)證。實(shí)驗(yàn)重復(fù)10次，對(duì)結(jié)果取平均值，比較Cs1、Cs2和PCFRSC在不同原始成對(duì)約束下的分類精度，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 分層抽樣下的分類性能Fig 4 Classified property in stratified sampling

從圖4可以看出:在分層抽樣的條件下，PCFRSC算法的分類精度明顯高于Cs1和Cs2，但在成對(duì)約束較少的情況下，PCFRSC相對(duì)于Cs1和Cs2沒有明顯的優(yōu)勢(shì)，而當(dāng)成對(duì)約束的數(shù)量超過15，PCFRSC算法分類精確的提高非常明顯，雖然Cs1和Cs2的精度也呈現(xiàn)增長(zhǎng)的趨勢(shì)，而是提高比較緩慢。說明PCFRSC能在成對(duì)約束有限的情況下，擴(kuò)展成對(duì)約束，較充分地利用成對(duì)約束和無標(biāo)記樣本來進(jìn)行特征選。但當(dāng)成對(duì)約束的數(shù)量比較多時(shí)，PCFRSC和Cs1，Cs2的分類精度反而有所下降，這說明當(dāng)成對(duì)約束的數(shù)量較多時(shí)算法并不敏感，過多的先驗(yàn)知識(shí)不能過快地提高分類精度。

3．3 在均勻抽樣子集上的分類效果

分別抽取Moore-set每個(gè)應(yīng)用類型的1 000個(gè)樣本（由于INTERACTIVE和GAMES的數(shù)量較少，不具代表性，因此，在本實(shí)驗(yàn)中不采用這2種數(shù)據(jù)），形成一個(gè)新的各類樣本數(shù)量相等的訓(xùn)練集set-u1，從10個(gè)Moore-set中隨機(jī)選擇一個(gè)子集作為測(cè)試集set-t1。用PCFRSC，Cs1和Cs2在此訓(xùn)練集上訓(xùn)練獲得相應(yīng)的網(wǎng)絡(luò)流量分類器，并用測(cè)試數(shù)據(jù)集set-t1對(duì)訓(xùn)練出的分類器進(jìn)行驗(yàn)證。實(shí)驗(yàn)重復(fù)10次，對(duì)結(jié)果取平均值。比較比較Cs1，Cs2和PCFRSC在不同成對(duì)約束下的分類精度，實(shí)驗(yàn)結(jié)果如圖5所示:

圖5 均勻抽樣下的分類性能Fig 5 Classified property in uniform sampling

從圖5可以看出:在分層抽樣的條件下，PCFRSC算法的分類精度也明顯高于Cs1和Cs2，PCFRSC整體上還保持了較高的分類精度和較好穩(wěn)定性，分類精度平均提高了4%左右，在原始成對(duì)約束在20～25之間的時(shí)候，表現(xiàn)出了最佳的分類性能。但PCFRSC的性能也不是隨著成對(duì)約束的增多而不斷提高，當(dāng)約束的數(shù)量較多時(shí)，PCFRSC的分類性能反而下降，因?yàn)槌蓪?duì)約束越多，由約束擴(kuò)展產(chǎn)生噪音樣本的可能性就越大，計(jì)算的復(fù)雜度也越高。但總體而言，新的成對(duì)約束擴(kuò)展方法PCFRSC是有效和可行的。

當(dāng)訓(xùn)練集的樣本構(gòu)成比例不一樣時(shí)，對(duì)特征選擇和分類效果也會(huì)產(chǎn)生不同的影響。分層抽樣的方法更利于大樣本，均勻抽樣的方法更利于小樣本。從圖4和圖5可知，約束擴(kuò)展能較好地彌補(bǔ)成對(duì)約束數(shù)量上的不足，擴(kuò)展的成對(duì)約束在一定程度上反應(yīng)了數(shù)據(jù)的分布信息，兩者相互促進(jìn)。在監(jiān)督信息較少的情況下，半監(jiān)督特征選擇方法能同時(shí)利用少量有限監(jiān)督信息和大量無監(jiān)督信息，保證了成對(duì)約束擴(kuò)展的健壯性。

4 結(jié)束語

本文基于RSC模型提出了一種半監(jiān)督網(wǎng)絡(luò)流量特征選擇算法PCFRSC，該算法以原始成對(duì)約束為核心，將其擴(kuò)展到未標(biāo)記樣本上，同時(shí)進(jìn)一步解決了成對(duì)約束違反問題。與未進(jìn)行成對(duì)約束擴(kuò)展的算法相比，PCFRSC算法是比較有效的。但PCFRSC還存在一些需進(jìn)一步改進(jìn)的地方，比如建模的時(shí)間較長(zhǎng)，分類的精度還有再提升空間。

［1］ 張 賓，楊家海，吳建平．Internet流量模型分析與評(píng)述［J］．軟件學(xué)報(bào)，2011，22（1）:115 －131．

［2］ 劉 瓊，劉 珍，黃 敏．基于機(jī)器學(xué)習(xí)的 IP流量分類研究［J］．計(jì)算機(jī)科學(xué)，2010（37）:35－39．

［3］ Ming Yang，Jing Song．A novel hypothesis-margin based approach for feature selection side pairwise constraints［J］．Neurocomputing，2010，73:2859 －2872．

［4］ 韋 佳，彭 宏．基于局部與全局保持的維數(shù)約減方法［J］．軟件學(xué)報(bào)，2008，11（19）:2833 －2842．

［5］ Houle M E．The relevant-set correlation model for data clustering［J］．Statistical Analysis and Data Mining，2008（1）:157 －176．

［6］ Zhang D，Chen S，Zhou Z．Constraint score:A new filter method for feature selection with pairwise constraints［J］．Pattern Recognition，2008，41（5）:1440 －1451．

［7］ Yeung D Y，Chang H．Extending the relevant component analysis algorithm for metric learning using both positive and negative equivalence constraints［J］．Pattern Recognition，2006，39（5）:1007－1010．

［8］ Zhang D Q，Zhou Z H，Chen S C．Semi-supervised dimensionality reduction［C］∥Proc of the 7th SIAM Int'l Conf on Data Mining，2007:629－634．

［9］ Ren Jiangtao，Qiu Zhenyuan，F(xiàn)an Wei，et al．Forward semi-supervised feature selection［C］∥PAKDD，2008:970 －976．

［10］王 博，賈 焰，田 李．基于類標(biāo)號(hào)擴(kuò)展的半監(jiān)督特征選擇算法［J］．計(jì)算機(jī)科學(xué)，2009（36）:189－191．

［11］ Houle M E，Nizar Grira．A correlation-based model for unsupervised feature selection［C］∥CIKM，2007:897 －900．

［12］ Moore A W，Zuev D．Internet traffic classification using Bayesian analysis techniques［C］∥Proc of 2005 ACM SIGMETRICS Int'l Conf on Measurement and Modeling of Computer Systems，2005:50－60．