基于馬氏距離的重采樣方法在流量識(shí)別中的應(yīng)用?

時(shí)鴻濤， 李洪平， 劉 競(jìng)

(中國(guó)海洋大學(xué)信息工程學(xué)院， 山東 青島 266100)

精確的網(wǎng)絡(luò)流量識(shí)別是流量工程、網(wǎng)絡(luò)安全、網(wǎng)絡(luò)質(zhì)量服務(wù)(QOS)以及用戶(hù)行為分析等工作的基礎(chǔ)[1]。由于動(dòng)態(tài)傳輸技術(shù)、流量加密算法和隧道技術(shù)在互聯(lián)網(wǎng)中的廣泛應(yīng)用，傳統(tǒng)的基于端口號(hào)和有效載荷檢測(cè)的流量識(shí)別技術(shù)變得不再準(zhǔn)確和高效，因此人們提出了基于機(jī)器學(xué)習(xí)的流量識(shí)別算法[2]。這類(lèi)算法通過(guò)分析和識(shí)別流量底層的統(tǒng)計(jì)特征來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)流量的識(shí)別。由于不需要分析流量的有效載荷信息，這類(lèi)算法的計(jì)算性能和準(zhǔn)確率都非常高。目前，基于機(jī)器學(xué)習(xí)的流量識(shí)別方法已經(jīng)成為了網(wǎng)絡(luò)流量研究的重點(diǎn)。然而，隨著研究的深入，人們發(fā)現(xiàn)網(wǎng)絡(luò)流量中數(shù)據(jù)分布的不均衡問(wèn)題會(huì)嚴(yán)重影響流量識(shí)別的準(zhǔn)確率。這種不均衡通常會(huì)導(dǎo)致機(jī)器學(xué)習(xí)算法偏向于流量數(shù)據(jù)中多數(shù)類(lèi)的流量樣本。例如：文獻(xiàn)[3]指出網(wǎng)絡(luò)流量數(shù)據(jù)中HTTP流量的數(shù)量通常會(huì)遠(yuǎn)遠(yuǎn)超過(guò)P2P和VoIP流量的數(shù)量，而機(jī)器學(xué)習(xí)算法通常會(huì)將所有流量識(shí)別為HTTP流量以實(shí)現(xiàn)高準(zhǔn)確率。在這種情況下，機(jī)器學(xué)習(xí)算法對(duì)于少數(shù)類(lèi)流量的識(shí)別準(zhǔn)確率非常低。然而，在許多情況下這些少數(shù)類(lèi)流量(例如P2P和VoIP流量)卻是人們更加關(guān)心的。

