姜季春，馬 丹

（貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽550025）

0 引 言

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

1 調(diào)整AdaBoost算法

1.1 改進(jìn)C4.5決策樹

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

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

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

分裂后的信息增益為

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

定義中的變量p、pi和ni，用來表示樣本數(shù)量。改進(jìn)C4.5決策樹，即是將這3個(gè)變量重新定義為對(duì)應(yīng)樣本的權(quán)值之和。這樣的調(diào)整使得在迭代分類模型的過程中僅需修改訓(xùn)練樣本權(quán)重，從而避免了繁瑣的重復(fù)抽樣，降低了算法的實(shí)現(xiàn)難度。

1.2 調(diào)整后的AdaBoost算法過程描述

給出訓(xùn)練集、樣本個(gè)數(shù)、訓(xùn)練次數(shù)和改進(jìn)的C4.5決策樹算法。調(diào)整后的AdaBoost算法訓(xùn)練過程描述如下：

（1）設(shè)初值：ωj（1）＝1／p，其中ωj（i）描述第i次迭代中第j個(gè)樣本的權(quán)重。

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

1）使用C4.5決策樹改進(jìn)算法處理加權(quán)訓(xùn)練集T，獲得單個(gè)分類器Ci。

2）計(jì)算Ci的分類誤差ε（i）

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

exit

endif

4）計(jì)算每一條正確分類的樣本權(quán)重

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

end for

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

（1）設(shè)置所有類權(quán)重為0。

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

1）計(jì)算單分類器Ci的投票權(quán)重

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

3）累加ω（Ci）得到類c的權(quán)重ω（C）。

end for

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

以上為調(diào)整后的AdaBoost算法的過程描述。總的來說就是利用修改后的C4.5決策樹算法直接處理帶權(quán)樣本，再根據(jù)分類結(jié)果對(duì)樣本權(quán)重進(jìn)行調(diào)整。訓(xùn)練過程的每一次迭代都要降低正確分類樣本的權(quán)重，并且在后繼迭代中著重處理分類困難的訓(xùn)練樣本。根據(jù)對(duì)每條訓(xùn)練樣本分類難度的評(píng)估值，構(gòu)造一組互補(bǔ)型的單分類器。對(duì)待分類樣本的類別預(yù)測(cè)則是使用加權(quán)投票的方式進(jìn)行判別。

2 多分類器動(dòng)態(tài)集成算法AdaBoost.MDS

2.1 算法的設(shè)計(jì)思想

AdaBoost算法的缺點(diǎn)在于一旦得到分類模型，對(duì)于所有待分類的目標(biāo)樣本均使用同一組固定的單分類器序列進(jìn)行檢測(cè)。這種以靜態(tài)組合來集成單分類器的方式，在很大程度上影響了模型對(duì)待分類樣本分類的準(zhǔn)確率。為了彌補(bǔ)AdaBoost算法的不足，考慮將調(diào)整后的AdaBoost算法和動(dòng)態(tài)選擇 （DS）相結(jié)合，研究一種改進(jìn)的多分類器動(dòng)態(tài)集成算法。該算法通過比較待分類樣本和訓(xùn)練集之間決策屬性的相似程度，從固定的分類模型中動(dòng)態(tài)選擇出部分單分類器組成當(dāng)前待分類樣本的識(shí)別模型。

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

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

圖1 AdaBoost改進(jìn)算法一次迭代生成的決策樹

圖2 有效決策屬性矩陣

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

根據(jù)Fj（x′j，tij）得到屬性相關(guān)度定義如下

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

2.2 AdaBoost.MDS算法的過程描述

AdaBoost.MDI算法分為生成分類模型和預(yù)測(cè)結(jié)果兩個(gè)階段，其輸入條件和上一章中AdaBoost改進(jìn)算法一致。AdaBoost.MDI算法迭代分類模型的過程描述如下：

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

2）由Ci得到Bmn（i）。

3）計(jì)算Ci的分類誤差ε（i）

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

exit

endif

5）計(jì)算每一條正確分類的樣本的權(quán)重

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

endfor

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

（1）動(dòng)態(tài)選擇f 個(gè)單分類器構(gòu)建識(shí)別模型，f 為分類器的個(gè)數(shù)閾值。

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

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

計(jì)算相關(guān)度C（X，Ti）。

endfor

4）模糊綜合評(píng)價(jià)法：模糊綜合評(píng)價(jià)法是一種基于模糊數(shù)學(xué)的綜合評(píng)價(jià)方法。該綜合評(píng)價(jià)法根據(jù)模糊數(shù)學(xué)的隸屬度理論把定性評(píng)價(jià)轉(zhuǎn)化為定量評(píng)價(jià)，即用模糊數(shù)學(xué)對(duì)受到多種因素制約的事物或?qū)ο笞龀鲆粋€(gè)總體的評(píng)價(jià)。它具有結(jié)果清晰，系統(tǒng)性強(qiáng)的特點(diǎn)，能較好地解決模糊的、難以量化的問題，適合各種非確定性問題的解決。該方法可分為單層和多層次模糊綜合評(píng)判[7]。

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

（2）對(duì)每個(gè)類的權(quán)值賦0。

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

1）計(jì)算

得到預(yù)測(cè)類別c。

2）累加ω（Ci）得到類c的權(quán)重ω（C）。

endfor

3 實(shí)驗(yàn)結(jié)果分析

AdaBoost.MDS算法是在調(diào)整后的AdaBoost算法基礎(chǔ)上進(jìn)行改進(jìn)的。為了更好地分析AdaBoost.MDS算法的分類效果，先將調(diào)整后的AdaBoost算法與幾種常用分類算法的實(shí)驗(yàn)結(jié)果作比較，再分析AdaBoost.MDS 算法的分類性能。

