基于改進權值更新和選擇性集成的AdaBoost算法

歐陽瀟琴 王秋華

摘 要：針對傳統AdaBoost算法中樣本權值更新缺陷造成的分類準確率降低，以及冗余弱分類器造成的分類速度慢、計算開銷大等問題，提出一種基于改進權值更新和選擇性集成的AdaBoost算法。首先，在弱分類器訓練階段，提出一種改進權值更新方式的AdaBoost算法，根據各個樣本在前t次訓練中的平均正確率更新樣本權值，使所有樣本的權值更新更均衡，在一定程度上抑制了噪聲樣本權值的無限擴大;其次，在弱分類器組合階段，提出一種新的弱分類器相似度度量方式，并基于該度量方式和層次聚類算法進行選擇性集成，剔除了冗余的弱分類器，提高了分類速度，減少了計算開銷;最后使用KDDCUP99、waveform和image-segmentation三個數據集對所提方案進行性能仿真與驗證，分類準確率分別達到99.51%、86.07%和94.45%。實驗表明，將改進權值更新和選擇性集成的AdaBoost算法應用于入侵檢測系統，不僅提高了分類準確率和檢測速度，而且降低了計算開銷。

關鍵詞：入侵檢測;集成學習;AdaBoost;權值更新;選擇性集成

DOI： 10. 11907/rjdk.191736

開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312

文獻標識碼：A

文章編號：1672-7800（ 2020）004-0257-06

0 引言

入侵檢測可從網絡系統若干關鍵點收集信息，并分析網絡是否存在入侵行為及跡象[1，2]。入侵檢測可看作一個數據分類過程，從收集的信息中識別出正常操作和入侵行為。當前，入侵檢測分類算法主要有決策樹[3]、神經網絡[4]和支持向量機[5]等。上述分類器均為單個分類器，泛化能力不足，分類準確率不高。因此，集成學習方法[6]被引入。集成學習是一種通過構建多個弱分類器（單個分類器），再將其組合成一個強分類器的學習方法。集成學習方法充分利用單個弱分類器之間的互補性，有效提升了分類器的泛化能力。

集成學習方法分為Bagging[7]和Boosting[8]兩大類。Bagging方法通過對訓練樣本進行有放回的隨機抽樣得到不同的樣本集，從而構建一組具有差異的弱分類器，最后通過平均投票法確定待測樣本類別。隨機森林（ RandomForest）[9]是改進版的Bagging集成方法。Random Forest使用決策樹作為弱學習器，每個決策樹隨機選擇樣本的一部分特征，并從中選擇一個最優特征作為決策樹的左右子樹，進一步增強了模型的泛化能力。B oosting方法先通過初始訓練集訓練出一個弱分類器，再根據該分類器的表現對訓練樣本分布進行調整，使得先前弱分類器分錯的訓練樣本在后續受到更多關注;然后基于調整后的樣本分布訓練下一個弱分類器;最終將所有弱分類器進行加權組合，每個弱分類器的權重依賴于自身分類誤差。在B oosting方法中，最著名的是AdaBoost算法[10]（Adaptive Boosting：自適應提升），它是目前最具實用價值的集成學習算法，其本質是通過改變樣本分布實現弱分類器訓練。它根據每次訓練集中每個樣本的分類是否正確，以及上一次的總體分類準確率更新每個樣本的權值。將修改過權值的訓練集送給下層分類器進行訓練，最后將每次訓練得到的分類器組合成強分類器。雖然AdaBoost算法在一定程度上提高了分類器的泛化能力，其仍存在以下不足：

（1）該算法的權值更新機制容易造成不公平的權值分配，且容易導致噪聲樣本權值的無限增大。不少學者針對該缺點對算法進行了改進[11-14]。文獻[11]提出一種分級結構的AdaBoost算法，通過增大權重變化量、尋找最優分類器等方法，提高分類準確率與分類速度;文獻[12]提出一種基于噪聲檢測的AdaBoost改進算法，根據錯分樣本中噪聲樣本與普通錯分樣本的差異性確定噪聲樣本，并重新對其分類，從而提高了分類準確率;李文輝等[13]通過調整加權誤差分布限制目標類樣本權值的擴張，并且以概率值輸出代替傳統的離散值輸出作為強分類器的輸出結果;董超等[14]根據樣本分類正確率提高其權值，同時抑制噪聲樣本權值的無限增大。

