【机器学习】XGBoost模型详解-python while循环语句

 

简介：XGBoost也是梯度提升树模型的一种，同样是串行地生成模型，取所有模型的和为输出。XGBoost将损失函数作二阶泰勒展开，利用损失函数的二阶导数信息优化损失函数，根据损失函数是否减小来贪心的选择是否分裂节点。同时，XGBoost在防止过拟合方面加入了正则化、学习率、列采样、近似最优分割点等手段。在处理缺失值方面也做了一定的优化。

1 模型原理

首先回顾一下最简单的决策树。当我们用一颗CART决策树作回归的时候，我们遍历所有的特征和分割点，选择使得平方误差最小的特征及其分割点进行分裂。当我们用一颗CART决策树作分类的时候，我们遍历所有的特征和分割点，选择使得基尼系数最小的特征及其分割点进行分裂。

到了GBDT的时代。GBDT是对多个CART集成，每一颗CART训练的目标都是当前损失函数的负梯度方向。在节点分裂的过程中，依然是基于最小平方误差或基于最小基尼系数做特征选择。

XGBoost也是一个加法模型，但是它结点分裂的标准发生了新的变化。无论是回归问题还是分类问题，我们都先定义一个损失函数 L(y,y^)\mathcal{L}(y, \widehat{y}) ，损失函数是可微的任意损失函数。对于一个树结构q，它的损失函数如下：

（ mm 为样本总数， tt 为当前基学习器索引， TT 为当前基学习器叶子结点数， IjI_j 为第 jj 个结点的样本索引集合， wjw_j 为第 jj 个结点的权重，如果样本 xx 在第 jj 个结点上，则 f(x)=wjf(x) = w_j ）

展开二阶泰勒展开，，展开去掉常数，合并叶子结点的样本定义：，Objt=∑i=1mL(y(i),y^t(i))+Ω(ft)=∑i=1mL(y(i),y^t−1(i)+ft(x(i)))+Ω(ft)展开y^=∑i=1m[L(y(i),y^t−1(i))+gift(x(i))+12hift(x(i))2]+Ω(ft)二阶泰勒展开，gi=∂L(y,yt−1^(i))∂y^t−1(i)，hi=∂2L(y,yt−1^(i))∂y^t−1(i)2=∑i=1m[L(y(i),y^t−1(i))+gift(x(i))+12hift(x(i)))2]+γT+12λ∑j=1Twj2展开Ω(ft)=∑j=1T[(∑i∈Ijgi)wj+12(∑i∈Ijhj+λ)wj2]+γT去掉常数，合并叶子结点的样本=∑j=1T[Gjwj+12(Hj+λ)wj2]+γT定义：Gi=∑i∈Ijgi，Hj=∑i∈Ijhj\begin{align*} &Obj_t=\sum_{i=1}^{m}\mathcal{L}(y^{(i)}, \widehat{y}^{(i)}_t)+\Omega(f_t) \\ &\ \ \ \ \ \ \ =\sum_{i=1}^{m}\mathcal{L}(y^{(i)}, \widehat{y}_{t-1}^{(i)}+f_t(x^{(i)}))+\Omega(f_t)\ \ \ \ \ \ \ \ \ \ \ 展开\widehat{y}\\ &\ \ \ \ \ \ \ =\sum_{i=1}^{m}[\mathcal{L}(y^{(i)}, \widehat{y}_{t-1}^{(i)})+g_if_t(x^{(i)})+\frac{1}{2}h_if_t(x^{(i)})^2]+\Omega(f_t)\ \ \ \ \ \ \ \ \ \ \ 二阶泰勒展开，g_i=\frac{\partial{\mathcal{L}(y, \widehat{y_{t-1}}^{(i)})}}{\partial{\widehat{y}_{t-1}^{(i)}}}，h_i=\frac{\partial^2{\mathcal{L}(y, \widehat{y_{t-1}}^{(i)})}}{\partial{\widehat{y}_{t-1}^{(i)}}^2} \\ &\ \ \ \ \ \ \ =\sum_{i=1}^{m}[\mathcal{L}(y^{(i)}, \widehat{y}^{(i)}_{t-1})+g_if_t(x^{(i)})+\frac{1}{2}h_if_t(x^{(i)}))^2]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^Tw_j^2\ \ \ \ \ \ \ \ \ \ \ 展开\Omega(f_t) \\ &\ \ \ \ \ \ \ =\sum_{j=1}^T[(\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i\in I_j}h_j+\lambda)w_j^2]+\gamma T\ \ \ \ \ \ \ \ \ \ \ 去掉常数，合并叶子结点的样本 \\ &\ \ \ \ \ \ \ =\sum_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T\ \ \ \ \ \ \ \ \ \ \ 定义：G_i=\sum_{i \in I_j}g_i，H_j=\sum_{i\in I_j}h_j \\ \end{align*}

