xgboost是時(shí)下熱門的機(jī)器學(xué)習(xí)算法狗准，在面試和競(jìng)賽中出現(xiàn)的頻率非常高，但網(wǎng)上卻沒(méi)有一篇能夠完全講清楚的文章茵肃，因此腔长，本文旨在用盡量少的公式，將xgboost講清楚验残，明白捞附，透徹。
1 背景知識(shí)
xgboost是Boost（提升）算法家族中的一員，Boost根本思想在于通過(guò)多個(gè)簡(jiǎn)單的弱分類器鸟召，構(gòu)建出準(zhǔn)確率很高的強(qiáng)分類器胆绊。簡(jiǎn)單地來(lái)說(shuō)，Boost（提升）就是指每一步我都產(chǎn)生一個(gè)弱預(yù)測(cè)模型欧募，然后加權(quán)累加到總模型中压状，可以用于回歸和分類問(wèn)題。如果每一步的弱預(yù)測(cè)模型生成都是依據(jù)損失函數(shù)的梯度方向槽片，則稱之為梯度提升(Gradient boosting)何缓，這樣若干步以后就可以達(dá)到逼近損失函數(shù)局部最小值的目標(biāo)。
boosting集成學(xué)習(xí)还栓，由多個(gè)相關(guān)聯(lián)的決策樹聯(lián)合決策碌廓，什么叫相關(guān)聯(lián)，舉個(gè)例子剩盒，有一個(gè)樣本[數(shù)據(jù)->標(biāo)簽]是[(2谷婆，4，5)-> 4]辽聊，第一棵決策樹用這個(gè)樣本訓(xùn)練得預(yù)測(cè)為3.3纪挎，那么第二棵決策樹訓(xùn)練時(shí)的輸入，這個(gè)樣本就變成了[(2跟匆，4异袄，5)-> 0.7]，也就是說(shuō)玛臂，下一棵決策樹輸入樣本會(huì)與前面決策樹的訓(xùn)練和預(yù)測(cè)相關(guān)烤蜕。其中，0.7是模型預(yù)測(cè)和樣本標(biāo)記的差迹冤，稱為殘差讽营。我們每次要學(xué)習(xí)的目標(biāo)是上次學(xué)習(xí)的殘差，直到殘差小到滿足我們的要求或其他終止條件泡徙。這個(gè)殘差就是一個(gè)加預(yù)測(cè)值后能得真實(shí)值的累加量橱鹏。
上面的例子，如果第二次直接預(yù)測(cè)得到0.7堪藐，并不一定好莉兰，因?yàn)槊看巫咭恍〔街饾u逼近結(jié)果的效果，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過(guò)擬合礁竞。換句話說(shuō)我們思想不完全信任每一個(gè)棵殘差樹糖荒，我們認(rèn)為每棵樹只學(xué)到了真理的一小部分，累加的時(shí)候只累加一小部分苏章，只有通過(guò)多學(xué)幾棵樹才能彌補(bǔ)不足。
舉一個(gè)簡(jiǎn)單的例子，同樣使用年齡進(jìn)行分枝枫绅，假設(shè)我們A的真實(shí)年齡是18歲泉孩，但第一棵樹的預(yù)測(cè)年齡是12歲，即殘差為6歲并淋。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)寓搬，如果第二棵樹真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹的結(jié)論就是A的真實(shí)年齡县耽；如果第二棵樹的結(jié)論是5歲句喷，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲……以此類推學(xué)習(xí)下去
與之對(duì)比的是random forest（隨機(jī)森林）算法兔毙，各個(gè)決策樹是獨(dú)立的唾琼、每個(gè)決策樹在樣本堆里隨機(jī)選一批樣本，隨機(jī)選一批特征進(jìn)行獨(dú)立訓(xùn)練澎剥，各個(gè)決策樹之間沒(méi)有啥毛線關(guān)系锡溯。
2 初識(shí)xgboost
xgboost本質(zhì)上就是k個(gè)CART樹，k是一個(gè)正整數(shù)哑姚。
CART樹也叫分類與回歸樹祭饭，是一種決策樹，既能做分類任務(wù)也能做回歸任務(wù)叙量。分類樹的輸出是樣本的類別倡蝙， 回歸樹的輸出是一個(gè)實(shí)數(shù)（連續(xù)型變量）。
回歸樹的運(yùn)行流程與分類樹基本類似绞佩，但有以下兩點(diǎn)不同之處：
第一寺鸥，回歸樹的每個(gè)節(jié)點(diǎn)得到的是一個(gè)預(yù)測(cè)值而非分類樹式的樣本計(jì)數(shù)，假設(shè)在某一棵樹的某一節(jié)點(diǎn)使用了年齡進(jìn)行分枝（并假設(shè)在該節(jié)點(diǎn)上人數(shù)>1征炼，那么這個(gè)預(yù)測(cè)值就是屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值析既。
-
第二，在分枝節(jié)點(diǎn)的選取上谆奥，回歸樹并沒(méi)有選用最大熵值來(lái)作為劃分標(biāo)準(zhǔn)眼坏，而是常用了最小化均方差，即
這很好理解酸些，被預(yù)測(cè)出錯(cuò)的次數(shù)越多宰译，錯(cuò)的越離譜，均方差就越大魄懂，通過(guò)最小化均方差也就能夠找到最靠譜的分枝依據(jù)沿侈。
對(duì)于回歸問(wèn)題，我們常用的損失函數(shù)是MSE（均方誤差）市栗，即：
對(duì)于分類問(wèn)題缀拭，我們常用的損失函數(shù)是對(duì)數(shù)損失函數(shù)：
前面提到咳短，xgboost是具有k個(gè)CART樹的集成學(xué)習(xí)算法，那么問(wèn)題來(lái)了蛛淋，我們應(yīng)該怎么得到這k個(gè)樹咙好，k又是多少呢？（注意：不是隨機(jī)得到k個(gè)樹褐荷，是一個(gè)一個(gè)來(lái)勾效，后一個(gè)依賴于前一個(gè)）
在我們一顆接著一顆樹的構(gòu)建過(guò)程中，我們的目標(biāo)是：預(yù)測(cè)誤差盡量小叛甫，葉子節(jié)點(diǎn)盡量少层宫，節(jié)點(diǎn)數(shù)值盡量不極端。第一個(gè)目標(biāo)很清晰其监，而第二個(gè)目標(biāo)的原因是因?yàn)闃涞膹?fù)雜度越低萌腿，泛化能力越強(qiáng)，在后面我們會(huì)知道葉子節(jié)點(diǎn)數(shù)量是樹的復(fù)雜度計(jì)算中的一個(gè)考量棠赛，葉子節(jié)點(diǎn)數(shù)越多哮奇，樹越復(fù)雜。節(jié)點(diǎn)數(shù)值盡量不極端指的是某棵樹對(duì)一個(gè)樣本的預(yù)測(cè)值相對(duì)于其它樹對(duì)這個(gè)樣本的預(yù)測(cè)值相差比較大睛约，比如某個(gè)樣本label數(shù)值為4鼎俘，那么第一個(gè)回歸樹預(yù)測(cè)3，第二個(gè)預(yù)測(cè)為1辩涝；另外一組回歸樹贸伐，一個(gè)預(yù)測(cè)2，一個(gè)預(yù)測(cè)2怔揩，那么傾向后一種捉邢，為什么呢？前一種情況商膊，第一棵樹學(xué)的太多伏伐，太接近4，也就意味著有較大的過(guò)擬合的風(fēng)險(xiǎn)晕拆。
生成決策樹：決策樹算法相信大家都比較熟悉了藐翎，還不清楚的讀者請(qǐng)先了解一下決策樹算法。在xgboost中实幕，生成決策樹時(shí)吝镣，劃分屬性的方式如下：
為了更好的解釋xgboost算法，我們必須定義一些公式了昆庇。
首先是模型的預(yù)測(cè)：
這里的K就是樹的棵數(shù)末贾，F(xiàn)表示所有可能的CART樹，f表示一棵具體的CART樹整吆，fk(xi)表示樣本xi在第k棵樹上的預(yù)測(cè)值拱撵。這個(gè)模型由K棵CART樹組成辉川。
模型的目標(biāo)函數(shù)：
第一部分就是損失函數(shù)，第二部分就是正則項(xiàng)拴测。yi表示期望輸出员串。關(guān)于第二部分的解釋，我在網(wǎng)站找了個(gè)圖昼扛，不過(guò)下邊和上面的公式有點(diǎn)不一樣，注意一下就好欲诺。
還記得xgboost樹的生成過(guò)程嗎抄谐？一棵接一棵是不是？那么扰法，我們的目標(biāo)函數(shù)的優(yōu)化過(guò)程頁(yè)應(yīng)當(dāng)如此：首先優(yōu)化第一棵樹蛹含，完了之后再優(yōu)化第二棵樹，直至優(yōu)化完K棵樹塞颁。整個(gè)過(guò)程如下
所以浦箱，對(duì)于第t棵樹，它的目標(biāo)函數(shù)就是
這里祠锣，我們把ft(xi)當(dāng)做我們模型的變量參數(shù)酷窥，本身它表示樣本xi在第t棵樹上的預(yù)測(cè)值，這個(gè)預(yù)測(cè)值使我們經(jīng)過(guò)第t棵決策樹分類后再計(jì)算一下得到的伴网，也就是說(shuō)雖然分類了蓬推，但我們可以給他設(shè)不同的值（或者叫權(quán)值，一般用w表示）澡腾，所以這個(gè)值就是優(yōu)化模型過(guò)程中用到的參數(shù)之一沸伏。可以發(fā)現(xiàn)动分，目標(biāo)函數(shù)是ft(xi)的一次式和二次式毅糟，而且一次式項(xiàng)的系數(shù)是殘差，此時(shí)就是一個(gè)值澜公。而且一次式和二次式的函數(shù)優(yōu)化問(wèn)題又是特別簡(jiǎn)單的姆另，是不是很棒，很激動(dòng)玛瘸。
綜上蜕青，我們可以將損失函數(shù)用以下函數(shù)表示：
但是，損失函數(shù)一定是二次函數(shù)嗎糊渊？如果不是右核，就泰勒展開成二次，簡(jiǎn)單粗暴渺绒。
它背后的思路就是在損失函數(shù)上執(zhí)行梯度下降贺喝，然后用基學(xué)習(xí)器對(duì)其進(jìn)行擬合菱鸥。當(dāng)梯度為負(fù)時(shí)，我們稱它為偽殘差躏鱼，因?yàn)樗鼈円廊荒荛g接幫助我們最小化目標(biāo)函數(shù)氮采。
建樹的過(guò)程中，在以下情況下完成這棵樹的創(chuàng)建：
（1）當(dāng)引入的分裂帶來(lái)的增益小于一個(gè)閥值的時(shí)候染苛，我們可以剪掉這個(gè)分裂鹊漠，所以并不是每一次分裂loss function整體都會(huì)增加的，有點(diǎn)預(yù)剪枝的意思茶行。
（2）當(dāng)樹達(dá)到最大深度時(shí)則停止建立決策樹躯概，設(shè)置一個(gè)超參數(shù)max_depth，樹太深很容易出現(xiàn)的情況學(xué)習(xí)局部樣本畔师，過(guò)擬合娶靡。
（3）當(dāng)樣本權(quán)重和小于設(shè)定閾值時(shí)則停止建樹。
3 XGBoost和GBDT的區(qū)別
1）將樹模型的復(fù)雜度加入到正則項(xiàng)中看锉，來(lái)避免過(guò)擬合姿锭，因此泛化性能會(huì)好于GBDT。XGBoost的正則項(xiàng)會(huì)懲罰具有多個(gè)葉子節(jié)點(diǎn)的樹結(jié)構(gòu)伯铣。
2）損失函數(shù)是用泰勒展開式展開的呻此，同時(shí)用到了一階導(dǎo)和二階導(dǎo)，可以加快優(yōu)化速度腔寡。
3）和GBDT只支持CART作為基分類器之外趾诗，還支持線性分類器，在使用線性分類器的時(shí)候可以使用L1蹬蚁，L2正則化恃泪。
4）引進(jìn)了特征子采樣，像RandomForest那樣犀斋，這種方法既能降低過(guò)擬合贝乎，還能減少計(jì)算。
5）在尋找最佳分割點(diǎn)時(shí)叽粹，考慮到傳統(tǒng)的貪心算法效率較低览效，實(shí)現(xiàn)了一種近似貪心算法，用來(lái)加速和減小內(nèi)存消耗虫几，除此之外還考慮了稀疏數(shù)據(jù)集和缺失值的處理锤灿，對(duì)于特征的值有缺失的樣本，XGBoost依然能自動(dòng)找到其要分裂的方向辆脸。
6）XGBoost支持并行處理但校，XGBoost的并行不是在模型上的并行，而是在特征上的并行啡氢，將特征列排序后以block的形式存儲(chǔ)在內(nèi)存中状囱，在后面的迭代中重復(fù)使用這個(gè)結(jié)構(gòu)术裸。這個(gè)block也使得并行化成為了可能，其次在進(jìn)行節(jié)點(diǎn)分裂時(shí)亭枷，計(jì)算每個(gè)特征的增益袭艺，最終選擇增益最大的那個(gè)特征去做分割，那么各個(gè)特征的增益計(jì)算就可以開多線程進(jìn)行叨粘。
參考資料：
https://blog.csdn.net/mxg1022/article/details/80702264
https://blog.csdn.net/yinyu19950811/article/details/81079192
https://www.cnblogs.com/jiangxinyang/p/9248154.html
http://www.reibang.com/p/7467e616f227
https://blog.csdn.net/legendavid/article/details/78904353
