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

易磊，潘志松，邱俊洋，薛膠，任會峰

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

?

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

易磊，潘志松，邱俊洋，薛膠，任會峰

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

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

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

網(wǎng)絡(luò)流量分類是指識別網(wǎng)絡(luò)中的各種應(yīng)用與協(xié)議并對相關(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)用趨勢分析、入侵檢測等方面具有重大的作用。近年來，基于網(wǎng)絡(luò)流量統(tǒng)計特征的機(jī)器學(xué)習(xí)分類方法受到了研究者的極大關(guān)注[2]。這類方法主要是利用網(wǎng)絡(luò)流量在傳輸層的統(tǒng)計特征，根據(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)出爆炸式的增長?，F(xiàn)有的批處理方法在處理大規(guī)模網(wǎng)絡(luò)流量分類問題時，其分類準(zhǔn)確率與模型訓(xùn)練速率等通常難以取得平衡，模型訓(xùn)練時間將隨著樣本數(shù)量的增大而急劇上升。如何解決大規(guī)模網(wǎng)絡(luò)流量分類問題已成為學(xué)者和業(yè)界人士面臨的重大挑戰(zhàn)。

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

針對高速骨干網(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)對比了8種不同在線學(xué)習(xí)算法在網(wǎng)絡(luò)流量分類應(yīng)用中的分類性能差異，為應(yīng)用打下了基礎(chǔ)；

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

1相關(guān)研究

近年來，基于流量統(tǒng)計特征的機(jī)器學(xué)習(xí)分類方法受到了研究者的極大關(guān)注[2]。這類方法主要是利用網(wǎng)絡(luò)流量在傳輸層的統(tǒng)計特征，根據(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ò)流量分類方法主要分為監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)兩類。監(jiān)督學(xué)習(xí)方面，Moore等[4]提出了一種使用樸素貝葉斯的分類方法，分類準(zhǔn)確率能達(dá)到約65%。Auld等[5]使用了貝葉斯神經(jīng)網(wǎng)絡(luò)的方法，并對特征集合進(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)用了決策樹理論。無監(jiān)督學(xué)習(xí)方面，Zander等[10]提出了基于AutoClass的無監(jiān)督網(wǎng)絡(luò)流量分類方法，是一種基于EM算法的無監(jiān)督貝葉斯分類器。Erman等[11]使用了EM聚類方法來解決流量分類問題，與貝葉斯分類方法相比有更高的分類準(zhǔn)確率。這些算法都屬于批處理的方法，在解決大規(guī)模網(wǎng)絡(luò)流量分類問題時，存在著分類器訓(xùn)練慢、計算復(fù)雜度高的缺陷。

在線學(xué)習(xí)是一種解決大規(guī)模問題的有效手段。在線學(xué)習(xí)自提出以來，已應(yīng)用于許多實(shí)際的應(yīng)用場景中，例如垃圾郵件檢測、在線廣告推送、多媒體檢索和金融時間序列預(yù)測。研究者們提出了大量的在線學(xué)習(xí)算法并進(jìn)行了理論性證明。Rosenblatt于1958年提出的感知機(jī)算法[12]是最為人熟知的在線學(xué)習(xí)算法。Crammer等[13]提出的Passive-Aggressive(PA)算法也是一種著名的在線學(xué)習(xí)算法。為了提高在線學(xué)習(xí)算法的效率，研究者們提出了一系列的二階在線學(xué)習(xí)算法[14]。與一階算法不同，二階算法通常假定權(quán)重向量服從一個高斯分布，并在每次迭代時嘗試更新高斯分布的均值與方差。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í)概念自提出以來發(fā)展出了一系列的算法，既能處理二分類問題又能處理多分類問題。為了驗(yàn)證在線學(xué)習(xí)方法在網(wǎng)絡(luò)流量分類 問題中的有效性，本文將網(wǎng)絡(luò)流量分類簡化為一個二分類問題。下面將由在線學(xué)習(xí)二分類算法的一般流程出發(fā)，提出在線學(xué)習(xí)網(wǎng)絡(luò)流量分類框架。

(1)

(2)

