boosting翻譯過(guò)來(lái)就是提升的意思，通過(guò)研究如果將許多個(gè)弱分類(lèi)器集成在一起提升為一個(gè)強(qiáng)分類(lèi)器就是多數(shù)boosting算法所研究的內(nèi)容。其中最為經(jīng)典的算法就是Adaboost,gdbt,xgboost等算法，本文將從xgboost的原理出發(fā)，帶大家理解boosting算法。由于xgboost是提升樹(shù)模型，所以它與決策樹(shù)是息息相關(guān)的，它通過(guò)將很多的決策樹(shù)集成起來(lái)，從而得到一個(gè)很強(qiáng)的分類(lèi)器。

1、基礎(chǔ)知識(shí)

CART回歸樹(shù)

決策樹(shù)實(shí)際就是一種對(duì)空間不斷進(jìn)行劃分算法，通過(guò)給每個(gè)劃分的空間賦予一個(gè)標(biāo)簽或權(quán)重，那么當(dāng)樣本落到這個(gè)空間里面，我們就認(rèn)為這個(gè)樣本就滿(mǎn)足這個(gè)標(biāo)簽。

可以預(yù)見(jiàn)的是，對(duì)空間進(jìn)行劃分其實(shí)是一個(gè)NP完全的問(wèn)題，因此我們決策樹(shù)算法通常采用啟發(fā)式方法對(duì)空間進(jìn)行劃分的。常用的決策樹(shù)算法有ID3，C4.5，CART決策樹(shù)。

CART決策樹(shù)又分為回歸樹(shù)和分類(lèi)樹(shù)，CART回歸樹(shù)，它假設(shè)了決策樹(shù)是一顆二叉樹(shù)。它通過(guò)不斷地將特征進(jìn)行分裂(劃分為左右兩半)來(lái)構(gòu)造一顆決策樹(shù)。正是因?yàn)檫@一點(diǎn)，我們?cè)谑褂胋oosting的時(shí)候，需要對(duì)離散變量進(jìn)行one-hot編碼處理。你可以想象一下，將一個(gè)離散的變量劃分為兩部分其實(shí)是完全沒(méi)有意義的，因?yàn)殡x散的變量之間并不存在大小關(guān)系。

一個(gè)典型的CART回歸樹(shù)產(chǎn)生算法包含了一個(gè)目標(biāo)函數(shù)：

如果我們希望對(duì)變量進(jìn)行一個(gè)劃分，比如說(shuō)將第j個(gè)變量x(j)和它的某個(gè)取值s劃分為兩個(gè)區(qū)域：

于是，為了求解最優(yōu)的切分變量j和最優(yōu)的切分點(diǎn)s，就轉(zhuǎn)化為求解這么一個(gè)目標(biāo)函數(shù)：

那么我們只需要遍歷一次所有的變量的所有切分點(diǎn)，就可以找到一個(gè)最優(yōu)的切分位置和變量。然后就這樣遞歸地往下找，就可以產(chǎn)生一顆回歸樹(shù)。
xgboost的建樹(shù)過(guò)程其實(shí)是與CART回歸樹(shù)類(lèi)似的，有了CART回歸樹(shù)的知識(shí)，我們理解xgboost的原理也可以輕松很多。

Boosting

boosting的核心思想就是我們希望訓(xùn)練出K顆樹(shù)，將它們集成起來(lái)從而預(yù)測(cè)我們的Y。我們可以用以下公式表示：

在這里，我們用一個(gè)函數(shù)fk(x)來(lái)表示一顆決策樹(shù)，那個(gè)函數(shù)f可以理解為將樣本x映射到樹(shù)的某個(gè)葉子結(jié)點(diǎn)中，樹(shù)中的每個(gè)葉子結(jié)點(diǎn)都會(huì)對(duì)應(yīng)著一個(gè)權(quán)重w。

如圖，這就是提升樹(shù)的一個(gè)例子，這里一共有兩顆樹(shù)，意味著我們有兩個(gè)函數(shù)f1,f2，K=2 ，然后將樣本分別放到我們的兩顆樹(shù)中，就可以計(jì)算出兩個(gè)值，把它加起來(lái)就是我們要預(yù)測(cè)的Y。

