易磊，潘志松，邱俊洋，薛膠，任會(huì)峰

(中國(guó)人民解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

?

在線學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)流量分類研究

易磊，潘志松，邱俊洋，薛膠，任會(huì)峰

(中國(guó)人民解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，江蘇 南京 210007)

摘要：傳統(tǒng)的批處理機(jī)器學(xué)習(xí)方法在面對(duì)大規(guī)模網(wǎng)絡(luò)流量分類問題時(shí)存在分類器訓(xùn)練速度慢、計(jì)算復(fù)雜度高的缺陷。近年來(lái)迅速發(fā)展的在線學(xué)習(xí)方法是解決大規(guī)模問題的有效途徑。本文針對(duì)高速骨干網(wǎng)上的大規(guī)模網(wǎng)絡(luò)流量分類問題，提出了一個(gè)基于在線學(xué)習(xí)的分類框架，并應(yīng)用了8種在線學(xué)習(xí)算法。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，在分類精度相當(dāng)?shù)那闆r下，在線學(xué)習(xí)算法與支持向量機(jī)(SVM)相比空間開銷小、模型訓(xùn)練時(shí)間顯著縮短。同時(shí)，為了考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，本文?duì)比了樣本按時(shí)序處理與隨機(jī)處理兩種方式的差異，驗(yàn)證了網(wǎng)絡(luò)流量樣本存在著時(shí)序上的相關(guān)性。

關(guān)鍵詞：在線學(xué)習(xí)；大規(guī)模；網(wǎng)絡(luò)流量分類；時(shí)序相關(guān)性；數(shù)據(jù)流；隨機(jī)優(yōu)化

網(wǎng)絡(luò)流量分類是指識(shí)別網(wǎng)絡(luò)中的各種應(yīng)用與協(xié)議并對(duì)相關(guān)的網(wǎng)絡(luò)流量進(jìn)行分類的過程。網(wǎng)路流量分類是現(xiàn)代網(wǎng)絡(luò)管理與安全系統(tǒng)中最基本的功能[1]，在QOS服務(wù)質(zhì)量控制、網(wǎng)絡(luò)應(yīng)用趨勢(shì)分析、入侵檢測(cè)等方面具有重大的作用。近年來(lái)，基于網(wǎng)絡(luò)流量統(tǒng)計(jì)特征的機(jī)器學(xué)習(xí)分類方法受到了研究者的極大關(guān)注[2]。這類方法主要是利用網(wǎng)絡(luò)流量在傳輸層的統(tǒng)計(jì)特征，根據(jù)實(shí)驗(yàn)或經(jīng)驗(yàn)提取相關(guān)的特征屬性再運(yùn)用機(jī)器學(xué)習(xí)的方法進(jìn)行分類。傳統(tǒng)的機(jī)器學(xué)習(xí)方法在網(wǎng)絡(luò)流量分類領(lǐng)域已有了應(yīng)用，但依然存在如下問題：隨著日益擴(kuò)大的網(wǎng)絡(luò)帶寬與互聯(lián)網(wǎng)用戶規(guī)模，各類網(wǎng)絡(luò)流量呈現(xiàn)出爆炸式的增長(zhǎng)?，F(xiàn)有的批處理方法在處理大規(guī)模網(wǎng)絡(luò)流量分類問題時(shí)，其分類準(zhǔn)確率與模型訓(xùn)練速率等通常難以取得平衡，模型訓(xùn)練時(shí)間將隨著樣本數(shù)量的增大而急劇上升。如何解決大規(guī)模網(wǎng)絡(luò)流量分類問題已成為學(xué)者和業(yè)界人士面臨的重大挑戰(zhàn)。

在機(jī)器學(xué)習(xí)領(lǐng)域中，在線學(xué)習(xí)代表著一類利用一組有序的樣本建立預(yù)測(cè)模型的高效的、大規(guī)模的算法。在線學(xué)習(xí)算法按時(shí)序一次處理一個(gè)或者一小批樣本，處理過的樣本不再處理也不再保存，這使得在線學(xué)習(xí)方法計(jì)算迅速且高效，更適合樣本規(guī)模大且樣本按時(shí)序到達(dá)并動(dòng)態(tài)變化的應(yīng)用場(chǎng)景。有些研究者認(rèn)為，在線學(xué)習(xí)能夠敏銳地捕捉到數(shù)據(jù)變化的趨勢(shì)，進(jìn)而解決數(shù)據(jù)非同分布和實(shí)時(shí)學(xué)習(xí)問題[3]。

針對(duì)高速骨干網(wǎng)上的大規(guī)模網(wǎng)絡(luò)流量分類問題，本文將在線學(xué)習(xí)方法應(yīng)用于網(wǎng)絡(luò)流量分類問題，主要貢獻(xiàn)有：

1)提出了一種基于在線學(xué)習(xí)的網(wǎng)絡(luò)流量分類框架，在分類精度相當(dāng)?shù)臈l件下，在線學(xué)習(xí)方法比傳統(tǒng)的支持向量機(jī)(SVM)方法有更好的分類效率；

