Inferring Reduced Ordered Decision Graphs of Minimum Description Length

We propose an heuristic algorithm that induces decision graphs from training sets using Rissanen's minimum description length principle to control the tradeoff between accuracy in the training set and complexity of the hypothesis description. 1 INTRODUCTION Decision graphs can be viewed as a generalization of decision trees, a very successful approach for the inference of classification rules [Breiman et al., 1984, Quinlan, 1986]. The selection of decision graphs instead of decision trees as the representation scheme is important because many concepts of interest require very large decision trees. In particular, the quality of the generalization performed by a decision tree induced from data suffers because of two well known problems [Oliver, 1993]: the replication of subtrees required to represent some concepts and the rapid fragmentation of the training set data when attributes that can take a high number of values are tested at a node. Decision graphs have been proposed as one way ..