翟夕陽(yáng)，王曉丹，雷 蕾，魏曉輝

(1.空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051; 2.解放軍第463醫(yī)院，沈陽(yáng) 110042)

基于多類指數(shù)損失函數(shù)逐步添加模型的改進(jìn)多分類AdaBoost算法

翟夕陽(yáng)1，王曉丹1*，雷 蕾1，魏曉輝2

(1.空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051; 2.解放軍第463醫(yī)院，沈陽(yáng) 110042)

(*通信作者電子郵箱afeu_wang@163.com)

多類指數(shù)損失函數(shù)逐步添加模型(SAMME)是一種多分類的AdaBoost算法，為進(jìn)一步提升SAMME算法的性能，針對(duì)使用加權(quán)概率和偽損失對(duì)算法的影響進(jìn)行研究，在此基礎(chǔ)上提出了一種基于基分類器對(duì)樣本有效鄰域分類的動(dòng)態(tài)加權(quán)AdaBoost算法SAMME.RD。首先，確定是否使用加權(quán)概率和偽損失;然后,求出待測(cè)樣本在訓(xùn)練集中的有效鄰域;最后,根據(jù)基分類器針對(duì)有效鄰域的分類結(jié)果確定基分類器的加權(quán)系數(shù)。使用UCI數(shù)據(jù)集進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明：使用真實(shí)的錯(cuò)誤率計(jì)算基分類器加權(quán)系數(shù)效果更好；在數(shù)據(jù)類別較少且分布平衡時(shí)，使用真實(shí)概率進(jìn)行基分類器篩選效果較好；在數(shù)據(jù)類別較多且分布不平衡時(shí)，使用加權(quán)概率進(jìn)行基分類器篩選效果較好。所提的SAMME.RD算法可以有效提高多分類AdaBoost算法的分類正確率。

集成學(xué)習(xí)；多分類；AdaBoost算法；多類指數(shù)損失函數(shù)逐步添加模型(SAMME)；動(dòng)態(tài)加權(quán)融合

0 引言

Boosting算法[1]是基于可能近似正確(Probably Approximately Correct, PAC)可學(xué)習(xí)性模型而提出的一種經(jīng)典集成算法。由于Boosting算法存在缺陷，很難應(yīng)用于實(shí)際問題，針對(duì)此問題Freund等[2]1995年提出了AdaBoost(Adaptive Boosting)算法。AdaBoost算法是最常用的一種Boosting算法的變形，更加面向?qū)嶋H，可以有效提升弱分類器的性能。

傳統(tǒng)的AdaBoost算法只能解決二分類問題，然而在實(shí)際應(yīng)用中要處理的問題經(jīng)常是多分類問題?；诖?需要把AdaBoost算法擴(kuò)展為多分類算法，現(xiàn)有的擴(kuò)展方法可以分為兩種：一種直接把AdaBoost算法擴(kuò)展為多分類算法，另一種使用多個(gè)二分類算法去解決多分類問題。傳統(tǒng)的多分類AdaBoost算法主要有AdaBoost.M1[3]、AdaBoost.M2[3]和AdaBoost.MH[4]。AdaBoost.M1是一種直接由AdaBoost算法擴(kuò)展而成的多分類算法，這種擴(kuò)展比較容易，但是它對(duì)基分類器的要求過高，它要求基分類器的分類正確率大于1/2，這對(duì)于多類的弱分類器而言是比較難以達(dá)到的條件，基分類器的獲取變得困難，可能導(dǎo)致基分類器數(shù)目不足，無法集成出足夠好的強(qiáng)分類器。AdaBoost.M2是在AdaBoost.M1的基礎(chǔ)上提出的一種多分類算法，它在算法中使用偽損失來代替錯(cuò)誤率作為選取基分類器的標(biāo)準(zhǔn)。它對(duì)基分類器的要求有所降低，只需要偽損失比1/2略高，而且由于使用偽損失使算法不僅關(guān)注錯(cuò)分樣本同時(shí)關(guān)注難分樣本。但是偽損失的計(jì)算比較復(fù)雜，算法的時(shí)間復(fù)雜度較高，同時(shí)由于使用偽損失造成的退化現(xiàn)象可能更為嚴(yán)重。AdaBoost.MH是一種典型的把多類問題轉(zhuǎn)換為二類問題處理的算法，由于多類問題轉(zhuǎn)變成了二類問題，基分類的獲取變得相對(duì)容易，但是算法的復(fù)雜度卻大大增加，尤其是在類別數(shù)較大時(shí)增加得更為明顯。