（2）弱分類器訓練過程帶有一定隨機性，容易導致冗余弱分類器產生。此類弱分類器不僅不能提高分類準確率，還會增加計算開銷，降低分類速度。周志華[15]提出的“Many could be better than all”理論證明，使用較少的弱分類器組合而成的強分類器也可以達到相同甚至更優的效果。基于該理論，選擇性集成方法[16-17]被提出，該方法在集成學習的基礎上增加了一個分類器選擇階段。在該階段，通過某種策略剔除那些對集成分類器分類能力具有負面影響的弱分類器，將剩下的弱分類器組合成強分類器，從而進一步提高分類性能;謝元澄等[18]通過刪除弱分類器中性能差的分類器進行選擇性集成;王忠民等[19]通過計算弱分類器的雙誤差異性增量值并結合近鄰傳播聚類算法，將T個弱分類器分成K個簇，選取每簇的中心分類器組合成強分類器。

為解決AdaBoost算法存在的上述問題，本文提出一種基于改進權值更新和選擇性集成的AdaBoost算法，該算法分別在弱分類器訓練階段和弱分類器組合階段進行改進。

在弱分類器訓練階段，針對AdaBoost算法僅依靠前一次分類情況決定樣本的權值變化太過片面，并且容易導致噪聲樣本權值無限擴大的缺點，提出一種改進權值更新方式的AdaBoost算法。改進更新方式根據各個樣本在前t次訓練中的加權平均正確率更新樣本權值，所有樣本都在前t次訓練的基礎上提升其權值。前t次的分類正確率越高，權值提升越小。最后再對提升后的權值歸一化，在一定程度上抑制了噪聲樣本權值的無限擴大，令所有樣本的權值更新更均衡。

在弱分類器組合階段，針對弱分類器冗余導致的分類速度慢、計算開銷大等問題，提出一種新的弱分類器相似度度量方式，并基于該相似度度量方式和層次聚類算法[20-21]進行選擇性集成，將相似度超過閾值的弱分類器歸入一類，取分類準確率最高的弱分類器組合成強分類器，從而剔除冗余的弱分類器，提高分類速度，減少計算開銷。

基于KDDCUP99、wavetorm和image-segmentation三個數據集對所提方案進行性能仿真與驗證，實驗結果表明，改進權值更新方式的AdaBoost算法提高了分類準確率。選擇性集成不僅剔除了冗余的弱分類器，并且能夠保持相同甚至更高的分類準確率。

1 AdaBoost算法及分析

1.1 AdaBoost算法

AdaBoost算法是一種將多個弱分類器組合成一個強分類器的迭代算法，通過T次迭代訓練出T個弱分類器，算法框架如圖1所示。

算法流程如下：①在第t次迭代時，根據此次樣本權值分布Wt，從初始訓練集D中隨機抽取N個樣本作為此次訓練樣本集Dt，并根據Dt訓練得到第t個弱分類器h.;②使用h.預測D中的每個樣本，得到ht的分類準確率。根據該準確率計算ht的權重ac，，準確率越高，權重越大;③根據步驟②的分類結果對Wt進行更新，提升錯誤分類樣本的權值，降低正確分類樣本的權值，使得錯分樣本在下一次迭代中被選中的概率更大;④將訓練得到的弱分類器組合成一個強分類器H，弱分類器的加權投票結果作為強分類器的輸出。

1.2 AdaBoost算法分析

AdaBoost算法通過訓練多個弱分類器對待分類樣本進行分類，并投票決定樣本類別，利用弱分類器之間的互補性提高強分類器的分類精度。相比于單個分類器，在一定程度上提高了分類準確率，但其缺點也很明顯。

