随機森林，GBDT，XGBoost的對比

随機森林 RF RandomForest

　　随機森林的內建學習方法是bagging ，但是和bagging 不同的是bagging隻使用bootstrap有放回的采樣樣本，但随機森林即随機采樣樣本，也随機選擇特征，是以防止過拟合能力更強，降低方差。

使用的融合方法：bagging

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

随機森林進一步在決策樹訓練時加入随機屬性選擇：

　　如果有M個輸入變量，每個節點都将随機選擇m(m<M)個特定的變量，然後運用這m個變量來确定最佳的分裂點。在決策樹的生成過程中，m的值是保持不變的。m一般取M均方根

　　是以随機森林即有樣本随機性（來自bagging的boostrap sampling）又有特征随機性。

随機森林的優缺點

優點：

a）随機森林算法能解決分類與回歸兩種類型的問題，表現良好，由于是內建學習，方差和偏差都比較低，泛化性能優越；

b）随機森林對于高維資料集的處理能力很好，它可以處理成千上萬的輸入變量，并确定最重要的變量，是以被認為是一個不錯的降維方法。此外，該模型能夠輸出特征的重要性程度，這是一個非常實用的功能。

c) 可以應對缺失資料；

d）當存在分類不平衡的情況時，随機森林能夠提供平衡資料集誤差的有效方法；

e ) 高度并行化，易于分布式實作

f) 由于是樹模型 ，不需要歸一化即可之間使用

缺點：

a）随機森林在解決回歸問題時并沒有像它在分類中表現的那麼好，這是因為它并不能給出一個連續型的輸出。當進行回歸時，随機森林不能夠作出超越訓練集資料範圍的預測，這可能導緻在對某些還有特定噪聲的資料進行模組化時出現過度拟合。

b）對于許多統計模組化者來說，随機森林給人的感覺像是一個黑盒子——你幾乎無法控制模型内部的運作，隻能在不同的參數和随機種子之間進行嘗試。

c) 忽略屬性之間的相關性

RF的調參

通用的調參方法：

1. grid search 網格搜尋。 sklearn 提供了相應的方GridSearchCV。即使用cross validation，對模型疊代的選用候選參數進行交叉驗證，取結果最好的參數，優點：效果好，相當于窮舉的思想，調參得到了候選參數裡全局最優化結果。 缺點：計算複雜。 一般做競賽的小項目選這個啦。
2. 基于貪心的坐标下降搜尋。即固定其他參數，把某個參數取得最好。這樣疊代一遍得到最終結果。優點：計算量少，缺點：可能不是全局最優值、陷入局部最優解。
3. 随機網格搜尋：防止 網格搜尋間隔過大而跳過最優值，而随機可以相對單個參數取到更多的值。

•  n_estimators越多結果更穩定（方差越小），是以隻要允許内，數目越大越好, 但計算量會大增。隻有這個參數對結果的影響是越大越好，其他參數都是中間取得最優值。
• “分裂條件”（criterion）對模型的準确度的影響也不一樣，該參數需要在實際運用時靈活調整，可取gini或者資訊增益比？。
• 每棵樹最大特征數（max_features） 一般用sqrt(總特征數)。
• 調整“最大葉節點數”（max_leaf_nodes）以及“最大樹深度”（max_depth）之一，可以粗粒度地調整樹的結構：葉節點越多或者樹越深，意味着子模型的偏差越低，方差越高；同時，調整“分裂所需最小樣本數”（min_samples_split）、“葉節點最小樣本數”（min_samples_leaf）及“葉節點最小權重總值”（min_weight_fraction_leaf），可以更細粒度地調整樹的結構：分裂所需樣本數越少或者葉節點所需樣本越少，也意味着子模型越複雜。

随機森林的推廣(Extra Trees)

extra trees是RF的一個變種, 原理幾乎和RF一模一樣，僅有差別有：

1） 對于每個決策樹的訓練集，RF采用的是随機采樣bootstrap來選擇采樣集作為每個決策樹的訓練集，而extra trees一般不采用随機采樣，即每個決策樹采用原始訓練集。

2） 在標明了劃分特征後，RF的決策樹會基于資訊增益，基尼系數，均方差之類的原則，選擇一個最優的特征值劃分點，這和傳統的決策樹相同。但是extra trees比較的激進，他會随機的選擇一個特征值來劃分決策樹。

從第二點可以看出，由于随機選擇了特征值的劃分點位，而不是最優點位，這樣會導緻生成的決策樹的規模一般會大于RF所生成的決策樹。也就是說，模型的方差相對于RF進一步減少，但是bias相對于RF進一步增大。在某些時候，extra trees的泛化能力比RF更好

GBDT (Gradient Boosting Decision Tree)

gbdt的基本原理是boost 裡面的 boosting tree（提升樹），并使用 gradient boost。

GBDT中的樹都是回歸樹，不是分類樹 ，因為gradient boost 需要按照損失函數的梯度近似的拟合殘差，這樣拟合的是連續數值，是以隻有回歸樹。

梯度提升 gradient boosting:

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

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

對于梯度提升樹其學習流程與提升樹類似隻是不再使用殘差作為新的訓練資料而是使用損失函數的梯度作為新的新的訓練資料的y值，具體的來說就是使用損失函數對f（x）求梯度然後帶入fm-1（x）計算：

GDBT與提升樹之間的關系：