傳統(tǒng)的多分類AdaBoost算法存在時(shí)間復(fù)雜度高和獲取基分類器困難的問題。針對(duì)這些缺點(diǎn)，文獻(xiàn)[5]提出了一種改進(jìn)的從兩類直接擴(kuò)展為多類的AdaBoost算法——多類指數(shù)損失函數(shù)逐步添加模型(Stagewise Additive Modeling using a Multi-class Exponential loss function, SAMME)，通過擴(kuò)展算法的指數(shù)損失函數(shù)把對(duì)基分類器正確率的要求降低到1/K(K為類別數(shù))這就使得基分類的獲取變得相對(duì)容易。文獻(xiàn)[6]對(duì)此算法進(jìn)行了證明，并把它應(yīng)用于航空發(fā)動(dòng)機(jī)故障診斷之中。文獻(xiàn)[7]指出SAMME算法對(duì)基分類器的要求過低，容易使算法陷入退化。針對(duì)此問題，楊新武等[7]提出了一種基于弱分類器調(diào)整的SAMME.R算法，并且達(dá)到了不弱于AdaBoost.M1的效果。

AdaBoost算法已經(jīng)廣泛應(yīng)用于人臉識(shí)別[8-10]、目標(biāo)檢測(cè)[11]和網(wǎng)絡(luò)異常檢測(cè)[12]之中。SAMME算法解決了由二類算法擴(kuò)展而來的多類算法所存在的問題，使AdaBoost算法處理多類問題更加方便。為進(jìn)一步提升SAMME算法的性能，本文研究了使用加權(quán)錯(cuò)誤率和偽損失對(duì)算法性能的影響，并且提出了一種改進(jìn)的多分類算法——SAMME.RD(SAMMEwithResamplingandDynamicweighting)。首先確定是否使用加權(quán)的錯(cuò)誤率和偽損失，之后判斷是否需要求出待測(cè)樣本在測(cè)試集中的有效鄰域，不需要?jiǎng)t直接輸出分類結(jié)果，若需要?jiǎng)t求出有效鄰域，并使用基分類器對(duì)有效鄰域進(jìn)行分類，由此得出基分類器的加權(quán)系數(shù)，最后求出待測(cè)樣本的分類結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文提出的算法相比SAMME和SAMME.R算法，分類性能有所提高。

1 SAMME和SAMME.R

對(duì)于多類問題，要獲取分類正確率大于1/2的基分類器比較困難，針對(duì)此問題SAMME算法改變了傳統(tǒng)的AdaBoost算法的權(quán)值分配策略，令αt=ln(εt/(1-εt))+ln(k-1)來降低對(duì)基分類器分類正確率的要求。文獻(xiàn)[5]使用統(tǒng)計(jì)學(xué)的觀點(diǎn)證明了αt的合理性，但文獻(xiàn)[7]指出，SAMME算法對(duì)基分類器的要求過低可能會(huì)導(dǎo)致強(qiáng)分類器分類結(jié)果偏向于分類正確率較大的錯(cuò)誤類，為此文獻(xiàn)[7]提出了一種基于弱分類器調(diào)整的SAMME.R算法。

1.1SAMME

SAMME算法通過擴(kuò)展指數(shù)損失函數(shù)直接把二類的AdaBoost算法擴(kuò)展為多類，使分類器的要求得到降低，它的合理性也從統(tǒng)計(jì)學(xué)方面得到了證明。SAMME算法的流程與傳統(tǒng)的AdaBoost算法相似，具體如下：

步驟1 初始化權(quán)值:

步驟2 對(duì)于t=1,2,…,T，執(zhí)行以下1)～6)步：

1)依據(jù)權(quán)值wt，選擇訓(xùn)練樣本。

2)對(duì)樣本進(jìn)行分類識(shí)別ht:X→Y。

3)計(jì)算ht的偽錯(cuò)誤率：

4)置αt=ln(ξt/(1-ξt))+ln(k-1)。

5)計(jì)算新的樣本權(quán)重：

6)歸一化wt+1。

步驟3 最終強(qiáng)分類器為：

1.2SAMME.R

