本文參考文章：

1. 《XGBoost中文文檔》 http://xgboost.apachecn.org/cn/latest/model.html
2. 《xgboost的原理沒(méi)你想像的那么難》http://www.reibang.com/p/7467e616f227

XGBoost

1. CART

• 函數(shù)
  CART就是某種類(lèi)似輸入x，獲得y的某種決策樹(shù)尼啡，我們可以將其看作是一個(gè)函數(shù)y=f(x)怀伦。
• 連續(xù) VS 離散
  CART的葉子葉子節(jié)點(diǎn)處是連續(xù)數(shù)值准给，既可以處理回歸問(wèn)題，也可以處理分類(lèi)問(wèn)題（CART：Classification And Regression Tree）虐译。 作為對(duì)比，decision trees（決策樹(shù)）的葉子節(jié)點(diǎn)一般是離散值，這樣就只能用來(lái)處理分類(lèi)問(wèn)題了岳链。
• 二分
  二分切分法：如果特征值大于給定值就走左子樹(shù)，否則就走右子樹(shù)劲件。CART就是使用了二分切分來(lái)處理連續(xù)型變量掸哑。
  針對(duì)每個(gè)特征：按照每個(gè)特征值，劃分?jǐn)?shù)據(jù)集兩份零远，計(jì)算切分誤差苗分，比較當(dāng)前最小誤差，最終選出最佳切分牵辣。
• 剪枝
  預(yù)剪枝：建樹(shù)的時(shí)候摔癣，通過(guò)設(shè)定條件來(lái)停止某些點(diǎn)繼續(xù)劃分。比如在實(shí)行二分切分法的時(shí)候纬向，設(shè)定一定條件（設(shè)定誤差下降值择浊，劃分后誤差不能下降這么多的話，那么就停止劃分逾条；設(shè)定最少樣本數(shù)近她，劃分后某一邊的樣本不能太少）。
  后剪枝：需要將數(shù)據(jù)集分成測(cè)試集和訓(xùn)練集膳帕。訓(xùn)練集粘捎，構(gòu)建足夠復(fù)雜的樹(shù)；測(cè)試集危彩，判斷葉節(jié)點(diǎn)合并是否可以降低測(cè)試誤差攒磨，是的話就合并。

CART：葉子節(jié)點(diǎn)處預(yù)測(cè)的是一個(gè)人是否喜歡電腦游戲的評(píng)分汤徽，而非是否喜歡

2. Boosting Decision Tree

• 整體認(rèn)知
  提升樹(shù)的方法就是：一點(diǎn)一點(diǎn)地提升娩缰，不斷地向最好的靠近。
  比如上圖中谒府，TrainData中原有數(shù)據(jù)是<小明拼坎、3.2>浮毯，而一個(gè)CART樹(shù)預(yù)測(cè)的值為<小明、2>泰鸡，就不準(zhǔn)確债蓝，我們需要添加CART樹(shù)來(lái)完善結(jié)果，如下圖盛龄。這就是一個(gè)Boosting的過(guò)程饰迹。

Tree Ensemble

• 偽代碼示例
  有一批數(shù)據(jù)，一個(gè)個(gè)的權(quán)重一開(kāi)始是一樣的余舶；
  {
  用一個(gè)弱分類(lèi)器（如：CART）方法訓(xùn)練啊鸭，找出此刻權(quán)重下較好的分類(lèi)器；
  將這個(gè)分類(lèi)器記下匿值，并計(jì)算出這個(gè)分類(lèi)器的權(quán)重赠制；（如下圖）
  統(tǒng)計(jì)錯(cuò)的、對(duì)的挟憔，更新一個(gè)個(gè)數(shù)據(jù)的權(quán)重钟些；（如下圖）
  更新累計(jì)類(lèi)別估計(jì)值；
  } 循環(huán)到錯(cuò)誤率滿(mǎn)足條件

分類(lèi)器權(quán)重更新公式：ε是上一時(shí)刻的錯(cuò)誤率

數(shù)據(jù)權(quán)重更新公式：y^是實(shí)際標(biāo)簽曲楚，f(x)是求出的標(biāo)簽

3. Gradient Boosting Decision Tree

為了求得最好的模型（求得模型參數(shù)）厘唾，我們構(gòu)造：損失函數(shù)與模型參數(shù)之間的函數(shù) loss = f(θ)，并通過(guò)“梯度下降”的方式求得θ

θ = θ + Δθ —— 這是我們更新θ 的方式

梯度下降

在提升樹(shù)（Boosting Decision Tree）的大前提下龙誊，我們要尋找的θ是所有樹(shù)的參數(shù)（樹(shù)的結(jié)構(gòu)抚垃、葉子節(jié)點(diǎn)的分?jǐn)?shù)），但是這樣的話參數(shù)太多趟大，因此為了便于計(jì)算鹤树，我們先將一棵樹(shù)當(dāng)作為一個(gè)θ，在損失函數(shù)與某一棵樹(shù)之間構(gòu)建關(guān)聯(lián)逊朽，loss = f(tree)罕伯，之后再將深入考慮樹(shù)的參數(shù)

