参考链接：https://blog.****.net/fenghuibian/article/details/91353348

首先说下决策树

• 决策树是啥？ 
  举个例子，有一堆人，我让你分出男女，你依靠头发长短将人群分为两拨，长发的为“女”，短发为“男”，你是不是依靠一个指标“头发长短”将人群进行了划分，你就形成了一个简单的决策树，官方细节版本自行baidu或google

• 划分的依据是啥？ 
  这个时候，你肯定问，为什么用“头发长短”划分啊，我可不可以用“穿的鞋子是否是高跟鞋”，“有没有喉结”等等这些来划分啊，Of course！那么肯定就需要判断了，那就是哪一种分类效果好，我就选哪一种啊。

• 分类效果如何评价量化呢？ 
  怎么判断“头发长短”或者“是否有喉结”…是最好的划分方式，效果怎么量化。直观来说，如果根据某个标准分裂人群后，纯度越高效果越好，比如说你分为两群，“女”那一群都是女的，“男”那一群全是男的，这个效果是最好的，但事实不可能那么巧合，所以越接近这种情况，我们认为效果越好。于是量化的方式有很多，信息增益（ID3）、信息增益率（C4.5）、基尼系数（CART）等等，来用来量化纯度

• 其他细节如剪枝、过拟合、优缺点、并行情况等自己去查吧。决策树的灵魂就已经有了，依靠某种指标进行树的分裂达到分类/回归的目的（上面的例子是分类），总是希望纯度越高越好。

说下Xgboost的建树过程

Xgboost是很多CART回归树集成

• 概念1：回归树与决策树 
  事实上，分类与回归是一个型号的东西，只不过分类的结果是离散值，回归是连续的，本质是一样的，都是特征（feature）到结果/标签（label）之间的映射。说说决策树和回归树，在上面决策树的讲解中相信决策树分类已经很好理解了。

  回归树是个啥呢？

  直接摘抄人家的一句话，分类树的样本输出（即响应值）是类的形式，如判断蘑菇是有毒还是无毒，周末去看电影还是不去。而回归树的样本输出是数值的形式，比如给某人发放房屋贷款的数额就是具体的数值，可以是0到120万元之间的任意值。

  那么，这时候你就没法用上述的信息增益、信息增益率、基尼系数来判定树的节点分裂了，你就会采用新的方式，预测误差，常用的有均方误差、对数误差等。而且节点不再是类别，是数值（预测值），那么怎么确定呢，有的是节点内样本均值，有的是最优化算出来的比如Xgboost。 
  细节http://blog.****.net/app_12062011/article/details/52136117博主讲的不错

• 概念2：boosting集成学习，由多个相关联的决策树联合决策，什么叫相关联，举个例子，有一个样本[数据->标签]是[(2，4，5)-> 4]，第一棵决策树用这个样本训练得预测为3.3，那么第二棵决策树训练时的输入，这个样本就变成了[(2，4，5)-> 0.7]，也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关。

  与之对比的是random foreast（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥毛线关系。

  所以首先Xgboost首先是一个boosting的集成学习，这样应该很通俗了

• 这个时候大家就能感觉到一个回归树形成的关键点：（1）分裂点依据什么来划分（如前面说的均方误差最小，loss）；（2）分类后的节点预测值是多少（如前面说，有一种是将叶子节点下各样本实际值得均值作为叶子节点预测误差。

XGBoost

XGBoost全名叫（eXtreme Gradient Boosting）极端梯度提升，经常被用在一些比赛中，其效果显著。它是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包。下面我们将XGBoost的学习分为3步：①集成思想 ②损失函数分析 ③求解。我们知道机器学习三要素：模型、策略、算法。对于集成思想的介绍，XGBoost算法本身就是以集成思想为基础的。所以理解清楚集成学习方法对XGBoost是必要的，它能让我们更好的理解其预测函数模型。在第二部分，我们将详细分析损失函数，这就是我们将要介绍策略。第三部分，对于目标损失函数求解，也就是算法了。

一、集成思想

在学习XGBoost之前，我们得需要先明白集成思想。集成学习方法是指将多个学习模型组合，以获得更好的效果，使组合后的模型具有更强的泛化能力。另外XGBoost是以分类回归树(CART树)进行组合。故在此之前，我们先看下CART树(CART树具体原理请自行复习，或者可以留言)。如下，通过输入用户年龄、性别进行判断用户是否喜欢玩游戏的得分值。由此得到一颗CART树模型。

                                       

我们知道对于单个的决策树模型容易出现过拟合，并且不能在实际中有效应用。所以出现了集成学习方法。如下图，通过两棵树组合进行玩游戏得分值预测。其中tree1中对小男生的预测分值为2，tree2对小男生的预测分值为0.9。则该小男生的最后得分值为2.9。

                                              