SAMME.R是在SAMME的基礎(chǔ)上改進(jìn)而來的，該算法為了解決SAMME算法對(duì)基分類器要求過弱的問題，對(duì)每次迭代訓(xùn)練出的弱分類器進(jìn)行檢驗(yàn)，判斷分類器對(duì)于數(shù)據(jù)分到正確類的概率是否大于分到其他任意錯(cuò)誤類的概率，如果滿足該條件則保留該基分類器，否則重新訓(xùn)練新的基分類器。SAMME.R算法的主要改進(jìn)在于通過篩選基分類器保證算法訓(xùn)練出的強(qiáng)分類器可以分類正確。

SAMME.R算法的主要改進(jìn)就是在步驟2的2)～3)之間加入了如下的篩選：

a)循環(huán)計(jì)算各類中，分到各類樣本的權(quán)值和：

對(duì)于j=1,2,…,K，有：

b)判斷各類中分類正確的樣本權(quán)值和是否大于等于分到其他各類的樣本的權(quán)值和：

γtkj[ht(xi)=j]≥?γtkj[ht(xi)≠j]

若滿足，則進(jìn)行下一步驟；若不滿足，則返回步驟2。

2 改進(jìn)的SAMME算法

2.1 錯(cuò)誤率和偽錯(cuò)誤率對(duì)算法影響

文獻(xiàn)[13]指出在AdaBoost算法進(jìn)行權(quán)值更新和基分類器加權(quán)系數(shù)計(jì)算時(shí)使用真實(shí)錯(cuò)誤率比加權(quán)錯(cuò)誤率效果更好，雖然偽錯(cuò)誤率在考慮分類是否正確的同時(shí)考慮了樣本的難分程度，但是隨著迭代次數(shù)的增加，難分樣本權(quán)重過大，會(huì)出現(xiàn)加權(quán)錯(cuò)誤率較小而真實(shí)錯(cuò)誤率較大的基分類器，在最后的加權(quán)融合中由于加權(quán)錯(cuò)誤率較小而權(quán)值較大，導(dǎo)致算法出現(xiàn)退化的現(xiàn)象，所以本文對(duì)SAMME和SAMME.R算法作出改進(jìn)，在算法中使用真實(shí)的錯(cuò)誤率，改進(jìn)后的SAMME命名為SAMME.RE，改進(jìn)后的SAMME.R命名為SAMME.RRE。

文獻(xiàn)[7]在分析中指出SAMME算法對(duì)基分類器的要求過低，給出了進(jìn)一步的要求，并從直觀上和理論上證明了所提要求的合理性。SAMME.R算法指出要循環(huán)計(jì)算各類中分到每類樣本的權(quán)值和，并且要求分到正確類的權(quán)值和大于分到任意錯(cuò)誤類的權(quán)值和。文獻(xiàn)[7]在進(jìn)行直觀和理論證明時(shí)指出，基分類器對(duì)每類數(shù)據(jù)分類時(shí)要求分到正確類的概率要大于分到任意錯(cuò)誤類的概率，而在SAMME.R中要求分到正確類的權(quán)值和大于分到任意錯(cuò)誤類的權(quán)值和，降低了算法的要求。隨著迭代次數(shù)的增加，部分難分?jǐn)?shù)據(jù)的權(quán)值迅速增加，如果只要求分類正確的權(quán)值大于分到其他任意類的權(quán)值，可能分類器的真實(shí)正確率還達(dá)不到大于隨機(jī)的要求，這就會(huì)導(dǎo)致隨著迭代次數(shù)的增加，強(qiáng)分類器陷入退化的現(xiàn)象。但是如果要求分到正確類的概率大于分到其他任意類的概率又會(huì)導(dǎo)致對(duì)基分類器要求較高，對(duì)于有些分布不平衡的數(shù)據(jù)難以獲取足夠的基分類器。從直觀上可以看出，在數(shù)據(jù)類別較少、數(shù)據(jù)分布較平衡時(shí)，基分類器獲取比較容易，使用真實(shí)的概率對(duì)基分類器進(jìn)行篩選效果更好，在數(shù)據(jù)類別較多、數(shù)據(jù)分布不平衡時(shí)，基分類器獲取比較困難，使用加權(quán)和對(duì)基分類器進(jìn)行篩選或不篩選效果更好。為了能夠更好地使用SAMME.R算法，本文針對(duì)使用加權(quán)概率或真實(shí)概率對(duì)算法的影響進(jìn)行實(shí)驗(yàn)研究。把使用真實(shí)概率進(jìn)行基分類器篩選的算法命名為SAMME.R1，在SAMME.R1的基礎(chǔ)上又使用真實(shí)分類錯(cuò)誤率的算法命名為SAMME.R2。

