基于特征加權(quán)的樸素貝葉斯流量分類方法研究①

張澤鑫 李 俊 常向青

(*中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心 北京 100190) (**中國科學(xué)院大學(xué) 北京 100049)

?

基于特征加權(quán)的樸素貝葉斯流量分類方法研究①

張澤鑫②***李 俊*常向青*

(*中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心 北京 100190) (**中國科學(xué)院大學(xué) 北京 100049)

研究了被廣泛應(yīng)用于互聯(lián)網(wǎng)流量分類的樸素貝葉斯分類方法的性能特點，針對此方法在給定類別下給出的所有流量特征同等重要并且是獨立的假設(shè)在現(xiàn)實中難以滿足，致使分類準(zhǔn)確率不高的問題，提出一種基于特征加權(quán)的樸素貝葉斯流量分類算法。該算法基于NetFlow記錄的特征信息，采用特征選擇算法ReliefF和相關(guān)系數(shù)方法計算每個特征的權(quán)重值，然后將網(wǎng)絡(luò)流量分配至后驗概率最大的應(yīng)用類別中。實驗結(jié)果表明，這種基于特征加權(quán)的樸素貝葉斯算法具有超過94%的分類準(zhǔn)確率，并且維持了樸素貝葉斯方法簡單高效、分類穩(wěn)定的特性，可以滿足當(dāng)前高帶寬網(wǎng)絡(luò)流量分類的需求。

流量分類(TC), ReliefF, 相關(guān)系數(shù), 特征加權(quán)(AW), 樸素貝葉斯(NB), NetFlow

0 引 言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，越來越多的新型網(wǎng)絡(luò)應(yīng)用不斷興起，網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)組成也越來越復(fù)雜。音頻、視頻等實時應(yīng)用的興起，更是從根本上改變了人們對網(wǎng)絡(luò)的使用方式，網(wǎng)絡(luò)復(fù)雜性上升的同時，網(wǎng)絡(luò)的異構(gòu)性也愈來愈強(qiáng)，各種新的應(yīng)用和未知協(xié)議使網(wǎng)絡(luò)日益復(fù)雜、多樣化和難以管理。進(jìn)行網(wǎng)絡(luò)管理離不開互聯(lián)網(wǎng)流量分類(traffic classification, TC)，互聯(lián)網(wǎng)流量分類是認(rèn)識、管理和優(yōu)化各種網(wǎng)絡(luò)資源的重要依據(jù)。網(wǎng)絡(luò)服務(wù)提供商(ISP)通過對網(wǎng)絡(luò)流進(jìn)行分類，獲悉各類網(wǎng)絡(luò)應(yīng)用所占的比例，預(yù)測網(wǎng)絡(luò)業(yè)務(wù)的發(fā)展趨勢，對不同的網(wǎng)絡(luò)業(yè)務(wù)實行差異化收費(fèi)標(biāo)準(zhǔn)。流量分類在網(wǎng)絡(luò)安全性檢測方面也發(fā)揮著巨大的作用，可以實現(xiàn)更精確的異常檢測，入侵檢測等。因此，開展互聯(lián)網(wǎng)流量分類研究具有重要實際意義和應(yīng)用價值。

由于很多新的網(wǎng)絡(luò)應(yīng)用采用動態(tài)端口、數(shù)據(jù)載荷字段加密，導(dǎo)致傳統(tǒng)的基于端口和基于有效載荷分析的流量分類方法變得越來越受限制，分類準(zhǔn)確率下降。因此，基于流量行為特征，采用機(jī)器學(xué)習(xí)的方法處理流量分類問題逐漸成為國內(nèi)外學(xué)者研究的熱點。樸素貝葉斯(Naive Bayes, NB)分類方法因其實現(xiàn)簡單、處理高效的特征被很多學(xué)者用于流量分類領(lǐng)域[1，2]。然而，樸素貝葉斯(NB)方法在估計類條件概率時，假設(shè)流量特征之間是同等重要且條件獨立的，該假設(shè)在實際情況中很難滿足，流量特征之間往往存在著相關(guān)性。解決該問題的一個方法是特征過濾，從流量特征集中刪除冗余的特征，使用過濾后的特征子集進(jìn)行分類模型訓(xùn)練。該方法提高了樸素貝葉斯進(jìn)行流量分類的準(zhǔn)確率，但是，并沒有考慮不同流量特征對分類的重要性不同。因此，本文提出了一種特征加權(quán)(attribute weighting, AW)的樸素貝葉斯流量分類方法，該方法賦予每個特征一個權(quán)重，越重要的特征權(quán)重值越大，然后將流量分至后驗概率最大的應(yīng)用類別中。特征加權(quán)是特征選擇的一種擴(kuò)展方法，賦予冗余度高的特征較小的權(quán)重，賦予對網(wǎng)絡(luò)應(yīng)用區(qū)分度大的特征較高的權(quán)重，既能解決流量特征之間存在冗余的問題，也考慮了不同流量特征對分類重要性不同。

