基于卡方方法及對(duì)稱不確定性的網(wǎng)絡(luò)流量特征選擇方法

（長(zhǎng)春理工大學(xué) 理學(xué)院，長(zhǎng)春 130022）

隨著網(wǎng)絡(luò)技術(shù)的日益發(fā)展，互聯(lián)網(wǎng)已經(jīng)成為人們獲取和共享信息資源的非常重要的方式。但同時(shí)由于互聯(lián)網(wǎng)的飛速發(fā)展，互聯(lián)網(wǎng)的用戶規(guī)模、網(wǎng)絡(luò)應(yīng)用種類以及網(wǎng)絡(luò)流量數(shù)據(jù)也隨之急劇增長(zhǎng)，使得網(wǎng)絡(luò)結(jié)構(gòu)愈加復(fù)雜，這就對(duì)網(wǎng)絡(luò)管理、維護(hù)和檢測(cè)技術(shù)提出更高的要求。

網(wǎng)絡(luò)流量分類是指按照各個(gè)應(yīng)用的屬性將大量的混合網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行歸類的過程［1］。但是由于互聯(lián)網(wǎng)的用戶對(duì)各種網(wǎng)絡(luò)應(yīng)用的使用頻率不同，使得各個(gè)網(wǎng)絡(luò)應(yīng)用的數(shù)據(jù)出現(xiàn)了不平衡現(xiàn)象。如劍橋大學(xué)Moore等提供的數(shù)據(jù)集，共包括10個(gè)數(shù)據(jù)集，涵蓋了12類的網(wǎng)絡(luò)流量數(shù)據(jù)，共377526個(gè)樣本［3］。但是Moore數(shù)據(jù)集卻是一個(gè)數(shù)據(jù)不均衡數(shù)據(jù)集，其中大類別（WWW類）占總樣本的85%以上，而小類別（ATTACK、INTERACTIVE類等）在總樣本中所占比例不足1%，故對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行分類時(shí)，得到的分類模型對(duì)大類別效果更好，而對(duì)小類別效果欠佳，因此關(guān)注點(diǎn)不能只是整體的分類準(zhǔn)確率，應(yīng)對(duì)各個(gè)類別的召回率考慮更加重視。如直接對(duì)Moore數(shù)據(jù)集分類時(shí)，由于WWW類別樣本的個(gè)數(shù)較多，其召回率也高達(dá)90%以上，但是由于ATTACK類別樣本數(shù)量小，其召回率只達(dá)50%左右。

盡管有些類別的樣本量小，但是并不能忽略其重要性，如P2P類型的網(wǎng)絡(luò)流量數(shù)據(jù)對(duì)于合理分配網(wǎng)絡(luò)寬帶具有指導(dǎo)意義；而ATTACK類型的網(wǎng)絡(luò)流量屬于網(wǎng)絡(luò)攻擊，準(zhǔn)確地識(shí)別出此類型的流量也是十分重要的。所以為了最大可能地減弱各類數(shù)據(jù)不均衡問題的影響，需要在保證分類準(zhǔn)確的基礎(chǔ)上，提高小類的召回率。

在網(wǎng)絡(luò)流量分類問題中，每個(gè)樣本都具有248個(gè)特征，特征屬性繁多且許多特征之間存在強(qiáng)相關(guān)性，這增加了網(wǎng)絡(luò)流量分類問題中建模的復(fù)雜度，并且會(huì)降低分類的準(zhǔn)確率。因此需要在保證其分類準(zhǔn)確性的前提下對(duì)網(wǎng)絡(luò)流量進(jìn)行特征選擇，剔除一些具有冗余性和相關(guān)性極小的特征，以提高各個(gè)類別的召回率。

1 相關(guān)工作