2.2 動(dòng)態(tài)加權(quán)SAMME.R算法

動(dòng)態(tài)集成方法根據(jù)目標(biāo)樣本的特征和識(shí)別性能，動(dòng)態(tài)地組合基分類器或調(diào)整基分類器權(quán)重[14]。根據(jù)動(dòng)態(tài)集成方法在作出預(yù)測(cè)時(shí)的選擇和加權(quán)方式，可以把動(dòng)態(tài)集成方法分為動(dòng)態(tài)選擇、動(dòng)態(tài)投票和動(dòng)態(tài)選擇與動(dòng)態(tài)投票混合使用的三種類型。動(dòng)態(tài)集成方法可以有效地提高集成分類的性能，為進(jìn)一步提升SAMME.R算法的分類性能，本節(jié)在2.1節(jié)的基礎(chǔ)之上，提出一種動(dòng)態(tài)投票的改進(jìn)SAMME.R算法，改變SAMME.R預(yù)測(cè)時(shí)的加權(quán)方式。傳統(tǒng)的AdaBoost算法對(duì)待測(cè)樣本進(jìn)行預(yù)測(cè)時(shí)各個(gè)分類器的加權(quán)系數(shù)是固定不變的，但是通過分析可以知道基分類器對(duì)不同的待測(cè)樣本的分類能力是不一樣的，這是因?yàn)榛诸惼魇褂貌煌挠?xùn)練集訓(xùn)練而來，它們對(duì)分布在不同區(qū)域的樣本分類能力是不一樣的。如果在預(yù)測(cè)時(shí)使用相同的加權(quán)系數(shù)，預(yù)測(cè)結(jié)果的準(zhǔn)確性將會(huì)受到一定的影響，所以為了進(jìn)一步提升算法的預(yù)測(cè)性能，本文提出一種動(dòng)態(tài)加權(quán)投票的改進(jìn)SAMME.R算法SAMME.RD。

改進(jìn)算法主要包括以下兩個(gè)方面：1)對(duì)基分類器的分類結(jié)果進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)分到各類的基分類器個(gè)數(shù)，如果分到某類的個(gè)數(shù)與基分類器總數(shù)的比值大于一個(gè)設(shè)定的閾值α，則直接輸出此類作為待測(cè)樣本的類別。2)對(duì)于分到各類的數(shù)目沒有大于設(shè)定閾值α的情況，求出待測(cè)樣本在訓(xùn)練樣本中的有效鄰域，統(tǒng)計(jì)基分類器對(duì)有效鄰域中的樣本的分類能力，根據(jù)基分類器對(duì)有效鄰域分類正確率的大小來確定基分類器的加權(quán)系數(shù)。

假設(shè)有T個(gè)基分類器分別為ht(t=1,2,…,T)，有M個(gè)類別分別為ci(i=1,2,…,M)，ht對(duì)待測(cè)樣本x的輸出為ht(x)。

定義1 定義MC(x)={h1(x),h2(x),…,hT(x)}為T個(gè)基分類器對(duì)待測(cè)樣本x的分類行為。

設(shè)定閾值α(0<α≤1)，如果向量MC中有多于T*α個(gè)基分類器分到同一個(gè)類別，那么直接把這一類別作為待測(cè)樣本x的分類結(jié)果輸出，否則求出樣本x的有效鄰域進(jìn)行下一步的判斷。

待測(cè)樣本的鄰域指的是在空間上與之鄰近的部分樣本，在這部分樣本中有一些樣本與待測(cè)樣本的分類相似度較低，我們認(rèn)定此類樣本為無效的鄰域樣本對(duì)其進(jìn)行剔除，剔除無效鄰域樣本后剩余的鄰域樣本稱之為有效鄰域。為了描述樣本之間的相似程度，在定義2中定義相似度。

由定義2可知0≤S(x,y)≤1，在選取待測(cè)樣本x的有效鄰域時(shí)，設(shè)定閾值β，如果S(x,y)≥β則認(rèn)定y為有效的鄰域樣本，否則認(rèn)定為無效樣本進(jìn)行剔除。

