基于概念飄移檢測的自適應(yīng)流量識別的研究
2013-04-29 15:06:15馬保雷宋穎慧劉亞維
智能計算機與應(yīng)用 2013年6期
馬保雷 宋穎慧 劉亞維
第3卷第6期2013年12月智 能 計 算 機 與 應(yīng) 用INTELLIGENT COMPUTER AND APPLICATIONSVol.3 No.6Dec.2013
摘要：基于機器學(xué)習(xí)的網(wǎng)絡(luò)流量識別技術(shù)作為一種典型的數(shù)據(jù)流分類的應(yīng)用，對概念漂移檢測方法的要求越來越高。針就這個問題，首先分析了概念漂移檢測的兩種典型方法，然后結(jié)合實際的網(wǎng)絡(luò)環(huán)境中經(jīng)常存在類別不平衡的特性提出了一種檢測概念漂移的算法CF_CDD，并對該算法的原理和統(tǒng)計學(xué)理論基礎(chǔ)進行了詳細的論述。再根據(jù)提出的概念漂移檢測算法構(gòu)建基于權(quán)重的集成分類器算法TCEL_CF_CDD，以達到自適應(yīng)流量識別的目的。最后進行實驗，驗證了文中提出的概念漂移檢測算法的可行性。
關(guān)鍵詞：流量識別； 概念漂移； 統(tǒng)計學(xué)檢驗； 集成學(xué)習(xí)
中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）06-0050-05
0引言
隨著網(wǎng)絡(luò)日新月異地迅猛發(fā)展，網(wǎng)絡(luò)上的各種協(xié)議也相繼出現(xiàn)，與此相對應(yīng)，流量識別技術(shù)則日趨顯示了其重要的作用和價值。傳統(tǒng)的基于端口的流量識別方法和深層數(shù)據(jù)包檢測（DPI）技術(shù)已經(jīng)不能很好地完成識別的任務(wù)，當前基于機器學(xué)習(xí)的流量識別技術(shù)已經(jīng)成為引領(lǐng)該領(lǐng)域研究的主流和方向[1]。網(wǎng)絡(luò)流量識別本質(zhì)上是根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包的特征將網(wǎng)絡(luò)數(shù)據(jù)流分成已知的協(xié)議類別，而這正是一種典型的數(shù)據(jù)流分類的應(yīng)用，那么必然地數(shù)據(jù)流分類面臨的概念漂移檢測問題在進行流量識別技術(shù)研究時也就需要慎重對待、深入考慮。近年來，關(guān)于數(shù)據(jù)流分類中概念漂移檢測的研究已取得了不少的成果，但是各類方法在應(yīng)對某種具體的數(shù)據(jù)流時卻都具有一定的局限性[2]。本文結(jié)合實際網(wǎng)絡(luò)環(huán)境中存在類別不平衡的情況，提出了更適用于網(wǎng)絡(luò)流量識別的概念漂移檢測方法。
1流量識別與概念漂移
概念漂移是數(shù)據(jù)流分類中的問題。作為一種具體的數(shù)據(jù)流，網(wǎng)絡(luò)數(shù)據(jù)流當然也存在概念漂移的相關(guān)問題。
1.1流量識別中的概念漂移
以機器學(xué)習(xí)的角度來看，基于機器學(xué)習(xí)的網(wǎng)絡(luò)流量識別技術(shù)實際上就是學(xué)習(xí)概念的過程[3]。識別的實現(xiàn)是通過在訓(xùn)練網(wǎng)絡(luò)數(shù)據(jù)集內(nèi)尋找其蘊含的協(xié)議分類規(guī)則（概念），由此得到網(wǎng)絡(luò)流量識別器，進而識別測試網(wǎng)絡(luò)數(shù)據(jù)包或者實際工作中到來的網(wǎng)絡(luò)數(shù)據(jù)包的類別。
假定網(wǎng)絡(luò)數(shù)據(jù)流D={…，di-1，di，di+1，…}，其網(wǎng)絡(luò)數(shù)據(jù)流中的協(xié)議類別C={C1，C2，…，Cn}，t時刻，在訓(xùn)練網(wǎng)絡(luò)數(shù)據(jù)集Dt上訓(xùn)練得到識別規(guī)則f：Dt→C，那么在t+1時刻就可以對dt+1網(wǎng)絡(luò)數(shù)據(jù)包的協(xié)議類別預(yù)測為f（dt+1）。但是，如果網(wǎng)絡(luò)數(shù)據(jù)流的隱藏背景在t時刻和t+1時刻發(fā)生了改變，引發(fā)了概念漂移，t+1時刻的實際識別規(guī)則已經(jīng)是g：Dt+1→C，且g≠f。也就是說，dt+1的真實協(xié)議類別是g（dt+1），因而利用原來的識別規(guī)則f預(yù)測的dt+1的協(xié)議類別即是不盡合理的。通過上面的論述可以看到，概念漂移對網(wǎng)絡(luò)流量識別的影響，而正確的做法也就相應(yīng)可得了。假定在t+△t時刻發(fā)生了概念漂移，應(yīng)該迅速檢測出漂移的發(fā)生，然后重新訓(xùn)練識別器，得到正確的識別規(guī)則g，然后利用g來進行以后的網(wǎng)絡(luò)數(shù)據(jù)包協(xié)議類別預(yù)測。
自適應(yīng)的流量識別就是能夠自主地檢測到概念漂移的發(fā)生，而后再對分類器進行重新構(gòu)建，以保證其對動態(tài)網(wǎng)絡(luò)數(shù)據(jù)流的正確識別。
1.2檢測方法分類
由于概念漂移的生成原因極其復(fù)雜，目前的檢測方法都不是直接的，而只是間接的[4]。最為基礎(chǔ)的有兩個：
（1）可能導(dǎo)致概念漂移發(fā)生的原因；
（2）概念漂移發(fā)生后可能產(chǎn)生的結(jié)果。
前者稱之為性質(zhì)法，后者為性能法[5]。
性質(zhì)法是指監(jiān)測最新的網(wǎng)絡(luò)數(shù)據(jù)集合的相關(guān)統(tǒng)計性質(zhì)，如協(xié)議種類的分布、各數(shù)據(jù)包的特征分布等等。Alippi設(shè)計了不依賴先驗信息而只需要數(shù)據(jù)分布模型的中心極限定理的概念漂移檢測算法[6]；Peter等提出了基于熵的概念漂移檢測方法[7]。
性能法是指檢測識別器最新的性能指標，如分類精度、召回率等等，如果分類器的性能指標出現(xiàn)較大波動，即說明發(fā)生了概念漂移。Widmer的FLORA算法依賴分類器的樣本覆蓋量和準確率決定窗口大小[8]；Last等提出的OLIN算法[9]即根據(jù)誤差率來判斷概念漂移產(chǎn)生與否。
2概念漂移檢測
上節(jié)闡述的兩種概念漂移檢測方法中，最經(jīng)常使用的是基于性能監(jiān)測的方法，但是卻不適合類別不平衡的數(shù)據(jù)流環(huán)境。本節(jié)將會看到，網(wǎng)絡(luò)流量環(huán)境中經(jīng)常出現(xiàn)的類別不平衡現(xiàn)象對概念漂移檢測的影響，同時結(jié)合這點，本文也提出了改進算法，以適應(yīng)實際網(wǎng)絡(luò)環(huán)境下的動態(tài)流量變化。
2.1檢測算法原理
對于穩(wěn)定的網(wǎng)絡(luò)流量，其各個協(xié)議類別是大致服從同一概率函數(shù)分布的，但是，如果一個存在概念漂移的網(wǎng)絡(luò)流量中，網(wǎng)絡(luò)數(shù)據(jù)包協(xié)議類別的分布概率卻會隨著概念漂移的發(fā)生而相應(yīng)改變。因此以觀察協(xié)議類別的概率分布變化來檢測網(wǎng)絡(luò)流量是否發(fā)生概念漂移則不失為一個恰當穩(wěn)妥的辦法。根據(jù)貝葉斯理論知道，概率分布P（w/x） = P（x/w）P（w）/P（x）。當P（x）改變而P（x/w）不變時，也就是說之前不常出現(xiàn)的協(xié)議數(shù)據(jù)包開始大量出現(xiàn)了或者相反，此時發(fā)生的概念漂移就是漸變；當P（x）不變而P（x/w）發(fā)生改變時，這種概念漂移就是突變。通常，在一個網(wǎng)絡(luò)數(shù)據(jù)流中多會同時存在這兩種類型的概念漂移，且也很難進行有效區(qū)分，但是從檢測概念漂移的目的來說，檢測到概念漂移后即可對分類器進行重新構(gòu)建，因此也就沒有必要區(qū)分概念漂移的具體類型了。
網(wǎng)絡(luò)數(shù)據(jù)流量是按照時間相依有序的離散的數(shù)據(jù)集合，流量識別實質(zhì)上就是進行時間序列分析。粗略來看，如果只是簡單的對網(wǎng)絡(luò)流量進行時序分析，似乎忽略了數(shù)據(jù)流變量之間內(nèi)存因果關(guān)系和結(jié)構(gòu)關(guān)系的影響。但是實際上時序分析是從總體方面對網(wǎng)絡(luò)流量進行考察，綜合說明各種作用力的共同影響。當無法輕易獲得所關(guān)心的各種紛繁因素時，就可以直接將時間t用作變量來代替各種因素。因此，概念漂移檢測就可以將時間t引入到文中的檢測模型內(nèi)，從而完成整個算法。
綜上，當將時間t作為變量引入檢測模型后，再加上一定的協(xié)議類別變量，此時如果能夠找到兩個變量之間的關(guān)系問題，就能夠得到概念漂移檢測的解決方法。而統(tǒng)計學(xué)理論已有很多研究成果就是致力于探討變量之間的關(guān)系，本文就從統(tǒng)計學(xué)理論中尋求概念漂移檢測的方法。
2.1.1統(tǒng)計學(xué)理論——卡方檢驗
卡方檢驗是一種應(yīng)用相當廣泛的非參數(shù)統(tǒng)計理論，利用該理論，可以判定實際觀察的概率分布是否發(fā)生了改變還是僅來自于理論誤差。
網(wǎng)絡(luò)數(shù)據(jù)包集合
P（Z=ci）=pi，s.t. Pi>0， ∑ni=1 pi=1（1）
變量ni代表監(jiān)測到的網(wǎng)絡(luò)流量數(shù)據(jù)集合中數(shù)據(jù)包協(xié)議類別為ci的數(shù)量，所有ni的和滿足條件（2）：
∑mi=1 ni=n（2）
已經(jīng)知道，ni是監(jiān)測值，再假定mi是理論值，則根據(jù)以上定義可得卡方值，如式（3）：
χ2=∑ni=1（ni-mi）2mi（3）
綜上可得，如果卡方值小于其臨界值，函數(shù)ψ就是變量Z的最優(yōu)擬合函數(shù)；相反，如果卡方值大于臨界值，函數(shù)ψ就不再是變量Z的最優(yōu)擬合函數(shù)。卡方的臨界值取決于已驗證得到的χ2統(tǒng)計理論表。
本文中，利用卡方值來檢驗連續(xù)兩個網(wǎng)絡(luò)流量的數(shù)據(jù)集合Di和Di+1是否發(fā)生了概念漂移。為了進一步闡述檢測方法，先做如下兩個假設(shè)。
（1）假定函數(shù)ψ已經(jīng)滿足于一個數(shù)據(jù)包集合的分布，然后驗證其連續(xù)的下一個集合是否滿足該條件；
（2）假定這個網(wǎng)絡(luò)流量中只存在兩種協(xié)議的數(shù)據(jù)包，即Http和Non-http。
根據(jù)上述假設(shè)，探討分析可得如表1所示的連續(xù)兩個網(wǎng)絡(luò)流量的數(shù)據(jù)包集合Di和Di+1的類別分布，表1中變量c1， c2， c3， c4分別代表Http和Non-http在不同數(shù)據(jù)集合中的觀察個數(shù)。根據(jù)這四個變量，就可以得到期望的兩個數(shù)據(jù)包集合中的協(xié)議類別數(shù)c1，c2 ，c3 ，c4 ，具體如公式（4）、（5）、（6）、（7）所示。
計算得到卡方值后，再和臨界值比較就能夠判定函數(shù)ψ是否滿足于Di+1，以此就可以判定概念漂移是否發(fā)生。
2.1.2類別不平衡與Fisher檢驗
χ2檢驗對2維表的各個協(xié)議類別的數(shù)量是有一定要求的，要求20%的協(xié)議類別數(shù)量不小于某個特定值。但是在真實的網(wǎng)絡(luò)環(huán)境下，經(jīng)常存在類別不平衡的流量，因此就無法滿足χ2檢驗的要求，此時就只能應(yīng)用Fisher精確檢驗。
同樣，使用上小節(jié)的2*2表進行說明，先設(shè)幾個變量：C1= c1 + c2，C2= c3 +c4，C3= c1 + c3，C4= c2 + c4，C = C1 + C2或C3 + C4 ，就可以得到p值，如式（9）所示，根據(jù)P{cij}來確定是否發(fā)生了概念漂移。
2.1.3檢驗步驟
根據(jù)概念漂移的檢測原理和統(tǒng)計學(xué)理論，就可以利用χ2檢驗和Fisher檢驗來共同確定連續(xù)的兩個數(shù)據(jù)包集合是否發(fā)生了概念漂移。具體步驟如下：
（1）建立零假說，即認為沒有發(fā)生概念漂移；
（2）確定數(shù)據(jù)包集合之間的實際差異，即根據(jù)類別是否平衡，進行χ2檢驗或者Fisher檢驗；
（3）根據(jù)χ2檢驗或者Fisher檢驗的結(jié)果，和理論值進行比較。如果大于理論值，則拒絕零假說，即認為發(fā)生了概念漂移。
2.2概念漂移檢測算法
通過上述的分析，本文接下來將給出一個利用統(tǒng)計學(xué)理論來檢測概念漂移發(fā)生的方法。和已經(jīng)存在的大部分概念漂移算法相比，該方法有兩個顯著的特征：第一，該方法屬于顯示探測概念漂移，因此其中含有單獨的檢測概念漂移發(fā)生的模塊；第二，該方法結(jié)合網(wǎng)絡(luò)流量識別的實際環(huán)境——經(jīng)常存在類別不平衡的特性，利用集成學(xué)習(xí)的方法來適應(yīng)動態(tài)的網(wǎng)絡(luò)數(shù)據(jù)變化。當一個網(wǎng)絡(luò)數(shù)據(jù)包集合到達以后，概念漂移檢測模塊就對其進行檢測，檢測是否有概念漂移發(fā)生，如果概念漂移發(fā)生了，檢測模塊就會告知流量識別器更新或者重構(gòu)識別器，以保證流量識別器能夠繼續(xù)對其后的網(wǎng)絡(luò)數(shù)據(jù)流進行準確識別。
算法CF_CDD旨在檢測出動態(tài)變化的網(wǎng)絡(luò)數(shù)據(jù)流中發(fā)生的概念漂移，一旦網(wǎng)絡(luò)數(shù)據(jù)包數(shù)量達到合適的窗口大小，概念漂移模塊就檢測連續(xù)的兩個網(wǎng)絡(luò)數(shù)據(jù)包集合之間是否有概念漂移發(fā)生。CF_CDD （Di，Di-1）算法如下。
在如上算法中，第1步、第2步是分類器對數(shù)據(jù)包Di，Di-1進行分類，并統(tǒng)計了相應(yīng)的樣本數(shù)量，第3步判斷協(xié)議類別是否出現(xiàn)了不平衡。若平衡，就進行χ2檢驗；不平衡，就是Fisher檢驗。最后，根據(jù)檢驗結(jié)果P和CONST的比較，判定是否發(fā)生了概念漂移。其中，CONST是根據(jù)自由度和置信度查表得來的界限。
2.3自適應(yīng)流量識別
若要完成自適應(yīng)的網(wǎng)絡(luò)流量識別，就要有效地檢測出概念漂移，再對分類器進行調(diào)整。本文采用集成學(xué)習(xí)來構(gòu)建分類器，因而構(gòu)建集成分類器的子分類器的機器學(xué)習(xí)算法就需要進行重點研究和專門討論了。
2.3.1類別不平衡下的機器學(xué)習(xí)算法
網(wǎng)絡(luò)數(shù)據(jù)流量中經(jīng)常存在協(xié)議類別不平衡的情況，協(xié)議類別的分布對基于機器學(xué)習(xí)的流量識別技術(shù)有著不小的影響。因此，選擇合適的機器學(xué)習(xí)算法以適應(yīng)網(wǎng)絡(luò)協(xié)議流不平衡環(huán)境下的在線流量分類，即顯得尤為重要[10]。
本文在實驗與分析中，將幾種典型的機器學(xué)習(xí)算法——決策樹C4.5、NBK、SVM與提出的概念漂移檢測算法結(jié)合后進行了對比，選取得到最能適應(yīng)含有類別不平衡協(xié)議流的真實環(huán)境的算法，且算法性能良好。
2.3.2集成學(xué)習(xí)
算法TCEL_CF_CDD，利用權(quán)重集成分類器對到達的網(wǎng)絡(luò)數(shù)據(jù)包進行分類，集成分類器的子分類器要根據(jù)概念漂移檢測模塊的結(jié)果進行調(diào)整、更新。
在上述算法的第4步中，基分類器的構(gòu)建過程中采用的是一種常用的機器學(xué)習(xí)算法，本文將通過實驗來選擇出實驗真實環(huán)境的算法；第4-6步是集成分類器的構(gòu)建過程，當變量Num等于Max時，標志著集成分類器構(gòu)造完成；而后在第8-11步中定義基分類器在相應(yīng)的數(shù)據(jù)集上的準確性；第12步是對各子分類器權(quán)重進行規(guī)格化；第13步表明了在本課題中為了充分利用樣本信息，對每組樣本均采用了先測試、后訓(xùn)練的策略；第14步是調(diào)用CF_CDD算法來檢測連續(xù)的兩個樣本網(wǎng)絡(luò)數(shù)據(jù)包集合之間是否發(fā)生了概念漂移，如果發(fā)生了概念漂移就要在最新的樣本數(shù)據(jù)集中構(gòu)建最新的基分類器，并用構(gòu)建出來的新分類器替換已經(jīng)存在的基分類器中表現(xiàn)最差的那個；第19步是在調(diào)整子分類器后，對各分類器的權(quán)重進行調(diào)整。
3實驗與分析
本文利用已經(jīng)捕獲的幾個網(wǎng)絡(luò)數(shù)據(jù)包集合來模擬網(wǎng)絡(luò)流量，將數(shù)據(jù)包按捕獲的時間進行順序排列
3.1機器學(xué)習(xí)算法的比較
將三種典型的機器學(xué)習(xí)算法——決策樹C4.5、NBK、SVM與本文提出的概念漂移檢測算法CF_CDD結(jié)合，分別構(gòu)造識別器，利用模擬的網(wǎng)絡(luò)流量的第一個數(shù)據(jù)包集合作為訓(xùn)練集，并且對后續(xù)的五個數(shù)據(jù)包集合進行分類，以測試不同的機器學(xué)習(xí)算法對識別精確性的影響，其結(jié)果如表2所示。從表2中可以看到：NBK的精確度明顯不高，而且也有隨時間下降的趨勢；決策樹C4.5和SVM相比NBK則有不錯且相對穩(wěn)定的精確度，適合提出的概念漂移檢測算法。
C4.5和SVM雖然都有不錯的精確度，但是因為知道SVM的建模時間相對C4.5來說耗時更長，再結(jié)合處理概念漂移檢測的實際特點——需要經(jīng)常調(diào)整分類器，因而此處不難得出結(jié)論：決策樹C4.5與本文提出的對概念漂移檢測算法CF_CDD結(jié)合進行網(wǎng)絡(luò)流量識別更能夠自適應(yīng)地處理實際網(wǎng)絡(luò)環(huán)境中的概念漂移問題。
3.2漂移檢測算法的比較
一般的數(shù)據(jù)流中，檢測概念漂移的算法是基于誤差率的，利用對分類器誤差率的監(jiān)測來判定是否發(fā)生了概念漂移。本實驗就對基于誤差率（Error_CDD）和本文提出的基于統(tǒng)計學(xué)檢驗（CF_CDD）的兩種概念漂移的算法在模擬的網(wǎng)絡(luò)流量識別的精度進行了對比，對比結(jié)果如圖1所示。
從圖1中可以看到，當有類別不平衡的協(xié)議類別時，Error_CDD的識別精度大幅度下降，驗證了之前提到的性能法不適合于類別不平衡的網(wǎng)絡(luò)數(shù)據(jù)流量識別，而本文提出的CF_CDD算法卻有良好的穩(wěn)定性，也說明本文提出的算法能夠很好地適應(yīng)類別不平衡現(xiàn)象。
4結(jié)束語
本文對流量識別中的概念漂移進行了深入研究，主要分析了漂移檢測原理，并結(jié)合真實網(wǎng)絡(luò)環(huán)境中存在的類別不平衡的特點，提出了基于統(tǒng)計學(xué)理論的概念漂移檢測算法，在檢測算法的基礎(chǔ)上提出了利用集成學(xué)習(xí)來完成自適應(yīng)的流量識別，最后的實驗證明了本文提出的算法的可行性和可靠性。當然，數(shù)據(jù)流概念漂移的問題還有很多，建議其后的主要研究方向就是類似本文這樣針對某種具體數(shù)據(jù)流的特點進行詳細的分析。
參考文獻：
[1]王耀南，張瑩.基于可信多數(shù)投票的快速概念漂移檢測[J].湖南大學(xué)學(xué)報（自然科學(xué)版）， 2010， 37（6）： 36-40.
[2]GUAN Jinghua， LIU Dayou. Selected ensemble of classifiers for handling concept-drifting data streams[J]. Computer Science， 2010，37（1）：204-207.
[3]王濤，李舟軍，顏躍進，等.數(shù)據(jù)流挖掘分類技術(shù)綜述[J].計算機研究與發(fā)展，2007，44（11）： 1809-1815.
[4]SUN Yue， MAO Guojun， LIU Xu. Mining concept drifts from data streams based on multi-classifiers[J]. Acta Automatica Sinica， 2008， 34（1）： 93-97.
[5]文益民.概念漂移數(shù)據(jù)流分類研究綜述[J].智能系統(tǒng)學(xué)報， 2012，7（6）：1-10.
[6]ALIPPI C， BORACCHI G， ROVERI M. An effective just-in-time adaptive classifier for gradual concept drifts[C]//Proceedings of the 2011 International Joint Conference on Neural Networks. San Jose， USA， 2011： 1675-1681.
[7]PETER V， ABRANHAM B. Entropy-based concept drift detection[C]//Proceedings of the 6th International Conference on Data Mining. Hong Kong， China， 2006： 1113-1118.
[8]WIDMER G， KUBAT M. Effective learning in dynamic environments by explicit context tracking[C]//Proceedings of the Sixth European Conference on Machine Learning. Vienna， Austria， 2003： 69-101.
[9]LAST M. Online classification of non-stationary data streams [J]. Intelligent Data Analysis， 2005， 6 （2）： 1-16.
[10]魯剛.分類不平衡協(xié)議流的機器學(xué)習(xí)算法評估與比較[J].軟件學(xué)報.2012，23（6）：1500-1516.