对于每一种树结构q，它的叶子结点的权重可以求解得到：

∂Objt∂wj=Gj+(Hj+λ)wj=0⇒wj=−GjHj+λ\frac{\partial{Obj_t}}{\partial{w_j}}=G_j+(H_j+\lambda)w_j=0\ \ \Rightarrow\ \ \ w_j=-\frac{G_j}{H_j+\lambda}\\

因此，对于树结构q，它的损失函数为：

Objt=−12∑j=1TGj2Hj+λ+γTObj_t=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T\\

如此一来，只要遍历所有的树结构q，计算所有样本在结构q下的一阶导、二阶导，就能计算每个树结构的损失 ObjtObj_t 。通过比较所有树结构的 ObjtObj_t ，选择最小 ObjtObj_t 对应的结构就是当前t时刻的新学习器。

然而上述过程计算量太大，是不现实的。因此XGBoost使用一个贪心方法，对于当前节点及其对应数据集，可以计算出一个损失，为分裂前损失（类似于原始决策树中的熵）：

一个结点−12G2H+λ+γ一个结点T=1-\frac{1}{2}\frac{G^2}{H+\lambda}+\gamma\ \ \ \ 一个结点T=1\\

再计算按某一特征与分裂点分裂成左右子树的损失和，为分裂后损失：

两个结点−12GL2HL+λ−12GR2HR+λ+2γ两个结点T=2-\frac{1}{2}\frac{G_L^2}{H_L+\lambda}-\frac{1}{2}\frac{G_R^2}{H_R+\lambda}+2\gamma\ \ \ \ 两个结点T=2\\

定义分裂增益为 = 分裂前的损失 - 分裂后的损失：

Gain=12(GLHL2+λ+GRHR2+λ−GH2+λ)−γGain=\frac{1}{2}(\frac{G_L}{H_L^2+\lambda} + \frac{G_R}{H_R^2+\lambda}- \frac{G}{H^2+\lambda})-\gamma \\

若 0">Gain>0Gain>0 ，表示分裂前增益大于分裂后增益，分裂可行。综上，寻找最优树结构q的问题，就可以简化为遍历当前结点的所有特征及其分裂点，选择Gain最大的特征及分裂点的问题。

如果人工不加限制，XGBoost停止分裂的标准是分裂增益小于0。但实践中往往会出现过拟合情况，因此可以通过人工设定参数，如最大深度max_depth、叶子结点最小样本数min_data_in_leaf等等的超参数来限制基学习器的复杂度，也就是常说的预剪枝。

2 其他方面

XGBoost防止过拟合的手段

首先，在其损失函数的定义中加入了正则化项。 γ\gamma 是叶子节点个数的正则化， λ\lambda

叶子结点权重的正则化。

其次，XGBoost在论文中点明了通过shrinkage（等同于梯度下降的学习率）和列采样（借鉴随机森林列采样）防止过拟合。

再次，在实践中可以通过设定基学习器的一些超参数，如树深度、叶子结点最小样本数、叶子结点个数等防止过拟合。

近似最优分割点与并行化处理

为了能加速最优分割点的选择，XGBoost按照特征值的密度分布，对特征值进行分桶，用桶的边界值作为分裂点的候选。因此在训练之前，需对特征值进行预排序找出候选切割点，然后保存为block结构，后面的迭代中重复地使用这个结构，从而大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂。因此各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

这种处理也能够起到防止过拟合的作用。

缺失值

在训练阶段寻找分裂点的时候，计算的分裂增益不包含缺失值样本。在逻辑实现上，为了保证完备性，会分别将缺失该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向归类含缺失值样本。

在预测阶段，如果训练集没有缺失值而测试集出现缺失值，则要为缺失值（或者指定的值未出现的值）指定分支的默认方向，预测时自动将缺失值的划分到这一分支。

Ref.

XGBoost：A Scalable Tree Boosting System

NLP/AI面试全记录（持续更新）

gbdt、xgb、lgb、cat面经整理——from牛客

ID3、C4.5、CART、RF、boosting、Adaboost、GBDT、xgboost模型

LightGBM GBDT XGBoost的区别