100天搞定機(jī)器學(xué)習(xí)|Day60 遇事不決，XGBoost

XGBoost 是一種集大成的機(jī)器學(xué)習(xí)算法，可用于回歸，分類和排序等各種問(wèn)題，在機(jī)器學(xué)習(xí)大賽及工業(yè)領(lǐng)域被廣泛應(yīng)用。成功案例包括：網(wǎng)頁(yè)文本分類、顧客行為預(yù)測(cè)、情感挖掘、廣告點(diǎn)擊率預(yù)測(cè)、惡意軟件分類、物品分類、風(fēng)險(xiǎn)評(píng)估、大規(guī)模在線課程退學(xué)率預(yù)測(cè)。

XGBoost是初學(xué)者最值得深度理解的模型之一，它將決策樹(shù)、boosting、GBDT 等知識(shí)點(diǎn)串聯(lián)起來(lái)，強(qiáng)烈建議大家都手?jǐn)]一波。本文我將從XGBoost淵源及優(yōu)點(diǎn)、模型原理及優(yōu)化推導(dǎo)、XGBoost模型參數(shù)解析、調(diào)參實(shí)例，XGBoost可視化等方面介紹XGBoost。提醒一下，XGBoost 是在 GBDT 基礎(chǔ)上的改進(jìn)，閱讀本文需對(duì) GBDT 有一定的了解，不熟悉的同學(xué)可以看一下前篇：100天搞定機(jī)器學(xué)習(xí)|Day58 機(jī)器學(xué)習(xí)入門：硬核拆解GBDT

XGBoost淵源及優(yōu)勢(shì)

在數(shù)據(jù)建模中，經(jīng)常采用Boosting方法，該方法將成百上千個(gè)分類準(zhǔn)確率較低的樹(shù)模型組合起來(lái)，成為一個(gè)準(zhǔn)確率很高的預(yù)測(cè)模型。這個(gè)模型會(huì)不斷地迭代，每次迭代就生成一顆新的樹(shù)。但在數(shù)據(jù)集較復(fù)雜的時(shí)候，可能需要幾千次迭代運(yùn)算，這將造成巨大的計(jì)算瓶頸。

針對(duì)這個(gè)問(wèn)題，華盛頓大學(xué)的陳天奇博士開(kāi)發(fā)的XGBoost（eXtreme Gradient Boosting）基于C++通過(guò)多線程實(shí)現(xiàn)了回歸樹(shù)的并行構(gòu)建，并在原有Gradient Boosting算法基礎(chǔ)上加以改進(jìn)，從而極大地提升了模型訓(xùn)練速度和預(yù)測(cè)精度。

XGBoost 主要優(yōu)勢(shì)如下：

1、GBDT在優(yōu)化時(shí)只用到一階導(dǎo)數(shù)信息，XGBoost同時(shí)用到了一階和二階導(dǎo)數(shù)，還支持自定義損失函數(shù)，前提是損失函數(shù)可一階和二階求導(dǎo)；

2、加入了正則項(xiàng)，用于控制模型的復(fù)雜度，防止過(guò)擬合；

3、借鑒了隨機(jī)森林的做法，支持列抽樣(隨機(jī)選擇特征)，不僅能降低過(guò)擬合，還能減少計(jì)算；

4、尋找最佳分割點(diǎn)時(shí)，實(shí)現(xiàn)了一種近似法，還考慮了稀疏數(shù)據(jù)集、缺失值的處理，大大提升算法的效率；

5、支持并行；

6、近似直方圖算法，用于高效地生成候選的分割點(diǎn)；

7、在算法實(shí)現(xiàn)時(shí)做了很多優(yōu)化，大大提升了算法的效率，內(nèi)存空間不夠時(shí)，利用了分塊、預(yù)取、壓縮、多線程協(xié)作的思想。

XGBoost模型原理及優(yōu)化推導(dǎo)

XGBoost其實(shí)也是GBDT的一種，還是加性模型和前向優(yōu)化算法。

加法模型就是說(shuō)強(qiáng)分類器由一系列弱分類器線性相加而成。一般組合形式如下：

其中，就是一個(gè)個(gè)的弱分類器，是弱分類器學(xué)習(xí)到的最優(yōu)參數(shù)，就是弱學(xué)習(xí)在強(qiáng)分類器中所占比重，P是所有和的組合。這些弱分類器線性相加組成強(qiáng)分類器。

