【机器学习】XGBoost

1.什么是XGBoost

        XGBoost(eXtreme Gradient Boosting)极度梯度提升树，属于集成学习中的boosting框架算法。对于提升树，简单说就是一个模型表现不好，继续按照原来模型表现不好的那部分训练第二个模型，依次类推。本质思想与GBDT一致，构建多个基学习器使用加法模型，学习前面基学习器的结果与真实值的偏差，通过多个学习器的学习，不断降低模型值和实际值的差。

         最终模型的预测结果是由所有基学习器预测结果的加和。 

2.XGBoost的目标函数

        XGBoost整体思想就是直接把损失函数和正则项加起来合成一个整体的损失函数，对这个损失函数求二阶导，得到最终的obj，通过obj计算得到一个分数，这个分数越小越好，最终通过obj计算得到的分数确定了树的结构和整个强学习器的分数。所以XGBoost不是通过拟合残差实现的，而是计算obj函数直接得到的树结构。 

        目标函数由两部分组成，第一部分是模型误差，即样本真实值和预测值之间的差值，第二部分是模型的结构误差，即正则项，通过使用超参数乘以结点个数和节点值限制模型的复杂度。 

        正则项公式如下： 

        参数说明： 

       

        优化目标:

         由于是加法模型，所以可以将正则项进行改写，整体的正则项就等于前面t-1棵树的正则项加上当前回归树的正则项。

         而在计算时，前面t-1棵树正则项中的T和w是已经确定的，整体优化目标可以近似表示:

         正则项的确定只与要优化的当前的这颗回归树的叶子结点的w值和叶子结点的个数T有关。

        由于树模型是阶跃的，是不连续的，不适合用梯度下降法，所以需要将目标函数改写，按照样本的顺序做遍历更改为按照叶子结点的顺序做遍历。例如叶子结点有w1、w2....wn。经过回归后落到w1叶子结点下的样本集合K1中包含有不同的预测值，w1的损失值就是w1(叶子结点的值)的值与K1中不同预测值的损失加和，以此类推。

         已经将损失函数转化为与叶子结点的值w有关的多项式，因为损失函数根据不同的任务定义，所以无法提前预知损失函数的形式。接下来的任务是将抽象的损失函数分解为包含w的多项式，通过泰勒二阶展开将w进行提取。

3.公式推导

        使用泰勒二阶对目标函数展开。

         泰勒二阶展开后的损失函数。

         通过分步+贪婪的到树的结构。确定树的结构就是来确定树的叶子结点的值w。

4. XGBoost的优缺点

4-1 优点

（1）精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；

（2）灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑回归（分类问题）或者线性回归（回归问题）。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；

（3）正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是XGBoost优于传统GBDT的一个特性。

（4）防止过拟合：

        1.Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，使每棵树的影响不会过大，让后面有更大的学习空间。主要用于传统GBDT的实现也有学习速率；

        2.Column Subsampling(列采样)，类似于随机森林选区部分特征值进行建树，其中又分为两个方式:方式一按层随机采样，在对同一层结点分裂前，随机选取部分特征值进行遍历，计算信息增益；方式二在建一棵树前随机采样部分特征值，然后这棵树的所有结点分裂都遍历这些特征值，计算信息增益。这也是XGBoost异于传统GBDT的一个特性；

（5）缺失值处理：XGBoost和LightGBM是支持缺失值的，并且XGBoost和LightGBM对缺失值的处理方法相同。xgboost为缺失值设定了默认的分裂方向，对于存在某一维特征缺失的样本XGBoost会先将其划入左子树计算增益，再划入右子树计算训练增益，对比放在左右子树增益的大小决定放在哪个子树。

4-2 缺点

（1）计算量大:虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；

   (2)内存消耗大：预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

5.  XGBoost与GBDT的联系和区别有哪些？

（1）GBDT是机器学习算法，XGBoost是该算法的工程实现。

（2）正则项：在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。

（3）导数信息：GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。

（4）基分类器：传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。

（5）子采样：传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样。

（6）缺失值处理：传统GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。

（7）并行化：传统GBDT没有进行并行化设计，注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。

Reference：

（1）15.【近似算法】加权分位法_哔哩哔哩_bilibili

（2）XGBoost算法介绍_月落乌啼silence的博客-CSDN博客_xgboost

（3）深入理解XGBoost - 知乎