基于Histogram的决策树算法, 更快的训练速度和更高的效率：LightGBM使用基于直方图的算法。例如，它将连续的特征值分桶(buckets)装进离散的箱子(bins)，这是的训练过程中变得更快。
带深度限制的Leaf-wise的叶子生长策略, LightGBM的分裂节点的方式与XGBoost不一样。LGB避免了对整层节点分裂法，而采用了对增益最大的节点进行深入分解的方法。这样节省了大量分裂节点的资源。
更低的内存占用：使用离散的箱子(bins)保存并替换连续值导致更少的内存占用。
更高的准确率(相比于其他任何提升算法)：它通过leaf-wise分裂方法产生比level-wise分裂方法更复杂的树，这就是实现更高准确率的主要因素。然而，它有时候或导致过拟合，但是我们可以通过设置 max-depth 参数来防止过拟合的发生。
大数据处理能力：相比于XGBoost，由于它在训练时间上的缩减，它同样能够具有处理大数据的能力。
支持并行学习
Cache命中率优化
基于直方图的稀疏特征优化

Histogram算法:直方图加速算法。
GOSS算法:基于梯度的单边采样算法。
EFB算法:互斥特征捆绑算法。

可以用如下一个简单公式来说明LightGBM和XGBoost的关系：

LightGBM = XGBoost + Histogram + GOSS + EFB

XGBoost模型训练的总体的复杂度可以粗略估计为：

训练复杂度 = 树的棵数✖️每棵树上叶子的数量✖️生成每片叶子的复杂度

由于XGBoost采用的基模型是二叉树，因此生成每片叶子需要分裂一次。

而每次分裂，需要遍历所有特征上所有候选分裂点位，计算按照这些候选分裂点位分裂后的全部样本的目标函数增益，找到最大的那个增益对应的特征和候选分裂点位，从而生成一片新叶子。因此生成一片叶子的复杂度可以粗略估计为：

生成一片叶子的复杂度 = 特征数量✖️候选分裂点位数量✖️样本的数量。

而Hitogram算法的作用是减少候选分裂点位数量，GOSS算法的作用是减少样本的数量，EFB算法的作用是减少特征的数量。

通过这3个算法的引入，LightGBM生成一片叶子需要的复杂度大大降低了，从而极大节约了计算时间。

同时Histogram算法还将特征由浮点数转换成0~255位的整数进行存储，从而极大节约了内存存储。

二 Histogram算法

直方图算法的基本思想：先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。遍历数据时，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

LightGBM里默认的训练决策树时使用直方图算法(直方图算法是替代XGBoost的预排序(pre-sorted)算法的)，XGBoost里现在也提供了这一选项，不过默认的方法是对特征预排序，计算过程当中是按照value的排序，逐个数据样本来计算划分收益，这样的算法能够精确的找到最佳划分值，但是代价比较大同时也没有较好的推广性。

预排序算法首先将样本按照特征取值排序，然后从全部特征取值中找到最优的分裂点位，该算法的候选分裂点数量与样本数量成正比。

而直方图算法通过将连续特征值离散化到固定数量(如255个)的bins上，使得候选分为点位为常数个(num_bins -1)

a. 降低计算分裂增益的成本

基于预排序的算法具有时间复杂性 O(#
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/273388