RF、GBDT、XGBoost常見面試題整理

04-28

1：RF與GBDT之間的區別

（1）相同點

都是由多棵樹組成
最終的結果都是由多棵樹一起決定

（2）不同點

組成隨機森林的樹可以分類樹也可以是回歸樹，而GBDT只由回歸樹組成
組成隨機森林的樹可以並行生成，而GBDT是串列生成
隨機森林的結果是多數表決表決的，而GBDT則是多棵樹累加之和
隨機森林對異常值不敏感，而GBDT對異常值比較敏感
隨機森林是通過減少模型的方差來提高性能，而GBDT是減少模型的偏差來提高性能的
隨機森林不需要進行數據預處理，即特徵歸一化。而GBDT則需要進行特徵歸一化

2：分類樹和回歸樹的區別

（1）分類樹使用信息增益或增益比率來劃分節點；每個節點樣本的類別情況投票決定測試樣本的類別。

（2)回歸樹使用最小化均方差劃分節點；每個節點樣本的均值作為測試樣本的回歸預測值

3：說一下GBDT

GBDT的核心就在於，每一棵樹學的是之前所有樹結論和的殘差，這個殘差就是一個加預測值後能得真實值的累加量

4：Xgboost和GBDT的區別

(1)傳統GBDT以CART作為基分類器，xgboost還支持線性分類器，這個時候xgboost相當於帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。節點分裂的方式不同，gbdt是用的gini係數，xgboost是經過優化推導後的

(2)傳統GBDT在優化時只用到一階導數信息，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。為什麼xgboost要用泰勒展開，優勢在哪裡？xgboost使用了一階和二階偏導, 二階導數有利於梯度下降的更快更准. 使用泰勒展開取得函數做自變數的二階導數形式, 可以在不選定損失函數具體形式的情況下, 僅僅依靠輸入數據的值就可以進行葉子分裂優化計算, 本質上也就把損失函數的選取和模型演算法優化/參數選擇分開了. 這種去耦合增加了xgboost的適用性, 使得它按需選取損失函數, 可以用於分類, 也可以用於回歸。

(3)Xgboost在代價函數里加入了正則項，用於控制模型的複雜度，降低了過擬合的可能性。正則項里包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和

(4)Xgboost工具支持並行。boosting不是一種串列的結構嗎?怎麼並行的？注意xgboost的並行不是tree粒度的並行，xgboost也是一次迭代完才能進行下一次迭代的（第t次迭代的代價函數里包含了前面t-1次迭代的預測值）。xgboost的並行是在特徵粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特徵的值進行排序（因為要確定最佳分割點），xgboost在訓練之前，預先對數據進行了排序，然後保存為block結構，後面的迭代中重複地使用這個結構，大大減小計算量。這個block結構也使得並行成為了可能，在進行節點的分裂時，需要計算每個特徵的增益，最終選增益最大的那個特徵去做分裂，那麼各個特徵的增益計算就可以開多線程進行

5:N問GBDT

(1)怎樣設置單棵樹的停止生長條件？

答：A. 節點分裂時的最小樣本數

B. 最大深度

C. 最多葉子節點數

D. loss滿足約束條件

(2)如何評估特徵的權重大小？

答：a. 通過計算每個特徵在訓練集下的信息增益，最後計算每個特徵信息增益與所有特徵信息增益之和的比例為權重值。

b. 借鑒投票機制。用相同的gbdt參數對w每個特徵訓練出一個模型，然後在該模型下計算每個特徵正確分類的個數，最後計算每個特徵正確分類的個數與所有正確分類個數之和的比例為權重值。

(3)當增加樣本數量時，訓練時長是線性增加嗎？

答：不是。因為生成單棵決策樹時，對於

，

損失函數極小值

與樣本數量N不是線性相關

(4)當增加樹的棵樹時，訓練時長是線性增加嗎？

答：不是。因為每棵樹的生成的時間複雜度不一樣。

(5)當增加一個棵樹葉子節點數目時，訓練時長是線性增加嗎？

答：不是。葉子節點數和每棵樹的生成的時間複雜度不成正比。

(6)每個節點上都保存什麼信息？

答：中間節點保存某個特徵的分割值，葉結點保存預測是某個類別的概率。

(7)如何防止過擬合？

答：a. 增加樣本（data bias or small data的緣故），移除雜訊。

b. 減少特徵，保留重要的特徵（可以用PCA等對特徵進行降維）。

c. 對樣本進行採樣（類似bagging）。就是建樹的時候，不是把所有的樣本都作為輸入，而是選擇一個子集。

d. 對特徵進行採樣。類似樣本採樣一樣, 每次建樹的時候，只對部分的特徵進行切分。

(8) gbdt在訓練和預測的時候都用到了步長，這兩個步長一樣么？都有什麼用，如果不一樣，為什麼？怎麼設步長的大小？（太小？太大？）在預測時，設太大對排序結果有什麼影響？跟shrinking裡面的步長一樣么這兩個步長一樣么？

答：訓練跟預測時，兩個步長是一樣的，也就是預測時的步長為訓練時的步長，從訓練的過程可以得知（更新當前迭代模型的時候）。

都有什麼用，如果不一樣，為什麼？答：它的作用就是使得每次更新模型的時候，使得loss能夠平穩地沿著負梯度的方向下降，不至於發生震蕩。

那麼怎麼設步長的大小?

答：有兩種方法，一種就是按策略來決定步長，另一種就是在訓練模型的同時，學習步長。

A. 策略：

a 每個樹步長恆定且相等，一般設較小的值；

b 開始的時候給步長設一個較小值，隨著迭代次數動態改變，或者說衰減。

B. 學習：

因為在訓練第k棵樹的時候，前k-1棵樹時已知的，而且求梯度的時候是利用前k-1棵樹來獲得。所以這個時候，就可以把步長當作一個變數來學習。

