A Scalable MIP-based Method for Learning Optimal Multivariate Decision\n Trees

Abstract

Several recent publications report advances in training optimal decision\ntrees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in\ninteger programming and a growing interest in addressing the inherent\nsuboptimality of heuristic approaches such as CART. In this paper, we propose a\nnovel MIP formulation, based on a 1-norm support vector machine model, to train\na multivariate ODT for classification problems. We provide cutting plane\ntechniques that tighten the linear relaxation of the MIP formulation, in order\nto improve run times to reach optimality. Using 36 data-sets from the\nUniversity of California Irvine Machine Learning Repository, we demonstrate\nthat our formulation outperforms its counterparts in the literature by an\naverage of about 10% in terms of mean out-of-sample testing accuracy across the\ndata-sets. We provide a scalable framework to train multivariate ODT on large\ndata-sets by introducing a novel linear programming (LP) based data selection\nmethod to choose a subset of the data for training. Our method is able to\nroutinely handle large data-sets with more than 7,000 sample points and\noutperform heuristics methods and other MIP based techniques. We present\nresults on data-sets containing up to 245,000 samples. Existing MIP-based\nmethods do not scale well on training data-sets beyond 5,500 samples.\n