直接在连续特征上构建最优分类树，速度提升10倍以上，准确率更高。
Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
- 用动态规划与分支定界法直接处理连续特征，避免粗糙离散化。
- 运行时间比现有最优方法快一到两个数量级，深度为二的树可快速求解。
- 适合追求高精度且对模型可解释性要求高的决策场景。
在给定大小限制下计算能证明最大化训练性能的最优分类树是NP难问题，现有最先进方法通常仅能处理深度不超过三的树，因此普遍采用对连续特征进行粗粒度二值化以保证可扩展性。本文提出一种新算法，直接在连续特征数据上优化分类树，结合动态规划与分支定界法。我们设计了新的剪枝技术，在搜索中剔除与先前计算过的分裂相似的次优分裂，并提供高效子程序用于求解最优深度为二的树。实验表明，该方法相比现有最优方法在运行时间上提升一个或多个数量级，测试准确率相比贪心启发式方法提高5%。
原文摘要 · Abstract (English)
Computing an optimal classification tree that provably maximizes training performance within a given size limit, is NP-hard, and in practice, most state-of-the-art methods do not scale beyond computing optimal trees of depth three. Therefore, most methods rely on a coarse binarization of continuous features to maintain scalability. We propose a novel algorithm that optimizes trees directly on the continuous feature data using dynamic programming with branch-and-bound. We develop new pruning techniques that eliminate many sub-optimal splits in the search when similar to previously computed splits and we provide an efficient subroutine for computing optimal depth-two trees. Our experiments demonstrate that these techniques improve runtime by one or more orders of magnitude over state-of-the-art optimal methods and improve test accuracy by 5% over greedy heuristics.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。