2)對(duì)比了8種不同在線學(xué)習(xí)算法在網(wǎng)絡(luò)流量分類應(yīng)用中的分類性能差異，為應(yīng)用打下了基礎(chǔ)；

3)為了考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，?duì)比了樣本按時(shí)序處理與隨機(jī)處理兩種方式的差異，驗(yàn)證了網(wǎng)絡(luò)流量樣本存在著時(shí)序上的相關(guān)性。

1相關(guān)研究

近年來(lái)，基于流量統(tǒng)計(jì)特征的機(jī)器學(xué)習(xí)分類方法受到了研究者的極大關(guān)注[2]。這類方法主要是利用網(wǎng)絡(luò)流量在傳輸層的統(tǒng)計(jì)特征，根據(jù)實(shí)驗(yàn)或經(jīng)驗(yàn)提取相關(guān)的特征屬性再運(yùn)用機(jī)器學(xué)習(xí)的方法進(jìn)行分類。基于統(tǒng)計(jì)特征的機(jī)器學(xué)習(xí)網(wǎng)絡(luò)流量分類方法主要分為監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)兩類。監(jiān)督學(xué)習(xí)方面，Moore等[4]提出了一種使用樸素貝葉斯的分類方法，分類準(zhǔn)確率能達(dá)到約65%。Auld等[5]使用了貝葉斯神經(jīng)網(wǎng)絡(luò)的方法，并對(duì)特征集合進(jìn)行了特征選擇，使得分類精度得到了提高，分類準(zhǔn)確率達(dá)到了95%。此外，還有一系列監(jiān)督學(xué)習(xí)方法運(yùn)用到了網(wǎng)絡(luò)流量分類問題中：文獻(xiàn)[6-7]將支持向量機(jī)運(yùn)用到了網(wǎng)絡(luò)流量分類問題；文獻(xiàn)[8-9]運(yùn)用了決策樹理論。無(wú)監(jiān)督學(xué)習(xí)方面，Zander等[10]提出了基于AutoClass的無(wú)監(jiān)督網(wǎng)絡(luò)流量分類方法，是一種基于EM算法的無(wú)監(jiān)督貝葉斯分類器。Erman等[11]使用了EM聚類方法來(lái)解決流量分類問題，與貝葉斯分類方法相比有更高的分類準(zhǔn)確率。這些算法都屬于批處理的方法，在解決大規(guī)模網(wǎng)絡(luò)流量分類問題時(shí)，存在著分類器訓(xùn)練慢、計(jì)算復(fù)雜度高的缺陷。

在線學(xué)習(xí)是一種解決大規(guī)模問題的有效手段。在線學(xué)習(xí)自提出以來(lái)，已應(yīng)用于許多實(shí)際的應(yīng)用場(chǎng)景中，例如垃圾郵件檢測(cè)、在線廣告推送、多媒體檢索和金融時(shí)間序列預(yù)測(cè)。研究者們提出了大量的在線學(xué)習(xí)算法并進(jìn)行了理論性證明。Rosenblatt于1958年提出的感知機(jī)算法[12]是最為人熟知的在線學(xué)習(xí)算法。Crammer等[13]提出的Passive-Aggressive(PA)算法也是一種著名的在線學(xué)習(xí)算法。為了提高在線學(xué)習(xí)算法的效率，研究者們提出了一系列的二階在線學(xué)習(xí)算法[14]。與一階算法不同，二階算法通常假定權(quán)重向量服從一個(gè)高斯分布，并在每次迭代時(shí)嘗試更新高斯分布的均值與方差。Confidence-Weighted (CW)算法[15]是一種典型的二階算法。此外，還有許多基于CW算法的改進(jìn)算法， Crammer等[16]提出了一種改進(jìn)CW算法魯棒性的AROW算法，Wang等[17]提出了Soft Confidence-weighted(SCW)算法。

本文提出的在線學(xué)習(xí)網(wǎng)絡(luò)流量分類框架應(yīng)用了8種在線學(xué)習(xí)算法。其中，一階算法有感知機(jī)算法、在線梯度下降算法(OGD)、Passive-Aggressive算法(PA)以及兩種基于PA的改進(jìn)算法：PA-I、PA-II算法；二階算法則選用了3種：Confidence-Weighted (CW)算法，以及基于CW算法改進(jìn)的2種Soft Confidence-weighted(SCW)算法：SCW-I、SCW-II算法。

2在線學(xué)習(xí)的網(wǎng)絡(luò)流量分類框架

2.1在線學(xué)習(xí)網(wǎng)絡(luò)流量分類框架

在線學(xué)習(xí)概念自提出以來(lái)發(fā)展出了一系列的算法，既能處理二分類問題又能處理多分類問題。為了驗(yàn)證在線學(xué)習(xí)方法在網(wǎng)絡(luò)流量分類 問題中的有效性，本文將網(wǎng)絡(luò)流量分類簡(jiǎn)化為一個(gè)二分類問題。下面將由在線學(xué)習(xí)二分類算法的一般流程出發(fā)，提出在線學(xué)習(xí)網(wǎng)絡(luò)流量分類框架。

(1)

(2)

