转载：https://www.cnblogs.com/fisherinbox/p/6519910.html

一。机器学习算法中GBDT和XGBOOST的区别有哪些？（转自知乎https://www.zhihu.com/question/41354392/answer/98658997）

xgboost相比传统gbdt有何不同？xgboost为什么快？xgboost如何支持并行？

- 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
- 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
- xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
- Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
- 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

- 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
- xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点

二、xgboost参数详解

General Parameters（常规参数）
1.booster [default=gbtree]：选择基分类器，gbtree: tree-based models/gblinear: linear models
2.silent [default=0]:设置成1则没有运行信息输出，最好是设置为0.
3.nthread [default to maximum number of threads available if not set]：线程数

Booster Parameters（模型参数）
1.eta [default=0.3]:shrinkage参数，用于更新叶子节点权重时，乘以该系数，避免步长过大。参数值越大，越可能无法收敛。把学习率 eta 设置的小一些，小学习率可以使得后面的学习更加仔细。
2.min_child_weight [default=1]:这个参数默认是 1，是每个叶子里面 h 的和至少是多少，对正负样本不均衡时的 0-1 分类而言，假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。这个参数非常影响结果，控制叶子节点中二阶导的和的最小值，该参数值越小，越容易 overfitting。
3.max_depth [default=6]: 每颗树的最大深度，树高越深，越容易过拟合。
4.max_leaf_nodes:最大叶结点数，与max_depth作用有点重合。
5.gamma [default=0]：后剪枝时，用于控制是否后剪枝的参数。
6.max_delta_step [default=0]：这个参数在更新步骤中起作用，如果取0表示没有约束，如果取正值则使得更新步骤更加保守。可以防止做太大的更新步子，使更新更加平缓。
7.subsample [default=1]：样本随机采样，较低的值使得算法更加保守，防止过拟合，但是太小的值也会造成欠拟合。
8.colsample_bytree [default=1]：列采样，对每棵树的生成用的特征进行列采样.一般设置为： 0.5-1
9.lambda [default=1]：控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。
10.alpha [default=0]:控制模型复杂程度的权重值的 L1 正则项参数，参数值越大，模型越不容易过拟合。
11.scale_pos_weight [default=1]：如果取值大于0的话，在类别样本不平衡的情况下有助于快速收敛。

Learning Task Parameters（学习任务参数）
1.objective [default=reg:linear]：定义最小化损失函数类型，常用参数：
binary:logistic –logistic regression for binary classification, returns predicted probability (not class)
multi:softmax –multiclass classification using the softmax objective, returns predicted class (not probabilities)
you also need to set an additional num_class (number of classes) parameter defining the number of unique classes
multi:softprob –same as softmax, but returns predicted probability of each data point belonging to each class.
2.eval_metric [ default according to objective ]：
The metric to be used for validation data.
The default values are rmse for regression and error for classification.
Typical values are:
rmse – root mean square error
mae – mean absolute error
logloss – negative log-likelihood
error – Binary classification error rate (0.5 threshold)
merror – Multiclass classification error rate
mlogloss – Multiclass logloss
auc: Area under the curve
3.seed [default=0]：
The random number seed. 随机种子，用于产生可复现的结果
Can be used for generating reproducible results and also for parameter tuning.

注意: python sklearn style参数名会有所变化
eta –> learning_rate
lambda –> reg_lambda
alpha –> reg_alpha

三。推导过程

1.以下内容转自http://www.52cs.org/?p=429，陈天奇大牛的解释。

2. Boosted Tree的若干同义词
说到这里可能有人会问，为什么我没有听过这个名字。这是因为Boosted Tree有各种马甲，比如GBDT, GBRT (gradient boosted regression tree)，MART11，LambdaMART也是一种boosted tree的变种。网上有很多介绍Boosted tree的资料，不过大部分都是基于Friedman的最早一篇文章Greedy Function Approximation: A Gradient Boosting Machine的翻译。个人觉得这不是最好最一般地介绍boosted tree的方式。而网上除了这个角度之外的介绍并不多。这篇文章是我个人对于boosted tree和gradient boosting 类算法的总结，其中很多材料来自于我TA UW机器学习时的一份讲义22。

