[机器学习 ]RandomForest、GBDT、XGBoost、lightGBM 原理与区别 - 好文

RF,GBDT,XGBoost,lightGBM都属于集成学习（Ensemble
Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善基本学习器的泛化能力和鲁棒性。

根据基本学习器的生成方式，目前的集成学习方法大致分为两大类：即基本学习器之间存在强依赖关系、必须串行生成的序列化方法，以及基本学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random
Forest）

这篇文章主要对集成学习中重要的、使用广泛的方法进行对比：

RF（随机森林））, GBDT（梯度提升决策树）, XGBoost, lightGBM

随机森林 -- RandomForest


提到随机森林，就不得不提Bagging，Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。
　　Random Forest（随机森林）是Bagging的扩展变体，它在以决策树
为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：1、随机选择样本（放回抽样）；2、随机选择特征属性；3、构建决策树；4、随机森林投票（平均）
因此防止过拟合能力更强，降低方差。

RF和Bagging对比：
RF的起始性能较差，特别当只有一个基学习器时，随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，
因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，
在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。

使用的融合方法：bagging

* 一种集成学习算法，基于bootstrap sampling 自助采样法，重复性有放回的随机采用部分样本进行训练最后再将结果 voting 或者
averaging 。
* 它是并行式算法，因为不同基学习器是独立
* 训练一个bagging集成学习器时间复杂度与基学习器同阶（n倍，n为基学习器个数）。
* bagging可以用于二分类／多分类／回归
* 每个基学习器的未用作训练样本可用来做包外估计，评价泛化性能。
* bagging主要关注降低方差。
* 两个步骤 1. 抽样训练（采样样本，采样特征） 2 融合
随机森林的优缺点

优点：

a）随机森林算法能解决分类与回归两种类型的问题，表现良好，由于是集成学习，方差和偏差都比较低，泛化性能优越；

b）随机森林对于高维数据集的处理能力很好，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。此外，该模型能够输出特征的重要性程度，这是一个非常实用的功能。
c) 可以应对缺失数据；
d）当存在分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法；
e ) 高度并行化，易于分布式实现
f) 由于是树模型，不需要归一化即可之间使用

缺点：

a）随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
b）对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。
c) 忽略属性之间的相关性

d)在噪声较大的分类或者回归问题上容易过拟合。

GBDT (Gradient Boosting Decision Tree)


提GBDT之前，谈一下Boosting，Boosting是一种与Bagging很类似的技术。不论是Boosting还是Bagging，所使用的多个分类器类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。

　　由于Boosting分类的结果是基于所有分类器的加权求和结果的，因此Boosting与Bagging不太一样，Bagging中的分类器权值是一样的，而Boosting中的分类器权重并不相等，每个权重代表对应的分类器在上一轮迭代中的成功度。

原理

　GBDT的基本原理是boost 里面的 boosting tree（提升树），并使用 gradient boost。

　GBDT与传统的Boosting区别较大，它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。
　在GradientBoosting算法中，关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。

　GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。因为
Gradient Boosting 需要按照损失函数的梯度近似的拟合残差，这样拟合的是连续数值，因此只有回归树。

梯度提升 Gradient Boosting:

    Gradient
Boosting是一种Boosting的方法，其与传统的Boosting的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，
在Gradient Boosting中，每个新的模型的建立是为了使得之前模型的残差往梯度方向减少
，与传统Boosting对正确、错误样本进行加权有着很大的区别。这个梯度代表上一轮学习器损失函数对预测值求导。

    与Boosting Tree的区别：Boosting Tree的适合于损失函数为平方损失或者指数损失。而Gradient
Boosting适合各类损失函数（损失函数为：平方损失则相当于Boosting
Tree拟合残差、损失函数为：使用指数损失则可以近似于Adaboost，但树是回归树）


