随机森林 | GBDT | XGBOOST | LightGBM 比较机器学习

目录
各种模型+正则的名称
随机森林 vs GBDT
【随机森林 | GBDT | XGBOOST | LightGBM 比较】XGBOOST vs GBDT
LightGBM vs GBDT
LightGBM vs XGBoost
RF、GBDT、XGBoost
LightGBM
关于直方图算法的解释
特性
类别特征支持
速度和内存使用的优化
稀疏优化
准确率的优化
Leaf-wise (Best-first) 的决策树生长策略

很好的GBDT+XGBoost+LightGBM参考资料：http://free.tianle.me/image/20180109/wepon_gbdt.pdf
各种模型+正则的名称 https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf

文章图片

随机森林 vs GBDT Q：随机森林和GBDT有什么异同？
A: 两者的相同点包括

两者都是基于决策树
两者都能够处理缺失值
两者都能给出特征重要性
两者都是bootstrap的思想

两者的不同点包括

随机森林采用bagging的思想，有放回地均匀抽取训练样本；GBDT采用boosting的思想，根据错误率来采样
GBDT的精度优于随机森林
随机森林可以由分类树或者回归树组成；GBDT由回归树组成
随机森林可以使用并行计算；GBDT使用串行计算
随机森林对所有结果取多数投票或平均；GBDT将每棵树的输出相加
随机森林对异常值不敏感；GBDT对异常值非常敏感
随机森林方差小；GBDT偏差小
随机森林不需要限制树的深度；GBDT需要限制树的深度

XGBOOST vs GBDT Q: xgboost是什么？xgboost和传统GBDT有什么不同？
A: xgboost专门用来训练梯度提升树的模型。xgboost在传统GBDT的基础上进行了一系列改进。xgboost和传统GBDT的区别包括一下：

传统的GBDT以CART回归树作为基学习器(base learner)，xgboost还支持线性分类器
传统的GBDT在优化时只用到了一阶梯度，xgboost用到了二阶梯度
xgboost在损失函数中加入了正则项，即加入叶子个数和叶子输出作为惩罚项
xgboost加入了缩减(shrinkage)，即每次更新fm之前，把叶子结点的输出乘以一个系数η
xgboost支持列抽样：类似随机森林，每次分裂一个树结点时只考虑一部分特征
xgboost在每棵树的每个结点需要选择最优特征时，使用多线程并行地计算各个特征的损失，从而减少了运算时间（为什么能并行计算：因为事先对每个特征进行了预排序）

文章图片

预排序：

文章图片

