Anytime induction of decision trees: An iterative improvement approach

Most existing decision tree inducers are very fast due to their greedy approach. In many real-life applications, however, we are willing to allocate more time to get bet-ter decision trees. Our recently introduced LSID3 con-tract anytime algorithm allows computation speed to be traded for better tree quality. As a contract algorithm, LSID3 must be allocated its resources a priori, which is not always possible. In this work, we present IIDT, a general framework for interruptible induction of deci-sion trees that need not be allocated resources a priori. The core of our proposed framework is an iterative im-provement algorithm that repeatedly selects a subtree whose reconstruction is expected to yield the highest marginal utility. The algorithm then rebuilds the sub-tree with a higher allocation of resources. IIDT can also be configured to receive training examples as they be-come available, and is thus appropriate for incremental learning tasks. Empirical evaluation with several hard concepts shows that IIDT exhibits good anytime behav-ior and significantly outperforms greedy inducers when more time is available. A comparison of IIDT to several modern decision tree learners showed it to be superior