Lookahead and Pathology in Decision Tree Induction

The standard approach t decision tree in duction is a top-down greedy agonthm that makes locall} optimal irrevocable decisions at each node of a tree In this paper we empir- •call} study an alternative approach in which the algorithms use one-level loo k a l i e to deride what test to use at a node weystematically compare using a very large number of rfal and artificial data sets the quality of dmsion trees induced by the greedv approach to that of trees induced using lookahead The main observations from our experments are (1) the greedv approach consistently produced trees that were just as at curate as trees produced with the much more expensive lookahead step and (n) we observed manv instances of pathology, l e , lookalnad producrd trees that were both larger and less accurate than trees produced without it .