3. 有监督学习算法的逻辑组成
要讲boosted tree，要先从有监督学习讲起。在有监督学习里面有几个逻辑上的重要组成部件33，初略地分可以分为：模型，参数和目标函数。

i. 模型和参数
模型指给定输入xixi如何去预测输出 yiyi。我们比较常见的模型如线性模型（包括线性回归和logistic regression）采用了线性叠加的方式进行预测y^i=∑jwjxijy^i=∑jwjxij 。其实这里的预测yy可以有不同的解释，比如我们可以用它来作为回归目标的输出，或者进行sigmoid 变换得到概率，或者作为排序的指标等。而一个线性模型根据yy的解释不同（以及设计对应的目标函数）用到回归，分类或排序等场景。参数指我们需要学习的东西，在线性模型中，参数指我们的线性系数ww。

ii. 目标函数：损失 + 正则
模型和参数本身指定了给定输入我们如何做预测，但是没有告诉我们如何去寻找一个比较好的参数，这个时候就需要目标函数登场了。一般的目标函数包含下面两项

常见的误差函数有L=∑nil(yi,y^i)L=∑inl(yi,y^i) 比如平方误差 l(yi,y^i)=(yi−y^i)2l(yi,y^i)=(yi−y^i)2 ，logistic误差函数（l(yi,y^i)=yiln(1+e−y^i)+(1−yi)ln(1+ey^i)l(yi,y^i)=yiln⁡(1+e−y^i)+(1−yi)ln⁡(1+ey^i) ）等。而对于线性模型常见的正则化项有L2L2正则和L1L1正则。这样目标函数的设计来自于统计学习里面的一个重要概念叫做Bias-variance tradeoff44。比较感性的理解，Bias可以理解为假设我们有无限多数据的时候，可以训练出最好的模型所拿到的误差。而Variance是因为我们只有有限数据，其中随机性带来的误差。目标中误差函数鼓励我们的模型尽量去拟合训练数据，这样相对来说最后的模型会有比较少的 bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

iii. 优化算法
讲了这么多有监督学习的基本概念，为什么要讲这些呢？是因为这几部分包含了机器学习的主要成分，也是机器学习工具设计中划分模块比较有效的办法。其实这几部分之外，还有一个优化算法，就是给定目标函数之后怎么学的问题。之所以我没有讲优化算法，是因为这是大家往往比较熟悉的“机器学习的部分”。而有时候我们往往只知道“优化算法”，而没有仔细考虑目标函数的设计的问题，比较常见的例子如决策树的学习，大家知道的算法是每一步去优化gini entropy，然后剪枝，但是没有考虑到后面的目标是什么。

4. Boosted Tree
i. 基学习器：分类和回归树（CART）
话题回到boosted tree，我们也是从这几个方面开始讲，首先讲模型。Boosted tree 最基本的组成部分叫做回归树(regression tree)，也叫做CART55。

上面就是一个CART的例子。CART会把输入根据输入的属性分配到各个叶子节点，而每个叶子节点上面都会对应一个实数分数。上面的例子是一个预测一个人是否会喜欢电脑游戏的 CART，你可以把叶子的分数理解为有多可能这个人喜欢电脑游戏。有人可能会问它和decision tree的关系，其实我们可以简单地把它理解为decision tree的一个扩展。从简单的类标到分数之后，我们可以做很多事情，如概率预测，排序。

ii. Tree Ensemble
一个CART往往过于简单无法有效地预测，因此一个更加强力的模型叫做tree ensemble。

在上面的例子中，我们用两棵树来进行预测。我们对于每个样本的预测结果就是每棵树预测分数的和。到这里，我们的模型就介绍完毕了。现在问题来了，我们常见的随机森林和boosted tree和tree ensemble有什么关系呢？如果你仔细的思考，你会发现RF和boosted tree的模型都是tree ensemble，只是构造（学习）模型参数的方法不同。第二个问题：在这个模型中的“参数”是什么。在tree ensemble中，参数对应了树的结构，以及每个叶子节点上面的预测分数。

最后一个问题当然是如何学习这些参数。在这一部分，答案可能千奇百怪，但是最标准的答案始终是一个：定义合理的目标函数，然后去尝试优化这个目标函数。在这里我要多说一句，因为决策树学习往往充满了heuristic。如先优化吉尼系数，然后再剪枝啦，限制最大深度，等等。其实这些heuristic的背后往往隐含了一个目标函数，而理解目标函数本身也有利于我们设计学习算法，这个会在后面具体展开。
对于tree ensemble，我们可以比较严格的把我们的模型写成是：