1 相關(guān)研究

早期，網(wǎng)絡(luò)應(yīng)用通過周知的端口來進(jìn)行分類，根據(jù)互聯(lián)網(wǎng)編號分配機(jī)構(gòu)(IANA)預(yù)定義和分配的端口映射表[3]，每個端口號對應(yīng)一個應(yīng)用，比如眾所周知的web應(yīng)用的端口號是80。然而，隨著網(wǎng)絡(luò)應(yīng)用的層出不窮，大量的隨機(jī)端口被用于數(shù)據(jù)通信，有些協(xié)議甚至封裝后通過周知的端口進(jìn)行通信。Moore和Papagiannaki[4]通過實驗研究發(fā)現(xiàn)使用IANA列表進(jìn)行基于端口號的流量識別，準(zhǔn)確率不超過70%?；诙丝诘膽?yīng)用識別方法變得越來越受限[5-8]。

為了提高分類的準(zhǔn)確率，很多學(xué)者開始關(guān)注網(wǎng)絡(luò)流量的負(fù)載特征。劍橋大學(xué)的Moore等人[4]、AT&T實驗室的Sen等[9]在他們的論文中都提出了采用基于有效載荷特征匹配的方法來對互聯(lián)網(wǎng)的業(yè)務(wù)流量進(jìn)行分類。基于載荷的流量分類方法準(zhǔn)確度非常高，但是需要檢索每個數(shù)據(jù)包中的Payload字段，需要的計算資源非常大，并且有效載荷的分析侵犯了用戶的隱私和安全性，其發(fā)展受到了很大的阻力。

隨著研究的不斷深入，基于行為特征的流量分類方法逐漸成為國內(nèi)外研究的熱點。該方法從不同的觀測角度發(fā)現(xiàn)網(wǎng)絡(luò)應(yīng)用的不同行為特征，例如包大小、包時間間隔、字節(jié)數(shù)、持續(xù)時間等作為流量特征，應(yīng)用機(jī)器學(xué)習(xí)方法對其建立相應(yīng)的模型，然后應(yīng)用于分類?；诹髁康慕y(tǒng)計行為特征，各研究機(jī)構(gòu)提出了基于機(jī)器學(xué)習(xí)的流量分類方法[10]，通過統(tǒng)計流持續(xù)時間、分組到達(dá)間隔等流統(tǒng)計特性，采用有監(jiān)督或者無監(jiān)督的機(jī)器學(xué)習(xí)方法實現(xiàn)業(yè)務(wù)分類。McGregor等[11]采用基于EM(expectation-maximization)算法無監(jiān)督的學(xué)習(xí)方法對基于連接層統(tǒng)計特征的“流”進(jìn)行分類。文獻(xiàn)[12]提出將P個特征屬性轉(zhuǎn)換為P維向量，通過定義距離函數(shù)，采用聚類的方法對網(wǎng)絡(luò)流進(jìn)行分類。無監(jiān)督的聚類方法分類精度不高，在類別數(shù)比較多的情況下，分類復(fù)雜度較大。同時有監(jiān)督的機(jī)器學(xué)習(xí)方法也被用于流量分類中，Moore等[1]通過傅里葉變換構(gòu)建了248個流特征，并采用FCBF(fast correlation-based filter)進(jìn)行特征選擇，最后采用樸素貝葉斯方法來區(qū)分各應(yīng)用。該方法的流量特征過多，增加了時間和空間復(fù)雜度，無法應(yīng)用于流量的在線識別。樸素貝葉斯分類模型具有簡單高效的特點，因此被很多研究者應(yīng)用于流量分類中。文獻(xiàn)[13]采用多種特征選擇方法，結(jié)合不同的訓(xùn)練數(shù)據(jù)集預(yù)處理方法，評估樸素貝葉斯分類器在檢測網(wǎng)絡(luò)異常時的性能差異。文獻(xiàn)[14]提出了一種新的特征選擇方法對流量特征過濾，該方法能有效緩解多類不平衡的問題，最后采用樸素貝葉斯分類器對流量進(jìn)行分類。Antonio等[15]為了改進(jìn)樸素貝葉斯分類器的分類準(zhǔn)確率，采用主成分分析法和關(guān)聯(lián)特征法對網(wǎng)絡(luò)流量特征進(jìn)行了選擇，結(jié)果顯示這兩種特征選擇方法都提高了樸素貝葉斯的分類準(zhǔn)確率。文獻(xiàn)[16，17]也分別使用樸素貝葉斯分類算法對網(wǎng)絡(luò)流量進(jìn)行分類。

