XGBoost: 从决策树说起

作者: 紫色de枫 | 来源:发表于2019-12-16 20:44 被阅读0次

XGBoost: 从决策树说起
从决策树到XGBoost
从决策树到XGBoost
一文道尽XGBOOST的前世今生
从cart决策树到XGBoost
机器学习面试005—决策树
数据挖掘实践任务4
【机器学习】决策树（下）——XGBoost、LightGBM（非
集成学习综述-从决策树到XGBoost
数据挖掘-分类

学习笔记，可能有些谬误，请批判性阅读。

决策树用来进行分类或回归都是可以的。

一棵决策树构成的分类器，从根节点开始，依循划分标准，向左或向右走下去。这样递归地进行，直到叶子节点为止。叶子节点的类别或值，就是分类或回归的预测结果。

一棵平平无奇的决策树，是怎么生成的

信息熵

用来衡量事件的确切性程度，或样本的同一性。

如果样本全部属于同一类，信息熵为0；

如果样本等分为不同类别，信息熵为1。

公式长这样：

$E(S)=\sum_{i=1}^c -p_{i} \log_2 p_{i}$

其中， $E$ 指entropy，这里是指信息熵； $S$ 是某个分布。

信息增益

增益，是一个相对值，划分后相对划分前，信息熵的变化值，就是信息增益。

$Gain(T,x)=E(T)-E(T,x)$

其中， $T$ 是划分前的树， $x$ 是该划分使用的特征。

构造决策树就是找到信息增益最大的分裂方法（或者说用什么特征什么阈值划分，即纯度最高的分支）。这个思路很直观，实际也很暴力。遍历每个特征的每个可能的分裂值，信息增益最高的，就是最佳分裂。

总结

信息熵和信息增益，是生成决策树的核心依据。具体的生成过程，在文章最后有补充说明。

决策树有一个缺点，容易过拟合。特别是对树的规模没有限制的时候，决策树甚至可以为训练集中的每个uniq样本，生成一条路径。这显然是矫枉过正，遇到没见过的样本，这棵决策树肯定歇菜了。

一般用剪枝来解决这个问题。剪枝的思想是，信息增益低于阈值的分裂（预剪枝，直接不分裂）/子树（后剪枝，已经生成子树），可以不进行分裂/或者用子树的叶子节点的众数进行替代。

集成学习(Boosting)

一棵树或者说单个分类/回归模型的力量是有限的，但我们可以集思广益，多个分类/回归模型共同预测（投票/均值/etc）一件事情。集成学习的单个模型并不局限于决策树，但在决策树中表现的尤为明显。

随机森林

听着还蛮高大上的名字。中心思想是，随机抽取样本子集，构建一棵决策树；这样重复，随机构建多棵决策树；再来，对每个样本，每棵树的预测结果进行投票，就得到了最终预测结果。

随机抽取子集这个思想，就大大降低了过拟合的概率。

梯度增强(Gradient Boosting)

这个就是大名鼎鼎的GBDT(Gradient Boosting Decesion Tree)了。GBDT也是多棵树，但多棵树不是相互独立，而是共同协作的，其中的纽带就是残差。

残差，就是当前状态（预测过程中的某一步），预测值离真实值还有多远。在模型生成/调整的过程中，不断地减小当前残差，使之趋近于0，这样来使模型趋近完美。（我一度十分怀疑Resnet借鉴了GBDT。）

具象一点。

首先，生成了一棵平平无奇的决策树 $T_{1}$ ，此时， $T_{1}$ 的预测值与真实值的差距为 $r_{1}$ 。

然后，我们再生成一棵平平无奇的决策树 $T_{2}$ ，此时 $T_{2}$ 的预测目标就是尽可能接近 $r_{1}$ 。

然鹅，天不遂人愿， $T_{1}+T_{2}$ 的预测值与真实值的差距还有 $r_{2}$ ，不抛弃不放弃，继续生成 $T_{3}$ ， $T_{4}$ ，……

