基于AdaBoost改進的多分類器動態集成算法

姜季春，馬 丹

（貴州大學 計算機科學與技術學院，貴州 貴陽550025）

0 引 言

根據集成過程中是否對待分類樣本的具體特征進行自適應選取，多分類器集成方法被分為靜態集成和動態集成兩種類型［1－3］。和靜態集成方法相比，動態集成方法可以在分類模型預測的過程中根據目標樣本的特征和識別性能，實時地組合一組單分類器或調整其權重［4］。根據分類器在執行預測時的兩種變化方式，得到應用于多分類器集成技術的動態集成方法有：動態選擇 （dynamic selection）、動態投票 （dynamic voting）、以及結合動態選擇和動態投票兩種方法的混合集成方法［5，6］。這幾種動態集成方法都可以有效提高集成分類的性能。目前一些實驗也驗證了動態集成分類器具有更好的針對性、靈活性和泛化能力，因此多分類器的動態集成無疑是進一步研究分類器集成技術的熱點［7，8］。為了在應用領域中獲得更好的分類性能，本文對當前最為流行的一種多分類器集成算法AdaBoost進行調整，在此基礎上引入動態選擇 （DS）的思想，得到一種改進的多分類器動態集成算法，并對比驗證了該算法的分類效果。

1 調整AdaBoost算法

1.1 改進C4.5決策樹

多分類器動態集成算法AdaBoost.MDS 是基于Ada－Boost算法提出改進的，改進的關鍵在于如何計算待分類樣本和訓練集之間決策屬性的相關度。為了利用影響權重量化決策屬性對于迭代生成分類模型的重要程度，進而引入屬性相關度的計算模型，于是考慮以C4.5 決策樹作為AdaBoost算法的基礎學習方法，用于構造集成模型中的單分類器。樣本權重在算法中描述該樣本被抽取的概率，反映當前分類模型對其進行處理的難易程度。C4.5決策樹中產生的殘缺值采用分數實例的觀念進行處理，對算法稍加調整即可直接處理帶有權值的樣本［9］。修改C4.5決策樹算法，實際上是對信息熵和信息增益的公式定義進行調整。

定義1［10］假設訓練集T 中包含p 個樣本，這些樣本分別屬于m 個類，pi為第i 個類在T 中出現的樣本個數，T 的信息熵為

假設屬性A 把集合T 劃分成V 個子集 ｛T1，T2，…，TV｝，其中Ti所包含的樣本數為ni，劃分后的熵為

分裂后的信息增益為

信息增益率定義為信息增益與初始信息量的比值

定義中的變量p、pi和ni，用來表示樣本數量。改進C4.5決策樹，即是將這3個變量重新定義為對應樣本的權值之和。這樣的調整使得在迭代分類模型的過程中僅需修改訓練樣本權重，從而避免了繁瑣的重復抽樣，降低了算法的實現難度。

1.2 調整后的AdaBoost算法過程描述

給出訓練集、樣本個數、訓練次數和改進的C4.5決策樹算法。調整后的AdaBoost算法訓練過程描述如下：

（1）設初值：ωj（1）＝1／p，其中ωj（i）描述第i次迭代中第j個樣本的權重。

（2）for i＝1，2，…，k do

1）使用C4.5決策樹改進算法處理加權訓練集T，獲得單個分類器Ci。

2）計算Ci的分類誤差ε（i）

3）if（ε（i）＝＝0） （ε（i）≥0.5）then

exit

endif

4）計算每一條正確分類的樣本權重

5）將每條樣本的權值乘以原來的權值總和，再除以新權值總和。

end for

訓練過程結束后得到分類模型，即一組固定的決策樹序列 ｛C1，C2，…，Ct｝，其中 （t＜＝k）。利用訓練過程產生的決策樹組就可以預測待分類樣本的所屬類別。調整后的AdaBoost算法決策過程描述如下：

（1）設置所有類權重為0。

（2）for i＝1，2，…，t do

1）計算單分類器Ci的投票權重

2）得到待分類樣本X 的類別c。

3）累加ω（Ci）得到類c的權重ω（C）。

end for

（3）返回ω（C）值最大的類。

以上為調整后的AdaBoost算法的過程描述。總的來說就是利用修改后的C4.5決策樹算法直接處理帶權樣本，再根據分類結果對樣本權重進行調整。訓練過程的每一次迭代都要降低正確分類樣本的權重，并且在后繼迭代中著重處理分類困難的訓練樣本。根據對每條訓練樣本分類難度的評估值，構造一組互補型的單分類器。對待分類樣本的類別預測則是使用加權投票的方式進行判別。