在線學(xué)習(xí)不再區(qū)分訓(xùn)練階段與測(cè)試階段，在接收到新樣本后對(duì)樣本類別進(jìn)行預(yù)測(cè)同時(shí)按照需要更新模型，其模型始終處于一個(gè)動(dòng)態(tài)變化的過程，具有良好的實(shí)時(shí)性，能夠跟蹤數(shù)據(jù)流的變化趨勢(shì)。在線學(xué)習(xí)需要在模型對(duì)樣本進(jìn)行預(yù)測(cè)后，能夠即時(shí)獲取到樣本的真實(shí)類別。網(wǎng)絡(luò)流量樣本雖然是流式數(shù)據(jù)，但是樣本的真實(shí)類別無(wú)法實(shí)時(shí)獲取。為此，提出了一種按照在線學(xué)習(xí)方法訓(xùn)練分類器的網(wǎng)絡(luò)流量分類框架，如圖1所示。訓(xùn)練階段，該框架首先對(duì)實(shí)時(shí)網(wǎng)絡(luò)流量進(jìn)行抽樣并通過特征提取與樣本標(biāo)記產(chǎn)生訓(xùn)練數(shù)據(jù)集，然后使用在線學(xué)習(xí)算法對(duì)分類模型進(jìn)行訓(xùn)練。特征提取可使用Moore[3]提出的248維網(wǎng)絡(luò)流統(tǒng)計(jì)特征，樣本標(biāo)記可使用深度包檢測(cè)工具nDPI以及開源工具Tstat。測(cè)試階段，該框架使用訓(xùn)練完成的模型對(duì)實(shí)時(shí)網(wǎng)絡(luò)流量進(jìn)行分類。將模型分類結(jié)果與nDPI與Tstat等工具的結(jié)果對(duì)比，當(dāng)偏差達(dá)到一定閾值時(shí)對(duì)模型進(jìn)行重新訓(xùn)練。

圖1　在線網(wǎng)絡(luò)流量分類框架Fig.1　Online traffic classification scheme

本框架在獲取到完整訓(xùn)練集后離線訓(xùn)練在線學(xué)習(xí)分類模型。在線學(xué)習(xí)方法在優(yōu)化理論中被稱作增量算法。增量算法的主要思路是：當(dāng)目標(biāo)函數(shù)由一些子函數(shù)之和組成時(shí)，可以通過每次僅對(duì)一個(gè)子函數(shù)進(jìn)行“首尾相接”依次傳遞式的梯度優(yōu)化迭代而最終得到原問題的最優(yōu)解。當(dāng)按照隨機(jī)的方式挑選子函數(shù)而不是按照順序依次進(jìn)行優(yōu)化時(shí)，增量式方法可以稱為隨機(jī)優(yōu)化方法[3]。在線學(xué)習(xí)與隨機(jī)優(yōu)化有很緊密的關(guān)系，在很多情況下，兩者甚至等同使用[19]。在線和隨機(jī)優(yōu)化形式上雖然只是抽取樣本方式上的區(qū)別，但研究表明，它們的收斂性存在著差異。另一方面，有研究者認(rèn)為在線學(xué)習(xí)按順序選擇樣本的方式能敏銳捕捉到數(shù)據(jù)變化的趨勢(shì)。為了考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，本文在SCW-I算法的基礎(chǔ)上將順序抽取樣本的方式改為隨機(jī)抽取的方式，實(shí)驗(yàn)對(duì)比了兩者在網(wǎng)絡(luò)流量分類問題中的差異，兩種方法之間的效果差異表明了網(wǎng)絡(luò)流量樣本存在著時(shí)序上的相關(guān)性。

2.2在線學(xué)習(xí)二分類算法

為了檢驗(yàn)本文提出的在線學(xué)習(xí)分類框架，我們選取了8種在線學(xué)習(xí)方法進(jìn)行驗(yàn)證。所有的在線學(xué)習(xí)算法均滿足表1所示的在線學(xué)習(xí)算法一般流程，但由于理論基礎(chǔ)不同，它們?cè)趽p失函數(shù)、學(xué)習(xí)率、模型的更新條件以及方式有差異。

2.2.1一階算法

感知機(jī)算法感知機(jī)算法[12]于1958年提出，是最早最簡(jiǎn)單的一階在線學(xué)習(xí)算法，其優(yōu)化目標(biāo)是：最小化學(xué)習(xí)到的分類器由當(dāng)前樣本帶來(lái)的損失。感知機(jī)算法采用0-1損失作為損失函數(shù)，當(dāng)損失大于0時(shí)，按照梯度下降的方式更新模型，其學(xué)習(xí)率恒為1。

PA算法 Passive-Aggressive算法[13]是一種比感知機(jī)算法和OGD算法更加復(fù)雜的一階在線學(xué)習(xí)算法，其優(yōu)化目標(biāo)是如下兩個(gè)目標(biāo)的權(quán)衡：最小化學(xué)習(xí)到的分類器與之前的分類器的距離、最小化學(xué)習(xí)到的分類器由當(dāng)前樣本帶來(lái)的損失。PA算法可以看作為如下的在線優(yōu)化問題：