在獲得待測(cè)樣本的有效鄰域后，計(jì)算每個(gè)基分類器對(duì)有效鄰域中的樣本的分類錯(cuò)誤率εt(t=1,2,…,T)，定義基分類器的權(quán)值w_dy(t)=lb((1-εt)/εt)。

改進(jìn)算法的具體流程如下：

1)根據(jù)2.1節(jié)中的AdaBoost算法訓(xùn)練生成基分類器。

2)輸入待測(cè)樣本x,計(jì)算待測(cè)樣本的MC值。

3)計(jì)算向量MC中分到某類的基分類器數(shù)目與總的基分類器數(shù)目的比值是否大于設(shè)定閾值α。如果大于閾值α則直接輸出對(duì)應(yīng)的類別，算法結(jié)束；否則，繼續(xù)下一步驟。

4)設(shè)定相似度的閾值β，計(jì)算待測(cè)樣本x的有效鄰域。

5)統(tǒng)計(jì)基分類器對(duì)有效鄰域樣本的分類效果，為基分類器賦權(quán)值w_dy(t)=lb((1-εt)/εt)，其中εt為第t個(gè)基分類器的分類錯(cuò)誤率。

SAMME.RD算法是一種改變基分類器加權(quán)方式的動(dòng)態(tài)加權(quán)多分類AdaBoost算法，它對(duì)如何訓(xùn)練基分類器沒有要求，所以SAMME.RD算法的思想可以通用，把針對(duì)SAMME.RRE的改進(jìn)命名為SAMME.RD1，針對(duì)SAMME.R2的改進(jìn)命名為SAMME.RD2。SAMME.RD算法需要對(duì)測(cè)試樣本在基分類器下的分類情況進(jìn)行統(tǒng)計(jì)，依據(jù)分類結(jié)果把樣本分類分為兩種方式：一種直接輸出類別；另一種求出待測(cè)樣本在訓(xùn)練集中的有效鄰域，對(duì)有效鄰域中樣本在基分類器下的分類情況進(jìn)行統(tǒng)計(jì)，計(jì)算出基分類器的加權(quán)系數(shù)。由于SAMME.RD算法需要對(duì)待測(cè)樣本的分類結(jié)果進(jìn)行統(tǒng)計(jì)，對(duì)部分樣本求有效鄰域并對(duì)有效鄰域樣本分類結(jié)果進(jìn)行統(tǒng)計(jì)提高了SAMME.R算法的時(shí)間復(fù)雜度。提升待測(cè)樣本有效鄰域的求解效率是解決SAMME.RD算法時(shí)間復(fù)雜度高的關(guān)鍵，還需要進(jìn)一步研究。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)所使用的數(shù)據(jù)均為UCI數(shù)據(jù)集中的多類數(shù)據(jù)集，在實(shí)驗(yàn)中采用三折交叉驗(yàn)證的方法來獲取訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)，數(shù)據(jù)集的詳細(xì)情況如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息

3.2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)通過對(duì)比SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1、SAMME.R2、SAMME.RD1和SAMME.RD2這8種算法的分類結(jié)果來驗(yàn)證SAMME.RD算法的性能以及使用真實(shí)錯(cuò)誤率的有效性，并總結(jié)出使用加權(quán)概率和真實(shí)概率進(jìn)行基分類器篩選的前提。

實(shí)驗(yàn)中8種算法所使用的弱分類算法均為決策樹，為了實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，本文對(duì)每次實(shí)驗(yàn)均進(jìn)行10次三折交叉驗(yàn)證，最后取這10次三折交叉驗(yàn)證的均值作為此次實(shí)驗(yàn)的最終結(jié)果。實(shí)驗(yàn)中為驗(yàn)證幾種算法的分類性能隨迭代次數(shù)增加的變化情況分別取迭代次數(shù)為10、20、30、40和50來對(duì)比8種算法的分類結(jié)果。為了對(duì)比算法的分類效率，統(tǒng)計(jì)迭代次數(shù)為50時(shí)算法對(duì)實(shí)驗(yàn)數(shù)據(jù)的分類時(shí)間。

3.3 結(jié)果分析

本次實(shí)驗(yàn)得出8種算法對(duì)12種UCI數(shù)據(jù)集的分類結(jié)果，如表2所示，表中的C1～C8分別表示SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1、SAMME.R2、SAMME.RD1和SAMME.RD2這8種算法，每種算法在相應(yīng)數(shù)據(jù)集上根據(jù)迭代次數(shù)的不同獲得不同的分類正確率。

