3.7 Xgboost与GBDT
3.7.1 什么是GBDT算法，与提升树的区别是什么
GBDT（Gradient Boosting Decision Tree）同AdaBoost相似，都是boosting方法与决策树的组合，只不过前者比一般的boosting方法多了“Gradient”，即说明是利用梯度去做提升。下面先介绍一般的提升树，再介绍梯度提升树（GBDT）
1.提升树
前文已经介绍过，AdaBoost方法实质上是前向分步算法求解加法模型的一个特例。提升树依然与AdaBoost相似，亦是采用前向分步算法的一种加法模型，但限制了模型中的基分类器都是决策树。模型表示如下：
其中M表示基分类器——决策树的个数；T(x;θm)表示第m棵决策树，θm则是第m棵决策树的参数。
对于分类与回归这两个问题，提升树也有两种，区别在于基分类器和损失函数。对于分类问题，提升树的基分类器采用二叉分类树，常用指数函数作为损失函数；而对于回归问题，提升树的基分类器采用回归二叉树，常用平方误差作为损失函数。
（1）分类问题的提升树算法
以二分类问题为例，因为同样采用指数损失函数，只需将AdaBoost算法中的基分类器设定为二叉分类树，这时就得到了提升树算法。可以说，在这种情况下，提升树算法是AdaBoost算法的一个特例，具体的实现步骤可参考前文的AdaBoost算法。
（2）回归问题的提升树算法
根据前向分步算法，在第m次循环时，将决策树作为基函数带入求解公式得到：
将均方损失函数代入计算：
L(yi,fm-1(x)+T(x;θm))=(yi- fm-1(x)-T(x;θ))2=(r-T(x;θ))
其中r是fm-1(x)与真实值的差，即表示当前模型的拟合残差。欲使损失函数最小，等价于新的决策树模型T(x;θ)应逼近残差r。
值得一提的是，这里体现出了加法模型与前向分步算法的思想与Bagging方法的典型代表随机森林的差异。随机森林希望基模型大都是准确的、逼近真实值的；而这里的决策树模型拟合的不是真实值，而是残差，强调各模型之间是互相补充、相得益彰的。
算法具体实现步骤如下。
1）令初始基函数为0：f0=0，令m=1。
2）计算现有模型的残差：rmi=yi-fm-1(xi),i=1,…,n
3）用残差rm拟合得到回归树T(x;θm)。
4）更新模型：
fm(x)=fm-1(x)+T(x;θm)
5）令m=m+1，重复2）～3）的步骤；直到m=M+1。
6）得到提升树模型：
2.GBDT
上述提升树采用了指数损失函数与均方损失函数，计算求解公式的最优解时较为简单。但对于一般的损失函数，优化求解会比较复杂。随机森林发明者Breiman的好朋友，Friedman于2001年提出了Gradient Boosting（梯度提升）法。
该方法沿用回归问题提升树中用残差拟合新模型的思想，通过利用最速下降法的原理，用损失函数的负梯度作为残差的近似值，以此拟合新的模型。
算法具体实现步骤如下。
1）令初始基函数为0：f0=0，令m=1。
2）计算现有模型的负梯度：
3）用rmi拟合得到回归树T(x;θm)。
4）更新模型：
fm(x)=fm-1(x)+T(x;θm)
5）令m=m+1，重复2）～3）的步骤；直到m=M+1。
6）得到梯度提升树模型：
对于这个算法，有以下两点说明：
1）m=1时，fm-1=f0=0，这时用rmi拟合得到回归树就等价于用yi拟合回归树。
2）有必要再次强调的是这里的决策树是回归决策树。根据回归树模型，梯度提升树模型可表示如下：
可以证明，GBDT和Adaboost一样都是收敛的。
3.GBDT模型优缺点
优点：
1）GBDT预测结果准确，被认为是统计学习中性能最好的方法之一。
2）可以适应多种损失函数，例如指数损失函数等。
缺点：
1）计算量大，运行速度慢。
2）不适用于高维稀疏特征环境下。
R语言中的gbm包的gbm()函数可以实现GBDT。具体调用如下所示：
其中distribution表示选择的损失函数形式，n.trees表示循环迭代次数，shrinkage表示学习速率等，更多的可参考该函数帮助文档。
Python中也有对应包文件可以直接调用：
3.7.2 什么是Xgboost算法
XGBoost（eXtreme Gradient Boosting）又称极端梯度提升模型，最早于2014年由美国华盛顿大学的博士陈天奇提出，并将其应用于比赛。由于准确率高和运算速度快等良好特性，XGBoost迅速成为各种比赛的“大杀器”，曾一度称霸Kaggle的Top排行榜。
XGBoost脱胎于提升树模型（或者更具体地说是GBDT模型），也是boosting算法的一种。简单来说，相较于GBDT，XGBoost主要在两方面做了进一步提升，除了直接改进模型，还在计算效率等方面做了优化，正是这两方面提升的结合，才使得XGBoost具有又准又快的两大优点，故而拥有很高的普适性和易实践性，成为最流行的机器学习算法之一。
1.模型改进
已知GBDT模型是以回归决策树为基函数，用已有模型的近似残差不断拟合新的模型，并加入现有模型进行更新。XGBoost的逻辑亦是如此，但在两方面有所改进。
一方面，改进损失函数，在损失函数中加上了正则化项。
此时损失函数表达式如下：
其中正则化项一般满足（但不是唯一形式）：
这里T表示树的叶子结点的数量；ω是一个向量，表示树的叶子结点值。
当树的结构越复杂、叶子结点数量越多时，正则化项有增大的倾向。因此，在最小化损失函数时由于正则化项同时会被尽可能地压缩，基函数树模型的复杂度就会得到一定限制。一定程度下避免了模型的过拟合，提高了准确率。
另一方面，改进残差的拟合算法，除了GBDT用到的一阶导数，还用了二阶导数以更精确地拟合残差。
已知泰勒二阶展开：
应用于损失函数为：
其中gi、hi分别为一阶导数、二阶导数，表达式为：
最小化损失函数即可得到新的模型。
2.其他优化
已知前面介绍的boosting方法如Adaboost和GBDT有个共同的缺点就是难以实现并行运算，效率太低，不适用大数据。然而当下大数据的收集是非常普及的，这就影响了理论方法的普适性。而XGBoost一开始就源于比赛实战，具有很强的实用性，这就是本章所讲的优化体现的作用了。
传统决策树在搜寻某一特征的分割点时，使用枚举法计算所有可能分割点的损失函数值并进行比较，对于连续变量效率极低；XGBoost为提升效率化简了枚举的过程，大致思想是将所有可能的分割点用百分位的一些点代替，从这些点中找到最佳分割点即可。
Boosting算法的树与树是串行的，但XGBoost将特征排序后以块的形式存储在内存中，可以在循环时重复使用，一棵树同层的结点可并行运算。具体的对于某个结点，结点内选择最佳分裂点，候选分裂点计算增益用多线程并行。
XGBoost还考虑了训练数据为稀疏值的情况，能极大提升算法效率（相关论文里显示可提升50%）。
3.模型优点
1）一定程度上可以实现并行化，训练速度快。
2）可以处理稀疏数据。
3）正则化项等策略可以更好地防止模型过拟合。
4.XGboost代码展示
Xgboost算法中有非常多的参数，比较重要的有：gamma用于控制是否后剪枝的参数，lambda控制模型复杂度的权重值的L2正则化项参数，max_depth指构建树的深度，subsample指采样训练数据的比例，min_child_weight指结点的最少特征数，nthread指cpu线程数。由于XGboost算法的参数非常多，一个一个调试调试非常麻烦，所以需要利用网格调参的方式选择恰当的参数，下面展示如何利用XGboost算法做网格调参和分类。
通过上面网格调参的方式即可获得最佳的max_depth、learning_rate值，然后定义好参数后，即可放入xgb.train()中进行训练。