標籤：

機器學習之梯度提升決策樹(GBDT)

05-16

由於較多公式，所以我將部分內容轉為圖片進行上傳，請見諒。清晰版請訪問weizhixiaoyi.com查看，你也可以關注我公眾號謂之小一，後台直接向我要pdf版本，如有相關問題可公眾號後台詢問，隨時回答。

1.GBDT演算法簡介

GBDT(Gradient Boosting Decision Tree)是一種迭代的決策樹演算法，由多棵決策樹組成，所有樹的結論累加起來作為最終答案，我們根據其名字(Gradient Boosting Decision Tree)來展開推導過程。決策樹(Decision Tree)我們已經不再陌生，在之前介紹到的機器學習之決策樹(C4.5演算法)、機器學習之分類與回歸樹(CART)、機器學習之隨機森林中已經多次接觸，在此不再贅述。但Boosting和Gradient方法是什麼含義呢，又如何跟Decision Tree相結合?首先我們來了解集成學習中的Boosting概念。

1.1集成學習之Boosting

集成學習不是單獨的機器學習方法，而是通過構建並結合多個機器學習器來完成任務，集成學習可以用於分類問題集成、回歸問題集成、特徵選取集成、異常點檢測集成等方面。其思想是對於訓練數據集，我們通過訓練若干個個體學習器，通過一定的結合策略形成一個強學習器，以達到博採眾長的目的。在機器學習之隨機森林中我們已經用到集成學習中的bagging方法，此處我們詳細介紹集成學習中的Boosting方法。

從上圖可以看出，Boosting演算法的工作機制是從訓練集用初始權重訓練出一個弱學習器1，根據弱學習器的學習誤差率來更新訓練樣本的權重，使得之前弱學習器1中學習誤差率高的訓練樣本點權重變高。然後這些誤差率高的點在弱學習器2中得到更高的重視，利用調整權重後的訓練集來訓練弱學習器2。如此重複進行，直到弱學習器數達到事先指定的數目T，最終將這T個弱學習器通過集合策略進行整合，得到最終的強學習器。了解Boosting方法後，我們便可將Boosting方法和Decision Tree相結合便可得到Boosting Decision Tree。

1.2 Boosting Decision Tree

提升樹(Boosting Decision Tree)由於輸出樣本是連續值，因此我們通過迭代多棵回歸樹來共同決策。在機器學習之分類與回歸樹(CART)中我們已經詳細推導分類樹與回歸樹的構建過程，在此不再贅述。

我們利用平方誤差來表示損失函數，其中每一棵回歸樹學習的是之前所有樹的結論和殘差，擬合得到一個當前的殘差回歸樹。其中殘差=真實值-預測值，提升樹即是整個迭代過程生成的回歸樹的累加。

我們通過以下例子來詳解演算法過程，希望通過訓練提升樹來預測年齡。訓練集是4個人，A、B、C、D年齡分別是14、16、24、26。樣本中有購物金額、上網時長、經常到百度知道提問等特徵。提升樹的過程如下

我們能夠直觀的看到，預測值等於所有樹值的累加，如A的預測值=樹1左節點(15)+樹2左節點(-1)=14。因此給定當前決策樹模型ft-1(x)，只需擬合決策樹的殘差，便可迭代得到提升樹，演算法過程如下

我們介紹了Boosting Decision Tree的基本思路，但是沒有解決損失函數擬合方法的問題。針對這個問題，Freidman提出用損失函數的負梯度來擬合本輪損失的近似值，進而擬合一個CART回歸樹。了解Boosting Decision Tree方法後，我們便可將Gradient與Boosting Decision Tree相結合得到Gradient Boosting Decision Tree的負梯度擬合。

1.3GBDT負梯度擬合

我們利用損失函數L的負梯度來擬合本輪損失函數的近似值，進而擬合一個CART回歸樹。其中第t輪的第i個樣本的損失函數的負梯度表示為

針對每一個葉子節點中的樣本，我們求出使損失函數最小，也就是擬合葉子節點最好的輸出值ctj。其中決策樹中葉節點值已經生成一遍，此步目的是稍加改變決策樹中葉節點值，希望擬合的誤差越來越小。

這樣我們便得到本輪的決策樹擬合函數

從而本輪最終得到的強學習器表達式如下

通過損失函數的負梯度擬合，我們找到一種通用的擬合損失函數的方法，這樣無論是分類問題還是回歸問題，我們通過其損失函數的負梯度擬合，就可以用GBDT來解決我們的分類回歸問題。

2.GBDT回歸演算法

通過上述GBDT負梯度擬合我們來總結下GBDT的回歸演算法，為什麼沒有加上分類演算法是因為分類演算法的輸出是不連續的類別值，需要一些處理才能使用負梯度，我們將在下一節詳細介紹GBDT分類演算法。

3.GBDT分類演算法

GBDT分類演算法在思想上和回歸演算法沒有區別，但是由於樣本輸出不是連續的值，而是離散的類別，導致我們無法直接從輸出類別去擬合類別輸出的誤差。為解決此問題，我們嘗試用類似於邏輯回歸的對數似然損失函數的方法,也就是說我們用的是類別的預測概率值和真實概率值來擬合損失函數。對於對數似然損失函數，我們有二元分類和多元分類的區別。

3.1二元GBDT分類演算法