目前，解決數(shù)據(jù)分布不均衡問(wèn)題的方法可以主要地分為兩個(gè)方向：數(shù)據(jù)層方法和算法層方法。數(shù)據(jù)層方法主要通過(guò)對(duì)不均衡數(shù)據(jù)中的少數(shù)類(lèi)進(jìn)行過(guò)采樣或者對(duì)多數(shù)類(lèi)進(jìn)行欠采樣來(lái)實(shí)現(xiàn)數(shù)據(jù)的均衡。文獻(xiàn)[4]提出了一種新的過(guò)采樣方法SMOTE(Synthetic minority over-sampling technique)，該方法能夠通過(guò)合成新的樣本來(lái)提高少數(shù)類(lèi)樣本的比例。文獻(xiàn)[5]提出了一種邊界SMOTE過(guò)采樣方法，該方法通過(guò)對(duì)邊界附近的少數(shù)類(lèi)樣本進(jìn)行過(guò)采樣來(lái)實(shí)現(xiàn)樣本的均衡。文獻(xiàn)[6]通過(guò)比較過(guò)采樣方法和欠采樣方法，指出過(guò)采樣方法在解決數(shù)據(jù)分布不均衡問(wèn)題時(shí)比欠采樣方法更加有效。此外，算法層方法主要通過(guò)調(diào)整與錯(cuò)誤分類(lèi)相關(guān)的偏差來(lái)解決數(shù)據(jù)分布不均衡問(wèn)題。文獻(xiàn)[7]通過(guò)使用樣本加權(quán)方法來(lái)構(gòu)建成本敏感決策樹(shù)(Cost-sensitive decision tree)以解決數(shù)據(jù)分布不均衡問(wèn)題，并且該方法被證明能夠非常有效的解決數(shù)據(jù)分布不均衡問(wèn)題。文獻(xiàn)[8]比較了成本敏感方法和重采樣方法在解決數(shù)據(jù)分布不均衡問(wèn)題的效果，結(jié)果顯示成本敏感方法能夠?qū)崿F(xiàn)與重采樣方法相似的效果。然而，以上方法雖然取得不錯(cuò)的效果，但這些方法主要用于二分類(lèi)的數(shù)據(jù)分布不均衡問(wèn)題，對(duì)于網(wǎng)絡(luò)流量中的多分類(lèi)數(shù)據(jù)分布不均衡問(wèn)題，現(xiàn)有的重采樣方法往往存在過(guò)擬合的缺點(diǎn)，而成本敏感方法則由于難以獲得準(zhǔn)確的錯(cuò)誤分類(lèi)偏差從而導(dǎo)致較低的識(shí)別準(zhǔn)確率。

本文針對(duì)以上存在的問(wèn)題，提出了一種基于馬氏距離的重采樣算法，該方法能夠兼顧數(shù)據(jù)分布結(jié)構(gòu)和變量間的相關(guān)性。因此所生的樣本能夠保留原始數(shù)據(jù)分布特征，并最大程度地避免過(guò)擬合的發(fā)生。

1 算法模型

1.1 馬氏距離度量方法

馬氏距離是由印度學(xué)者馬哈拉諾比斯提出的一種距離度量方法，該方法能夠有效的計(jì)算兩個(gè)向量之間的相似度距離。相比歐氏距離，馬氏距離能夠考慮到向量中各變量之間的相關(guān)性。歐氏距離是一種普遍采用的距離度量方法，它被定義為n維空間中兩個(gè)向量之間的幾何距離，其計(jì)算公式如下：

(1)

也可以通過(guò)向量運(yùn)算形式來(lái)表示：

(2)

歐氏距離的特點(diǎn)是計(jì)算向量之間的平均幾何距離，即向量中每個(gè)變量對(duì)于歐氏距離的貢獻(xiàn)是相同的。然而，在統(tǒng)計(jì)學(xué)中人們更傾向于根據(jù)向量中每個(gè)變量的方差來(lái)評(píng)估變量間的距離，并且具有較大方差的變量在距離計(jì)算中將具有較高的權(quán)重。因此，馬氏距離度量更能體現(xiàn)這一統(tǒng)計(jì)特性。馬氏距離的計(jì)算公式可表示如下：

(3)

式中：S為樣本集的協(xié)方差矩陣；因此，馬氏距離能夠兼顧數(shù)據(jù)分布特征和變量之間的相關(guān)性。值得注意的是，當(dāng)協(xié)方差矩陣S為單位矩陣時(shí)，馬氏距離可簡(jiǎn)化為歐氏距離。

1.2 主成分分析介紹

主成分分析是一種的多元統(tǒng)計(jì)方法，它能夠在降低數(shù)據(jù)維度的同時(shí)盡可能的保留原始數(shù)據(jù)中的大多數(shù)變量信息。該方法主要通過(guò)線(xiàn)性轉(zhuǎn)換將一組存在相關(guān)性的變量轉(zhuǎn)換為一組線(xiàn)性無(wú)關(guān)的綜合變量，這些轉(zhuǎn)換后的綜合變量被稱(chēng)為主成分。主成分分析的公式可表示如下：

C=AX

。

(4)