(3)

式中目標(biāo)函數(shù)項(xiàng)為Passive項(xiàng)，表示最小化學(xué)習(xí)到的分類器與之前的分類器的距離，約束項(xiàng)為Aggressive項(xiàng)，表示學(xué)習(xí)到的分類器由當(dāng)前樣本帶來(lái)的損失。PA算法的損失函數(shù)采用了hinge損失，模型的更新方式為梯度下降，學(xué)習(xí)率為1。此外，PA算法還能擴(kuò)展成PA-I算法與PA-II算法，這兩種算法能更好地處理不可分或者有噪聲的數(shù)據(jù)。

PA-I算法可以看作如下優(yōu)化問題：

(4)

PA-Ⅱ算法可以看作如式(5)形式：

(5)

2.2.2二階算法

(6)

式中:目標(biāo)函數(shù)項(xiàng)表示最小化新舊分布權(quán)重的KL散度，約束項(xiàng)表示分類正確的概率大于某個(gè)閾值。

SCW算法針對(duì)CW算法的局限，Wang等[17]于2013年提出了Soft Confidence-weighted算法。首先引入一種新的損失函數(shù)：

(7)

(8)

原始的CW算法采取了一種非常激進(jìn)的更新策略，即盡可能地改變分布以滿足當(dāng)前樣本帶來(lái)的約束。盡管這種方式有非常迅速的學(xué)習(xí)速率，但是在處理標(biāo)記錯(cuò)誤的樣本時(shí)會(huì)導(dǎo)致分布的參數(shù)誤修改。這就使CW算法在應(yīng)用于有大量噪聲的真實(shí)問題中時(shí)效果不理想。

SCW算法的提出克服CW算法的上述缺陷，具體的形式如下：

(9)

式中C是權(quán)衡passiveness與aggressiveness的參數(shù)。式(9)表示的是SCW-I算法。此外，若使用平方懲罰項(xiàng)，則變成了SCW-II算法：

(10)

一階算法方面，感知機(jī)算法優(yōu)化目標(biāo)是最小化學(xué)習(xí)到的分類器由當(dāng)前樣本帶來(lái)的損失，損失函數(shù)采用0-1損失，以定步長(zhǎng)的梯度下降的方式來(lái)更新模型；OGD算法與感知機(jī)算法優(yōu)化目標(biāo)一致，但采用了4種不同的損失函數(shù)，梯度下降迭代的步長(zhǎng)隨迭代輪數(shù)增長(zhǎng)而縮短；PA算法的優(yōu)化目標(biāo)是最小化學(xué)習(xí)到的分類器與之前的分類器的距離、最小化學(xué)習(xí)到的分類器由當(dāng)前樣本帶來(lái)的損失。PA算法也使用了梯度下降來(lái)更新模型。PA-Ⅰ算法與PA-Ⅱ算法類似，均使用了一個(gè)參數(shù)C來(lái)調(diào)節(jié)兩個(gè)目標(biāo)的權(quán)重，只是PA-Ⅱ算法使用了平方約束項(xiàng)。

二階算法則是假定權(quán)重向量服從高斯分布，每次迭代使用梯度下降嘗試更新均值與方差。CW算法的優(yōu)化目標(biāo)是最小化新舊分布權(quán)重的KL散度來(lái)更新，并確保分類正確的概率大于一個(gè)閾值。SCW算法在CW算法中引入了新的損失函數(shù)，并使用了參數(shù)C來(lái)調(diào)節(jié)兩個(gè)目標(biāo)的權(quán)重。SCW-Ⅰ算法與SCW-Ⅱ算法區(qū)別在于PA-Ⅱ算法使用了平方約束項(xiàng)。

3網(wǎng)絡(luò)流量分類實(shí)驗(yàn)

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

為了檢驗(yàn)本文提出的在線學(xué)習(xí)分類框架的性能，本實(shí)驗(yàn)采用了Moore等在文獻(xiàn)[3]中所使用的網(wǎng)絡(luò)流量數(shù)據(jù)集，每個(gè)樣本均是由一條完整的雙向TCP流提取248維流量統(tǒng)計(jì)特征而來(lái)，實(shí)驗(yàn)中我們直接使用了完整的248維屬性作為樣本特征。該數(shù)據(jù)集采集了某網(wǎng)絡(luò)出口24 h內(nèi)10個(gè)時(shí)間段的雙向流量數(shù)據(jù)，每個(gè)時(shí)間段的平均抽樣時(shí)間約為1 680 s。該數(shù)據(jù)集共包含10種類別的377 526個(gè)網(wǎng)絡(luò)流量樣本，每種類別包含的流量和所占比例如表1。

表1　Moore數(shù)據(jù)集樣本類別分布