那么我們應(yīng)該如何去建立一顆樹(shù)呢？如果你了解過(guò)Adaboost,那么可能會(huì)知道，這些樹(shù)是一顆一顆地建立起來(lái)的，通過(guò)一顆一顆地建立，不斷地減少我們的損失函數(shù)。那么如何建立一顆樹(shù)呢？建立的時(shí)候應(yīng)該怎么去評(píng)價(jià)一次分裂的效果呢？接下來(lái)將會(huì)回答這些問(wèn)題。

泰勒展開(kāi)
由于XGBoost的數(shù)學(xué)原理中要用到泰勒展開(kāi)的知識(shí)，所以我們簡(jiǎn)單的復(fù)習(xí)一下泰勒展開(kāi)公式：

2、XGBoost原理

我們先來(lái)來(lái)考慮一個(gè)general的目標(biāo)函數(shù)。

其中l(wèi)是可導(dǎo)且凸的損失函數(shù)，用來(lái)衡量? 與y的相近程度，第二項(xiàng)Ω則是正則項(xiàng)，它包含了兩個(gè)部分，第一個(gè)是γT，這里的T表示葉子結(jié)點(diǎn)的數(shù)量，γ是超參，也就是說(shuō)如果γ越大，那么我們的葉子結(jié)點(diǎn)數(shù)量就會(huì)越小。另外一部分則是L2正則項(xiàng)，通過(guò)對(duì)葉子結(jié)點(diǎn)的權(quán)重進(jìn)行懲罰，使得不會(huì)存在權(quán)重過(guò)大的葉子結(jié)點(diǎn)防止過(guò)擬合。w就表示葉子結(jié)點(diǎn)的權(quán)重。
但是對(duì)于上面這么一個(gè)目標(biāo)函數(shù)，我們是很難進(jìn)行優(yōu)化的，于是我們將它變換一下，我們通過(guò)每一步增加一個(gè)基分類(lèi)器ft，貪婪地去優(yōu)化這個(gè)目標(biāo)函數(shù)，使得每次增加，都使得loss變小。如此一來(lái)，我們就得到了一個(gè)可以用于評(píng)價(jià)當(dāng)前分類(lèi)器ft性能的一個(gè)評(píng)價(jià)函數(shù)：

這個(gè)算法又可以稱(chēng)為前向分步優(yōu)化。為了更快地去優(yōu)化這個(gè)函數(shù)，我們可以在ft=0處二階泰勒展開(kāi)：

注意，這里我們是把ft這一個(gè)函數(shù)看作一個(gè)變量，而不是把xi看作我們的變量，所以當(dāng)gi和hi分別是l對(duì)ft的一階偏導(dǎo)和二階偏導(dǎo)時(shí)，我們的損失函數(shù)可以寫(xiě)成上面的樣子，不信的話(huà)大家可以自己手動(dòng)推導(dǎo)一下。由于我們的目標(biāo)函數(shù)L只受函數(shù)f的影響，上一次的loss對(duì)本次迭代并沒(méi)有影響，于是我們可以刪除掉常數(shù)項(xiàng)，得到：

舉個(gè)例子，假設(shè)我們的損失函數(shù)l是square loss:

那么：

由于每個(gè)ft(xi)都對(duì)應(yīng)著一個(gè)葉子結(jié)點(diǎn)wi，于是我們可以用wi來(lái)代替一個(gè)個(gè)ft，所以我們將該目標(biāo)函數(shù)改寫(xiě)一下可以得到：

于是，我們對(duì)wj求偏導(dǎo)，并令其等于0，于是就可以得到基于該目標(biāo)函數(shù)的最優(yōu)權(quán)重：

在實(shí)際中我們可以直接使用這里w?j的公式來(lái)計(jì)算葉子結(jié)點(diǎn)上的權(quán)重。

我們將最優(yōu)權(quán)重回代進(jìn)去，就得到我們的目標(biāo)函數(shù)：

我們就可以用這個(gè)作為我們對(duì)決策樹(shù)ft性能的評(píng)分函數(shù)。但是構(gòu)造決策樹(shù)實(shí)際上是一個(gè)NP問(wèn)題，我們不可能遍歷所有的樹(shù)結(jié)構(gòu)，那么可以用一個(gè)貪婪算法去做。它跟CART決策樹(shù)是一樣的，按照評(píng)分函數(shù)來(lái)進(jìn)行貪婪搜索。

