面向不均衡數據的動態抽樣集成學習算法

張 燕 杜紅樂

(商洛學院數學與計算機應用學院 陜西 商洛 726000)

0 引 言

在日益復雜的網絡環境中，網絡攻擊越來越多樣化、復雜化，新的攻擊手段層出不窮。網絡入侵檢測通過分析用戶行為來判斷用戶是否存在威脅，是網絡安全體系中的重要組成部分。基于數據的網絡入侵檢測常采用機器學習將攻擊檢測問題轉換為數據分類問題，然而，在實際中，收集攻擊行為數據并進行正確標注比較困難，代價也非常大。另外，新的攻擊方法日新月異，及時收集并標注相應的攻擊行為樣本難度很大，導致訓練數據集中包含大量的正常行為數據和少量的攻擊行為數據。因此，網絡行為數據是不均衡數據。

傳統分類算法在均衡數據集下有較好的分類性能，而實際應用中的數據集多是不均衡的，面向不均衡數據分類的研究是數據挖掘、機器學習等領域當前的熱點之一[1-13]，對不均衡數據的解決方法主要集中在數據層面[1-4]和算法層面[5-13]。

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

基于以上分析，本文提出一種基于動態抽樣概率的集成學習算法，并應用到網絡入侵檢測中。該算法依據抽樣概率分布對多數類樣本進行欠取樣，構建多個均衡的訓練子集；獲得對應的子分類器，按照一定的參數計算分類效果，計算子分類器權值并獲得本輪循環的分類器；然后依據多輪循環所得分類器的分類效果更新多數類樣本的抽樣概率，進入下一次迭代；最后對多輪循環所得分類器進行集成獲得最終分類器。

1 相關工作

1.1 Boosting算法

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

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

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

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

1.2 抽樣概率

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

(1)

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

(2)

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

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

2 入侵檢測模型

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

圖1 入侵檢測模型構建

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

3 基于抽樣概率集成學習算法

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

算法1SP-Adaboost算法

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

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

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

3. fork=1:K

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

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

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

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的數據集，Car Evaluation、TIC-TAC-Toe Endgame、Liver Disorders、Breast Cancer、Haberman’s Survival、Blood transfusion和Teaching Assistant Evaluation，驗證所提算法的有效性，然后把所提算法應用到網絡入侵檢測公共數據集KDDCUP，兩部分的實驗數據集的詳細情況如表1和表2所示。

表1 實驗數據集

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

表2 實KDDCUP數據集

4.1 實驗評價指標

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

表3 混淆矩陣

依據混淆矩陣可以計算上面評價指標：

(4)

(5)

(6)

(7)

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

4.2 UCI數據實驗結果

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

表4 算法性能對比1

續表4

4.3 KDDCUP數據集

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

表5 算法性能對比2

圖2 KDDCUP的ROC曲線

為了驗證迭代次數對分類結果的影響，設計該部分實驗，該部分實驗數據仍然是采用5次實驗，然后取平均值。如表6所示。可以看出，進行10次以上的迭代時實驗結果差別很小，因此，為了減少算法時間，上面的實驗數據均是采用10次迭代的實驗結果。

表6 迭代次數的影響

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

表7 調控系數的影響

5 結 語

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