在線學(xué)習(xí)不再區(qū)分訓(xùn)練階段與測試階段，在接收到新樣本后對樣本類別進(jìn)行預(yù)測同時按照需要更新模型，其模型始終處于一個動態(tài)變化的過程，具有良好的實(shí)時性，能夠跟蹤數(shù)據(jù)流的變化趨勢。在線學(xué)習(xí)需要在模型對樣本進(jìn)行預(yù)測后，能夠即時獲取到樣本的真實(shí)類別。網(wǎng)絡(luò)流量樣本雖然是流式數(shù)據(jù)，但是樣本的真實(shí)類別無法實(shí)時獲取。為此，提出了一種按照在線學(xué)習(xí)方法訓(xùn)練分類器的網(wǎng)絡(luò)流量分類框架，如圖1所示。訓(xùn)練階段，該框架首先對實(shí)時網(wǎng)絡(luò)流量進(jìn)行抽樣并通過特征提取與樣本標(biāo)記產(chǎn)生訓(xùn)練數(shù)據(jù)集，然后使用在線學(xué)習(xí)算法對分類模型進(jìn)行訓(xùn)練。特征提取可使用Moore[3]提出的248維網(wǎng)絡(luò)流統(tǒng)計特征，樣本標(biāo)記可使用深度包檢測工具nDPI以及開源工具Tstat。測試階段，該框架使用訓(xùn)練完成的模型對實(shí)時網(wǎng)絡(luò)流量進(jìn)行分類。將模型分類結(jié)果與nDPI與Tstat等工具的結(jié)果對比，當(dāng)偏差達(dá)到一定閾值時對模型進(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ù)進(jìn)行“首尾相接”依次傳遞式的梯度優(yōu)化迭代而最終得到原問題的最優(yōu)解。當(dāng)按照隨機(jī)的方式挑選子函數(shù)而不是按照順序依次進(jìn)行優(yōu)化時，增量式方法可以稱為隨機(jī)優(yōu)化方法[3]。在線學(xué)習(xí)與隨機(jī)優(yōu)化有很緊密的關(guān)系，在很多情況下，兩者甚至等同使用[19]。在線和隨機(jī)優(yōu)化形式上雖然只是抽取樣本方式上的區(qū)別，但研究表明，它們的收斂性存在著差異。另一方面，有研究者認(rèn)為在線學(xué)習(xí)按順序選擇樣本的方式能敏銳捕捉到數(shù)據(jù)變化的趨勢。為了考察網(wǎng)絡(luò)流量中樣本順序?qū)Ψ诸愋Ч挠绊?，本文在SCW-I算法的基礎(chǔ)上將順序抽取樣本的方式改為隨機(jī)抽取的方式，實(shí)驗(yàn)對比了兩者在網(wǎng)絡(luò)流量分類問題中的差異，兩種方法之間的效果差異表明了網(wǎng)絡(luò)流量樣本存在著時序上的相關(guān)性。

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

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

2.2.1一階算法

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

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

(3)

式中目標(biāo)函數(shù)項為Passive項，表示最小化學(xué)習(xí)到的分類器與之前的分類器的距離，約束項為Aggressive項，表示學(xué)習(xí)到的分類器由當(dāng)前樣本帶來的損失。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ù)項表示最小化新舊分布權(quán)重的KL散度，約束項表示分類正確的概率大于某個閾值。

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

(7)

(8)

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

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

(9)

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

(10)

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

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

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ù)集，每個樣本均是由一條完整的雙向TCP流提取248維流量統(tǒng)計特征而來，實(shí)驗(yàn)中我們直接使用了完整的248維屬性作為樣本特征。該數(shù)據(jù)集采集了某網(wǎng)絡(luò)出口24 h內(nèi)10個時間段的雙向流量數(shù)據(jù)，每個時間段的平均抽樣時間約為1 680 s。該數(shù)據(jù)集共包含10種類別的377 526個網(wǎng)絡(luò)流量樣本，每種類別包含的流量和所占比例如表1。

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

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

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

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

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

3.3評價指標(biāo)

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

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

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

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

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

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

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

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

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

表4　測試精度

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

表5　F-measure

表6　支持向量數(shù)

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

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

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

表7　時序方式與隨機(jī)方式對比

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

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

(a)Moore4

(b)Moore6

(c)Moore8

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

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

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

4結(jié)束語

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

本文發(fā)現(xiàn)的網(wǎng)絡(luò)流量樣本的相關(guān)性只是通過實(shí)驗(yàn)來驗(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é)報, 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ī)學(xué)會模式識別與人工智能專委會委員，主要研究方向?yàn)槟Ｊ阶R別、機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)安全。主持國家科研項目多項，發(fā)表學(xué)術(shù)論文30余篇。

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

中文引用格式：易磊，潘志松，邱俊洋，等.在線學(xué)習(xí)的大規(guī)模網(wǎng)絡(luò)流量分類研究[J]. 智能系統(tǒng)學(xué)報， 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

作者簡介：

中圖分類號：TP181

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

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

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

基金項目：國家自然科學(xué)基金項目(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