2 多分類器動態集成算法AdaBoost.MDS

2.1 算法的設計思想

AdaBoost算法的缺點在于一旦得到分類模型，對于所有待分類的目標樣本均使用同一組固定的單分類器序列進行檢測。這種以靜態組合來集成單分類器的方式，在很大程度上影響了模型對待分類樣本分類的準確率。為了彌補AdaBoost算法的不足，考慮將調整后的AdaBoost算法和動態選擇 （DS）相結合，研究一種改進的多分類器動態集成算法。該算法通過比較待分類樣本和訓練集之間決策屬性的相似程度，從固定的分類模型中動態選擇出部分單分類器組成當前待分類樣本的識別模型。

AdaBoost.MDS算法設計的重點在于如何引入待分類樣本和訓練集之間決策屬性的相關度。圖1為AdaBoost改進算法一次迭代得到的決策樹。定義決策樹中間結點的存儲結構為 （attribute，w，p），葉結點存儲結構為 （category，w，p），并設定決策屬性attribute、目標類別category、影響權重w 和雙親結點的指針p。設w＝d＋1－l，其中d 為樹的深度，l為結點所在層數。定義影響權重w 以表示決策樹中不同層次的決策屬性對于迭代生成分類模型的重要程度，且其重要性按層次逐漸下降。

按照從左到右的順序從根開始逐層遍歷決策樹的決策屬性，得到有效決策屬性序列 ｛attribute1，attribute2，…，attribute n｝。定義訓練集有效決策屬性值的二維矩陣Bmn。以矩陣形式來存儲所有的決策屬性序列，從而保證有效決策屬性序列的排列順序和Bmn的列次序一致。如圖2所示，tm（m∈N ∣1≤m≤k）表示訓練集中的一條樣本，其中k表示樣本數量，n表示有效決策屬性序列包含的值的個數。

圖1 AdaBoost改進算法一次迭代生成的決策樹

圖2 有效決策屬性矩陣

預測時，按Bmn的列順序排列待分類樣本X（x1，x2，…，xs，c）的決策屬性。重新排列待分類樣本后得到X′（x1′，x2′，…，xn′），其中xj′表示待分類樣本X 的決策屬性按照Bmn的列順序排列之后的第j 個屬性值，而tij表示Bmn第i行第j 列的屬性值。在此基礎上，定義Fj（xj′，tij）統計有效決策屬性矩陣Bmn第j 列中與X′的第j個屬性值xj′相等的樣本數目。函數定義如下

根據Fj（x′j，tij）得到屬性相關度定義如下

由上述定義可知，變量C（X，T）的取值反映了待分類樣本與訓練集決策屬性特征之間的關系。C 的值越大表明X 與決策屬性的特征分布越接近，即當前單分類器預測的類別與期望的分類結果越接近。

2.2 AdaBoost.MDS算法的過程描述

AdaBoost.MDI算法分為生成分類模型和預測結果兩個階段，其輸入條件和上一章中AdaBoost改進算法一致。AdaBoost.MDI算法迭代分類模型的過程描述如下：

（1）設初值：ωj（1）＝1／k。（2）for i＝1，2，…，ndo 1）使用修改后的C4.5決策樹訓練單分類器Ci。

2）由Ci得到Bmn（i）。

3）計算Ci的分類誤差ε（i）

4）if（ε（i）＝＝0） （ε（i）≥0.5）then

exit

endif

5）計算每一條正確分類的樣本的權重

6）將每條樣本的權值乘以原來的權值總和，再除以新權值總和。

endfor

訓練過程結束后得到一組固定的決策樹序列 ｛C1，C2，…，Ct｝和訓練集有效決策屬性矩陣序列 ｛Bmn（1），Bmn（2），…，Bmn（t）｝。預測之前需給定待分類樣本和單分類器的個數閾值，預測時利用訓練過程輸出的結果得到待分類樣本的類別。AdaBoost.MDI算法預測待分類樣本的過程描述如下：

（1）動態選擇f 個單分類器構建識別模型，f 為分類器的個數閾值。

1）根據矩陣Bmn的列次序排列待分類樣本X（x1，x2，…，xt，c），得到X′（x1′，x2′，…，xt′）。

2）for i＝1，2，…，t do

