GBDT算法原理以及實(shí)例理解

寫在前面：去年學(xué)習(xí)GBDT之初，為了加強(qiáng)對(duì)算法的理解，整理了一篇筆記形式的文章，發(fā)出去之后發(fā)現(xiàn)閱讀量越來越多，漸漸也有了評(píng)論，評(píng)論中大多指出來了筆者理解或者編輯的錯(cuò)誤，故重新編輯一版文章，內(nèi)容更加翔實(shí)，并且在GitHub上實(shí)現(xiàn)了和本文一致的GBDT簡(jiǎn)易版（包括回歸、二分類、多分類以及可視化），供大家交流探討。感謝各位的點(diǎn)贊和評(píng)論，希望繼續(xù)指出錯(cuò)誤~Github：

簡(jiǎn)介：

GBDT 的全稱是 Gradient Boosting Decision Tree，梯度提升樹，在傳統(tǒng)機(jī)器學(xué)習(xí)算法中，GBDT算的上TOP3的算法。想要理解GBDT的真正意義，那就必須理解GBDT中的Gradient Boosting 和Decision Tree分別是什么？

1. Decision Tree：CART回歸樹

首先，GBDT使用的決策樹是CART回歸樹，無論是處理回歸問題還是二分類以及多分類，GBDT使用的決策樹通通都是都是CART回歸樹。為什么不用CART分類樹呢？因?yàn)镚BDT每次迭代要擬合的是梯度值，是連續(xù)值所以要用回歸樹。

對(duì)于回歸樹算法來說最重要的是尋找最佳的劃分點(diǎn)，那么回歸樹中的可劃分點(diǎn)包含了所有特征的所有可取的值。在分類樹中最佳劃分點(diǎn)的判別標(biāo)準(zhǔn)是熵或者基尼系數(shù)，都是用純度來衡量的，但是在回歸樹中的樣本標(biāo)簽是連續(xù)數(shù)值，所以再使用熵之類的指標(biāo)不再合適，取而代之的是平方誤差，它能很好的評(píng)判擬合程度。

回歸樹生成算法：

輸入：訓(xùn)練數(shù)據(jù)集D:輸出：回歸樹f(x).在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸的將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域上的輸出值，構(gòu)建二叉決策樹：（1）選擇最優(yōu)切分變量jj與切分點(diǎn)s，求解

遍歷變量j，對(duì)固定的切分變量j掃描切分點(diǎn)s，選擇使得上式達(dá)到最小值的對(duì)(j,s).

（2）用選定的對(duì)(j,s)劃分區(qū)域并決定相應(yīng)的輸出值：

（3）繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步驟（1）和（2），直至滿足停止條件。

（4）將輸入空間劃分為M個(gè)區(qū)域，生成決策樹：

2. Gradient Boosting：擬合負(fù)梯度

梯度提升樹（Grandient Boosting）是提升樹（Boosting Tree）的一種改進(jìn)算法，所以在講梯度提升樹之前先來說一下提升樹。

先來個(gè)通俗理解：假如有個(gè)人30歲，我們首先用20歲去擬合，發(fā)現(xiàn)損失有10歲，這時(shí)我們用6歲去擬合剩下的損失，發(fā)現(xiàn)差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有一歲了。如果我們的迭代輪數(shù)還沒有完，可以繼續(xù)迭代下面，每一輪迭代，擬合的歲數(shù)誤差都會(huì)減小。最后將每次擬合的歲數(shù)加起來便是模型輸出的結(jié)果。

提升樹算法：

（1）初始化

（2）對(duì)m=1,2,…,M?（a）計(jì)算殘差

（b）擬合殘差學(xué)習(xí)一個(gè)回歸樹，得到

（c） 更新

（3）得到回歸問題提升樹

上面?zhèn)未a中的殘差是什么？在提升樹算法中，假設(shè)我們前一輪迭代得到的強(qiáng)學(xué)習(xí)器是

損失函數(shù)是

我們本輪迭代的目標(biāo)是找到一個(gè)弱學(xué)習(xí)器

最小化本輪的損失

當(dāng)采用平方損失函數(shù)時(shí)

這里，

是當(dāng)前模型擬合數(shù)據(jù)的殘差（residual）。所以，對(duì)于提升樹來說只需要簡(jiǎn)單地?cái)M合當(dāng)前模型的殘差。??回到我們上面講的那個(gè)通俗易懂的例子中，第一次迭代的殘差是10歲，第二次殘差4歲...

