XGBoost介绍

一、简介

  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，类似于随机森林选区部分特征值进行建树，其中又分为两个方式:方式一按层随机采样，在对同一层结点分裂前，随机选取部分特征值进行遍历，计算信息增益；方式二在建一棵树前随机采样部分特征值，然后这棵树的所有结点分裂都遍历这些特征值，计算信息增益。

五、总结

  以上是对xgb的一些理解，大多是观看了很多大神的博客，通过不断的看别人总结的部分以及公式的推导，才让我逐渐理解xgb的各种特征。本文还是有很多不足的地方，后续逐渐补充，完善。