XGB算法梳理

算法原理

XGB(extreme gradient boosting)是GBDT的一种工业实现，也是通过不断增加新树，拟合伪残差去降低损失函数。其拟合过程是使用的损失函数的二阶泰勒展开，这是和GBDT的一个区别。

xgboost使用CART树而不是用普通的决策树。对于分类问题，由于CART树的叶子节点对应的值是一个实际的分数，而非一个确定的类别，这将有利于实现高效的优化算法。xgboost出名的原因一是准，二是快，之所以快，其中就有选用CART树的一份功劳。

损失函数

xgboost的数学模型：

$$\hat{y}_{i}=\sum_{k=1}^{K} f_{k}\left(x_{i}\right), f_{k} \in \mathcal{F}$$

其中，$K$ 就是树的棵数，$\mathcal{F}$ 表示所有可能的CART树，$f$ 表示一棵具体的CART树。

模型的目标函数：

$$\operatorname{obj}(\theta)=\sum_{i}^{n} l\left(y_{i}, \hat{y}_{i}\right)+\sum_{k=1}^{K} \Omega\left(f_{k}\right)$$

第一部分就是损失函数，第二部分就是正则项，这里的正则化项由K棵树的正则化项相加而来。

第 $t$ 步时，我们添加了一棵最优的CART树 $f_t$，这棵最优的CART树 $f_t$ 是怎么得来的呢？非常简单，就是在现有的 $t-1$ 棵树的基础上，使得目标函数最小的那棵CART树：

$$\begin{aligned} \mathrm{obj}^{(t)} &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t)}\right)+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)+\Omega\left(f_{t}\right)+\text {constant } \end{aligned}$$

如使用的损失函数时MSE，上式则变为：

$$\begin{aligned} \mathrm{obj}^{(t)} &=\sum_{i=1}^{n}\left(y_{i}-\left(\hat{y}_{i}^{(t-1)}+f_{t}\left(x_{i}\right)\right)\right)^{2}+\sum_{i=1}^{t} \Omega\left(f_{i}\right) \\ &=\sum_{i=1}^{n}\left[2\left(\hat{y}_{i}^{(t-1)}-y_{i}\right) f_{t}\left(x_{i}\right)+f_{t}\left(x_{i}\right)^{2}\right]+\Omega\left(f_{t}\right)+\text {constant } \end{aligned}$$

对于一般的损失函数，我们需要将其作泰勒二阶展开，如下所示：

$$\mathrm{obj}^{(t)}=\sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)+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)+\text {constant }$$

其中：

$$\begin{aligned} g_{i} &=\partial_{\hat{y}_{i}^{(t-1)}} l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right) \\ h_{i} &=\partial_{\hat{y}_{i}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right) \end{aligned}$$

式子最后有一个 $constant$ 项，就是前 $t-1$ 棵树的正则化项。$l\left(y_{i}, \hat{y}_{i}^{(t-1)}\right)$也是常数项。剩下的三个变量项分别是第 $t$ 棵CART树的一次式，二次式，和整棵树的正则化项。

将常数项去掉，变为下式：

$$\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)$$

xgboost可以支持自定义损失函数，只需满足二次可微即可。

分裂结点算法

• 精确的贪心法，枚举所有分割点。当数据量十分庞大，以致于不能全部放入内存时，Exact Greedy 算法就会很慢。
• 针对精确贪心法的不足，引入了近似的算法。简单来说，就是根据特征 $k$ 的分布来确定 $l$ 个候选切分点 $Sk={sk1,sk2,…,skl}$，然后根据这些候选切分点把相应的样本放入对应的桶中，对每个桶中的 G,H 进行累加。最后在候选切分点集合上贪心查找。
• 加权分位法
• 稀疏自适应分割策略

正则化

假设CART树如下所示：

$$f_{t}(x)=w_{q(x)}, w \in R^{T}, q : R^{d} \rightarrow\{1,2, \cdots, T\}.$$

一棵树有 $T$ 个叶子节点，这T个叶子节点的值组成了一个 $T$ 维向量 $w$，$q(x)$ 是一个映射，用来将样本映射成 $1$ 到 $T$ 的某个值，也就是把它分到某个叶子节点，$q(x)$ 其实就代表了CART树的结构，$w_{q(x)}$ 是这棵树对样本 $x$ 的预测值。

xgboost 使用如下的正则化项：

$$\Omega(f)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}$$

