面向不均衡數(shù)據(jù)的動態(tài)抽樣集成學(xué)習(xí)算法

張 燕 杜紅樂

(商洛學(xué)院數(shù)學(xué)與計算機應(yīng)用學(xué)院 陜西 商洛 726000)

0 引 言

在日益復(fù)雜的網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)攻擊越來越多樣化、復(fù)雜化，新的攻擊手段層出不窮。網(wǎng)絡(luò)入侵檢測通過分析用戶行為來判斷用戶是否存在威脅，是網(wǎng)絡(luò)安全體系中的重要組成部分?；跀?shù)據(jù)的網(wǎng)絡(luò)入侵檢測常采用機器學(xué)習(xí)將攻擊檢測問題轉(zhuǎn)換為數(shù)據(jù)分類問題，然而，在實際中，收集攻擊行為數(shù)據(jù)并進行正確標(biāo)注比較困難，代價也非常大。另外，新的攻擊方法日新月異，及時收集并標(biāo)注相應(yīng)的攻擊行為樣本難度很大，導(dǎo)致訓(xùn)練數(shù)據(jù)集中包含大量的正常行為數(shù)據(jù)和少量的攻擊行為數(shù)據(jù)。因此，網(wǎng)絡(luò)行為數(shù)據(jù)是不均衡數(shù)據(jù)。

傳統(tǒng)分類算法在均衡數(shù)據(jù)集下有較好的分類性能，而實際應(yīng)用中的數(shù)據(jù)集多是不均衡的，面向不均衡數(shù)據(jù)分類的研究是數(shù)據(jù)挖掘、機器學(xué)習(xí)等領(lǐng)域當(dāng)前的熱點之一[1-13]，對不均衡數(shù)據(jù)的解決方法主要集中在數(shù)據(jù)層面[1-4]和算法層面[5-13]。

算法層面的方法則是提出新方法或者改進已有算法，減少數(shù)據(jù)不均衡對分類性能的影響，主要包括代價敏感學(xué)習(xí)[3-4]、單類學(xué)習(xí)、集成學(xué)習(xí)[5-13]等。其中集成學(xué)習(xí)方法是通過迭代重采樣構(gòu)建多個弱分類器，然后再把弱分類器集成為強分類器，可以較好地提高分類器的分類性能，同時也是解決數(shù)據(jù)不均衡分類問題的方法[5-11]。文獻[5]中結(jié)合聚類算法對多數(shù)類樣本進行欠采樣，獲得與少數(shù)類樣本數(shù)量相同的樣本，并與少數(shù)類樣本一起構(gòu)成訓(xùn)練集，采用Adaboost算法獲得最終分類器。文獻[6]利用抽樣概率進行抽樣，通過迭代不斷修正抽樣概率，對于分類錯誤的樣本加大抽樣概率，而分類正確的樣本減小抽樣概率，目的是爭取下輪迭代中能選中進行學(xué)習(xí)。文獻[7-10]都是按照一定測量把數(shù)據(jù)集劃分為多個均衡的訓(xùn)練子集，生成多個基礎(chǔ)分類器，然后對多個分類器按照一定的規(guī)則進行集成，獲得最終分類器，從而提高分類性能。該類方法中如何對多數(shù)類樣本進行重取樣構(gòu)建平衡的訓(xùn)練子集，將對最終的分類器有較大的影響。而以上方法多是采用隨機抽取，并且每次抽取樣本的概率是相同且保持不變，這樣進行抽樣無法區(qū)分樣本的重要性。在算法迭代過程中，樣本被錯分，則表明樣本所包含的信息沒有被充分學(xué)習(xí)，在下一輪迭代中應(yīng)該加大被學(xué)習(xí)的力度，而對正確分類的樣本說明模型中已經(jīng)包含該樣本的信息，下一輪迭代中應(yīng)該減小學(xué)習(xí)，因此，采用動態(tài)的抽樣概率，區(qū)分在下一輪迭代中對樣本的重視程度。

基于以上分析，本文提出一種基于動態(tài)抽樣概率的集成學(xué)習(xí)算法，并應(yīng)用到網(wǎng)絡(luò)入侵檢測中。該算法依據(jù)抽樣概率分布對多數(shù)類樣本進行欠取樣，構(gòu)建多個均衡的訓(xùn)練子集；獲得對應(yīng)的子分類器，按照一定的參數(shù)計算分類效果，計算子分類器權(quán)值并獲得本輪循環(huán)的分類器；然后依據(jù)多輪循環(huán)所得分類器的分類效果更新多數(shù)類樣本的抽樣概率，進入下一次迭代；最后對多輪循環(huán)所得分類器進行集成獲得最終分類器。