由表1可以看出，數(shù)據(jù)集中各類數(shù)據(jù)數(shù)量分布極不平均，WWW流量占據(jù)了數(shù)據(jù)集中的很高的比例。樣本數(shù)量不平均問題對(duì)分類器的效果會(huì)有很大的影響，這是網(wǎng)絡(luò)流量分類問題中的一個(gè)難點(diǎn)。本文重點(diǎn)不在于此，因此我們將數(shù)據(jù)集的樣本分類簡(jiǎn)化為兩類：一類為WWW流，另一類為其他應(yīng)用。如表2所示，本次實(shí)驗(yàn)所用實(shí)驗(yàn)數(shù)據(jù)集分為兩組，一組是將10個(gè)子集獨(dú)立的作為實(shí)驗(yàn)數(shù)據(jù)集，記為：Moore1～Moore10；另一組將10個(gè)子集按順序合成為一個(gè)數(shù)據(jù)集，記為：MooreSet。為了模擬網(wǎng)絡(luò)流量按序到達(dá)的特點(diǎn)，我們將數(shù)據(jù)集的前90%樣本為訓(xùn)練集訓(xùn)練分類模型，后10%為測(cè)試集來(lái)測(cè)試模型效果。每個(gè)數(shù)據(jù)集的樣本分布如表2所示。

表2　數(shù)據(jù)集樣本分布

3.2實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文提出的在線學(xué)習(xí)網(wǎng)絡(luò)分類框架的有效性，本文使用MATLAB 2015a用于數(shù)值計(jì)算，SVM的實(shí)現(xiàn)采用了Libsvm軟件包，在線學(xué)習(xí)算法的實(shí)現(xiàn)采用了的LIBOL算法庫(kù)[20]。實(shí)驗(yàn)采用普通臺(tái)式電腦，操作系統(tǒng)為Windows 7 旗艦版，其中CPU為Intel i5處理器，內(nèi)存4 GB。

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

網(wǎng)絡(luò)流量分類系統(tǒng)的評(píng)價(jià)指標(biāo)主要有兩個(gè)方面：分類系統(tǒng)的效率與精度，效率意味著分類模型的訓(xùn)練時(shí)間足夠短，消耗的存儲(chǔ)空間能夠被接受，精度意味著分類準(zhǔn)確率較高，且漏報(bào)率與誤報(bào)率控制在一定范圍內(nèi)。為了對(duì)比批處理方法與在線學(xué)習(xí)方法在網(wǎng)絡(luò)流量分類問題中的性能差異，參考了文獻(xiàn)[21]的做法，將在線學(xué)習(xí)算法與SVM算法進(jìn)行對(duì)比，采用了模型訓(xùn)練時(shí)間、分類精度和F-measure為評(píng)價(jià)指標(biāo)。

對(duì)于在線學(xué)習(xí)，模型訓(xùn)練過程中的支持向量數(shù)量也是一項(xiàng)重要的評(píng)價(jià)指標(biāo)。支持向量是指在線學(xué)習(xí)模型訓(xùn)練過程中產(chǎn)生損失，并導(dǎo)致模型發(fā)生更新的樣本。支持向量數(shù)量過少導(dǎo)致模型訓(xùn)練比較粗糙，可能無(wú)法達(dá)到相應(yīng)的精度；數(shù)量過多則會(huì)導(dǎo)致計(jì)算量增加，降低模型訓(xùn)練的效率。因此，在對(duì)比不同在線學(xué)習(xí)方法的性能時(shí)，增加了模型訓(xùn)練過程的支持向量數(shù)。在對(duì)比樣本按時(shí)序處理與隨機(jī)處理的訓(xùn)練過程的差異時(shí)，還采用了模型訓(xùn)練的累積錯(cuò)誤率作為評(píng)價(jià)指標(biāo)。

3.4實(shí)驗(yàn)與分析

為了評(píng)估本文提出的在線學(xué)習(xí)網(wǎng)絡(luò)流量分類框架，本節(jié)設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1側(cè)重于對(duì)比在線學(xué)習(xí)算法與SVM以及不同在線學(xué)習(xí)方法之間的性能差異。實(shí)驗(yàn)2側(cè)重于考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，?duì)比樣本時(shí)序處理方式與隨機(jī)處理方式的性能差異。

3.4.1性能對(duì)比實(shí)驗(yàn)

性能對(duì)比實(shí)驗(yàn)在10個(gè)數(shù)據(jù)子集與1個(gè)完整的數(shù)據(jù)集上，分別運(yùn)行SVM算法與8種在線學(xué)習(xí)算法，使用每個(gè)數(shù)據(jù)集的前90%的樣本作為訓(xùn)練集訓(xùn)練模型，使用后10%的樣本作為測(cè)試集模擬模型實(shí)時(shí)運(yùn)行的性能。實(shí)驗(yàn)結(jié)果及分析如下：

表3　模型訓(xùn)練時(shí)間

表3列出了不同算法在不同數(shù)據(jù)集上的訓(xùn)練時(shí)間，由表可以看出：在線學(xué)習(xí)算法與SVM算法的模型訓(xùn)練時(shí)間存在相當(dāng)大的差異，在線學(xué)習(xí)模型訓(xùn)練速度要遠(yuǎn)快于SVM算法，在樣本數(shù)量大時(shí)，兩者速度差別尤其明顯。在使用完整數(shù)據(jù)集時(shí)，在線學(xué)習(xí)算法模型訓(xùn)練時(shí)間最多只需要18 s，而SVM算法則需要3 990 s，超過了1 h。另一方面，一階在線學(xué)習(xí)算法與二階在線學(xué)習(xí)算法在模型訓(xùn)練速度上也存在差異，二階算法要比一階算法略慢，其中可能的原因會(huì)在后文分析。

