從零解讀 Xgboost 算法 (原理+代碼)
文中涉及到的公式和注解都可以左右滑動查看全部，涉及到的代碼去這里下載：https://github.com/DA-southampton/NLP_ability
全文目錄如下：
0.提升樹
1. xgboost原理解讀
1.0 學習路徑：
1.1 目標函數(shù)
1.2 泰勒公式對目標函數(shù)近似展開
1.3 樹的參數(shù)化
1.4尋找樹的形狀-特征分裂
2.工程實現(xiàn)細節(jié)
2.0 特征分裂并行尋找
2.1 緩存訪問
2.2 xgboost特征的重要性是如何評估的
3. 代碼匯總
3.0 xgboost 如何篩選特征重要程度
3.1 xgboost完整訓練代碼
xgboost 代碼調(diào)參
xgboost常規(guī)面試題
參考鏈接
0.提升樹
首先要明確一點，xgboost 是基于提升樹的。
什么是提升樹，簡單說，就是一個模型表現(xiàn)不好，我繼續(xù)按照原來模型表現(xiàn)不好的那部分訓練第二個模型，依次類推。
來幾個形象的比喻就是：
做題的時候，第一個人做一遍得到一個分數(shù)，第二個人去做第一個人做錯的題目，第三個人去做第二個人做錯的題目，以此類推，不停的去擬合從而可以使整張試卷分數(shù)可以得到100分（極端情況）。
把這個比喻替換到模型來說，就是真實值為100，第一個模型預測為90，差10分，第二個模型以10為目標值去訓練并預測，預測值為7，差三分，第三個模型以3為目標值去訓練并預測，以此類推。
1. xgboost原理解讀
1.0 學習路徑：
我們xgboost的學習路徑可以按照下面四個步驟來：
構造原始目標函數(shù)問題： xgboost目標函數(shù)包含損失函數(shù)和基于樹的復雜度的正則項； 泰勒展開問題： 原始目標函數(shù)直接優(yōu)化比較難，如何使用泰勒二階展開進行近似； 樹參數(shù)化問題： 假設弱學習器為樹模型，如何將樹參數(shù)化，并入到目標函數(shù)中；這一步的核心就是要明白我們模型優(yōu)化的核心就是優(yōu)化參數(shù)，沒有參數(shù)怎么訓練樣本，怎么對新樣本進行預測呢？ 如何優(yōu)化化簡之后的目標函數(shù)問題，優(yōu)化泰勒展開并模型參數(shù)化之后的的目標函數(shù)，主要包含兩個部分： 如何求得葉子節(jié)點權重 如何進行樹模型特征分割
1.1 目標函數(shù)
1.1.0 原始目標函數(shù)
目標函數(shù)，可以分為兩個部分，一部分是損失函數(shù)，一部分是正則（用于控制模型的復雜度）。
xgboost屬于一種前向迭代的模型，會訓練多棵樹。
對于第t顆樹，第i個樣本的，模型的預測值是這樣的：
進一步，我們可以得到我們的原始目標函數(shù)，如下：
從這個目標函數(shù)我們需要掌握的細節(jié)是，前后部分是兩個維度的問題
兩個累加的變量是不同的:
一個是
i，i這邊代表的是樣本數(shù)量，也就是對每個樣本我們都會做一個損失的計算，這個損失是第t個樹的預測值和真實值之間的差值計算（具體如何度量損失視情況而定）。另一個是累加變量是
j，代表的是樹的數(shù)量，也就是我們每個樹的復雜度進行累加。
需要注意的是我們這里具體的損失函數(shù)是沒有給出定義的，所以它可以是樹模型，也可以是線性模型。
1.1.1 簡單化簡損失函數(shù)
正如上面所說，Xgboost是前向迭代，我們的重點在于第t個樹，所以涉及到前t-1個樹變量或者說參數(shù)我們是可以看做常數(shù)的。
所以我們的損失函數(shù)進一步可以化為如下，其中一個變化是我們對正則項進行了拆分，變成可前t-1項，和第t項：
基于此，在不改變目標函數(shù)精讀的情況下，我們已經(jīng)做了最大的簡化，最核心的點就是我們認為前t-1個樹已經(jīng)訓練好了，所以涉及到的參數(shù)和變量我們當成了常數(shù)。
接下來，我們使用泰勒級數(shù)，對目標函數(shù)近似展開.
1.2 泰勒公式對目標函數(shù)近似展開
使用泰勒公式進行近似展開的核心目標是就是對目標函數(shù)進行化簡，將常數(shù)項抽離出來。
基本泰勒公式展開如下：
損失函數(shù)展開公式細節(jié)推導如下：
所以原有公式進行泰勒公式二階展開，結果為:
進而我們可以得到目標函數(shù)展開公式為如下：
還是那句話，我們可以使用任意一個損失函數(shù)，這里沒有定式。
上述中樹的表達我們都是使用函數(shù)f(x)來表示，本質(zhì)上模型的優(yōu)化求解是在求參數(shù)，所以我們需要對樹模型參數(shù)化才可以進行進一步的優(yōu)化
1.3 樹的參數(shù)化
樹的參數(shù)化有兩個，一個是對樹模型參數(shù)化，一個是對樹的復雜度參數(shù)化。
1.3.0 樹模型參數(shù)化-如何定義一個樹
主要是定義兩個部分：
每棵樹每個葉子節(jié)點的值(或者說每個葉子節(jié)點的權重) w：這是一個向量，因為每個樹有很多葉子節(jié)點樣本到葉子節(jié)節(jié)點的映射關系 q：(大白話就是告訴每個樣本落在當前這個樹的哪一個葉子節(jié)點上)葉子節(jié)點樣本歸屬集合 I：就是告訴每個葉子節(jié)點包含哪些樣本
1.3.1 樹復雜度的參數(shù)化-如何定義樹的復雜度
定義樹的復雜度主要是從兩個部分出發(fā)：
每個樹的葉子節(jié)點的個數(shù)（葉子節(jié)點個數(shù)越少模型越簡單） 葉子節(jié)點的權重值 w（值越小模型越簡單）
對于第二點，我們可以想一下L正則不就是想稀疏化權重，從而使模型變得簡單嗎，其實本質(zhì)是一樣的。
我們樹的復雜度如下：
進而我們可以對樹進行了參數(shù)化，帶入到目標函數(shù)我們可以得到如下：
隨后我們做如下定義：
葉子節(jié)點 ?j ?所包含的樣本的一階導數(shù)累加之和為：
葉子節(jié)點 ?j ?所包含的樣本的二階導數(shù)累加之和為：
進而我們可以進一步化簡為：
針對這個目標函數(shù)，我們對Xgboost優(yōu)有面臨兩個問題：
第一就是如何求得：這一步其實很簡單，直接使用目標函數(shù)對求導就可以。
還有一個就是如何做到特征的分裂，接下來我們詳細聊一下如何去做
1.4尋找樹的形狀-特征分裂
首先明確一點，我們增益使用的是基于當前特征分裂點前后，目標函數(shù)的差值。
我們當然是希望，使用這個分裂點，目標函數(shù)降低的越多越好。
1.4.0 貪心算法
本質(zhì)上是做兩次循環(huán)，第一個是是針對每個特征的每個分割點做一次循環(huán)，計算收益，從而選擇此特征的最佳分割點。分裂收益使用的是分裂之后的目標函數(shù)的變化差值。
第二個循環(huán)是對樣本所有特征的循環(huán)，從中挑選出收益最大的特征。
簡單說就是首先找到基于每個特征找到收益最大的分割點，然后基于所有特征找到收益最大的特征。
然后在這所有的循環(huán)中，挑出增益最大的那個分割點
1.4.1 近似算法-分位數(shù)候選點
對于每個特征，不去暴力搜索每個值，而是使用分位點
根據(jù)樣本數(shù)量選擇三分位點或者四分位點等等；
或者根據(jù)二階導數(shù)（也就是梯度）作為權重進行劃分
也就是說原來是某個特征的所有取值是候選點，現(xiàn)在是某個特征的分位點作為候選點。
2.工程實現(xiàn)細節(jié)
2.0 特征分裂并行尋找
尋找特征分隔點需要對特征值進行排序，這個很耗時間。我們可以在訓練之前先按照特征對樣本數(shù)據(jù)進行排序，并分別保存在不同的塊結構中。每個塊都有一個按照某個特征排好序的特征加對應的一階二階導數(shù)。
對于不同的特征的特征劃分點，XGBoost分別在不同的線程中并行選擇分裂的最大增益
2.1 緩存訪問
特征是排好序，但是通過索引獲取一階二階導數(shù)值是不連續(xù)的，造成cpu緩存命中率低；xgboost解決辦法：為每個線程分配一個連續(xù)的緩存區(qū)，將需要的梯度信息存放在緩沖區(qū)中，這樣就連續(xù)了；
同時通過設置合理的分塊的大小，充分利用了CPU緩存進行讀取加速（cache-aware access）。使得數(shù)據(jù)讀取的速度更快。另外，通過將分塊進行壓縮（block compressoin）并存儲到硬盤上，并且通過將分塊分區(qū)到多個硬盤上實現(xiàn)了更大的IO。
2.2 xgboost特征的重要性是如何評估的
weight ：該特征在所有樹中被用作分割樣本的特征的總次數(shù)。 gain ：該特征在其出現(xiàn)過的所有樹中產(chǎn)生的平均增益（我自己的理解就是目標函數(shù)減少值總和的平均值，這里也可以使用增益之和）。 cover ：該特征在其出現(xiàn)過的所有樹中的平均覆蓋范圍。
這里有一個細節(jié)需要注意，就是節(jié)點分割的時候，之前用過的特征在當前節(jié)點也是可以使用的，所以weight才是有意義的。
3. 代碼匯總
3.0 xgboost 如何篩選特征重要程度
xgboost 模型訓練完畢之后，可以查一下每個特征在模型中的重要程度;
進一步的，我們可以暴力搜索一下，通過這個相關性篩選一下模型，看能不能在特征數(shù)量減少的情況下，模型表現(xiàn)能力不變甚至提升或者有我們可以接受的降低幅度。
核心代碼如下(完整運行去github吧)
##?如何獲取特征重要程度
print(model.feature_importances_)
plot_importance(model)
pyplot.show()
##?如何篩選特征
selection?=?SelectFromModel(model,?threshold=thresh,?prefit=True)
完整代篇幅太大，不展示在這里，直接去github：
3.1 xgboost完整訓練代碼
完整代篇幅太大，不展示在這里，直接去github：
xgboost 代碼調(diào)參
框架參數(shù)：
booster：弱學習器類型
objective：分類還是回歸問題以及對應的損失函數(shù)
n_estimators：弱學習器的個數(shù)
弱學習器參數(shù)：
max_depth：樹的深度
min_child_weight：最小節(jié)點的權重閾值，小于這個值，節(jié)點不會再分裂；
gamma：節(jié)點分裂帶來損失最小閾值，我們使用目標函數(shù)之差計算增益，小于這個閾值的時候，不再分裂
learning_rate:控制每個弱學習器的權重縮減系；這個系數(shù)會乘以葉子節(jié)點的權重值，它的作用在于削弱每個樹的影響力，如果學習率小，對應的弱學習器的個數(shù)就應該增加。
xgboost常規(guī)面試題
與GBDT相比，Xgboost的優(yōu)化點： 算法本身的優(yōu)化：首先GBDT只支持決策樹，Xgboost除了支持決策樹，可以支持多種弱學習器，可以是默認的gbtree, 也就是CART決策樹，還可以是線性弱學習器gblinear以及DART；其次GBDT損失函數(shù)化簡的時候進行的是一階泰勒公式的展開，而Xgboost使用的是二階泰勒公式的展示。還有一點是Xgboost的目標函數(shù)加上了正則項，這個正則項是對樹復雜度的控制，防止過擬合。 可以處理缺失值。嘗試通過枚舉所有缺失值在當前節(jié)點是進入左子樹，還是進入右子樹更優(yōu)來決定一個處理缺失值默認的方向 運行效率：并行化，單個弱學習器最耗時的就是決策樹的分裂過程，對于不同特征的特征分裂點，可以使用多線程并行選擇。這里想提一下，我自己理解，這里應該針對的是每個節(jié)點，而不是每個弱學習器。這里其實我當時深究了一下，有點混亂。為什么是針對每個節(jié)點呢？因為我每個節(jié)點也有很多特征，所以在每個節(jié)點上，我并行（多線程）除了多個特征，每個線程都在做尋找增益最大的分割點。還有需要注意的一點是Xgboost在并行處理之前，會提前把樣本按照特征大小排好序，默認都放在右子樹，然后遞歸的從小到大拿出一個個的樣本放到左子樹，然后計算對基于此時的分割點的增益的大小，然后記錄并更新最大的增益分割點。
參考鏈接
劉建平：https://www.cnblogs.com/pinard/p/11114748.html
B站視頻：https://www.bilibili.com/video/BV1mZ4y1j7UJ?from=search&seid=4849972439430408952
知乎：Microstrong：https://zhuanlan.zhihu.com/p/83901304
更多閱讀
特別推薦
點擊下方閱讀原文加入社區(qū)會員