一、简介

??XGBoost(eXtreme Gradient Boosting)又叫极度梯度提升树，是boosting算法的一种实现方式。针对分类或回归问题，效果非常好。在各种数据竞赛中大放异彩，而且在工业界也是应用广泛，主要是因为其效果优异，使用简单，速度快等优点。本文主要从以下几个方面介绍该算法模型：

二、基本原理

??xgb是boosting算法的一种实现方式，主要是降低偏差，也就是降低模型的误差。因此它是采用多个基学习器，每个基学习器都比较简单，避免过拟合，下一个学习器是学习前面基学习器的结果 $y^{t}_{i}$ 和实际值 $y_{i}$ 的差值，通过多个学习器的学习，不断降低模型值和实际值的差。
$y_{i}^{0} = 0$
$y_{i}^{1} = f_{1}(x_{i}) = y_{i}^{0}+f_{1}(x_{i})$
$ $y_{i}^{2}=f_{1}(x_{i})+f_{2}(x_{i})=y_{i}^{1}+f_{2}(x_{i})$
$y_{i}^{t}=\sum_{k=1}^{t}f_{k}(x_{i})=y_{i}^{t-1}+f_{t}(x_{i})$
基本思路就是不断生成新的树，每棵树都是基于上一颗树和目标值的差值来进行学习，从而降低模型的偏差。最终模型结果的输出如下： $y_{i}=\sum_{k=1}^{t}f_{k}(x_{i})$ ，即所有树的结果累加起来才是模型对一个样本的预测值。那在每一步如何选择/生成一个较优的树呢？那就是由我们的目标函数来决定。

三、目标函数

