基于直方图的分裂点查找

传统梯度提升机，甚至像XGBoost这样使用其精确贪婪算法的优化版本，在查找连续特征的最佳分裂点时面临很大的计算难题。它们通常需要在每个节点对特征值进行排序，并迭代每个特征的所有可能分裂点来计算潜在的信息增益。此过程在每个节点和每棵树中重复，计算成本会很高，尤其是在大型数据集上（每个节点的时间复杂度为 $O(\#数据量 \times \#特征量)$ ）。

LightGBM通过采用基于直方图的算法直接解决这个瓶颈。LightGBM不将连续特征的每个唯一值视为一个潜在的分裂点，而是首先将这些连续值离散化或分箱成一组离散的箱。

分箱过程

在训练过程开始之前（或有时在构建每棵树的开始时），LightGBM会迭代连续特征并构建直方图。每个连续特征被分成固定数量的箱，这由max_bin参数 (parameter)确定（通常默认为255）。落在相同范围内的数据点被分组到相同的箱中。

例如，考虑一个范围从20到80的特征，比如“年龄”。如果max_bin=6，算法可能会创建以下箱：[20-30), [30-40), [40-50), [50-60), [60-70), [70-80]。所有年龄为35的数据实例都会落入[30-40)箱中。这种分箱通常对整个数据集中的每个特征只进行一次。

一个直方图，展示了连续的“年龄”值如何被分组到离散的箱中。高度表示每个箱中的数据点数量。

构建直方图和查找分裂点

一旦箱建立完成，核心训练循环会发生很大变化。在构建树并在特定节点考虑分裂时，LightGBM不会迭代特征的已排序数据点。而是执行以下步骤：

按箱累计统计量： 对于每个特征，它会创建一个直方图。直方图中的每个条（箱）会累计属于当前节点中该箱的所有数据点的梯度之和和海森之和（二阶导数，与XGBoost类似）。
遍历箱： 为了查找一个特征的最佳分裂点，LightGBM会迭代其直方图的箱（从1到max_bin）。对于每个箱 $k$ ，它会考虑将数据分裂为特征值 $\le$ 箱 $k$ 的实例和特征值 $>$ 箱 $k$ 的实例。
高效计算增益： 每个潜在分裂点（由箱边界表示）的增益可以利用直方图中存储的梯度和海森累计和非常迅速地计算出来。查找一个特征的最佳分裂点的时间复杂度从 $O(\#数据量)$ 降低到 $O(\#箱数量)$ 。

因此，每个节点的总时间复杂度变为 $O(\#箱数量 \times \#特征量)$ ，当#箱数量 << #数据量时，这比精确贪婪方法的 $O(\#数据量 \times \#特征量)$ 快得多。

直方图减法优化

LightGBM进一步优化此过程。当一个节点分裂成两个子节点时，从头计算子节点的直方图仍然需要遍历分配给每个子节点的数据点。LightGBM通过一个巧妙的技巧避免了这种情况：直方图减法。

由于父节点中的数据点完全分配到其左右子节点，父节点的直方图就是其子节点直方图的总和。因此，LightGBM计算一个子节点（通常是较小的那个，需要较少计算量）的直方图，并通过从父节点的直方图中减去已计算的子节点直方图来获取其兄弟节点的直方图。这避免了遍历较大子节点的数据，大大加快了更深树的训练速度。

LightGBM计算一个子节点 ( $H_l$ ) 的直方图，并通过从父节点的直方图 ( $H_p$ ) 中减去它来推导出另一个子节点 ( $H_r$ ) 的直方图，从而节省了计算量。

优势与考量

基于直方图方法的首要优势包括：

速度： 大幅降低了查找分裂点的成本，与精确贪婪方法相比，训练时间大大缩短，尤其是在大型数据集上。
内存效率： 需要存储箱的聚合值（梯度/海森之和），而不是预排序的特征值，大大减少了内存消耗。与特征值相关的内存使用量与 $O(\#箱数量 \times \#特征量)$ 成比例，而不是 $O(\#数据量 \times \#特征量)$ 。
缓存友好性： 基于箱访问数据可以带来更好的缓存利用率，与访问分散在内存中的排序索引相比。

然而，存在一个权衡：

近似性： 分箱本质上涉及近似。分裂只能发生在箱边界，不一定在两个数据点之间的精确最佳值处。这可能导致与精确方法相比准确性略有下降，尽管在实践中，由于分箱的正则化 (regularization)效应，这种差异通常可以忽略不计，甚至可能带来积极效果。
max_bin 参数 (parameter)： max_bin的选择会影响这种权衡。较小的max_bin会导致更快的训练和更低的内存使用量，但近似程度更粗（可能导致准确性下降）。较大的max_bin会提高准确性潜力，但也会增加计算和内存需求。默认值（通常为255）通常能提供很好的平衡。

基于直方图的算法是LightGBM效率的核心组成部分，它与GOSS（减少用于直方图构建的数据点数量）和EFB（减少需要直方图的特征数量）等技术协同工作，以实现其出色的速度和可扩展性。在设置LightGBM模型时，您主要通过max_bin参数来配置箱的数量。

import lightgbm as lgb
import numpy as np

# 示例数据（请替换为实际数据）
X_train = np.random.rand(1000, 10)
y_train = np.random.randint(0, 2, 1000)
lgb_train = lgb.Dataset(X_train, y_train)

# 设置参数，包括max_bin
params = {
    'objective': 'binary',
    'metric': 'binary_logloss',
    'boosting_type': 'gbdt',
    'num_leaves': 31,
    'learning_rate': 0.05,
    'feature_fraction': 0.9,
    'max_bin': 255  # 控制直方图的箱数量
}

# 训练模型
gbm = lgb.train(params,
                lgb_train,
                num_boost_round=100)

print(f"模型已使用max_bin={params['max_bin']}进行训练")

理解这一机制对于理解LightGBM为何在大型表格数据集上表现如此出色是必不可少的。它代表着从不惜一切代价追求精确性，转变为通过智能近似获得显著性能提升的转变。

这部分内容有帮助吗？

参考文献

LightGBM: A Highly Efficient Gradient Boosting Decision Tree, Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu, 2017 Advances in Neural Information Processing Systems, Vol. 30 (NeurIPS) DOI: 10.5555/3295222.3295232 - 介绍了基于直方图的算法、GOSS和EFB，以提高梯度提升的效率。
XGBoost: A Scalable Tree Boosting System, Tianqi Chen, Carlos Guestrin, 2016 Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (ACM) DOI: 10.1145/2939672.2939785 - 描述了用于分割查找的精确贪婪算法，为LightGBM的方法提供了一个比较点。
Parameters - LightGBM Documentation, LightGBM Contributors, 2023 - 提供了max_bin参数及其对LightGBM性能和准确性影响的实用细节。
The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Trevor Hastie, Robert Tibshirani, Jerome Friedman, 2009 (Springer) DOI: 10.1007/978-0-387-84858-7 - 介绍了梯度提升、决策树和相关算法的全面理论背景。