國內(nèi)方面，徐鵬等人[18]采用C4.5決策樹方法對流量進(jìn)行分類，實驗證明決策樹分類方法在處理動態(tài)變化的樣本和大規(guī)模流量分類時具有較好的性能，然而采用的流量屬性還無法實時獲取，不適合用于網(wǎng)絡(luò)流在線識別。陳亮等人[19]首先采用簡單相關(guān)系數(shù)方法進(jìn)行流量特征選擇，然后基于Bayes判別法進(jìn)行流量分類。該方法雖然整體的分類準(zhǔn)確率較高，但是有些應(yīng)用的分類結(jié)果卻不佳，例如P2P、ATTACK等。

2 特征加權(quán)的樸素貝葉斯流量分類方法

2.1 特征加權(quán)的樸素貝葉斯流量分類算法

樸素貝葉斯分類器具有穩(wěn)定的分類效率，對缺失數(shù)據(jù)也不敏感，并且算法簡單，因此，被廣泛地應(yīng)用在分類領(lǐng)域。樸素貝葉斯分類器利用貝葉斯定理計算待分類實例的最大后驗概率，在估計類條件概率時假設(shè)屬性之間條件獨立，形式化描述為

(1)

其中A代表屬性集A={A1,A2,…,Ad}，包含d個屬性。

在條件獨立假設(shè)下，只需對給定的Y，計算每一個Ai的條件概率。假設(shè)有N條網(wǎng)絡(luò)流X={X1,X2,…,Xn}，每條網(wǎng)絡(luò)流Xi由d個屬性值描述{A1,A2,…,Ad}，有m個網(wǎng)絡(luò)應(yīng)用類別，Y={Y1,Y2,…,Ym}。對于網(wǎng)絡(luò)流Xi，屬于類別Yj的概率為：

(2)

其中，先驗概率P(Yj)代表網(wǎng)絡(luò)應(yīng)用類別Yj在整個網(wǎng)絡(luò)流中占有的比例，P(Xi|Yj)為類條件概率，表示在應(yīng)用類別為Yj時，Xi出現(xiàn)的概率。樸素貝葉斯分類器的目標(biāo)是找出使得P(Xi|Yj)P(Yj)(j=1,2…，m)最大的類Yj，此時，流量Xi對應(yīng)的類別即為Yj。根據(jù)式(1)、(2)，樸素貝葉斯分類器的后驗概率計算公式為

(3)

樸素貝葉斯分類器對網(wǎng)絡(luò)流量進(jìn)行分類時，假定每條流的特征是相互獨立的，并且每個特征對分類的貢獻(xiàn)度都是一樣的。然而，在真實的網(wǎng)絡(luò)環(huán)境中，這些假設(shè)條件都是難以滿足的，結(jié)果導(dǎo)致分類準(zhǔn)確率降低。針對這個問題，文獻(xiàn)[1]中采用FCBF方法進(jìn)行流量特征選擇，選擇一個與類別相關(guān)性高，特征之間冗余度低的特征子集進(jìn)行分類模型訓(xùn)練，削弱了流量特征之間的相關(guān)性，提高了分類的準(zhǔn)確率。特征加權(quán)是另一種可以保留或刪除特征的方法，特征越重要，賦予的權(quán)值越大，而不太重要的特征賦予較小的權(quán)值。特征加權(quán)是特征選擇的普適化方法，特征選擇是特征加權(quán)方法的一個特例，權(quán)值等于0或1。特征加權(quán)的樸素貝葉斯分類器后驗概率計算公式為

