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

時鴻濤， 李洪平， 劉 競

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

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

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

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

1 算法模型

1.1 馬氏距離度量方法

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

(1)

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

(2)

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

(3)

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

1.2 主成分分析介紹

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

C=AX

。

(4)

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

V=λE。

(5)

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

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

(6)

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

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

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

(7)

即：

(8)

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

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

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

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

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

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

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

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

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

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

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

1:forj=1 tomdo

end for

2:計算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項賦值。

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

end for

將q加入集合Tnew。

end for

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

6:返回Sout。

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

2 實(shí)驗分析

2.1 實(shí)驗數(shù)據(jù)

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

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

2.2 評估指標(biāo)

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

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

(9)

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

(10)

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

(11)

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

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

2.3 分類結(jié)果分析

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

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

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

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

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

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

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

3 結(jié)語

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