XGBoost
XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。讲解其原理前，要先理解成一下[cart回归树](CART回归树)。
# [XGBoost算法思想](https://www.jianshu.com/p/ac1c12f3fba1)（有实例）
该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。
::: hljs-center
$\hat{y}=\phi\left(x_{i}\right)=\sum_{k=1}^{K} f_{k}\left(x_{i}\right)$
:::
::: hljs-center
其中 $F=\left\{f(x)=w_{q(x)}\right\}\left(q: R^{m} \rightarrow T, w \in R^{T}\right)$
:::
注：$w_q(x)$为叶子节点$q$的分数，$f(x)$为其中一棵回归树
如下图例子，训练出了2棵决策树，小孩的预测分数就是两棵树中小孩所落到的结点的分数相加。爷爷的预测分数同理。
::: hljs-center
:::
# XGBoost原理
XGBoost目标函数定义为：
::: hljs-center
:::
其中，$\Omega(f)=\gamma T+\frac{1}{2} \lambda\|w\|^{2}$
目标函数由两部分构成，第一部分用来衡量预测分数和真实分数的差距，另一部分则是正则化项。正则化项同样包含两部分，T表示叶子结点的个数，w表示叶子节点的分数。γ可以控制叶子结点的个数，λ可以控制叶子节点的分数不会过大，防止过拟合。
正如上文所说，新生成的树是要拟合上次预测的残差的，即当生成t棵树后，预测分数可以写成：
::: hljs-center
$\hat{y}_{i}^{(t)}=\hat{y}_{i}^{(t-1)}+ f_{t}\left(x_{i}\right)$
:::
同时，可以将目标函数改写成：
::: hljs-center
$\mathcal{L}^{(t)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(\mathbf{x}_{i}\right)\right)+\Omega\left(f_{t}\right)$
:::
很明显，我们接下来就是要去找到一个$f_t$能够最小化目标函数。XGBoost的想法是利用其在$f_t=0$处的泰勒二阶展开近似它。所以，目标函数近似为：
::: hljs-center
$\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)$
:::
其中$g_i$为一阶导数，$h_i$为二阶导数：
::: hljs-center
$g_{i}=\partial_{\hat{y}^{(t-1)}} l\left(y_{i}, \hat{y}^{(t-1)}\right), \quad h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)$
:::
由于前t-1棵树的预测分数与y的残差对目标函数优化不影响，可以直接去掉。简化目标函数为：
::: hljs-center
$\tilde{\mathcal{L}}^{(t)}=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)$
:::
上式是将每个样本的损失函数值加起来，我们知道，**每个样本都最终会落到一个叶子结点中，所以我们可以将所以同一个叶子结点的样本重组起来**，过程如下图：
::: hljs-center
$\begin{aligned} O b j^{(t)} & \simeq \sum_{i=1}^{n}\left[g_{i} f_{t}\left(x_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(x_{i}\right)\right]+\Omega\left(f_{t}\right) \\ &=\sum_{i=1}^{n}\left[g_{i} w_{q\left(x_{i}\right)}+\frac{1}{2} h_{i} w_{q\left(x_{i}\right)}^{2}\right]+\gamma T+\lambda \frac{1}{2} \sum_{j=1}^{T} w_{j}^{2} \\ &=\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 \end{aligned}$
:::
因此通过上式的改写，我们可以将目标函数改写成关于叶子结点分数w的一个一元二次函数，求解最优的w和目标函数值就变得很简单了，直接使用顶点公式即可。因此，最优的w和目标函数公式为
::: hljs-center
$w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda} \quad O b j=-\frac{1}{2} \sum_{j=1}^{T} \frac{G_{j}^{2}}{H_{j}+\lambda}+\gamma T$
:::
（ 其中 ： $G_{j}=\sum_{i \in I_{j}} g_{i} \quad H_{j}=\sum_{i \in I_{j}} h_{i}$ ）
# 分裂结点算法
在上面的推导中，**<font color=#008000>我们知道了如果我们一棵树的结构确定了，如何求得每个叶子结点的分数</font>。但我们还没介绍如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点。**
正如上文说到，基于空间切分去构造一颗决策树是一个**NP难问题**，我们不可能去遍历所有树结构，因此，XGBoost提供了3中分裂节点的算法，见：[**XGBoost学习-分裂点的选择**](https://blog.csdn.net/dpengwang/article/details/87910480)，并使用上式目标函数值作为评价函数 。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。
同时可以设置树的最大深度、当样本权重和小于设定阈值时停止生长去防止过拟合。
# XGBoost为什么要二阶导
**xgboost使用二阶泰勒展开的目的和优势有一下两方面：**
>- xgboost是以mse为基础推导出来的，在mse的情况下，xgboost的目标函数展开就是一阶项+二阶项的形式，而其他类似logloss这样的目标函数不能表示成这种形式。为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接**自定义损失函数**了，只要二阶可导即可，增强了模型的扩展性。
>- 二阶信息能够让梯度**收敛的更快**，类似牛顿法比SGD收敛更快。一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。
# XGBoost防止过拟合
XGBoost还提出了两种防止过拟合的方法：**Shrinkage** 和 **Column Subsampling**
**Shrinkage方法**就是在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重η，这可以使得每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型。
**Column Subsampling**类似于随机森林中的选取部分特征进行建树。其可分为两种，一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。
# 针对稀疏数据的算法（缺失值处理）
当样本的第i个特征值缺失时，无法利用该特征进行划分时，XGBoost的想法是**将该样本分别划分到左结点和右结点，然后计算其增益，哪个大就划分到哪边。**
---
# [xgboost模型特征重要性的不同计算方式](https://blog.csdn.net/oppo62258801/article/details/100941922)
# XGBoost的优缺点
之所以XGBoost可以成为机器学习的大杀器，广泛用于数据科学竞赛和工业界，是因为它有许多优点：
>1. 使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等。
>2. 目标函数优化利用了损失函数关于待求函数的二阶导数
>3. 支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。
>4. 添加了对稀疏数据的处理。
>5. 交叉验证，early stop，当预测结果已经很好的时候可以提前停止建树，加快训练速度。
>6. 支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本。
**然而，与LightGBM相比，又表现出了明显的不足：**
1. xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；
2. xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.
我的补充：最多到千百量级的特征，特征再多了效果提升不明显(LR+FTRL可到十亿百亿级)；不支持线上实时训练(LR+FTRL支持)
# XGBoost常见面试题
[XGBOOST常见问题以及面试题](https://blog.csdn.net/qq_38147421/article/details/107832974)
---
**扩展阅读：**
[灵魂拷问，你看过Xgboost原文吗？](https://zhuanlan.zhihu.com/p/86816771)
[Xgboost使用](http://www.huaxiaozhuan.com/%E5%B7%A5%E5%85%B7/xgboost/chapters/xgboost_usage.html)
[xgboost怎么调参？](http://sofasofa.io/forum_main_post.php?postid=1000868)
---
转载：[xgboost原理？(知乎：灰灰的回答)](https://www.zhihu.com/question/58883125/answer/669406071)
讲解：[XGBoost](https://www.bilibili.com/video/BV1S441147Ae?p=1)