y^i=∑Kk=1fk(xi),fk∈Fy^i=∑k=1Kfk(xi),fk∈F

其中每个ff是一个在函数空间66(FF)里面的函数，而FF对应了所有regression tree的集合。我们设计的目标函数也需要遵循前面的主要原则，包含两部分

Obj(Θ)=∑nil(yi,y^i)+∑Kk=1Ω(fk)Obj(Θ)=∑inl(yi,y^i)+∑k=1KΩ(fk)

iii. 模型学习：additive training
其中第一部分是训练误差，也就是大家相对比较熟悉的如平方误差, logistic loss等。而第二部分是每棵树的复杂度的和。这个在后面会继续讲到。因为现在我们的参数可以认为是在一个函数空间里面，我们不能采用传统的如SGD之类的算法来学习我们的模型，因此我们会采用一种叫做additive training的方式（另外，在我个人的理解里面77，boosting就是指additive training的意思）。每一次保留原来的模型不变，加入一个新的函数$f$到我们的模型中。

现在还剩下一个问题，我们如何选择每一轮加入什么ff呢？答案是非常直接的，选取一个ff来使得我们的目标函数尽量最大地降低88。

这个公式可能有些过于抽象，我们可以考虑当ll是平方误差的情况。这个时候我们的目标可以被写成下面这样的二次函数99：

更加一般的，对于不是平方误差的情况，我们会采用如下的泰勒展开近似来定义一个近似的目标函数，方便我们进行这一步的计算。

当我们把常数项移除之后，我们会发现如下一个比较统一的目标函数。这一个目标函数有一个非常明显的特点，它只依赖于每个数据点的在误差函数上的一阶导数和二阶导数1010。有人可能会问，这个材料似乎比我们之前学过的决策树学习难懂。为什么要花这么多力气来做推导呢？

因为这样做使得我们可以很清楚地理解整个目标是什么，并且一步一步推导出如何进行树的学习。这一个抽象的形式对于实现机器学习工具也是非常有帮助的。传统的GBDT可能大家可以理解如优化平法aa残差，但是这样一个形式包含可所有可以求导的目标函数。也就是说有了这个形式，我们写出来的代码可以用来求解包括回归，分类和排序的各种问题，正式的推导可以使得机器学习的工具更加一般。

iv. 树的复杂度
到目前为止我们讨论了目标函数中训练误差的部分。接下来我们讨论如何定义树的复杂度。我们先对于f的定义做一下细化，把树拆分成结构部分qq和叶子权重部分ww。下图是一个具体的例子。结构函数qq把输入映射到叶子的索引号上面去，而ww给定了每个索引号对应的叶子分数是什么。

当我们给定了如上定义之后，我们可以定义一棵树的复杂度如下。这个复杂度包含了一棵树里面节点的个数，以及每个树叶子节点上面输出分数的$L2$模平方。当然这不是唯一的一种定义方式，不过这一定义方式学习出的树效果一般都比较不错。下图还给出了复杂度计算的一个例子。

v. 关键步骤
接下来是最关键的一步1111，在这种新的定义下，我们可以把目标函数进行如下改写，其中I被定义为每个叶子上面样本集合 IjIj = { i|q(xi)=ji|q(xi)=j}

这一个目标包含了TT个相互独立的单变量二次函数。我们可以定义

Gj=∑i∈IjgiHj=∑i∈IjhiGj=∑i∈IjgiHj=∑i∈Ijhi

那么这个目标函数可以进一步改写成如下的形式，假设我们已经知道树的结构qq，我们可以通过这个目标函数来求解出最好的ww，以及最好的ww对应的目标函数最大的增益

Obj(t)=∑Tj=1[(∑i∈Ijgi)wj+12(∑i∈Ijhi+λ)w2j]+γT=∑Tj=1[Gjwj+12(Hj+λ)w2j]+γTObj(t)=∑j=1T[(∑i∈Ijgi)wj+12(∑i∈Ijhi+λ)wj2]+γT=∑j=1T[Gjwj+12(Hj+λ)wj2]+γT