(4)

其中ωk∈R+，代表特征的重要程度。

2.2 基于ReliefF和相關(guān)系數(shù)的流量特征加權(quán)算法

特征加權(quán)的樸素貝葉斯流量分類方法的關(guān)鍵是特征權(quán)值的計算，給每個流量特征分配合適的權(quán)重不僅能夠區(qū)分特征之間的預(yù)測能力，也能降低違背特征獨立性假設(shè)所帶來的影響，提高樸素貝葉斯分類器的分類準(zhǔn)確率。因此，本文從兩個方面考慮流量特征權(quán)重的計算，首先，認(rèn)為與類別相關(guān)性高的特征具有較高的權(quán)重，采用ReliefF[20]方法計算每個特征的權(quán)重值；其次，認(rèn)為與其它特征冗余度高的特征具有較低的權(quán)重，采用相關(guān)系數(shù)方法修正每個特征的權(quán)重值。

ReliefF是由Kononenko提出的一種多類別特征選擇算法，其基本思想是給特征集中的每個特征賦予一個權(quán)重值，賦予和類別相關(guān)性高的特征較高的權(quán)重，最后根據(jù)這些權(quán)重值進(jìn)行特征子集選擇。本文則根據(jù)這些權(quán)重值對流量特征進(jìn)行加權(quán)，權(quán)重向量為ω=(ω1,ω2,…,ωd)，算法見表1。Class(Xi)表示樣本Xi所屬的類別，函數(shù)diff(A,I1,I2)計算樣本I1和樣本I2在特征A上的距離，P(Y)表示網(wǎng)絡(luò)應(yīng)用Y的先驗概率。

表1 基于ReliefF的流量特征權(quán)重計算算法

ReliefF算法沒有限定特征權(quán)值的取值范圍，有可能為負(fù)值，所以，為了避免發(fā)生這種情況，根據(jù)Han等人[21]提出的min-max方法對權(quán)值進(jìn)行標(biāo)準(zhǔn)化操作。假設(shè)流量特征的權(quán)值向量為[ω1，ω2，…，ωk]，采用公式

+new_minω

(5)

ReliefF算法僅考慮了特征與類別之間的相關(guān)性程度，沒有考慮特征之間的相關(guān)性，本文采用相關(guān)系數(shù)來度量特征之間的相關(guān)性程度，如下式所示：

(6)

3 實 驗

為了驗證特征加權(quán)的樸素貝葉斯流量分類算法的有效性，設(shè)置了兩組對比實驗。第一組采用標(biāo)準(zhǔn)的樸素貝葉斯分類方法進(jìn)行流量分類；第二組首先采用文獻(xiàn)[22]中提出的FCBF方法對流量特征過濾，然后使用過濾的訓(xùn)練數(shù)據(jù)集運(yùn)行樸素貝葉斯分類器，構(gòu)造分類模型。

3.1 實驗數(shù)據(jù)

實驗的數(shù)據(jù)集來自中國科技網(wǎng)(China Science and Technology Network，CSTNET)。為了驗證不同時間段算法的性能，采集了2014年12月16日上午10:00～11:00，下午14:00～15:00，晚上19:00～20:00之間經(jīng)過該出口的所有Netflow網(wǎng)絡(luò)流量，分別為CSTNET_1，CSTNET_2，CSTNET_3。經(jīng)分析，TCP流量仍為中國科技網(wǎng)的主要流量，所以本文僅對完整的TCP流進(jìn)行分類。

為了避免用每種應(yīng)用的訓(xùn)練樣本過少而影響分類準(zhǔn)確率，抽樣時使得每種應(yīng)用的流數(shù)基本保持一致，即采用均勻無放回抽樣方法，從每個數(shù)據(jù)集中抽取約3萬條數(shù)據(jù)，每種應(yīng)用約3000條流數(shù)據(jù)作為樣本集。經(jīng)分析，表2中的10種應(yīng)用為科技網(wǎng)TCP流量中的主要部分，所以本文選取這10種應(yīng)用進(jìn)行分類。每組數(shù)據(jù)集輪流作為訓(xùn)練集對分類器進(jìn)行訓(xùn)練，剩余兩組作為測試集。

表2 數(shù)據(jù)集