LightGBM vs GBDT https://zhuanlan.zhihu.com/p/25308051
https://blog.csdn.net/maqunfi/article/details/82219999
1.LightGBM是微软2017年新提出的，比Xgboost更强大、速度更快的模型，性能上有很大的提升，与传统算法相比具有的优点：*更快的训练效率
*低内存使用
*更高的准确率
*支持并行化学习
*可处理大规模数据
*原生支持类别特征，不需要对类别特征再进行0-1编码这类的
2.LightGBM一大的特点是在传统的GBDT基础上引入了两个新技术和一个改进：
（1）Gradient-based One-Side Sampling(GOSS)技术是去掉了很大一部分梯度很小的数据，只使用剩下的去估计信息增益，避免低梯度长尾部分的影响。由于梯度大的数据在计算信息增益的时候更重要，所以GOSS在小很多的数据上仍然可以取得相当准确的估计值。【减少数据量】
（2）Exclusive Feature Bundling(EFB)技术是指捆绑互斥的特征(i.e.，从不同时取非零值)，以减少特征的数量。但对互斥特征寻找最佳的捆绑方式是一个NP难问题，当时贪婪算法可以取得相当好的近似率(因此可以在不显著影响分裂点选择的准确性的情况下，显著地减少特征数量)。【减少特征量】
（3）在传统GBDT算法中，最耗时的步骤是找到最优划分点，传统方法是Pre-Sorted方式，其会在排好序的特征值上枚举所有可能的特征点，而LightGBM中会使用histogram算法替换了传统的Pre-Sorted。基本思想是先把连续的浮点特征值离散化成k个整数，同时构造出图8所示的一个宽度为k的直方图。最开始时将离散化后的值作为索引在直方图中累积统计量，当遍历完一次数据后，直方图累积了离散化需要的统计量，之后进行节点分裂时，可以根据直方图上的离散值，从这k个桶中找到最佳的划分点，从而能更快的找到最优的分割点，而且因为直方图算法无需像Pre-Sorted那样存储预排序的结果，而只是保存特征离散过得数值，所以使用直方图的方式可以减少对内存的消耗。【加速】
Pre-sorted 算法需要 O(data) 次的计算
Histogram 算法只需要计算 O(bins) 次, 并且 bins 远少于data（直方图仍然需要 O(#data) 次来构建直方图, 而这仅仅包含总结操作，只是第一次做data此即可）
LightGBM vs XGBoost

histogram算法替换了传统的Pre-Sorted，某种意义上是牺牲了精度换取速度，直方图作差构建叶子直方图更有创造力（直方图算法的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点[利于计算分割打分]。）
内存做了优化，内存中仅仅需要保存直方图数值，而不是之前的所有数据，另外如果直方图比较小的时候，我们还可以使用保存uint8的形式保存来训练数据。
准确率优化：带有深度限制的按叶子生长 (leaf-wise) 算法代替了传统的(level-wise) 决策树生长策略，提升精度（level-wise会划分出一些没有必要的叶子），同时避免过拟合危险（不太深了）。
额外的优化还有Cache命中率优化、多线程优化。 lightGBM优越性：速度快，代码清晰，占用内存小。lightGBM可以在更小的代价下控制分裂树。有更好的缓存利用，是带有深度限制的按叶子生长的策略，使用了leaf-wise策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后进行分裂，不断的进行循环下去，而lead-wise（智能）算法的缺点是可能生长出比较深的决策树，导致过拟合问题，为了解决过拟合问题，我们会在LightGBM中会对leaf-wise之上增加一个最大深度的限制，在保持高效率的同时防止过拟合。

RF、GBDT、XGBoost 　RF、GBDT和XGBoost都属于集成学习（Ensemble Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性。
根据个体学习器的生成方式，目前的集成学习方法大致分为两大类：即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。
1、RF
1.1 原理
提到随机森林，就不得不提Bagging，Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。
Random Forest（随机森林）是Bagging的扩展变体，它在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：1、随机选择样本（放回抽样）；2、随机选择特征；3、构建决策树；4、随机森林投票（平均）。
随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。
(As a result of this randomness, the bias of the forest usually slightly increases (with respect to the bias of a single non-random tree) but, due to averaging, its variance also decreases, usually more than compensating for the increase in bias, hence yielding an overall better model.)
在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。
RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计，它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每个基学习器只使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。
RF和Bagging对比：RF的起始性能较差，特别当只有一个基学习器时，随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。
1.2 优缺点
随机森林的优点较多，简单总结：1、在数据集上表现良好，相对于其他算法有较大的优势（训练速度、预测准确度）；2、能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性；3、容易做成并行化方法。
RF的缺点：在噪声较大的分类或者回归问题上回过拟合。
2、GBDT
提GBDT之前，谈一下Boosting，Boosting是一种与Bagging很类似的技术。不论是Boosting还是Bagging，所使用的多个分类器类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。
由于Boosting分类的结果是基于所有分类器的加权求和结果的，因此Boosting与Bagging不太一样，Bagging中的分类器权值是一样的，而Boosting中的分类器权重并不相等，每个权重代表对应的分类器在上一轮迭代中的成功度。
2.1 原理
GBDT与传统的Boosting区别较大，它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。
在GradientBoosting算法中，关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。
GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。
2.2 优缺点
GBDT的性能在RF的基础上又有一步提升，因此其优点也很明显，1、它能灵活的处理各种类型的数据；2、在相对较少的调参时间下，预测的准确度较高。
当然由于它是Boosting，因此基学习器之前存在串行关系，难以并行训练数据。
3、XGBoost
3.1 原理
XGBoost的性能在GBDT上又有一步提升，而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算，同时在算法精度上也进行了精度的提高。
由于GBDT在合理的参数设置下，往往要生成一定数量的树才能达到令人满意的准确率，在数据集较复杂时，模型可能需要几千次迭代运算。但是XGBoost利用并行的CPU更好的解决了这个问题。
其实XGBoost和GBDT的差别也较大，这一点也同样体现在其性能表现上，详见XGBoost与GBDT的区别。
4、区别
4.1 GBDT和XGBoost区别
传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）；
传统的GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数；
XGBoost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，放置过拟合，这也是XGBoost优于传统GBDT的一个特性；
shrinkage（缩减），相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）；
列抽样。XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算；
对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动学习出它的分裂方向；
XGBoost工具支持并行。Boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
---------------------
作者：Vico_Men
来源：CSDN
原文：https://blog.csdn.net/qq_28031525/article/details/70207918
版权声明：本文为博主原创文章，转载请附上博文链接！

LightGBM 关于直方图算法的解释 https://blog.csdn.net/jasonwang_/article/details/80833001
特性 http://lightgbm.apachecn.org/cn/latest/Features.html
类别特征支持
LightGBM 可以直接使用 categorical feature（类别特征）（不需要单独编码）。 Expo data 实验显示，与 one-hot 编码相比，其速度提高了 8 倍。
速度和内存使用的优化
许多提升工具对于决策树的学习使用基于 pre-sorted 的算法 [1, 2] (例如，在xgboost中默认的算法) ，这是一个简单的解决方案，但是不易于优化。
LightGBM 利用基于 histogram 的算法 [3, 4, 5]，通过将连续特征（属性）值分段为 discrete bins 来加快训练的速度并减少内存的使用。如下的是基于 histogram 算法的优点：

减少分割增益的计算量
- Pre-sorted 算法需要 O(#data) 次的计算
- Histogram 算法只需要计算 O(#bins) 次, 并且 #bins 远少于 #data
  - 这个仍然需要 O(#data) 次来构建直方图, 而这仅仅包含总结操作
通过直方图的相减来进行进一步的加速
- 在二叉树中可以通过利用叶节点的父节点和相邻节点的直方图的相减来获得该叶节点的直方图
- 所以仅仅需要为一个叶节点建立直方图 (其 #data 小于它的相邻节点)就可以通过直方图的相减来获得相邻节点的直方图，而这花费的代价(O(#bins))很小。
减少内存的使用
- 可以将连续的值替换为 discrete bins。如果 #bins 较小, 可以利用较小的数据类型来存储训练数据, 如 uint8_t。
- 无需为 pre-sorting 特征值存储额外的信息
减少并行学习的通信代价

稀疏优化

对于稀疏的特征仅仅需要 O(2 * #non_zero_data) 来建立直方图

准确率的优化
Leaf-wise (Best-first) 的决策树生长策略
大部分决策树的学习算法通过 level(depth)-wise 策略生长树，如下图一样：

文章图片

LightGBM 通过 leaf-wise (best-first)[6] 策略来生长树。它将选取具有最大 delta loss 的叶节点来生长。当生长相同的 #leaf，leaf-wise 算法可以比 level-wise 算法减少更多的损失。
当 #data 较小的时候，leaf-wise 可能会造成过拟合。所以，LightGBM 可以利用额外的参数 max_depth 来限制树的深度并避免过拟合（树的生长仍然通过 leaf-wise 策略）。