LightGBM

特点

速度快；耗内存小

使用直方图简化计算，计算split时只考虑直方图的bin做划分点，而不细化到每个sample。计算直方图时，两个子节点只用计算其中一个，另一个通过root和前一个做差可得。

基于histogram的算法，在寻找最佳split时，可以先顺序访问data的gradient，填入对应bin中，提高cache hit。

建立直方图的过程如下：

首先对原数据排序；
然后统计出distinct value以及对应的count；
如果distinct value数目小于max bin数，则正好每个value放入一个bin；
如果distinct value大于max bin，计算bin大小的均值，按一定规则将sample放入bin，保证相同value的放入同一bin，bin包含的sample数尽量平均。
注：max bin的默认值是256。
对于category类型的feature，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。
在求split时，对于category类型的feature，算的是“按是否属于某个category值划分”的gain，这和数值型feature是完全不同的，它的实际效果就是类似one-hot的编码方法。（最新的好像可以不是属于某个类别值，可以属于几个类别值，这样效果更好了）

算法优点：

内存消耗的降低。直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的1/8。
计算代价的降低。预排序算法每遍历一个特征值就需要计算一次分裂的增益，而直方图算法只需要计算k次（k可以认为是常数），时间复杂度从O(样本数*#特征数)优化到 O(k*特征数)。
计算直方图时，两个子节点只用计算其中一个，另一个通过root和前一个做差可得。

算法缺点：

当然直方图的缺点也是显而易见的，特征被离散化后，必然找到的分割点不是精确的，因此会对结果产生影响。但由于本身每一棵决策树就是弱学习器，所以这样的特征离散化，某种程度上说是被允许的，甚至也有特征扰动防止过拟合的效果。可以说是boosting这样的框架允许了直方图算法的运用。