📊 statistics

DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers

本文提出了数据驱动质心分裂（Data-Informed Centroid Splitting, DICS），这是一种基于聚类的框架，它通过利用数据驱动的先验知识来缩小分裂搜索空间，在保持相当的预测准确度的同时，显著加速了决策树的训练，并提供了理论上的性能保证。

原作者： MD Saifur Rahman Mazumder, Feng Yu

发布于 2026-08-21

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： MD Saifur Rahman Mazumder, Feng Yu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代计算的广袤领域中，存在着一类被称为决策树的工具家族。想象一个流程图，它会对一段数据提出一系列简单的“是”或“否”的问题——例如，一封电子邮件是否包含某些词汇，或者患者的血压是否超过了特定水平——以此得出最终结论。这些模型深受数据科学家喜爱，因为它们易于理解且通常非常准确。然而，构建它们需要付出巨大的代价。为了创建一个最有效的流程图，计算机必须在每一步都检查数百万个可能的提问，寻找能够将一组数据与另一组数据区分开的最佳分割点。这种穷举搜索就像是在试图通过逐一检查每一根稻草来寻找大海捞针中的那根针；虽然可行，但极其耗费时间和计算能力，尤其是在处理大规模且复杂的数据时。

德克萨斯大学埃尔帕索分校的研究人员提出了一种在不牺牲准确性的情况下加速这一过程的新方法。他们将这种方法称为“数据启发式质心分割”（Data-Informed Centroid Splitting，简称 DICS）。这种新方法不再盲目地检查每一个可能的问题，而是通过一个初步步骤来了解数据的总体形状。它将相似的数据点聚集在一起，并识别出这些组的中心。通过观察这些中心之间的边界，该方法生成了一份关于最值得提问的候选问题的精简且智能的列表。这使得计算机可以跳过绝大多数无用的选项，只专注于那些可能产生影响的分割点。其结果是一个学习速度更快、同时仍能做出与传统慢速方法同样正确预测的系统。

这项工作的核心思想基于一个简单的观察：属于同一类别的观测点往往会在数字空间中聚集在一起。如果你绘制出成千上万条客户记录或生物样本的图表，同类型的项目自然会形成紧密的集群。研究人员认为，分隔这些集群的线很可能就是分隔不同分类任务中不同类别的线。为了测试这一点，他们首先使用了一种标准的聚类技术来找到每组相似数据点的中心。然后，他们计算了这些中心之间的中点，以创建一组候选问题。为了使这一过程更加精确，他们根据每组数据内部的离散程度调整了这些中点，从而确保即使某一组的数据分布较为分散，其划分界限依然是公平的。

这种方法与那些通过简单地舍入数据值或使用随机猜测来尝试加速树构建的旧方法形成了鲜明对比。虽然那些技术很快，但它们往往会丢失重要的细节，或者需要计算机进行更多次的猜测才能找到理想答案。然而，这种新方法是由数据的实际结构所引导的。研究人员表明，通过使用这种聚类引导，他们可以大幅减少计算机需要提出的问题数量。在测试中，他们发现，在合成数据集上，这种新方法训练决策树的速度比标准方法快了多达 22 倍，而在现实世界的数据集上则快了多达 21 倍，且几乎没有精度损失。

该团队并未止步于单棵决策树；他们将同样的逻辑应用于结合了许多树的更强大的系统，例如随机森林和梯度提升机。这些集成方法通常是处理复杂任务时最准确的工具，但也是计算成本最高的。通过将这种数据启发式分割策略整合到这些更大的系统中，研究人员实现了类似的显著加速。例如，在一个包含超过两万条记录的数据集上，新方法在不到两秒钟内就训练好了一棵随机森林，而标准方法则耗时超过 44 秒。准确率几乎保持不变，这证明了这种速度提升源于效率的提高，而非在模型质量上偷工减料。

为了确保研究结果的稳健性，研究人员在各种现实世界的挑战中测试了他们的方法，包括检测垃圾邮件、识别欺诈性金融交易以及对服装和数字图像进行分类。在每种情况下，新方法都保持了其速度优势。例如，在 Spambase 数据集上，传统方法仅需极短的时间，但新方法快了一倍。在包含 20 万条记录的较大规模 Santander 数据集上，新方法比标准方法快了 7 倍以上。即使是在数据处理难度极高的复杂图像识别任务（如 CIFAR-10）中，新方法也比标准决策树快了近 13 倍，同时保持了较低的错误率。

