[機器學習 ] RandomForest、GBDT、XGBoost、lightGBM 原理與差別

目錄

随機森林 -- RandomForest

GBDT (Gradient Boosting Decision Tree)

XGBoost

lightGBM

一 知識點介紹

RF,GBDT,XGBoost,lightGBM都屬于內建學習（Ensemble Learning），內建學習的目的是通過結合多個基學習器的預測結果來改善基本學習器的泛化能力和魯棒性。

根據基本學習器的生成方式，目前的內建學習方法大緻分為兩大類：即基本學習器之間存在強依賴關系、必須串行生成的序列化方法，以及基本學習器間不存在強依賴關系、可同時生成的并行化方法；前者的代表就是Boosting，後者的代表是Bagging和“随機森林”（Random Forest）

這篇文章主要對內建學習中重要的、使用廣泛的方法進行對比：

RF（随機森林））, GBDT（梯度提升決策樹）, XGBoost,  lightGBM

二 随機森林 -- RandomForest

提到随機森林，就不得不提Bagging，Bagging可以簡單的了解為：放回抽樣，多數表決（分類）或簡單平均（回歸）,同時Bagging的基學習器之間屬于并列生成，不存在強依賴關系。

Random Forest（随機森林）是Bagging的擴充變體，它在以決策樹 為基學習器建構Bagging內建的基礎上，進一步在決策樹的訓練過程中引入了随機特征選擇

是以可以概括RF包括四個步驟：

1、随機選擇樣本（放回抽樣）；

2、随機選擇特征屬性；

3、建構決策樹；

4、随機森林投票（平均）

是以防止過拟合能力更強，降低方差。

RF和Bagging對比： RF的起始性能較差，特别當隻有一個基學習器時，随着學習器數目增多，随機森林通常會收斂到更低的泛化誤差。随機森林的訓練效率也會高于Bagging，因為在單個決策樹的建構中，Bagging使用的是‘确定性’決策樹，在選擇特征劃分結點時，要對所有的特征進行考慮，而随機森林使用的是‘随機性’特征數，隻需考慮特征的子集。

使用的融合方法：bagging

• 一種內建學習算法，基于bootstrap sampling 自助采樣法，重複性有放回的随機采用部分樣本進行訓練最後再将結果 voting 或者 averaging 。
• 它是并行式算法，因為不同基學習器是獨立
• 訓練一個bagging內建學習器時間複雜度與基學習器同階（n倍，n為基學習器個數）。
• bagging可以用于二分類／多分類／回歸
• 每個基學習器的未用作訓練樣本可用來做包外估計，評價泛化性能。
• bagging主要關注降低 方差。
• 兩個步驟 1. 抽樣訓練（采樣樣本，采樣特征） 2 融合

随機森林的優缺點

優點：

1. 随機森林算法能解決分類與回歸兩種類型的問題，表現良好，由于是內建學習，方差和偏差都比較低，泛化性能優越；
2. 随機森林對于高維資料集的處理能力很好，它可以處理成千上萬的輸入變量，并确定最重要的變量，是以被認為是一個不錯的降維方法。此外，該模型能夠輸出特征的重要性程度，這是一個非常實用的功能。
3. 可以應對缺失資料；
4. 當存在分類不平衡的情況時，随機森林能夠提供平衡資料集誤差的有效方法；
5. 高度并行化，易于分布式實作
6. 由于是樹模型 ，不需要歸一化即可之間使用

缺點：

1. 随機森林在解決回歸問題時并沒有像它在分類中表現的那麼好，這是因為它并不能給出一個連續型的輸出。當進行回歸時，随機森林不能夠作出超越訓練集資料範圍的預測，這可能導緻在對某些還有特定噪聲的資料進行模組化時出現過度拟合。
2. 對于許多統計模組化者來說，随機森林給人的感覺像是一個黑盒子——你幾乎無法控制模型内部的運作，隻能在不同的參數和随機種子之間進行嘗試。
3. 忽略屬性之間的相關性
4. 在噪聲較大的分類或者回歸問題上容易過拟合。

三 GBDT (Gradient Boosting Decision Tree)

      提GBDT之前，談一下Boosting，Boosting是一種與Bagging很類似的技術。不論是Boosting還是Bagging，所使用的多個分類器類型都是一緻的。但是在前者當中，不同的分類器是通過串行訓練而獲得的，每個新分類器都根據已訓練的分類器的性能來進行訓練。Boosting是通過關注被已有分類器錯分的那些資料來獲得新的分類器。