相關(guān)領(lǐng)域的各國學(xué)者針對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)分類問題進(jìn)行了分析研究，近些年來對(duì)于網(wǎng)絡(luò)流量分類的研究中基于統(tǒng)計(jì)方法和機(jī)器學(xué)習(xí)的方法成為熱點(diǎn)。Lei等［3］利用統(tǒng)計(jì)的方法計(jì)算出各個(gè)特征的卡方值并選擇前k個(gè)，之后利用遺傳算法和C4.5決策樹對(duì)所選出的前k個(gè)特征再進(jìn)行選擇；褚慧琳等［4］提出了過濾型和封裝型相結(jié)合的特征選擇算法；孫興斌等［5-6］先是提出了基于統(tǒng)計(jì)頻率的特征選擇方法，根據(jù)樣本的頻率計(jì)算特征選擇系數(shù)，選擇特征與類別相關(guān)性較強(qiáng)的特征，接著又提出基于相對(duì)不確定性和對(duì)稱不確定性的Hybrid型特征選擇方法，利用信息熵理論對(duì)特征進(jìn)行選擇；劉紀(jì)偉等［7］提出基于統(tǒng)計(jì)排序的網(wǎng)絡(luò)流量特征方法，基于統(tǒng)計(jì)方法定義特征選擇系數(shù)和特征影響系數(shù)對(duì)特征進(jìn)行二次選擇。

本文針對(duì)網(wǎng)絡(luò)流量不均衡問題提出一種基于卡方方法及對(duì)稱不確性的特征選擇方法（Chi-square method and symmetric uncertain network traffic feature selection，CHI-SU），CHI-SU方法首先計(jì)算出所有特征和各個(gè)類別之間的卡方值，接著引入信息熵對(duì)所計(jì)算得到卡方值進(jìn)行加權(quán)排序，選擇出候選特征子集后再進(jìn)行最優(yōu)特征子集的搜索。最終通過所構(gòu)造的特征集利用C4.5決策樹對(duì)網(wǎng)絡(luò)流量進(jìn)行分類，在分類準(zhǔn)確率較高的情況下，可以提高各個(gè)類別的召回率。

2 基于卡方方法及對(duì)稱不確定性的特征選擇方法

2.1 卡方統(tǒng)計(jì)選擇方法

卡方統(tǒng)計(jì)量可以衡量特征t與類別c的相關(guān)程度，假設(shè)t（共p個(gè)）和c（共q個(gè)）之間符合具有一階自由度的卡方分布，則特征t對(duì)于類別c的χ2值的計(jì)算公式為：

其中，N：總樣本的個(gè)數(shù)；Ni?j：有特征ti且屬于類cj的樣本個(gè)數(shù)；：有特征ti但不屬于類cj的樣本個(gè)數(shù)；：沒有特征ti但是屬于類cj的樣本個(gè)數(shù)；：沒有特征ti也不屬于類cj的樣本個(gè)數(shù)；Nj：屬于類cj的樣本個(gè)數(shù)；Njˉ：不屬于類cj的樣本數(shù)。

從（1）式可以得到，特征ti與類別cj相關(guān)性大時(shí)，χ2值也會(huì)較大，計(jì)算所有特征ti與所有類別的χ2值，可以計(jì)算得到χ2矩陣，記為K，則K為：

QIU Y.F等［8］已經(jīng)證明，用卡方方法對(duì)特征進(jìn)行選擇效果顯著，但是從（1）式可看出所計(jì)算的χ2值僅體現(xiàn)在特征與類之間的相關(guān)性，χ2值較大時(shí)表示此特征含有較多類別的信息，反之亦然，這種方法在處理各類別樣本數(shù)目相當(dāng)時(shí)具有良好的效果，但是對(duì)于各類數(shù)據(jù)不均衡時(shí)卡方方法具有一些偏差。所以對(duì)于處理不均衡的數(shù)據(jù)集，以往的卡方特征選擇方法存在著不足之處，為了解決這一問題，綜合考慮特征在每個(gè)類別中的具體分布，對(duì)各類別數(shù)據(jù)不均衡和特征選擇問題進(jìn)行處理，在卡方統(tǒng)計(jì)方法上融合信息熵［9］，計(jì)算加權(quán)的χ2統(tǒng)計(jì)量，可以較好地表示出特征對(duì)類的區(qū)分能力，更好地解決不均衡數(shù)據(jù)集下特征選擇問題。

2.2 對(duì)稱不確定性

