XGBoost算法思想

作者: PrivateEye_zzy | 来源:发表于2019-07-19 16:33 被阅读0次

[Python与数据分析]-16XGBoost
XGBoost原理以及python的实现
XGBoost算法思想
一文读懂机器学习大杀器XGBoost原理
基于树模型的集成算法 ---XGBoost
集成学习之Boosting-xgboost
win系统中安装xgboost的教程
Kaggle实战系列之"San Francisco Crime
必须掌握的算法
xgboost目标函数推导

本章涉及到的知识点清单：

1、boosting模式

2、集成学习模型的偏差和方差

3、bagging的偏差和方差

4、boosting的偏差和方差

5、XGBoost的基础模型

6、XGBoost的目标函数

7、优化目标函数

8、树的函数表达式的拆分

9、模型的复杂度定义

10、继续优化目标函数

11、求解目标函数极值

12、树节点分裂算法

13、XGBoost的算法步骤

14、案例演示

15、XGBoost的优点

一、boosting模式

boosting属于集成学习框架之一，与bagging类似，boosting也不再是用单一的模型来进行预测，而是组合若干弱学习器来产生一个强学习器

boosting：整个训练过程呈阶梯状，弱学习器按照次序逐一进行训练，与bagging不同在于每个弱学习器的训练集，都按照某种策略进行一定的转化，最后对所有弱学习器的预测结果进行线性综合来产生最终的预测结果。即：

boosting模型

boosting有如下特点：

（1）所有弱学习器的学习过程均依赖于同一份训练集结果，训练集在每个弱学习器训练完成后，都会按照同一策略更新转化

（2）所有弱学习器的训练过程是串行化的，即当前弱学习器训练的参数依赖于上一个弱学习器训练的结果

（3）所有弱学习器对于训练集的每个样本都有相同的初始化权重

（4）当每个弱学习器学习完，而对于那些预测结果错误的样本会采用某个策略来增加其权重

（5）boosting总是更加关注被错误预测的弱规则

关于boosting算法比较常见的有：AdaBoost、GBDT以及本文分析的XGBoost

二、集成学习模型的偏差和方差

偏差：描述模型的预测值和样本的真实值之间的差异，反映模型的准确度

方差：描述模型的预测值作为随机变量的离散程度，反映模型的过拟合能力

这里我们可以用期望这个统计量来描述模型的偏差

由方差和协方差的基本定义出发：

方差的定义

协方差的定义

对于集成学习模型，通过计算弱学习器模型的期望和方差，我们可以得到模型整体的期望和方差。而且不论是bagging还是boosting，其弱学习器都是线性组成的，我们设每个弱学习器为 $f_{i}$ ，总共有 $m$ 个弱学习器， $f_{i}$ 对应的权重为 $r_{i}$ ， $F$ 为整个模型

则模型的期望 $E(F)$ 为：

模型的期望

模型的方差 $var(F)$ 为：

模型的方差

这里需要用到二项展开公式

二项展开

带入模型方差展开得

模型的方差

我们再引入2个统计量：标准差 $\sigma$ 和相关系数 $\rho$ ，用来代表整体模型的标准差和相关系数，其基本定义为：

标准差和相关系数的定义

将 $\sigma$ 和 $\rho$ 带入模型方差，得

模型的方差

推导至此，我们得到了集成学习整体模型的期望 $E(F)$ 和方差 $var(F)$ 的数学表达式

集成学习模型的期望和方差

集成学习模型的整体偏差和方差的关系可形象的展示为：

集成学习模型的整体偏差和方差

接下来我们分别讨论在bagging或boosting算法下模型整体的期望和方差

三、bagging的期望和方差

对于bagging来说，每个弱学习器的权重 $r_{i}$ 都为 $\frac{1}{m}$ ，且每个弱学习器训练的样本都是从原始样本采取有放回式随机抽样，故每个弱学习器的期望 $E(f_{i})$ 近似相等为 $\mu$

则bagging的期望为：

bagging的期望

bagging的方差为：

bagging的方差

比较集成学习模型的期望和方差，可以总结出bagging：

（1）模型整体的期望近似等于单个弱学习器的期望

（2）随着训练的进行，模型整体的方差降低

我们也可以看到，随机森林(Random Forest)采取对训练集的特征进行随机抽样的策略，使得各个弱学习器的相关性降低，从而达到减少方差的效果

四、boosting的偏差和方差

对于boosting来说，训练集抽样是强相关的，即模型的相关系数 $\rho$ 近似等于1

