Learning optimal decision trees
Siegfried Nijssen, Élisa Fromont · Lirias · 2007
All currently known algorithms for learning decision trees are based on the paradigm of heuristic top-down induction. Although the results of these algorithms are usually good, there is no guarantee that the resulting trees are really as small, accurate or shallow as possible. In this paper, we introduce an algorithm for inducing the smallest most accurate decision tree on training data. This algorithm allows us to find out how well heuristic algorithms approximate truly optimal decision trees. 1.