對(duì)特征ti與類別cj計(jì)算出的卡方值進(jìn)行加權(quán)，加權(quán)后的卡方統(tǒng)計(jì)量記為SUχ2(ti,cj)，加權(quán)后的卡方統(tǒng)計(jì)量考慮了特征與類別之間的相關(guān)性又衡量在數(shù)據(jù)集不均衡的情況下特征對(duì)不同類別的區(qū)分能力，利用對(duì)稱不確定性來衡量某個(gè)特征對(duì)總體類別C的區(qū)分能力［10］，對(duì)稱不確定性的定義為：

其中：

則：

p(cj|ti,k)：cj類在特征ti離散化后的第k個(gè)取值條件下出現(xiàn)的概率；

Nti：特征ti離散化后的取值個(gè)數(shù)；

p(ti,k)：特征ti離散化后第k個(gè)取值出現(xiàn)的概率；

H(ti)：特征ti的信息熵；

H(C|ti)為總體類別C在特征ti下的條件熵；

IG(C|ti)：總體類別C在特征ti下的信息增益。

對(duì)稱不確定性可以用來衡量特征ti和類別C之間提供的信息量，為0表示特征ti和類別C相互獨(dú)立，如果，則表示特征ti能更容易地區(qū)分不同類別的樣本。對(duì)于不均衡的數(shù)據(jù)集，首先根據(jù)卡方統(tǒng)計(jì)量可以看出一些特征含有較多的區(qū)分信息，再根據(jù)其信息熵、信息增益以及對(duì)稱不確定性，對(duì)各個(gè)類別的權(quán)重加以調(diào)整，使得最終分類時(shí)提高其整體和小類別的召回率，對(duì)χ2統(tǒng)計(jì)矩陣進(jìn)行加權(quán)得到矩陣K′：

2.3 特征選擇方法（CHI-SU方法）

基于卡方特征選擇方法首先根據(jù)公式（3）計(jì)算出的加權(quán)卡方矩陣（4）選擇與每個(gè)類相關(guān)性較高的k個(gè)特征，去掉重復(fù)的特征后再選擇，構(gòu)成候選特征子集；再從已經(jīng)構(gòu)成的候選特征集中依次選擇特征，利用C4.5決策樹對(duì)數(shù)據(jù)集進(jìn)行分類，同時(shí)記錄結(jié)果，根據(jù)分類結(jié)果確定最優(yōu)特征子集。步驟如下：

步驟1.對(duì)于每個(gè)類cj，由（1）式計(jì)算出χ2(ti,cj)；對(duì)于每個(gè)特征ti，由（2）式計(jì)算得到SU(ti,C)；根據(jù)公式（3）計(jì)算 SUχ2(ti,cj) ，得到加權(quán)χ2矩陣K′，按照矩陣（4）的列即對(duì)于每個(gè)類cj的每個(gè)特征ti排序，選擇前l(fā)個(gè)加權(quán)χ2值大的特征。

步驟2.對(duì)于每個(gè)特征集合Tj，去除Tj中屬于T1,T2,…,Tj-1的特征，將集合中所有特征按照其SU值降序排列，保留前k個(gè)特征，過濾其余特征，得到q個(gè)特征集合Tj(j=1,2,…,q)。

步驟3.搜索最優(yōu)特征子集，初始化特征集合T′為空集，對(duì)于每個(gè)特征集合Tj，從中選擇一個(gè)特征放入T′集合中。

步驟4.對(duì)數(shù)據(jù)集訓(xùn)練集S、測(cè)試集D進(jìn)行預(yù)處理，保留T′集合中的特征，得到處理后的訓(xùn)練集S′和測(cè)試集D′，用C4.5決策樹分類器對(duì)S′進(jìn)行訓(xùn)練，并利用D′進(jìn)行測(cè)試，記錄分類效果；

步驟5.重復(fù)步驟3，直到完全搜索整個(gè)特征空間，選擇分類效果最好的特征集合輸出。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集采用的為Moore數(shù)據(jù)集［3］，該數(shù)據(jù)集共包含了10個(gè)數(shù)據(jù)集，分為了12個(gè)類型的網(wǎng)絡(luò)流量數(shù)據(jù)，每條數(shù)據(jù)均有249個(gè)流特征，其中最后一項(xiàng)為類別特征。但是由于GAMES、INTERACTIVE、DATABASE和MUTIMEDIA這四個(gè)類型的網(wǎng)絡(luò)流量數(shù)據(jù)并不是在每個(gè)子數(shù)據(jù)集中都存在，故對(duì)過濾掉四類數(shù)據(jù)集進(jìn)行分類預(yù)測(cè)，過濾之后的樣本數(shù)及比例如表1所示。