（1）樣本權值更新時對所有正確（或錯誤）分類的樣本同等看待，并且僅憑第t次訓練結果決定一個樣本在下一次迭代中的權值太過片面。例如，在前t-1次訓練中，樣本xp被多次分錯，而樣本xq被多次分對，但在第t次訓練中二者都分類錯誤。那么，令xp和xq的權值有同樣變化是不公平的，而應令xp的權值比xq有更大提升，使其在第t+1次訓練中更容易被選中。除此之外，一味降低分對樣本的權值、提升分錯樣本的權值，容易導致噪聲樣本權值無限增大，從而使非噪聲樣本被選中的概率降低，最終分類準確率也可能隨之降低。

（2）由于弱分類器訓練階段采用有概率的隨機抽樣方法選取訓練樣本，有可能使得兩次訓練抽取到的訓練集十分相似，從而得到兩個差異性很小的弱分類器。這些冗余的弱分類器不僅對分類性能沒有幫助，反而會降低分類速度，增加計算開銷。

2 AdaBoost算法改進

針對AdaBoost算法缺點，本文提出一種基于改進權值更新和選擇性集成的AdaBoost算法，該算法分為弱分類器訓練和弱分類器組合兩個階段。

該方法不需要預先設置K值，并且保證最后得到的K個類中任意兩個類之間的相似度小于或等于δ，每個類內的任意兩個弱分類器相似度大于δ。剔除冗余的弱分類器，保留相互之間差異性較大的弱分類器，既提高了分類速度，又保證了較高的準確率。

3 性能仿真與分析

3.1 實驗數據集

本文使用3個數據集對所提算法進行性能仿真，分別是KDDCUP1999、wavetorm和image-segmentation，如表1所示。KDDCUP1999是一個入侵檢測數據集，包含Nor-mal、DoS、Probe、U2L和R2L五個類別標簽;wavetorm是一個聲音波形數據集，包含3個類別標簽：0、1和2;im -age-segmentation是一個圖像識別數據集，包含7個類別標簽：CRASS、CEMENT、WINDOW、PATH、SKY、FOLIAGE、BRICKFACE。

實驗中將每個數據集的70%劃分為訓練集，30%劃分為測試集，取10次實驗結果的平均值作為最終結果。采用分類準確率衡量分類效果，其計算方式為分類正確的樣本數與樣本總數的比例。另外，分類效率的衡量標準為最終用來組合成強分類器的弱分類器數目，弱分類器越少，效率越高，反之越低。

3.2 分類準確率

首先對傳統的AdaBoost算法權值更新方式進行改進。為了驗證改進權值更新后的AdaBoost算法分類效果，在KDDCUP1999、wavef orm、image-segmentation三個數據集上進行實驗，并與傳統AdaBoost算法和文獻[14]所提改進AdaBoost算法進行對比，對比結果如圖2、圖3和圖4所示。

從圖2、圖3和圖4可以看出，文獻[14]所提算法雖然提高了部分類別的分類準確率，但對U2R類別的樣本分類準確率明顯偏低，而本文所提算法在各個樣本類別的分類準確率都優于傳統AdaBoost算法和文獻[14]的算法。

3.3 不同弱分類器數目對分類準確率的影響

在集成學習方法中，弱分類器數目T與最終強分類器性能有直接關系。為了驗證T對分類效果的影響，本文基于KDDCUP99、Image-Segmentation和Waveform三個數據集進行實驗。對于每個數據集，分別令T=1、2、4、7、11、16、22、29、37、46、56、67，進行12組實驗，結果如圖5所示。

從圖5可以看出，對于KDDCUP99數據集，當T<30時，分類準確率隨T的增大而提高，T=29時，分類準確率最高，達到99.51%;而當T>30時，分類準確率不再隨著T的增大而繼續增加，而是穩定在99.4%左右;對于image-seg-mentation數據集，當T從1增大到16時，其分類準確率不斷上升，從86.62%提高到94.62%。當T>16之后，準確率不再隨著T的增大而提高，而是穩定在94.45%左右;對于wavetorm數據集，當T從1增大到37時，其分類準確率不斷上升，從74.74%上升至86.07%，T>37之后，準確率穩定在86%左右。

