兩分類(lèi)不平衡數(shù)據(jù)的Boosting算法

宋 捷 ，呂曉玲 ，吳喜之 ,b

(中國(guó)人民大學(xué)a.統(tǒng)計(jì)學(xué)院；b.應(yīng)用統(tǒng)計(jì)研究中心，北京 100872)

0 引言

分類(lèi)是統(tǒng)計(jì)應(yīng)用中的一個(gè)重要領(lǐng)域。它通常是通過(guò)訓(xùn)練數(shù)據(jù)學(xué)習(xí)得到一個(gè)分類(lèi)器，然后再用這個(gè)分類(lèi)器對(duì)需要預(yù)測(cè)的數(shù)據(jù)進(jìn)行預(yù)測(cè)。目的是得到較好的預(yù)測(cè)，也就是得到更小的預(yù)測(cè)誤差。以?xún)煞诸?lèi)為例，預(yù)測(cè)誤差是這樣兩部分之和，一部份是把1類(lèi)分為2類(lèi)發(fā)生的錯(cuò)誤，另一部分是把2類(lèi)分為1類(lèi)發(fā)生的錯(cuò)誤。但是有時(shí)這個(gè)預(yù)測(cè)誤差越小卻不能說(shuō)明這個(gè)分類(lèi)就好。比如：有一個(gè)兩分類(lèi)的總體，兩個(gè)類(lèi)在總體中的比例為（0.10，0.90），有一個(gè)分類(lèi)器的預(yù)測(cè)誤差為0.19，兩個(gè)類(lèi)各自的類(lèi)內(nèi)預(yù)測(cè)誤差為（0.9,0.1）；另一個(gè)分類(lèi)器的預(yù)測(cè)誤差為0.22，兩個(gè)類(lèi)各自的類(lèi)內(nèi)預(yù)測(cè)誤差為（0.4,0.2）。第一個(gè)分類(lèi)器的預(yù)測(cè)誤差更小，但是它把第一個(gè)類(lèi)中的樣品幾乎都分錯(cuò)了。第二個(gè)分類(lèi)器雖然預(yù)測(cè)誤差稍大，但是在兩個(gè)類(lèi)中的預(yù)測(cè)誤差都比較小。由此可見(jiàn)，用總體的預(yù)測(cè)誤差來(lái)評(píng)價(jià)分類(lèi)器的好壞此時(shí)已經(jīng)不妥。像這種各個(gè)類(lèi)在總體中的比例相差很大的數(shù)據(jù)我們稱(chēng)為不平衡數(shù)據(jù)。實(shí)際中我們也會(huì)遇到很多這樣的數(shù)據(jù)。比如在診斷病人時(shí)，我們有的只是很少的病例，而絕大多數(shù)人都是健康人。這時(shí)病人和健康人就是比例相差很大的兩個(gè)類(lèi)。診斷病人時(shí)我們希望最好把病人都診斷為病人，健康人都診斷為健康人。但是不管怎樣都會(huì)有錯(cuò)分發(fā)生，而且把病人診斷為健康人的風(fēng)險(xiǎn)總是遠(yuǎn)遠(yuǎn)高于把健康人診斷為病人。也就是說(shuō)我們希望的是兩個(gè)人群中各自的錯(cuò)分都要比較小。我們就想到為什么不同時(shí)減小每個(gè)類(lèi)內(nèi)部的預(yù)測(cè)誤差，而不僅僅是減小所有類(lèi)的預(yù)測(cè)誤差。也就是說(shuō)我們需要消除兩個(gè)類(lèi)之間的不平等性。

在此之前，有很多人通過(guò)調(diào)整各個(gè)類(lèi)在總體中的比例來(lái)處理不平衡數(shù)據(jù)。Xingye Qiao和Yufeng Liu[5]提出一種對(duì)每個(gè)類(lèi)的樣品錯(cuò)分率迭代加權(quán)的方法。本文也將通過(guò)減小各個(gè)類(lèi)內(nèi)部的預(yù)測(cè)誤差的想法出發(fā)提出一種自適應(yīng)的處理不平衡數(shù)據(jù)的Boosting算法Baboost。

1 Adaboost算法

Adaboost算法是一種集成的分類(lèi)算法。因?yàn)槠淞己玫姆诸?lèi)能力與抵抗過(guò)擬和的能力而受到大家的廣泛應(yīng)用。Breiman[1]用Boosting技術(shù)來(lái)提高一次分類(lèi)的能力，通過(guò)集成的方法有效地減小偏差，從而提高單個(gè)不穩(wěn)定分類(lèi)的預(yù)測(cè)誤差。Adaboost算法的運(yùn)行機(jī)制也一直是大家研究的熱點(diǎn)。目前流行的觀點(diǎn)是由Friedman等人[2]提出的，認(rèn)為Boosting是一種可加模型?；诓煌膿p失與不同的組合方式，研究者們提出了很多不同的Boosting算法。

