提出一种可随时中断的连续特征最优决策树学习方法
Anytime Optimal Decision Tree Learning with Continuous Features
- 采用有限偏差搜索均衡分配计算资源，避免深度优先导致的不平衡
- 在任意中断时刻都能给出高质量树结构，显著优于传统方法
- 适合需要快速响应的场景，如实时决策系统
近年来，针对二元特征的最优决策树学习算法取得了显著进展。然而，将这些方法扩展到连续特征仍面临巨大挑战，主要源于每维特征可能产生的大量分裂点。最近一项优雅的精确算法虽能处理连续特征，但计算时间随深度迅速增长，实际应用受限于浅层深度（通常为3或4）。该方法采用深度优先搜索优化策略，完全优化每个分裂的左子树后才探索右子树，虽能保证解的最优性，但在时间不足时会导致已找到的树高度不平衡且次优，此时纯贪婪方法如C4.5反而可能表现更好。为此，我们提出一种具备随时中断能力且完整的算法，利用有限偏差搜索策略，更均匀地分配计算资源，从而确保在任何中断点均有高质量的决策树可用。实验表明，本方法在随时性能上显著优于现有方案。
原文摘要 · Abstract (English)
In recent years, significant progress has been made on algorithms for learning optimal decision trees, primarily in the context of binary features. Extending these methods to continuous features remains substantially more challenging due to the large number of potential splits for each feature. Recently, an elegant exact algorithm was proposed for learning optimal decision trees with continuous features; however, the rapidly increasing computational time limits its practical applicability to shallow depths (typically 3 or 4). It relies on a depth-first search optimization strategy that fully optimizes the left subtree of each split before exploring the corresponding right subtree. While effective in finding optimal solutions given sufficient time, this strategy can lead to poor anytime behavior: when interrupted early, the best-found tree is often highly unbalanced and suboptimal. In such cases, purely greedy methods such as C4.5 may, paradoxically, yield better solutions. To address this limitation, we propose an anytime, yet complete approach leveraging limited discrepancy search, distributing the computational effort more evenly across the entire tree structure, and thus ensuring that a high-quality decision tree is available at any interruption point. Experimental results show that our approach outperforms the existing one in terms of anytime performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。