灵宝超市建设管理局信访网站,百度推广网页版,网站开发交接表,wordpress 移动域名文章最前#xff1a; 我是Octopus#xff0c;这个名字来源于我的中文名--章鱼#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github #xff1b;这博客是记录我学习的点点滴滴#xff0c;如果您对 Python、Java、AI、算法有兴趣#xff0c;可以关注我的… 文章最前 我是Octopus这个名字来源于我的中文名--章鱼我热爱编程、热爱算法、热爱开源。所有源码在我的个人github 这博客是记录我学习的点点滴滴如果您对 Python、Java、AI、算法有兴趣可以关注我的动态一起学习共同进步。 目录
1. 基于梯度的单侧采样GOSS
2. 基于直方图的树节点分裂
3. 分类特征的最优分割
4. 独家功能捆绑
5. Leaf-wise 树生长策略
6. 并行优化
7.总结 LightGBM是微软于2016年开发的梯度提升决策树模型GBDT与其他GBDT模型相比LightGBM的最大特点是训练效率更快、准确率更高。 LightGBM 与一般的 Gradient Boosting Decision Tree 模型在结构上没有根本的区别但通过以下特殊技术LightGBM 使其训练速度更快。
基于梯度的一侧采样GOSS树节点分裂中基于直方图的最佳值搜索分类特征的最佳分割独家功能捆绑叶向树生长策略并行优化
1. 基于梯度的单侧采样GOSS 经典的基于树的梯度提升GBDT训练是一个重复过程用于训练新树以适应所有训练集实例上先前树集的预测误差。预测误差是所有训练集实例上的损失函数梯度
因此默认情况下GBDT 使用所有训练集实例来训练其集合中的每棵树。 针对这一点LightGBM引入了GOSS其中我们只需要使用部分训练集来训练每个集成树。GOSS 的直觉是
具有大梯度的训练实例意味着该实例具有较大的当前预测误差并且应该是适合下一个集成树的主要目标小梯度的训练实例意味着该实例当前的预测误差相对较小不需要下一个集成树过多担心因此我们可以以某种概率丢弃它。 一般来说GOSS的主要思想是在训练下一个集成树之前我们保留梯度较大的训练实例并丢弃一些梯度较小的训练实例。
下图为GOSS算法。
所有训练实例均按梯度排序a表示大梯度实例的采样百分比b表示小梯度实例的采样百分比。 通过使用 GOSS我们实际上减少了训练下一个集成树的训练集的大小这将使训练新树的速度更快。
2. 基于直方图的树节点分裂
在寻找最佳特征值来分割树节点时LightGBM使用特征值直方图并尝试所有直方图bin值而不是尝试所有可能的特征值因此可以减少寻找最佳特征吐出值的时间和计算量。顺便说一下LightGBM 的分割标准是减少从父级到子级的梯度方差。
例如给定下面的年龄特征将直方图离散特征值放入不同的范围箱中因此我们可以使用像Age⩽30Age⩽40Age⩽100这样的吐槽标准而不是尝试像Age这样的所有可能的年龄值⩽31、年龄⩽32 等 用bin来替换原始数据相当于增加正则化bin的数量决定了正则化的程度。bin 越小惩罚越严重欠拟合的风险越高。 同样在树分裂场景中对于给定的特征直方图是可加的 父节点直方图 左子直方图 右子直方图
因此在计算子直方图时我们只需要计算一个子直方图选择较小尺寸的子直方图另一子直方图是父直方图减去计算得到的直方图。
3. 分类特征的最优分割
通常在处理树节点分裂中的分类特征时我们总是使用One Vs Rest作为节点分裂规则例如分裂条件是“Weather Sunny” vs “All other Weather (Rainy, Cloudy, Snowy etc)”。一般来说这一“一对一”策略的问题是
它往往会在子节点中生成不平衡的数据点分配例如左子节点比右子节点分配更多的数据点并且需要增长得很深才能获得良好的准确性由于需要生长很深的树需要多次节点分裂所以建树效率很低。
受这些问题的启发LightGBM 采用了如下多对多策略。
对于给定的分类特征
对于特征的每个类别计算平均值 Sum(y)/Count(y)按平均值对所有类别进行排序如下图所示。从最低平均值到最大平均值枚举分割值以找到最佳分割值。分裂值将所有类别分为两部分类别均值小于或大于分裂值这就是节点分裂条件。 4. 独家功能捆绑 EFB旨在通过合并特征来减少特征具体来说就是合并互斥的特征这些特征很少同时取非零值。 LightGBM提供了以下两种算法来实现 从训练集中识别互斥的特征包合并功能包并为该包分配一个值 下面是一个 EFB 示例显示了特征合并的结果。
在该示例中最大冲突计数K2表明根据EFB算法原来的5个特征可以减少到3个特征。 5. Leaf-wise 树生长策略
LightGBM 放弃了大多数 GBDT 工具所使用的 level-wise 决策树生长策略而使用了具有深度限制的 leaf-wise 算法。 Leaf-wise策略中每次从所有叶子中找到分裂增益最高的叶子然后分裂并循环。 在上面的树生长过程中绿叶节点是分裂增益最高的节点因此对其进行分裂然后重新评估以找到下一个绿叶节点。
leaf-wise的好处是对于每一次节点分裂我们总是能为树带来最高的增益因此它比level-wise更有效地生长树。但我们需要添加树深度和一些其他限制以避免过度拟合。
6. 并行优化
为了处理超大型数据集LightGBM引入了分布式过程来并行计算特征直方图和最佳分割特征值。
LightGBM支持两种并行策略——特征并行和数据并行
特征并行算法
训练数据被垂直列或特征分割并分配到不同的工作计算机以计算分配的特征的局部直方图和局部最佳分割然后从所有工作器输出中全局选择最佳分割。 数据并行算法
训练数据被水平行分割并分配到不同的工作计算机根据分配的训练子集计算所有特征的局部直方图然后合并来自所有工作计算机的局部直方图的所有特征直方图。 LightGBM还对数据并行算法进行了进一步的优化其思想是每个worker在本地选择前K个最佳分割特征然后在全局投票选出顶级特征。
一旦获得顶部特征我们只需要从所有工人本地直方图中合并顶部特征直方图。 7.总结
上述所有 LightGBM 创新技术的目的都是为了使其训练速度更快它们使 LightGBM 在以下方面表现出色
训练效率快内存使用率低高精度并行学习处理大规模数据的能力