文獻(xiàn)[1]采用傅里葉變換得到249項網(wǎng)絡(luò)流特征，在這些特征中存在著大量的冗余特征，對分類器進(jìn)行訓(xùn)練時，不但增加了分類的時間復(fù)雜度，也降低了分類的準(zhǔn)確率，并且不適合用于網(wǎng)絡(luò)流的在線分類。為了降低分類系統(tǒng)采集報文、計算流量特征的開銷，本文采用NetFlow的統(tǒng)計特征作為網(wǎng)絡(luò)流的屬性，見表3。對于不同的網(wǎng)絡(luò)應(yīng)用，這些屬性特征通常表現(xiàn)出較大的差異性，因此，可以利用NetFlow的流記錄信息對網(wǎng)絡(luò)應(yīng)用進(jìn)行識別。

表3 網(wǎng)絡(luò)流屬性集合

3.2 評估指標(biāo)

評價一個網(wǎng)絡(luò)流量分類器的好壞需要在一定指標(biāo)下測試其分類結(jié)果，然后通過測試結(jié)果得出結(jié)論。分類器首先通過訓(xùn)練集進(jìn)行模型的學(xué)習(xí)，擬合訓(xùn)練集數(shù)據(jù)中類標(biāo)號和屬性集之間的聯(lián)系，建立分類模型。隨后將該模型應(yīng)用于測試集數(shù)據(jù)，分類模型的性能根據(jù)測試集數(shù)據(jù)的運(yùn)行結(jié)果進(jìn)行評估，運(yùn)行結(jié)果計數(shù)存放在混淆矩陣中，如表4。表中每項fij表示實際類標(biāo)號為i，但被預(yù)測為類j的記錄數(shù)。

表4 多類問題的混淆矩陣

根據(jù)混淆矩陣，分類器性能評價指標(biāo)計算公式如下：

3.3 樸素貝葉斯網(wǎng)絡(luò)流量分類

本節(jié)僅采用標(biāo)準(zhǔn)的樸素貝葉斯方法對網(wǎng)絡(luò)流量進(jìn)行分類，分別選取數(shù)據(jù)集中的一組數(shù)據(jù)作為訓(xùn)練集，另外兩組數(shù)據(jù)作為測試集，每組實驗重復(fù)10次，取每組實驗的平均值作為分類結(jié)果。如表5所示，三組實驗的平均分類準(zhǔn)確率分別為80.7%，81.0%，81.2%。從表5可以看出，樸素貝葉斯分類器的分類結(jié)果較差，整體的分類準(zhǔn)確率較低，主要是由于樸素貝葉斯分類器在估計類條件概率時假設(shè)流量特征之間是條件獨立的，流量特征之間的相關(guān)性違背了條件獨立性假設(shè)，降低了樸素貝葉斯分類器的分類準(zhǔn)確率。

表5 基于樸素貝葉斯流量分類方法的整體分類準(zhǔn)確率

3.4 基于FCBF特征選擇的樸素貝葉斯(FCBF_NB)網(wǎng)絡(luò)流量分類

由于流量特征之間存在冗余，導(dǎo)致樸素貝葉斯分類器的分類準(zhǔn)確率降低，所以采用文獻(xiàn)[22]提出的FCBF方法對流量特征進(jìn)行選擇，選擇與類別相關(guān)性高且特征之間冗余度低的流量特征用于構(gòu)建樸素貝葉斯分類器模型。選出的特征集為M={dest_port, packet_size, duration, IAT, pps}，然后在完成過濾的訓(xùn)練數(shù)據(jù)集上運(yùn)行樸素貝葉斯分類器，構(gòu)建分類模型，并使用數(shù)據(jù)集中的另外兩組數(shù)據(jù)測試模型。每組實驗重復(fù)10次，取每組實驗的平均值為分類結(jié)果，如表6所示。采用FCBF方法對流量特征過濾之后，每組實驗的整體分類準(zhǔn)確率較特征過濾之前有了一定的提高，每組實驗分別增長了3.6%，3.7%，3.2%，但是整體的分類準(zhǔn)確率仍然較低。主要是由于采用FCBF方法選出的特征子集，雖然使得特征之間的冗余度降低了，但是并不能完全消除，并且認(rèn)為每個特征對分類是同等重要的，從而導(dǎo)致較低的分類準(zhǔn)確率。

表6 基于特征選擇的樸素貝葉斯流量分類方法 整體分類準(zhǔn)確率