表4列出了不同算法在不同數(shù)據(jù)集上的測(cè)試精度，對(duì)于每個(gè)數(shù)據(jù)集，用黑體標(biāo)出了分類精度比SVM更差的在線算法；用星號(hào)標(biāo)出了分類精度最好的算法。由表可以看出：在使用完整數(shù)據(jù)集時(shí)，SVM的分類精度比所有的在線學(xué)習(xí)算法都要好。但在使用10個(gè)子集進(jìn)行實(shí)驗(yàn)時(shí)，二階在線算法總體來(lái)說具有比SVM更好的分類效果，一階算法在數(shù)據(jù)樣本較少的前5個(gè)子集上的分類效果明顯要差于SVM算法，尤其是OGD算法與感知機(jī)算法的分類效果最差，感知機(jī)算法在Moore3數(shù)據(jù)集上分類精度僅有0.452。后文將會(huì)解釋OGD算法與感知機(jī)算法在數(shù)據(jù)樣本少的情況下，分類精度差的原因。

表4　測(cè)試精度

表5列出了不同算法在不同數(shù)據(jù)集上的F-measure，對(duì)于每個(gè)數(shù)據(jù)集，用黑體標(biāo)出了F-measure比SVM更差的在線算法；用星號(hào)標(biāo)出了F-measure最好的算法。從表5可以得出與表4一致的結(jié)論。表6列出了8種不同在線算法在不同數(shù)據(jù)集上訓(xùn)練時(shí)的支持向量數(shù)。支持向量是指在線學(xué)習(xí)模型訓(xùn)練過程中產(chǎn)生損失，并導(dǎo)致模型發(fā)生更新的樣本。支持向量越多表示模型更新次數(shù)越多，模型訓(xùn)練越充分，相應(yīng)的計(jì)算量也越大。反之，則計(jì)算量更少，模型訓(xùn)練可能不夠。這里嘗試從支持向量數(shù)的角度解釋上文中發(fā)現(xiàn)的二階算法訓(xùn)練時(shí)間比一階算法慢，但是效果比一階算法好的現(xiàn)象。二階算法的模型更加復(fù)雜，模型每次更新的計(jì)算量更大，由表6可以看出，二階算法的支持向量數(shù)比一階算法略多，這就導(dǎo)致了二階算法比一階算法模型訓(xùn)練所需時(shí)間更長(zhǎng)。感知機(jī)與OGD算法的支持向量數(shù)明顯要少于其他在線算法，這導(dǎo)致了模型沒有得到有效的訓(xùn)練，達(dá)不到其他算法相當(dāng)?shù)姆诸惥?。我們注意到感知機(jī)算法的支持向量數(shù)最少，這可能是其分類精度極不穩(wěn)定甚至分類精度非常低的原因。

表5　F-measure

表6　支持向量數(shù)

通過性能對(duì)比實(shí)驗(yàn)可以發(fā)現(xiàn)，在8種在線學(xué)習(xí)分類算法中，二階算法的分類效果普遍優(yōu)于一階算法，與SVM分類效果相當(dāng)；SCW-Ⅰ算法有著較好的分類精度與分類效率，具有良好的應(yīng)用前景。

3.4.2時(shí)序相關(guān)性實(shí)驗(yàn)

為了考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，我們將?xùn)練數(shù)據(jù)集中樣本的順序隨機(jī)打亂，再用在線學(xué)習(xí)算法去訓(xùn)練模型。本實(shí)驗(yàn)使用10個(gè)數(shù)據(jù)子集作為實(shí)驗(yàn)數(shù)據(jù)集，將分類性能最好的SCW-I算法分別用樣本按時(shí)序處理與隨機(jī)處理的方式進(jìn)行訓(xùn)練，然后使用測(cè)試集進(jìn)行測(cè)試。其中，隨機(jī)處理方式按照不同的隨機(jī)順序重復(fù)實(shí)驗(yàn)20次，對(duì)實(shí)驗(yàn)結(jié)果取平均。實(shí)驗(yàn)還使用了模型訓(xùn)練過程中的累積錯(cuò)誤率作為評(píng)價(jià)指標(biāo)。時(shí)序方式與隨機(jī)方式對(duì)比見表7。

表7　時(shí)序方式與隨機(jī)方式對(duì)比

表7對(duì)比了SCW-Ⅰ算法時(shí)序方式與隨機(jī)方式在不同數(shù)據(jù)集下的性能指標(biāo)，用黑體標(biāo)出了較好的指標(biāo)。由表可以看出：在網(wǎng)絡(luò)流量分類問題中，時(shí)序方式比隨機(jī)方式有更低的訓(xùn)練累積錯(cuò)誤率、較好的測(cè)試精度與F-measure、更快的模型訓(xùn)練時(shí)間。這表明網(wǎng)絡(luò)流量的樣本順序?qū)Ψ诸愋Ч姓嬗绊?，因此可以認(rèn)為網(wǎng)絡(luò)流量樣本存在著一種時(shí)間上的相關(guān)性，這種特性對(duì)分類效率的提高有積極意義。