上述結果表明，雖然集成學習方法都是通過訓練多個弱分類器來提高強分類器的泛化能力，但不表示弱分類器越多效果越好。當弱分類器超過一定數目時，準確率將不再繼續提升，甚至有可能下降，這也表示在弱分類器訓練過程中極有可能產生冗余分類器，這些冗余弱分類器不僅不能令強分類器性能得到提升，反而會使強分類器性能下降，進而影響分類速度。因此，選擇性集成是有必要的。

3.4 基于層次聚類的選擇性集成效果分析

為驗證本文提出的基于層次聚類的選擇性集成方法，分別對3個數據集在T=10、20、30、40、50、60、70的情況下進行實驗。

表2、表3和表4分別顯示了KDDCUP99、Image-Seg-mentation和Waveform三個數據集在選擇性集成前后的分類效果對比。從表中可以看出，由不同數目弱分類器組合成的強分類器，在經過選擇性集成后都可以減少弱分類器數目，達到相同甚至更優的分類性能。例如，對于KDD-CUP99數據集，在T=10的條件下，選擇性集成前分類準確率為99.25%，而δ=0.85和δ=0.9條件下的選擇性集成分別將弱分類器數目減至7個和8個，分類準確率分別達到了99.26%和99.32%;對于Image-Segmentation數據集，在T=20的條件下，選擇性集成前分類準確率為93.38%，而在δ =0.8、0.85和0.9的條件下，選擇性集成可以將弱分類器數目減至12、14和16個，分類準確率分別達到93 .42%、93.90%和93.38%;對于Waveform數據集，在T=60的條件下，選擇性集成前分類準確率為86.4%，而在δ= 0.9的條件下，選擇性集成可以將弱分類器數目減至43個，達到86.6%的準確率。以上數據表明，本文提出的基于層次聚類的選擇性集成方法可以在保證準確率的前提下，選取盡可能少的弱分類器組合成強分類器，從而提升分類效率。

此外，不同δ值得到的選擇性集成結果也不同，δ越大得到的弱分類器越多。由于選擇性集成既要剔除冗余的弱分類器，又要保留差異性較大的弱分類器，即在使用盡可能少的弱分類器同時要達到最為理想的分類性能，因此δ的選取尤為重要。若δ值過大，可能導致存在冗余的弱分類器沒有被剔除;若δ過小，則會導致過多弱分類器被剔除，使得剩余的弱分類器之間互補性不足，達不到最優性能。如表3所示，在T=30的條件下，選擇性集成前的分類準確率為94.19%;當δ=0.8時，選擇性集成后得到的弱分類器數目為17，準確率為93.76%，小于94.19%;當δ=0.85時，選擇性集成后得到的弱分類器數目為20，準確率為94.48%，大于94.19%;而當δ=0.9時，選擇性集成后得到的弱分類器數目為23，準確率為94.33%，小于94.48%。因此，本實驗中，δ =0.85時分類性能達到最優。

3.5 不同集成方法分類效果對比

本文同時基于上述3個數據集使用其它集成學習方法Bagging、AdaBoost和Random Forest進行分類實驗，實驗中所使用的弱分類器數目T=30，本文所提方案中令δ= 0.85，各方案分類結果如表5所示。通過表中數據對比可知，本文所提方法在分類準確率上略優于其它3種集成學習方法。但本文方案經過選擇性集成后將弱分類器數目減少至23個，提高了強分類器的分類效率，減少了計算開銷。因此，本文所提方案在準確率和效率上都優于Bag-glng、AdaBoost和Random Forest。

4 結語

為提高AdaBoost算法的分類準確率和效率，本文首先提出改進樣本權值更新方式的AdaBoost算法，在一定程度上提高了分類準確率;其次，利用基于層次聚類和相似度的選擇性集成方法對弱分類器進行篩選，得到一個弱分類器子集，并組合成強分類器。與其它集成學習方法相比，本文所提方法不僅提高了分類速度，而且保證了相同甚至更高的分類準確率。然而，與其它集成方法一樣，弱分類器訓練階段的耗時問題仍然存在。另外，本文在參數選取方面，只能通過多次實驗得出最佳參數。因此，提升弱分類器訓練階段效率、優化參數選取方式是今后的研究重點。

參考文獻

