B0516
Title: Optimal classification and regression trees
Authors: Jack Dunn - Massachusetts Institute of Technology (United States) [presenting]
Dimitris Bertsimas - MIT (United States)
Abstract: Decision tree methods are widely used for classification and regression problems, but one must choose between methods that are interpretable (such as CART) and those with high accuracy (random forests or boosting). We introduce a new approach for constructing Optimal Classification and Regression Trees based on mixed-integer optimization, and develop high-performance heuristics for these problems that offer significant improvements over traditional greedy approaches and run in comparable times. We show in a collection of synthetic and real-world instances that our Optimal Trees significantly improve upon greedy tree methods like CART, giving solutions that are both interpretable and have accuracies comparable to ensemble methods.