前向分步就是說(shuō)在訓(xùn)練過(guò)程中，下一輪迭代產(chǎn)生的分類器是在上一輪的基礎(chǔ)上訓(xùn)練得來(lái)的。也就是可以寫成這樣的形式：

XGBoost 的模型是什么樣子的呢？

• 其中 K 是樹(shù)的棵數(shù)。
• 是回歸樹(shù)，，滿足
• q表示每棵樹(shù)的結(jié)構(gòu)，它會(huì)將一個(gè)訓(xùn)練樣本實(shí)例映射到相對(duì)應(yīng)的葉子索引上。
• T是樹(shù)中的葉子數(shù)。
• 每個(gè)對(duì)應(yīng)于一個(gè)獨(dú)立的樹(shù)結(jié)構(gòu)q和葉子權(quán)重w。
• 是所有回歸樹(shù)組成的函數(shù)空間。

與決策樹(shù)不同的是，每棵回歸樹(shù)包含了在每個(gè)葉子上的一個(gè)連續(xù)分值，我們使用來(lái)表示第i個(gè)葉子上的分值。對(duì)于一個(gè)給定樣本實(shí)例，我們會(huì)使用樹(shù)上的決策規(guī)則(由q給定)來(lái)將它分類到葉子上，并通過(guò)將相應(yīng)葉子上的分值(由w給定)做求和，計(jì)算最終的預(yù)測(cè)值。

XGBoost的學(xué)習(xí)

為了在該模型中學(xué)到這些函數(shù)集合，我們會(huì)對(duì)下面的正則化目標(biāo)函數(shù)做最小化：

其中： 是損失函數(shù)，常見(jiàn)的有 2 種：
平方損失函數(shù)：
邏輯回歸損失函數(shù)：

: 正則化項(xiàng)，用于懲罰復(fù)雜模型，避免模型過(guò)分?jǐn)M合訓(xùn)練數(shù)據(jù)。常用的正則有L1正則與L2正則:
L1正則（lasso）:
L2正則:

下一步就是對(duì)目標(biāo)函數(shù)進(jìn)行學(xué)習(xí)，每一次保留原來(lái)的模型不變，加入一個(gè)新的函數(shù)到我們的模型中。

其中，為第i個(gè)實(shí)例在第t次迭代時(shí)的預(yù)測(cè)，我們需要添加樹(shù) ，然后最小化下面的目標(biāo)函數(shù)：

假設(shè)損失函數(shù)使用的是平方損失 ，則上式進(jìn)一步寫為：

現(xiàn)在，我們采用泰勒展開(kāi)來(lái)定義一個(gè)近似的目標(biāo)函數(shù)：

其中：

分別是loss function上的一階梯度和二階梯度。

忘記基礎(chǔ)知識(shí)的同學(xué)順便重溫一下泰勒公式吧

泰勒公式（Taylor’s Formula）是一個(gè)用函數(shù)在某點(diǎn)的信息描述其附近取值的公式。其初衷是用多項(xiàng)式來(lái)近似表示函數(shù)在某點(diǎn)周圍的情況。

函數(shù)在處的基本形式如下

還有另外一種常見(jiàn)的寫法，,將在處進(jìn)行泰勒展開(kāi)，得：

現(xiàn)在，我們?nèi)サ舫Ａ浚缓笾匦抡J(rèn)識(shí)一下我們新的目標(biāo)函數(shù)：

定義是葉子 j 的實(shí)例集合。將正則項(xiàng)帶入，展開(kāi)目標(biāo)函數(shù)：

看起來(lái)有點(diǎn)復(fù)雜，令：，，上式簡(jiǎn)化為：

上式中是相互獨(dú)立的，是平方項(xiàng)。對(duì)于一個(gè)確定的結(jié)構(gòu)，我們可以計(jì)算最優(yōu)的權(quán)重:

將帶入上式，計(jì)算得到的loss最優(yōu)解：

可以作為一個(gè)得分函數(shù)（scoring function）來(lái)衡量一棵樹(shù)結(jié)構(gòu)的質(zhì)量。