1 相關(guān)工作

1.1 Boosting算法

Boosting算法的基本思想是組合學(xué)習(xí)，把多個預(yù)測精度不高的弱分類器提升到有高精度的強分類器，Boosting家族中最有代表性的是Adaboost算法，基本思想是：每次迭代更新樣本的權(quán)值，增加錯分樣本的權(quán)重，減小正確分類樣本的權(quán)重。樣本被錯分，表明樣本包含的信息未被學(xué)習(xí)或者學(xué)習(xí)不夠充分，因此在下輪迭代加大對錯分樣本的學(xué)習(xí)。然而Adaboost算法中，在計算樣本權(quán)重時，依據(jù)本輪循環(huán)所得分類器計算分類效果，而沒有考慮本次迭代之前所得分類器的分類情況。因此本文所提算法對樣本抽樣概率的更新綜合考慮本輪迭代之前所有分類器的分類效果，能夠更準(zhǔn)確地更新樣本的抽樣概率。

在Adaboost算法中，每次迭代中都更新樣本的權(quán)重，目的是改變下次循環(huán)中對樣本的學(xué)習(xí)程度。而本文所提算法在每次迭代中更新樣本的抽樣概率，目的是改變樣本被抽中的概率，也改變在下次迭代中對各個樣本的學(xué)習(xí)程度。因此本文借鑒Adaboost算法中更新權(quán)重的思想，在每次迭代中更新多數(shù)類樣本的抽樣概率。

EasyEnsemble算法可以解決不均衡數(shù)據(jù)問題，屬于欠采樣算法，是從多數(shù)類樣本中隨機抽取與少數(shù)類樣本數(shù)目相同的樣本，然后與少數(shù)類樣本一起構(gòu)成訓(xùn)練集，進行多次抽取，獲得多個均衡的訓(xùn)練子集，并獲得多個基礎(chǔ)分類器，然后通過Bagging方法集成得到最終分類器。Balance Cascad算法則是每次訓(xùn)練Adaboost后都會丟棄已被正確分類的多數(shù)類樣本，經(jīng)過反復(fù)迭代，使得數(shù)據(jù)集逐漸平衡。

EasyEnsemble算法在每次抽樣過程中，每個樣本被抽中的概率是相同的。而實際上，對于錯分樣本需要加大學(xué)習(xí)力度，即需要加大樣本的抽樣概率。因此本文所提方法對抽取樣本是依據(jù)樣本的抽樣概率分布進行抽取，每次迭代，對錯分樣本加大抽樣概率，而對正確分類樣本減小抽樣概率，目的在于加大下輪循環(huán)中對錯分樣本的學(xué)習(xí)。

1.2 抽樣概率

對多數(shù)類樣本按照概率pti進行抽樣，抽樣概率的總和為：

(1)

因為每個樣本被抽中的概率為pti，即被抽中期望為E(pti)，因此，對多數(shù)類樣本的抽樣期望值總和為：

(2)

在第一輪抽樣是，假設(shè)所有樣本有相同的抽樣概率，為了抽取與少數(shù)類樣本有相同數(shù)量的樣本，對多數(shù)類樣本的抽樣概率初始化為|T-|/|T+|。

在每輪迭代過程中，依據(jù)分類器對樣本包含信息的學(xué)習(xí)程度修改多數(shù)類樣本的抽樣概率，對樣本包含信息的學(xué)習(xí)程度依據(jù)當(dāng)前分類器對數(shù)據(jù)集的測試結(jié)果來評價。被正確分類表示學(xué)習(xí)較充分，可以減小該樣本抽樣概率，否則表示學(xué)習(xí)不充分或者未被學(xué)習(xí)，應(yīng)該加大該樣本的抽樣概率。由于少數(shù)類樣本數(shù)量較少，因此每個樣本都被抽中，即每個樣本的抽樣概率都為1。

2 入侵檢測模型

針對網(wǎng)絡(luò)行為數(shù)據(jù)不均衡的問題，本文提出基于抽樣概率分布的集成學(xué)習(xí)方法，提高對未知攻擊行為的識別能力。如圖1所示，該方法通過多次迭代獲得最終入侵檢測分類器，在每輪迭代中，依據(jù)多數(shù)類樣本的抽樣概率分布進行抽樣，抽取與少數(shù)類數(shù)目相同的樣本，然后與少數(shù)類樣本合并，構(gòu)成均衡的訓(xùn)練子集。該過程經(jīng)過多次，得到num個均衡的訓(xùn)練子集。然后采用Adaboost算法訓(xùn)練每個子集，獲得num個子分類器，依據(jù)各子分類器的分類效果計算權(quán)值，加權(quán)集成獲得本輪迭代的分類器。最后對數(shù)據(jù)集進行測試，依據(jù)測試的結(jié)果更新多數(shù)類樣本的抽樣概率，進入下一輪迭代。

