Variable selection heuristics and optimum decision trees-an experimental study

Given a decision table it is often the case to find among its trees one tree with the minimum, or at least small, number of the nodes of the tree. It is known that a DP based algorithm works to obtain an optimal tree requiring O(3^L) computation (comparisons). On the other hand a top-down method based on a variable selection method (VSM) choosing a variable at each node according to some simple heuristic can be devised to obtain near optimum trees requiring less computation. We briefly review 3 such heuristics Γ_A, Γ_H and Γ_D motivated by the three different standpoints (among them one based on discriminant analysis is new) and their behaviors. Then we present experimental data showing that near optimizations they achieve reflect their respective behaviors. All the heuristics require at most O(L²2^L) operations with O(L2^L) storage, where L is the number of variables of the input table