用混合整数规划优化决策树，解决不平衡数据下的分类问题。
Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach
- 基于混合整数规划构建可优化非线性指标的决策树框架
- 在50个基准数据集上实现更快求解与更强预测性能
- 适合需要高可解释性且数据不平衡的场景
决策树的全局优化是组合优化中的长期挑战，但在可解释机器学习中具有重要意义。尽管该问题已研究数十年，但直到最近离散优化的进步才使实际算法成为可能。混合整数规划（MIP）具备高度建模灵活性，本文提出一种基于MIP的框架，用于在非线性性能指标（如F1分数）下学习最优分类树，明确处理类别不平衡问题。为提升可扩展性，开发了专用加速技术，包括定制的分支定切割算法、实例缩减方案和热启动策略。在50个基准数据集上评估表明，该框架能高效优化非线性指标，同时保持优异预测性能并显著降低求解时间，优于现有方法。
原文摘要 · Abstract (English)
Global optimization of decision trees is a long-standing challenge in combinatorial optimization, yet such models play an important role in interpretable machine learning. Although the problem has been investigated for several decades, only recent advances in discrete optimization have enabled practical algorithms for solving optimal classification tree problems on real-world datasets. Mixed-integer programming (MIP) offers a high degree of modeling flexibility, and we therefore propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics, such as the F1-score, that explicitly addresses class imbalance. To improve scalability, we develop problem-specific acceleration techniques, including a tailored branch-and-cut algorithm, an instance-reduction scheme, and warm-start strategies. We evaluate the proposed approach on 50 benchmark datasets. The computational results show that the framework can efficiently optimize nonlinear metrics while achieving strong predictive performance and reduced solution times compared with existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。