GBDT相對于經(jīng)典的決策樹，算是一種比較成熟而且可以實(shí)際應(yīng)用的決策樹算法了。我們想要理解GBDT這種決策樹，得先從感性上理解這棵樹的工作方式。
首先我們要了解到，DBDT是一種回歸樹(Regression Decision tree)?；貧w樹與分類樹的差距請看我的文章《經(jīng)典的回歸樹算法》。
我們知道，分類樹在每一次分支的時(shí)候，窮舉每一個(gè)特征的每一個(gè)閾值，然后按照大于或者小于閾值的方式將其相互分開。這就是分類樹的算法。
而回歸樹也十分類似，但是在每個(gè)節(jié)點(diǎn)都會(huì)得到一個(gè)預(yù)測值。

以年齡為例，該預(yù)測值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化均方差--即（每個(gè)人的年齡-預(yù)測年齡）^2 的總和 / N，或者說是每個(gè)人的預(yù)測誤差平方和 除以 N。這很好理解，被預(yù)測出錯(cuò)的人數(shù)越多，錯(cuò)的越離譜，均方差就越大，通過最小化均方差能夠找到最靠譜的分枝依據(jù)。分枝直到每個(gè)葉子節(jié)點(diǎn)上人的年齡都唯一（這太難了）或者達(dá)到預(yù)設(shè)的終止條件（如葉子個(gè)數(shù)上限），若最終葉子節(jié)點(diǎn)上人的年齡不唯一，則以該節(jié)點(diǎn)上所有人的平均年齡做為該葉子節(jié)點(diǎn)的預(yù)測年齡。

BDT(Boosting Decision Tree 提升決策樹)

這其實(shí)是一個(gè)很好的思維方式。
Boosting，提升。這涉及到機(jī)器學(xué)習(xí)中的集成學(xué)習(xí)。原理就是通過多個(gè)特征生成多個(gè)樹，來決策一件事情。也就是“三個(gè)臭皮匠，頂一個(gè)諸葛亮”的原理。這是如何實(shí)現(xiàn)的呢？我們舉一個(gè)簡單的例子。BDT的核心就在于，每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加預(yù)測值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，我們訓(xùn)練的時(shí)候，第一棵樹的擬合過后預(yù)測年齡是12歲，我們與真實(shí)數(shù)據(jù)比對差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去擬合學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹的結(jié)論就是A的真實(shí)年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)。
如果還有疑問，請看下面這個(gè)例子：
還是年齡預(yù)測，簡單起見訓(xùn)練集只有4個(gè)人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練，會(huì)得到如下圖1所示結(jié)果：

傳統(tǒng)回歸樹模型(圖片來自網(wǎng)絡(luò))

這是一棵普通的回歸樹，我們可以看到，我們通過年齡平均值將少年和青年分開
，再用上網(wǎng)時(shí)長將每個(gè)分支繼續(xù)細(xì)分到不能分割或者達(dá)到要求為止。
接下來看BDT實(shí)現(xiàn)：

BDT模型(圖片來自網(wǎng)絡(luò))

在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測值 + A的殘差 = A的實(shí)際值），所以A的殘差就是16-15=1（注意，A的預(yù)測值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來作為A的預(yù)測值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹去學(xué)習(xí)，如果我們的預(yù)測值和它們的殘差相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測值。

換句話說，現(xiàn)在A,B,C,D的預(yù)測值都和真實(shí)年齡一致了:

1. 14歲高一學(xué)生，購物較少，經(jīng)常問學(xué)長問題；預(yù)測年齡A = 15 – 1 = 14

2. 16歲高三學(xué)生；購物較少，經(jīng)常被學(xué)弟問問題；預(yù)測年齡B = 15 + 1 = 16

3. 24歲應(yīng)屆畢業(yè)生；購物較多，經(jīng)常問師兄問題；預(yù)測年齡C = 25 – 1 = 24

4. 26歲工作兩年員工；購物較多，經(jīng)常被師弟問問題；預(yù)測年齡D = 25 + 1 = 26

