52ML系列(3)--Xgboost詳解

本來覺得xgboost已經(jīng)弄懂了，但聽了AI Lab陳博士的講座之后仿畸，又有了更深入的認(rèn)知，本文將詳細(xì)解釋一些細(xì)節(jié)朗和，幫助大家理解错沽。順便表示對陳博的膜拜眶拉，講的太清楚了??。

首先呢忆植，Xgboost是一個究極進(jìn)化體谒臼，它的祖先其實(shí)是棵樹蜈缤。我們來看下它的進(jìn)化史：
$\begin{align} X\!G\!Boost&=eXtreme+GBDT\\ &=eXtreme+(Gradient+BDT) \\ &=eXtreme+Gradient+(Boosting+DecisionTree) \end{align}$

$Boosting \to BDT \to GBDT \to X\!G\!Boost$

本文為了讓你真正懂Xgboost冯挎，將追根溯源，從他的祖先開始一層一層的講解Xgboost是怎么進(jìn)化來的??

But房官！本文默認(rèn)你是懂DecisionTree的，不清楚決策樹是啥的請自行百度??

But孵奶，but蜡峰！還是要提一嘴決策樹的表示形態(tài)了袁，這個很重要，因?yàn)閄gboost的進(jìn)化與決策樹的形態(tài)變化密不可分湿颅。

決策樹有哪些表示形態(tài)霸芈獭？

樹形結(jié)構(gòu)
if-else判斷結(jié)構(gòu)
圖像區(qū)域劃分
肖爵。。臀脏。

前三種是我們常見的形式了劝堪，點(diǎn)點(diǎn)點(diǎn)我們后面再說??

好！我們正式開始研究Xgboost的進(jìn)化史揉稚，首先是Boosting秒啦。

Boosting

提升方法(boosting)就是集成方法中的一員(另一員是Bagging，其中差別不在本文討論范圍內(nèi)搀玖，請自行百度)余境，它將所有臭皮匠加起來，最后賽過一個諸葛亮灌诅。所以boosting本質(zhì)是一個加法模型芳来。

加法模型：
$f\left(x\right)=\sum_{m=1}^M\beta_m b\left(x;\gamma_m\right) \tag{1.1}$
其中， $b\left(x;\gamma_m\right)$ 為基函數(shù)猜拾， $\gamma_m$ 為基函數(shù)的參數(shù)即舌， $\beta_m$ 為基函數(shù)的系數(shù)。 $b\left(x;\gamma_m\right)$ 基函數(shù)是什么挎袜？只要保證函數(shù)可加性就可以，比如決策樹蜜葱。

有了這個加法模型牵囤，那么我們的目標(biāo)就是：在給定訓(xùn)練數(shù)據(jù) $\{\left(x_i,y_i\right)\}_{i=1}^N$ 及損失函數(shù) $L\left(y,f\left(x\right)\right)$ 的條件下，學(xué)習(xí)加法模型 $f\left(x\right)$ 成為經(jīng)驗(yàn)風(fēng)險(xiǎn)極小化問題：
$\min_{\beta_m,\gamma_m}\sum_{i=1}^N L\left(y_i,\sum_{m=1}^M\beta_m b\left(x_i;\gamma_m\right)\right)\tag{1.2}$
稍微解釋下經(jīng)驗(yàn)風(fēng)險(xiǎn)極小化是什么鬼汹桦，其實(shí)就是損失函數(shù)舞骆。還有一個結(jié)構(gòu)風(fēng)險(xiǎn)極小化，指的是正則化項(xiàng)狈惫。

式（1.2）這個模型看上去有點(diǎn)麻煩胧谈，但我們可以從前向后，每一步只學(xué)習(xí)一個基函數(shù)及其系數(shù)稳强，逐步逼近優(yōu)化目標(biāo)函數(shù)式（1.2）退疫，這樣就可以簡化優(yōu)化復(fù)雜度。具體地澜汤，每步只需優(yōu)化如下?lián)p失函數(shù)：
$\min_{\beta,\gamma}\sum_{i=1}^N L\left(y_i,\beta b\left(x_i;\gamma\right)\right)\tag{1.3}$

于是有了前向分布算法：

算法1：前向分步算法

