Optimal classification trees
Optimal classification trees
复制标题
DOI：
10.1007/s10994-017-5633-9
复制
发表时间：
2017-07-01
期刊：
影响因子：
7.5
通讯作者：
Dunn, Jack
中科院分区：
文献类型：
--
作者：
Bertsimas, Dimitris;Dunn, Jack
最先进的决策树方法递归地应用递归来创建每个分离，这可能无法很好地捕捉数据集的底层特征。最优决策树问题试图通过一次创建整个决策树来实现全局最优来解决这个问题。在过去的25年里，整数优化算法的进步加上硬件的改进，使混合整数优化（MIO）的因子加速达到了惊人的8000亿。出于这种加速，我们提出了最佳分类树，一种新的配方的决策树问题，使用现代MIO技术，产生最佳的决策树轴对齐的分裂。我们还显示了丰富的MIO制定适应它给最佳的分类树与超平面，生成最佳的决策树与多变量分裂。综合测试表明，这些方法恢复真正的决策树更接近于算法，驳斥了最佳方法过拟合训练数据的概念。我们在UCI机器学习库的53个数据集样本上对这些方法进行了全面的基准测试。我们建立了这些MIO方法实际上是可解决的真实世界的数据集的大小在1000年代，并给出了平均绝对改善CART的1-2和3-5%的单变量和多变量的情况下，分别在样本外的准确性。此外，我们发现，在CART准确度高并且我们有足够的训练数据的情况下，最佳分类树可能比CART高1.2-1.3%，而当CART准确度或数据集的维数低时，多变量版本的性能比CART高4-7%。
State-of-the-art decision tree methods apply heuristics recursively to create each split in isolation, which may not capture well the underlying characteristics of the dataset. The optimal decision tree problem attempts to resolve this by creating the entire decision tree at once to achieve global optimality. In the last 25 years, algorithmic advances in integer optimization coupled with hardware improvements have resulted in an astonishing 800 billion factor speedup in mixed-integer optimization (MIO). Motivated by this speedup, we present optimal classification trees, a novel formulation of the decision tree problem using modern MIO techniques that yields the optimal decision tree for axes-aligned splits. We also show the richness of this MIO formulation by adapting it to give optimal classification trees with hyperplanes that generates optimal decision trees with multivariate splits. Synthetic tests demonstrate that these methods recover the true decision tree more closely than heuristics, refuting the notion that optimal methods overfit the training data. We comprehensively benchmark these methods on a sample of 53 datasets from the UCI machine learning repository. We establish that these MIO methods are practically solvable on real-world datasets with sizes in the 1000s, and give average absolute improvements in out-of-sample accuracy over CART of 1-2 and 3-5% for the univariate and multivariate cases, respectively. Furthermore, we identify that optimal classification trees are likely to outperform CART by 1.2-1.3% in situations where the CART accuracy is high and we have sufficient training data, while the multivariate version outperforms CART by 4-7% when the CART accuracy or dimension of the dataset is low.