（太小？太大？）在預測時，對排序結果有什麼影響？

答：如果步長過大，在訓練的時候容易發生震蕩，使得模型學不好，或者完全沒有學好，從而導致模型精度不好。

而步長過小，導致訓練時間過長，即迭代次數較大，從而生成較多的樹，使得模型變得複雜，容易造成過擬合以及增加計算量。

不過步長較小的話，使訓練比較穩定，總能找到一個穩定的局部最優解。

個人覺得過大過小的話，模型的預測值都會偏離真實情況（可能比較嚴重），從而導致模型精度不好。

跟shrinking裡面的步長一樣么？答：這裡的步長跟shrinking裡面的步長是一致的。

(9)boosting的本意是是什麼？跟bagging，random forest，adaboost，gradient boosting有什麼區別？

答：Bagging:

可以看成是一種圓桌會議，或是投票選舉的形式。通過訓練多個模型，將這些訓練好的模型進行加權組合來獲得最終的輸出結果(分類/回歸)，一般這類方法的效果，都會好於單個模型的效果。在實踐中，在特徵一定的情況下，大家總是使用Bagging的思想去提升效果。例如kaggle上的問題解決，因為大家獲得的數據都是一樣的，特別是有些數據已經過預處理。

基本的思路比較簡單，就是：訓練時，使用replacement的sampling方法，sampling一部分訓練數據k次並訓練k個模型；預測時，使用k個模型，如果為分類，則讓k個模型均進行分類並選擇出現次數最多的類（每個類出現的次數佔比可以視為置信度）；如為回歸，則為各類器返回的結果的平均值。在該處，Bagging演算法可以認為每個分類器的權重都一樣由於每次迭代的採樣是獨立的，所以bagging可以並行。

而boosting的採樣或者更改樣本的權重依賴於上一次迭代的結果，在迭代層面上是不能並行的。

Random forest：

隨機森林在bagging的基礎上做了修改。

A. 從樣本集散用Boostrap採樣選出n個樣本，預建立CART

B. 在樹的每個節點上，從所有屬性中隨機選擇k個屬性/特徵，選擇出一個最佳屬性/特徵作為節點

C. 重複上述兩步m次，i.e.build m棵cart

D. 這m棵cart形成random forest。

隨機森林可以既處理屬性是離散的量，比如ID3演算法，也可以處理屬性為連續值得量，比如C4.5演算法。

這裡的random就是指：

A. boostrap中的隨機選擇樣本

B. random subspace的演算法中從屬性/特徵即中隨機選擇k個屬性/特徵，每棵樹節點分裂時，從這隨機的k個屬性/特徵，選擇最優的。

Boosting:

boosting是」提升」的意思。一般Boosting演算法都是一個迭代的過程，每一次新的訓練都是為了改進上一次的結果。

boosting在選擇hyperspace的時候給樣本加了一個權值，使得loss function盡量考慮那些分錯類的樣本（如分錯類的樣本weight大）。怎麼做的呢？

boosting重採樣的不是樣本，而是樣本的分布，對於分類正確的樣本權值低，分類錯誤的樣本權值高(通常是邊界附近的樣本)，最後的分類器是很多弱分類器的線性疊加(加權組合)。

或者這麼理解也是可以的:

如果弱學習器與強學習器是等價的, 當強學習器難以學習時(如強學習器高度非線性等)，問題就可以轉化為這樣的學習問題：

學習多個弱分類器(弱分類器容易學習)，並將多個弱分類器組合成一個強分類器(與原來的強學習器等價)。

Adaboosting:

這其實思想相當的簡單，大概是對一份數據，建立M個模型(比如分類)，而一般這種模型比較簡單，稱為弱分類器(weak learner)。每次分類都將上一次分錯的數據權重提高一點，對分對的數據權重降低一點，再進行分類。這樣最終得到的分類器在測試數據與訓練數據上都可以得到比較好的效果。

每次迭代的樣本是一樣的，即沒有採樣過程，不同的是不同的樣本權重不一樣。(當然也可以對樣本/特徵進行採樣，這個不是adaboosting的原意)。

另外，每個分類器的步長由在訓練該分類器時的誤差來生成。

Gradient boosting:

每一次的計算是為了減少上一次的殘差(residual)，而為了消除殘差，我們可以在殘差減少的梯度 (Gradient)方向上建立一個新的模型。所以說在Gradient Boost中，每個新模型是為了使之前模型的殘差往梯度方向減少，與傳統Boost對正確，錯誤的樣本進行加權有著很大的區別。(或者這樣理解：每一次建立模型是在之前建立模型損失函數的梯度下降方向。這句話有一點拗口，損失函數(loss function)描述的是模型的不靠譜程度，損失函數越大，則說明模型越容易出錯(其實這裡有一個方差、偏差均衡的問題, 但是這裡就假設損失函數越大, 模型越容易出錯)。如果我們的模型能夠讓損失函數持續的下降, 則說明我們的模型在不停的改進, 而最好的方式就是讓損失函數在其Gradient的方向上下降)。

(10)gbdt中哪些部分可以並行？

答：A. 計算每個樣本的負梯度

B. 分裂挑選最佳特徵及其分割點時，對特徵計算相應的誤差及均值時

C. 更新每個樣本的負梯度時

D. 最後預測過程中，每個樣本將之前的所有樹的結果累加的時候

(11) 樹生長成畸形樹，會帶來哪些危害，如何預防？

答：在生成樹的過程中，加入樹不平衡的約束條件。這種約束條件可以是用戶自定義的。

例如對樣本集中分到某個節點，而另一個節點的樣本很少的情況進行懲罰。

參考博客：N問GBDT（1-12答案） - CSDN博客