将上面集成学习方法推广到一般情况，可知其预测模型为：

                                                                                   

其中为树的总个数，表示第颗树，表示样本的预测结果。

损失函数为：

                                                                       

其中为样本的训练误差，表示第颗树的正则项。

二、损失函数

上面一部分我们知道了集成学习方法的预测模型，因为XGBoost也是集成学习方法的一种。对于XGBoost的预测模型同样可以表示为：

                                                                                              

其中k为树的总个数，表示第k颗树，表示样本的预测结果。

其中损失函数也同样表示为：

                                                                              

其中为样本的训练误差，表示第k棵树的正则项。

看到了这里，我们可能会想到，现在知道了模型预测函数和损失函数，那我们是不是直接就能求出其预测模型了呢？答案肯定不是，我们首先需要明确知道优化和求解的参数是什么呢？由上面的预测模型中，我们可以看到对于每棵树的预测值是如何计算的？想到这里，你就已经知道了需要做的事了，我需要求解和优化的就是每个叶子节点的得分值，也就是的值。另外我们知道XGBoost是以CART树中的回归树作为基分类器，在给定训练数据后，其单个树的结构(叶子节点个数、树深度等等)基本可以确定了。但XGBoost并不是简单重复的将几个CART树进行组合。它是一种加法模型，将模型上次预测(由t-1棵树组合而成的模型)产生的误差作为参考进行下一棵树(第t棵树)的建立。以此，每加入一棵树，将其损失函数不断降低。如下图就为加法模型案例，它将模型预测值与实际值残差作为下一颗树的输入数据。

                                               

对于加法策略可以表示如下：

初始化(模型中没有树时，其预测结果为0)：

往模型中加入第一棵树：

往模型中加入第二棵树：

                                                                 …

往模型中加入第t棵树：

其中表示第棵树，表示组合棵树模型对样本的预测结果。

我们知道，每次往模型中加入一棵树，其损失函数便会发生变化。另外在加入第t棵树时，则前面第t-1棵树已经训练完成，此时前面t-1棵树的正则项和训练误差都成已知常数项。对于每棵树的正则项部分，我们将在后面再细说。

                                                          

如果损失函数采用均方误差时，其目标损失函数变为：

另外对于目标损失函数中的正则项(复杂度)部分，我们从单一的树来考虑。对于其中每一棵回归树，其模型可以写成：

                                            

其中为叶子节点的得分值，表示样本对应的叶子节点。为该树的叶子节点个数。

因此，在这里。我们将该树的复杂度写成：

                                                                  

复杂度计算例子如下：

                              

此时，对于XGBoost的目标函数我们可以写为：

                                                             

三、求解

在推导之前，我们先介绍下泰勒展开式：

                                                         

这里我们用泰勒展开式来近似原来的目标函数，将看作。则原目标函数可以写成：

                       

令，，同时对于第t棵树时，为常数。同时去除所有常数项。故目标损失函数可以写成：

                                                   

由上面介绍书的复杂度时，我们知道：，同时我们将目标函数全部转换成在第t棵树叶子节点的形式。因为目前对于可以看做是每个样本在第t棵树的叶子节点得分值相关函数的结果之和，所以我们也能从第t棵树的叶子节点上来表示。

                                                     

其中T为第t棵树中总叶子节点的个数，表示在第个叶子节点j上的样本，为第j个叶子节点的得分值。

在这里，令，。

则：                   

对求偏导，并使其导函数等于0，则有：

求解得：

其目标函数可以为：

到此，推导完成。

XGBoost的优点

（1）高度灵活性
       传统GBDT以CART作为基分类器，XGBoost还支持线性分类器，这个时候XGBoost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。传统GBDT在优化时只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

（2）正则化
       xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性。

（3）Shrinkage（缩减）
       相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。

（4）剪枝
       当分裂时遇到一个负损失时，GBM会停止分裂。因此GBM实际上是一个贪心算法。XGBoost会一直分裂到指定的最大深度(max_depth)，然后回过头来剪枝。如果某个节点之后不再有正值，它会去除这个分裂。 这种做法的优点，当一个负损失（如-2）后面有个正损失（如+10）的时候，就显现出来了。GBM会在-2处停下来，因为它遇到了一个负值。但是XGBoost会继续分裂，然后发现这两个分裂综合起来会得到+8，因此会保留这两个分裂。

（5）缺失值处理
       对缺失值的处理。对于特征的值有缺失的样本，XGBoost内置处理缺失值的规则，可以自动学习出它的分裂方向。

（6）并行操作
       XGBoost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。
       我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
       可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。