这两个的结果对应如下，左边是最好的ww，右边是这个ww对应的目标函数的值。到这里大家可能会觉得这个推导略复杂。其实这里只涉及到了如何求一个一维二次函数的最小值的问题1212。如果觉得没有理解不妨再仔细琢磨一下

w∗j=−GjHj+λObj=−12∑Tj=1G2jHj+λ+γTwj∗=−GjHj+λObj=−12∑j=1TGj2Hj+λ+γT

vi. 打分函数计算举例
Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)。你可以认为这个就是类似吉尼系数一样更加一般的对于树结构进行打分的函数。下面是一个具体的打分函数计算的例子

vii. 枚举所有不同树结构的贪心法
所以我们的算法也很简单，我们不断地枚举不同树的结构，利用这个打分函数来寻找出一个最优结构的树，加入到我们的模型中，再重复这样的操作。不过枚举所有树结构这个操作不太可行，所以常用的方法是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算

对于每次扩展，我们还是要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？我假设我们要枚举所有 x<ax<a 这样的条件，对于某个特定的分割aa我们要计算aa左边和右边的导数和。

我们可以发现对于所有的aa，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GLGL和GRGR。然后用上面的公式计算每个分割方案的分数就可以了。

观察这个目标函数，大家会发现第二个值得注意的事情就是引入分割不一定会使得情况变好，因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝，当引入的分割带来的增益小于一个阀值的时候，我们可以剪掉这个分割。大家可以发现，当我们正式地推导目标的时候，像计算分数和剪枝这样的策略都会自然地出现，而不再是一种因为heuristic而进行的操作了。

讲到这里文章进入了尾声，虽然有些长，希望对大家有所帮助，这篇文章介绍了如何通过目标函数优化的方法比较严格地推导出boosted tree的学习。因为有这样一般的推导，得到的算法可以直接应用到回归，分类排序等各个应用场景中去。

寻找分裂结点的候选集
1、暴力枚举

2、近似方法，近似方法通过特征的分布，按照百分比确定一组候选分裂点，通过遍历所有的候选分裂点来找到最佳分裂点。
两种策略：全局策略和局部策略。在全局策略中，对每一个特征确定一个全局的候选分裂点集合，就不再改变；而在局部策略中，每一次分裂都要重选一次分裂点。前者需要较大的分裂集合，后者可以小一点。对比补充候选集策略与分裂点数目对模型的影响。全局策略需要更细的分裂点才能和局部策略差不多

3、Weighted Quantile Sketch

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

近似算法的主要思想就是将每个特征的值划分范围，而不是暴力枚举，在划分的时候是通过特征值分布密度的面积来划分的，通过构建直方图来计算面试，尽量使得划分之后的每个部分面积差不多。

------------------------------------------------------------------

参考文章二：机器学习（四）--- 从gbdt到xgboost

gbdt（又称Gradient Boosted Decision Tree/Grdient Boosted Regression Tree），是一种迭代的决策树算法，该算法由多个决策树组成。它最早见于yahoo，后被广泛应用在搜索排序、点击率预估上。

xgboost是陈天奇大牛新开发的Boosting库。它是一个大规模、分布式的通用Gradient Boosting（GBDT）库，它在Gradient Boosting框架下实现了GBDT和一些广义的线性机器学习算法。

本文首先讲解了gbdt的原理，分析了代码实现；随后分析了xgboost的原理和实现逻辑。本文的目录如下：

一、GBDT

1. GBDT简介

2. GBDT公式推导

3. 优缺点

4. 实现分析

5. 常用参数和调优

二、Xgboost

1. Xgboost简介

2. Xgboost公式推导

3. 优缺点

4. 实现分析

5. 常用参数和调优

一、GBDT/GBRT

1. GBDT简介

GBDT是一个基于迭代累加的决策树算法，它通过构造一组弱的学习器（树），并把多颗决策树的结果累加起来作为最终的预测输出。

