一、概述

在之前的介绍Xgboost的众多博文中，已经介绍过，在树分裂计算分裂特征的增益时，xgboost 采用了预排序的方法来处理节点分裂，这样计算的分裂点比较精确。但是，也造成了很大的时间开销。为了解决这个问题，Lightgbm 选择了基于 histogram 的决策树算法。相比于 pre-sorted算法，histogram 在内存消耗和计算代价上都有不少优势。

histogram算法简单来说，就是先对特征值进行装箱处理，形成一个一个的bins。对于连续特征来说，装箱处理就是特征工程中的离散化：如[0,0.3)—>0，[0.3,0.7)—->1等。在Lightgbm中默认的#bins为256（1个字节的能表示的长度，可以设置）。对于分类特征来说，则是每一种取值放入一个bin，且当取值的个数大于max bin数时，会忽略那些很少出现的category值。

在节点分裂的时候，这时候就不需要按照预排序算法那样，对于每个特征都计算#data遍了，而是只需要计算#bins遍，这样就大大加快了训练速度。

二、算法流程

下面是训练过程中利用直方图寻找最佳分割点的算法。

从算法中可以看到：直方图优化算法需要在训练前预先把特征值转化为bin value，也就是对每个特征的取值做个分段函数，将所有样本在该特征上的取值划分到某一段（bin）中。最终把特征取值从连续值转化成了离散值。需要注意得是：feature value对应的bin value在整个训练过程中是不会改变的。

最外面的 for 循环表示的意思是对当前模型下所有的叶子节点处理，需要遍历所有的特征，来找到增益最大的特征及其划分值，以此来分裂该叶子节点。

第二个 for 循环开始要对某个叶子分裂处理处理，这一步就开始遍历所有的特征了。对于每个特征，首先为其创建一个直方图。这个直方图存储了两类信息，分别是每个bin中样本的梯度之和（ $H[ f.bins[i] ].g$H[f.bins[i]].g），还有就是每个bin中样本数量（ $H[ f.bins[i] ].n$H[f.bins[i]].n）

第三个 for 循环遍历所有样本，累积上述的两类统计值到样本所属的bin中。即直方图的每个 bin 中包含了一定的样本，在此计算每个 bin 中的样本的梯度之和并对 bin 中的样本记数。

最后一个for循环，遍历所有bin，分别以当前bin作为分割点，累加其左边的bin至当前bin的梯度和（ $S_L$SL​）以及样本数量（ $n_L$nL​），并与父节点上的总梯度和（ $S_p$Sp​）以及总样本数量（ $n_p$np​）相减，得到右边所有bin的梯度和（ $S_R$SR​）以及样本数量（ $n_R$nR​），带入公式，计算出增益，在遍历过程中取最大的增益，以此时的特征和bin的特征值作为分裂节点的特征和分裂特征取值。

三、histogram算法与 pre-sorted算法对比

3.1 优势