輸入：訓(xùn)練數(shù)據(jù)集 $T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\}$ 谁不；損失函數(shù) $L\left(y,f\left(x\right)\right)$ 刹帕；基函數(shù)集合 $\{b\left(x;\gamma\right)\}$ ；
輸出：加法模型 $f\left(x\right)$
（1）初始化 $f_0\left(x\right)=0$
（2）對 $m=1,2,\dots,M$
（a）極小化損失函數(shù)
$\left(\beta_m,\gamma_m\right)=\mathop{\arg\min}_{\beta,\gamma} \sum_{i=1}^N L\left(y_i, f_{m-1}\left(x_i\right)+\beta b\left(x_i;\gamma\right)\right) \tag{1.4}$
得到參數(shù) $\beta_m$ 挫掏， $\gamma_m$
（b）更新
$f_m\left(x\right)=f_{m-1}\left(x\right)+\beta_m b\left(x;\gamma_m\right) \tag{1.5}$
（3）得到加法模型
$f\left(x\right)=f_M\left(x\right)=\sum_{m=1}^M\beta_m b\left(x;\gamma_m\right) \tag{1.6}$

前向分步算法將同時求解從 $m=1$ 到 $M$ 所有參數(shù) $\beta_m,\gamma_m$ 的優(yōu)化問題簡化為逐次求解各個 $\beta_m, \gamma_m$ 的優(yōu)化問題。

以上就是Boosting

好啦袄友，接下來要開始進(jìn)化了：boosting->boosting+decision tree

BDT

我們把boosting的基函數(shù)設(shè)置成決策樹，那么boosting就變成了BDT鸠按，提升決策樹待诅。
提升決策樹模型可以表示為決策樹的加法模型：
$f_M=\sum_{m=1}^M T\left(x;\Theta_m\right) \tag{2.1}$
其中， $T\left(x;\Theta_m\right)$ 表示決策樹绪囱； $\Theta_m$ 為決策樹的參數(shù)； $M$ 為樹的個數(shù)齿椅。

還記得前文說的決策樹形式嗎涣脚？這下又多了一種表示形式 $T\left(x;\Theta_m\right)$ 矾麻。下面是對這種表示形式的解釋：

已知訓(xùn)練數(shù)據(jù)集 $T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots\left(x_N,y_N\right)\}$ ， $x_i\in\mathcal{X}\subseteq\mathbb{R}^n$ 甩牺， $\mathcal{X}$ 為輸入空間柴灯， $y_i\in\mathcal{Y}\subseteq\mathbb{R}$ ， $\mathcal{Y}$ 為輸出空間查描。如果將輸入空間 $\mathcal{X}$ 劃分為 $J$ 個互不相交的區(qū)域 $R_1,R_2,\dots,R_J$ 冬三，并且在每個區(qū)域上確定輸出的常量 $c_j$ ，那么決策樹可表示為
$T\left(x;\Theta\right)=\sum_{j=1}^J c_j I\left(x\in R_j\right) \tag{2.4}$
其中窝爪，參數(shù) $\Theta=\{\left(R_1,c_1\right),\left(R_2,c_2\right),\dots,\left(R_J,c_J\right)\}$ 表示決策樹的區(qū)域劃分和各區(qū)域上的常量值。 $J$ 是決策樹的復(fù)雜度即葉子結(jié)點(diǎn)個數(shù)邀杏。

我們回到BDT上來望蜡，提升決策樹使用以下前向分步算法：
$\begin{align} f_0\left(x\right)&=0 \\ f_m\left(x\right)&=f_{m-1}\left(x\right)+T\left(x;\Theta_m\right),\quad m=1,2,\dots,M \\ f_M\left(x\right)&=\sum_{m=1}^M T\left(x;\Theta_m\right) \end{align}$
在前向分步算法的第 $m$ 步浩姥，給定當(dāng)前模型 $f_{m-1}\left(x\right)$ 勒叠，需要求解
$\hat{\Theta}_m=\mathop{\arg\min}_{\Theta_m}\sum_{i=1}^N L\left(y_i,f_{m-1}\left(x_i\right)+T\left(x_i;\Theta_m\right)\right)$
得到 $\hat{\Theta}_m$ ，即第 $m$ 棵樹的參數(shù)弊决。