优缺点
　　优点：GBDT的性能在RF的基础上又有一步提升，因此其优点也很明显，1、它能灵活的处理各种类型的数据；2、在相对较少的调参时间下，预测的准确度较高。
　　缺点：当然由于它是Boosting，因此基学习器之前存在串行关系，难以并行训练数据。

XGBoost

原理

      XGBoost的原理详细，推荐两篇大神博客， xgboost原理
<http://blog.csdn.net/a819825294/article/details/51206410> ，xgboost 算法原理
<http://blog.csdn.net/a1b2c3d4123456/article/details/52849091>。


XGBoost是集成学习Boosting家族的成员，是在GBDT的基础上对boosting算法进行的改进。GBDT是用模型在数据上的负梯度作为残差的近似值，从而拟合残差。XGBoost也是拟合的在数据上的残差，但是它
是用泰勒展式对模型损失残差的近似；同时XGBoost对模型的损失函数进行的改进，并加入了模型复杂度的正则项。

　　XGBoost的性能在GBDT上又有一步提升，而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算，同时在算法精度上也进行了精度的提高。由于GBDT在合理的参数设置下，往往要生成一定数量的树才能达到令人满意的准确率，在数据集较复杂时，模型可能需要几千次迭代运算。但是XGBoost利用并行的CPU更好的解决了这个问题。

XGBoost与GBDT的区别：在了解了XGBoost原理后容易理解二者的不同
损失函数的改变：（导数和正则项的认识）

*
传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）；
* 传统的GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数；
* XGBoost在代价函数中加入了正则项
，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，放置过拟合，这也是XGBoost优于传统GBDT的一个特性；
工具的优化：（趋势值和并行的认识）

　　1、shrinkage（缩减），相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）；
　　2、列抽样。XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算；
　　3、对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动学习出它的分裂方向；
　 4   XGBoost工具支持并行。Boosting不是一种串行的结构吗?怎么并行
的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代
中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

缺点
　　1、level-wise 建树方式对当前层的所有叶子节点一视同仁，有些叶子节点分裂收益非常小，对结果没影响，但还是要分裂，加重了计算代价。

　　2、预排序方法空间消耗比较大，不仅要保存特征值，也要保存特征的排序索引，同时时间消耗也大，在遍历每个分裂点时都要计算分裂增益(不过这个缺点可以被近似算法所克服)

lightGBM

它是微软出的新的boosting框架，基本原理与XGBoost一样，只是在框架上做了一优化（重点在模型的训练速度的优化）。
关于lightGBM的介绍参考：比XGBOOST更快–LightGBM介绍 <https://www.jianshu.com/p/48e82dbb142b>

与XGboost对比

　　1、xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了务必要的开销。
leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
　　2、lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact
算法，histogram算法在内存和计算代价上都有不小优势。
　　（1）内存上优势：很明显，直方图算法的内存消耗为(#data* #features *
1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features*
4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。

　　（2）计算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)
　　3、直方图做差加速
一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。
　　4、lightgbm支持直接输入categorical 的feature
在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。
　　5、多线程优化

       6 lightgbm哪些方面做了并行？
-. feature parallel
一般的feature parallel就是对数据做垂直分割（partiion data
vertically，就是对属性分割），然后将分割后的数据分散到各个worker上，各个workers计算其拥有的数据的best splits point,
之后再汇总得到全局最优分割点。但是lightgbm说这种方法通讯开销比较大，lightgbm的做法是每个worker都拥有所有数据，再分割？（没懂，既然每个worker都有所有数据了，再汇总有什么意义？这个并行体现在哪里？？）
-. data parallel
传统的data parallel是将对数据集进行划分，也叫平行分割(partion data horizontally)，
分散到各个workers上之后，workers对得到的数据做直方图，汇总各个workers的直方图得到全局的直方图。
lightgbm也claim这个操作的通讯开销较大，lightgbm的做法是使用”Reduce
Scatter“机制，不汇总所有直方图，只汇总不同worker的不同feature的直方图(原理？)，在这个汇总的直方图上做split，最后同步。

热门工具换一换