我們有了一個(gè)方法來(lái)衡量一棵樹(shù)有多好，現(xiàn)在來(lái)看XGBoost優(yōu)化的第二個(gè)問(wèn)題：如何選擇哪個(gè)特征和特征值進(jìn)行分裂，使最終我們的損失函數(shù)最小？

XGBoost特征選擇和切分點(diǎn)選擇指標(biāo)定義為：

具體如何分裂？

XGBoost每一步選能使分裂后增益最大的分裂點(diǎn)進(jìn)行分裂。而分裂點(diǎn)的選取之前是枚舉所有分割點(diǎn)，這稱為完全貪婪算法(exact greedy algorithm)，在所有特征上，枚舉所有可能的劃分。

• 基于當(dāng)前節(jié)點(diǎn)嘗試分裂決策樹(shù)，默認(rèn)分?jǐn)?shù)score=0，G和H為當(dāng)前需要分裂的節(jié)點(diǎn)的一階二階導(dǎo)數(shù)之和。
• 對(duì)特征序號(hào) k=1,2...K:
• 將樣本按特征k從小到大排列，依次取出第i個(gè)樣本，依次計(jì)算當(dāng)前樣本放入左子樹(shù)后，左右子樹(shù)一階和二階導(dǎo)數(shù)和：
  
• 嘗試更新最大的分?jǐn)?shù)：

• 基于最大score對(duì)應(yīng)的劃分特征和特征值分裂子樹(shù)。
• 如果最大score為0，則當(dāng)前決策樹(shù)建立完畢，計(jì)算所有葉子區(qū)域的, 得到弱學(xué)習(xí)器，更新強(qiáng)學(xué)習(xí)器,進(jìn)入下一輪弱學(xué)習(xí)器迭代.如果最大score不是0，則繼續(xù)嘗試分裂決策樹(shù)。

當(dāng)數(shù)據(jù)量十分龐大時(shí)，Exact Greedy 算法就會(huì)很慢，因此XGBoost引入了近似的算法，和Exact Greedy很類似，這里就不再展開(kāi)講了。

原理推導(dǎo)（精簡(jiǎn)版）

下面是XGBoost原理推導(dǎo)的精簡(jiǎn)版，方便同學(xué)們復(fù)習(xí)使用。

Xgboost@sklearn模型參數(shù)解析

XGBoost的實(shí)現(xiàn)有原生版本，同時(shí)也有Scikit-learn版本，兩者在使用上有一些微差異，這里給出xgboost.sklearn 參數(shù)解釋。XGBoost使用key-value字典的方式存儲(chǔ)參數(shù)：

#部分重要參數(shù)
params?=?{
????'booster':?'gbtree',
????'objective':?'multi:softmax',??#?多分類的問(wèn)題
????'num_class':?10,???????????????#?類別數(shù)，與?multisoftmax?并用
????'gamma':?0.1,??????????????????#?用于控制是否后剪枝的參數(shù),越大越保守，一般0.1、0.2這樣子。
????'max_depth':?12,???????????????#?構(gòu)建樹(shù)的深度，越大越容易過(guò)擬合
????'lambda':?2,???????????????????#?控制模型復(fù)雜度的權(quán)重值的L2正則化項(xiàng)參數(shù)，參數(shù)越大，模型越不容易過(guò)擬合。
????'subsample':?0.7,??????????????#?隨機(jī)采樣訓(xùn)練樣本
????'colsample_bytree':?0.7,???????#?生成樹(shù)時(shí)進(jìn)行的列采樣
????'min_child_weight':?3,
????'silent':?1,???????????????????#?設(shè)置成1則沒(méi)有運(yùn)行信息輸出，最好是設(shè)置為0.
????'eta':?0.007,??????????????????#?如同學(xué)習(xí)率
????'seed':?1000,
????'nthread':?4,??????????????????#?cpu?線程數(shù)
}

篇幅原因，調(diào)參實(shí)例及XGBoost可視化且聽(tīng)下回分解。
如有收獲，還請(qǐng)不吝給個(gè)在看、收藏、轉(zhuǎn)發(fā)

參考

https://www.cnblogs.com/pinard/p/10979808.html
https://www.biaodianfu.com/xgboost.html https://www.zybuluo.com/vivounicorn/note/446479 https://www.cnblogs.com/chenjieyouge/p/12026339.html