當(dāng)采用平方誤差損失函數(shù)時，
$L\left(y,f\left(x\right)\right)=\left(y-f\left(x\right)\right)^2$
其損失變?yōu)?br> $\begin{align} L\left(y,f_{m-1}\left(x\right)+T\left(x;\Theta_m\right)\right) &=\left[y-f_{m-1}\left(x\right)-T\left(x;\Theta_m\right)\right]^2 \\ &=\left[r-T\left(x;\Theta_m\right)\right]^2 \end{align}$
其中昆稿，
$r=y-f_{m-1}\left(x\right) \tag{2.5}$
是當(dāng)前模型擬合數(shù)據(jù)的殘差（residual）。對回歸問題的提升決策樹喳瓣，只需要簡單地?cái)M合當(dāng)前模型的殘差畏陕。

算法2：回歸問題的提升決策樹算法

輸入：訓(xùn)練數(shù)據(jù)集 $T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\}$ ；
輸出：提升決策樹 $f_M\left(x\right)$
（1）初始化 $f_0\left(x\right)=0$
（2）對 $m=1,2,\dots,M$
（a）按照式（2.5）計(jì)算殘差
$r_{mi}=y_i-f_{m-1}\left(x_i\right), \quad i=1,2,\dots,N$
（b)擬合殘差 $r_{mi}$ 學(xué)習(xí)一個回歸樹仁讨，得到 $T\left(x;\Theta_m\right)$
（c）更新 $f_m\left(x\right)=f_{m-1}\left(x\right)+T\left(x;\Theta_m\right)$
（3）得到回歸提升決策樹
$f_M\left(x\right)=\sum_{m=1}^M T\left(x;\Theta_m\right)$

簡單總結(jié)下，BDT其實(shí)就是把boosting的基函數(shù)設(shè)定成了決策樹而已荒给。

形象的說說Boosting和BDT：
諸葛亮的智力值為100曙咽，有個智力值為40的臭皮匠A想打敗他例朱。兩者差了60點(diǎn)智力值洒嗤，實(shí)力太懸殊，于是A又找了個智力值為30的臭皮匠B间唉，這下A呈野、B加起來智力值就是70了，只差諸葛亮30點(diǎn)了喉钢。于是他們又找到了智力值為20的臭皮匠C幔戏。闲延。。好吧找颓，你們慢慢找佛析，總有一天能夠打敗諸葛亮捺萌。

好啦桃纯，又要進(jìn)化了：BDT->GBDT

GBDT

前文的加法模型中慈参，新的基模型都是在擬合真實(shí)殘差，既 $r_{mi}=y_i-f_{m-1}\left(x_i\right), \quad i=1,2,\dots,N$
如何加速這個擬合過程呢壮锻？我們知道負(fù)導(dǎo)數(shù)是函數(shù)下降最快的方向猜绣，那么對損失函數(shù)求偏導(dǎo)就能得到極值掰邢。

GBDT使用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值
$-\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]_{f\left(x\right)=f_{m-1}\left(x\right)} \tag{3.1}$
作為回歸問題提升決策樹算法中殘差的近似值，擬合一個回歸樹怀估。

算法3：梯度提升算法

輸入：訓(xùn)練數(shù)據(jù)集 $T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\}$ 多搀；損失函數(shù) $L\left(y,f\left(x\right)\right)$
輸出：梯度提升決策樹 $\hat{f}\left(x\right)$
（1）初始化
$f_0\left(x\right)=\mathop{\arg\min}_c\sum_{i=1}^N L\left(y_i,c\right)$
（2）對 $m=1,2,\dots,M$
（a）對 $i=1,2,\dots,N$ ，計(jì)算
$r_{mi}=-\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]_{f\left(x\right)=f_{m-1}\left(x\right)}$
（b)對 $r_{mi}$ 擬合一個回歸樹从藤，得到第 $m$ 棵樹的葉結(jié)點(diǎn)區(qū)域 $R_{mj},j=1,2,\dots,J$
（c）對 $j=1,2,\dots,J$ ，計(jì)算
$c_{mj}=\mathop{\arg\min}_c\sum_{x_i\in R_{mj}} L\left(y_i, f_{m-1}\left(x_i\right)+c\right)$
（d）更新 $f_m\left(x\right)=f_{m-1}\left(x\right)+\sum_{j=1}^J c_{mj} I\left(x\in R_{mj}\right)$
（3）得到回歸梯度提升決策樹
$\hat{f}\left(x\right)=f_M\left(x\right)=\sum_{m=1}^M \sum_{j=1}^J c_{mj} I\left(x\in R_{mj}\right)$