具體步驟，先從單個(gè)葉子開(kāi)始，我們?cè)O(shè)某個(gè)分裂后的屬性，將數(shù)據(jù)分為了IL，IR兩個(gè)部分，然后我們就可以計(jì)算：IL+IR?I的評(píng)分，就是我們分裂后的Gain。所以算法的基本步驟應(yīng)該就是遍歷所有特征的所有分割方法，選擇損失最小的，得到兩個(gè)葉子，然后繼續(xù)遍歷。遍歷的時(shí)候可以并行的執(zhí)行。

這個(gè)公式形式上跟CART算法是一致的，都是用分裂后的某種值 減去 分裂前的某種值，從而得到增益。為了限制樹(shù)的生長(zhǎng)，我們可以加入閾值，當(dāng)增益大于閾值時(shí)才讓節(jié)點(diǎn)分裂，上式中的gamma即閾值，它是正則項(xiàng)里葉子節(jié)點(diǎn)數(shù)T的系數(shù)，所以xgboost在優(yōu)化目標(biāo)函數(shù)的同時(shí)相當(dāng)于做了預(yù)剪枝。另外，上式中還有一個(gè)系數(shù)λ，是正則項(xiàng)里leaf score的L2模平方的系數(shù)，對(duì)leaf score做了平滑，也起到了防止過(guò)擬合的作用，這個(gè)是傳統(tǒng)GBDT里不具備的特性。

3、其他細(xì)節(jié)

缺失值處理
另外，基于這個(gè)分裂的評(píng)分函數(shù)，我們還可以用來(lái)處理缺失值。處理的方法就是，我們把缺失值部分額外取出來(lái)，分別放到IL和IR兩邊分別計(jì)算兩個(gè)評(píng)分，看看放到那邊的效果較好，則將缺失值放到哪部分。

建樹(shù)時(shí)的終止條件
max_depth最大樹(shù)深度：當(dāng)樹(shù)達(dá)到最大深度時(shí)則停止建立決策樹(shù)。
min_child_weight:最小的樣本權(quán)重和，樣本權(quán)重和就是∑hi，當(dāng)樣本權(quán)重和小于設(shè)定閾值時(shí)則停止建樹(shù)。

Shrinkage 與采樣
除了以上提到了正則項(xiàng)以外，我們還有shrinkage與列采樣技術(shù)來(lái)避免過(guò)擬合的出現(xiàn)。所謂shrinkage就是在每個(gè)迭代中樹(shù)中，對(duì)葉子結(jié)點(diǎn)乘以一個(gè)縮減權(quán)重eta。該操作的作用就是減少每顆樹(shù)的影響力，留更多的空間給后來(lái)的樹(shù)提升。

另一個(gè)技術(shù)則是采樣的技術(shù)，有兩種，一種是列采樣(colsample_bytree和colsample_bylevel)，一種是行采樣(subsample)。其中列采樣的實(shí)現(xiàn)一般有兩種方式，一種是按層隨機(jī)colsample_bylevel（一般來(lái)講這種效果會(huì)好一點(diǎn)），另一種是建樹(shù)前就隨機(jī)選擇特征colsample_bytree。

按層隨機(jī)colsample_bylevel的意思就是，上文提到每次分裂一個(gè)結(jié)點(diǎn)的時(shí)候，我們都要遍歷所有的特征和分割點(diǎn)，從而確定最優(yōu)的分割點(diǎn)，那么如果加入了列采樣，我們會(huì)在對(duì)同一層內(nèi)每個(gè)結(jié)點(diǎn)分裂之前，先隨機(jī)選擇一部分特征，于是我們只需要遍歷這部分的特征，來(lái)確定最優(yōu)的分割點(diǎn)。

建樹(shù)前就隨機(jī)選擇特征colsample_bytree就表示我們?cè)诮?shù)前就隨機(jī)選擇一部分特征，然后之后所有葉子結(jié)點(diǎn)的分裂都只使用這部分特征。

而行采樣則是bagging的思想，每次只抽取部分的樣本進(jìn)行訓(xùn)練，而不使用全部的樣本，從而增加樹(shù)的多樣性。

參考博客：http://blog.csdn.net/a358463121/article/details/68617389