language: en

Global Tree Optimization: A Non-greedy Decision Tree Algorithm

Kristin P. Bennett
Email bennek@rpi.edu
Department of Mathematical Sciences Rensselaer Polytechnic Institute
Troy, NY 12180

Abstract A non-greedy approach for constructing globally optimal multivariate decision trees with fixed structure is proposed. Previous greedy tree construction algorithms are locally optimal in that they optimize some splitting criterion at each decision node, typically one node at a time. In contrast, global tree optimization explicitly considers all decisions in the tree concurrently. An iterative linear programming algorithm is used to minimize the classification error of the entire tree. Global tree optimization can be used both to construct decision trees initially and to update existing decision trees. Encouraging computational experience is reported.

1 Introduction