計算相關度C（X，Ti）。

endfor

4）模糊綜合評價法：模糊綜合評價法是一種基于模糊數學的綜合評價方法。該綜合評價法根據模糊數學的隸屬度理論把定性評價轉化為定量評價，即用模糊數學對受到多種因素制約的事物或對象做出一個總體的評價。它具有結果清晰，系統性強的特點，能較好地解決模糊的、難以量化的問題，適合各種非確定性問題的解決。該方法可分為單層和多層次模糊綜合評判[7]。

3）根據C（X，Ti）的計算值，在迭代分類模型之后輸出的一組分類器中從大到小地選擇出f 個單分類器，組成當前待分類樣本的識別模型 ｛C′1，C′2，…，C′f｝。

（2）對每個類的權值賦0。

（3）for i＝1，2，…，fdo

1）計算

得到預測類別c。

2）累加ω（Ci）得到類c的權重ω（C）。

endfor

3 實驗結果分析

AdaBoost.MDS算法是在調整后的AdaBoost算法基礎上進行改進的。為了更好地分析AdaBoost.MDS算法的分類效果，先將調整后的AdaBoost算法與幾種常用分類算法的實驗結果作比較，再分析AdaBoost.MDS 算法的分類性能。

3.1 實驗1對比調整后的AdaBoost算法性能

實驗使用UCI（University of California Irvine）機器學習數據庫中的數據集驗證分類算法的性能。經過預處理步驟之后，每條樣本選取20個決策屬性和1個類標號屬性。從數據集中選取部分樣本作為訓練集用來生成分類模型，余下的樣本可作為測試集以預測模型的性能。實驗1 中，先將訓練集劃分比例設置為60%。常用的分類學習算法可直接從weka中調用。使用MyEclipse和weka平臺實現改進算法的編寫，其參數采用weka中的默認設置，并在平臺中進行實驗數據處理和算法分類性能的測試。7 種分類算法在該訓練集中建模并在測試集上進行預測，得到的實驗結果見表1。

表1 7種分類算法實驗結果對比

由表1可見，Bagging、AdaBoost、調整后的AdaBoost 3種集成算法的分類錯誤率和運行時間均低于其它4種單分類算法，并且調整后的AdaBoost算法所得模型的分類錯誤率最低，耗時最少。

采用交叉測試法將訓練集的比例按照20%、40%、60%和80%進行劃分，每種算法在4種比例的訓練集中均生成一個分類模型。使用多組待分類樣本，分別對3種算法的分類模型進行測試。預測后得到Bagging、AdaBoost、調整后的AdaBoost這3種集成算法在4種比例訓練集中的分類錯誤率如圖3所示。

圖3 3種集成分類算法的實驗結果對比

由圖3可見，和兩種流行的分類集成算法相比，在不同劃分比例的訓練集中，調整后的AdaBoost算法取得的分類錯誤率最低。并且隨著訓練樣本數據規模的增加，調整后的AdaBoost算法的分類錯誤率下降幅度最小。

綜合二項實驗結果來看，相較于單分類算法而言，集成分類算法的分類錯誤率更低。和流行的單分類算法、集成分類算法相比較，調整后的AdaBoost算法耗時短，分類精度更高。

3.2 實驗2AdaBoost.MDS算法性能分析

為了更好地對比實驗結果，AdaBoost.MDS算法性能分析使用的數據集、實驗環境與實驗1相同。實驗仍然按照20%、40%、60%、80%4種比例從數據集中抽取所需的訓練集，得到training sets 1、training sets 2、training sets 3和training sets 4。分類集成算法AdaBoost、調整后的AdaBoost和動態集成算法AdaBoost.MDS在4個訓練集中各自生成分類模型。每個分類模型均在4種劃分比例的數據集中經過多次預測，得到平均分類準確率見表2。

表2 AdaBoost.MDS算法實驗結果對比／%

在上述實驗的基礎上改變樣本決策屬性的數量，以進一步測試算法的準確率和泛化能力。3 種集成算法在不同的樣本條件下重新生成分類模型，預測后得到模型的分類準確率如圖4、圖5、圖6所示，圖中X 軸表示訓練樣本決策屬性數量，Y 軸表示訓練樣本集合在數據集中的劃分比例，Z軸表示算法的分類準確率，圖中的曲面表示分類集成算法在不同劃分比例的訓練集和不同數量的樣本決策屬性下的分類結果。

圖4 AdaBoost算法在不同樣本條件下的分類準確率