3.5 特征加權(quán)的樸素貝葉斯網(wǎng)絡(luò)流量分類

考慮到不同的流量特征對分類的重要程度不同，越重要的特征賦予的權(quán)值越大，不太重要的特征賦予較小的權(quán)值。首先通過ReliefF和相關(guān)系數(shù)方法對流量特征計算權(quán)值。然后在訓(xùn)練數(shù)據(jù)集上運(yùn)行特征加權(quán)的樸素貝葉斯分類器，構(gòu)建分類模型，并使用數(shù)據(jù)集中的另外兩組數(shù)據(jù)測試模型。每組實驗重復(fù)10次，取每組實驗的平均值為分類結(jié)果，如表7 所示。較上述兩種方法，特征加權(quán)(AW)的樸素貝葉斯(NB)流量分類(TC)算法(簡稱AWNBTC算法)的整體分類準(zhǔn)確率有了顯著提高，每組實驗結(jié)果較樸素貝葉斯分類方法分別增長了13.8%，13.2%，13.0%，較基于FCBT特征選擇的樸素貝葉斯(FCBF_NB)方法分別增長了10.2%，9.5%，9.8%。

表7 基于特征加權(quán)的樸素貝葉斯流量分類方法 整體分類準(zhǔn)確率

為進(jìn)一步分析AWNBTC算法的分類準(zhǔn)確性，通過圖1和圖2描述了每種網(wǎng)絡(luò)應(yīng)用的分類精度和召回率。從圖中看出，較樸素貝葉斯(NB)方法和FCBF_NB方法，AWNBTC算法每種應(yīng)用的分類精度

圖1 網(wǎng)絡(luò)應(yīng)用類精度

圖2 網(wǎng)絡(luò)應(yīng)用類召回率

和召回率都提高了，除了Http、Https和SMTP，其他應(yīng)用的分類精度和召回率超過了96%，MSN和BT的分類精度和召回率達(dá)到了99%。SMTP的分類精度改善得最多，較NB算法和FCBF_NB算法分別增長了18.7%和16.6%，Datatransfer、Jabber、IMAP和BT應(yīng)用的分類精度較NB算法和FCBF_NB算法也平均提高了約14.9%和12.6%。關(guān)于應(yīng)用的召回率，Https和SSH應(yīng)用增長得最多，Https分別提高了20.8%和15.2%，SSH則分別提高了26.1%和14.3%。其他應(yīng)用的召回率也有顯著增長，Http、Datatransfer、Jabber和IMAP較NB算法和FCBF_NB算法平均提高了約13.2%和8.2%。由此可見，特征加權(quán)的樸素貝葉斯分類方法較NB和FCBF_NB方法，不僅具有較高的整體分類準(zhǔn)確率，而且每類應(yīng)用的分類準(zhǔn)確性也很高。

4 算法評估

4.1 時效性

樸素貝葉斯分類器的實現(xiàn)主要包括模型訓(xùn)練和流量分類兩部分，其中模型訓(xùn)練部分由流量特征離散化和樸素貝葉斯模型構(gòu)建組成。首先采用基于等寬的離散化方法將各個流量特征的值域劃分成具有相同寬度的區(qū)間，并用離散化后所在區(qū)間的標(biāo)稱值代替原來的值，其算法時間復(fù)雜度為O(N)；模型構(gòu)造主要為計算每個分類屬性的類條件概率，時間復(fù)雜度為O(N)，因此整個模型訓(xùn)練的時間復(fù)雜度為O(N)，其中N為整個訓(xùn)練樣本規(guī)模。流量分類部分首先對一條流的流量特征進(jìn)行離散化，時間復(fù)雜度為O(1)。然后通過樸素貝葉斯概率公式對每個網(wǎng)絡(luò)應(yīng)用計算后驗概率，并找出最大的后驗概率，由于樣本特征屬性和協(xié)議類型是有限的，因此其時間復(fù)雜度也可以近似看成是常數(shù)O(1)。所以，樸素貝葉斯分類器處理每一條流的時間復(fù)雜度都是常數(shù)，對于n個樣本的分類處理，整個時間復(fù)雜度為O(N)。