式中：X為樣本數(shù)據(jù)矩陣；A為主成分系數(shù)矩陣；C為主成分向量，且主成分之間相關(guān)性為零，即Cov(Ci,Cj)=0 (Ci,Cj∈C,i≠j)。因此，主成分之間的協(xié)方差矩陣可表示為一個(gè)對(duì)角矩陣V，其公式如下：

V=λE。

(5)

式中：λ是主成分的特征值向量，E為單位矩陣。

此外，為了簡(jiǎn)化原始數(shù)據(jù)，在選擇主成分?jǐn)?shù)量時(shí)通常會(huì)選擇一個(gè)主成分集合的子集來(lái)代表原始變量。通常主成分個(gè)數(shù)的選擇需要根據(jù)所選主成分的方差累計(jì)貢獻(xiàn)率G來(lái)決定。

(6)

式中：λ為各主成分的特征值；s為所選擇的主成分?jǐn)?shù)量；n為全部主成分?jǐn)?shù)量。當(dāng)方差累積貢獻(xiàn)率G>85%時(shí)，就認(rèn)為所選擇的前s個(gè)主成分能夠反映原始變量的信息。

1.3 基于馬氏距離的重采樣方法

本文所提出的基于馬氏距離的重采樣方法將根據(jù)少數(shù)類(lèi)中每個(gè)樣本點(diǎn)與樣本集中心之間的馬氏距離來(lái)生成新的合成樣本。由于馬氏距離計(jì)算的復(fù)雜性，本文先利用主成分分析將原始樣本數(shù)據(jù)轉(zhuǎn)換到主成分空間，再通過(guò)計(jì)算各樣本點(diǎn)到樣本集中心的馬氏距離來(lái)實(shí)現(xiàn)新樣本的生成。主成分空間下馬氏距離的計(jì)算公式可簡(jiǎn)化為

(7)

即：

(8)

本文將利用公式(8)來(lái)實(shí)現(xiàn)樣本數(shù)據(jù)的重采樣，整個(gè)算法流程如算法1所示?；隈R氏距離的重采樣算法主要包含以下幾個(gè)步驟：

(1)對(duì)輸入的樣本數(shù)據(jù)進(jìn)行零均值化處理(代碼1)。

(2)使用主成分分析方法將零均值化后的樣本數(shù)據(jù)轉(zhuǎn)換至主成分空間，并選擇方差累積貢獻(xiàn)率G>85%的主成分子集作為原始變量的代表以簡(jiǎn)化計(jì)算復(fù)雜度(代碼2)。

(3)在主成分空間中循環(huán)生成新樣本(代碼3)。首先，隨機(jī)選擇一個(gè)樣本數(shù)據(jù)p，計(jì)算它到樣本集中心的馬氏距離dM(p,0)(代碼3.1)，然后，定義一個(gè)新的樣本數(shù)據(jù)q，并使該樣本數(shù)據(jù)滿(mǎn)足條件dM(q,0)=dM(p,0)(代碼3.2)。

(4)使用主成分分析方法將生成的新樣本集合轉(zhuǎn)換至原始數(shù)據(jù)空間(代碼4)。

(5)通過(guò)逆零均值化得到最終數(shù)據(jù)結(jié)果(代碼5)。

(6)對(duì)所有新樣本數(shù)據(jù)進(jìn)行輸出(代碼6)。

算法1基于馬氏距離的重采樣算法

輸入：Sin={(x1,1,x1,2,…，x1,m),…，(xn,1,xn,2,…，xn,m)} %少數(shù)類(lèi)樣本集合，

k%需要生成的新樣本數(shù)量，

輸出：Sout%新生成的樣本集合。

1:forj=1 tomdo

end for