當(dāng)損失函數(shù)是平方損失和指數(shù)損失函數(shù)時(shí)，梯度提升樹每一步優(yōu)化是很簡(jiǎn)單的，但是對(duì)于一般損失函數(shù)而言，往往每一步優(yōu)化起來不那么容易，針對(duì)這一問題，F(xiàn)reidman提出了梯度提升樹算法，這是利用最速下降的近似方法，其關(guān)鍵是利用損失函數(shù)的負(fù)梯度作為提升樹算法中的殘差的近似值。那么負(fù)梯度長(zhǎng)什么樣呢？第t輪的第i個(gè)樣本的損失函數(shù)的負(fù)梯度為：

此時(shí)不同的損失函數(shù)將會(huì)得到不同的負(fù)梯度，如果選擇平方損失

負(fù)梯度為

此時(shí)我們發(fā)現(xiàn)GBDT的負(fù)梯度就是殘差，所以說對(duì)于回歸問題，我們要擬合的就是殘差。??那么對(duì)于分類問題呢？二分類和多分類的損失函數(shù)都是log loss，本文以回歸問題為例進(jìn)行講解。

3. GBDT算法原理

上面兩節(jié)分別將Decision Tree和Gradient Boosting介紹完了，下面將這兩部分組合在一起就是我們的GBDT了。

GBDT算法：（1）初始化弱學(xué)習(xí)器

（2）對(duì)m=1,2,…,M有：

（a）對(duì)每個(gè)樣本i=1,2,…,N，計(jì)算負(fù)梯度，即殘差

（b）將上步得到的殘差作為樣本新的真實(shí)值，并將數(shù)據(jù)作為下棵樹的訓(xùn)練數(shù)據(jù)，得到一顆新的回歸樹，其對(duì)應(yīng)的葉子節(jié)點(diǎn)區(qū)域?yàn)?img src="http://file.elecfans.com/web1/M00/90/3B/o4YBAFzFaWSAW5aUAAABVyvjO4s875.png" />，。其中J為回歸樹t的葉子節(jié)點(diǎn)的個(gè)數(shù)。

（c）對(duì)葉子區(qū)域j =1,2,..J計(jì)算最佳擬合值

（d）更新強(qiáng)學(xué)習(xí)器

（3）得到最終學(xué)習(xí)器

4. 實(shí)例詳解

==本人用python以及pandas庫實(shí)現(xiàn)GBDT的簡(jiǎn)易版本，在下面的例子中用到的數(shù)據(jù)都在github可以找到，大家可以結(jié)合代碼和下面的例子進(jìn)行理解，歡迎star~==??Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

數(shù)據(jù)介紹：

如下表所示：一組數(shù)據(jù)，特征為年齡、體重，身高為標(biāo)簽值。共有5條數(shù)據(jù)，前四條為訓(xùn)練樣本，最后一條為要預(yù)測(cè)的樣本。

訓(xùn)練階段：

參數(shù)設(shè)置：

學(xué)習(xí)率：learning_rate=0.1

迭代次數(shù)：n_trees=5

樹的深度：max_depth=3

1.初始化弱學(xué)習(xí)器:

損失函數(shù)為平方損失，因?yàn)槠椒綋p失函數(shù)是一個(gè)凸函數(shù)，直接求導(dǎo)，倒數(shù)等于零，得到c。

令導(dǎo)數(shù)等于0

所以初始化時(shí)，c取值為所有訓(xùn)練樣本標(biāo)簽值的均值。c=(1.1+1.3+1.7+1.8)/4=1.475，此時(shí)得到初始學(xué)習(xí)器

2.對(duì)迭代輪數(shù)m=1，2,…,M:??由于我們?cè)O(shè)置了迭代次數(shù)：n_trees=5，這里的M=5。??計(jì)算負(fù)梯度，根據(jù)上文損失函數(shù)為平方損失時(shí)，負(fù)梯度就是殘差殘差，再直白一點(diǎn)就是y與上一輪得到的學(xué)習(xí)器的差值

殘差在下表列出：

此時(shí)將殘差作為樣本的真實(shí)值來訓(xùn)練弱學(xué)習(xí)器，即下表數(shù)據(jù)：