??目标函数由两部分组成，一是模型误差，即样本真实值和预测值之间的差值，二是模型的结构误差，即正则项，用于限制模型的复杂度。
$Obj(\theta)=L(\theta)+\Omega(\theta)=L(y_{i},y_{i}^{t})+\sum_{k=1}^{t}\Omega(f_{k}(x_{i}))$
因为 $y_{i}^{t}=y_{i}^{t-1}+f_{t}(x_{i})$ ，所以将其带入上面的公式中转换为：
$Obj^{t}=\sum_{n=1}^{n}L(y_{i},y_{i}^{t-1}+f_{t}(x_{i}))+\Omega(f_{t})+\sum_{t=1}^{T-1}\Omega(f_{t})$ ，第t颗树的误差由三部分组成，n个样本在第t颗树的误差求和，以及第t颗树的结构误差和前t-1颗树的结构误差。其中前t-1颗树的结构误差是常数，因为我们已经知道前t-1颗树的结构了。
??假设我们的损失函数是平方损失函数(mse)，则上述目标函数转换为：
$Obj^{t}=\sum_{i=1}^{n}L(y_{i},y_{i}^{t-1}+f_{t}(x_{i}))+\Omega(f_{t})+\sum_{t=1}^{T-1}\Omega(f_{t}) \\ =\sum_{i=1}^{n}(y_{i}-(y_{i}^{t-1}+f_{t}(x_{i})))^2+\Omega(f_{t})+constant$
上述公式即为损失函数为mse时xgb第t步的目标函数。唯一的变量即为 $f_{t}$ ，此处的损失函数仍然是一个相对复杂的表达式，所以为了简化它，采用二阶泰勒展开来近似表达，即 $f(x+\Delta x)=f(x)+f^{'}(x)\Delta x+1/2f^{''}(x)\Delta x^2$ ，所以另 $g_{i}=\partial _{y_{i}^{t-1}}l(y_{i},y_{i}^{t-1})$ ， $h_{i}=\partial _{y_{i}^{t-1}} ^ 2 l(y_{i},y_{i}^{t-1})$ ，即分别是 $l(y_{i},y_{i}^{t-1})$ 的一阶导和二阶导。则上述损失函数转换为二阶导之后， $Obj^{t}=\sum_{i=1}^{n}[l(y_{i},y_{i}^{t-1})+g_{i} f_{t}(x_{})+1/2h_{i} f_{t}^2(x)]+\Omega(f_{t})+constant$ ，
??所以当损失函数是mse时， $g_{i}=2(y_{i}^{t-1}-y_{i})$ ， $h_{i}=2$ 。
??经过转换之后，其中第一项是所有样本与第t-1颗树的误差之和，因为第t-1颗树是已知的，所以可以将其视为常数项，我们暂时在目标函数中将其舍去，我们的目标函数变为关于 $f_{t}(x)$ 的函数了。而 $f_{t}(x)$ 则是关于叶子节点输出 $w$ 的函数，所以我们的目标函数全部转换为关于 $w$ 的函数， $Obj^{t}=\sum_{i=1}^{n}[g_{i} f_{t}(x_{})+1/2h_{i} f_{t}^2(x)]+\Omega(f_{t})+constant \\ =\sum_{i=1}^{n}[g_{i}w_{q}(x_{i})+1/2h_{i}w_{q}^2(x_{i})]+\gamma T+1/2\lambda\sum_{j=1}^{T}w_{j}^{2} \\ =\sum_{j=1}^{T}[\sum_{i \in I_{j}}(g_{i})*w_{j}+1/2*\sum_{i \in I_{j}}(h_{i}+\lambda)w_{j}^2]+\gamma T$ 。我们令 $G_{j}=\sum_{i \in I_{j}}(g_{i})$ ，令 $H_{j}=\sum i \in I_{j}(h_{i})$ ，则我们的目标函数转换为 $Obj^{t}=\sum_{j=1}^{T}G_{j}*w_{j}+1/2(H_{j}+\lambda)*w_{j}^{2}+\lambda T$ 。在上述表达式中， $j 表示第 j 个节点$ ， $i 表示第 i 个样本$ 。所以整个目标函数转换成了关于 $w$ 即叶节点分数的一元二次函数，想要优化目标函数，就是求解最优的w，因此我们对目标求导，得到 $w^{*}=-G_{i}/(H_{i}+\lambda)$ ，将 $w^{*}$ 代入目标函数中，则目标函数变为 $Obj^{t}=-1/2\sum_{j=1}^{T}G_{j}^{2}/(H_{j}+\lambda)+\lambda T$ 。如此简单，所以在求解二叉树的目标函数时，只要知道损失函数的一阶导、二阶导，以及样本落在哪个叶子节点上，我们只要求出在每个叶子节点上，该样本的一阶导和二阶导就能求出目标函数。也就能决定是否分裂该节点，依据哪个节点的特征值来进行分裂。

三、节点分裂

?? xgb节点是否分裂取决于信息增益的变化，若分裂当前节点，信息增益>0，则进行分裂，若不大于0则不分裂，如何判断分列前后信息增益的变化呢。那就可以使用我们的目标函数来表示了。
$Gain=G_{L}^{2}/(H_{L}+\lambda)+G_{R}^{2}/(H_{R}+\lambda)-(G_{L}+G_{R})^2/(H_{L}+H_{R}+\lambda)+\gamma$
??节点分裂有两种方式：1、贪心算法，2、近似算法

3.1 贪心算法

??贪心算法分裂的方式就是一种暴力搜索的方式，遍历每一个特征，遍历该特征的每一个取值，计算分裂前后的增益，选择增益最大的特征取值作为分裂点。

分裂流程如上图所示。

3.2 近似算法

?? 近似算法，其实就是分桶，目的是为了提升计算速度，降低遍历的次数，所以对特征进行分桶。就是将每一个特征的取值按照分位数划分到不同的桶中，利用桶的边界值作为分裂节点的候选集，每次遍历时不再是遍历所有特征取值，而是仅遍历该特征的几个桶（每个桶可以理解为该特征取值的分位数）就可以，这样可以降低遍历特征取值的次数。
??分桶算法分为global模式和local模式，global模式就是在第一次划分桶之后，不再更新桶，一直使用划分完成的桶进行后续的分裂。这样做就是计算复杂度降低，但是经过多次划分之后，可能会存在一些桶是空的，即该桶中已经没有了数据。
??local模式就是在每次分列前都重新划分桶，优点是每次分桶都能保证各桶中的样本数量都是均匀的，不足的地方就是计算量大。

四、其它特点

4.1 缺失值处理

?? 对于存在某一维特征缺失的样本，xgb会尝试将其放到左子树计算一次增益，再放到右子树计算一次增益，对比放在左右子树增益的大小决定放在哪个子树。

4.2 防止过拟合

?? xgb提出了两种防止过拟合的方法：第一种称为Shrinkage，即学习率，在每次迭代一棵树的时候对每个叶子结点的权重乘上一个缩减系数，使每棵树的影响不会过大，并且给后面的树留下更大的空间优化。另一个方法称为Column Subsampling，类似于随机森林选区部分特征值进行建树，其中又分为两个方式:方式一按层随机采样，在对同一层结点分裂前，随机选取部分特征值进行遍历，计算信息增益；方式二在建一棵树前随机采样部分特征值，然后这棵树的所有结点分裂都遍历这些特征值，计算信息增益。