表2 8種算法的分類結(jié)果對(duì)比

首先對(duì)比表2中SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2這6種算法的分類情況，之后對(duì)比表2中SAMME.RRE與SAMME.RD1兩種算法的分類結(jié)果以及SAMME.R2與SAMME.RD2兩種算法的分類結(jié)果。在迭代次數(shù)相同的情況下對(duì)比算法的分類結(jié)果可以發(fā)現(xiàn)，在迭代次數(shù)較少時(shí)經(jīng)常會(huì)出現(xiàn)SAMME算法分類結(jié)果優(yōu)于其他幾種算法的情況。但是隨著迭代次數(shù)的增加，SAMME算法分類正確率急劇下降，很快地陷入退化。SAMME.R算法雖然在一定程度上解決了SAMME算法的退化問題但是效果也不太好；其他幾種算法分類效果逐漸變優(yōu)，退化現(xiàn)象發(fā)生緩慢，而且退化較弱整體趨于平衡。從分類結(jié)果可以看出SAMME.R算法并不是在所有情況下都優(yōu)于SAMME算法，在數(shù)據(jù)分類正確率較低、基分類器獲取較難時(shí)，SAMME算法的分類效果優(yōu)于SAMME.R，例如在yeast和soybean數(shù)據(jù)集上。對(duì)比SAMME和SAMME.RE、SAMME.R和SAMME.RRE、SAMME.R1和SAMME.R2的分類結(jié)果可以看出，在算法中使用真實(shí)錯(cuò)誤率計(jì)算基分類器的加權(quán)系數(shù)是有效的，避免了算法嚴(yán)重退化現(xiàn)象的發(fā)生，但是同時(shí)也存在算法正確率提升速度較慢的缺點(diǎn)。對(duì)比SAMME.R與SAMME.R2、SAMME.RE與SAMME.RRE和SAMME.R2的分類結(jié)果可以看出：在分類正確率較低、數(shù)據(jù)類別較多且分布不平衡時(shí)使用加權(quán)概率篩選比真實(shí)概率效果好；在分類正確率較高、數(shù)據(jù)類別較少、分布平衡時(shí)使用真實(shí)概率篩選比加權(quán)概率效果好。對(duì)比SAMME、SAMME.RE、SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2這6種算法分類結(jié)果隨迭代次數(shù)增加的變化情況：隨著迭代次數(shù)的增加SAMME算法很快陷入退化之中；SAMME.R算法達(dá)到的效果在大部分?jǐn)?shù)據(jù)集上優(yōu)于SAMME，而且陷入退化也較慢；其他幾種算法的分類正確率隨迭代次數(shù)增加穩(wěn)步上升，達(dá)到最大值后基本趨于穩(wěn)定

接下來對(duì)比SAMME.RRE與SAMME.RD1、SAMME.R2與SAMME.RD2，從實(shí)驗(yàn)結(jié)果可以看出：在大部分?jǐn)?shù)據(jù)集上SAMME.RD1與SAMME.RD2的分類正確率優(yōu)于SAMME.RRE與SAMME.R2，但是在vowel和zoo數(shù)據(jù)集上卻比SAMME.RRE與SAMME.R2差。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的動(dòng)態(tài)加權(quán)SAMME.RD算法的有效性，但是算法的適用范圍還需要進(jìn)一步研究。在研究算法分類正確率的同時(shí)，本文對(duì)算法的分類效率也進(jìn)行了研究。通過對(duì)算法的分析可以知道SAMME和SAMME.RE分類時(shí)間大致相同，SAMME.R、SAMME.RRE、SAMME.R1和SAMME.R2這4種算法的分類時(shí)間大致相同，SAMME.RD1和SAMME.RD2分類時(shí)間大致相同。為了分析算法的效率，給出迭代次數(shù)為50的情況下SAMME、SAMME.R和SAMME.RD1對(duì)實(shí)驗(yàn)數(shù)據(jù)的分類時(shí)間，如表3所示。

表3 不同算法的分類時(shí)間對(duì)比(迭代50次)