最终，由于残差到0还是过于理想，达到给定阈值就可以了，这样结束了模型生成/调整。

相比随机森林内部比稿，梯度增强还是更团结一些，一起朝着目标进发。

XGBoost推导

XGBoost的X，是指extremely，卓越的GB。

XGBoost在最原始的GBDT基础上，添加了对树结构的惩罚，也就是希望模型尽可能简单，树少一点，每棵树的深度、节点都少一点。

下面给出XGBoost的目标函数的推导过程。

1、假设当前已经生成了 $t$ 棵决策树

那么样本 $x_{i}$ 当前预测值为：

$\hat{y_{i} } ^t =\sum_{k=1}^t f_{k} (x_{i} )=\hat{y_{i}}^{t-1} + f_{t} (x_{i} )$

2、损失函数 $l$

$l=\sum_{i=1}^n (y_{i},\hat{y}^t)=\sum_{i=1}^n(y_i,\hat{y_{i}}^{t-1}+f_t(x_i))$

这里的 $y_i$ 是样本 $x_i$ 的真实值，也就是一个常数。

3、目标函数是在损失函数的基础上，加上了对模型复杂度的惩罚。

$Obj(\Theta )=L(\Theta)+\Omega (\Theta)$

展开来，以 $t$ 棵树构成的分类模型的损失函数，就是

$Obj^t =\sum_{i=1}^n l(y_i,\hat{y}^{t-1}+f_t(x_i))+\Omega(f_t)+constant$

这里取值 $\Omega(\Theta)=\Omega(f_t)+constant$ ，是因为当构造第 $t$ 棵树时，前 $t-1$ 棵树已经固定下来，模型复杂度已经是个常数。实际上这里也是一个归纳法。

4、接下来，借助神奇的泰勒展开。

泰勒展开是一个极限逼近原理，二阶展开式为：

$f(x+\Delta{x})\approx f(x)+g(x)\Delta{x}+\frac{1}{2}h(x)\Delta{x}^2$

其中，

$g(x)=\frac{\mathrm{d}{f}}{\mathrm{d}{x}}$ ，是 $f(x)$ 的一阶导数；

$h(x)=\frac{\partial^2{f}}{\partial{x}}$ ，是 $f(x)$ 的二阶导数。

在目标函数中， $\Delta{x}$ 就是 $f_t$ （第t棵树的预测结果）， $f(x)$ 则是前 $t-1$ 棵树构成的模型的损失函数 $l$ 。

将目标函数转换为：

$Obj^t=\sum_{i=1}^n[ l(y_i,\hat{y}^{t-1})+g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\Omega{(f_t)}+constant$

其中， $g_i$ ， $h_i$ 与上述类似。

然后去掉目标函数中的常数项：

$Obj^t=\sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if^2_t(x_i)]+\Omega{(f_t)}$

5、然后回归到树结构。

假设第 $t$ 棵树的叶子节点个数为 $T$ ，定义这棵树的复杂度：

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

其中， $w_j$ 表示叶子节点 $j$ 对应的值向量。

然后，定义集合 $I_j=\{i\vert q(x_i)=j\}$ ，这里的 $q(x_i)$ 表示样本 $x_i$ 被第 $t$ 棵树预测到叶子节点 $j$ ，这个集合表示所有被第 $t$ 棵树预测到叶子节点 $j$ 的样本的集合。这样，样本集合的分布，就可以转换为叶子节点的分布了。

这样，当 $x\in I_j$ ， $f_t(x_i)=w_j$ 。

目标函数被转换为：

$Obj^t=\sum_{j=1}^T[(\sum_{i\in I_j }g_i)w_j+(\frac{1}{2}\sum_{i\in I_j}h_i)w^2_j]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw^2_j$

合并同类项：

$Obj^t=\sum_{j=1}^T[(\sum_{i\in I_j }g_i)w_j+\frac{1}{2}(\lambda+\sum_{i\in I_j}h_i)w^2_j]+\gamma T$

令：

$G_j=\sum_{i\in I_j}g_i$

$H_j=\sum_{i\in I_j}h_i$

（ $G_j$ ， $H_j$ 是怎么计算的？或者说 $g_i$ ， $h_i$ 是怎么计算的？由定义来看， $g_i$ 是loss函数的一阶导数，例如常见的均方误差，同理可得 $h_i$ 。）

这样，目标函数被化简为：

$Obj^t=\sum_{j=1}^T[(G_jw_j+\frac{1}{2}(\lambda +H_j)w^2_j]+\gamma T$

取极小值时， $Obj^t$ 的一阶导数为0，也就是：

$G_j+(\lambda+H_j)w_j=0$

此时， $w_j=-\frac{Gj}{\lambda+H_j}$ ，这个式子是叶子节点赋值的依据。

代入目标函数，最终可得：

$Obj^t=-\sum_{j=1}^T \frac{G^2_j}{\lambda+H_j}+\gamma T$

这个，奏是XGBoost的目标函数了。

生成一棵新的决策树

需要补充说明的是，XGBoost是如何生成一棵新的决策树呢？采用的是贪心策略。

第一步，计算每个特征的最大收益。（从根节点开始）

其中，收益是指分列前的 $Obj$ ，减去分裂后左右两子树的 $Obj$ 之和，差值越大，分类越好。

对每个特征，将走到当前节点的所有样本的该特征值有序排列，枚举所有取值作为阈值，选取最大收益，作为该特征的收益，记下此时的阈值。

第二步，选择收益最大的特征为分裂特征，以收益最大的阈值进行分裂。

然后，对于当前节点分裂出来的左右节点，分别循环第一步&第二步，直到满足停止条件为止。

参考

[1] https://cloud.tencent.com/developer/article/1005611

[2] http://baijiahao.baidu.com/s?id=1641541736640596344&wfr=spider&for=pc

XGBoost: 从决策树说起
学习笔记，可能有些谬误，请批判性阅读。决策树用来进行分类或回归都是可以的。一棵决策树构成的分类器，从根节点开始...
从决策树到XGBoost
1.引子 XGBoost在机器学习领域可谓风光无限，作为从学术界来的模范生，帮助工业界解决了许多实际问题，真可...
从决策树到XGBoost
ID3：最大信息增益，只能处理离散特征，只能做分类，多叉树，不能处理缺失值。C4.5：最大信息增益率，可以对连续型...
一文道尽XGBOOST的前世今生
XGBOOST 简介 XGBOOST：简单来说是集成了很多个基学习器（如Cart决策树）的模型。它是集成学习的串行...
从cart决策树到XGBoost
一. cart决策树简述我们知道决策树算法有ID3、C4.5和cart三种，ID3和C4.5是基于信息增益和信息...
机器学习面试005—决策树
1. 请问（决策树、随机森林，Boosting、Adaboot）GBDT和XGBoost的区别是什么？ Ans：①...
数据挖掘实践任务4
任务4：记录5个模型（逻辑回归、SVM、决策树、随机森林、XGBoost）关于accuracy、precisio...
【机器学习】决策树（下）——XGBoost、LightGBM（非
此文为转载，原文链接:【机器学习】决策树（下）——XGBoost、LightGBM（非常详细） - 阿泽的文章 -...
集成学习综述-从决策树到XGBoost
姓名李林涛学号 16020199032 转自：http://sigai.cn/paper_11.html 有删...
数据挖掘-分类
分类--逻辑回归，朴素贝叶斯，决策树，随机森林，GDBT，XGBoost 分类评估--正确率，精度，召回率，F1值...

XGBoost: 从决策树说起

一棵平平无奇的决策树，是怎么生成的

信息熵

信息增益

总结