LightGBM原理与实现

1. LightGBM是什么东东

不久前微软DMTK(分布式机器学习工具包)团队在GitHub上开源了性能超越其他boosting工具的LightGBM,在三天之内GitHub上被star了1000次,fork了200次。知乎上有近千人关注“如何看待微软开源的LightGBM?”问题,被评价为“速度惊人”,“非常有启发”,“支持分布式”,“代码清晰易懂”,“占用内存小”等。

LightGBM (Light Gradient Boosting Machine)(请点击https://github.com/Microsoft/LightGBM)是一个实现GBDT算法的框架,支持高效率的并行训练。

LightGBM在Higgs数据集上LightGBM比XGBoost快将近10倍,内存占用率大约为XGBoost的1/6,并且准确率也有提升。GBDT在每一次迭代的时候,都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小;如果不装进内存,反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据,普通的GBDT算法是不能满足其需求的。

LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题,让GBDT可以更好更快地用于工业实践。

1.1 LightGBM在哪些地方进行了优化 (区别XGBoost)?

  • 基于Histogram的决策树算法
  • 带深度限制的Leaf-wise的叶子生长策略
  • 直方图做差加速直接
  • 支持类别特征(Categorical Feature)
  • Cache命中率优化
  • 基于直方图的稀疏特征优化多线程优化。

1.2 Histogram算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数(其实又是分桶的思想,而这些桶称为bin,比如[0,0.1)→0, [0.1,0.3)→1),同时构造一个宽度为k的直方图。

在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。

使用直方图算法有很多优点。首先,最明显就是内存消耗的降低,直方图算法不仅不需要额外存储预排序的结果,而且可以只保存特征离散化后的值,而这个值一般用8位整型存储就足够了,内存消耗可以降低为原来的1/8。然后在计算上的代价也大幅降低,预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k次(k可以认为是常数),时间复杂度从O(#data*#feature)优化到O(k*#features)。

1.3 带深度限制的Leaf-wise的叶子生长策略

在XGBoost中,树是按层生长的,称为Level-wise tree growth,同一层的所有节点都做分裂,最后剪枝,如下图所示:

Level-wise过一次数据可以同时分裂同一层的叶子,容易进行多线程优化,也好控制模型复杂度,不容易过拟合。但实际上Level-wise是一种低效的算法,因为它不加区分的对待同一层的叶子,带来了很多没必要的开销,因为实际上很多叶子的分裂增益较低,没必要进行搜索和分裂。

在Histogram算法之上,LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长 (level-wise) 的决策树生长策略,而使用了带有深度限制的按叶子生长 (leaf-wise)算法。

Leaf-wise则是一种更为高效的策略,每次从当前所有叶子中,找到分裂增益最大的一个叶子,然后分裂,如此循环。因此同Level-wise相比,在分裂次数相同的情况下,Leaf-wise可以降低更多的误差,得到更好的精度。Leaf-wise的缺点是可能会长出比较深的决策树,产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度的限制,在保证高效率的同时防止过拟合。

1.4 直方图差加速

LightGBM另一个优化是Histogram(直方图)做差加速。一个容易观察到的现象:一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。

利用这个方法,LightGBM可以在构造一个叶子的直方图后,可以用非常微小的代价得到它兄弟叶子的直方图,在速度上可以提升一倍。

1.5 直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征,一般需要把类别特征,转化到多维的0/1特征,降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑,LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。在Expo数据集上的实验,相比0/1展开的方法,训练速度可以加速8倍,并且精度一致。据我们所知,LightGBM是第一个直接支持类别特征的GBDT工具。

2. LightGBM优点

LightGBM (Light Gradient Boosting Machine)(请点击https://github.com/Microsoft/LightGBM)是一个实现GBDT算法的框架,支持高效率的并行训练,并且具有以下优点:

  • 更快的训练速度
  • 更低的内存消耗
  • 更好的准确率
  • 分布式支持,可以快速处理海量数据

3. 代码实现

为了演示LightGBM在Python中的用法,本代码以sklearn包中自带的鸢尾花数据集为例,用lightgbm算法实现鸢尾花种类的分类任务。

本文分享自微信公众号 - 机器学习入门与实战(datanlp)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • XGBoost原理与实现

    XGBoost是陈天奇等人开发的一个开源机器学习项目,高效地实现了GBDT算法并进行了算法和工程上的许多改进,被广泛应用在Kaggle竞赛及其他许多机器学习竞赛...

    大数据技术与机器学习
  • 马尔可夫网络、马尔可夫模型、马尔可夫过程

    这一节我们重点来讲一下马尔可夫,正如题目所示,看了会一脸蒙蔽,好在我们会一点一点的来解释上面的概念,请大家按照顺序往下看就会完全弄明白了,这里我给一个通俗易懂的...

    大数据技术与机器学习
  • ⻓短期记忆LSTM

    在你阅读这篇文章时候,你都是基于自己已经拥有的对先前所见词的理解来推断当前词的真实含义。我们不会将所有的东西都全部丢弃,然后用空白的大脑进行思考。我们的思想拥有...

    大数据技术与机器学习
  • 开源|LightGBM基本原理,以及调用形式

    学到老
  • 你会做Excel直方图吗?一个超实用的数据分析神图

    在日常工作中,我们最常用的是柱形图、折线图和饼图。今天兰色要分享一个冷门图表:直方图

    Piper蛋窝
  • 两个不错的django免费入门学习资源

    近期在群里看到一些群友分享的 django 学习资料,感觉质量非常不错,关键是这些学习资料还都是免费的!因此在这里分享给大家,希望好的东西能让更多的人知道,也算...

    追梦人物
  • RTSP协议视频智能分析平台EasyNVR播放界面为什么无法查看HLS视频流?

    自2021年开年来,各大浏览器就已经禁止了RTMP协议视频流的网页播放,flash插件已经成为历史,但是其他协议视频流的队伍仍在不断壮大,拿EasyNVR平台来...

    EasyNVR
  • 关于友盟分享的小问题

    1.目前碰到一个问题是这样的:将友盟分享作为一个工程依赖的方式引入项目中,而你的的工程项目中如果有同名的资源文件,就有可能如下问题(找不到引用id)

    夏洛克的猫
  • HiC-Pro实战详解

    HiC-Pro软件非常灵活,不仅可以处理各种不同建库方式的Hi-C数据,也可以处理capture Hi-C数据。软件安装过程如下

    生信修炼手册
  • LintCode 全排列题目分析

    添加的时候排除掉相同的元素即可,回溯法我们经常会设置一个已访问标识数组,来表示数组被访问过,但这里不用这样,因为如果list里面已经包含就说明已经访问过了,所以...

    desperate633

扫码关注云+社区

领取腾讯云代金券