對於二元GBDT，如果用類似於邏輯回歸的對數似然損失函數，則損失函數表示為

對於生成的決策樹，我們各個葉子節點的最佳殘差擬合值為

由於上式比較難優化，我們一般使用近似值代替

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜索外，二元GBDT分類和GBDT回歸演算法過程相同。

3.2多元GBDT分類演算法

多元GBDT要比二元GBDT複雜一些，對應的是多元邏輯回歸和二元邏輯回歸的複雜度差別。假如類別數為K，則我們的對數似然函數為

其中如果樣本輸出類別為k，則yk=1。第k類的概率pk(x)的表達式為

集合上兩式，我們可以計算出第t輪的第i個樣本對應類別l的負梯度誤差為

其實這裡的誤差就是樣本i對應類別l的真實概率和t-1輪預測概率的差值。對於生成的決策樹，我們各個葉子節點的最佳殘差擬合值為

由於上式比較難優化，我們用近似值代替

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜索，多元GBDT分類和二元GBDT分類以及GBDT回歸演算法過程相同。

4.GBDT損失函數

對於回歸演算法，常用損失函數有均方差、絕對損失、Huber損失和分位數損失。

  • 均方差損失。

  • 絕對損失和對應的負梯度誤差。

  • Huber損失是均方差和絕對損失的折衷產物，對於遠離中心的異常點，採用絕對損失，而中心點附近採用均方差。這個界限一般用分位數點來度量，損失函數和對應的負梯度誤差如下

  • 分位數損失和負梯度誤差如下所示。其中其中theta為分位數，需要我們在回歸前指定。

對於Huber損失和分位數損失，主要用於健壯回歸，也就是減少異常點對損失函數的影響。

對於分類演算法，常用損失函數有指數損失函數和對數損失函數。

  • 對數損失函數，分為二元分類和多元分類兩種，我們已在上述3.1和3.2節進行介紹。
  • 指數損失函數

5.GBDT正則化

針對GBDT正則化，我們通過子採樣比例方法和定義步長v方法來防止過擬合。

  • 子採樣比例:通過不放回抽樣的子採樣比例（subsample），取值為(0,1]。如果取值為1，則全部樣本都使用。如果取值小於1，利用部分樣本去做GBDT的決策樹擬合。選擇小於1的比例可以減少方差，防止過擬合，但是會增加樣本擬合的偏差。因此取值不能太低，推薦在[0.5, 0.8]之間。
  • 定義步長v:針對弱學習器的迭代，我們定義步長v，取值為(0,1]。對於同樣的訓練集學習效果，較小的v意味著我們需要更多的弱學習器的迭代次數。通常我們用步長和迭代最大次數一起來決定演算法的擬合效果。

6.Sklearn實現GBDT演算法

我們經常需要通過改變參數來讓模型達到更好的分類或回歸結果，具體參數設置可參考sklearn官方教程。

from sklearn.ensemble import GradientBoostingRegressorfrom sklearn.datasets import make_regressionX,y=make_regression(n_samples=1000,n_features=4, n_informative=2,random_state=0)print(X[0:10],y[0:10])### X Number# [[-0.34323505 0.73129362 0.07077408 -0.78422138]# [-0.02852887 -0.30937759 -0.32473027 0.2847906 ]# [ 2.00921856 0.42218461 -0.48981473 -0.85152258]# [ 0.15081821 0.54565732 -0.25547079 -0.35687153]# [-0.97240289 1.49613964 1.34622107 -1.49026539]# [ 1.00610171 1.42889242 0.02479266 -0.69043143]# [ 0.77083696 0.96234174 0.24316822 0.45730965]# [ 0.8717585 -0.6374392 0.37450029 0.74681383]# [ 0.69178453 -0.23550331 0.56438821 2.01124319]# [ 0.52904524 0.14844958 0.42262862 0.47689837]]### Y Number# [ -12.63291254 2.12821377 -34.59433043 6.2021494 -18.03000376# 32.9524098 85.33550027 15.3410771 124.47105816 40.98334709]clf=GradientBoostingRegressor(n_estimators=150,learning_rate=0.6, max_depth=15,random_state=0,loss=ls)clf.fit(X,y)print(clf.predict([[1,-1,-1,1]]))# [ 25.62761791]print(clf.score(X,y))# 0.999999999987

7.GBDT優缺點

7.1優點

  • 相對少的調參時間情況下可以得到較高的準確率。
  • 可靈活處理各種類型數據，包括連續值和離散值，使用範圍廣。
  • 可使用一些健壯的損失函數，對異常值的魯棒性較強，比如Huber損失函數。

7.2缺點

  • 弱學習器之間存在依賴關係，難以並行訓練數據。

8.推廣

更多內容請關注公眾號謂之小一，若有疑問可在公眾號後台提問，隨時回答，歡迎關注，內容轉載請註明出處。

weixin.qq.com/r/Ty_4oDP (二維碼自動識別)

文章參考

  • 劉建平Pinard_梯度提升樹(GBDT)原理小結
  • taotick_GBDT梯度提升決策樹

推薦閱讀：

※OpenCV AdaBoost + Haar目標檢測技術內幕（下）
※從結構到性能，一文概述XGBoost、Light GBM和CatBoost的同與不同
※GBDT:梯度提升樹演算法

TAG:機器學習 | gbdt | boosting |