Mixed integer linear optimization formulations for learning optimal binary classification trees
Decision trees are powerful tools for classification and regression that
attract many researchers working in the burgeoning area of machine learning.
One advantage of decision trees over other methods is their interpretability,
which is often preferred over other higher accuracy methods that are relatively
uninterpretable. A binary classification tree has two types of vertices: (i)
branching vertices which have exactly two children and where datapoints are
assessed on a set of discrete features; and (ii) leaf vertices at which
datapoints are given a discrete prediction. An optimal binary classification
tree can be obtained by solving a biobjective optimization problem that seeks
to (i) maximize the number of correctly classified datapoints and (ii) minimize
the number of branching vertices. In this paper, we propose four mixed integer
linear optimization (MILO) formulations for designing optimal binary
classification trees: two flow-based formulations and two-cut based
formulations. We provide theoretical comparisons between our proposed
formulations and the strongest flow-based MILO formulation of Aghaei et al.
(2021). We conduct experiments on 13 publicly available datasets to show the
models' ability to scale and the strength of a biobjective approach using
Pareto frontiers. Our code and data are available on GitHub.