如果你還不了解GBDT，不妨看看這篇文章

作者：Freemanzxp

寫在前面： 去年學習 GBDT 之初，為了加強對算法的了解，整理了一篇筆記形式的文章，發出去之後發現閱讀量越來越多，漸漸也有了評論，評論中大多指出來了筆者了解或者編輯的錯誤，故重新編輯一版文章，内容更加翔實，并且在 GitHub 上實作了和本文一緻的 GBDT 簡易版（包括回歸、二分類、多分類以及可視化），供大家交流探讨。感謝各位的點贊和評論，希望繼續指出錯誤~Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

簡介：

GBDT 的全稱是 Gradient Boosting Decision Tree，梯度提升樹，在傳統機器學習算法中，GBDT 算得上 TOP3 的算法。想要了解 GBDT 的真正意義，那就必須了解 GBDT 中的 Gradient Boosting 和 Decision Tree 分别是什麼？

1. Decision Tree：CART回歸樹

首先，GBDT 使用的決策樹是 CART 回歸樹，無論是處理回歸問題還是二分類以及多分類，GBDT 使用的決策樹通通都是都是 CART 回歸樹。

為什麼不用 CART 分類樹呢？因為 GBDT 每次疊代要拟合的是梯度值，是連續值是以要用回歸樹。

對于回歸樹算法來說最重要的是尋找最佳的劃分點，那麼回歸樹中的可劃分點包含了所有特征的所有可取的值。在分類樹中最佳劃分點的判别标準是熵或者基尼系數，都是用純度來衡量的，但是在回歸樹中的樣本标簽是連續數值，是以再使用熵之類的名額不再合适，取而代之的是平方誤差，它能很好的評判拟合程度。

回歸樹生成算法：

輸入：訓練資料集

D

:

輸出：回歸樹

f(x)

.

在訓練資料集所在的輸入空間中，遞歸的将每個區域劃分為兩個子區域并決定每個子區域上的輸出值，建構二叉決策樹：

（1）選擇最優切分變量 

j

 與切分點 

s

，求解

周遊變量 

j

，對固定的切分變量 

j

 掃描切分點 

s

，選擇使得上式達到最小值的對 

(j,s)

（2）用標明的對 

(j,s)

劃分區域并決定相應的輸出值：

（3）繼續對兩個子區域調用步驟（1）和（2），直至滿足停止條件。

（4）将輸入空間劃分為 

M

 個區域 

，生成決策樹：

2. Gradient Boosting：拟合負梯度

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

先來個通俗了解：

假如有個人30歲，我們首先用20歲去拟合，發現損失有10歲，這時我們用6歲去拟合剩下的損失，發現差距還有4歲，第三輪我們用3歲拟合剩下的差距，差距就隻有一歲了。

如果我們的疊代輪數還沒有完，可以繼續疊代下面，每一輪疊代，拟合的歲數誤差都會減小。

最後将每次拟合的歲數加起來便是模型輸出的結果。

提升樹算法：

 （b）拟合殘差學習一個回歸樹，得到

上面僞代碼中的殘差是什麼？

損失函數是

我們本輪疊代的目标是找到一個弱學習器

最小化讓本輪的損失

當采用平方損失函數時

這裡，

是目前模型拟合資料的殘差（residual）

是以，對于提升樹來說隻需要簡單地拟合目前模型的殘差。

回到我們上面講的那個通俗易懂的例子中，第一次疊代的殘差是10歲，第二 次殘差4歲……

當損失函數是平方損失和指數損失函數時，梯度提升樹每一步優化是很簡單的，但是對于一般損失函數而言，往往每一步優化起來不那麼容易，針對這一問題，Freidman 提出了梯度提升樹算法，這是利用最速下降的近似方法，其關鍵是利用損失函數的負梯度作為提升樹算法中的殘差的近似值。

那麼負梯度長什麼樣呢？

第 t 輪的第 i 個樣本的損失函數的負梯度為：

此時不同的損失函數将會得到不同的負梯度，如果選擇平方損失

負梯度為

此時我們發現 GBDT 的負梯度就是殘差，是以說對于回歸問題，我們要拟合的就是殘差。

log(loss)

，本文以回歸問題為例進行講解。

3. GBDT算法原理

上面兩節分别将 Decision Tree 和 Gradient Boosting 介紹完了，下面将這兩部分組合在一起就是我們的 GBDT 了。

GBDT算法：

（2）對有：，計算負梯度，即殘差

作為下棵樹的訓練資料，得到一顆新的回歸樹

其對應的葉子節點區域為。其