Adaboost算法通過(guò)不斷迭代優(yōu)化的方法來(lái)進(jìn)行分類(lèi)?？紤]到解釋變量與被解釋變量的全概率，不管類(lèi)與類(lèi)之間數(shù)據(jù)多少的比例，通過(guò)減小總的分類(lèi)誤差來(lái)進(jìn)行分類(lèi)。但是當(dāng)類(lèi)與類(lèi)之間數(shù)據(jù)嚴(yán)重不平衡時(shí)，Adaboost算法的誤差會(huì)只由數(shù)據(jù)少的那類(lèi)帶來(lái)，可能那一類(lèi)的數(shù)據(jù)完全被錯(cuò)分。之所以出現(xiàn)這個(gè)問(wèn)題的原因是Adaboost算法是基于類(lèi)之間地位平等的時(shí)候的一種分類(lèi)算法。以?xún)煞诸?lèi)為例，當(dāng)以損失采用指數(shù)損失時(shí)，最優(yōu)解是我們可以看到，這個(gè)最優(yōu)解等價(jià)于也就是x與y的全概率之比。但是當(dāng)遇到兩個(gè)類(lèi)的數(shù)據(jù)比例相差很大時(shí)，這個(gè)解就會(huì)受到很大影響。因?yàn)楫?dāng)很小或者很大時(shí)，最優(yōu)解就會(huì)受到很大影響，而的作用不容易顯露。

W.Fan 等人(1999)[4]，Nitesh V.Chawla 等人(2002)[3]等人都提出一些通過(guò)調(diào)整不同類(lèi)的權(quán)重的方法來(lái)改進(jìn)Adaboost，得到比Adaboost小的預(yù)測(cè)誤差。但是他們的方法都不是直接從各個(gè)類(lèi)內(nèi)部的錯(cuò)誤率出發(fā)來(lái)更新權(quán)重，而且其中的參數(shù)也比較難于的確定。

2 Balanced Adaboost算法

Adaboost的目標(biāo)是減小錯(cuò)分誤差。錯(cuò)分誤差包括兩部分：一部分是把屬于1類(lèi)的樣品分為0類(lèi)，一部分是把屬于0類(lèi)的樣品分為1類(lèi)。Adaboost將這兩種誤差看作是同等地位的誤差。從而目標(biāo)就是減小這兩種誤差之和。但是在很多實(shí)際問(wèn)題中兩種錯(cuò)誤的地位是不同的。比如在醫(yī)學(xué)中，將一個(gè)沒(méi)有病的人診斷為病人帶來(lái)的風(fēng)險(xiǎn)就遠(yuǎn)遠(yuǎn)小于將有病的人診斷為沒(méi)有病。此時(shí)兩個(gè)類(lèi)之間不平等正是由數(shù)據(jù)量的差別所帶來(lái)的，需要調(diào)整兩個(gè)類(lèi)的權(quán)重。這里我們通過(guò)各個(gè)類(lèi)內(nèi)部的預(yù)測(cè)誤差來(lái)自適應(yīng)地調(diào)整權(quán)重，提出一種新的自適應(yīng)的處理不平衡數(shù)據(jù)的Balanced Adaboost算法，簡(jiǎn)稱(chēng)：Baboost。對(duì)于兩分類(lèi)而言，算法如下。

算法1：

輸入: 訓(xùn)練集(X1,Y1),(X2,Y2),…(Xn,Yn)，Yi∈{-1,+1}

(1)給出初始化權(quán)重ω0=1/n，H初值為0；

(2)放回地以概率分布為ωi對(duì)所有樣品進(jìn)行抽樣(i=0,1,2,…，n)，用抽出的樣品得到一個(gè)弱分類(lèi)器ht:Xn→{-1,+1},這里假設(shè)1類(lèi)是多數(shù)類(lèi),-1類(lèi)是少數(shù)類(lèi)；

(3)計(jì)算兩種錯(cuò)分率

當(dāng)ht(Xi)=1時(shí)

et1=∑Dt(i)*I(ht(Xn)≠Yi∩ht(Xi)=1/∑Dt(i)*I(ht(Xn)=1)

計(jì)算ct1=ln(1-et1)/et1)

當(dāng)ht(Xi)=-1時(shí)