提升樹模型每一次的提升都是靠上次的預測結果與訓練資料的label值內插補點作為新的訓練資料進行重新訓練，GDBT則是将殘差計算替換成了損失函數的梯度方向，将上一次的預測結果帶入梯度中求出本輪的訓練資料，這兩種模型就是在生成新的訓練資料時采用了不同的方法，那麼在這個背後有啥差別？使用殘差有啥不好？

李航老師《統計學習方法》中提到了在使用平方誤差損失函數和指數損失函數時，提升樹的殘差求解比較簡單，但是在使用一般的損失誤差函數時，殘差求解起來不是那麼容易，是以就是用損失函數的負梯度在目前模型的值作為回歸問題中殘差（均方誤差）或者殘差的近似值。 

（來自MLAPP）

XGBoost

XGBoost比GBDT好的地方：

二階泰勒展開

節點分數懲罰正則

增益計算不同，gbdt是gini，xgb是優化推導公式

以下來自 一步一步了解GB、GBDT、xgboost

Xgboost是GB算法的高效實作，xgboost中的基學習器除了可以是CART（gbtree）也可以是線性分類器（gblinear）。下面所有的内容來自原始paper，包括公式。

(1). xgboost在目标函數中顯示的加上了正則化項，基學習為CART時，正則化項與樹的葉子節點的數量T和葉子節點的值有關。

(2). GB中使用Loss Function對f(x)的一階導數計算出僞殘差用于學習生成fm(x)，xgboost不僅使用到了一階導數，還使用二階導數。

第t次的loss：

對上式做二階泰勒展開：g為一階導數，h為二階導數

(3). 上面提到CART回歸樹中尋找最佳分割點的衡量标準是最小化均方差，xgboost尋找分割點的标準是最大化，lamda，gama與正則化項相關

xgboost算法的步驟和GB基本相同，都是首先初始化為一個常數，gb是根據一階導數ri，xgboost是根據一階導數gi和二階導數hi，疊代生成基學習器，相加更新學習器。

xgboost與gdbt除了上述三點的不同，xgboost在實作時還做了許多優化：

• 在尋找最佳分割點時，考慮傳統的枚舉每個特征的所有可能分割點的貪心法效率太低，xgboost實作了一種近似的算法。大緻的思想是根據百分位法列舉幾個可能成為分割點的候選者，然後從候選者中根據上面求分割點的公式計算找出最佳的分割點。
• xgboost考慮了訓練資料為稀疏值的情況，可以為缺失值或者指定的值指定分支的預設方向，這能大大提升算法的效率，paper提到50倍。
• 特征列排序後以塊的形式存儲在記憶體中，在疊代中可以重複使用；雖然boosting算法疊代必須串行，但是在處理每個特征列時可以做到并行。
• 按照特征列方式存儲能優化尋找最佳的分割點，但是當以行計算梯度資料時會導緻記憶體的不連續通路，嚴重時會導緻cache miss，降低算法效率。paper中提到，可先将資料收集到線程内部的buffer，然後再計算，提高算法的效率。
• xgboost 還考慮了當資料量比較大，記憶體不夠時怎麼有效的使用磁盤，主要是結合多線程、資料壓縮、分片的方法，盡可能的提高算法的效率。

以下内容來自wepon 作者：wepon

連結：https://www.zhihu.com/question/41354392/answer/98658997

• 傳統GBDT以CART作為基分類器，xgboost還支援線性分類器，這個時候xgboost相當于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。
• 傳統GBDT在優化時隻用到一階導數資訊，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。順便提一下，xgboost工具支援自定義代價函數，隻要函數可一階和二階求導。
• xgboost在代價函數裡加入了正則項，用于控制模型的複雜度。正則項裡包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過拟合，這也是xgboost優于傳統GBDT的一個特性。
• Shrinkage（縮減），相當于學習速率（xgboost中的eta）。xgboost在進行完一次疊代後，會将葉子節點的權重乘上該系數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間。實際應用中，一般把eta設定得小一點，然後疊代次數設定得大一點。（補充：傳統GBDT的實作也有學習速率）
• 列抽樣（column subsampling）即特征抽樣。xgboost借鑒了随機森林的做法，支援列抽樣，不僅能降低過拟合，還能減少計算，這也是xgboost異于傳統gbdt的一個特性。

• 對缺失值的處理。對于特征的值有缺失的樣本，xgboost可以自動學習出它的分裂方向。
• xgboost工具支援并行。boosting不是一種串行的結構嗎?怎麼并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次疊代完才能進行下一次疊代的（第t次疊代的代價函數裡包含了前面t-1次疊代的預測值）。xgboost的并行是在特征粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特征的值進行排序（因為要确定最佳分割點），xgboost在訓練之前，預先對資料進行了排序，然後儲存為block結構，後面的疊代中重複地使用這個結構，大大減小計算量。這個block結構也使得并行成為了可能，在進行節點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那麼各個特征的增益計算就可以開多線程進行。

• 可并行的近似直方圖算法。樹節點在進行分裂時，我們需要計算每個特征的每個分割點對應的增益，即用貪心法枚舉所有可能的分割點。當資料無法一次載入記憶體或者在分布式情況下，貪心算法效率就會變得很低，是以xgboost還提出了一種可并行的近似直方圖算法，用于高效地生成候選的分割點。
• 多種語言封裝支援。

XGBoost 調參

參考資料：

chentq的slides  http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

chentq的paper  http://arxiv.org/abs/1603.02754

chentq在52cs上的中文博文  http://www.52cs.org/?p=429

微網誌上分享的 xgboost導讀和實戰.pdf XGBoost all in one

轉自 http://www.cnblogs.com/sarahp/p/6900572.html