这里出现了 $γ$ 和 $λ$，这是xgboost自己定义的，在使用xgboost时，可以设定它们的值，$γ$ 越大，表示获得结构越简单的树，因为此时对较多叶子节点的树的惩罚越大。$λ$ 越大也是获得结构越简单的树。

对缺失值处理

通常情况下，人为处理缺失值的时候大多会选用中位数、均值或二者的融合来对数值型特征进行填补，使用出现次数多的类别来填补缺失的类别特征。

在xgboost模型中允许缺失值存在。

对于特征的值有缺失的样本，xgboost可以自动学习出他的分裂方向。Xgboost内置处理缺失值的规则。用户需要提供一个和其他样本不同的值，然后把它作为一个参数穿进去，以此来作为缺失值的取值。Xgboost在不同节点遇到缺失值时采用不同的处理方法，并且会学习未来遇到缺失值时的处理方法。

优缺点

xgBoosting在传统Boosting的基础上，利用cpu的多线程，引入正则化项，加入剪纸，控制了模型的复杂度。

与GBDT相比，xgBoosting有以下进步：

1. GBDT以传统CART作为基分类器，而xgBoosting支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；
2. GBDT在优化时只用到一阶导数，xgBoosting对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数；
3. 当样本存在缺失值是，xgBoosting能自动学习分裂方向；
4. xgBoosting借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算；
5. xgBoosting的代价函数引入正则化项，控制了模型的复杂度，正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从贝叶斯方差角度考虑，正则项降低了模型的方差，防止模型过拟合；
6. xgBoosting在每次迭代之后，为叶子结点分配学习速率，降低每棵树的权重，减少每棵树的影响，为后面提供更好的学习空间；
7. xgBoosting工具支持并行,但并不是tree粒度上的，而是特征粒度，决策树最耗时的步骤是对特征的值排序，xgBoosting在迭代之前，先进行预排序，存为block结构，每次迭代，重复使用该结构，降低了模型的计算；block结构也为模型提供了并行可能，在进行结点的分裂时，计算每个特征的增益，选增益最大的特征进行下一步分裂，那么各个特征的增益可以开多线程进行；
8. 可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；

然而，与LightGBM相比，又表现出了明显的不足：

1. xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；
2. xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.

sklearn参数

xgboost.XGBClassifier(max_depth=3, learning_rate=0.1, n_estimators=100, silent=True, objective='binary:logistic', booster='gbtree', n_jobs=1, nthread=None, gamma=0, min_child_weight=1, max_delta_step=0, subsample=1, colsample_bytree=1, colsample_bylevel=1, reg_alpha=0, reg_lambda=1, scale_pos_weight=1, base_score=0.5, random_state=0, seed=None, missing=None, **kwargs)

参数：

• booster：
  • gbtree 树模型做为基分类器（默认）
  • gbliner 线性模型做为基分类器
• n_jobs： 并行线程数
• silent：
  • silent=0时，不输出中间过程（默认）
  • silent=1时，输出中间过程
• nthread：
  • nthread=-1时，使用全部CPU进行并行运算（默认）
  • nthread=1时，使用1个CPU进行运算。
• scale_pos_weight：
  • 正样本的权重，在二分类任务中，当正负样本比例失衡时，设置正样本的权重，模型效果更好。例如，当正负样本比例为1:10时，scale_pos_weight=10。
• n_estimatores：
  • 含义：总共迭代的次数，即决策树的个数
• max_depth：
  • 含义：树的深度，默认值为6，典型值3-10。
  • 调参：值越大，越容易过拟合；值越小，越容易欠拟合。
• min_child_weight：
  • 含义：默认值为1,。
  • 调参：值越大，越容易欠拟合；值越小，越容易过拟合（值较大时，避免模型学习到局部的特殊样本）。
• subsample：
  • 含义：训练每棵树时，使用的数据占全部训练集的比例。默认值为1，典型值为0.5-1。
  • 调参：防止overfitting。
• colsample_bytree：
  • 含义：训练每棵树时，使用的特征占全部特征的比例。默认值为1，典型值为0.5-1。
  • 调参：防止overfitting。
• learning_rate：
  • 含义：学习率，控制每次迭代更新权重时的步长，默认0.3。
  • 调参：值越小，训练越慢。
  • 典型值为0.01-0.2。
• gamma：
  • 惩罚项系数，指定节点分裂所需的最小损失函数下降值。
• alpha：
  • L1正则化系数，默认为1
• lambda：
  • L2正则化系数，默认为1