ett-1=∑Dt(i)*I(ht(Xi)≠Yi∩ht(Xi)=-1)/∑Dt(i)*I(ht(Xn)=-1)

計(jì)算ct1=ln(1-et1)/et1)

更新H=H+ctht

更新權(quán)值:如果 ht(Xi)≠Yi，且 ht(Xi)=1，Dt+1(i)Dt(i)exp(ct1)

如果 ht(Xi)≠Yi，且 ht(Xi)=-1，Dt+1(i)Dt(i)exp(ct1)

如果ht(Xi)=Yi,Dt+1(i)=Dt(i)，將兩類(lèi)權(quán)重分別歸一化后再歸一化；

(4)重復(fù)B,C步次；

(5)輸出 sign(H(x))。

從上面的算法程序中我們可以直觀地看到，對(duì)于兩類(lèi)樣品分別計(jì)算了類(lèi)內(nèi)的錯(cuò)分誤差，數(shù)據(jù)多的那類(lèi)錯(cuò)分率相對(duì)于數(shù)據(jù)少的那類(lèi)的錯(cuò)分率要低。這樣在下一步更新權(quán)重時(shí)，對(duì)于分錯(cuò)的樣品就不再是同樣的更新方式了。分錯(cuò)的樣品的權(quán)重都將給以更高的權(quán)重，權(quán)重都要增加。但是他們不再增加相同的量。數(shù)據(jù)多的那類(lèi)被錯(cuò)分的樣品的權(quán)重增加量比數(shù)據(jù)少的那類(lèi)被錯(cuò)分的樣品的權(quán)重增加量要小。同時(shí)，每個(gè)分類(lèi)器在劃分1類(lèi)與-1類(lèi)的準(zhǔn)確性上也做了區(qū)分，不再是同樣的劃分能力。如果該分類(lèi)器把原本是1類(lèi)的樣品劃分為-1類(lèi)的概率很高，即偏大，那么該分類(lèi)器將樣品劃分為-1類(lèi)的準(zhǔn)確性低，此時(shí)相應(yīng)地就偏小。如果該分類(lèi)器把原本是-1類(lèi)的樣品劃分為1類(lèi)的概率很高，即偏大，那么該分類(lèi)器把樣品劃分為1類(lèi)的準(zhǔn)確性低，此時(shí)相應(yīng)地就偏小。

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

3.1 數(shù)值試驗(yàn)

圖1 數(shù)據(jù)散點(diǎn)圖

我們隨機(jī)選取其中的一半數(shù)據(jù)作為訓(xùn)練集，剩下的作為測(cè)試集。下面的結(jié)構(gòu)都是計(jì)算了100次的平均結(jié)果。運(yùn)算中，還可以依據(jù)實(shí)際情況自己調(diào)整的取值為上面算法描述中的1/100，1/200等。ct1越小，-1類(lèi)的錯(cuò)分率越低。下面的結(jié)果是取ct1/500的結(jié)果。Adaboost算法與Baboost算法結(jié)果如表1。

表1 模擬數(shù)據(jù)試驗(yàn)結(jié)果

從上面的結(jié)果中我們可以看到，只從測(cè)試誤差上來(lái)看，Adaboost的測(cè)試誤差比Baboost小了49.7%。但是我們把測(cè)試誤差分開(kāi)來(lái)看，可以看到，測(cè)試誤差中的90%都是由-1類(lèi)的錯(cuò)分所帶來(lái)的。也就是說(shuō)此時(shí)Adaboost在劃分-1類(lèi)的樣品時(shí)所發(fā)生的錯(cuò)誤相當(dāng)大，幾乎是劃分1類(lèi)樣品發(fā)生錯(cuò)誤的15倍。而B(niǎo)aboost在-1類(lèi)上的錯(cuò)分率比Adaboost在-1類(lèi)上的錯(cuò)分率小了81.4%，并且Baboost在劃分-1類(lèi)樣品時(shí)所發(fā)生的錯(cuò)誤比劃分1類(lèi)樣品發(fā)生錯(cuò)誤還小。圖2是兩種算法分別計(jì)算100次在兩個(gè)類(lèi)中的錯(cuò)分率。

圖2 100次類(lèi)內(nèi)誤差

橫軸是在1類(lèi)中的錯(cuò)分率，縱軸是在-1類(lèi)中的錯(cuò)分率。從圖2可以看到，Baboost的錯(cuò)分率點(diǎn)幾乎 100%都在點(diǎn)(0.2,0.2)的右下方，而Adaboost的錯(cuò)分率點(diǎn)只有20%左右在點(diǎn)(0.2,0.2)的右下方。我們當(dāng)然希望一個(gè)算法能使得兩個(gè)類(lèi)的錯(cuò)分類(lèi)率都比較低，而不是只是某一類(lèi)的錯(cuò)分率較低。

