A New Method for Constructing Decision Tree Based on Rough Set Theory

One of the keys to constructing decision tree model is to choose standard for testing attribute, for the criteria of selecting test attributes influences the classification accuracy of the tree. There exists diversity choosing standards for testing attribute based on entropy, Bayesian, and so on. In this paper, the degree of dependency of decision attribute on condition attribute, based on rough set theory, is used as a heuristic for selecting the attribute that will best separate the samples into individual classes. The results of example and experiments show that compared with the entropy-based approach, our approach is a better way to select nodes for constructing decision tree.

1. Introduction

Decision tree induction is a well-known discipline in Machine Learning presented by Quinlan in 1986 [4]. The basic algorithm for decision tree induction is a greedy algorithm that constructs decision trees in a top-down recursive divide-and-conquer manner. In the process of constructing a tree, the criteria of selecting test attributes influences the classification accuracy of the tree. Presently, there have many criteria for choosing the test attribute in building decision tree, such as ID3 [4] and C4.5 [5] which use an entropy-based measure known as information gain as a heuristic for selecting the attribute. However, the main problem of these algorithms is that a sub-tree may repeat several times in a decision tree, and that an attribute may be used for several times in some certain paths of the tree, which degrades the efficiency of classification.