從回歸樹到GBDT

時間：2015-03-17 21:58:20 ???? 閱讀：3206 ???? 評論：0 ???? 收藏：0 ???? [點我收藏+]

標(biāo)簽：class???style???log???src???java???http???si???it???數(shù)據(jù)???

GBDT可以看做是由多棵回歸樹組成的，所以要理解GBDT，就要先理解回歸樹。回歸樹也是為了做預(yù)測，只是將特征空間劃分成了若干個區(qū)域，在每個區(qū)域里進行預(yù)測，舉個簡單例子。

圖中的數(shù)據(jù)有兩個特征：x1、x2，根據(jù)這兩個特征可以很容易地把數(shù)據(jù)分為左下角、左上角、右上角、右下角四個區(qū)域，這四個區(qū)域各有一個中心點（5,5）、（5,10）、（10,10）、（10,5），在對新數(shù)據(jù)做預(yù)測時，該數(shù)據(jù)落在哪個區(qū)域，就把該區(qū)域的中心點作為它的預(yù)測值。那么如何判斷新數(shù)據(jù)將落在哪個區(qū)域呢？這時候“樹”就派上用場了。樹的根節(jié)點以x1做劃分，小于8的劃分到左子樹，大于8的劃分到右子樹，在劃分好的左右子樹上再以x2做進一步的劃分，小于8的劃分為左葉子，大于8的劃分為右葉子，如下圖所示：

可以看到，回歸樹也相當(dāng)于一個映射，一個函數(shù)，即根據(jù)輸入x1、x2來求得輸出 y，表達(dá)式如下：

y=h(x)=∑j=1JbjI(x∈Rj)
其中，Rj就是一個個的區(qū)域，如第一張圖中的“左下角”、“左上角”等，如果x屬于Rj，那么它的預(yù)測值就是bj。I()為指示函數(shù)，當(dāng)括號內(nèi)的式子成立時返回1，否則返回0。

GBDT

在很多情況下，一棵回歸樹的預(yù)測是不太準(zhǔn)確的，我們可以嘗試采用多棵回歸樹去預(yù)測，第 m 棵回歸樹可以表示為如下數(shù)學(xué)形式：

hm(x)=∑jJbjmI(x∈Rjm)
假設(shè)共有M棵回歸樹，那么最終的預(yù)測結(jié)果為：
y=FM(x)=∑m=1Mhm(x)
表達(dá)成遞歸形式則為：
y=FM?1(x)+hM(x)
最完美的GBDT（就訓(xùn)練集而言，不考慮測試集）就是預(yù)測值 y 與目標(biāo)值 t 相等，所以我們建立模型的目標(biāo)就是令y=t，即：
t=FM?1(x)+hM(x)
GBDT也是從第一棵回歸樹開始的，不管效果怎么樣，先建第一棵回歸樹，有了第一棵樹，就可以通過上面的遞歸表達(dá)式建立第二棵，直到第M棵樹，那么我們先看一下第二棵樹怎么建立。對上面的遞歸式做個變形，即：
hM(x)=t?FM?1(x)
注意到hM(x)就是我們要建立的第2 (M=2)棵樹，已有的是第一棵樹，第一棵樹一經(jīng)建成就不變了，相當(dāng)于一個已知的函數(shù)，那么（t?FM?1(x)）實際上就是我們在建第 M 棵樹時想要得到的預(yù)測值。所以在建第二棵樹時，我們將目標(biāo)值 t 與第一棵樹的預(yù)測值的差作為新的目標(biāo)值，同樣，在建第三顆樹時，我們將目標(biāo)值 t 與前兩棵樹的預(yù)測值的差作為新的目標(biāo)值，直到第 M 棵樹。（t?FM?1(x)）就是所謂的殘差，這就是從殘差的角度來理解GBDT。
注意到，GBDT的建樹過程不是并行的，而是串行的，所以速度較慢，但所有的樹一旦建好，用它來預(yù)測時是并行的，最終的預(yù)測值就是所有樹的預(yù)測值之和。

拓展

GBDT實際上是由兩部分組成：GB 和 DT，DT 意味著每個basic learner （weaker learner）是“樹”的形式，而GB則是建樹過程中依據(jù)的準(zhǔn)則。DT 可以不變，而 GB 有多種形式，上述的殘差只是其中的一種形式。注意到損失函數(shù)可以表示為：

ε=12（t?F(x)）2
該損失函數(shù)關(guān)于F(x)的導(dǎo)數(shù)（梯度）為：
dε/dF(x)=?（t?F(x)）
該損失函數(shù)在FM?1(x)處的導(dǎo)數(shù)（梯度）為：
dε/dF(x)|FM?1(x)=?（t?FM?1(x)）
所以在建立第 M 棵樹時，新的目標(biāo)值正好就是損失函數(shù)在 FM?1(x) 處的負(fù)梯度。眾所周知，損失函數(shù)可以有多種形式，所以不同的損失函數(shù)就可以對應(yīng)到不同的變種。

舉例

本例僅用于說明大意，實際結(jié)果肯能不同，比如數(shù)據(jù)有兩個feature：x1、x2，對應(yīng)的目標(biāo)值為 t=sin(x1)+sin(x2)，如下圖所示：

根據(jù)feature1可以建立一個回歸樹，預(yù)測結(jié)果如下：

這兩張圖的差值用于建立第二棵回歸樹，這次選擇了feature2，預(yù)測結(jié)果如下：

上述兩棵樹的和就是正確的預(yù)測值。

總結(jié)

以上是生活随笔為你收集整理的从回归树到GBDT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。