機器學習算法總結(jié)-決策樹(含代碼)

1、第六章提升算法6.1引言當做重要決定時，大家可能都會考慮吸取多個專家而不是一個人的意見。機器學習處理問題時也是如此，這就是提升算法背后的思路，提升算法是對其它算法進行組合的一種方式，接下來我們將對提升算法，以及提升算法中最流行的一個算法AdaBoost算法進行介紹，并對提升樹以及簡單的基于單層決策樹的Adaboost算法進行討論。提升方法是一種常用的統(tǒng)計學習方法，應(yīng)用廣泛且有效，在分類問題上，它通過改變訓(xùn)練樣本的權(quán)重，學習多個分類器，并將這些分類器進行線性組合，提高分類性能。一個分類器在訓(xùn)練數(shù)據(jù)上能夠獲得比其他分類器更好的擬合，但是在訓(xùn)練數(shù)據(jù)外的數(shù)據(jù)集上卻不能很好的擬合數(shù)據(jù)，這時就稱為該分類器

2、出現(xiàn)了過擬合(overfitting)提升算法能夠有效地防止過擬合現(xiàn)象的發(fā)生。提升算法是一種為了擬合自適應(yīng)基函數(shù)模型(adaptivebasis-functionmodels,ABM)的貪心算法，自適應(yīng)基函數(shù)模型可表達為：f(X)=w+w(X)(6-1)0mmm=1其中，是一種分類算法或者回歸算法，被稱為弱分類器(weaklearner)或者基分類m器(baselearner)o也可以表達為如下形式：f(X)=第卩b(X;y)(6-2)mm提升算法的目的是對以下公式的優(yōu)化：6-3)min*L(y,f(x)fi=i11其中，L(y，y)稱為損失函數(shù)(lossfunction),f是ABM模型。不

3、同的損失函數(shù)有著不同的性質(zhì)，對應(yīng)不同的提升算法，如表1所示。6-4)將(2)式代入(3)式可得如下表達式：min乙I/WmJ詢mim丿因為學習的是加法模型，如果能夠從前向后，每一步只學習一個基分類器及其系數(shù)，那么就可以簡化優(yōu)化的復(fù)雜度，具體推導(dǎo)過程如下所示：6-5)min、L(y,卩Q(x;y)6丫imimmj=表1常見損失函數(shù)以及相應(yīng)提升算法名稱損失函數(shù)導(dǎo)數(shù)f*算法平差誤；(y-f(x)b2iiy-f(x)iiL2Boosting絕對誤差Gradient指數(shù)損失對數(shù)損失|y-f(x)|iiiii-()()_exp-yf(x/-yexp-yf(x)logiiiii21-兀iTkisgny-f(

4、x)mediary|x)boostingAdaBoostIog1+e-yifiIIy-兀iiLogitBoostf(X)=argminL(y,0yiii=1(卩,y)=argminL(y,f(x)+卩Q(x;y)mmim-1ii卩,yi=1f(X)=f(X)+卩0(X;y)mm-1mm算法不進行回溯對參數(shù)進行修改，因此該算法稱為前向分步算法6.2AdaBoost算法6-6)6-7)6-8)AdaBoost(Adaptiveboosting)算法，也稱為自適應(yīng)提升算法。訓(xùn)練數(shù)據(jù)中的每個樣本，并賦予其一個權(quán)重，這些權(quán)重構(gòu)成向量D。一開始，這些權(quán)重都初始化為相等值，首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個弱分類器

5、并計算該分類器的錯誤率，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器。再次訓(xùn)練分類器的過程中，將會重新調(diào)整每個樣本的權(quán)重，其中上一次分對的樣本權(quán)重會降低，而上一次分錯的樣本權(quán)重會提高。分類器分類器10.87圖2AdaBoost算法示意圖給定一個二類分類的訓(xùn)練數(shù)據(jù)集T=（x,y）,（x,y）,Xy），其中，每個樣本點由實例與標記組成，實例x二Rn，標記yG丫=l；1，；是實例空間，Y是標記集合。損失函數(shù)可以表達為：L=細exp-y(f(x)+卩Q(x)=細wexp-卩yQ(x)心Y*mim-1iii,mi=1i=1其中，wexp-yf(x)，yw1汁小則可以有如卞推導(dǎo)：i,mim-1iiL(妨=e邛工w+

6、邙工w=(環(huán)e_卩丿)mi,mi,myi“(xi)X神(x”工nwj(y冷(x)i_1i,mijmiNwi_1i,mi=1ywI(yhQ(x)+e卩wi,miii,mi_16-9)6-10)其中，t;m個分類器：1-errlogmerrmerrmerr稱為分類誤差率。m則可以得到第f（X）=f（X）+卩e（x）m介1m6-11)計算第m+1個分類器的參數(shù)可以通過下式得到：wi,m+1_we_py.e(x)_we(2I(y詡(x)-1)_we2卩I(y詢(x)e-卩mimimimimimimi,mi,mi,m總結(jié)起來Adaboost算法主要有以卞7步。(6-12)wi_1Nform_1:MdoF

7、itaclassifier兇tothetrainingsetusingweightswymnwI(yh(x)i_i,ymiNwi_1i1-err_logm(a_2卩)errmm4Computeerrm5Computem6SetmwJWQI(yh(x)iimimi7Returnf(x)=sgnT工Mae(X)Lm=1mm-算法結(jié)束條件是訓(xùn)練錯誤率為0或者弱分類器數(shù)目達到用戶指定的值。在具體應(yīng)用AdaBoost算法時，可以將其總結(jié)為以下的一般流程：(1)收集數(shù)據(jù)：可以使用任意方法；準備數(shù)據(jù)：依賴于所使用弱分類器的類型，這里k-近鄰、決策樹、樸素貝葉斯、邏輯回歸、支持向量機等任意分類算法都可以作為本

8、部分弱分類器；分析數(shù)據(jù)：可使用任意方法；訓(xùn)練算法：AdaBoost算法大部分時間都用在訓(xùn)練上，分類器將多次在同一數(shù)據(jù)集上訓(xùn)練弱分類器；測試算法：計算分類錯誤率；使用算法：同支持向量機類似，AdaBoost算法預(yù)測兩個類別中的一個，如果想應(yīng)用多分類，需要做與支持向量機類似的相應(yīng)修改。6.3提升樹分類與回歸樹(Classificationandregressiontrees,CART)又稱為決策樹(decisiontree),使用分類數(shù)與回歸樹作為基本分類器的提升方法，稱為提升樹B6ostingtree)。圖3決策樹示意圖決策樹模型將空間分為數(shù)個互不相交的區(qū)域只=1,J，每一個區(qū)域作為樹的葉子節(jié)點

9、，并為每個區(qū)域分配一個參數(shù)v:fjXeRnf(x)=y(6-13)因此決策樹則可以表達為如下形式：T(x;0)=2vi(XeR)(6-14)=jj其中，0=R,vJ，該參數(shù)由最小化經(jīng)驗風險計算得到：jj16-15)0=argmin工L(y,y)0j=1X衆(zhòng)jj決策樹模型是一種傳統(tǒng)的學習方法，易于被理解，相比較人工神經(jīng)網(wǎng)絡(luò)，我們能夠清晰地了解如何構(gòu)建決策樹，而且決策樹模型無信息丟失。但是決策樹模型也存在不穩(wěn)定的缺點，訓(xùn)練樣本較小的變化會導(dǎo)致結(jié)果的較大差異。為解決這一問題，研究者主要通過提升算法來對決策樹模型進行優(yōu)化，即所謂的提升樹(Boostingtree),其基本算法思路為，構(gòu)建多個決策樹，多

10、個決策樹決策結(jié)果的加權(quán)平均對樣本的變化不敏感。提升樹模型是一系列的決策樹的和：Mm=16-16)6-17)6-18)f(x)=第T(x;0)引入前向分步算法：0=argminL(y,f(x)+T(x;0)m0mi=iim-1iimhm已知R求y:jm已知f(X)求得0=R,ym1mjmjm1jmy=argmin工L(y,f(x)+y)jmyjmxeRim-1ijm6.4基于單層決策樹的AdaBoost算法單層決策樹(decisionstump，也稱決策樹樁)是一種簡單的決策樹，僅基于單個特征來做決策，由于這棵樹只有一次分裂過程，因此它實際上就是一個樹樁。利用Python對單層決策樹進行實現(xiàn)，代

11、碼如下：defstumpClassify(dataMatrix,dimen,threshVal,threshIneq):retArray=ones(shape(dataMatrix)0,1)ifthreshIneq=lt:retArraydataMatrix:,dimenthreshVal=-1.0returnretArraydefbuildStump(dataArr,classLabels,D):dataMatrix=mat(dataArr);labelMat=mat(classLabels).Tm,n=shape(dataMatrix)numSteps=10.0;bestStump=;be

12、stClasEst=mat(zeros(m,1)minError=infforiinrange(n):rangeMin=dataMatrix:,i.min();rangeMax=dataMatrix:,i.max();stepSize=(rangeMax-rangeMin)/numStepsforjinrange(-1,int(numSteps)+1):forinequalinlt,gt:threshVal=(rangeMin+float(j)*stepSize)predictedVals=stumpClassify(dataMatrix,i,threshVal,inequal)errArr=

13、mat(ones(m,1)errArrpredictedVals=labelMat=0weightedError=D.T*errArrifweightedError-Vjlfcy9Mjfatri5筑Qxx-ain.nLuttsex:Z39tram,erloxrate：0.1572309699tCJt-ezsot:14o七estk*JT匕(T567化3匚errorlate:.Zv955223-55150個分類器wedklearnererrorraue:0eatclearnererTorrate:D.1ST15Q35452w&ak1電謹片21色才Ortit-S:;：0-.1571903545weak&xcrrac;0.15T1日0石3旨h亡耳輕|.亍f盯|3herrorrate:.l&713)fi3552weaklearnererrorrace20reak1電arnere*Tarrate:D.157190635452weaklearnereTorrate:D.151903542weakltarnererrorrate：0祐UM昴討恥trainerrGritrazrniurher:299e*aind護亢忙丄*-rat:0,157150勺客生呂2tescrrcr:17tQteat砧遼nhn；67c