则boosting的期望为：

boosting的期望

boosting的方差为：

boosting的方差

比较集成学习模型的期望和方差，可以总结出boosting：

（1）刚初始化时，模型整体的期望较低，方差较低

（2）随着训练的进行，模型整体的期望升高，方差也增大

五、XGBoost的基础模型

XGBoost（Extreme Gradient Boosting）是GBDT的一种高效实现，其弱学习器除了可以是CART回归树，也可以是线性分类器。这里我们用CART树来当作弱学习器

考虑场景：我们要预测一家人对电子游戏的喜好程度，为此可以构建2颗CART树

第1颗CART树：考虑到年轻和年老相比，年轻更可能喜欢电子游戏，故使用“年龄”作为第1个特征来二分样本集；再考虑到男性和女性相比，男性更喜欢电子游戏，故使用“性别”作为第2个特征来二分子样本集，最后逐一给各人在电子游戏喜好程度上打分

第2颗CART树：考虑到喜欢电子游戏的人每天使用电脑的频率较高，故使用“每天使用电脑的频率”作为特征来二分子样本集，最后逐一给各人在电子游戏喜好程度上打分

场景CART树

对于上述两颗CART树，我们要计算小男孩的预测分数，只需在每颗CART树中找到小男孩落在的树叶位置，将树叶对应的分数累加即可

上述物理场景的行为过程如下：

（1）有K颗CART树

（2）对于任意n维样本 $x_{i}$ ，找到其在每颗树中所在叶子的位置和该叶子的权重

（3）将这些权重相加，作为 $x_{i}$ 最后的预测分数

我们将上述场景数学化

设 $\hat{y}_{i}$ 是样本 $x_{i}$ 的最终预测分数， $f_{i}$ 是第i颗树的叶子打分映射，则预测函数为

模型的预测函数

所有树的叶子打分映射将共同构成模型的函数空间，即

模型的函数空间

（PS：注意这里不再是模型的参数空间 $\theta$ ，而是函数空间 $f$ ）

六、XGBoost的目标函数

我们继续定义出模型的损失函数为

模型的损失函数

其中 $l(y_{i}, \hat{y}_{i})$ 是单个样本 $x_{i}$ 的损失函数，可以是任意可微函数，比如平方误差和逻辑误差函数

平方误差函数

逻辑误差函数

接下来我们再定义出模型的复杂度为

模型的复杂度

其中 $\Omega(f_{i})$ 可以用树的深度、叶子的数量、叶子权重的L2范式等量化

我们对上述模型的损失函数和复杂度进行线性组合，便得到了XGBoost的目标函数 $Obj$

XGBoost的目标函数

显然，XGBoost的目标函数加入了正则项，即：用 $L(F)$ 表示模型的偏度（期望），用 $\Omega (F)$ 表示模型的复杂度（方差）

七、优化目标函数

从数学角度看，目标函数 $Obj$ 的定义是一个泛函，优化目标函数等价于泛函最优化问题，这使得我们很难进行优化

（PS： $\hat{y}_{i}$ 的自变量包含K个函数 $f_{i}(x_{i})$ ，即 $\hat{y}_{i}$ 是函数的函数—泛函）

为此我们需要对目标函数进行变换，根据boosting的思想：

（1）每次迭代，都是在现有模型的基础上，增加一个弱学习器

（2）新增加的弱学习器就是一个新函数 $f$ ，用来拟合当前模型的预测结果和真实值的残差

（3）通过不断迭代K个弱学习器来不断降低模型的预测结果和真实值的残差

我们将上述思想进行数学化，即

加入第0颗树，当前模型的预测结果为

加入第0颗树

加入第1颗树，当前模型的预测结果为

加入第1颗树

加入第2颗树，当前模型的预测结果为

加入第2颗树

根据数学归纳法，加入第t颗树，即第t次迭代，当前模型的预测结果为

加入第t颗树

将上述迭代结果带入目标函数，则目标函数改为迭代版本如下

迭代版本的目标函数

下面我们需要对目标函数进行一些数学上的近似处理

我们知道二阶泰勒公式的迭代形式为

二阶泰勒公式的迭代形式

这里我们将目标函数类比二阶泰勒公式，即

类比二阶泰勒公式

且定义 $g_{i}$ 和 $h_{i}$ 来类比二阶泰勒公式中的一阶导数和二阶导数，即

类比二阶泰勒公式

有了上述近似类比，我们将目标函数在 $f_{t}(x_{i})$ 处进行二阶泰勒展开，得