树模型也分为决策树和回归树，决策树常用来分类问题，回归树常用来预测问题。决策树常用于分类标签值，比如用户性别、网页是否是垃圾页面、用户是不是作弊；而回归树常用于预测真实数值，比如用户的年龄、用户点击的概率、网页相关程度等等。由于GBDT的核心在与累加所有树的结果作为最终结果，而分类结果对于预测分类并不是这么的容易叠加（稍等后面会看到，其实并不是简单的叠加，而是每一步每一棵树拟合的残差和选择分裂点评价方式都是经过公式推导得到的），所以GBDT中的树都是回归树（其实回归树也能用来做分类的哈）。同样的我们经常会把RandomForest的思想引入到GBDT里面来，即每棵树建树的时候我们会对特征和样本同时进行采样，然后对采样的样本和特征进行建树。

好啦，既然每棵树拟合的值、预测值、分裂点选取都不是随便选取的，那么到底是如何选择的呢？我们先进入GBDT的公式推导吧

2. GBDT公式推导

我们都知道LR的映射函数是机器学习算法中GBDT和XGBOOST的区别有哪些----重点，损失函数是。对于分类问题来说，我们一般选取映射函数，构造损失函数，然后逐步求解使得损失函数最小化就行了，可是对于回归问题，求解的方式就有些不同了。那么GBDT的目标函数和损失函数分别又是什么的呢？每个树拟合的残差是什么呢？首先GBDT和LR是不一样的，因为GBDT是希望组合一组弱的学习器的线性组合，于是我们有：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

那么它的目标函数就如下，其中如上公式中是p步长，而h(x;am)是第m颗树的预测值---梯度方向。我们可以在函数空间上形式使用梯度下降法求解，首先固定x，对F(x)求其最优解。下面给出框架流程和Logloss下的推导，框架流程如下：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

我们需要估计g_m(x)，这里使用决策树实现去逼近g_m(x)，使得两者之间的距离尽可能的近。而距离的衡量方式有很多种，比如均方误差和Logloss误差。我在这里给出Logloss损失函数下的具体推导：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点（GBDT预测值到输出概率[0,1]的sigmoid转换）

下面，我们需要首先求解F0，然后再求解每个梯度。

Step 1. 首先求解初始值F0，令其偏导为0。（实现时是第1颗树需要拟合的残差）

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

Step2. 估计g_m(x)，并用决策树对其进行拟合。g_m(x)是梯度，实现时是第m颗树需要拟合的残差：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

Step3. 使用牛顿法求解下降方向步长。r_jm是拟合的步长，实现时是每棵树的预测值：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

Step4. 预测时就很简单啦，把每棵树的预测值乘以缩放因子加到一起就得到预测值啦：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

注意如果需要输出的区间在(0,1)之间，我们还需要做如下转换：

机器学习算法中GBDT和XGBOOST的区别有哪些----重点

3. 优缺点

GBDT的优点当然很明显啦，它的非线性变换比较多，表达能力强，而且不需要做复杂的特征工程和特征变换。

GBDT的缺点也很明显，Boost是一个串行过程，不好并行化，而且计算复杂度高，同时不太适合高维洗漱特征。

4. 实现分析

5. 参数和模型调优

GBDT常用的参数有如下几个：

1. 树个数
2. 树深度
3. 缩放因子
4. 损失函数
5. 数据采样比
6. 特征采样比

二、Xgboost

xgboost是boosting Tree的一个很牛的实现，它在最近Kaggle比赛中大放异彩。它有以下几个优良的特性：

1. 显示的把树模型复杂度作为正则项加到优化目标中。

2. 公式推导中用到了二阶导数，用了二阶泰勒展开。（GBDT用牛顿法貌似也是二阶信息）

3. 实现了分裂点寻找近似算法。

4. 利用了特征的稀疏性。

5. 数据事先排序并且以block形式存储，有利于并行计算。

6. 基于分布式通信框架rabit，可以运行在MPI和yarn上。（最新已经不基于rabit了）

7. 实现做了面向体系结构的优化，针对cache和内存做了性能优化。

在项目实测中使用发现，Xgboost的训练速度要远远快于传统的GBDT实现，10倍量级。

1. 原理

在有监督学习中，我们通常会构造一个目标函数和一个预测函数，使用训练样本对目标函数最小化学习到相关的参数，然后用预测函数和训练样本得到的参数来对未知的样本进行分类的标注或者数值的预测。一般目标函数是如下形式的，我们通过对目标函数最小化，求解模型参数机器学习算法中GBDT和XGBOOST的区别有哪些----重点。预测函数、损失函数、正则化因子在不同模型下是各不相同的。