這里和BDT有幾處不同：

第一步的基分類器不再是粗暴的設(shè)置為 $f_0\left(x\right)=0$ 扫责，而是擬合了一個當(dāng)前最優(yōu)解c鳖孤。
擬合的殘差是損失函數(shù)的負(fù)梯度。
我們觀察式（3.1）推姻，可以發(fā)現(xiàn)它是一個二元函數(shù)增炭。與常見的邏輯回歸隙姿、svm中的梯度下降不太一樣的是输玷，前者求得是參數(shù) $w$ ，而這里我們直接把 $f\left(x\right)$ 作為變量求解貌虾。
決策樹的表示形式又不一樣了尽狠，這次變成了 $\sum_{j=1}^J c_{mj} I\left(x\in R_{mj}\right)$ 袄膏，這樣表示的意思是以樹的葉節(jié)點(diǎn)作為考量码党，樣本放入樹模型后揖盘，被劃分到哪個葉節(jié)點(diǎn)兽狭？而該葉節(jié)點(diǎn)又將輸出何值箕慧？

終于進(jìn)化到究極體了颠焦！GBDT->Xgboost

Xgboost

在Xgboost里伐庭，我們又雙叒叕重新改變了決策樹的表示形式：
訓(xùn)練數(shù)據(jù)集 $\mathcal{D}=\{\left(\mathbf{x}_i,y_i\right)\}$ ，其中 $\mathbf{x}_i\in\mathbb{R}^m,y_i\in\mathbb{R},\left|\mathcal{D}\right|=n$ 盯捌，則決策樹表示為：
$f\left(\mathbf{x}\right)=w_{q\left(\mathbf{x}\right)} \tag{4.1}$
其中， $q:\mathbb{R}^m\to \{1,\dots,T \},w\in\mathbb{R}^T$ , $T$ 為決策樹葉子節(jié)點(diǎn)數(shù)幼衰。

這里是第一個重點(diǎn)渡嚣，需要解釋下识椰。
首先我們對決策樹來個功能上的認(rèn)知：給樹模型一個樣本，樹模型就輸出一個預(yù)測值功咒，對吧力奋？這個預(yù)測值實(shí)際上就是葉子節(jié)點(diǎn)的分?jǐn)?shù)溅呢，也就是說一個葉子節(jié)點(diǎn)對應(yīng)一個預(yù)測值挪蹭。
那么這里的 $q$ 函數(shù)表示的是葉子節(jié)點(diǎn)的序號， $q\left(\mathbf{x}\right)$ 的意思就是樣本 $x$ 給到 $q$ 函數(shù)之后， $q$ 函數(shù)將樣本分配到某個葉子節(jié)點(diǎn)上八秃，并輸出這個葉子節(jié)點(diǎn)的序號昔驱。
而 $w$ 表示的是葉子節(jié)點(diǎn)的分?jǐn)?shù)骤肛，用下標(biāo)（就是 $q(x)$ ）的形式來表示是哪一個葉子節(jié)點(diǎn)的分?jǐn)?shù)。

理解了究極體的樹模型表示形式淑玫，接下來我們來看看Xgboost模型：
$\hat{y}_i=\phi\left(\mathbf{x}_i\right)=\sum_{k=1}^K f_k\left(\mathbf{x}_i\right) \tag{4.2}$
其中叁鉴， $f_k\left(\mathbf{x}\right)$ 為第 $k$ 棵決策樹亲茅。

這種模型跟前文的BDT、GBDT看起來并沒有什么區(qū)別，但是基于全新的樹模型表示方式捞附，我們可以把正則化項(xiàng)加到目標(biāo)函數(shù)中去：
$\mathcal{L}\left(\phi\right)=\sum_i l\left(\hat{y}_i,y_i\right)+\sum_k \Omega\left(f_k\right) \tag{4.3}$
其中鸟召， $\Omega\left(f\right)=\gamma T+\frac{1}{2}\lambda\|w\|^2=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T w_j^2$ 。