圖1 入侵檢測模型構(gòu)建

在抽樣環(huán)節(jié)依據(jù)樣本的抽樣概率對多數(shù)類樣本進行抽樣，而不是EasyEnsemble算法中對多數(shù)類樣本的隨機抽樣，并且在每次迭代中更新多數(shù)類樣本的抽樣概率。在更新抽樣概率時，依據(jù)本次迭代之前所得分類器的加權(quán)集成分類器的測試效果，而不是依據(jù)本輪循環(huán)所得分類器的測試結(jié)果，這樣更有助于最終的集成并獲得最終分類器。

3 基于抽樣概率集成學(xué)習(xí)算法

EasyEnsemble算法中對多數(shù)類樣本進行隨機采樣，即平等地看待每個樣本，可以提高算法的泛化性能。但實際上每個樣本的重要性是不同的，即樣本包含的信息是不同的，常用解決方法是每次迭代更新樣本的抽樣概率。原因在于，如果樣本被錯分則表明該樣本中包含的信息沒有被學(xué)習(xí)或者沒有被充分學(xué)習(xí)，因此應(yīng)該加大該樣本被抽中的概率，而對正確分類的樣本則相反，應(yīng)減小樣本的抽樣概率。這個思想與Adaboost算法中更新樣本權(quán)值的思想是一致的。本文算法中采用同樣的思想更新樣本的抽樣概率，另外少數(shù)類樣本全部被選擇，則不需要改變抽樣概率。

算法1SP-Adaboost算法

輸入：數(shù)據(jù)集train_data={(xi,yi)},xi∈Rn,yi∈Y={-1,1}，迭代次數(shù)K，子分類器數(shù)num。

1. 把數(shù)據(jù)集劃分為多數(shù)類T+和少數(shù)類T-，|T+|和|T-|是兩類樣本數(shù)目。

2. 初始化多數(shù)類樣本抽樣概率分布：probk-1(p11,p12,…,p1|T+|),p1i=|T-|/|T+|,i=1,2,…,|T+|。

3. fork=1:K

(1) 依據(jù)抽樣概率分布probk-1從多數(shù)類樣本中抽取|T-|個樣本，采用放回抽樣，抽取num次得到num個子集，與少數(shù)類樣本一起構(gòu)成訓(xùn)練子集：Bk1，Bk2,…,Bknum,其中，num=┌a×|T+|/|T-|┐ ,a為調(diào)控系數(shù)；

(2) 對每個子集用Adaboost進行訓(xùn)練，獲得num個子分類器：fk1,fk2,…,fknum；

(4) 更新多數(shù)類的抽樣概率分布：

end fork

probk+1(i)=probk(i)×exp(-ak)/Zk=

probk(i)×exp(-0.5×ln((1-Ek)/Ek))/Zk=

probk(i)×|T-|/(2(1-Ek))

(3)

-1，則:

probk+1(i)=probk(i)×exp(ak)/Zk=

probk(i)×exp(0.5×ln((1-Ek)/Ek))/Zk=

probk(i)×|T-|/(2×Ek)

樣本抽樣概率被更新過后，期望值仍然為|T-|。

