如果你还不了解GBDT，不妨看看这篇文章
作者：Freemanzxp
簡介：中科大研二在讀，目前在微軟亞洲研究院實習，主要研究方向是機器學習。
原文：https://blog.csdn.net/zpalyq110/article/details/79527653
Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial
本文已授權，未經原作者允許，不得二次轉載
寫在前面： 去年學習 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:
https://github.com/Freemanzxp/GBDT_Simple_Tutorial
參考資料
李航 《統計學習方法》
Friedman J H . Greedy Function Approximation: A Gradient Boosting Machine[J]. The Annals of Statistics, 2001, 29(5):1189-1232.
歡迎關注我的微信公眾號--機器學習與計算機視覺，或者掃描下方的二維碼，大家一起交流，學習和進步！
總結
以上是生活随笔為你收集整理的如果你还不了解GBDT，不妨看看这篇文章的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Web前端第一季(HTML):十四:课时
- 下一篇： 数据库优化：SqlServer的with