GBDT核心思想就是這樣，但是既然普通的樹和GBDT結(jié)果一樣，那為什么還需要GBDT呢？
原因就是過擬合。過擬合就是模型在訓(xùn)練數(shù)據(jù)集上表現(xiàn)的過于好，分的過于細(xì)。以致于容錯(cuò)能力很低，也可以稱作”泛化能力“低。這就會(huì)導(dǎo)致在實(shí)際測試數(shù)據(jù)中表現(xiàn)明顯差很多。我們發(fā)現(xiàn)圖1為了達(dá)到100%精度使用了3個(gè)feature（上網(wǎng)時(shí)長、時(shí)段、網(wǎng)購金額），其中分枝“上網(wǎng)時(shí)長>1.1h” 很顯然已經(jīng)過擬合了，這個(gè)數(shù)據(jù)集上A,B也許恰好A每天上網(wǎng)1.09h, B上網(wǎng)1.05小時(shí)，但用上網(wǎng)時(shí)間是不是>1.1小時(shí)來判斷所有人的年齡很顯然是有悖常識的；
相對來說圖2的boosting雖然用了兩棵樹 ，但其實(shí)只用了2個(gè)feature就搞定了，后一個(gè)feature是問答比例，顯然圖2的依據(jù)更靠譜（這是杜撰的數(shù)據(jù)，為了顯示效果夸張的一下，實(shí)際有實(shí)驗(yàn)證明以上論點(diǎn)）。

GB(Gradient Boosting 梯度提升)

我們前面一直都在討論GBDT的基本原理，是從宏觀上對于這種算法有個(gè)感性的認(rèn)識。但是我們要想進(jìn)一步理解GBDT，就得知道負(fù)梯度擬合，或者我們也叫梯度提升。
我們都知道，在機(jī)器學(xué)習(xí)算法中，為了降低誤差函數(shù)，我們會(huì)有一個(gè)方法叫做梯度下降法。其做法是誤差函數(shù)中，每一步都走當(dāng)前的梯度方向，也就是下降最快的方向進(jìn)行下降，這樣多次迭代步長之后，誤差函數(shù)就會(huì)降到一個(gè)局部最低點(diǎn)（凸函數(shù)中也是全局最低點(diǎn)），也就得到了最小的誤差函數(shù)。
我們嘗試使用這種方法去訓(xùn)練一棵回歸樹，或者更精確的說，是一棵CART，如有朋友不太熟悉CART，請看我之前的文章《CART》。正如前面所提到，我們GBDT每次訓(xùn)練的時(shí)候都是擬合上一棵樹的殘差，那么我們使用損失函數(shù)來擬合這棵樹:

損失函數(shù)擬合一棵決策樹

使用損失函數(shù)的負(fù)梯度來擬合它的殘差：

這樣將所有的負(fù)梯度加起來之后就會(huì)得到一個(gè)整體的梯度下降。使得整個(gè)系統(tǒng)的誤差函數(shù)最小。
我貼出梯度提升算法以輔助理解，內(nèi)容來自李航的《統(tǒng)計(jì)學(xué)習(xí)方法》：

梯度提升算法過程

我們來看看這梯度提升算法的流程：

1. 我們先初始化第一棵回歸樹，使這個(gè)分界點(diǎn)讓整體誤差最小。具體細(xì)節(jié)上為什么初始化成這種形式，請看我之前寫過的文章《CART》;

2. 我們每生成一棵樹之后，就將這棵樹的每一條數(shù)據(jù)的損失函數(shù)的梯度求出來；損失函數(shù)我們一般寫作是均方誤差，每個(gè)數(shù)據(jù)與切分點(diǎn)之間的均方差就是損失函數(shù)；

3. 求出每個(gè)數(shù)據(jù)的負(fù)梯度之后，我們依據(jù)已有數(shù)據(jù)和每個(gè)數(shù)據(jù)的負(fù)梯度，生成一個(gè)新樹出來，我們先將每個(gè)數(shù)據(jù)的負(fù)梯度當(dāng)作新的數(shù)據(jù)的yi，這樣就得到了一組新數(shù)據(jù)，也確定了新數(shù)據(jù)的空間劃分。然后再計(jì)算每一條數(shù)據(jù)的誤差函數(shù)，取誤差函數(shù)最小的那個(gè)點(diǎn)做為下一個(gè)分支切分點(diǎn)，這也就生成了一顆新樹；

4. 我們將新樹加到原來那棵樹上；

5. 最后總和得到一棵樹；

如果不夠理解，請將這個(gè)負(fù)梯度擬合的殘差直接帶入之前文章《CART》例子中的殘差數(shù)據(jù)中去，這樣就有一個(gè)例子可供參考輔助理解。

作者：香橙云子
鏈接：https:///post/5a1624d9f265da43310d79d5
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。