這樣第 $t$ 輪目標(biāo)函數(shù)就是這樣：
$\mathcal{L}^{\left(t\right)}=\sum_{i=1}^n l\left(y_i,\hat{y}^{\left(t-1\right)}_i+f_t\left(\mathbf{x}_i\right)\right)+\Omega\left(f_t\right) \tag{4.4}$

這里是第二個重點(diǎn)，在目標(biāo)函數(shù)里加入了GBDT沒有考慮的正則項(xiàng)舔糖，降低了模型過擬合風(fēng)險(xiǎn)莺匠。

接下來是第三個重點(diǎn)金吗，GBDT采用損失函數(shù)負(fù)梯度（一階求導(dǎo)）作為殘差，Xgboost嫌他慢了趣竣，采用二階求導(dǎo)摇庙。為了讓損失函數(shù)具有一般性，這里要應(yīng)用泰勒展開公式期贫，什么是泰勒公式自行百度??跟匆。

這里的損失函數(shù)是二元的有序，我們只對 $\hat{y}$ 做變換迹冤。
第 $t$ 輪目標(biāo)函數(shù)在 $\hat{y}^{\left(t-1\right)}$ 處的二階泰勒展開得到：
$\mathcal{L}^{\left(t\right)}\simeq\sum_{i=1}^n\left[l\left(y_i,\hat{y}^{\left(t-1\right)}\right)+g_i f_t\left(\mathbf{x}_i\right)+\frac{1}{2}h_i f^2_t\left(\mathbf{x}_i\right)\right]+\Omega\left(f_t\right) \tag{4.5}$
其中莉兰， $g_i=\partial_{\hat{y}^{\left(t-1\right)}}l\left(y_i,\hat{y}^{\left(t-1\right)}\right),h_i=\partial^2_{\hat{y}^{\left(t-1\right)}}l\left(y_i,\hat{y}^{\left(t-1\right)}\right)$ 。

第 $t$ 輪目標(biāo)函數(shù)的二階泰勒展開并移除關(guān)于 $f_t\left(\mathbf{x}_i\right)$ 常數(shù)項(xiàng)岖食，得到：
$\begin{align} \tilde{\mathcal{L}}^{\left(t\right)}&=\sum_{i=1}^n\left[g_if_t\left(\mathbf{x}_i\right)+\frac{1}{2}h_i f^2_t\left(\mathbf{x}_i\right)\right]+\Omega\left(f_t\right) \\ &=\sum_{i=1}^n\left[g_i f_t\left(\mathbf{x}_i\right)+\frac{1}{2}h_i f^2_t\left(\mathbf{x}_i\right)\right]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T w_j^2 \end{align} \tag{4.6} \\$

這里稍微解釋下兄春，我們的目標(biāo)是求出讓損失函數(shù)最小的 $f_t(x)$ 叙量，而 $\hat{y}^{(t-1)}$ 是在上一輪已經(jīng)求出的已知項(xiàng)，因此 $l\left(y_i,\hat{y}^{\left(t-1\right)}\right)$ 在這里是常數(shù)項(xiàng)。

式（4.6）左邊是用樣本點(diǎn)的標(biāo)號來遍歷凉驻，而右邊是用葉子節(jié)點(diǎn)的標(biāo)號遍歷缀拭，能不能統(tǒng)一一下呢？可以啊，就全部以葉子標(biāo)號來遍歷好了：

定義葉結(jié)點(diǎn) $j$ 上的樣本的下標(biāo)集合 $I_j=\{i|q\left(\mathbf{x}_i\right)=j\}$ 抖苦，則目標(biāo)函數(shù)可表示為按葉結(jié)點(diǎn)累加的形式
$\tilde{\mathcal{L}}^{\left(t\right)}=\sum_{j=1}^T\left[\left(\sum_{i\in I_j}g_i\right)w_j+\frac{1}{2}\left(\sum_{i\in I_j}h_i+\lambda\right)w_j^2\right]+\gamma T \tag{4.7}$

