一文详尽XGBOOST的前世今生

XGBOOST 简介

XGBOOST：简单来说是集成了很多个基学习器（如Cart决策树）的模型。它是集成学习的串行方式（boosting）的一种经典实现，是广泛应用在工业、竞赛上的一大神器。

集成学习是结合一些的基学习器来改进其泛化能力和鲁棒性的方法，主流的有两种集成思想：

并行方式（bagging）：独立的训练一些基学习器，然后（加权）平均它们的预测结果。如：Random Forests；
串行方式（boosting）：一个接一个的(串行)训练基学习器，每一个基学习器主要用来修正前面学习器的偏差。如：AdaBoost、GBDT及XGBOOST； （注：此外还有stacking方法，但stacking更多被看做是融合的策略；）

一、基学习器--决策树

决策树有非线性、拟合能力强且可以通过剪枝快速调整的特性，集成学习通常选择决策树作为基学习器。（注：XGBOOST中的基学习器可以是CART回归树-gbtree, 也可以是线性分类器-gblinear。本文着重从树模型介绍。）

决策树是一种简单的机器学习回归/分类方法，它是由(if-then)决策结构以树形组合起来，叶子节点代表最终的预测值或类别。典型的决策树模型有：ID3、C4.5和CART。

决策树算法可以概括为两个阶段：

树的生长：思想是自顶向下递归分治构建树，是依靠（信息增益、信息增益比、gini、平方误差）等某个指标做特征选择、划分的过程。

树的剪枝：决策树容易对数据产生过拟合，即生长出结构过于复杂的树模型。通过剪枝算法可以降低复杂度，减少过拟合的风险。

决策树剪枝算法的根本目的是极小化损失函数（经验损失结构损失），基本策略有”预剪枝“和”后剪枝“两种策略：①预剪枝：是在决策树生成过程中，限制划分的最大深度、叶子节点数和最小样本数目等，以减少不必要的模型复杂度；②后剪枝：先从训练集生成一棵完整的决策树，然后用用验证集自底向上地对非叶结点进行考察，若将该节点对应的子树替换为叶子结点（剪枝）能带来决策树的泛化性能提升（即目标函数损失更小，常用目标函数如：loss = 模型经验损失bias 模型结构损失α|T|， T为节点数目, α为系数），则将该子树替换为叶子结点。

二、从Cart回归树到GBDT

CART回归树是二叉树结构的决策树，GBDT、XGBoost等梯度提升方法都使用了Cart回归树做基学习器。树的生长是通过平方误差指标选择特征及切分点进行分裂。即遍历所有特征的的所有切分点，最小化目标函数，选择合适的树切分特征（j）及特征阈值（s）找到最优的切分特征和切分点，最终得到一棵回归树。

比如下图的树结点是基于特征（age）进行分裂的，设该特征值小于阈值（20）的样本划分为左子树，其他样本划分为右子树。

GBDT(梯度提升决策树) XGBOOST是在GBDT基础上提升了效率。说到Xgboost，都不得不先从GBDT(Gradient Boosting Decision Tree)说起， GBDT串行学习原理简单来说分为三步：

初始化，通过学习数据集拟合第一棵Cart回归树。如下图的这棵 Tree1学习去预测真实值y，最终模型预测输出y1；
通过学习上一棵树的残差(残差就是预测值与真实值之间的误差，GBDT算法中的关键就是利用损失函数的负梯度作为残差的近似值）拟合下一棵Cart回归树，而后基学习器Cart树依次串行学习。如下图的这棵Tree2学习的是Tree1损失函数的负梯度数据(y-y1)；
最终模型预测值就是将所有串行Cart回归树输出的预测结果相加。