目标函数的泰勒二阶展开

我们继续优化目标函数

由于目标函数只受到基学习器 $f$ 的影响，上一次的误差 $l(y_{i},\hat{y_{i}}^{(t-1)})$ 是常数项，对本次迭代没有影响（常量微分为0），于是我们可以删除掉常数项，即

优化目标函数

至此我们得到了迭代过程下，目标函数的近似表达式，继续优化之前，我们需要先讨论每棵树的函数表达式 $f_{t}(x_{i})$

八、树的函数表达式的拆分

我们将第t颗树的函数表达式 $f_{t}(x_{i})$ ，拆分成树结构部分q和叶子权重部分w，即

树结构和叶子权重

如上图，树的物理意义为：

每个样本均落在树中对应的叶子中，且每片叶子都有权重分数值

我们将其数学化，即定义：

$q(x_{i}):=$ 在树中，任意样本 $x_{i}$ 落在叶子的位置

$w_{q(x_{i})}:=$ 在树中，任意样本 $x_{i}$ 所在叶子的权重

至此，我们可以将树的函数表达式 $f_{t}(x_{i})$ 写为

树的函数表达

九、模型的复杂度定义

紧接着我们定义出模型的复杂度 $\Omega(f_{t})$

我们用叶子节点的个数 $T$ 和每片叶子的权重 $w_{j}$ 的L2范数来共同描述模型的复杂度，即

模型的复杂度

其中 $\gamma$ 和 $\lambda$ 是超参数， $\gamma$ 用来收缩叶子个数， $\lambda$ 控制叶子权重分数不会过大，二者同时防止模型过拟合

十、继续优化目标函数

有了树的函数表达式 $f_{t}(x_{i})$ 的拆分和模型的复杂度 $\Omega(f_{t})$ ，我们继续优化目标函数

将二者带入目标函数，得

目标函数

下面需要用到一个数学技巧，仔细观察上式

目标函数

上式中，红色部分表示：对整个样本集合的遍历；蓝色部分表示：对所有叶节点的遍历

为了将二者的累加形式统一，我们有如下结论

（1）由于所有样本在树结构中，最终都会落在叶子节点上

（2）则遍历所有样本 $\Leftrightarrow$ 遍历所有叶子节点中的子样本

因此我们定义 $I_{j}$ 表示树中第j个叶子中样本的集合，即

第j个叶子中样本集合

将 $I_{j}$ 带入目标函数，我们就可以统一两个 $\sum$ 的物理意义和数学形式，即

目标函数

紧接着我们定义 $G_{i}$ 和 $H_{i}$ 来简化目标函数

简化目标函数

带入则目标函数最终可以化简为

目标函数

至此，我们一步步推导出了XGBoost目标函数的最终表达式，接下来就可以求解其极值

十一、求解目标函数极值

此时弱学习器—树已经构造完成，即树结构 $q(x)$ 确定，为了使得目标函数达到最小值，我们令对每个叶子的偏导数为0，即

每个叶子的偏导数为0

求解上述偏导数，便可解出每个叶子的最优权重 $w_{j}^{*}$ 为：

每个叶子的最优权重

将其带入目标函数，便得到模型的最小损失 $obj^{*}$ 为：

模型的最小损失

至此，我们完成了XGBoost对目标函数的最优化过程。且从本质上讲，这就是转化为一个二次函数最优化问题

十二、树节点分裂算法

下面我们需要关心XGBoost的基学习器—树到底长什么样子？

显然，一棵CART树的生长过程，是由一个根节点开始二分裂，然后各子节点继续二分裂直到分裂产生叶子节点停止

那么一个节点应该怎么分裂？就成为了接下来我们要探讨的关键

我们采取贪心算法来分裂树节点

（1）从根节点开始对每个节点，都遍历所有特征

（2）将所有特征的特征值进行排序，选取不同分位点作为候选点

（3）遍历所有候选点，量化计算按照当前候选点分裂后产生的增益Gain

（4）选择Gain最高的特征和候选点作为当前节点的最优特征和最优分割点

（5）直到产生叶子节点，则停止节点分裂

关于Gain增益的计算，我们使用当前树的最小损失，用节点分裂前的损失值减去分裂后的损失值，作为按当前特征和候选点分裂的增益量化

Gain的计算

按照贪心算法构建树，有下面两种构建方案

方案一：当Gain为负值则停止分裂，树生长完成，这样做效率会高，但有可能会放弃一些更好的情况（预剪枝）

方案二：先让树生长到最大深度，再递归到Gain为负数的节点进行修剪（后剪枝）

这里我们选取方案二进行建树剪枝

十三、XGBoost的算法步骤

（1）循环增加一颗CART树 $f_{t}(x_{i})$

（2）用贪婪算法构建树，包含用损失函数一阶和二阶导数信息计算叶子的最优权重 $w_{j}$ 和节点分裂的最优增益 $Gain$

（3）用构建好的树迭代优化函数空间： $\hat{y}^{(t)}_{i} = \hat{y}^{(t-1)}_{i} + f_{t}(x_{i})$

（4）重新更新计算损失函数的一阶和二阶导数

（5）重复第(1)步，直到生成K颗树

从上面步骤可以看到，关键点是树的构造和剪枝

十四、案例演示

下面我们用原生python来实现myXGBoost模型（不考虑并行计算）

训练样本集为

训练样本集

首先构造树节点类和方法

树节点类

计算样本所在叶子权重

递归统计回归树叶子节点数量和叶子节点的父节点数量

剪枝操作

下面构造树模型类和方法

树模型类

训练CART树

递归构建回归树

选择使得节点分裂最好的特征

计算叶节点的权重值

计算节点分裂后的增益

根据特征和分割点二分化

最后我们构建XGBoost类和方法

XGBoost类

贪婪算法构建树

预测测试集类别

接下来我们定义损失函数，这里用logistic函数

定义损失函数

logistic函数的一阶和二阶偏导数为：

logistic函数

最后比较我们自己写的myXGBoost和官方封装好的黑盒模型xgboost的预测结果差异，用准确度和ROC曲线下面积这两个统计量来比较

和官方黑盒模型比较预测结果

可以看到自己写的模型的预测结果，很逼近官方黑盒模型的预测效果

十五、XGBoost的优点

最后我们可以总结出XGBoost有如下优点：

（1）泰勒二阶

XGBoost对Loss函数的数学处理用到了泰勒二阶展开，除了提高了误差精度，更将待优化的Loss函数转化为关于 $f_{t}(x)$ 的二次函数最优化问题

（2）支持自定义损失函数

XGBoost对Loss函数进行泰勒二阶展开，即支持任意二阶可导的函数作为模型的损失函数

（3）正则化

XGBoost的Loss加入了正则化项，包含了对复杂模型的惩罚，比如惩罚了叶子的节点数量和叶子权重的分数值大小，降低了模型的方差，防止模型过拟合

（4）特征列抽样

XGBoost借鉴了随机森林的做法，对每个训练集特征进行随机不放回式抽样，降低了不同树之间的相关性，从而降低了模型的方差，防止模型过拟合

（5）贪心构建树

采取贪心策略构建最大深度的树，在递归剪枝

（6）支持并行

样本数据事先排好序并以block的形式存储，利于并行计算

还可把XGBoost模型高度抽象为：

把样本从根分配到叶子结点，本质是一个排列组合，而不同的组合对应不同的损失函数，我们要优化寻找的，就是使得损失函数达到最小值的那一种组合方案

案例代码见：XGBoost算法思想

[Python与数据分析]-16XGBoost
1 Xgboost简介 Xgboost是Boosting算法的其中一种，Boosting算法的思想是将许多弱分...
XGBoost原理以及python的实现
文章来源：XGBoost原理 XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱...
XGBoost算法思想
本章涉及到的知识点清单：1、boosting模式2、集成学习模型的偏差和方差3、bagging的偏差和方差4、bo...
一文读懂机器学习大杀器XGBoost原理
作者 | Ray XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在...
基于树模型的集成算法 ---XGBoost
一、模型介绍 XGBoost 是 boosting 算法的其中一种。Boosting 算法的思想是将许多弱分类器集...
集成学习之Boosting-xgboost
一、什么是Xgboost 二、Xgboost的基本原理三、Xgboost的工作实例四、算法的优缺点 *****...
win系统中安装xgboost的教程
xgboost是Tianqi Chen实现的一个boost算法（详细介绍参见XGBoost Documents）,...
Kaggle实战系列之"San Francisco Crime
算法和技术 XGBoost XGBoost全称为eXtreme Gradient Boosting，是陈天奇大牛开...
必须掌握的算法
逻辑回归 SVM XGBoost LDA FM FMM 推荐算法常用推荐算法
xgboost目标函数推导
一说明 xgboost是boosting算法的其中一种，该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵...