Xgboost原理和应用

xgboost作为新出现的集成算法，在各种大赛和实际项目中，取得了很好的效果，本文略去复杂的推导过程，简单讲解原理和python实现

一、直接上代码
xgboost.XGBClassifier(self, max_depth=3, learning_rate=0.1, n_estimators=100, silent=True, objective='binary:logistic', nthread=-1,gamma=0, min_child_weight=1, max_delta_step=0, subsample=1, colsample_bytree=1, base_score=0.5, seed=0)
重点调整参数：
1）

import xgboost
xgb = xgboost.XGBClassifier()
xgb.fit(xdata,ydata)
xgb.predict_proba(xdata)

二、xgboost具体步骤
1、原理部分
1）Xgboost是很多CART回归树集成,
2）一个回归树形成的关键点：
a）分裂点依据什么来划分；
b）分类后的节点预测值是多少
2、具体步骤
1）假如考虑对第t颗树进行优化，那么第t-1颗cart树的预测值 $\hat{y}_{i}^{(t-1)}$ 已知，由此可计算每个样本的 $g_{i},h_{i}$
$g_{i}=\frac{\partial L(y_{i},\hat{y}_{i}^{(t-1)})}{\partial \hat{y}_{i}^{(t-1)}}$ , $h_{i}=\frac{\partial^{2} L(y_{i},\hat{y}_{i}^{(t-1)})}{\partial^{2} \hat{y}_{i}^{(t-1)}}$ ,

计算过程如下，假如样本 $(x_{i},y_{i}=1)$ 的在第t-1颗树预测值为 $y_{i}^{(t-1)}=-1$ ，假定损失函数是：
$L(\Theta )=\sum_{i=1}^{n}\left [ y_{i}ln(1+e^{-\hat{y}_{i}})+(1-y_{i})ln(1+e^{\hat{y}_{i}}) \right ]$
在 $y_{i}=1$ 时，损失函数为：
$L(\Theta )=ln(1+e^{\hat{y}_{i}})$
将 $\hat{y}_{i}^{(t-1)}=-1$ 代入，可得：
$g_{i}^{(t)}=\frac{\partial L(y_{i},\hat{y}_{i}^{(t-1)})}{\partial \hat{y}_{i}^{(t-1)}}=\frac{-e^{\hat{y}_{i}}}{1+e^{\hat{y}_{i}}}=-0.27$
假设总共有N个样本，需要计算N个 $g_{i}^{(t)},h_{i}^{(t)}$ ,但是可以并行计算，这也是xgboost速度很快的原因

对每个feature的每个分割点进行分割，选取gain最大的feature和分割方式，不断迭代，形成新树，计算出新的最优权值 $w_{j}^{*}$ (第t颗树的预测值，公式见公式推导）

image.png

举例：

image.png

3）利用第t颗cart树的预测值，计算第t+1颗cart树的 $g_{i}^{(t+1)},$ h_{i}^{(t+1)}$

4）第t颗树分割停止的条件
a）当引入的分裂带来的增益小于一个阀值的时候，我们可以剪掉这个分裂，阈值参数为正则
项里叶子节点数T的系数；
b）当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，
c）当样本权重和小于设定阈值时则停止建树

三、xgboost公式推导

1、确定损失函数和目标函数
假设第m颗决策树可由第m-1颗决策树的预测值加误差项得到，即：
$y^{(i)}=\hat{y}_{m-1}^{(i)}+f_{t}(x_{i})$ ，
假设损失函数为：
$L(x)=\sum_{i=1}^{n}L(y_{i},\hat{y}_{i}^{t-1}+f_{t}(x_{i}))$

目标函数: $J(f_{t})=\sum_{i=1}^{n}L(y_{i},\hat{y}_{i}^{t-1}+f_{t}(x_{i}))+\Omega (f_{t})+C$
根据Taylor展开式： $f(x+\Delta x)\approx f(x)+f^{'}(x)\Delta x +f^{''}(x)\Delta x^{2}$
令，
$g_{i}=\frac{\partial L(y_{i},\hat{y}_{i}^{(t-1)})}{\partial \hat{y}_{i}^{(t-1)}}$ , $h_{i}=\frac{\partial^{2} L(y_{i},\hat{y}_{i}^{(t-1)})}{\partial^{2} \hat{y}_{i}^{(t-1)}}$
得：
$J(f_{t})\approx \sum_{i=1}^{n}\left [ L(y_{i},\hat{y}_{i}^{t-1})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i}) \right ] +\Omega (f_{t})+C$

注：
1） $\Omega (f_{t})$ 为第t颗决策树的正则项，可定义为：
$\Omega (f_{t})=\gamma \cdot T_{t}+\lambda \cdot \frac{1}{2}\sum_{j=1}^{T}w_{j}^{2}$
其中， $T_{t}$ 为第t颗决策树叶子节点数， $w_{j}$ 为第t颗决策树第j个叶子节点的预测值（叶权值）
注意：这里出现了 $\gamma$ 和 $\lambda$ ，这是xgboost自己定义的，在使用xgboost时，可以设定它们的值，显然，γ越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。λ越大也是越希望获得结构简单的树。

2、求极值
接下来是无聊的推导，实在是看不懂，，，直接上结果吧：
$w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda }$
代入目标函数，可得：
$obj^{*}=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_{j}}{H_{j}+\lambda }+\gamma \cdot T$
其中： $G_{j}=\sum_{i\epsilon I_{j}}g_{i}$ , $H_{j}=\sum_{i\epsilon I_{j}}g_{i}$ , $i$ 的范围为第t颗CART树的叶子节点数（例如 $g_{1},g_{1}+g_{2}$ 等等）

注：
1） $w_{j}^{*}$ 为第t棵CART树各个叶子几点的最佳值
2）目标函数的值是衡量第t颗CART树的结构好坏的标准，值越小，代表这样的结构越好

3、找出最优的树结构
衡量切分好坏的标准如下：
$Gain=\frac{1}{2}\left [ \frac{G_{L}^{2}}{H_{L}+\lambda }+ \frac{G_{R}^{2}}{H_{R}+\lambda }-\frac{(G_{L}+G_{R})^{2}}{H_{L}+H_{R}+\lambda } \right ]-\gamma$
枚举可行的分割点，选择增益最大的划分，循环执行

注：
1）Gain的左半部分如果小于右侧的γ，则Gain就是负的，表明切分后obj反而变大了。γ在这里实际上是一个临界值，它的值越大，表示我们对切分后obj下降幅度要求越严。这个值也是可以在xgboost中设定的。

4、举例
假设第t颗决策树为：

第t颗决策树

image.png

此时可计算每个样本的 $g_{i}$ 和 $h_{i}$ 值,此时T=3,Obj=

继续对每个节点的的样本按照特征进行分割，当引入的分割带来的增益小于一个阀值的时候，我们可以剪掉这个分割

五、xgboost具体步骤

六、python实现

Xgboost原理和应用

推荐阅读更多精彩内容