第六章提升算法6.1引言當(dāng)做重要決定時(shí)，大家可能都會(huì)考慮吸取多個(gè)專家而不是一個(gè)人的意見。機(jī)器學(xué)習(xí)處理問題時(shí)也是如此，這就是提升算法背后的思路，提升算法是對(duì)其它算法進(jìn)行組合的一種方式，接下來我們將對(duì)提升算法，以及提升算法中最流行的一個(gè)算法AdaBoost算法進(jìn)行介紹，并對(duì)提升樹以及簡單的基于單層決策樹的Adaboost算法進(jìn)行討論。提升方法是一種常用的統(tǒng)計(jì)學(xué)習(xí)方法，應(yīng)用廣泛且有效，在分類問題上，它通過改變訓(xùn)練樣本的權(quán)重，學(xué)習(xí)多個(gè)分類器，并將這些分類器進(jìn)行線性組合，提高分類性能。一個(gè)分類器在訓(xùn)練數(shù)據(jù)上能夠獲得比其他分類器更好的擬合，但是在訓(xùn)練數(shù)據(jù)外的數(shù)據(jù)集上卻不能很好的擬合數(shù)據(jù)，這時(shí)就稱為該分類器出現(xiàn)了過擬合(overfitting)。提升算法能夠有效地防止過擬合現(xiàn)象的發(fā)生。圖1圖1過擬合現(xiàn)象示意圖提升算法是一種為了擬合自適應(yīng)基函數(shù)模型(adaptivebasis-functionmodels,ABM)(6-1(6-1)f（X）=Wo+Xw$（X）m=1(6-2)其中，蠕是一種分類算法或者回歸算法，被稱為弱分類器(weaklearner)或者基分類器(baselearner(6-2)f（x）=X叩（x；ym）m=1提升算法的目的是對(duì)以下公式的優(yōu)化:

(6-3)min藝乙(y,f(%(6-3)? iifi=1其中，L(y,y)稱為損失函數(shù)(lossfunction)，f是ABM模型。不同的損失函數(shù)有著不同的性質(zhì)，對(duì)應(yīng)不同的提升算法，如表1所示。將(2)式代入(3)式可得如下表達(dá)式:minZlfyminZlfy,XPP,y.Immi=1(6-4)Xm=1 /因?yàn)閷W(xué)習(xí)的是加法模型，如果能夠從前向后，每一步只學(xué)習(xí)一個(gè)基分類器及其系數(shù)，那么就可以簡化優(yōu)化的復(fù)雜度，具體推導(dǎo)過程如下所示：min乙G,(M3a))Pm"=1 'm1m表1常見損失函數(shù)以及相應(yīng)提升算法名稱損失函數(shù)導(dǎo)數(shù)f*算法平方誤差2(yi-f(%i))2yi-f(%i)E【y1%.]L2Boosting絕對(duì)誤差ly-f(%)1i isgn(y—f(%))iimedian(y1%.)Gradientboosting指數(shù)損失exp(-yf(%))i i-y,expCyf(%「)1】-^-log—i—2 1-兀iAdaBoost對(duì)數(shù)損失log(+e-f)yi一氣1】logi2 1-兀iLogitBoostf(X)=argmin%L(y,f(%;邛))y,=i(p,y)=argmin1^L(y,f(%)+階(%;y))mm im-1i ip,yi=1f(X)=fm-1(X)+Pm4(X;ym)因此該算法稱為前向分步算法。(6-5)(6-6)(6-7)(6-8)m(6-5)(6-6)(6-7)(6-8)m算法不進(jìn)行回溯對(duì)參數(shù)進(jìn)行修改AdaBoost(Adaptiveboosting)算法，也稱為自適應(yīng)提升算法。訓(xùn)練數(shù)據(jù)中的每個(gè)樣本，并賦予其一個(gè)權(quán)重，這些權(quán)重構(gòu)成向量D。一開始，這些權(quán)重都初始化為相等值，首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個(gè)弱分類器并計(jì)算該分類器的錯(cuò)誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器。再次訓(xùn)練分類器的過程中，將會(huì)重新調(diào)整每個(gè)樣本的權(quán)重，其中上一次分對(duì)的樣本權(quán)重會(huì)降低，而上一次分錯(cuò)的樣本權(quán)重會(huì)提高。

圖2AdaBoost算法示意圖給定一個(gè)二類分類的訓(xùn)練數(shù)據(jù)集t={3,y）,（x）），川,）}，其中，每個(gè)樣本點(diǎn)由實(shí)例1 1 2 2一、N.N〔TOC\o"1-5"\h\z與標(biāo)記組成，實(shí)例xexoRn，標(biāo)記ye丫={-1,+1}，/是實(shí)例空間，y是標(biāo)記集合。損失函數(shù)可以表達(dá)為： ' 'L(們=￡exp[-y.(f](x)+。。3))]=l^wexp(-。y?(x)) (6-9)i=1 i=1其中，w"exp(-yfZi))，y.e{-1,+1}，則可以有如下推導(dǎo)：L(?L(?)=e-P￡w+eP￡wy{=?(x.) y.耳(x.)P-e-p)￡wI(y。。(x))+e-P￡wi=1 i=1（6-10）其中 1[ 1—err其中,P=一log r,m2errmm個(gè)分類器：其中 1[ 1—err其中,P=一log r,m2errmm個(gè)分類器：￡NwI(y。。(x))

err=—曰~￡， m一i—，i=1i，merr稱為分類誤差率。則可以得到第mfm(X)=fm—1(X)+Pm?(X)（6-11）計(jì)算第m+1個(gè)分類器的參數(shù)可以通過下式得到:w=we-Py.?(x.)=weP(21(y.A(x.))—1)=we2Pi(y.A(x.))e—P”， 1 ”,—mJi'my" ”,J，m'、勺'm' ' ”,—，m、勺'm' m（6-12）總結(jié)起來Adaboost算法主要有以下7步。wi=Lform=1：mdo3Fitaclassifier?(X)tothetrainingsetusingweightsw4Compute￡NwI(y。。(x))err= i=1i，￡imii=1i5Computea=log12-^(a=2P)m6Setw—weami(yi，虬(x,))7Return/⑴=sgn￡Ma。(x)Lm=1mm-算法結(jié)束條件是訓(xùn)練錯(cuò)誤率為0或者弱分類器數(shù)目達(dá)到用戶指定的值。在具體應(yīng)用AdaBoost算法時(shí)，可以將其總結(jié)為以下的一般流程：收集數(shù)據(jù)：可以使用任意方法；準(zhǔn)備數(shù)據(jù)：依賴于所使用弱分類器的類型，這里k-近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機(jī)等任意分類算法都可以作為本部分弱分類器；分析數(shù)據(jù)：可使用任意方法；訓(xùn)練算法：AdaBoost算法大部分時(shí)間都用在訓(xùn)練上，分類器將多次在同一數(shù)據(jù)集上訓(xùn)練弱分類器；測試算法：計(jì)算分類錯(cuò)誤率；使用算法：同支持向量機(jī)類似，AdaBoost算法預(yù)測兩個(gè)類別中的一個(gè)，如果想應(yīng)用多分類，需要做與支持向量機(jī)類似的相應(yīng)修改。6.3提升樹分類與回歸樹(Classificationandregressiontrees,CART)又稱為決策樹(decisiontree)，使用分類數(shù)與回歸樹作為基本分類器的提升方法，稱為提升樹(Boostingtree)。圖3圖3決策樹示意圖決策樹模型將空間分為數(shù)個(gè)互不相交的區(qū)域A,j=i,,7，每一個(gè)區(qū)域作為樹的葉子節(jié)點(diǎn)，并為每個(gè)區(qū)域分配一個(gè)參數(shù)y: j...jxGRnf(x)=y. (6-13)因此決策樹則可以表達(dá)為如下形式：(6-14)T(x;⑥)=￡yI(xg(6-14)j=i其中，0={R,y.}：，該參數(shù)由最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)計(jì)算得到:

(6-15)0=argmin￡EL(y,(6-15)0j=1Xj^Rj決策樹模型是一種傳統(tǒng)的學(xué)習(xí)方法，易于被理解，相比較人工神經(jīng)網(wǎng)絡(luò)，我們能夠清晰地了解如何構(gòu)建決策樹，而且決策樹模型無信息丟失。但是決策樹模型也存在不穩(wěn)定的缺點(diǎn)，訓(xùn)練樣本較小的變化會(huì)導(dǎo)致結(jié)果的較大差異。為解決這一問題，研究者主要通過提升算法來對(duì)決策樹模型進(jìn)行優(yōu)化，即所謂的提升樹(Boostingtree)，其基本算法思路為，構(gòu)建多個(gè)決策樹，多個(gè)決策樹決策結(jié)果的加權(quán)平均對(duì)樣本的變化不敏感。提升樹模型是一系列的決策樹的和：(6-16)f(%)=Yt(%;(6-16)m=1引入前向分步算法:◎=argminXl◎=argminXl(y,f(%)+T(x;◎))

m^ im-1i im(6-17)0mi=1已知f1(x)求得0={R^,y.}伽，已知R,求y.:Y=argmin￡L(y,f(x)+y)

jm y im-1ijm*jm%,^R.6.4基于單層決策樹的AdaBoost算法(6-18)單層決策樹(decisionstump，也稱決策樹樁)是一種簡單的決策樹，僅基于單個(gè)特征來做決策，由于這棵樹只有一次分裂過程，因此它實(shí)際上就是一個(gè)樹樁。利用Python對(duì)單層決策樹進(jìn)行實(shí)現(xiàn)，代碼如下：defstumpClassify(dataMatrix,dimen,threshVal,threshIneq):retArray=ones((shape(dataMatrix)[0],1))ifthreshIneq=='lt':retArray[dataMatrix[:,dimen]<=threshVal]=-1.0else:retArray[dataMatrix[:,dimen]>threshVal]=-1.0returnretArraydefbuildStump(dataArr,classLabels,D):dataMatrix=mat(dataArr);labelMat=mat(classLabels).Tm,n=shape(dataMatrix)numSteps=10.0;bestStump={};bestClasEst=mat(zeros((m,1)))minError=infforiinrange(n):rangeMin=dataMatrix[:,i].min();rangeMax=dataMatrix[:,i].max();stepSize=(rangeMax-rangeMin)/numStepsforjinrange(-1,int(numSteps)+1):forinequalin['lt','gt']:threshVal=(rangeMin+float(j)*stepSize)predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal)errArr=mat(ones((m,1)))errArr[predictedVals==labelMat]=0weightedError=D.T*errArrifweightedError<minError:minError=weightedErrorbestClasEst=predictedVals.copy()bestStump['dim']=ibestStump['thresh']=threshValbestStump['ineq']=inequalreturnbestStump,minError,bestClasEst上述程序包含兩個(gè)函數(shù)。第一個(gè)函數(shù)stumpClassfy()是通過閾值比較對(duì)數(shù)據(jù)進(jìn)行分類的，所有的閾值一邊的數(shù)據(jù)會(huì)分到類別-1,而在另一邊的數(shù)據(jù)分到類別+1.該函數(shù)可以通過數(shù)組過濾來實(shí)現(xiàn)，首先將返回?cái)?shù)組的全部元素設(shè)置為1,然后將所有不滿足不等式要求的元素設(shè)置為-1,可以給予數(shù)據(jù)集中的任意元素進(jìn)行比較，同時(shí)也可以將不等號(hào)在大于、小于之間切換。第二個(gè)函數(shù)buildStump()將會(huì)遍歷stumpClassfy()函數(shù)所有可能的輸入，并找到數(shù)據(jù)集上最佳的單層決策樹。在確保輸入數(shù)據(jù)符合矩陣格式之后，整個(gè)函數(shù)就開始執(zhí)行了，然后函數(shù)將構(gòu)建一個(gè)稱為bestStump的空字典，這個(gè)字典用語存儲(chǔ)給定權(quán)重向量D時(shí)所得到的最佳單層決策樹的相關(guān)信息。變量numSteps用于在特征的所有可能值上進(jìn)行遍歷。而變量minError則在一開始就初始化成正無窮大，之后用語尋找可能的最小錯(cuò)誤率。三層嵌套的for循環(huán)是程序最主要的部分。第一層for循環(huán)在數(shù)據(jù)集所有特征上遍歷?？紤]到數(shù)值型的特征，我們就可以通過計(jì)算最小值和最大值來了解應(yīng)該需要多大的不暢。然后，第二層for循環(huán)再在這些值上遍歷。甚至將閾值設(shè)置為整個(gè)取值范圍之外也是可以的。因此在取值范圍之外還應(yīng)該有兩個(gè)額外的步驟，最后一個(gè)for循環(huán)則是在大于和小于之間切換不等式。上述單層決策樹的生成函數(shù)是決策樹的一個(gè)簡化版本，即是所謂的弱學(xué)習(xí)器(弱分類器)。到現(xiàn)在為止，我們已經(jīng)建立了單層決策樹，并生成了程序，做好了過渡到完整AdaBoost算法，如下所示：defadaBoostTrainDS(dataArr,classLabels,numIt=40):weakClassArr=[]m=shape(dataArr)[0]D=mat(ones((m,1))/m)#initDtoallequalaggClassEst=mat(zeros((m,1)))foriinrange(numIt):bestStump,error,classEst=buildStump(dataArr,classLabels,D)alpha=float(0.5*log((1.0-error)/max(error,1e-16)))bestStump['alpha']=alphaweakClassArr.append(bestStump)expon=multiply(-1*alpha*mat(classLabels).T,classEst)D=multiply(D,exp(expon))D=D/D.sum()aggClassEst+=alpha*classEstaggErrors=multiply(sign(aggClassEst)!=mat(classLabels).T,ones((m,1)))errorRate=aggErrors.sum()/mprint"totalerror:",errorRateiferrorRate==0.0:breakreturnweakClassArr偽代碼可以簡單總結(jié)為以下步驟:對(duì)每次迭代：利用buildStump()函數(shù)找到最佳的單層決策樹將最佳單層決策樹加入到單層決策樹組計(jì)算alpha計(jì)算新的權(quán)重向量D更新累積類別估計(jì)值如果錯(cuò)誤率等于0.0，則退出循環(huán)該AdaBoost算法的輸入?yún)?shù)包括數(shù)據(jù)集、類別標(biāo)簽以及迭代次數(shù)numIt，其中numI是在整個(gè)AdaBoost算法中唯一需要用戶指定的參數(shù)。AdaBoost算法的核心在于for循環(huán)，該循環(huán)運(yùn)行numIt次，或者知道訓(xùn)練錯(cuò)誤率為0為止。循環(huán)中的第一件事就是利用前面介紹的buildStump()函數(shù)建立一個(gè)單層決策樹，同時(shí)返回的還有最小的錯(cuò)誤率以及估計(jì)的類別向量。然后則需要計(jì)算的則是alpha值，該值會(huì)告訴總分類器本次單層決策樹輸出結(jié)果的權(quán)重，其中的語句max(error,1e-16)用語確保在沒有錯(cuò)誤時(shí)，不會(huì)發(fā)生除零溢出，而后，alpha值加入到bestStump字典中，該字典又添加到列表中。該字典包含分類所需要的所有信息。接下來則是計(jì)算下一次迭代中的新權(quán)重向量D，在訓(xùn)練錯(cuò)誤率為0時(shí)則提前結(jié)束for循環(huán)。圖4則為我們所得到的一組弱分類器及其權(quán)重。[{1dirr.1:9,1ineq':1gt\"thresh':3. 1dlphd': .46166237926576756：-,{'dim':17,'ineq':'gt','thresh':52.5,'alpha':3.3124S245342467243：-,■{'dirr.':3r'ineq':"gt','tnresh':55.199999999999996,'alpha':3.2S6S：＞97323169559：-,{"dim1:IS,'ineq':'it','thresh':62.3：＞333333:'3:'3:'alpha'::2329733463S939772?,■{'dim':13f'ineq':'It'f'thresn': 1alpha': 19S33S46151213622：-,{"dim':5fineq':'gt'f'thresh':2.3f'alpha':：'.1SB47BB7349：'2：'733:-f'diir.':12,"ineq':It\'thresh':1.2f'dlphd'::.1522736599747672:'dim1: ■ineq':"gt'r'thresh':1.2,'alpha':1551：'57：'521693356：-f{■dim1:5,'ineq1:■It','thresh1:：'.：',1alpha1: 1353619735335926：-,■{'din':七,ineq':'If,1thresh':25.799999999999997,'alpha1:：'.1252155732613193:-]圖4弱分類器如圖5所示，為不同弱分類器數(shù)，所得的分類結(jié)果，可以看到，弱分類器越多，在訓(xùn)練集上分類錯(cuò)誤率越低，分類效果越好，但是并不是弱分類器越多，對(duì)測試數(shù)據(jù)的分類效果越好。weaklearnererrorrste;0.284280936455weaklearnererrorrate:0.28^280936455weaklearnererrorrate:0.2B^2B05364S5weakleamezerrorrate:0.2^^200936453weaklearnererrorrates0.247491636796weaklearnererrorrace:0.247491638796weaklearnererrorrste:0.2^7^91630796weaklearnererrorrate:0.24749163B796weaklearnererrorrate:0.254180602007weaklearnererrorrate:0,254150602007weaklearnererrorrates0.240802675585weakweaklearnererrorrate:learnererrorra^e:0.2408026755E50.22073S78S553weaklearnererrorrate:0.1872909699weaklearnererrorrate:0<24749163B796weaklearnererrorrate;0,19397993311weaklearnererrorrate:0.230769230769weaklearnererrorrate:0.1872909699traintraintrainierrors69*0inunntser: 299ierrorrate: 0.230769230769craintraintrainerror;numbererror:56.0:299rate:0.1872909699cesc.testtesterror: 16*0number: 67errorra*e: 0.23S80S970149teattesttesterror: 14+0nujuber: €7errorra^e:0.2089SS2238S110個(gè)分類器50個(gè)分類器10個(gè)分類器100個(gè)分類器100個(gè)分類器500個(gè)分類器weaklearnererrorra^e;0.284280936455 weaklearnererrorrace:0..28^280936155weaklearnererrorrate:0*157190635452weaklearnererrorrate:0.247^91638796weaklearnererrorrate: