通用和可扩展的最优稀疏决策树

ICMLJun, 2020

Generalized and Scalable Optimal Sparse Decision Trees

Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, Margo Seltzer

TL;DR通过提出一种决策树优化框架，解决了当前领域中两个开放性问题：不平衡数据处理和连续变量完全优化。此外，我们还介绍了一种可扩展的算法，可以在存在连续变量的情况下产生可证明的最优结果，并相对于现有技术将决策树构建速度提高了数个数量级。

Abstract

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have

decision trees optimization interpretable machine learning imbalanced data continuous variables

发现论文，激发创造

最优稀疏决策树

这篇论文介绍了第一种针对二进制变量进行最佳决策树生成的实用算法，该算法结合了分析界限和数据结构等现代技术，在可扩展性、速度和最优性方面具有明显优势。

Apr, 2019

通过参考集合快速稀疏决策树优化

通过使用智能猜测策略，我们可以在几个数量级的时间里降低运行时间，提供对最佳决策树误差和表达能力偏差的界限，并在许多情况下快速构建与黑盒模型的匹配精度的稀疏决策树。

Dec, 2021

最优随机分类树中的稀疏性

本文提出了一种连续优化方法来构建精简的最佳分类树，基于斜裁剪，并旨在在整个树中使用较少的预测变量进行剪枝。该方法模拟了本地和全局稀疏性，证明了其对提高分类精度具有实用性。

Feb, 2020

用于最优治疗方案和最优策略设计的加权稀疏决策树快速优化

本研究提出了三种算法来高效地稀疏加权决策树优化，解决了算法无法处理加权数据样本的问题，这在影响个体数据点上的倒数概率加权方面有重要应用.

Oct, 2022

最优稀疏回归树

本文提出了一种动态编程方法来构建确切的最优稀疏回归树，并基于一维 k-Means 聚类算法提出了新的下界，我们能够在几秒钟内找到具有挑战性的数据集的最优稀疏树。

Nov, 2022

决策树高效非贪婪优化

该论文提出了一种算法，该算法能够基于全局目标同时优化决策树的所有级别的分裂函数和叶参数，使用随机梯度下降进行优化，实验结果表明，该算法相比贪心算法在分类任务的表现优秀。

Nov, 2015

基于整数规划的最优广义决策树

本文提出了一种混合整数规划的方法来构建特定大小的最优决策树，采用特殊结构的分类特征，考虑每个节点上基于特征子集的组合决策，并通过阈值处理处理数值特征，证明了在中等规模的训练集下，采用小型决策树可获得很高的准确率，我们使用现代求解器解决所提出的优化问题。

Dec, 2016

可分离目标的最优决策树：推动动态规划的极限

本研究探索了决策树中子树优化的分离可行性条件及其建立的动态规划框架对于不同应用各目标和约束的普适性。实验证明该框架在可扩展性上优于通用求解器。

May, 2023

MurTree：使用动态规划和搜索实现的最优分类树

本研究提出了一种基于动态规划和搜索的学习算法来实现最优决策树，这种算法支持对树的深度和节点数量设置限制，并在实验证明使用我们的算法只需要很短的时间就可以处理具有成千上万个实例的数据集，从而极大地提高了最优决策树的实用性。

Jul, 2020

预测优化框架下的决策树决策

该研究探讨了在 “先预测，再优化” 框架下使用决策树进行决策问题的决策，并提出了一种可观的方法称为 SPO Trees (SPOTs) 用于训练决策树，该方法具有较高的解释性。实验结果表明，SPOTs 可提供更高质量的决策，并显著降低了模型复杂性。

Feb, 2020