loss & tree

以前是loss對(duì)θ求導(dǎo)，現(xiàn)在變成了loss對(duì)tree求導(dǎo)叽讳，這個(gè)尋求樹(shù)的過(guò)程就是Gradient Boosting Decision Tree求解的過(guò)程追他。

4. XGBoost

• 本章注意事項(xiàng)：
• 將一個(gè)CART決策樹(shù)看作是一個(gè)函數(shù) y = f(x)
• 目標(biāo)函數(shù) = 損失函數(shù) + 正則化公式
• 假設(shè)整個(gè)模型所需的K棵樹(shù)的結(jié)構(gòu)都已經(jīng)確定，只需求K棵樹(shù)的葉子節(jié)點(diǎn)的值

我們嘗試使用數(shù)學(xué)公式表示XGBoost模型：用f(x)來(lái)表示一棵決策樹(shù)岛蚤，F(xiàn)表示所有決策樹(shù)的一個(gè)集合邑狸，K棵決策樹(shù)累加起來(lái)就是最終的預(yù)測(cè)結(jié)果。我們要做的就是：帶入 x 求得 y^涤妒，計(jì)算 y 與 y^ 的差距（loss）单雾，沿著loss梯度下降的路徑求解參數(shù)。

K棵決策樹(shù)f(x)的累加，F(xiàn)表示所有可能的CART樹(shù)

定義XGBoost的目標(biāo)函數(shù)（它將衡量我們求出的值與實(shí)際值之間的差距）：

XGBoost目標(biāo)函數(shù)

除了loss之外硅堆，這里還加了一個(gè)正則化屿储。正則化的作用就是控制模型的復(fù)雜度，Ω(f)就表示了一棵樹(shù)的復(fù)雜度渐逃。樹(shù)的復(fù)雜度過(guò)高會(huì)導(dǎo)致過(guò)擬合够掠。這里正則化也算是起到了預(yù)剪枝的作用。

至于loss函數(shù)怎么定義朴乖？
如果是回歸問(wèn)題祖屏，我們常用的損失函數(shù)是MSE助赞，即：

回歸問(wèn)題

如果是分類(lèi)問(wèn)題买羞，我們常用的損失函數(shù)是對(duì)數(shù)損失函數(shù)：

分類(lèi)問(wèn)題

正則化又怎么定義？
xgboost是這樣定義的：

xgboost的正則化項(xiàng)

T代表的是葉子節(jié)點(diǎn)的個(gè)數(shù)雹食，而ω則是每個(gè)葉子上的分?jǐn)?shù)畜普。γ和λ是需要手動(dòng)調(diào)整的超參，它們值越大那么樹(shù)的模型就越簡(jiǎn)單群叶。至于樹(shù)結(jié)構(gòu)中的其他參數(shù)吃挑，正則化中就沒(méi)有更多體現(xiàn)了，主要是T和ω足夠了街立。

加法訓(xùn)練

下面通過(guò)大量公式來(lái)說(shuō)明加法訓(xùn)練（如上圖）中是如何每次優(yōu)化一棵樹(shù)的：

如何優(yōu)化某一棵樹(shù)（這個(gè)一定要看舶衬，重點(diǎn)）

學(xué)習(xí)樹(shù)結(jié)構(gòu)，由loss=f(tree)進(jìn)入tree的結(jié)構(gòu)細(xì)節(jié)
在我們將一片葉子分成兩片時(shí)赎离，采用如下分?jǐn)?shù)衡量：

二分劃分

這個(gè)公式可以分解為 1) 新左葉上的得分 2) 新右葉上的得分 3) 原始葉子上的得分 4) additional leaf（附加葉子）上的正則化逛犹。 我們可以在這里看到一個(gè)重要的事實(shí)：如果增益小于 γ，我們最好不要添加那個(gè)分支梁剔。這正是基于樹(shù)模型的 pruning（剪枝） 技術(shù)虽画！

再看那個(gè)公式，如果Gain值是大于0的荣病，說(shuō)明下面這個(gè)值變大了码撰，那么obj*就變小了，那就值得劃分个盆。

obj*相關(guān)公式

對(duì)于真實(shí)有價(jià)值的數(shù)據(jù)脖岛，我們通常要尋找一個(gè)最佳的分割。為了有效地做到這一點(diǎn)颊亮，我們把所有的實(shí)例按照排序順序排列柴梆，如下圖所示。

然后從左到右的掃描就足以計(jì)算所有可能的拆分解決方案的結(jié)構(gòu)得分编兄，我們可以有效地找到最佳的拆分轩性。