特征加權(quán)的樸素貝葉斯分類器僅在計算后驗概率時為每個特征賦予一個權(quán)重，時間復(fù)雜度與樸素貝葉斯分類器一樣，處理單條流的時間復(fù)雜度為O(1)，n個樣本的分類處理時間復(fù)雜度也為O(N)。為了測試AWNBTC方法的準(zhǔn)確時間，使用三組數(shù)據(jù)分別對特征加權(quán)的樸素貝葉斯分類器進(jìn)行訓(xùn)練，得到分類模型，然后，使用另外兩組流量數(shù)據(jù)對分類模型進(jìn)行測試，每組實驗重復(fù)10次，得到的實驗結(jié)果如表8。從表中可以看出，AWNBTC方法可每秒約處理15000條網(wǎng)絡(luò)流，而中國科技網(wǎng)國際出口在一天當(dāng)中高峰時刻的流約為14000條/s，AWNBTC方法完全能夠滿足實時處理該出口的流量。

表8 AWNBTC方法的分類時間

4.2 時間穩(wěn)定性

當(dāng)前的網(wǎng)絡(luò)應(yīng)用可謂是百花齊放，層出不窮，時時刻刻都在發(fā)生著變化。為了測試分類器的時間穩(wěn)定性，即舊的分類模型是否適用于新數(shù)據(jù)的分類，使用三組原數(shù)據(jù)分別進(jìn)行模型訓(xùn)練，一個月后的流量數(shù)據(jù)(CSTNET_set4)進(jìn)行模型測試，每組實驗重復(fù)10次。實驗結(jié)果表明整體的平均分類準(zhǔn)確率為94.2%，保持穩(wěn)定。應(yīng)用的分類精度和召回率如表9所示，雖然每類應(yīng)用的分類精度和召回率都有些波動，但總體仍保持較高的分類準(zhǔn)確性。實驗結(jié)果表明，AWNBTC算法具有很強(qiáng)的動態(tài)適應(yīng)性，不需經(jīng)常更新樣本和對模型進(jìn)行重新訓(xùn)練，適合于流量的在線識別。

表9 AWNBTC算法時間穩(wěn)定性測試結(jié)果

5 結(jié) 論

實際網(wǎng)絡(luò)中流量特征無法滿足樸素貝葉斯分類方法的特征同等重要和條件獨立性假設(shè)，從而導(dǎo)致分類準(zhǔn)確率低，為此本文提出了一種特征加權(quán)的樸素貝葉斯流量分類算法。該算法有如下優(yōu)勢：(1)僅使用NetFlow記錄的統(tǒng)計特征便得到很高的分類準(zhǔn)確率，減少了基于數(shù)據(jù)報文計算流量特征的開銷，提高了分類速度，節(jié)約了存儲空間，更適合用于流量的在線識別。(2)具有樸素貝葉斯算法簡單高效的分類特點，又不依賴于樸素貝葉斯的條件獨立性假設(shè)，并且較樸素貝葉斯算法在整體的分類準(zhǔn)確率、每類應(yīng)用的分類精度和召回率上都有了很大的改進(jìn)。理論分析和實驗結(jié)果表明，本文算法具有超過94%的分類準(zhǔn)確率，并且能適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，可以滿足當(dāng)前高帶寬網(wǎng)絡(luò)流量分類準(zhǔn)確性、實時性和穩(wěn)定性的需求。

[1] Moore A W, Zuev D. Internet traffic classification using Bayesian analysis techniques.ACMSIGMETRICSPerformanceEvaluationReview,2005, 33(1):50-60

[2] Williams N,Zander S,Armitage G. A preliminaryperformance comparison of five machine learning algorithms forpractical IP traffic flowclassification.ACMSIGCOMMComputerCommunicationReview, 2006, 36(5):5-16

[3] Internet Assigned Numbers Authority.http://www.iana.org.

[4] Moore A W, Papagiannaki K. Toward the accurate identification of network applications. In: Proceedings of the 6th Passive and Active Measurement Workshop, Boston, USA, 2005. 41-54

[5] Zander S, Nguyen T, Armitage G. Automated trafficclassification and application identification using machine learning. In: Proceedings of the 30th IEEE Conference on Local Computer Networks, Sydney, Australia, 2005. 250-257

[6] Karagiannis T, Papagiannaki K, Faloutsos M. BLINC: multilevel traffic classification in the dark.ACMSIGCOMMComputerCommunicationReview, 2005, 35(4):229-240

[7] Tavallaee M, Lu W, Ghorbani A. Online classification ofnetwork flows. In: Proceedings of the 7th Communication Networks and Services Research Conference, Moncton, Canada, 2009. 78-85

