一、bagging和boosting的区别

参考：https://www.cnblogs.com/liuwu265/p/4690486.html

Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。

首先介绍Bootstraping，即自助法：它是一种有放回的抽样方法（可能抽到重复的样本）。

1、Bagging (bootstrap aggregating)

Bagging即套袋法，其算法过程如下：

A）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）

B）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

C）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

2、Boosting

其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题：

1）在每一轮如何改变训练数据的权值或概率分布？

通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。

2）通过什么方式来组合弱分类器？

通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。

而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

3、Bagging，Boosting二者之间的区别

Bagging和Boosting的区别：

1）样本选择上：

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

4、总结

这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

1）Bagging + 决策树 = 随机森林

2）AdaBoost + 决策树 = 提升树

3）Gradient Boosting + 决策树 = GBDT

5，常用模型

 bagging：随机森林

boosting：Adaboost、GBDT、XGBoost

6，随机森林和GBDT的区别：

训练集选取：随机森林采用的Bagging思想，而GBDT采用的Boosting思想。这两种方法都是Bootstrap思想的应用，Bootstrap是一种有放回的抽样方法思想。虽然都是有放回的抽样，但二者的区别在于：Bagging采用有放回的均匀取样，而Boosting根据错误率来取样（Boosting初始化时对每一个训练样例赋相等的权重1／n，然后用该算法对训练集训练t轮，每次训练后，对训练失败的样例赋以较大的权重），因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各训练集之间相互独立，弱分类器可并行，而Boosting的训练集的选择与前一轮的学习结果有关，是串行的；决策树类型：组成随机森林的树可以是分类树，也可以是回归树；而GBDT只能由回归树组成；结果预测：对于最终的输出结果而言，随机森林采用多数投票、简单平均等；而GBDT则是将所有结果累加起来，或者加权累加起来；并行/串行：组成随机森林的树可以并行生成；而GBDT只能是串行生成；异常值：随机森林对异常值不敏感；GBDT对异常值非常敏感；方差/偏差：随机森林是通过减少模型方差提高性能；GBDT是通过减少模型偏差提高性能。7，GBDT 与 XGBOOST的比较：

1.传统的GBDT以CART树作为基分类器，而XGBOOST还支持线性分类器，此时的线性分类器自带正则项

2.传统的GBDT在优化时，只用到了loss function的一阶导信息，而XGBOOST对loss function做了Taylor展开，用到了二阶导信息

3.XGBOOST在loss function中引入了正则项，防止过拟合，正则项里包含叶节点数以及每个叶节点上的score的L2的平方和

在计算划分增益时，如果gain < gamma, 不划分，gain> gamma，划分，这相当于决策树的预剪枝。 gamma是叶节点个数的参数

4.XGBOOST还借用了RandomForest中的列抽样思想，也支持在划分节点时，只考虑部分属性

（现状sklearn中的GBDT也实现了列抽样）

5.XGBOOST可以自动学习出缺失值的分裂方向，论文中的default direction

（具体做法时，遍历的尝试将所有的缺失值分裂到所有方向{left or right}，split and default directions with max gain）

6.XGBOOST实现了并行化，这个并行化是特征粒度上的并行化：划分节点时，每个特征并行计算，同时每个特征的划分节点也是并行计算（这是加速最猛的处理）

7.XGBOOST提出了block的概念，简单的说将排序后的特征值放在block中，以后划分特征的时候，只需要遍历一次即可，因为决策树在处理属性值时，需要将属性值先排序，这是最耗时的步骤，而block预先存储了排序的特征值，在后续过程中可以重复利用这个结构中的数据，同时，计算每个特征的划分增益可以并行处理了

Collecting statistics for each column can be parallelized,giving us a parallel algorithm for split finding!!

8.贪心算法在选择最佳划分方式时需要遍历所有的划分点子集，在数据非常大时，这会非常低效，xgboost提出了近似直方图计算，根据数据的二阶导信息进行排序，提出一些候选划分点子集

8，xgboost为什么快？xgboost如何支持并行？