On Lookahead Heuristics in Decision Tree Learning

In decision tree learning attribute selection is usually based on greedy local splitting criterion. More extensive search quickly leads to intolerable time consumption. Moreover, it has been observed that lookahead cannot benefit prediction accuracy as much as one would hope. It has even been claimed that lookahead would be mostly harmful in decision tree learning.We present a computationally efficient splitting algorithm for numerical domains, which, in many cases, leads to more accurate trees. The scheme is based on information gain and an efficient variant of lookahead. We consider the performance of the algorithm, on one hand, in view of the greediness of typical splitting criteria and, on the other hand, the possible pathology caused by oversearching in the hypothesis space. In empirical tests, our algorithm performs in a promising manner.