從表3的結(jié)果可以看出,SAMME和SAMME.R兩種算法時(shí)間復(fù)雜度大致相同，SAMME.R算法略高；SAMME.RD與SAMME和SAMME.R兩種算法相比，時(shí)間復(fù)雜度較高，在數(shù)據(jù)量較少時(shí)，分類時(shí)間是SAMME和SAMME.R兩種算法的5～10倍，隨著數(shù)據(jù)量的增多，算法的時(shí)間迅速增長(zhǎng)至SAMME和SAMME.R的幾十甚至上百倍，SAMME.RD算法變得不可用。SAMME.RD算法能夠有效提升SAMME算法的分類正確率，但在效率上存在時(shí)間復(fù)雜度高的問題，SAMME.RD算法的時(shí)間復(fù)雜度主要源于求解待測(cè)樣本的有效鄰域，如何減少求解待測(cè)樣本有效鄰域的時(shí)間是降低算法時(shí)間復(fù)雜度的關(guān)鍵。

4 結(jié)語(yǔ)

本文分析了SAMME算法及其改進(jìn)算法SAMME.R，并針對(duì)SAMME和SAMME.R算法使用偽錯(cuò)誤率和加權(quán)概率對(duì)算法性能的影響進(jìn)行了討論。得出了使用真實(shí)錯(cuò)誤率要優(yōu)于偽損失的結(jié)論以及加權(quán)概率和真實(shí)概率的適用前提。在此研究基礎(chǔ)上，本文提出了一種動(dòng)態(tài)加權(quán)的SAMME.RD算法。通過實(shí)驗(yàn)驗(yàn)證了SAMME.RD算法對(duì)分類器性能提升的有效性，但是SAMME.RD算法仍然存在時(shí)間復(fù)雜度高的問題，如何降低算法的時(shí)間復(fù)雜度是下一步研究的主要方向。

)

[1]SCHAPIRERE.Thestrengthofweaklearnability[J].MachineLearning, 1990, 5(2): 197-227.

[2]FREUNDY,SCHAPIRERE.Adecision-theoreticgeneralizationofon-linelearningandanapplicationtoboosting[C]//ProceedingsoftheSecondEuropeanConferenceonComputationalLearningTheory,LNCS904.Berlin:Springer, 1995: 23-37.

[3]FREUNDY,SCHAPIRERE.Experimentswithanewboostingalgorithm[C]//ProceedingsoftheThirteenthInternationalConferenceonMachineLearning.SanFrancisco,CA:MorganKaufmann, 1996: 148-156.

[4]SCHAPIRERE,SINGERY.Improvedboostingalgorithmsusingconfidence-ratedpredictions[J].MachineLearning, 1999, 37(3): 297-336.

[5]ZHUJ,ZOUH,ROSSETS,etal.Multi-classAdaBoost[J].StatisticsandItsInterface, 2009, 2(3): 349-360.

[6] 胡金海,駱廣琦,李應(yīng)紅,等.一種基于指數(shù)損失函數(shù)的多類分類AdaBoost算法及其應(yīng)用[J].航空學(xué)報(bào),2008,29(4):811-816.(HUJH,LUOGQ,LIYH,etal.AnAdaBoostalgorithmformulti-classclassificationbasedonexponentiallossfunctionanditsapplication[J].ActaAeronauticaEtAstronauticaSinica, 2008, 29(4): 811-816.)

[7] 楊新武,馬壯,袁順.基于弱分類器調(diào)整的多分類AdaBoost算法[J].電子與信息學(xué)報(bào),2016,38(2):373-380.(YANGXW,MAZ,YUANS.Multi-classAdaBoostalgorithmbasedontheadjustedweakclassifier[J].JournalofElectronicsandInformationTechnology, 2016, 38(2): 373-380.)

[8] 孫士明,潘青,紀(jì)友芳.多閾值劃分的連續(xù)AdaBoost人臉檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2009,29(8):2098-2100.(SUNSM,PANQ,JIYF.RealAdaBoostfacedetectionmethodbasedonmulti-threshold[J].JournalofComputerApplications, 2009, 29(8): 2098-2100.)

[9] 阮錦新,尹俊勛.基于人臉特征和AdaBoost算法的多姿態(tài)人臉檢測(cè)[J].計(jì)算機(jī)應(yīng)用,2010,30(4):967-970.(RUANJX,YINJX.Multi-posefacedetectionbasedonfacialfeaturesandAdaBoostalgorithm[J].JournalofComputerApplications, 2010, 30(4): 967-970.)

[10] 王燕,公維軍.雙閾值級(jí)聯(lián)分類器的加速人臉檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用,2011,31(7):1821-1824.(WANGY,GONGWJ.Acceleratedalgorithmoffacedetectionbasedondual-thresholdcascadeclassifiers[J].JournalofComputerApplications, 2011, 31(7): 1821-1824.)