　 由于Boosting分類的結果是基于所有分類器的權重求和結果的，是以Boosting與Bagging不太一樣，Bagging中的分類器權值是一樣的，而Boosting中的分類器權重并不相等，每個權重代表對應的分類器在上一輪疊代中的成功度。

原理

• GBDT的基本原理是boost 裡面的 boosting tree（提升樹），并使用 gradient boost。
• GradientBoosting算法關鍵是利用損失函數的負梯度方向在目前模型的值作為殘差的近似值，進而拟合一棵CART回歸樹。
• GBDT會累加所有樹的結果，而這種累加是無法通過分類完成的，是以GBDT的樹都是CART回歸樹，而不是分類樹（盡管GBDT調整後也可以用于分類但不代表GBDT的樹為分類樹) 因為Gradient Boosting 需要按照損失函數的梯度近似的拟合殘差，這樣拟合的是連續數值，是以隻有回歸樹。

梯度提升 Gradient Boosting:

    Gradient Boosting是一種Boosting的方法，其與傳統的Boosting的差別是，每一次的計算是為了減少上一次的殘差(residual)，而為了消除殘差，可以在殘差減少的梯度(Gradient)方向上建立一個新的模型。是以說，在Gradient Boosting中，每個新的模型的建立是為了使得之前模型的殘差往梯度方向減少，與傳統Boosting對正确、錯誤樣本進行權重有着很大的差別。這個梯度代表上一輪學習器損失函數對預測值求導。

    與Boosting Tree的差別：Boosting Tree适合于損失函數為平方損失或者指數損失。而Gradient Boosting适合各類損失函數（損失函數為平方損失則相當于Boosting Tree拟合殘差、損失函數為指數損失則可以近似于Adaboost，但樹是回歸樹）

優缺點

　　優點：GBDT的性能在RF的基礎上又有一步提升，是以其優點也很明顯，1、它能靈活的處理各種類型的資料；2、在相對較少的調參時間下，預測的準确度較高。

　　缺點：當然由于它是Boosting，是以基學習器之前存在串行關系，難以并行訓練資料。

四 XGBoost

XGBoost的原理詳細，推薦兩篇大神部落格， xgboost原理 ，xgboost 算法原理。

       XGBoost是內建學習Boosting家族的成員，是在GBDT的基礎上對boosting算法進行的改進。GBDT是用模型在資料上的負梯度作為殘差的近似值，進而拟合殘差。XGBoost也是拟合的在資料上的殘差，但是它是用泰勒展開式對模型損失殘差的近似；同時XGBoost對模型的損失函數進行的改進，并加入了模型複雜度的正則項。

　   XGBoost的性能在GBDT上又有一步提升，而其性能也能通過各種比賽管窺一二。坊間對XGBoost最大的認知在于其能夠自動地運用CPU的多線程進行并行計算，同時在算法精度上也進行了精度的提高。由于GBDT在合理的參數設定下，往往要生成一定數量的樹才能達到令人滿意的準确率，在資料集較複雜時，模型可能需要幾千次疊代運算。但是XGBoost利用并行的CPU更好的解決了這個問題。

XGBoost與GBDT的差別： 在了解了XGBoost原理後容易了解二者的不同

損失函數的改變：（導數和正則項的認識）

• 傳統的GBDT以CART樹作為基學習器，XGBoost還支援線性分類器，這個時候XGBoost相當于L1和L2正則化的邏輯斯蒂回歸（分類）或者線性回歸（回歸）；
• 傳統的GBDT在優化的時候隻用到一階導數資訊，XGBoost則對代價函數進行了二階泰勒展開，得到一階和二階導數；
• XGBoost在代價函數中加入了正則項，用于控制模型的複雜度。從權衡方差偏差來看，它降低了模型的方差，使學習出來的模型更加簡單，防止過拟合，這也是XGBoost優于傳統GBDT的一個特性；

工具的優化：（趨勢值和并行的認識）

