New algorithm of simplifying the ID3 decision tree
Shi Bin-ning · Journal of Hefei University of Technology · 2004
Decision tree simplification is a significant branch in the study of decision-tree learning algorithms. Based on the decision tree constructed with the ID3 algorithm,a new and efficient algorithm is presented to simplify the decision tree. In the algorithm,each node of the ID3 decision tree is traversed in preorder,and then its subtrees are compared and, if the root attributes of each subtree are the same and some corresponding branches of all the subtrees are identical, the hierarchical relationship of the correlative attributes in the decision tree can be changed and the identical branches can be merged respectively. The algorithm reduces the depth and the width of the decision tree and the number of leaves and thus decreases the tree size. Especially for the inductive learning of logic expressions, the decision tree after being simplified is apparently better than the original one.