Decision Tree Pruning Methods Based On Genetic Algorithms

Decision tree pruning is an often used method for simplifying decision trees. To limit the size of a decision tree while preserve its accuracy, the pruning method removes certain subtrees of the original decision tree. Most decision tree pruning methods visit all subtrees of the given decision tree in top-down or bottom-up order, to determine whether one subtree should be cut according to the accuracy and size of this decision tree.This paper presents a decision tree post-pruning method based on genetic algorithms, which has two stages. In the first stage, the hypothesis space of pruned decision tree is searched by genetic algorithms to find the currently optimal decision trees in different size. In the second stage, the best pruned decision tree is finally selected in the current optimal pruned decision trees, based on their accuracy, size and stability. This decision tree which has the best performance is considered as the finally optimal pruned decision tree.This two-stage pruning method evaluates decision trees with multiple measures which can reduce the effect of the pruning bias in decision tree pruning, and accelerates search speed by using genetic algorithms. The experimental results on UCI datasets show that this method keep well balance between accuracy and size of decision trees, and the optimal pruned decision tree has better performance than that of traditional methods in classification problems.