LightGBM

Note

LightGBM是一个基于树的学习算法的梯度增强框架，被设计成分布式的和高效的

优点：

原理

lightGBM 主要基于以下方面优化，提升整体特特性：

直方图算法的基本特征是：

Note

举个例子：

[0 , 0.1) --> 0;

[0.1 , 0.3) --> 1;

使用直方图算法有很多优点。首先，最明显的是 内存消耗的降低 ，直方图算法不仅不需要额外存储预排序的结构，而且只需要保持特征离散化之后的值，而这个值一般使用 8 位整型存储就够了，内存消耗方面可以降低为原来的 $\frac{1}{8}$

然后在计算方面的代价也大幅度降低

预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数）

当然，Histogram不是完美的，由于特征被离散化，所以导致不是很精确，所以会对结果产生影响。
但其实上，在不同的数据集上的结果表明，离散化的分割点对最终的精度影响不是很大，甚至有时候会好一点，原因是决策树本来就是弱模型。

一个叶子节点的直方图可以由它父亲节点的直方图与它兄弟的直方图做差得到。

通常构造直方图，需要遍历这个叶子上的所有数据，但直方图做差只需要遍历直方图的k个桶

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

level-wise 遍历一次数据可以同时分裂同一层的叶子，容易实现多线程优化，也好控制模型复杂度，不容易过拟合

Leaf-wise则是一个比较高效的策略，每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环

大多数的机器学习工具都不能直接支持类别特征，一般需要把类别特征，转化到多维的0/1特征，在效率上降低了不少

而类别特征的使用是在实践中很常用的。但是基于这个考虑，lightGBM优化了对类别特征的支持，可以直接输入类别特征，不需要额外的0/1的展开。并且在决策树上增加了类别特征的决策规则

目前看来，lightGBM是第一个支持类别特征的GBDT工具

LightGBM还具有支持高效并行的优点。LightGBM原生支持并行学习，目前支持特征并行和数据并行的两种。

LightGBM针对这两种并行方法都做了优化:

数据并行中使用分散规约（Reduce Scatter）把直方图合并的任务分摊到不同的机器上，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量