• Pre-sorted 算法需要的内存约是训练数据的两倍(2 * #data * #features* 4Bytes)，它需要用32位浮点(4Bytes)来保存 feature value，并且对每一列特征，都需要一个额外的排好序的索引，这也需要32位(4Bytes)的存储空间。因此是(2 * #data * #features* 4Bytes)。而对于 histogram 算法，则只需要(#data * #features * 1Bytes)的内存消耗，仅为 pre-sorted算法的1/8。因为 histogram 算法仅需要存储 feature bin value (离散化后的数值)，不需要原始的 feature value，也不用排序，而 bin value 用 1Bytes(256 bins) 的大小一般也就足够了。

• 在计算上的优势则主要体现在“数据分割”。决策树算法有两个主要操作组成，一个是“寻找分割点”，另一个是“数据分割”。从算法时间复杂度来看，Histogram 算法和 pre-sorted 算法在“寻找分割点”的代价是一样的，都是O(#feature*#data)。而在“数据分割”时，pre-sorted 算法需要O(#feature*#data)，而 histogram 算法是O(#data)。因为 pre-sorted 算法的每一列特征的顺序都不一样，分割的时候需要对每个特征单独进行一次分割。Histogram算法不需要排序，所有特征共享同一个索引表，分割的时候仅需对这个索引表操作一次就可以。（更新: 这一点不完全正确，pre-sorted 与 level-wise 结合的时候，其实可以共用一个索引表(row_idx_to_tree_node_idx)。然后在寻找分割点的时候，同时操作同一层的节点，省去分割的步骤。但这样做的问题是会有非常多随机访问，有很大的chche miss，速度依然很慢。）
  （这里也不是特别明白，需要再深入研究）

• 另一个计算上的优势则是大幅减少了计算分割点增益的次数。对于每一个特征，pre-sorted 需要对每一个不同特征值都计算一次分割增益，而 histogram 只需要计算 #bins次。

• 最后，在数据并行的时候，用 histgoram 可以大幅降低通信代价。用 pre-sorted 算法的话，通信代价是非常大的（几乎是没办法用的）。所以 xgoobst 在并行的时候也使用 histogram 进行通信。
  （数据并行的优化是Lightgbm的令一个亮点，这里不是特别理解，需要再深入研究）

3.2 劣势

• histogram 算法不能找到很精确的分割点，训练误差没有 pre-sorted 好。但从实验结果来看， histogram 算法在测试集的误差和 pre-sorted 算法差异并不是很大，甚至有时候效果更好。实际上可能决策树对于分割点的精确程度并不太敏感，而且较“粗”的分割点也自带正则化的效果，再加上boosting算法本身就是弱分类器的集成。

四、直方图做差加速

在histogram算法上一个trick是histogram 做差加速。一个容易观察到的现象：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。利用这个方法，Lightgbm 可以在构造一个叶子（含有较少数据）的直方图后，可以用非常微小的代价得到它兄弟叶子（含有较多数据）的直方图。

因为构建兄弟叶子的直方图是做差得到的，时间复杂度仅为O（#bins），几乎可以忽略，因此，比起不做差得到的兄弟节点的直方图，在速度上可以提升一倍。

举例来说明什么是histogram 做差加速。

假设我们共有10个样本，2个特征。
特征 $f_1$f1​为类别特征，共有2个不同的属性值，分成了桶 $b_{11}$b11​、 $b_{12}$b12​；桶 $b_{11}$b11​的样本数是4个，桶 $b_{12}$b12​的样本数是6个。
特征 $f_2$f2​为连续特征，离散化后分成了桶 $b_{21}$b21​、 $b_{22}$b22​和 $b_{23}$b23​；桶 $b_{21}$b21​的样本数是2个，桶 $b_{22}$b22​的样本数是4个，桶 $b_{23}$b23​的样本数是4个。

我们依次计算每个bin作为分割点的增益，假设在桶 $b_{11}$b11​作为分割点时增益最大，那么以桶 $b_{11}$b11​分割，这时候：

a. 左子节点有4个样本。特征 $f_1$f1​的桶 $b_{11}$b11​的样本数为4个，桶 $b_{12}$b12​样本为0个。假设特征 $f_2$f2​仍有3个桶 $b_{21}$b21​、 $b_{22}$b22​和 $b_{23}$b23​，且桶 $b_{21}$b21​的样本数是1个，桶 $b_{22}$b22​的样本数是2个，桶 $b_{23}$b23​的样本数是1个。这时候左子节点2个特征的直方图已经构建成功。

b. 左子节点有4个样本，右子节点自然有6个样本。这时候右子节点的2个特征的直方图就可以根据父节点和左子节点的2个特征的直方图做差得到：
特征 $f_1$f1​只有桶 $b_{12}$b12​，且样本数为6个（6-0=0）。桶 $b_{11}$b11​样本数为0个（4-4=0）。
特征 $f_2$f2​仍有3个桶 $b_{21}$b21​、 $b_{22}$b22​和 $b_{23}$b23​，且桶 $b_{21}$b21​的样本数是1个（2-1=1），桶 $b_{22}$b22​的样本数是2个（4-2=2），桶 $b_{23}$b23​的样本数是3个（4-1=3）。
这时候右子节点2个特征的直方图也已经构建成功。

下图表示了整个过程：

深入分析就可以知道，左子节点计算直方图的复杂度是基于样本个数的，而左子节点计算直方图的复杂度却是基于桶的个数的。因此，大大节省了构建直方图的时间。

五、参考文献

如何看待微软新开源的LightGBM?
LightGBM 直方图优化算法