為了說明此種相關(guān)性，在模型訓(xùn)練過程中按照樣本數(shù)量間隔設(shè)置了15個(gè)采樣點(diǎn)，記錄了在線方式與隨機(jī)方式訓(xùn)練過程中訓(xùn)練錯(cuò)誤率的變化趨勢(shì)。我們選取了第4、6、8、10個(gè)子集的一次實(shí)驗(yàn)結(jié)果，繪制了模型訓(xùn)練累積錯(cuò)誤率的趨勢(shì)，如圖2所示。

(a)Moore4

(b)Moore6

(c)Moore8

(d)Moore10圖2　訓(xùn)練累積錯(cuò)誤率Fig.2　Training cumulative mistake rate

由圖2可以看出，模型訓(xùn)練過程中，隨機(jī)方式與時(shí)序方式的累積錯(cuò)誤率的變化趨勢(shì)有很大的不同。兩種方法不僅是收斂速度的差異，隨機(jī)方式的累積錯(cuò)誤率的變化趨勢(shì)是一個(gè)緩慢下降的過程，而在線方式的變化趨勢(shì)卻是一個(gè)曲折上升的過程，且每個(gè)數(shù)據(jù)集的曲線都有各自的結(jié)構(gòu)特點(diǎn)。

由此可以發(fā)現(xiàn)，網(wǎng)絡(luò)流量樣本中存在著一種時(shí)間上的相關(guān)性，對(duì)模型的分類效果有一定的正面影響。但這種特性還缺乏理論性的分析，同時(shí)如何運(yùn)用這種特性還需要進(jìn)一步研究。

4結(jié)束語(yǔ)

本文針對(duì)高速骨干網(wǎng)大規(guī)模網(wǎng)絡(luò)流量分類問題提出了一種基于在線學(xué)習(xí)的網(wǎng)絡(luò)流量分類框架，并將8種在線學(xué)習(xí)方法運(yùn)用到網(wǎng)絡(luò)流量分類問題中。對(duì)比在線算法與批處理方法SVM的性能差異，實(shí)驗(yàn)表明在分類精度相當(dāng)?shù)那闆r下，在線學(xué)習(xí)算法與SVM相比空間開銷小、模型訓(xùn)練時(shí)間顯著縮短；對(duì)比不同在線學(xué)習(xí)方法的分類性能，實(shí)驗(yàn)表明SCW-Ⅰ算法在8種在線學(xué)習(xí)算法中有最好的分類效果；對(duì)比樣本時(shí)序處理方式與隨機(jī)處理方式的差異，實(shí)驗(yàn)表明網(wǎng)絡(luò)流量樣本中存在著一種時(shí)間序列上的相關(guān)性。

本文發(fā)現(xiàn)的網(wǎng)絡(luò)流量樣本的相關(guān)性只是通過實(shí)驗(yàn)來(lái)驗(yàn)證，缺乏理論分析，也沒有找到合適的利用方法。另一方面，本文僅使用了二分類在線算法在實(shí)驗(yàn)數(shù)據(jù)集上進(jìn)行驗(yàn)證，如何把算法擴(kuò)展到多分類并實(shí)際應(yīng)用于大規(guī)模網(wǎng)絡(luò)環(huán)境是下一步工作的重點(diǎn)。

參考文獻(xiàn):

[1]ZHANG Jun, CHEN Xiao, XIANG Yang, et al. Robust network traffic classification[J]. IEEE/ACM transactions on networking, 2015, 23(4): 1257-1270.

[2]NGUYEN T T T, ARMITAGE G. A survey of techniques for internet traffic classification using machine learning[J]. IEEE communications surveys & tutorials, 2008, 10(4): 56-76.

[3]陶卿, 高乾坤, 姜紀(jì)遠(yuǎn), 等. 稀疏學(xué)習(xí)優(yōu)化問題的求解綜述[J]. 軟件學(xué)報(bào), 2013, 24(11): 2498-2507.

TAO Qing, GAO Qiankun, JIANG Jiyuan, et al. Survey of solving the optimization problems for sparse learning[J]. Journal of software, 2013, 24(11): 2498-2507.

[4]MOORE A W, ZUEV D. Internet traffic classification using bayesian analysis techniques[J]. ACM sigmetrics performance evaluation review, 2005, 33(1): 50-60.

[5]AULD T, MOORE A W, GULL S F. Bayesian neural networks for internet traffic classification[J]. IEEE transactions on neural networks, 2007, 18(1): 223-239.

[6]ESTE A, GRINGOLI F, SALGARELLI L. Support vector machines for TCP traffic classification[J]. Computer networks, 2009, 53(14): 2476-2490.

[7]SCHATZMANN D, MüHLBAUER W, SPYROPOULOS T, et al. Digging into HTTPS: flow-based classification of webmail traffic[C]//Proceedings of the 10th ACM SIGCOMM conference on internet measurement. New York, NY, USA, 2010: 322-327.