[1]BUCZAK A L， GUVEN E. A survey of data mining and machine learn-ing methods for cyber security intrusion detection[J] . IEEE Communi-cations Survevs & Tutorials . 2017. 18（ 2） ： 1153-1176.

[2]OZA N C.Online ensemble learning[C].Seventeenth National Confer-ence on Artificial Intelligence and Twelfth Conference on InnovativeApplications of Artificial Intelligence， July 30- August 3，2000，Austin， Texas， Usa. DBLP， 2000： 1109.

[3]JIANG F，SUI Y，CAO C.An incremental decision tree algorithmhased on rough sets and its application in intrusion detection[J].Arti-ficial Intelligence Review， 2013， 40（4）：517-530.

[4]SIMON H. Neural network：a comprehensive foundation [M]. NeuralNetworks：A Comprehensive Foundation. Prentice Hall PTR， 1994：71-80.

[5]YANG Q， FU H， ZHU T.An optimization method for parameters ofsvm in network intrusion detection system [C]. International Confer-ence on Distributed Computing in Sensor Systems. IEEE， 2016：136-142.

[6]WANG Y. SHEN Y， ZHANC G.Research on intrusion detection mod-el using ensemble learning methods[C] In IEEE International Con-ference on Soft，vare Engineering and Service Science， 2017： 422-425.

[7]BREIMAN L Bagging predictors [J]. Machine Learning， 1996， 24（ 2）：123-140.

[8]SCHAPIRE R， FREUND Y.Boosting： foundations and algorithms[J].Kvbernetes， 2012， 42（1）：164 -166.

[9]BIAU G，SCORNET E.A random forest guided tour[Jl. Test， 2016，25（2）：1-31.

[10] 曹瑩，苗啟廣，劉家辰，等.AdaBoost算法研究進展與展望[J].自動化學報，2013，39（6）：745-758.

[11] 楊曉元，胡志鵬，魏立線.分級結構Adaboost算法在無線傳感器網絡入侵檢測中的應用研究[J].傳感技術學報，2012. 25（8）：1159-1165.

[12]張子祥，陳優廣.基于樣本噪聲檢測的AdaBoost算法改進[J].計算機系統應用，2017（ 12）：186-190.

[13] 李文輝，倪洪印，一種改進的Adaboost訓練算法[J].吉林大學學報（理學版），2011（3）：498-504.

[14]董超，周剛，劉玉嬌，等.基于改進的Adaboost算法在網絡入侵檢測中的應用[J].四川大學學報（自然科學版），2015， 52（6）：568-574.

[15]ZHOU Z H， WU J，TANG W. Ensembling neural net，vorks： manvcould be better than all[C].Artificial Intelligence， 2002.

[16] 張春霞，張講社.選擇性集成學習算法綜述[J]計算機學報，2011. 34（8）：1399-1410.

[17]CHEN T.A selective ensemble classification method on microarravdata[J].Journal of Chemical& Pharmaceutical Research， 2014（9）：851-859.

[18]謝元澄，楊靜宇.刪除最差基學習器來層次修剪Bagging集成[J].計算機研究與發展，2009，46（2）：261-267.

[19] 王忠民，張爽，賀炎.基于差異性聚類的選擇性集成人體行為識別模型[J].計算機科學，2018. 45（1）：307-312.

[20]ZHAO Y. KARYPIS G，FAYYAD U.Hierarchical clustering algo-rithms for document datasets[J].Data Mining& Knowledge Discov-ery， 2005， 10（2）： 141-168.

[21]惠飛，彭娜，景首才，等.基于凝聚層次的駕駛行為聚類與異常檢測方法[J].計算機工程，2018 .44（12）：196-201.

（責任編輯：杜能鋼）

基金項目：浙江省自然科學基金項目（ IY19F020039）;之江實驗室重大科研項目（2019DHOZXOI）

作者簡介：歐陽瀟琴（1993-），女，杭州電子科技大學通信工程學院碩士研究生，研究方向為傳感器網絡安全、計算機網絡安全;王秋華（1978-），女，博士，杭州電子科技大學網絡空間安全學院副教授，研究方向為傳感器網絡安全、計算機網絡安全、安全密鑰管理。