A Fast Way to Produce Optimal Fixed-Depth Decision Trees.
Alireza Farhangfar, Russell Greiner, Martin Zinkevich · 2008
Decision trees play an essential role in many classification tasks. In some circumstances, we only want to consider fixeddepth trees. Unfortunately, finding the optimal depth-d decision tree can require time exponential in d. This paper presents a fast way to produce a fixed-depth decision tree that is optimal under the Naïve Bayes (NB) assumption. Here, we prove that the optimal depth-d feature essentially depends only on the posterior probability of the class label given the tests previously performed, but not on either the identity nor the outcomes of these tests. We can therefore precompute, in a fast pre-processing step, which features to use at the final layer. This results in a speedup of O(n / log n), where n is the number of features. We apply this technique to learning fixed-depth decision trees from standard datasets from the UCI repository, and find this model improves the computational cost significantly. Surprisingly, this approach still yields relatively high classification accuracy, despite the NB assumption. 1