基于改進權(quán)值更新和選擇性集成的AdaBoost算法

歐陽瀟琴 王秋華

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

關(guān)鍵詞：入侵檢測;集成學習;AdaBoost;權(quán)值更新;選擇性集成

DOI： 10. 11907/rjdk.191736

開放科學（資源服務(wù)）標識碼（OSID）：

中圖分類號：TP312

文獻標識碼：A

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

0 引言

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

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

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

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

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

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

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

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

1 AdaBoost算法及分析

1.1 AdaBoost算法

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

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

1.2 AdaBoost算法分析

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

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

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

2 AdaBoost算法改進

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

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

3 性能仿真與分析

3.1 實驗數(shù)據(jù)集

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

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

3.2 分類準確率

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻

[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] 楊曉元，胡志鵬，魏立線.分級結(jié)構(gòu)Adaboost算法在無線傳感器網(wǎng)絡(luò)入侵檢測中的應(yīng)用研究[J].傳感技術(shù)學報，2012. 25（8）：1159-1165.

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

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

[14]董超，周剛，劉玉嬌，等.基于改進的Adaboost算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[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].計算機研究與發(fā)展，2009，46（2）：261-267.

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

[20]ZHAO Y. KARYPIS G，F(xiàn)AYYAD 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-），女，杭州電子科技大學通信工程學院碩士研究生，研究方向為傳感器網(wǎng)絡(luò)安全、計算機網(wǎng)絡(luò)安全;王秋華（1978-），女，博士，杭州電子科技大學網(wǎng)絡(luò)空間安全學院副教授，研究方向為傳感器網(wǎng)絡(luò)安全、計算機網(wǎng)絡(luò)安全、安全密鑰管理。