3.2 實(shí)際應(yīng)用

這里我們將上述算法應(yīng)用到Satimage數(shù)據(jù)集。該數(shù)據(jù)集來(lái)源于UCI機(jī)器學(xué)習(xí)網(wǎng)站http://www.ics.uci.edu/～mlearn/。該數(shù)據(jù)的分類(lèi)目標(biāo)是決定是否一個(gè)病人有甲狀腺功能減退的癥狀。該數(shù)據(jù)集包括7200個(gè)樣品，21個(gè)自變量，因變量為3分類(lèi)的變量。自變量中有15個(gè)屬性變量，6個(gè)連續(xù)變量。其中三個(gè)類(lèi)的樣品個(gè)數(shù)分別為：166，368，6666。我們選擇其中200個(gè)樣品做為訓(xùn)練集，200個(gè)樣品做為測(cè)試集。訓(xùn)練集和測(cè)試集中三個(gè)類(lèi)的樣品個(gè)數(shù)分別為：5，10，185，保持了原來(lái)數(shù)據(jù)各個(gè)類(lèi)之間的比例。

試驗(yàn)中，我們選取Ct3/200，重復(fù)試驗(yàn)了100次，每次的訓(xùn)練集與測(cè)試集都是隨機(jī)選取。表2結(jié)果是100次的平均結(jié)果。

表2 hyroid數(shù)據(jù)試驗(yàn)結(jié)果

從表2可以看到，如果用Adaboost算法處理這個(gè)數(shù)據(jù)時(shí)數(shù)據(jù)少的類(lèi)的錯(cuò)分率比數(shù)據(jù)多的類(lèi)的錯(cuò)分率高很多。而用Baboost對(duì)數(shù)據(jù)進(jìn)行處理將會(huì)大大改善結(jié)果，尤其是在一類(lèi)和二類(lèi)數(shù)據(jù)的劃分上。而且我們這個(gè)算法比Xingye Qiao和Yufeng Liu[3]提出的方法的每個(gè)類(lèi)的錯(cuò)分率都要低。他們的方法在三個(gè)類(lèi)上的錯(cuò)分率分別為：0.153，0.187，0.201。原因是我們對(duì)每個(gè)的基分類(lèi)器都要加權(quán)，考慮每個(gè)基分類(lèi)器的分類(lèi)能力。而他們的方法不考慮每個(gè)基分類(lèi)器的分類(lèi)能力。

4 結(jié)論

從上面的試驗(yàn)中我們可以看到，當(dāng)數(shù)據(jù)不平衡時(shí)，Baboost在總的預(yù)測(cè)誤差上會(huì)比Adaboost要高一點(diǎn)。但是總的預(yù)測(cè)誤差此時(shí)用來(lái)評(píng)價(jià)模型的好壞已經(jīng)不完善了。當(dāng)我們分別用類(lèi)內(nèi)的預(yù)測(cè)誤差來(lái)評(píng)價(jià)時(shí)，發(fā)現(xiàn)此時(shí)Baboost比Adaboost的預(yù)測(cè)性能更好。尤其是在數(shù)據(jù)偏少的那些類(lèi)。而在實(shí)際問(wèn)題中，我們經(jīng)常關(guān)心的很可能正好是數(shù)據(jù)少的那些類(lèi)，所以減少少量數(shù)據(jù)那類(lèi)的類(lèi)內(nèi)誤差更實(shí)際有效。

算法的不足是沒(méi)有對(duì)的取值進(jìn)行優(yōu)化，只是簡(jiǎn)單的選擇1/500或者1/200。這可以在以后的工作中加以進(jìn)一步討論。

[1]Breiman L.Bias,Variance,Arcing Classifiers,Tech.Rep.460[M].California：University of California，1996.

[2]Friedman,J.H.,Hastie,T.,Tibshirani,R.Additive Logistic Regression:A Statistical View of Boosting[J].Annals of Statistics,2000,28.

[3]N.V.Chawla,K.W.Bowyer,L.O.Hall,W.P.Kegelmeyer.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research,2002,16.

[4]W.Fan,S.Stolfo,J.Zhang,P.Chan.Ada Cost:Misclassification Cost-Sensitive Boosting[C].Proceedings of 16th International Conference on Machine Learning,Slovenia,1999.

[5]Xingye Qiao,Yufeng Liu.Adaptive Weighted Learning for Unbalanced Multicategory Classification[M].USA：University of North Carolina,2008.