GBDT（Gradient Boosting Decision Tree）是一種采用加法模型（即基函數(shù)的線性組合）與前向分步算法并以決策樹作為基函數(shù)的提升方法。通俗來說就是，該算法由多棵決策樹組成，所有樹的結(jié)論加起來形成最終答案。
GBDT也是集成學(xué)習(xí)Boosting家族的成員，但是卻和傳統(tǒng)的Adaboost有很大的不同?；仡櫹翧daboost，我們是利用前一輪迭代弱學(xué)習(xí)器的誤差率來更新訓(xùn)練集的權(quán)重，這樣一輪輪的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱學(xué)習(xí)器限定了只能使用CART回歸樹模型，同時迭代思路和Adaboost也有所不同。
在GBDT的迭代中，假設(shè)我們前一輪迭代得到的強學(xué)習(xí)器是ft?1(x), 損失函數(shù)是L(y,ft?1(x)), 我們本輪迭代的目標是找到一個CART回歸樹模型的弱學(xué)習(xí)器ht(x)，讓本輪的損失函數(shù)L(y,ft(x)=L(y,ft?1(x)+ht(x))最小。也就是說，本輪迭代找到?jīng)Q策樹，要讓樣本的損失盡量變得更小。
1.前向分布算法
要理解GBDT算法，得先來了解一下什么是前向分步算法。下面一起來瞧瞧。
我們將
作為加法模型，其中b(x;γm)為基函數(shù)，γm為基函數(shù)的參數(shù)，βm為基函數(shù)的系數(shù)，βm表示著對應(yīng)的基函數(shù)在加法模型f(x)中的重要性。
在給定訓(xùn)練數(shù)據(jù)和損失函數(shù)L(y,f(x))的條件下，學(xué)習(xí)加法模型成為經(jīng)驗風險極小化 (即損失函數(shù)極小化問題) :
（很多參數(shù)都不明白作用）
前向分步算法求解這一優(yōu)化問題的思路：因為學(xué)習(xí)的是加法模型，如果能夠從前向后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)，逐步去逼近上述的目標函數(shù)式，就可簡化優(yōu)化的復(fù)雜度，每一步只需優(yōu)化如下?lián)p失函數(shù)：
前向分步算法流程：
因此，前向分布算法將同時求解從m=1到M的所有參數(shù)βm, rm的優(yōu)化問題簡化為逐次求解各個βm, rm的優(yōu)化問題。
2.負梯度擬合
提升樹利用加法模型與前向分步算法實現(xiàn)學(xué)習(xí)的優(yōu)化過程，當損失函數(shù)是平方損失和指數(shù)損失函數(shù)時，每一步優(yōu)化很簡單，但對一般損失函數(shù)而言，每一步的優(yōu)化并不容易。Freidman提出了梯度提升算法（gradient boosting），其關(guān)鍵是利用損失函數(shù)的負梯度在當前模型的值作為回歸問題提升樹算法中的殘差的近似值，擬合一個回歸樹（用損失函數(shù)的負梯度來擬合本輪損失的近似值，進而擬合一個CART回歸樹）。第t輪的第i個樣本的損失函數(shù)的負梯度表示為：
. 其中 J 為葉子節(jié)點的個數(shù)。
針對每一個葉子節(jié)點里的樣本，我們求出使損失函數(shù)最小，也就是擬合葉子節(jié)點最好的的輸出值Ctj
如下：
這樣我們就得到了本輪的決策樹擬合函數(shù)如下：
從而本輪最終得到的強學(xué)習(xí)器的表達式如下：
通過損失函數(shù)的負梯度來擬合，我們找到了一種通用的擬合損失誤差的辦法，這樣無輪是分類問題還是回歸問題，我們通過其損失函數(shù)的負梯度的擬合，就可以用 GBDT 來解決我們的分類回歸問題。區(qū)別僅僅在于損失函數(shù)不同導(dǎo)致的負梯度不同而已。
3.損失函數(shù)
在GBDT算法中，損失函數(shù)的選擇十分重要。針對不同的問題，損失函數(shù)有不同的選擇。
1.對于分類算法，其損失函數(shù)一般由對數(shù)損失函數(shù)和指數(shù)損失函數(shù)兩種。
(1)指數(shù)損失函數(shù)表達式：
(2)對數(shù)損失函數(shù)可分為二分類和多分類兩種。
2.對于回歸算法，常用損失函數(shù)有如下4種。
(1)平方損失函數(shù)：
(2)絕對損失函數(shù)：
對應(yīng)負梯度誤差為：
(3)Huber損失，它是均方差和絕對損失的折中產(chǎn)物，對于遠離中心的異常點，采用絕對損失誤差，而對于靠近中心的點則采用平方損失。這個界限一般用分位數(shù)點度量。損失函數(shù)如下：
對應(yīng)的負梯度誤差為：
（4）分位數(shù)損失。它對應(yīng)的是分位數(shù)回歸的損失函數(shù)，表達式為：
其中 θ為分位數(shù)，需要我們在回歸之前指定。對應(yīng)的負梯度誤差為：
對于Huber損失和分位數(shù)損失，主要用于健壯回歸，也就是減少異常點對損失函數(shù)的影響。
4.回歸
5.分類問題（二分類與多分類）
這里我們再看看GBDT分類算法，GBDT的分類算法從思想上和GBDT的回歸算法沒有區(qū)別，但是由于樣本輸出不是連續(xù)的值，而是離散的類別，導(dǎo)致我們無法直接從輸出類別去擬合類別輸出的誤差。
為了解決這個問題，主要有兩個方法，一個是用指數(shù)損失函數(shù)，此時GBDT退化為Adaboost算法。另一種方法是用類似于邏輯回歸的對數(shù)似然損失函數(shù)的方法。也就是說，我們用的是類別的預(yù)測概率值和真實概率值的差來擬合損失。本文僅討論用對數(shù)似然損失函數(shù)的GBDT分類。而對于對數(shù)似然損失函數(shù)，我們又有二元分類和多元分類的區(qū)別。
5.1二元 GBDT分類
5.2 多元GBDT分類
6.正則化
和 Adaboost 一樣，我們也需要對 GBDT 進行正則化，防止過擬合。GBDT 的正則化主要有三種方式。
-
第一種是和 Adaboost 類似的正則化項，即步長 (learning rate)。定義為 V, 對于前面的弱學(xué)習(xí)器的迭代
image
如果我們加上了正則化項，則有
image
v 的取值范圍為0<=v<=1。對于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的 v 意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用步長和迭代最大次數(shù)一起來決定算法的擬合效果。 第二種正則化的方式是通過子采樣比例（subsample）。取值為 (0,1]。注意這里的子采樣和隨機森林不一樣，隨機森林使用的是放回抽樣，而這里是不放回抽樣。如果取值為 1，則全部樣本都使用，等于沒有使用子采樣。如果取值小于 1，則只有一部分樣本會去做 GBDT 的決策樹擬合。選擇小于 1 的比例可以減少方差，即防止過擬合，但是會增加樣本擬合的偏差，因此取值不能太低。推薦在0.5, 0.8 之間。 使用了子采樣的 GBDT 有時也稱作隨機梯度提升樹(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采樣，程序可以通過采樣分發(fā)到不同的任務(wù)去做 boosting 的迭代過程，最后形成新樹，從而減少弱學(xué)習(xí)器難以并行學(xué)習(xí)的弱點。
第三種是對于弱學(xué)習(xí)器即 CART 回歸樹進行正則化剪枝。
7.優(yōu)缺點
7.1 優(yōu)點
- 預(yù)測精度高
- 適合低維數(shù)據(jù)
- 能處理非線性數(shù)據(jù)
- 可以靈活處理各種類型的數(shù)據(jù)，包括連續(xù)值和離散值。
- 在相對少的調(diào)參時間情況下，預(yù)測的準備率也可以比較高。這個是相對SVM來說的。
- 使用一些健壯的損失函數(shù)，對異常值的魯棒性非常強。比如 Huber損失函數(shù)和Quantile損失函數(shù)。
7.2 缺點
- 由于弱學(xué)習(xí)器之間存在依賴關(guān)系，難以并行訓(xùn)練數(shù)據(jù)。不過可以通過自采樣的SGBT來達到部分并行。
- 如果數(shù)據(jù)維度較高時會加大算法的計算復(fù)雜度
8.sklearn參數(shù)
在scikit-learn中，GradientBoostingClassifier為GBDT的分類類， 而GradientBoostingRegressor為GBDT的回歸類。兩者的參數(shù)類型完全相同，當然有些參數(shù)比如損失函數(shù)loss的可選擇項并不相同。這些參數(shù)中，類似于Adaboost，我們把重要參數(shù)分為兩類，第一類是Boosting框架的重要參數(shù)，第二類是弱學(xué)習(xí)器即CART回歸樹的重要參數(shù)。
下面我們就從這兩個方面來介紹這些參數(shù)的使用。
9.應(yīng)用場景
這次基本上是個CRUD boy，對于這些資料都大部分沒有消化完成，還不知道能用在哪個地方。
參考資料：
梯度提升樹(GBDT)原理小結(jié) http://www.cnblogs.com/pinard/p/6140514.html