1. shrinkage（縮減），相當于學習速率（XGBoost中的eta）。XGBoost在進行完一次疊代時，會将葉子節點的權值乘上該系數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間。（GBDT也有學習速率）；
2. 列抽樣。XGBoost借鑒了随機森林的做法，支援列抽樣，不僅防止過 拟合，還能減少計算；
3. 對缺失值的處理。對于特征的值有缺失的樣本，XGBoost還可以自動學習出它的分裂方向；
4.  XGBoost工具支援并行。Boosting不是一種串行的結構嗎?怎麼并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次疊代完才能進行下一次疊代的（第t次疊代的代價函數裡包含了前面t-1次疊代的預測值）。XGBoost的并行是在特征粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特征的值進行排序（因為要确定最佳分割點），XGBoost在訓練之前，預先對資料進行了排序，然後儲存為block結構，後面的疊代 中重複地使用這個結構，大大減小計算量。這個block結構也使得并行成為了可能，在進行節點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那麼各個特征的增益計算就可以開多線程進行。

缺點

　　1、level-wise 建樹方式對目前層的所有葉子節點一視同仁，有些葉子節點分裂收益非常小，對結果沒影響，但還是要分裂，加重了計算代價。

　　2、預排序方法空間消耗比較大，不僅要儲存特征值，也要儲存特征的排序索引，同時時間消耗也大，在周遊每個分裂點時都要計算分裂增益(不過這個缺點可以被近似算法所克服)

五 lightGBM

它是微軟出的新的boosting架構，基本原理與XGBoost一樣，隻是在架構上做了一優化（重點在模型的訓練速度的優化）。

關于lightGBM的介紹參考：比XGBOOST更快–LightGBM介紹

與XGboost對比

　　1、xgboost采用的是level-wise的分裂政策，而lightGBM采用了leaf-wise的政策.

• level-wise：指對每一層所有節點做無差别分裂，可能有些節點的增益非常小，對結果影響不大，但是xgboost也進行了分裂,帶來了沒必要的開銷。
• leaf-wise：指在目前所有葉子節點中選擇分裂收益最大的節點進行分裂，如此遞歸進行，容易出現過拟合，是以需要做最大深度限制，進而避免過拟合。

　　2、lightgbm使用了基于histogram的決策樹算法，這一點不同與xgboost中的 exact 算法（tree_method 可以使用 hist參數），histogram算法在記憶體和計算代價上都有不小優勢。

　　（1）記憶體上優勢：很明顯，直方圖算法的記憶體消耗為(#data* #features * 1Bytes)(因為對特征分桶後隻需儲存特征離散化之後的值)，而xgboost的exact算法記憶體消耗為：(2 * #data * #features* 4Bytes)，因為xgboost既要儲存原始feature的值，也要儲存這個值的順序索引，這些值需要32位的浮點數來儲存。

　　（2）計算上的優勢，預排序算法在選擇好分裂特征計算分裂收益時需要周遊所有樣本的特征值，時間為(#data),而直方圖算法隻需要周遊桶就行了，時間為(#bin)

　　3、直方圖做差加速

一個子節點的直方圖可以通過父節點的直方圖減去兄弟節點的直方圖得到，進而加速計算。

　　4、lightgbm支援直接輸入categorical 的feature

在對離散特征分裂時，每個取值都當作一個桶，分裂時的增益算的是”是否屬于某個category“的gain。類似于one-hot編碼。

　　5、多線程優化

lightgbm哪些方面做了并行？

1. Feature Parallel

一般的feature parallel就是對資料做垂直分割（partiion data vertically，就是對屬性分割），然後将分割後的資料分散到各個worker上，各個workers計算其擁有的資料的best splits point, 之後再彙總得到全局最優分割點。但是lightgbm說這種方法通訊開銷比較大，lightgbm的做法是每個worker都擁有所有資料，再分割？（沒懂，既然每個worker都有所有資料了，再彙總有什麼意義？這個并行展現在哪裡？？）

2. Data Parallel

傳統的data parallel是将對資料集進行劃分，也叫 平行分割(partion data horizontally)， 分散到各個workers上之後，workers對得到的資料做直方圖，彙總各個workers的直方圖得到全局的直方圖。 lightgbm也claim這個操作的通訊開銷較大，lightgbm的做法是使用”Reduce Scatter“機制，不彙總所有直方圖，隻彙總不同worker的不同feature的直方圖(原理？)，在這個彙總的直方圖上做split，最後同步。