研究人员还提供了数学证明来支持他们的观察。他们证明了随着数据量的增加，他们的新方法所选出的分割点与穷举搜索所选出的分割点之间的差异会变得微乎其微。本质上，只要数据遵循某些自然模式，该方法就能保证找到一个几乎与绝对最佳分割点同样优秀的分割点。这种理论支撑使人们相信，这种加速并非偶然的运气，而是一种可靠的特性。这项工作表明，通过在构建模型之前理解数据的形状，计算机可以对寻找方向做出更明智的决策，从而节省大量的计算时间和能量。

虽然目前的研究侧重于分类任务（即目标是将数据分为不同的类别），但研究人员承认，同样的原理也有潜力应用于回归问题（即目标是预测一个特定的数值）。他们指出，该方法目前仅限于分类任务，但这一方法的成功为未来将这些效率提升扩展到其他类型的机器学习领域打开了大门。目前，这项研究为任何需要处理大规模数据集且需要在等待计算机完成计算前构建准确模型的人提供了一条清晰的前行路径。通过让数据本身指引方向，研究人员展示了我们可以构建更聪明、更快速的树，而不必削弱森林的力量。

技术摘要：用于决策树分类器的基于数据信息的质心分裂 (DICS)

1. 问题陈述

基于决策树的模型，包括其集成变体如随机森林（Random Forests）和梯度提升机（Gradient Boosting Machines），因其可解释性和卓越的实证性能而被广泛应用。然而，训练这些模型面临着一个显著的计算瓶颈：每个节点处对最优分裂点进行穷举搜索。

在标准的决策树归纳过程中，算法需要评估每个特征的所有可能分裂点。对于一个拥有 $N$ 个样本和 $P$ 个特征的数据集，这涉及在每个节点评估多达 $(N-1)P$ 个候选分裂点。这一过程在计算上非常昂贵，尤其是在处理大规模和高维数据集时。虽然现有的方法（如 XGBoost 和 LightGBM 中的直方图分箱法）通过对特征进行离散化来降低这一成本，但它们会引入量化误差，并在效率与准确性之间进行权衡。此外，这些方法缺乏关于哪些分裂点更有可能具有信息量的先验指导，将所有候选阈值视为同等对待。

2. 方法论：基于数据信息的质心分裂 (DICS)

作者提出了基于数据信息的质心分裂 (DICS) 框架，该框架利用数据内部的结构信息来构建一组紧凑且具有信息量的候选分裂集，从而在不改变底层贪婪树目标的前提下缩小搜索空间。

核心概念

该方法的动机在于观察到：在分类任务中，属于同一类别的样本倾向于在特征空间中聚集在一起。因此，这些簇之间的边界往往近似于分类决策边界。DICS 通过使用聚类来生成候选分裂阈值，从而利用了这一特性。

算法步骤

聚类： 算法对特征矩阵 $X$ 应用 K-means 聚类，以获得 $K$ 个质心 $\{\mu_c\}_{c=1}^K$ 。这些质心代表了数据分布的主导模式。
边界生成： DICS 不再评估所有可能的阈值，而是基于簇质心之间的边界生成候选分裂。
- 中点边界： 最简单的边界是两个质心之间的中点： $\zeta = \frac{1}{2}(\mu_{c_1} + \mu_{c_2})$ 。
- 方差调整边界： 为了处理簇具有不同方差（离散度）的情况，作者提出了一个方差调整边界，其中质心到分裂点的距离与它们的标准差（ $\hat{\sigma}$ ）成比例：
  $\zeta(\mu_{c_1}, \mu_{c_2}) = \frac{\hat{\sigma}_{c_1}\mu_{c_2} + \hat{\sigma}_{c_2}\mu_{c_1}}{\hat{\sigma}_{c_1} + \hat{\sigma}_{c_2}}$