中 J 為回歸樹 t 的葉子節點的個數。計算最佳拟合值

 （d）更新強學習器

（3）得到最終學習器

4. 執行個體詳解

本人用 python 以及 pandas 庫實作 GBDT 的簡易版本，在下面的例子中用到的資料都在 github 可以找到，大家可以結合代碼和下面的例子進行了解，歡迎 star~  

Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

資料介紹：

如下表所示：一組資料，特征為年齡、體重，身高為标簽值。共有5條資料，前四條為訓練樣本，最後一條為要預測的樣本。

訓練階段：

參數設定：

• 學習率：learning_rate=0.1
• 疊代次數：n_trees=5
• 樹的深度：max_depth=3

1.初始化弱學習器:

損失函數為平方損失，因為平方損失函數是一個凸函數，直接求導，倒數等于零，得到 c。

令導數等于0

是以初始化時，c取值為所有訓練樣本标簽值的均值。

c=(1.1+1.3+1.7+1.8)/4=1.475，此時得到初始學習器

2.對疊代輪數m=1，2,…,M:

由于我們設定了疊代次數：n_trees=5，這裡的

M=5

。的內插補點

此時将殘差作為樣本的真實值來訓練弱學習器，即下表資料

接着，尋找回歸樹的最佳劃分節點，周遊每個特征的每個可能取值。從年齡特征的5開始，到體重特征的 70 結束，分别計算分裂後兩組資料的平方損失（Square Error）， 左節點平方損失， 右節點平方損失，找到使平方損失和 最小的那個劃分節點，即為最佳劃分節點。

例如：以年齡 7 為劃分節點，将小于 7 的樣本劃分為到左節點，大于等于 7 的樣本劃分為右節點。左節點包括 x0，右節點包括樣本，，所有可能劃分情況如下表所示：

以上劃分點是的總平方損失最小為0.025有兩個劃分點：年齡21和體重60，是以随機選一個作為劃分點，這裡我們選 年齡21

現在我們的第一棵樹長這個樣子：

我們設定的參數中樹的深度

max_depth=3

，現在樹的深度隻有 2，需要再進行一次劃分，這次劃分要對左右兩個節點分别進行劃分：

對于左節點，隻含有 0,1 兩個樣本，根據下表我們選擇 年齡7 劃分

對于右節點，隻含有 2,3 兩個樣本，根據下表我們選擇 年齡30 劃分（也可以選體重70）

此時我們的樹深度滿足了設定，還需要做一件事情，給這每個葉子節點分别賦一個參數 γ，來拟合殘差。

這裡其實和上面初始化學習器是一個道理，平方損失，求導，令導數等于零，化簡之後得到每個葉子節點的參數 γ，其實就是标簽值的均值。這個地方的标簽值不是原始的 y，而是本輪要拟合的标殘差 .

根據上述劃分結果，為了友善表示，規定從左到右為第個葉子結點

此時的樹長這個樣子：

此時可更新強學習器，需要用到參數學習率：learning_rate=0.1，用 lr 表示。

為什麼要用學習率呢？這是Shrinkage的思想，如果每次都全部加上（學習率為1）很容易一步學到位導緻過拟合。

重複此步驟，直到 結束，最後生成5棵樹。

下面将展示每棵樹最終的結構，這些圖都是GitHub上的代碼生成的，感興趣的同學可以去一探究竟

https://github.com/Freemanzxp/GBDT_Simple_Tutorial

第一棵樹：

第二棵樹：

第三棵樹：

第四棵樹：

第五棵樹：

4.得到最後的強學習器：

5.預測樣本5：

中，樣本4的年齡為25，大于劃分節點21歲，又小于30歲，是以被預測為0.2250。

在中，樣本4的…此處省略…是以被預測為0.2025

為什麼是 0.2025？

這是根據第二顆樹得到的，可以 GitHub 簡單運作一下代碼

在中，樣本4的…此處省略…是以被預測為0.1823

在中，樣本4的…此處省略…是以被預測為0.1640

在中，樣本4的…此處省略…是以被預測為0.1476

最終預測結果：

5. 總結

本文章從GBDT算法的原理到執行個體詳解進行了較長的描述，但是目前隻寫了回歸問題，GitHub 上的代碼也是實作了回歸、二分類、多分類以及樹的可視化，希望大家繼續批評指正，感謝各位的關注。

Github:

參考資料

1. 李航 《統計學習方法》
2. Friedman J H . Greedy Function Approximation: A Gradient Boosting Machine[J]. The Annals of Statistics, 2001, 29(5):1189-1232.