Gradient Boosted Decision Trees详解
感受
GBDT集成方法的一種，就是根據(jù)每次剩余的殘差，即損失函數(shù)的值。在殘差減少的方向上建立一個(gè)新的模型的方法，直到達(dá)到一定擬合精度后停止。我找了一個(gè)相關(guān)的例子來(lái)幫助理解。本文結(jié)合了多篇博客和書(shū)，試圖完整介紹GBDT的內(nèi)容，歡迎大家來(lái)指正。
介紹
GBDT是一個(gè)應(yīng)用很廣泛的算法，可以用來(lái)做分類、回歸。GBDT這個(gè)算法還有其它名字，如MART(Multiple AdditiveRegression Tree)，GBRT(Gradient Boost Regression Tree),TreeNet等等。Gradient Boost其實(shí)是一個(gè)框架，里面可以套入很多不同的算法。
原始的Boost算法是在算法開(kāi)始的時(shí)候，為每一個(gè)樣本賦上一個(gè)權(quán)重值，初始的時(shí)候，大家都是一樣重要的。在每一步訓(xùn)練中得到的模型，會(huì)使得數(shù)據(jù)點(diǎn)的估計(jì)有對(duì)有錯(cuò)，我們就在每一步結(jié)束后，增加分錯(cuò)的點(diǎn)的權(quán)重，減少分對(duì)點(diǎn)的權(quán)重，這樣使得某些點(diǎn)如果老師被分錯(cuò)，那么就會(huì)被“嚴(yán)重關(guān)注”，也就被賦上一個(gè)很高的權(quán)重。然后等進(jìn)行了N次迭代（由用戶指定），將得到N個(gè)簡(jiǎn)單的分類器（basic learner），然后我們將它們組合起來(lái)（比如說(shuō)可以對(duì)它們進(jìn)行加權(quán)、或者讓它們進(jìn)行投票等），得到一個(gè)最終的模型。
Gradient Boost與傳統(tǒng)的Boost的區(qū)別是，每一次的計(jì)算是為了減少上一次的殘差（residual），而為了消除殘差，我們可以在殘差減少的梯度方向上建立一個(gè)新的模型。所以說(shuō)，在Gradient Boost中，每個(gè)新模型的建立是為了使得之前模型的殘差梯度方向減少，對(duì)傳統(tǒng)Boost對(duì)正確，錯(cuò)誤的樣本進(jìn)行加權(quán)有很大的區(qū)別。
在GBDT的迭代中，假設(shè)我們前一輪迭代得到的強(qiáng)學(xué)習(xí)器是ft-1(x),損失函數(shù)是L(yi,ft-1(x))，我們本輪迭代的目標(biāo)是找到一個(gè)CART回歸樹(shù)模型的弱學(xué)習(xí)器ht(x),讓本輪的損失L(yi,ft(x)=L(yi,ft-1(x))+ht(x)最小。也就是說(shuō)，本輪迭代找到?jīng)Q策樹(shù)，要讓樣本的損失盡量變得更小。
GBDT的思想用一個(gè)通俗的例子解釋，加入有個(gè)人30歲，我們首先用20歲去擬合，發(fā)現(xiàn)損失有10歲，這時(shí)我們用6歲去擬合剩下的損失，發(fā)現(xiàn)差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有1歲了。如果我們的迭代輪數(shù)還沒(méi)有完，可以繼續(xù)往下迭代，每一輪迭代，擬合的歲數(shù)誤差都會(huì)減小。
上圖為一個(gè)GBDT的例子，表示預(yù)測(cè)一個(gè)人是否喜歡電腦游戲。
GBDT梯度提升決策樹(shù)算法是在決策樹(shù)的基礎(chǔ)上引入GB（逐步提升）和shrinkage（小幅縮進(jìn)）兩種思想，從而提升普通決策樹(shù)的泛化能力。核心點(diǎn)在于GBDT的結(jié)果是多顆決策樹(shù)預(yù)測(cè)值的累加，而殘差則是每棵決策樹(shù)的學(xué)習(xí)目標(biāo)。GBDT是回歸樹(shù)而不是分類樹(shù)，調(diào)整后可用于分類。
從上面的例子看這個(gè)思想還是蠻簡(jiǎn)單的，但是有個(gè)問(wèn)題是這個(gè)損失的擬合不好度量，損失函數(shù)各種各樣，怎么找到一種通用的擬合方法呢？
概念
GBDT的負(fù)梯度擬合
針對(duì)損失函數(shù)擬合方法的問(wèn)題，大牛Fredman提出了用損失函數(shù)的負(fù)梯度來(lái)擬合本輪損失的近似值，進(jìn)而擬合一個(gè)CART回歸樹(shù)。第t輪的第i個(gè)樣本的損失函數(shù)的負(fù)梯度表示為：
利用（xi,rti）(i=1,2,…,m),我們可以擬合一個(gè)CART回歸樹(shù)，得到了第t個(gè)回歸樹(shù)，其對(duì)應(yīng)的葉結(jié)點(diǎn)區(qū)域Rtj,j=1,2,…,J.其中J為葉子結(jié)點(diǎn)的個(gè)數(shù)。
針對(duì)每一個(gè)葉子結(jié)點(diǎn)里的樣本，我們求出使損失函數(shù)最小，也就是擬合葉子結(jié)點(diǎn)最好的輸出值cij如下：
這樣我們就得到了本輪的決策樹(shù)擬合函數(shù)如下：
從而本輪最終得到的強(qiáng)學(xué)習(xí)器的表達(dá)式如下：
通過(guò)損失函數(shù)的負(fù)梯度來(lái)擬合，我們找到了一種通用的擬合損失誤差的辦法，這樣無(wú)論是分裂問(wèn)題還是回歸問(wèn)題，我們通過(guò)其損失函數(shù)的負(fù)梯度的擬合，就可以用GBDT來(lái)解決我們的分類回歸問(wèn)題，區(qū)別僅僅在于損失函數(shù)不同導(dǎo)致的負(fù)梯度不同而已。
決策樹(shù)
決策樹(shù)時(shí)一個(gè)類似于流程圖的結(jié)構(gòu)，每個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)屬性的測(cè)試，每個(gè)分支代表測(cè)試的結(jié)果，每個(gè)葉子結(jié)點(diǎn)代表分類的結(jié)果。從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)代表分類的規(guī)則。
詳細(xì)了解的話可以參考我的博客http://blog.csdn.net/w5688414/article/details/77920930
上圖是一個(gè)決策樹(shù)的例子。
信息熵：
樣本集為D,Pk(k=1,2,…,Y)代表樣本集D中第k個(gè)樣本的比例。決策樹(shù)就是每次選擇一個(gè)屬性劃分使得Ent(D)最小。
決策樹(shù)有很多算法，ID3,CART的區(qū)別是所選擇的劃分標(biāo)準(zhǔn)不一樣，ID3選擇的是信息增益，當(dāng)CART是分類樹(shù)時(shí)，采用GINI值作為節(jié)點(diǎn)分裂的依據(jù)；當(dāng)CART是回歸樹(shù)時(shí)，采用樣本的最小方差作為節(jié)點(diǎn)分裂的依據(jù)；。
分裂特征為a’，值為v’.DL是樣本val(x,a’)<=v’ 的集合.DR是樣本val(x,a’)>v’的集合.D=DL∪DR。
選擇分裂點(diǎn)的依據(jù)：
對(duì)于決策樹(shù)模型，分類和回歸的損失函數(shù)可以用戶自定義，通常，掃描所有分裂點(diǎn)的代價(jià)很大，所以有一些近似算法（這個(gè)自行百度了），為了避免過(guò)擬合，常用的方法是后剪枝。
集成學(xué)習(xí)
集成方法就是使用多種學(xué)習(xí)算法去獲得更好的預(yù)測(cè)性能的方法，典型的集成方法有很多，如AdaBoost，隨機(jī)森林（Random Forest），GBDT。前面的兩種算法不是本文講的內(nèi)容，本文主要解析一下GBDT算法。
損失函數(shù)
算法
回歸算法
當(dāng)GBDT用于回歸時(shí)，常用的損失函數(shù)包括平方損失函數(shù)、絕對(duì)值損失函數(shù)、Huber損失函數(shù)。每次朝著損失函數(shù)的負(fù)梯度方向移動(dòng)即可取得損失函數(shù)的最小值。
輸入：訓(xùn)練樣本T={(x1,y1),(x2,y2),…,(xm,ym) },最大迭代次數(shù)是T,損失函樹(shù)為L(zhǎng).
輸出：強(qiáng)學(xué)習(xí)器f(x)
1)?????初始化弱分類器
2)?????對(duì)迭代輪數(shù)t=1,2,…,T有：
a)?????對(duì)樣本i=1,2,…,m,計(jì)算負(fù)梯度：
??????
b)?????利用(xi,rti)(i=1,2,…,m)，擬合一個(gè)CART回歸樹(shù)，得到第t顆回歸樹(shù)，其對(duì)應(yīng)的葉子結(jié)點(diǎn)區(qū)域?yàn)镽tj,j=1,2,…,J. 其中J為回歸樹(shù)t的葉子結(jié)點(diǎn)的個(gè)數(shù)。
c)?????對(duì)葉子區(qū)域j=1,2,…,J.計(jì)算最佳擬合值
????????d)?????更新強(qiáng)學(xué)習(xí)器
???????
3）得到強(qiáng)學(xué)習(xí)器f(x)的表達(dá)式
分類算法
當(dāng)GBDT用于分類時(shí)，常用的損失函數(shù)有對(duì)數(shù)損失函數(shù)、指數(shù)損失函數(shù)等。這種損失函數(shù)的目的是求預(yù)測(cè)值為真實(shí)值的概率。
二元分類
對(duì)于二元GBDT,如果用類似于邏輯回歸的對(duì)數(shù)似然損失函數(shù)，其損失函數(shù)為：
其中y∈{-1,+1}，則此時(shí)的負(fù)梯度誤差為
對(duì)于生成的決策樹(shù)，我們各個(gè)葉子結(jié)點(diǎn)的最佳殘差擬合值為
由于上式比較難優(yōu)化，我們一般使用近似值代替：
除了負(fù)梯度計(jì)算和葉子結(jié)點(diǎn)的最佳殘差擬合的線性搜索，二元GBDT回歸算法和GBDT回歸算法過(guò)程相同。
多元分類
多元GBDT比二元GBDT復(fù)雜一些，對(duì)應(yīng)的是多元邏輯回歸和二元邏輯回歸。假設(shè)類別為K,則此時(shí)我們的對(duì)數(shù)似然損失函數(shù)為：
其中如果樣本輸出類別為K,則yk=1。第k類的概率pk(x)的表達(dá)式為：
集合兩式，我們可以計(jì)算出第i個(gè)樣本對(duì)應(yīng)類別l的負(fù)梯度誤差為
（分母多了個(gè)括號(hào)）
觀察上式可以看出，其實(shí)這里的誤差就是樣本i對(duì)應(yīng)的類別l的真實(shí)概率和t-1輪預(yù)測(cè)概率的差值。
對(duì)于生成的決策樹(shù)，我們各個(gè)葉子結(jié)點(diǎn)的最佳殘差擬合值為
由于上式比較難優(yōu)化，我們一般使用近似值代替
除了負(fù)梯度計(jì)算和葉子結(jié)點(diǎn)的最佳殘差擬合的線性搜索，多元GBDT分類和二元GBDT分類以及回歸算法過(guò)程相似。
GBDT優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
1) 可以靈活處理各種類型的數(shù)據(jù)，包括連續(xù)值和離散值。
2) 在相對(duì)少的調(diào)參時(shí)間情況下，預(yù)測(cè)的準(zhǔn)確率也可以比較高。這個(gè)是相對(duì)SVM來(lái)說(shuō)的。
3）使用一些健壯的損失函數(shù)，對(duì)異常值的魯棒性非常強(qiáng)。比如 Huber損失函數(shù)（huber詳細(xì)見(jiàn)本文的損失函數(shù)模塊）和Quantile損失函數(shù)。
缺點(diǎn)
1) 由于弱學(xué)習(xí)器之間存在依賴關(guān)系，難以并行訓(xùn)練數(shù)據(jù)。不過(guò)可以通過(guò)自采樣的SGBT（Stochastic Gradient Boosting Tree）來(lái)達(dá)到部分并行。
例子
這個(gè)例子不是一個(gè)典型的GBDT的例子，沒(méi)有用到負(fù)梯度求解，但是過(guò)程和GBDT一樣，并且有明確的計(jì)算過(guò)程，可以幫助理解GBDT的過(guò)程，值得借鑒。實(shí)際問(wèn)題比這個(gè)簡(jiǎn)單的例子復(fù)雜得多。
已知如表8.2所示的訓(xùn)練數(shù)據(jù)，x的取值范圍為區(qū)間[0.5,10.5]，y的取值范圍為區(qū)間[5.0,10.0]，學(xué)習(xí)這個(gè)回歸問(wèn)題的boosted tree模型，考慮只用樹(shù)樁作為基本函數(shù)。損失函數(shù)是誤差的平方和。
按照算法，第1步求f1(x)即回歸樹(shù)T1(x)。
首先通過(guò)以下優(yōu)化問(wèn)題：
求解訓(xùn)練數(shù)據(jù)的切分點(diǎn)s:
容易求得在R1,R2內(nèi)部使平方損失誤差達(dá)到最小值的c1,c2為
這里N1,N2是R1,R2的樣本點(diǎn)數(shù)。
現(xiàn)將s及m(x)的計(jì)算結(jié)果列表如下：
用f1(x)擬合訓(xùn)練數(shù)據(jù)的殘差見(jiàn)表8.4，表中r2i=yi-f1(xi),i=1,2,…,10
用f1(x)擬合訓(xùn)練數(shù)據(jù)的平方損失誤差：
第2步求T2(x)。方法與求T1(x)一樣，只是擬合的數(shù)據(jù)表8.4的殘差。可以得到：
用f2(x)擬合訓(xùn)練數(shù)據(jù)的平方損失誤差是
繼續(xù)求得
用f6(x)擬合訓(xùn)練數(shù)據(jù)的平方損失誤差是
假設(shè)此時(shí)已滿足誤差要求，那么f(x)=f6(x)即為所求提升樹(shù)。讀者可以手算一下，計(jì)算量還是有點(diǎn)大，畢竟有那么多求和和求均值，還有平方和。
參考文獻(xiàn)
[1]. Gradient boosting. https://en.wikipedia.org/wiki/Gradient_boosting
[2]. 梯度提升樹(shù)(GBDT)原理小結(jié)
[3]. 決策樹(shù)系列（五）——CART
[4] GBDT(Gradient Boosting Decision Tree) 沒(méi)有實(shí)現(xiàn)只有原理
[5].李航.《統(tǒng)計(jì)機(jī)器學(xué)習(xí)》?
?
總結(jié)
以上是生活随笔為你收集整理的Gradient Boosted Decision Trees详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： Spark MLlib: Decisio
- 下一篇： spark.mllib源码阅读：Grad