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