候选选择： 存在 $\binom{K}{2}$ 对可能的质心对。为了避免冗余，算法选择具有最大质心间距的前 $m$ 个质心对。这些对定义了每个特征的候选阈值集。
集成： 生成的候选分裂集被用于生长树。该方法被集成到以下模型中：
- CGCT： 聚类引导分类树（标准决策树）。
- CGRF： 聚类引导随机森林。
- FastC-GBM： 一种结合了 DICS 与基于梯度的单侧采样 (GOSS) 以及特征子采样的梯度提升机。

计算复杂度

预计算： DICS 引入了一个一次性的开销 $O(TKbP)$ ，使用的是小批量 K-means（mini-batch K-means），其中 $T$ 是迭代次数， $b$ 是批大小。与分裂查找阶段相比，这一开销可以忽略不计。
分裂查找： 每个节点的成本从 $O(NP)$ （穷举法）或 $O(H P)$ （基于直方图的方法）降低到 $O(mP)$ ，其中 $m$ 是选定的质心对数量。由于 $m$ 通常很小（例如当 $K=5$ 时， $m=10$ ），这提供了显著的复杂度降低。

3. 理论分析

论文通过提供理论分析（定理 1）来证明 DICS 在渐近意义上不会降低预测性能。

假设： 分析假设特征的边缘密度在最优分裂点附近满足密度正则性条件。
结果： 由穷举搜索（DT）找到的最优分裂与由 DICS 找到的最优分裂之间的信息增益（impurity gain）差异被限制在 $O(1/\sqrt{N})$ 内。
含义： 随着样本数 $N$ 的增加，两种方法之间的性能差距会消失。DICS 诱导的分区与最优分区的差异最多仅涉及 $O(\sqrt{N})$ 个样本，确保了即使在更深的树层级，保留的增益比（gain ratio）仍然很高。

4. 实验结果

作者在合成数据集和真实世界数据集上对 DICS 进行了评估，并将其与标准决策树 (DT)、随机森林 (RF)、XGBoost 以及相关方法 BDTKS 进行了比较。

合成数据

加速比： 基于 DICS 的模型实现了显著的加速。
- CGCT： 比标准 DT 快 8–22 倍。
- CGRF： 比标准 RF 快 8–30 倍。
- FastC-GBM： 比 XGBoost 快 5–50 倍，比 LightGBM 快 3.6–27 倍。
准确率： 准确率的权衡非常微小，通常与基准模型的差距在 0.02 以内。
对比： 相关方法 BDTKS（在每个节点递归应用 K-means）被发现计算成本高昂，且在速度或准确性方面均未表现出优势。

真实世界数据集

实验涵盖了 Helena、Spambase、Santander、CIFAR-10、MNIST 和 Fashion-MNIST 等数据集。

效率： DICS 持续降低了训练时间。例如，在真实数据集上，CGCT 比 DT 快 2–21 倍。FastC-GBM 比 XGBoost 快达 18.75 倍。
鲁棒性： 在 Helena 数据集上，LightGBM 表现较差，而 FastC-GBM 保持了稳定的性能，这表明了其改进的鲁棒性。
准确率： 虽然某些数据集（如 CIFAR-10）显示出与合成设置相比略微下降的准确率，但这种下降保持在很小的范围内，且该方法总体上保留了预测性能。

5. 重要性与主张

论文声称 DICS 通过将基于数据的先验知识整合到分裂选择过程中，为训练树分类器提供了一种可扩展的解决方案。

核心贡献： 该研究的主要贡献在于证明了聚类结构可以作为有效的先验，从而在不破坏决策树贪婪优化目标的前提下，大幅缩小分裂搜索空间。
适度的声明： 作者明确指出，其理论结果表明 DICS 在渐近意义上接近穷举搜索，但并未声称在所有情况下都优于穷举搜索。他们承认分裂增益与最终分类准确率之间的关系并非简单的线性关系。
局限性与未来工作： 当前框架专注于分类任务。作者将把这种方法扩展到回归任务作为未来的主要研究方向。他们还指出，虽然该方法在分类中非常有效，但在特定真实世界数据集（如 Santander）上的性能可能会受到实现层面内存管理问题的影响，而非算法本身的问题。

总之，DICS 提供了一种原则性的方法，通过牺牲极小的搜索空间来换取巨大的计算成本降低，这使得它在处理大规模、高维分类问题时特别具有价值。