|T-|×(E(probk(i)/(2×(1-Ek))){yj×

由Adaboost算法可知:

因此，E(probk+1(i))=|T-|。

4 實驗分析

本文分為兩部分，首先選擇7組來自UCI的數(shù)據(jù)集，Car Evaluation、TIC-TAC-Toe Endgame、Liver Disorders、Breast Cancer、Haberman’s Survival、Blood transfusion和Teaching Assistant Evaluation，驗證所提算法的有效性，然后把所提算法應(yīng)用到網(wǎng)絡(luò)入侵檢測公共數(shù)據(jù)集KDDCUP，兩部分的實驗數(shù)據(jù)集的詳細(xì)情況如表1和表2所示。

表1 實驗數(shù)據(jù)集

序號數(shù)據(jù)集屬性多數(shù)類少數(shù)類比例1Car612103843.152Tic-Tac-To96263321.893liver72001451.384breast9201852.365haberman3225812.786blood45701783.207Teaching5102492.08

表2 實KDDCUP數(shù)據(jù)集

4.1 實驗評價指標(biāo)

分類器的分類性能多采用分類精度作為評價指標(biāo)，而對于不均衡數(shù)據(jù)，多關(guān)注少數(shù)類樣本的分類效果，分類準(zhǔn)確率不能準(zhǔn)確描述分類器的分類性能，針對不均衡數(shù)據(jù)分類的評價指標(biāo)多采用Recall、Precision、F-mean、G-mean、ROC曲線和AUC等，這些性能指標(biāo)是基于混淆矩陣來計算的，對于二分類問題的混淆矩陣如表3所示。

表3 混淆矩陣

依據(jù)混淆矩陣可以計算上面評價指標(biāo)：

(4)

(5)

(6)

(7)

式中：Recall表示正類的查全率，Precision表示正類的查準(zhǔn)率，F(xiàn)-mean同時考慮查全率和查準(zhǔn)率，只有當(dāng)兩個都大時F-mean的值才較大，可以較好地描述不均衡數(shù)據(jù)集下的分類性能，實驗中F-mean的n取值為2；G-mean綜合考慮兩類的準(zhǔn)確率，任何一類準(zhǔn)確率較低時，G-mean的值都會較小，因此能夠較好評價不均衡數(shù)據(jù)集下的分類性能。本文實驗通過以上指標(biāo)及ROC曲線、AUC值來評價算法的性能。

4.2 UCI數(shù)據(jù)實驗結(jié)果

本小節(jié)主要與Adaboost、Balance Cascad和EasyEnsemble算法進行性能對比，由于本文算法及Balance Cascad和EasyEnsemble算法的結(jié)果都有一定的隨機性。所以，實驗數(shù)據(jù)是經(jīng)過5次實驗，然后取平均值。另外，對各數(shù)據(jù)集采用一半作為訓(xùn)練集、一半作為測試集的式樣，具體的實驗結(jié)果如表4所示。從實驗結(jié)果可以看到，除了liver和Teaching數(shù)據(jù)集外，本文算法在其他實驗結(jié)果的大部分指標(biāo)上均優(yōu)于其他算法。

表4 算法性能對比1

續(xù)表4

4.3 KDDCUP數(shù)據(jù)集

本小節(jié)仍然是與Adaboost、Balance Cascad和EasyEnsemble算法進行性能對比，采用KDDCUP數(shù)據(jù)集的實驗結(jié)果。由表2可以看到,在測試數(shù)據(jù)集中增加了部分在訓(xùn)練數(shù)據(jù)集中沒有出現(xiàn)的攻擊類型數(shù)據(jù)，目的是為了驗證對新攻擊行為的檢測情況，詳細(xì)數(shù)據(jù)如表5所示，仿真結(jié)果是5次實驗結(jié)果的平均值。圖2是ROC曲線的對比結(jié)果，ROC曲線仍然是隨機的一次。

表5 算法性能對比2

圖2 KDDCUP的ROC曲線

為了驗證迭代次數(shù)對分類結(jié)果的影響，設(shè)計該部分實驗，該部分實驗數(shù)據(jù)仍然是采用5次實驗，然后取平均值。如表6所示?？梢钥闯?，進行10次以上的迭代時實驗結(jié)果差別很小，因此，為了減少算法時間，上面的實驗數(shù)據(jù)均是采用10次迭代的實驗結(jié)果。

表6 迭代次數(shù)的影響

為了驗證調(diào)控系數(shù)對實驗結(jié)果的影響，設(shè)計該部分實驗，該部分實驗數(shù)據(jù)仍然是采用5次實驗，然后取平均值，詳細(xì)的實驗結(jié)果如表7所示。實驗結(jié)果顯示，調(diào)控系數(shù)為1.5時，各項性能指標(biāo)比較均衡，因此上面實驗所得數(shù)據(jù)均是在調(diào)控系數(shù)為1.5時的實驗結(jié)果。

表7 調(diào)控系數(shù)的影響

5 結(jié) 語

針對網(wǎng)絡(luò)行為數(shù)據(jù)不均衡的問題，本文提出一種基于動態(tài)抽樣概率的集成學(xué)習(xí)算法，該算法依據(jù)抽樣概率分布對多數(shù)類樣本進行重采樣，相比隨機抽樣，能更準(zhǔn)確地加大對錯分樣本的學(xué)習(xí)。在更新樣本抽樣概率時，依據(jù)所得分類器的集成測試分類效果，而不是只依據(jù)本輪迭代所得分類器的分類效果。最后在兩種實驗數(shù)據(jù)集上的實驗結(jié)果也驗證本文算法的有效性。