[8] Crotti M, Dusi M, Gringoli F, et al. Trafficclassification through simple statistical fingerprinting.ACMSIGCOMMComputerCommunicationReview, 2007, 37(1):5-16

[9] Sen S, Spatscheck O, Wang D. Accurate, scalable in network identification of P2P traffic using application signatures. In: Proceedings of the 13th International Conference on World Wide Web, New York, USA, 2004. 512-521

[10] Nguyen T T T, Armitage G. A survey of techniques for Internet traffic classification using machine learning.IEEECommunicationsSurveysandTutorials, 2008, 10(4):56-76

[11] McGregor A, Hall M, Lorier P, et al. Flow clustering using machine learning techniques. In: Proceedings of the 5th Passive and Active Measurement Workshop,Antibes Juan-les-Pins, France, 2004. 205-214

[12] Bernaille L,Teixeira R, Akodkenou I, et al. Traffic classification on the fly.ACMSIGCOMMComputerCommunicationReview,2006, 36(2):23-26

[13] Katkar V D, Kulkarni S V. Experiments on detection of denial of service attacks using Naive Bayesian classifier. In: Proceedings of the 2013 IEEE International Conference on Green Computing, Communication and Conservation of Energy, Chennal, India, 2013. 725-730

[14] Zhen L, Qiong L. A new feature selection method for internet traffic classification using ml.PhysicsProcedia, 2012, 33: 1338-1345

[15] Antonio T, Paramita A S. Feature selection technique impact for Internet traffic classification using Naive Bayesian.JurnalTeknologi, 2015, 72(5):141-145

[16] Raveendran R, Menon R. An efficient method for Internet traffic classification and identification using statistical features.InternationalJournalofEngineeringResearchandTechnology,2015, 4(7):297-303

[17] Ghofrani F, Jamshidi A, Keshavarz-Haddad A. Internet traffic classification using hidden naive Bayes model. In: Proceedings of the 23rd Iranian Conference on Electrical Engineering, Tehran, Iran, 2015. 235-240

[18] 徐鵬,林森. 基于C4.5決策樹的流量分類方法. 軟件學(xué)報, 2009, 20(10):2692-2704

[19] 陳亮,龔儉. 基于NetFlow記錄的高速應(yīng)用流量分類方法. 通信學(xué)報, 2012, 33(1):145-152

[20] Kononenko I. Estimating attributes: analysis and extensions of Relief. In: Proceedings of the 1994 European Conference on Machine Learning, Catania, Italy, 1994. 171-182

[21] Han J, Kamber M. Data Mining:Concepts and Techniques.San Francisco:Morgan Kaufmann, 2001

[22] Yu L, Liu H. Feature selection for high-dimensionaldata: A fast correlation-based filter solution. In: Proceedings of the 20th International Conference on Machine Learning, Washington D.C, USA, 2003. 856-863

Internet traffic classification using the attribute weighted naive Bayes algorithm

Zhang Zexin***, Li Jun*, Chang Xiangqing*

(*Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190) (**University of Chinese Academy of Sciences, Beijing 100049)

Based on the analysis of the performance characteristics of the Naive Bayes (NB) method in wide use for network traffic classification, a novel attribute weighted Na?ve Bayes classification algorithm was proposed to overcome the NB method’s problem of low classification accuracy caused by its assumption that traffic attributes are of equal importance and independence is hard to satisfy in practice. The proposed algorithm uses the attribute selection algorithm of ReliefF and the correlation coefficient method to calculate the attribute weights based on the attribute information recorded by NetFlow. Then, it assigns a new instance to the most probable class, which has the largest posterior probability. The experiment showed that the classification accuracy of the proposed algorithm was over 94%, and the algorithm maintained simpleness, high efficiency and stability of the NB method. In short, this algorithm can fully meet the traffic classification demands of high-bandwidth networks.

traffic classification (TC), ReliefF, correlation coefficient, attribute weighting (AW), Naive Bayes (NB), NetFlow

10.3772/j.issn.1002-0470.2016.02.002

①973計劃(2012CB315803)和中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心“一三五”計劃(CNIC_PY-1401)資助項目。

2015-08-24)

②女，1987年生，博士生；研究方向：流量測量與特性分析，流量分類等；聯(lián)系人，E-mail: zhangzexin@cstnet.cn