1. 算法
GBDT (Gradient Boosting Decision Tree) ，梯度提升樹，是屬于集成算法中boosting類的一種算法。這個(gè)算法是現(xiàn)有機(jī)器學(xué)習(xí)算法中相對(duì)較實(shí)用的算法。由其衍生的lightGBR以及Xgboost都是非常實(shí)用的數(shù)據(jù)分析工具。
1.1 與Adboost比較
回顧下Adaboost，我們是利用前一輪迭代弱學(xué)習(xí)器的誤差率來更新訓(xùn)練集的權(quán)重，這樣一輪輪的迭代下去，Adboost實(shí)際上是加法模型（結(jié)果是加權(quán)累加各個(gè)單層決策樹的結(jié)果）+前向分布算法（利用前一輪迭代弱學(xué)習(xí)器的誤差率來更新訓(xùn)練集的權(quán)重）。GBDT也是迭代，使用了前向分布算法，二者的大體框架類似，但是弱學(xué)習(xí)器限定了只能使用CART回歸樹模型，同時(shí)迭代思路和Adaboost也有所不同。
相同:
1. 都是 Boosting 家族成員，使用弱分類器；
2. 都使用加法模型和前向分布算法；
不同:
1. 迭代思路不同：Adaboost 是通過提升錯(cuò)分?jǐn)?shù)據(jù)點(diǎn)的權(quán)重來彌補(bǔ)模型的不足，更新弱學(xué)習(xí)器的權(quán)重和強(qiáng)學(xué)習(xí)器的權(quán)重（利用錯(cuò)分樣本），而 GBDT 是通過算梯度來彌補(bǔ)模型的不足，更新弱學(xué)習(xí)器的權(quán)重和強(qiáng)學(xué)習(xí)器的權(quán)重（利用殘差）；
2. 損失函數(shù)不同：AdaBoost 采用的是指數(shù)損失，GBDT 使用的是絕對(duì)損失或者 Huber 損失函數(shù)；
1.2?GBDT的負(fù)梯度擬合
在GBDT的迭代中，假設(shè)我們前一輪迭代得到的強(qiáng)學(xué)習(xí)器是, 損失函數(shù)是
, 我們本輪迭代的目標(biāo)是找到一個(gè)CART回歸樹模型的弱學(xué)習(xí)器
，讓本輪的損失函數(shù)
最小。也就是說，本輪迭代找到?jīng)Q策樹，要讓樣本的損失盡量變得更小。
GBDT的思想可以用一個(gè)通俗的例子解釋，假如有個(gè)人30歲，我們首先用20歲去擬合，發(fā)現(xiàn)損失有10歲，這時(shí)我們用6歲去擬合剩下的損失，發(fā)現(xiàn)差距還有4歲，第三輪我們用3歲擬合剩下的差距，差距就只有一歲了。如果我們的迭代輪數(shù)還沒有完，可以繼續(xù)迭代下面，每一輪迭代，擬合的歲數(shù)誤差都會(huì)減小。
如果認(rèn)為 GBDT是分類樹那就大錯(cuò)特錯(cuò)了（雖然調(diào)整后也可以分類）。對(duì)于分類樹而言，其值加減無意義（如性別），而對(duì)于回歸樹而言，其值加減才是有意義的（如說年齡）。GBDT 的核心在于累加所有樹的結(jié)果作為最終結(jié)果，所以 GBDT 中的樹都是回歸樹，不是分類樹，這一點(diǎn)相當(dāng)重要。
回歸樹在分枝時(shí)會(huì)窮舉每一個(gè)特征的每個(gè)閾值以找到最好的分割點(diǎn)，衡量標(biāo)準(zhǔn)是最小化均方誤差。
模型的預(yù)測(cè)值可以表示為：
?為基模型與其權(quán)重的乘積，模型的訓(xùn)練目標(biāo)是使預(yù)測(cè)值?
逼近真實(shí)值 y，也就是說要讓每個(gè)基模型的預(yù)測(cè)值逼近各自要預(yù)測(cè)的部分真實(shí)值。由于要同時(shí)考慮所有基模型，導(dǎo)致了整體模型的訓(xùn)練變成了一個(gè)非常復(fù)雜的問題。所以研究者們想到了一個(gè)貪心的解決手段：每次只訓(xùn)練一個(gè)基模型。那么，現(xiàn)在改寫整體模型為迭代式：
這樣一來，每一輪迭代中，只要集中解決一個(gè)基模型的訓(xùn)練問題：使逼近真實(shí)值
。
舉個(gè)例子：比如說 A 用戶年齡 20 歲，第一棵樹預(yù)測(cè) 12 歲，那么殘差就是 8，第二棵樹用 8 來學(xué)習(xí)，假設(shè)其預(yù)測(cè)為 5，那么其殘差即為 3，如此繼續(xù)學(xué)習(xí)即可。
那么 Gradient 從何體現(xiàn)？其實(shí)很簡(jiǎn)單，其殘差其實(shí)是最小均方損失函數(shù)關(guān)于預(yù)測(cè)值的反向梯度(劃重點(diǎn))：
也就是說，預(yù)測(cè)值和實(shí)際值的殘差與損失函數(shù)的負(fù)梯度相同。
但要注意，基于殘差 GBDT 容易對(duì)異常值敏感，舉例：
很明顯后續(xù)的模型會(huì)對(duì)第 4 個(gè)值關(guān)注過多，這不是一種好的現(xiàn)象，所以一般回歸類的損失函數(shù)會(huì)用絕對(duì)損失或者 Huber 損失函數(shù)來代替平方損失函數(shù)。
1.3 GBDT回歸算法
好了，有了上面的思路，下面我們總結(jié)下GBDT的回歸算法。為什么沒有加上分類算法一起？那是因?yàn)榉诸愃惴ǖ妮敵鍪遣贿B續(xù)的類別值，需要一些處理才能使用負(fù)梯度，我們?cè)谙乱还?jié)講。
輸入是訓(xùn)練集樣本T={(x,y1),(x2,y2),...(xm,ym)}， 最大迭代次數(shù)T, 損失函數(shù)L。
輸出是強(qiáng)學(xué)習(xí)器f(x)
1) 初始化弱學(xué)習(xí)器
2) 對(duì)迭代輪數(shù)t=1,2,...T有：
????a)對(duì)樣本i=1,2，...m，計(jì)算負(fù)梯度
? ??b)利用, 擬合一顆CART回歸樹,得到第t顆回歸樹，其對(duì)應(yīng)的葉子節(jié)點(diǎn)區(qū)域?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=R_%7Btj%7D%2Cj%3D1%2C2%2C3...J" alt="R_{tj},j=1,2,3...J" mathimg="1">。其中J為回歸樹t的葉子節(jié)點(diǎn)的個(gè)數(shù)。
? ??c) 對(duì)葉子區(qū)域j =1,2,..J,計(jì)算最佳擬合值
? ??d) 更新強(qiáng)學(xué)習(xí)器
3) 得到強(qiáng)學(xué)習(xí)器f(x)的表達(dá)式
1.4 GBDT分類算法
梯度提升分類樹的原理和思想和梯度提升回歸樹本質(zhì)上是沒有區(qū)別的。他們的模型都是決策回歸樹(DecisionTreeRegressor),可能有人有疑問，為什么梯度提升分類樹的模型也是決策回歸樹，那是怎么實(shí)現(xiàn)分類的呢？其實(shí)梯度提升分類樹和邏輯斯蒂回歸類似。
? 邏輯斯蒂回歸的預(yù)測(cè)模型：sigmoid函數(shù) + 線性回歸
? 梯度提升分類樹的預(yù)測(cè)模型： sigmoid函數(shù) + 決策回歸樹
但是由于梯度提升分類樹的樣本輸出不是連續(xù)的而是離散的，因此無法直接擬合類別輸出的誤差。這時(shí)候需要構(gòu)建交叉熵?fù)p失函數(shù)(也叫對(duì)數(shù)損失函數(shù))。
詳細(xì)的數(shù)學(xué)推導(dǎo)可以看看這篇文章：http://www.itdecent.cn/p/e44f163fea1a
1.5?GBDT常用損失函數(shù)
這里我們?cè)賹?duì)常用的GBDT損失函數(shù)做一個(gè)總結(jié)。
對(duì)于分類算法，其損失函數(shù)一般有對(duì)數(shù)損失函數(shù)和指數(shù)損失函數(shù)兩種:
a) 如果是指數(shù)損失函數(shù)，則損失函數(shù)表達(dá)式為
其負(fù)梯度計(jì)算和葉子節(jié)點(diǎn)的最佳負(fù)梯度擬合參見Adaboost原理篇。
b)?如果是對(duì)數(shù)損失函數(shù)，分為二元分類和多元分類兩種，
對(duì)于回歸算法，常用損失函數(shù)有如下4種:
a)均方差，這個(gè)是最常見的回歸損失函數(shù)了
b)絕對(duì)損失，這個(gè)損失函數(shù)也很常見
對(duì)應(yīng)負(fù)梯度誤差為：
c)Huber損失，它是均方差和絕對(duì)損失的折衷產(chǎn)物，對(duì)于遠(yuǎn)離中心的異常點(diǎn)，采用絕對(duì)損失，而中心附近的點(diǎn)采用均方差。這個(gè)界限一般用分位數(shù)點(diǎn)度量。損失函數(shù)如下：
對(duì)應(yīng)的負(fù)梯度誤差為：
d) 分位數(shù)損失。它對(duì)應(yīng)的是分位數(shù)回歸的損失函數(shù)，表達(dá)式為
其中θ為分位數(shù)，需要我們?cè)诨貧w前指定。對(duì)應(yīng)的負(fù)梯度誤差為：
對(duì)于Huber損失和分位數(shù)損失，主要用于健壯回歸，也就是減少異常點(diǎn)對(duì)損失函數(shù)的影響。
1.6 正則化
和Adaboost一樣，我們也需要對(duì)GBDT進(jìn)行正則化，防止過擬合。GBDT的正則化主要有三種方式。
第一種是和Adaboost類似的正則化項(xiàng)，即步長(learning rate)。定義為ν,對(duì)于前面的弱學(xué)習(xí)器的迭代
如果我們加上了正則化項(xiàng)，則有
ν的取值范圍為0<ν≤10<ν≤1。對(duì)于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的ν意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用步長和迭代最大次數(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)行正則化剪枝。在決策樹原理篇里我們已經(jīng)講過，這里就不重復(fù)了。
2. 優(yōu)缺點(diǎn)
GBDT主要的優(yōu)點(diǎn)有：
1) 可以靈活處理各種類型的數(shù)據(jù)，包括連續(xù)值和離散值。
2) 在相對(duì)少的調(diào)參時(shí)間情況下，預(yù)測(cè)的準(zhǔn)確率也可以比較高。這個(gè)是相對(duì)SVM來說的。
3）使用一些健壯的損失函數(shù)，對(duì)異常值的魯棒性非常強(qiáng)。比如 Huber損失函數(shù)和Quantile損失函數(shù)。
4）可以自動(dòng)進(jìn)行特征組合，擬合非線性數(shù)據(jù)；
GBDT的主要缺點(diǎn)有：
1）由于弱學(xué)習(xí)器之間存在依賴關(guān)系，難以并行訓(xùn)練數(shù)據(jù)。不過可以通過自采樣的SGBT來達(dá)到部分并行。
3. 鏈接
梯度提升分類樹原理推導(dǎo)（超級(jí)詳細(xì)?。?/p>
http://www.itdecent.cn/p/e44f163fea1a
【機(jī)器學(xué)習(xí)】決策樹（中）——Random Forest、Adaboost、GBDT （非常詳細(xì)）
https://zhuanlan.zhihu.com/p/86263786
梯度提升樹(GBDT)原理小結(jié)