3.1 實(shí)驗(yàn)1對(duì)比調(diào)整后的AdaBoost算法性能

實(shí)驗(yàn)使用UCI（University of California Irvine）機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的數(shù)據(jù)集驗(yàn)證分類算法的性能。經(jīng)過預(yù)處理步驟之后，每條樣本選取20個(gè)決策屬性和1個(gè)類標(biāo)號(hào)屬性。從數(shù)據(jù)集中選取部分樣本作為訓(xùn)練集用來生成分類模型，余下的樣本可作為測(cè)試集以預(yù)測(cè)模型的性能。實(shí)驗(yàn)1 中，先將訓(xùn)練集劃分比例設(shè)置為60%。常用的分類學(xué)習(xí)算法可直接從weka中調(diào)用。使用MyEclipse和weka平臺(tái)實(shí)現(xiàn)改進(jìn)算法的編寫，其參數(shù)采用weka中的默認(rèn)設(shè)置，并在平臺(tái)中進(jìn)行實(shí)驗(yàn)數(shù)據(jù)處理和算法分類性能的測(cè)試。7 種分類算法在該訓(xùn)練集中建模并在測(cè)試集上進(jìn)行預(yù)測(cè)，得到的實(shí)驗(yàn)結(jié)果見表1。

表1 7種分類算法實(shí)驗(yàn)結(jié)果對(duì)比

由表1可見，Bagging、AdaBoost、調(diào)整后的AdaBoost 3種集成算法的分類錯(cuò)誤率和運(yùn)行時(shí)間均低于其它4種單分類算法，并且調(diào)整后的AdaBoost算法所得模型的分類錯(cuò)誤率最低，耗時(shí)最少。

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

圖3 3種集成分類算法的實(shí)驗(yàn)結(jié)果對(duì)比

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

綜合二項(xiàng)實(shí)驗(yàn)結(jié)果來看，相較于單分類算法而言，集成分類算法的分類錯(cuò)誤率更低。和流行的單分類算法、集成分類算法相比較，調(diào)整后的AdaBoost算法耗時(shí)短，分類精度更高。

3.2 實(shí)驗(yàn)2AdaBoost.MDS算法性能分析

為了更好地對(duì)比實(shí)驗(yàn)結(jié)果，AdaBoost.MDS算法性能分析使用的數(shù)據(jù)集、實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)1相同。實(shí)驗(yàn)仍然按照20%、40%、60%、80%4種比例從數(shù)據(jù)集中抽取所需的訓(xùn)練集，得到training sets 1、training sets 2、training sets 3和training sets 4。分類集成算法AdaBoost、調(diào)整后的AdaBoost和動(dòng)態(tài)集成算法AdaBoost.MDS在4個(gè)訓(xùn)練集中各自生成分類模型。每個(gè)分類模型均在4種劃分比例的數(shù)據(jù)集中經(jīng)過多次預(yù)測(cè)，得到平均分類準(zhǔn)確率見表2。

表2 AdaBoost.MDS算法實(shí)驗(yàn)結(jié)果對(duì)比／%

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

圖4 AdaBoost算法在不同樣本條件下的分類準(zhǔn)確率

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

圖5 調(diào)整后的AdaBoost算法在不同樣本條件下的分類準(zhǔn)確率

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

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

4 結(jié)束語

本文通過改進(jìn)調(diào)整后的AdaBoost算法，研究了一種多分類器動(dòng)態(tài)集成算法AdaBoost.MDS。算法中引入屬性相關(guān)度的定義以評(píng)價(jià)待分類樣本和訓(xùn)練集之間特征的相似程度，實(shí)現(xiàn)從待集成的一組固定序列的單分類器中動(dòng)態(tài)選擇出部分與當(dāng)前待分類樣本特征相似的單分類器組成識(shí)別模型。實(shí)驗(yàn)結(jié)果表明，基于調(diào)整后的AdaBoost算法和動(dòng)態(tài)選擇 （DS）相結(jié)合的改進(jìn)算法AdaBoost.MDS 在分類準(zhǔn)確率、運(yùn)行時(shí)間、泛化能力幾項(xiàng)性能指標(biāo)上均有較大的優(yōu)勢(shì)。

［1］ZHANG Xin.Classification－based data integration method［D］.Guangdong：Computer College of Guangdong University of Technology，2013 （in Chinese）. ［張?chǎng)?基于分類的數(shù)據(jù)集成方法 ［D］.廣東：廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，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）.［關(guān)菁華，劉大有，賈海洋.自適應(yīng)多分類器集成學(xué)習(xí)算法 ［J］.計(jì)算機(jī)研究與發(fā)展，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）.［陳冰，張化祥.集成學(xué)習(xí)的多分類器動(dòng)態(tài)組合方法 ［J］.計(jì)算機(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］.計(jì)算機(jī)工程與應(yīng)用，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）.［郝紅衛(wèi)，王志彬，殷續(xù)成，等.分類器的動(dòng)態(tài)選擇與循環(huán)集成方法 ［J］.自動(dòng)化學(xué)報(bào)，2011，37（11）：1290－1295.］

［9］WANG Bing.The mathematical analysis of AdaBoost algorethm ［J］.Software，2014 （3）：96－97 （in Chinese）. ［王兵.AdaBoost分類算法的數(shù)學(xué)分析［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）. ［陳安，陳寧，周龍?bào)J，等.數(shù)據(jù)挖掘技術(shù)及應(yīng)用 ［M］.北京：科學(xué)出版社，2006.］