最常用的决策树算法（二）Random Forest、Adaboost、GBDT 算法
決策樹是一個非常常見并且優秀的機器學習算法，它易于理解、可解釋性強，其可作為分類算法，也可用于回歸模型。本文將分三篇介紹決策樹，第一篇介紹基本樹（包括 ID3、C4.5、CART），第二篇介紹 Random Forest、Adaboost、GBDT，第三篇介紹 Xgboost 和 LightGBM。
第二篇： Random Forest、Adaboost、GBDT
本文主要介紹基于集成學習的決策樹，其主要通過不同學習框架生產基學習器，并綜合所有基學習器的預測結果來改善單個基學習器的識別率和泛化性。
集成學習
常見的集成學習框架有三種：Bagging，Boosting 和 Stacking。三種集成學習框架在基學習器的產生和綜合結果的方式上會有些區別，我們先做些簡單的介紹。
1.1 Bagging
Bagging 全稱叫 Bootstrap aggregating，看到 Bootstrap 我們立刻想到著名的開源前端框架（抖個機靈，是 Bootstrap 抽樣方法） ，每個基學習器都會對訓練集進行有放回抽樣得到子訓練集，比較著名的采樣法為 0.632 自助法。每個基學習器基于不同子訓練集進行訓練，并綜合所有基學習器的預測值得到最終的預測結果。Bagging 常用的綜合方法是投票法，票數最多的類別為預測類別。
1.2 Boosting
Boosting 訓練過程為階梯狀，基模型的訓練是有順序的，每個基模型都會在前一個基模型學習的基礎上進行學習，最終綜合所有基模型的預測值產生最終的預測結果，用的比較多的綜合方式為加權法。
1.3 Stacking
Stacking 是先用全部數據訓練好基模型，然后每個基模型都對每個訓練樣本進行的預測，其預測值將作為訓練樣本的特征值，最終會得到新的訓練樣本，然后基于新的訓練樣本進行訓練得到模型，然后得到最終預測結果。
那么，為什么集成學習會好于單個學習器呢？原因可能有三：
訓練樣本可能無法選擇出最好的單個學習器，由于沒法選擇出最好的學習器，所以干脆結合起來一起用；
假設能找到最好的學習器，但由于算法運算的限制無法找到最優解，只能找到次優解，采用集成學習可以彌補算法的不足；
可能算法無法得到最優解，而集成學習能夠得到近似解。比如說最優解是一條對角線，而單個決策樹得到的結果只能是平行于坐標軸的，但是集成學習可以去擬合這條對角線。
偏差與方差
上節介紹了集成學習的基本概念，這節我們主要介紹下如何從偏差和方差的角度來理解集成學習。
2.1 集成學習的偏差與方差
偏差（Bias）描述的是預測值和真實值之差；方差（Variance）描述的是預測值作為隨機變量的離散程度。放一場很經典的圖：
模型的偏差與方差
偏差：描述樣本擬合出的模型的預測結果的期望與樣本真實結果的差距，要想偏差表現的好，就需要復雜化模型，增加模型的參數，但這樣容易過擬合，過擬合對應上圖的 High Variance，點會很分散。低偏差對應的點都打在靶心附近，所以喵的很準，但不一定很穩；
方差：描述樣本上訓練出來的模型在測試集上的表現，要想方差表現的好，需要簡化模型，減少模型的復雜度，但這樣容易欠擬合，欠擬合對應上圖 High Bias，點偏離中心。低方差對應就是點都打的很集中，但不一定是靶心附近，手很穩，但不一定瞄的準。
我們常說集成學習中的基模型是弱模型，通常來說弱模型是偏差高（在訓練集上準確度低）方差小（防止過擬合能力強）的模型。但是，并不是所有集成學習框架中的基模型都是弱模型。Bagging 和 Stacking 中的基模型為強模型（偏差低方差高），Boosting 中的基模型為弱模型。
在 Bagging 和 Boosting 框架中，通過計算基模型的期望和方差我們可以得到模型整體的期望和方差。為了簡化模型，我們假設基模型的權重?、方差??及兩兩間的相關系數??相等。由于 Bagging 和 Boosting 的基模型都是線性組成的，那么有：
模型總體期望：
模型總體方差：
2.2 Bagging 的偏差與方差
對于 Bagging 來說，每個基模型的權重等于 1/m 且期望近似相等（子訓練集都是從原訓練集中進行子抽樣），故我們可以進一步化簡得到：
通過上式我們可以看到
整體模型的期望等于基模型的期望，這也就意味著整體模型的偏差和基模型的偏差近似。
整體模型的方差小于等于基模型的方差，當且僅當相關性為 1 時取等號，隨著基模型數量增多，整體模型的方差減少，從而防止過擬合的能力增強，模型的準確度得到提高。但是，模型的準確度一定會無限逼近于 1 嗎？并不一定，當基模型數增加到一定程度時，方差公式第一項的改變對整體方差的作用很小，防止過擬合的能力達到極限，這便是準確度的極限了。
在此我們知道了為什么 Bagging 中的基模型一定要為強模型，如果 Bagging 使用弱模型則會導致整體模型的偏差提高，而準確度降低。
Random Forest 是經典的基于 Bagging 框架的模型，并在此基礎上通過引入特征采樣和樣本采樣來降低基模型間的相關性，在公式中顯著降低方差公式中的第二項，略微升高第一項，從而使得整體降低模型整體方差。
2.3 Boosting 的偏差與方差
對于 Boosting 來說，基模型的訓練集抽樣是強相關的，那么模型的相關系數近似等于 1，故我們也可以針對 Boosting 化簡公式為：
通過觀察整體方差的表達式我們容易發現：
整體模型的方差等于基模型的方差，如果基模型不是弱模型，其方差相對較大，這將導致整體模型的方差很大，即無法達到防止過擬合的效果。因此，Boosting 框架中的基模型必須為弱模型。
此外 Boosting 框架中采用基于貪心策略的前向加法，整體模型的期望由基模型的期望累加而成，所以隨著基模型數的增多，整體模型的期望值增加，整體模型的準確度提高。
基于 Boosting 框架的 Gradient Boosting Decision Tree 模型中基模型也為樹模型，同 Random Forrest，我們也可以對特征進行隨機抽樣來使基模型間的相關性降低，從而達到減少方差的效果。
2.4 小結
我們可以使用模型的偏差和方差來近似描述模型的準確度；
對于 Bagging 來說，整體模型的偏差與基模型近似，而隨著模型的增加可以降低整體模型的方差，故其基模型需要為強模型；
對于 Boosting 來說，整體模型的方差近似等于基模型的方差，而整體模型的偏差由基模型累加而成，故基模型需要為弱模型。
Random Forest
Random Forest（隨機森林），用隨機的方式建立一個森林。RF 算法由很多決策樹組成，每一棵決策樹之間沒有關聯。建立完森林后，當有新樣本進入時，每棵決策樹都會分別進行判斷，然后基于投票法給出分類結果。
3.1 思想
Random Forest（隨機森林）是 Bagging 的擴展變體，它在以決策樹為基學習器構建 Bagging 集成的基礎上，進一步在決策樹的訓練過程中引入了隨機特征選擇，因此可以概括 RF 包括四個部分：
隨機選擇樣本（放回抽樣）；
隨機選擇特征；
構建決策樹；
隨機森林投票（平均）。
隨機選擇樣本和 Bagging 相同，采用的是 Bootstrap 自助采樣法；隨機選擇特征是指在每個節點在分裂過程中都是隨機選擇特征的（區別與每棵樹隨機選擇一批特征）。
這種隨機性導致隨機森林的偏差會有稍微的增加（相比于單棵不隨機樹），但是由于隨機森林的“平均”特性，會使得它的方差減小，而且方差的減小補償了偏差的增大，因此總體而言是更好的模型。
隨機采樣由于引入了兩種采樣方法保證了隨機性，所以每棵樹都是最大可能的進行生長就算不剪枝也不會出現過擬合。
3.2 優缺點
優點
在數據集上表現良好，相對于其他算法有較大的優勢
易于并行化，在大數據集上有很大的優勢；
能夠處理高維度數據，不用做特征選擇。
AdaBoost
AdaBoost（Adaptive Boosting，自適應增強），其自適應在于：前一個基本分類器分錯的樣本會得到加強，加權后的全體樣本再次被用來訓練下一個基本分類器。同時，在每一輪中加入一個新的弱分類器，直到達到某個預定的足夠小的錯誤率或達到預先指定的最大迭代次數。
4.1 思想
Adaboost 迭代算法有三步：
初始化訓練樣本的權值分布，每個樣本具有相同權重；
訓練弱分類器，如果樣本分類正確，則在構造下一個訓練集中，它的權值就會被降低；反之提高。用更新過的樣本集去訓練下一個分類器；
將所有弱分類組合成強分類器，各個弱分類器的訓練過程結束后，加大分類誤差率小的弱分類器的權重，降低分類誤差率大的弱分類器的權重。
4.2 細節
4.2.1 損失函數
Adaboost 模型是加法模型，學習算法為前向分步學習算法，損失函數為指數函數的分類問題。
加法模型：最終的強分類器是由若干個弱分類器加權平均得到的。
前向分布學習算法：算法是通過一輪輪的弱學習器學習，利用前一個弱學習器的結果來更新后一個弱學習器的訓練集權重。第 k 輪的強學習器為：
損失函數：
利用前向分布學習算法的關系可以得到損失函數為：
令?，它的值不依賴于?，因此與最小化無關，僅僅依賴于?，隨著每一輪迭代而將這個式子帶入損失函數，損失函數轉化為：
我們求?，可以得到：
將??帶入損失函數，并對 \alpha 求導，使其等于 0，則就得到了：
其中，?即為我們前面的分類誤差率。
最后看樣本權重的更新。利用??和?，即可得：
這樣就得到了樣本權重更新公式。
4.2.2 正則化
為了防止 Adaboost 過擬合，我們通常也會加入正則化項，這個正則化項我們通常稱為步長（learning rate）。定義為 v，對于前面的弱學習器的迭代
加上正則化我們有：
v 的取值范圍為 0v1。對于同樣的訓練集學習效果，較小的 v 意味著我們需要更多的弱學習器的迭代次數。通常我們用步長和迭代最大次數一起來決定算法的擬合效果。
4.3 優缺點
優點
分類精度高；
可以用各種回歸分類模型來構建弱學習器，非常靈活；
不容易發生過擬合。
缺點
對異常點敏感，異常點會獲得較高權重。
GBDT
GBDT（Gradient Boosting Decision Tree）是一種迭代的決策樹算法，該算法由多棵決策樹組成，從名字中我們可以看出來它是屬于 Boosting 策略。GBDT 是被公認的泛化能力較強的算法。
5.1 思想
GBDT 由三個概念組成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和SHringkage（一個重要演變）
5.1.1 回歸樹（Regression Decision Tree）
如果認為 GBDT 由很多分類樹那就大錯特錯了（雖然調整后也可以分類）。對于分類樹而言，其值加減無意義（如性別），而對于回歸樹而言，其值加減才是有意義的（如說年齡）。GBDT 的核心在于累加所有樹的結果作為最終結果，所以 GBDT 中的樹都是回歸樹，不是分類樹，這一點相當重要。
回歸樹在分枝時會窮舉每一個特征的每個閾值以找到最好的分割點，衡量標準是最小化均方誤差。
5.1.2 梯度迭代（Gradient Boosting）
上面說到 GBDT 的核心在于累加所有樹的結果作為最終結果，GBDT 的每一棵樹都是以之前樹得到的殘差來更新目標值，這樣每一棵樹的值加起來即為 GBDT 的預測值。
模型的預測值可以表示為：
?為基模型與其權重的乘積，模型的訓練目標是使預測值??逼近真實值?，也就是說要讓每個基模型的預測值逼近各自要預測的部分真實值。由于要同時考慮所有基模型，導致了整體模型的訓練變成了一個非常復雜的問題。所以研究者們想到了一個貪心的解決手段：每次只訓練一個基模型。那么，現在改寫整體模型為迭代式：
這樣一來，每一輪迭代中，只要集中解決一個基模型的訓練問題：使 F_i(x) 逼近真實值 y。
舉個例子：比如說 A 用戶年齡 20 歲，第一棵樹預測 12 歲，那么殘差就是 8，第二棵樹用 8 來學習，假設其預測為 5，那么其殘差即為 3，如此繼續學習即可。
那么 Gradient 從何體現？其實很簡單，其殘差其實是最小均方損失函數關于預測值的反向梯度：
也就是說，若??加上擬合了反向梯度的??得到?，該值可能將導致平方差損失函數降低，預測的準確度提高！
但要注意，基于殘差 GBDT 容易對異常值敏感，舉例：
很明顯后續的模型會對第 4 個值關注過多，這不是一種好的現象，所以一般回歸類的損失函數會用絕對損失或者 Huber 損失函數來代替平方損失函數。
GBDT 的 Boosting 不同于 Adaboost 的 Boosting，GBDT 的每一步殘差計算其實變相地增大了被分錯樣本的權重，而對與分對樣本的權重趨于 0，這樣后面的樹就能專注于那些被分錯的樣本。
5.1.13 縮減（Shrinkage）
Shrinkage 的思想認為，每走一小步逐漸逼近結果的效果要比每次邁一大步很快逼近結果的方式更容易避免過擬合。即它并不是完全信任每一棵殘差樹。
, ?(0v1)
Shrinkage 不直接用殘差修復誤差，而是只修復一點點，把大步切成小步。本質上 Shrinkage 為每棵樹設置了一個 weight，累加時要乘以這個 weight，當 weight 降低時，基模型數會配合增大。
5.2 優缺點
優點
可以自動進行特征組合，擬合非線性數據；
可以靈活處理各種類型的數據。
缺點
對異常點敏感。
5.3 與 Adaboost 的對比
相同：
都是 Boosting 家族成員，使用弱分類器；
都使用前向分布算法；
不同：
迭代思路不同：Adaboost 是通過提升錯分數據點的權重來彌補模型的不足（利用錯分樣本），而 GBDT 是通過算梯度來彌補模型的不足（利用殘差）；
損失函數不同：AdaBoost 采用的是指數損失，GBDT 使用的是絕對損失或者 Huber 損失函數；
參考
機器學習算法中 GBDT 與 Adaboost 的區別與聯系是什么？ - Frankenstein 的回答 - 知乎
往期精彩回顧
那些年做的學術公益-你不是一個人在戰斗
適合初學者入門人工智能的路線及資料下載
吳恩達機器學習課程筆記及資源（github標星12000+，提供百度云鏡像）
吳恩達深度學習筆記及視頻等資源（github標星8500+，提供百度云鏡像）
《統計學習方法》的python代碼實現（github標星7200+）
機器學習的數學精華（在線閱讀版）
備注：加入本站微信群或者qq群，請回復“加群”
加入知識星球（4300+用戶，ID：92416895），請回復“知識星球”
總結
以上是生活随笔為你收集整理的最常用的决策树算法（二）Random Forest、Adaboost、GBDT 算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 最常用的决策树算法（三）：XGBoost
- 下一篇： 最常用的决策树算法（一）：ID3、C4.