最近做的創新項目終於要結項了，做了一個針對交通數據的時序預測模型，其中一個很重要的組成部件就是梯度提升樹GBDT了。近幾年在數據挖掘比賽中屢屢斬獲獎項的XGBoost與LightGBM都是基於GBDT演算法開發的，這裡總結一下^_^

PS：材料參考是李航老師的《統計學習方法》如有錯誤以書上為準

封面： 電影《秒速五厘米》

1. CART回歸樹

GBDT是一個集成模型，可以看做是很多個基模型的線性相加，其中的基模型就是CART回歸樹。

CART樹是一個決策樹模型，與普通的ID3，C4.5相比，CART樹的主要特徵是，他是一顆二分樹，每個節點特徵取值為「是」和「不是」。舉個例子，在ID3中如果天氣是一個特徵，那麼基於此的節點特徵取值為「晴天」、「陰天」、「雨天」，而CART樹中就是「不是晴天」與「是晴天」。

這樣的決策樹遞歸的劃分每個特徵，並且在輸入空間的每個劃分單元中確定唯一的輸出。

1.1 回歸樹生成

輸入：訓練數據集D={(x1,y1),(x2,y2),....,(xn,yn)}

輸入：一顆回歸樹 f(x)=sum_{m=1}^{M}{hat{c}_mI(xin R_m)}

一個回歸樹對應的輸入空間的一個劃分，假設已經將輸入空間劃分為M個單元R1,R2,R3....Rm，並且每個單元都有固定的輸出值cm，其中I為判別函數。

當輸入空間確定時，可以用平方誤差來表示回歸樹在訓練數據上的預測誤差：

loss=sum_{x_iin R_m}{(y_i - f(x_i))^2}

則知道單元Rm上的最優輸出值就是Rm內所有樣本xi對應yi的均值。（可以自己求導推一推）

問題是如何對輸入空間進行劃分？這裡和決策樹一樣，選擇的是遍歷所有特徵，選擇最優的特徵作為劃分，具體的方法是選擇第j個變數x^j和它的取值s作為切分變數與切分點，並定義兩個區域

R1 = {x|x^j<=s} and R2 = {x|x^j > s}

如果特徵是連續變數，那麼方法可以是

R1 = {x|x^j==s} and R2 = {x|x^j != s}

然後尋找最優的變數j和最優切分點s，具體的求解

min_{j,s}[min_{c_1}sum_{x_iin R_1}{(y_i-c_1)^2+minc_2}sum_{x_iin R_2}{(y_i-c_2)^2}]

其實就是遍歷所有j，s找到本次的最佳劃分區域了。然後對每個區域遞歸這個劃分過程，直到滿足條件為止。

多說兩句，如果是分類樹的話就比較麻煩了，一般定義目標函數為基尼指數或者交叉信息熵。

1.2 回歸樹剪枝

根據奧卡姆剃刀原理，為了使模型有更準確的預測，我們要讓模型變得盡量簡單，對於決策樹來說就是要做剪枝處理。

剪枝的損失函數可以如下表示：

C_a(T)=C(T)+alpha|T|

其中C(T)為對訓練數據的誤差，|T|為樹的節點數量，其中alpha類似於一個turning parameter，調節的是到底要精準度還是要模型的簡單性。（過擬合與欠擬合）

具體的演算法如下，先從整體樹T0開始，對內部任意節點t，比較以t作為單節點樹的損失與t作為根節點樹的損失，如果單節點比下面一棵樹還要好，就給剪掉。剪完後的樹繼續重複此過程。

2. GBDT模型

GBDT模型是一個集成模型，是很多CART樹的線性相加。

GBDT模型可以表示為以下形式，我們約定f---t-(x)表示第t輪的模型，ht(x)表示第t顆決策樹，模型定義如下：

f_t(x)=sum_{t=1}^{T}{h_t(x)}

提升樹採用前向分步演算法。第t步的模型由第t-1步的模型形成，可以寫成：

f_t(x)=f_{t-1}(x)+h_t(x)

損失函數自然定義為這樣的：

L(f_t(x),y)=L(f_{t-1}+h_t(x),y)

雖然整體思路都挺清晰的，但是怎麼確定第t步該加上一顆什麼樣的樹確是個大問題。針對這個問題， Freidman提出了用損失函數的負梯度來擬合本輪損失的近似值，進而擬合一個CART回歸樹。即每次需要擬合的是模型的負梯度。第t輪的第i個樣本的損失函數的負梯度表示為:

r_{t,i}=-[frac{delta L(y,f(x_i))}{delta f(x_i)}]

那天看了這個公式後，我整個人都蒙蔽了，說好了GBDT樹每一步是在擬合上一步的殘差呢？為什麼成了擬合模型的負梯度了，擬合梯度是什麼鬼啊，梯度不是一個方向嗎為什麼你們要擬合他？（哭唧唧）

後來終於想清楚，tm的d((y-f(x))^2) / d(f(x))不就是 y-f(x)不就是殘差嗎！！！啊啊啊啊啊啊啊啊啊！！！

這裡可以借用SGD的觀點看一看，每一步的樹相當於是往梯度方向前進一步，這樣不考慮殘差，也挺好，嘻嘻。

總之，我們可以光明正大的這樣寫了：

r_{t,i}=-[frac{delta L(y,f(x_i))}{delta f(x_i)}]=y_i-f_{m-1}(x_i)

利用(xi, rti) (i=1,2,...m),我們可以擬合一顆CART回歸樹，得到了第t顆回歸樹，其對應的葉節點區域Rtj, j=1,2,...,J。其中J為葉子節點的個數。

針對每一個葉子節點裡的樣本，我們求出使損失函數最小，也就是擬合葉子節點最好的的輸出值ctj如下(注意這裡的yi是真實值，不是殘差)：

c_{t,j}=argminsum_{x_iin R_{t,j}}{L(y_i,f_{t-1}(x_i)+c)}

此時本輪的決策樹擬合函數就得到了：

h_t(x)=sum_{j=1}^{J}{c_{t,j}I(xin R_{t,j})}

然後本輪的強學習器也就得到了：

f_t(x)=f_{t-1}(x)+sum_{j=1}^{J}{c_{t,j}I(xin R_{t,j})}

之後一直迭代下去，直到損失函數收斂，完工！


推薦閱讀：
相关文章