bsnsing: A decision tree induction method based on recursive optimal boolean rule composition
This paper proposes a new mixed-integer programming (MIP) formulation to
optimize split rule selection in the decision tree induction process, and
develops an efficient search algorithm that is able to solve practical
instances of the MIP model faster than commercial solvers. The formulation is
novel for it directly maximizes the Gini reduction, an effective split
selection criterion which has never been modeled in a mathematical program for
its nonconvexity. The proposed approach differs from other optimal
classification tree models in that it does not attempt to optimize the whole
tree, therefore the flexibility of the recursive partitioning scheme is
retained and the optimization model is more amenable. The approach is
implemented in an open-source R package named bsnsing. Benchmarking experiments
on 75 open data sets suggest that bsnsing trees are the most capable of
discriminating new cases compared to trees trained by other decision tree codes
including the rpart, C50, party and tree packages in R. Compared to other
optimal decision tree packages, including DL8.5, OSDT, GOSDT and indirectly
more, bsnsing stands out in its training speed, ease of use and broader
applicability without losing in prediction accuracy.