[8]WANG Yu, YU Shunzheng. Supervised learning real-time traffic classifiers[J]. Journal of networks, 2009, 4(7): 622-629.

[9]NGUYEN T T T, ARMITAGE G, BRANCH P, et al. Timely and continuous machine-learning-based classification for interactive IP traffic[J]. IEEE/ACM transactions on networking, 2012, 20(6): 1880-1894.

[10]ZANDER S, NGUYEN T, ARMITAGE G. Automated traffic classification and application identification using machine learning[C]//Proceedings of the IEEE conference on local computer networks 30th anniversary. Sydney, NSW, Australia, 2005: 250-257.

[11]ERMAN J, ARLITT M, MAHANTI A. Traffic classification using clustering algorithms[C]//Proceedings of the 2006 SIGCOMM workshop on mining network data. New York, NY, USA, 2006: 281-286.

[12]ROSENBLATT F. The perception: a probabilistic model for information storage and organization in the brain[J]. Psychological review, 1958, 65(6): 386-408.

[13]CRAMMER K, DEKEL O, KESHET J, et al. Online passive-aggressive algorithms[J]. Journal of machine learning research, 2006, 7(3): 551-585.

[14]CESA-BIANCHI N, CONCONI A, GENTILE C. A second-order perceptron algorithm[J]. SIAM journal on computing, 2005, 34(3): 640-668.

[15]CRAMMER K, DREDZE M, PEREIRA F. Exact convex confidence-weighted learning[C]//Advances in neural information processing systems 21. Mountain View, CA, USA, 2008: 345-352.

[16]CRAMMER K, KULESZA A, DREDZE M. Adaptive regularization of weight vectors[J]. Machine learning, 2013, 91(2): 155-187.

[17]WANG Jialei, ZHAO Peilin, HOI S C H. Exact soft confidence-weighted learning[C]//Proceedings of the 29th international conference on machine learning. Edinburgh, Scotland, UK, 2012.

[18]ZINKEVICH M. Online convex programming and generalized infinitesimal gradient ascent[C]//Proceedings of the international conference on machine learning. Washington, DC, USA, 2003: 928-936.

[19]CESA-BIANCHI N, CONCONI A, GENTILE C. On the generalization ability of on-line learning algorithms[J]. IEEE transactions on information theory, 2004, 50(9): 2050-2057.

[20]HOI S C H, WANG Jialei, ZHAO Peilin. LIBOL: a library for online learning algorithms[J]. Journal of machine learning research, 2014, 15(1): 495-499.

[21]LU Jing, HOI S C H, WANG Jialei, et al. Large scale online kernel learning[J]. Journal of machine learning research, 2014, 1: 1-48.

易磊，男，1991年生，碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)及其在大規(guī)模網(wǎng)絡(luò)流量分類中的應(yīng)用。

潘志松，男，1973年生，教授，博士生導(dǎo)師，江蘇省計(jì)算機(jī)學(xué)會(huì)模式識(shí)別與人工智能專委會(huì)委員，主要研究方向?yàn)槟Ｊ阶R(shí)別、機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)安全。主持國(guó)家科研項(xiàng)目多項(xiàng)，發(fā)表學(xué)術(shù)論文30余篇。

邱俊洋，男，1989年生，博士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)及其在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)流異常檢測(cè)中的應(yīng)用，發(fā)表學(xué)術(shù)論文2篇。

中文引用格式：易磊，潘志松，邱俊洋，等.在線學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)流量分類研究[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(2): 318-327.

英文引用格式：YI Lei, PAN Zhisong, QIU Junyang, et al. Large-scale network traffic classification based on online learning [J]. CAAI transactions on intelligent systems, 2016,11(3): 318-327.

Large-scale network traffic classification based on online learning

YI Lei, PAN Zhisong, QIU Junyang, XUE Jiao, REN Huifeng

(Institute of Command Information System, PLA University of Science and Technology,Nanjing 210007, China)

Abstract：Facing the challenges of large-scale network traffic classification problem, traditional batch machine learning algorithms suffer from slow training process and high computational complexity. In recent years, the rapid developing online learning technology is an effective way to solve large-scale problems. To address the issue of large-scale network traffic classification problem on a high-speed backbone network, we proposed a traffic classification scheme based on online learning and applied eight online learning algorithms. Experiments on real network traffic data sets showed that in the classification accuracy similar situation, online learning algorithm has less space overhead and training time than the support vector machine. Meanwhile, to examine the impact of the order of network traffic samples on the classification results, this paper compared the difference between the two ways of processing samples, sequentially and random, we verified that the presence of timing correlation in network traffic samples by comparing online learning and stochastic optimization.

Keywords：online learning; large-scale; traffic classification; timing correlation; data stream; stochastic optimization

作者簡(jiǎn)介：

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-4785(2016)03-0318-10

通信作者：易磊.E-mail：yileinjut@163.com.

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61473149).

收稿日期：2016-03-18.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.3969/j.issn.1673-4785.201603033

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150930.1557.028.html