[11]NEGRIP,GOUSSIESN,LOTITOP.Detectingpedestriansonamovementfeaturespace[J].PatternRecognition, 2014, 47(1): 56-71.

[12] 董超,周剛,劉玉嬌,等.基于改進(jìn)的AdaBoost算法在網(wǎng)絡(luò)入侵檢測(cè)中的應(yīng)用[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,52(6):1225-1229.(DONGC,ZHOUG,LIUYJ,etal.ThedetectionofnetworkintrusionbasedonimprovedAdaBoostalgorithm[J].JournalofSichuanUniversity(NaturalScienceEdition), 2015, 52(6): 1225-1229.)

[13] 張彥峰,何佩琨.一種改進(jìn)的AdaBoost算法——M-AsyAdaBoost[J]. 北京理工大學(xué)學(xué)報(bào),2011,31(1):64-68.(ZHANGYF,HEPK.ArevisedAdaBoostalgorithm—M-AsyAdaBoost[J].TransactionsofBeijingInstituteofTechnology, 2011, 31(1): 64-68.)

[14]KOAHR,SABOURINR,JRASB.Fromdynamicclassifierselectiontodynamicensembleselection[J].PatternRecognition, 2008, 41(5): 1718-1731.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61273275, 61503407).

ZHAI Xiyang, born in 1994, M. S. candidate. His research interests include intelligent information processing, pattern recognition.

WANG Xiaodan, born in 1966, Ph.D., professor. Her research interests include intelligent information processing, machine learning.

LEI Lei, born in 1988, Ph. D. candidate. Her research interests include intelligent information processing, pattern recognition.

WEI Xiaohui, born in 1966, senior engineer. His research interest include computer information system.

Improved multi-class AdaBoost algorithm based on stagewise additive modeling using a multi-class exponential loss function

ZHAI Xiyang1, WANG Xiaodan1*, LEI Lei1, WEI Xiaohui2

(1.InstituteofAirDefenseandAnti-Missile,AirForceEngineeringUniversity,Xi’anShaanxi710051,China; 2.Hospital463ofPLA,ShenyangLiaoning110042,China))

Stagewise Additive Modeling using a Multi-class Exponential loss function (SAMME) is a multi-class AdaBoost algorithm. To further improve the performance of SAMME, the influence of using weighed error rate and pseudo loss on SAMME algorithm was studied, and a dynamic weighted Adaptive Boosting (AdaBoost) algorithm named SAMME with Resampling and Dynamic weighting (SAMME.RD) algorithm was proposed based on the classification of sample’s effective neighborhood area by using the base classifier. Firstly, it was determined that whether to use weighted probability and pseudo loss or not. Then, the effective neighborhood area of sample to be tested in the training set was found out. Finally, the weighted coefficient of the base classifier was determined according to the classification result of the effective neighborhood area based on the base classifier. The experimental results show that, the effect of calculating the weighted coefficient of the base classifier by using real error rate is better. The performance of selecting base classifier by using real probability is better when the dataset has less classes and its distribution is balanced. The performance of selecting base classifier by using weighed probability is better when the dataset has more classes and its distribution is imbalanced. The proposed SAMME.RD algorithm can improve the multi-class classification accuracy of AdaBoost algorithm effectively.

ensemble learning; multi-class; Adaptive Boosting(AdaBoost) algorithm; Stagewise Additive Modeling using a Multi-class Exponential loss function (SAMME); dynamic weighted fusion

2016- 11- 21;

2017- 01- 10。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61273275,61503407)。

翟夕陽(yáng)(1994—)，男，河南開封人，碩士研究生，主要研究方向：智能信息處理、模式識(shí)別； 王曉丹(1966—)，女，陜西漢中人，教授，博士，主要研究方向：智能信息處理、機(jī)器學(xué)習(xí)； 雷蕾(1988—)，女，四川南充人，博士研究生，主要研究方向：智能信息處理、模式識(shí)別；魏曉輝(1966—)，男，遼寧沈陽(yáng)人，高級(jí)工程師，主要研究方向：計(jì)算機(jī)信息系統(tǒng)。

1001- 9081(2017)06- 1692- 05

10.11772/j.issn.1001- 9081.2017.06.1692

TP181;TP301.6

A