這一步是第四個重點(diǎn)物喷，一個很有技巧的操作晕拆，也是很多人看不明白的地方末贾，我們來理解下：
我們的本來目的是要遍歷所有的樣本點(diǎn)對吧集索？而樣本點(diǎn)又無重復(fù)的分布在所有葉子節(jié)點(diǎn)上對吧？那我們遍歷所有的葉子節(jié)點(diǎn)不也能遍歷到所有的樣本嗎吸耿？
想像上課時老師點(diǎn)名，可以按學(xué)號從1到N來點(diǎn)名动分，也可以按小組序號來點(diǎn)名啊明吩，那么這里的學(xué)號就對應(yīng)這樣本點(diǎn)標(biāo)號，小組序號就對應(yīng)著葉子節(jié)點(diǎn)標(biāo)號畔师。
有了上面的解釋腔寡，相信大家應(yīng)該能理解式（4.7）是怎么得來的了吧？??

好啦但校，最困難的一步理解之后，就是喜聞樂見的求導(dǎo)了：
由于 $w_j^*=\mathop{\arg\min}_{w_j}\tilde{\mathcal{L}}^{\left(t\right)}$
可令 $\frac{\partial\tilde{\mathcal{L}}^{\left(t\right)}}{\partial w_j}=0$
得到每個葉結(jié)點(diǎn) $j$ 的最優(yōu)分?jǐn)?shù)為
$w_j^*=-\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j} h_i+\lambda} \tag{4.8}$

至此港庄，我們求出了每個葉子節(jié)點(diǎn)的分?jǐn)?shù)瓣履，但樹長什么樣還沒有完全得出。

最開始有個假設(shè)被我們忽略了婆硬，就是葉子節(jié)點(diǎn)個數(shù) $T$ 虚茶，這個條件一直被我們當(dāng)做常量來計(jì)算了员帮，也就是說我們已經(jīng)人為設(shè)定好了樹的形狀就是 $T$ 個葉子的樹，然后通過各種神操作得到了每個葉子的輸出值。

那么接下來的問題是，哪些樣本放在1號葉子里氮趋，哪些放2號葉子里呢椒惨？

我們回想下決策樹是怎么做的何恶？依照信息增益抵卫、信息增益比、gini系數(shù)對數(shù)據(jù)集進(jìn)行分裂對吧爵憎？那我們是不是可以創(chuàng)造一種新的分裂方法呢？

代入每個葉結(jié)點(diǎn) $j$ 的最優(yōu)分?jǐn)?shù)锻全，得到最優(yōu)化目標(biāo)函數(shù)值：
$\tilde{\mathcal{L}}^{\left(t\right)}\left(q\right)=-\frac{1}{2}\sum_{j=1}^T \frac{\left(\sum_{i\in I_j} g_i\right)^2}{\sum_{i\in I_j} h_i+\lambda}+\gamma T \tag{4.9}$

我們發(fā)現(xiàn)這個目標(biāo)函數(shù)僅與葉節(jié)點(diǎn)分?jǐn)?shù)的表達(dá)式（4.8）非常像呀呐伞。是不是可以認(rèn)為敌卓，葉節(jié)點(diǎn)的輸出衡量了最終的模型性能？

ok荸哟，那我們假設(shè) $I_L$ 和 $I_R$ 分別為分裂后左右結(jié)點(diǎn)的實(shí)例集假哎，令 $I=I_L\cup I_R$ ，則分裂后損失減少量由下式得出：
$\mathcal{L}_{split}=\frac{1}{2}\left[\frac{\left(\sum_{i\in I_L} g_i\right)^2}{\sum_{i\in I_L}h_i+\lambda}+\frac{\left(\sum_{i\in I_R} g_i\right)^2}{\sum_{i\in I_R}h_i+\lambda}-\frac{\left(\sum_{i\in I} g_i\right)^2}{\sum_{i\in I}h_i+\lambda}\right]-\gamma \tag{4.10}$
式（4.10）表示的是數(shù)據(jù)集分裂前后鞍历，目標(biāo)函數(shù)究竟提升了多少舵抹，這種操作是不是起到了跟gini系數(shù)一樣的作用呢？顯然答案是肯定的呀劣砍。