2:計(jì)算Z的主成分，并選擇G>85%的主成分子集T，其行數(shù)和列數(shù)分別為n和m1(m1

3:fori=1 tokdo

3.1:p=random(T)

3.2:定義q

forj=1 tom1-1 do %為q前m-1項(xiàng)賦值。

qj=random(-λ1dM，λidM)

end for

將q加入集合Tnew。

end for

4:將Tnew轉(zhuǎn)換至原始數(shù)據(jù)空間，得到新集合Znew。

6:返回Sout。

通過(guò)以上算法，所有新生成的樣本將與原始樣本保持相同的數(shù)據(jù)分布特征。下面將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文算法的效果。

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

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

為了檢驗(yàn)本文提出的重采樣方法，本文使用劍橋大學(xué)實(shí)驗(yàn)室提供的公共網(wǎng)絡(luò)流量數(shù)據(jù)[7]作為實(shí)驗(yàn)數(shù)據(jù)。這些網(wǎng)絡(luò)流量數(shù)據(jù)包含10個(gè)數(shù)據(jù)集合，每個(gè)集合包含有不同數(shù)量的網(wǎng)絡(luò)流量樣本。每個(gè)樣本具有248個(gè)特征，這些特征是通過(guò)使用Tcptrace進(jìn)行提取。實(shí)驗(yàn)數(shù)據(jù)的流量特征信息如表1所示。從表1中可以發(fā)現(xiàn)對(duì)于所有集合，WWW流量類(lèi)型的樣本數(shù)量遠(yuǎn)遠(yuǎn)超過(guò)其他流量類(lèi)型。因此，這些數(shù)據(jù)集都存在明顯的多分類(lèi)數(shù)據(jù)分布不均衡問(wèn)題。

表1 實(shí)驗(yàn)數(shù)據(jù)特征信息Table 1 The characteristic information of the experimental data

2.2 評(píng)估指標(biāo)

為了評(píng)價(jià)所提出方法的有效性，本文使用3種不同的評(píng)價(jià)指標(biāo)對(duì)分類(lèi)結(jié)果進(jìn)行分析。這些評(píng)價(jià)指標(biāo)包括總體準(zhǔn)確率(Overall Accuracy, OA)、F-measure和g-mean。這些指標(biāo)通常被用于評(píng)價(jià)信息分類(lèi)和檢索的效果。

令TP代表真陽(yáng)，TN代表真陰，F(xiàn)P代表假陽(yáng)，F(xiàn)N代表假陰。OA可以表示為被正確分類(lèi)的樣本數(shù)量與全部樣本數(shù)量之間的百分比，它反映了分類(lèi)結(jié)果的總體正確程度，OA越高表示被正確分類(lèi)的樣本數(shù)量越多，其公式如下：

(9)

F-measure是召回率R和精確率P的一種加權(quán)平均值，它表示了對(duì)分類(lèi)結(jié)果中的查準(zhǔn)率和查全率的綜合評(píng)價(jià)，F(xiàn)-measure越高表示分類(lèi)算法更加有效：

(10)

g-mean表示為所有類(lèi)型流量召回率的幾何平均值，它主要用于評(píng)估多分類(lèi)分布不均衡數(shù)據(jù)的分類(lèi)效果，g-mean越高表示對(duì)少數(shù)類(lèi)的分類(lèi)效果越好：

(11)

式中n為網(wǎng)絡(luò)流量類(lèi)型的數(shù)量。

在本文中，所有指標(biāo)將分別按照網(wǎng)絡(luò)流量數(shù)據(jù)的流(Flow)和字節(jié)(Byte)兩種方式進(jìn)行計(jì)算以評(píng)估本文方法的性能。

2.3 分類(lèi)結(jié)果分析

本文選用C4.5決策樹(shù)作為分類(lèi)算法，使用數(shù)據(jù)集1作為訓(xùn)練數(shù)據(jù)，并對(duì)其余9個(gè)數(shù)據(jù)集進(jìn)行分類(lèi)實(shí)驗(yàn)。為了證明本文方法的有效性，本文方法將與文獻(xiàn)[2]中的SMOTE方法，文獻(xiàn)[3]中的邊界SMOTE方法以及文獻(xiàn)[8]中的基于MetaCost的成本敏感算法進(jìn)行比較，總體實(shí)驗(yàn)結(jié)果如圖1所示。通過(guò)對(duì)圖1的觀察，我們發(fā)現(xiàn)本文方法對(duì)于流OA、字節(jié)OA和流g-mean都獲得了最佳分類(lèi)結(jié)果，然而對(duì)于字節(jié)g-mean，本文方法的性能略低于其他方法。此外，我們發(fā)現(xiàn)在本實(shí)驗(yàn)中邊界SMOTE方法的實(shí)驗(yàn)結(jié)果要優(yōu)于SMOTE方法，這與文獻(xiàn)[3]中的結(jié)論一致。相比之下，成本敏感算法得到了最差的實(shí)驗(yàn)結(jié)果。

圖1 總體實(shí)驗(yàn)結(jié)果Fig.1 Overall experimental results

表2詳細(xì)顯示了4種方法對(duì)于各流量類(lèi)型所獲得的流F-measure。通過(guò)表2不難發(fā)現(xiàn)本文方法對(duì)于大多數(shù)流量類(lèi)型均取得了最佳的流F-measure，而對(duì)于ATTACK和FTP-DATA流量類(lèi)型，本文方法所取得的流F-measure也接近于相應(yīng)的最佳流F-measure。此外，通過(guò)對(duì)表3中最后一行所顯示的平均流F-measure進(jìn)行分析，可以證明本文方法獲得了最佳的流分類(lèi)效果。

表3詳細(xì)顯示了4種方法對(duì)于各流量類(lèi)型所獲得的字節(jié)F-measure。與表2類(lèi)似，本文方法對(duì)于大多數(shù)流量類(lèi)型，特別是含有大象流(Elephant flow)的流量類(lèi)型(如：P2P和FTP-Data流量類(lèi)型)，均獲得了最佳的字節(jié)F-measure。此外，通過(guò)對(duì)表3中最后一行所顯示的平均字節(jié)F-measure進(jìn)行分析，可以證明本文方法獲得了最佳的字節(jié)分類(lèi)效果。

表2 4種方法對(duì)于各網(wǎng)絡(luò)流類(lèi)型所獲得的流F-measureTable 2 The flow F-measure of the four methods for each traffic class

通過(guò)對(duì)全部實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以發(fā)現(xiàn)本文方法在處理網(wǎng)絡(luò)流量中的多分類(lèi)數(shù)據(jù)分布不均衡的問(wèn)題時(shí)，其性能明顯優(yōu)于現(xiàn)有的重采樣方法以及成本敏感方法，這也充分證明了本文方法在生成新的少數(shù)類(lèi)樣本時(shí)能夠充分保留原始數(shù)據(jù)中的數(shù)據(jù)分布特征，從而最大程度地避免破壞原始樣本數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。

表3 4種方法對(duì)于各網(wǎng)絡(luò)流類(lèi)型所獲得的字節(jié)F-measureTable 3 The byte F-measure of the four methods for each traffic class

3 結(jié)語(yǔ)

本文提出了一種基于馬氏距離的重采樣方法，該方法能夠根據(jù)樣本數(shù)據(jù)到樣本集合中心點(diǎn)之間的馬氏距離為少數(shù)類(lèi)生成新的合成樣本。相比于現(xiàn)有的重采樣方法，本文方法在為少數(shù)類(lèi)生成新樣本的同時(shí)，能夠保持樣本數(shù)據(jù)的原始分布結(jié)構(gòu)，從而避免過(guò)擬合的發(fā)生。使用劍橋大學(xué)實(shí)驗(yàn)室提供的公共網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行流量分類(lèi)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明與現(xiàn)有的SMOTE方法、邊界SMOTE方法以及基于MetaCost的成本敏感算法相比，本文方法能夠更好的提升少數(shù)類(lèi)的分類(lèi)準(zhǔn)確率，從而實(shí)現(xiàn)最佳的流量分類(lèi)效果。