表1 Moore數(shù)據(jù)集詳細(xì)信息

3.2 實(shí)驗(yàn)工具與實(shí)驗(yàn)流程

實(shí)驗(yàn)使用的主要實(shí)驗(yàn)工具為Matlab R2012b和Weka 3.8，實(shí)驗(yàn)平臺(tái)運(yùn)行Windows 8操作系統(tǒng)，CPU為Iterl Core i5-4200 1.6GHz，內(nèi)存大小為4.00GB。

實(shí)驗(yàn)的算法流程圖如圖1所示。

圖1 實(shí)驗(yàn)的基本流程圖

表2 三種方法所選的特征符號(hào)及物理意義

孫興斌等人在文獻(xiàn)［6］中提出了FFS方法即基于統(tǒng)計(jì)頻率的網(wǎng)絡(luò)流量特征選擇方法，在文獻(xiàn)［7］中提出了FSMID方法即面向多類不均衡網(wǎng)絡(luò)流量的特征選擇方法，這兩種方法都是討論網(wǎng)絡(luò)流量數(shù)據(jù)不均衡性，且使用的實(shí)驗(yàn)數(shù)據(jù)集均為Moore數(shù)據(jù)集，評(píng)價(jià)指標(biāo)使用的均為準(zhǔn)確率以及召回率，故將CHI-SU方法和FFS方法、FSMID方法進(jìn)行對(duì)比分析，利用三種方法所選擇的流量特征的序號(hào)［11］如表2所示。

3.3 評(píng)價(jià)指標(biāo)

傳統(tǒng)的分類器評(píng)價(jià)標(biāo)準(zhǔn)是分類的精確率，可增加召回率這一指標(biāo)來共同衡量所選特征集合的優(yōu)劣。其中精確率和召回率可由二分類混合矩陣得出，二分類混合矩陣如表3所示。

表3 二分類混合矩陣

根據(jù)表3定義正類的Precision（精確率）和Recal（l召回率）：

3.4 實(shí)驗(yàn)結(jié)果

由表1可以看到，ATTACK類別的網(wǎng)絡(luò)流量數(shù)據(jù)占比為0.442%，數(shù)量相對(duì)較少，但是其在識(shí)別網(wǎng)絡(luò)攻擊時(shí)的重要性卻遠(yuǎn)超于其他類別。故對(duì)網(wǎng)絡(luò)流量進(jìn)行分類時(shí)，會(huì)對(duì)大類別如WWW類別的網(wǎng)絡(luò)流量數(shù)據(jù)更有利，而小類別的數(shù)據(jù)極易被誤分。

利用三種不同的方法得到的特征對(duì)少數(shù)類ATTACK類型的流量數(shù)據(jù)分類后的精確率如表4所示。

表5是通過三種不同的方法得到的特征對(duì)少數(shù)類ATTACK類型的流量數(shù)據(jù)分類后的召回率，可以得到在精確率都在90%以上的情況下，CHI-SU方法明顯也提高了小類ATTACK的召回率。

表4 三種方法在每個(gè)數(shù)據(jù)集中ATTACK類的精確率

表5 三種方法在每個(gè)數(shù)據(jù)集中ATTACK類的召回率

4 結(jié)語

對(duì)網(wǎng)絡(luò)流量進(jìn)行分類時(shí)，數(shù)據(jù)不均衡問題時(shí)常出現(xiàn)，故對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)不均衡問題的研究是一項(xiàng)熱門的問題，提出的基于卡方方法及對(duì)稱不確定性的網(wǎng)絡(luò)流量特征選擇方法對(duì)比于其他方法，準(zhǔn)確率并沒有明顯的提高，但是在小類別召回率有明顯提高。如何簡(jiǎn)單迅速地選擇出合適的特征集合，在保證整體分類準(zhǔn)確率以及各類別準(zhǔn)確率的同時(shí)，大幅度地提高其召回率及其他的一些指標(biāo)，是未來研究的一個(gè)方向。