那我們就可以用（4.10）貪婪的遍歷數(shù)據(jù)集的每一個特征惧蛹，每一個特征下的數(shù)據(jù)類別：

算法4 分裂查找的精確貪婪算法

輸入：當(dāng)前結(jié)點(diǎn)實(shí)例集 $I$ ;特征維度 $d$
輸出：根據(jù)最大分值分裂
（1） $gain\leftarrow 0$
（2） $G\leftarrow\sum_{i\in I}g_i$ ， $H\leftarrow\sum_{i\in I}h_i$
（3）for $k=1$ to $d$ do
（3.1） $G_L \leftarrow 0$ 刑枝， $H_L \leftarrow 0$
（3.2）for $j$ in sorted( $I$ , by $\mathbf{x}_{jk}$ ) do
（3.2.1） $G_L \leftarrow G_L+g_j$ 香嗓， $H_L \leftarrow H_L+h_j$
（3.2.2） $G_R \leftarrow G-G_L$ ， $H_R=H-H_L$
（3.2.3） $score \leftarrow \max\left(score,\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{G^2}{H+\lambda}\right)$
（3.3）end
（4）end

至此装畅，Xgboost打完收功??

附送陳天奇老師的圖片

xgboost的生成

參考
七月在線課程
《XGBoost A Scalable Tree Boosting System》-陳天奇
《統(tǒng)計(jì)學(xué)習(xí)方法》-李航

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末靠娱，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子掠兄，更是在濱河造成了極大的恐慌像云，老刑警劉巖，帶你破解...
沈念sama閱讀 212,718評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件蚂夕，死亡現(xiàn)場離奇詭異迅诬，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)婿牍，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,683評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門侈贷，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人等脂，你說我怎么就攤上這事俏蛮〕虐觯” “怎么了？”我有些...
開封第一講書人閱讀 158,207評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵嫁蛇，是天一觀的道長锨并。經(jīng)常有香客問我露该，道長睬棚，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,755評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任解幼，我火速辦了婚禮抑党，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘撵摆。我一直安慰自己底靠，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,862評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布特铝。她就那樣靜靜地躺著暑中，像睡著了一般。火紅的嫁衣襯著肌膚如雪鲫剿。梳的紋絲不亂的頭發(fā)上鳄逾，一...
開封第一講書人閱讀 50,050評論 1贊 291
城市分裂傳說
那天，我揣著相機(jī)與錄音灵莲，去河邊找鬼雕凹。笑死，一個胖子當(dāng)著我的面吹牛政冻，可吹牛的內(nèi)容都是我干的枚抵。我是一名探鬼主播，決...
沈念sama閱讀 39,136評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼明场，長吁一口氣：“原來是場噩夢啊……” “哼汽摹！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起苦锨，我...
開封第一講書人閱讀 37,882評論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤逼泣，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后逆屡，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體圾旨，經(jīng)...
沈念sama閱讀 44,330評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,651評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年魏蔗，在試婚紗的時候發(fā)現(xiàn)自己被綠了砍的。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,789評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡莺治，死狀恐怖廓鞠，靈堂內(nèi)的尸體忽然破棺而出帚稠，到底是詐尸還是另有隱情，我是刑警寧澤床佳，帶...
沈念sama閱讀 34,477評論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布滋早，位于F島的核電站，受9級特大地震影響砌们，放射性物質(zhì)發(fā)生泄漏杆麸。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,135評論 3贊 317
男人毒藥：我在死后第九天來索命
文/蒙蒙一浪感、第九天我趴在偏房一處隱蔽的房頂上張望昔头。院中可真熱鬧，春花似錦影兽、人聲如沸揭斧。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,864評論 0贊 21
一樁弒父案峻堰，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽讹开。三九已至，卻和暖如春捐名，著一層夾襖步出監(jiān)牢的瞬間旦万，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,099評論 1贊 267
情欲美人皮
我被黑心中介騙來泰國打工桐筏，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留纸型，地道東北人。一個月前我還...
沈念sama閱讀 46,598評論 2贊 362
代替公主和親
正文我出身青樓梅忌，卻偏偏與公主長得像狰腌，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子牧氮，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,697評論 2贊 351