The Accuracy of Decision Tree Induction in a Noisy Domain for Expert Systems Construction

Many studies have shown that decision tree induction methods could be used to determine rules for expert systems. Pruning techniques are often used to increase the accuracy of an induced decision tree over the instance space. While recent results of decision tree induction show that large samples may be required to induce a decision tree of small error, recent expository studies have used very small sample sizes. In such cases it is of value to obtain a posterior evaluation of the error of the induced concept. In this paper we give three methods to estimate the accuracy of a pruned decision tree. The first method assumes uniform prior distribution. For those cases where uniform prior is not appropriate, we develop a method to obtain appropriate prior using a beta distribution. Finally, we provide a general bound which requires no assumption over the instance space. These results can be used when a pruned decision tree is used to classify the original domain or another close domain.