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