對比圖4、圖5、圖6 可知，除了AdaBoost算法在訓練集劃分比例從20%增加到40%，且樣本的決策屬性數目較少時，其分類準確率有所下降以外，隨著有效范圍內樣本決策屬性的增加，3 種分類集成算法的識別模型在圖中其它結點處的分類準確率都呈現上升趨勢。

圖5 調整后的AdaBoost算法在不同樣本條件下的分類準確率

圖6 AdaBoost.MDS算法在不同樣本條件下的分類準確率

綜合分析以上實驗結果，可以發現不管和單分類器還是靜態集成分類算法相比，AdaBoost.MDS算法在4 種劃分比例的訓練集以及不同樣本決策屬性數量的條件下都取得了最高的分類準確率。并且隨著訓練集劃分比例和決策屬性數量的增加，AdaBoost.MDS算法所得模型的分類準確率上升幅度最小，說明該算法受抽取樣本的影響最小，算法的穩定性好，有效提高了分類精度和泛化能力。

4 結束語

本文通過改進調整后的AdaBoost算法，研究了一種多分類器動態集成算法AdaBoost.MDS。算法中引入屬性相關度的定義以評價待分類樣本和訓練集之間特征的相似程度，實現從待集成的一組固定序列的單分類器中動態選擇出部分與當前待分類樣本特征相似的單分類器組成識別模型。實驗結果表明，基于調整后的AdaBoost算法和動態選擇 （DS）相結合的改進算法AdaBoost.MDS 在分類準確率、運行時間、泛化能力幾項性能指標上均有較大的優勢。

［1］ZHANG Xin.Classification－based data integration method［D］.Guangdong：Computer College of Guangdong University of Technology，2013 （in Chinese）. ［張鑫.基于分類的數據集成方法 ［D］.廣東：廣東工業大學計算機學院，2013.］

［2］Chen L，Kamel MS.A generalized adaptive ensemble generation and aggregation approach for multiple classifier systems［J］.Pattern Recognition，2009，42 （5）：629－644.

［3］GUAN Jinghua，LIU Dayou，JIA Haiyang.An adaptive ensemble learning method of multiple classifiers ［J］.Journal of Computer Research and Development，2008，45 （Sl）：218－221 （in Chinese）.［關菁華，劉大有，賈海洋.自適應多分類器集成學習算法 ［J］.計算機研究與發展，2008，45 （Sl）：218－221.］

［4］Ko AHR，Sabourin R，Britto AS.From dynamic classifier selection to dynamic ensemble selection ［J］.Pattern Recognition，2008，41 （5）：1735－1748.

［5］Chen Bing，Zhang Huaxiang.An approach of multiple classifiers ensemble based on feature selection［C］／／Fifth International Conference on Fuzzy Systems and Knowledge Discovery，2008.

［6］CHEN Bing，ZHANG Huaxiang. Dyanmic combinatorial method of multiple classifiers on emsemble learning ［J］.Computer Engineering，2008，34 （24）：218－220 （in Chinese）.［陳冰，張化祥.集成學習的多分類器動態組合方法 ［J］.計算機工程，2008，34 （24）：218－220.］

［7］GUO Hongling，CHEN Xianyi.Method of selective multiple classifiers ensemble ［J］.Computer Engineering and Applications，2009，45 （13）：186－188 （in Chinese）.［郭紅玲，程顯毅.多分類器選擇集成方法 ［J］.計算機工程與應用，2009，45 （13）：186－188.］

［8］HAO Hongwei，WANG Zhibin，YIN Xucheng，et al.Dynamic selection and circulating combination for multiple classifiers systems［J］.Acta Automatica Sinica，2011，37 （11）：1290－1295 （in Chinese）.［郝紅衛，王志彬，殷續成，等.分類器的動態選擇與循環集成方法 ［J］.自動化學報，2011，37（11）：1290－1295.］

［9］WANG Bing.The mathematical analysis of AdaBoost algorethm ［J］.Software，2014 （3）：96－97 （in Chinese）. ［王兵.AdaBoost分類算法的數學分析［J］.軟件，2014 （3）：96－97.］

［10］CHEN An，CHEN Ning，ZHOU Longxiang，et al.Data mining technology and application ［M］.Beijing：Science Press，2006 （in Chinese）. ［陳安，陳寧，周龍驤，等.數據挖掘技術及應用 ［M］.北京：科學出版社，2006.］