Optimal Generalized Decision Trees via Integer Programming
Optimal Generalized Decision Trees via Integer Programming
复制标题
DOI：
--
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
M. Menickelly;O. Günlük;J. Kalagnanam;K. Scheinberg
中科院分区：
文献类型：
--
作者：
M. Menickelly;O. Günlük;J. Kalagnanam;K. Scheinberg
几十年来，决策树一直是一类非常流行的预测模型，这是由于它们的可解释性和分类特征的良好性能。然而，它们并不总是鲁棒的，并且倾向于过拟合数据。此外，如果允许它们变大，它们就失去了可解释性。本文提出了一种混合整数规划公式来构造预定大小的最佳决策树。我们考虑到分类特征的特殊结构，并允许在每个节点上进行组合决策（基于特征值的子集）。我们的方法还可以通过阈值处理来处理数值特征。我们表明，可以实现非常好的精度与小树使用中等大小的训练集。我们解决的优化问题是易于处理的现代求解器。
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.