Optimal decision trees for categorical data via integer programming
Optimal decision trees for categorical data via integer programming
复制标题
DOI：
10.1007/s10898-021-01009-y
复制
发表时间：
2021-03-24
影响因子：
1.8
通讯作者：
Scheinberg, Katya
中科院分区：
文献类型：
--
作者：
Gunluk, Oktay;Kalagnanam, Jayant;Scheinberg, Katya
几十年来，决策树一直是一类非常受欢迎的预测模型，因为它们具有可解释性和对分类特征的良好性能。然而，它们并不总是稳健的，往往会与数据过度匹配。此外，如果允许它们变大，它们就会失去可解释性。在这篇文章中，我们提出了一种混合整数规划公式来构造预先指定大小的最优决策树。我们考虑到分类特征的特殊结构，并允许在每个节点上进行组合决策(基于特征值子集)。我们的方法还可以通过阈值来处理数字特征。我们表明，使用中等大小的训练集可以在小树上获得非常好的精度。我们解决的优化问题用现代求解器是很容易处理的。
Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mixed integer programming formulation to construct optimal decision trees of a prespecified size. We take the special structure of categorical features into account and allow combinatorial decisions (based on subsets of values of features) at each node. Our approach can also handle numerical features via thresholding. We show that very good accuracy can be achieved with small trees using moderately-sized training sets. The optimization problems we solve are tractable with modern solvers.