《any time of decision tree》.pdf

Journal of Machine Learning Research 8 (2007) 891-933 Submitted 1/06; Revised 12/06; Published 5/07 Anytime Learning of Decision Trees Saher Esmeir E SAHER @C S .TECHN ION .AC .IL Shaul Markovitch SHAULM @C S .TECHN ION .AC .IL Department of Computer Science Technion—Israel Institute of Technology Haifa 32000, Israel Editor: Claude Sammut Abstract The majority of existing algorithms for learning decision trees are greedy—a tree is induced top- down, making locally optimal decisions at each node. In most cases, however, the constructed tree is not globally optimal. Even the few non-greedy learners cannot learn good trees when the concept is difficult. Furthermore, they require a fixed amount of time and are not able to generate a better tree if additional time is available. We introduce a framework for anytime induction of decision trees that overcomes these problems by trading computation speed for better tree quality. Our proposed family of algorithms employs a novel strategy for evaluating candidate splits. A biased sampling of the space of consistent trees rooted at an attribute is used to estimate the size of the minimal tree under that attribute, and an attribute with the smallest expected tree is selected. We present two types of anytime induction algorithms: a contract algorithm that determines the sample size on the basis of a pre-given allocation of time, and an interruptible algorithm that starts with a greedy tree and continuously improves subtrees by additional sampling. Experimental results indicate that, for several hard concepts, our proposed approach exhibits good any