接著，尋找回歸樹的最佳劃分節(jié)點(diǎn)，遍歷每個(gè)特征的每個(gè)可能取值。從年齡特征的5開始，到體重特征的70結(jié)束，分別計(jì)算分裂后兩組數(shù)據(jù)的平方損失（Square Error），左節(jié)點(diǎn)平方損失，右節(jié)點(diǎn)平方損失，找到使平方損失和最小的那個(gè)劃分節(jié)點(diǎn)，即為最佳劃分節(jié)點(diǎn)。

例如：以年齡7為劃分節(jié)點(diǎn)，將小于7的樣本劃分為到左節(jié)點(diǎn)，大于等于7的樣本劃分為右節(jié)點(diǎn)。

左節(jié)點(diǎn)包括，右節(jié)點(diǎn)包括樣本，，所有可能劃分情況如下表所示：

以上劃分點(diǎn)是的總平方損失最小為0.025有兩個(gè)劃分點(diǎn)：年齡21和體重60，所以隨機(jī)選一個(gè)作為劃分點(diǎn)，這里我們選年齡21??現(xiàn)在我們的第一棵樹長(zhǎng)這個(gè)樣子：

我們?cè)O(shè)置的參數(shù)中樹的深度max_depth=3，現(xiàn)在樹的深度只有2，需要再進(jìn)行一次劃分，這次劃分要對(duì)左右兩個(gè)節(jié)點(diǎn)分別進(jìn)行劃分：

對(duì)于左節(jié)點(diǎn)，只含有0,1兩個(gè)樣本，根據(jù)下表我們選擇年齡7劃分

對(duì)于右節(jié)點(diǎn)，只含有2,3兩個(gè)樣本，根據(jù)下表我們選擇年齡30劃分（也可以選體重70）

現(xiàn)在我們的第一棵樹長(zhǎng)這個(gè)樣子：

此時(shí)我們的樹深度滿足了設(shè)置，還需要做一件事情，給這每個(gè)葉子節(jié)點(diǎn)分別賦一個(gè)參數(shù)Υ，來擬合殘差。

這里其實(shí)和上面初始化學(xué)習(xí)器是一個(gè)道理，平方損失求導(dǎo)，令導(dǎo)數(shù)等于零，化簡(jiǎn)之后得到每個(gè)葉子節(jié)點(diǎn)的參數(shù)Υ，其實(shí)就是標(biāo)簽值的均值。這個(gè)地方的標(biāo)簽值不是原始的 y，而是本輪要擬合的標(biāo)殘差。

根據(jù)上述劃分結(jié)果，為了方便表示，規(guī)定從左到右為第1,2,3,4個(gè)葉子結(jié)點(diǎn)

此時(shí)的樹長(zhǎng)這個(gè)樣子：

此時(shí)可更新強(qiáng)學(xué)習(xí)器，需要用到參數(shù)學(xué)習(xí)率：learning_rate=0.1，用lr表示。

為什么要用學(xué)習(xí)率呢？這是Shrinkage的思想，如果每次都全部加上（學(xué)習(xí)率為1）很容易一步學(xué)到位導(dǎo)致過擬合。

重復(fù)此步驟，直到m>5結(jié)束，最后生成5棵樹。下面將展示每棵樹最終的結(jié)構(gòu)，這些圖都是GitHub上的代碼生成的，感興趣的同學(xué)可以去一探究竟

Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial第一棵樹：

第二棵樹：

第三棵樹：

第四棵樹：

第五棵樹：

4.得到最后的強(qiáng)學(xué)習(xí)器：

5.預(yù)測(cè)樣本5：

在中，樣本4的年齡為25，大于劃分節(jié)點(diǎn)21歲，又小于30歲，所以被預(yù)測(cè)為0.2250。

在中，樣本4的…此處省略…所以被預(yù)測(cè)為0.2025

==為什么是0.2025？這是根據(jù)第二顆樹得到的，可以GitHub簡(jiǎn)單運(yùn)行一下代碼==

在中，樣本4的…此處省略…所以被預(yù)測(cè)為0.1823

在中，樣本4的…此處省略…所以被預(yù)測(cè)為0.1640

在中，樣本4的…此處省略…所以被預(yù)測(cè)為0.1476

最終預(yù)測(cè)結(jié)果：