Abstract:

At present, the research on pruning optimization of the decision tree focuses on prepruning and postpruning algorithms. However, these pruning algorithms are usually effective for the traditional decision tree classification algorithms. The research on the pruning optimization algorithm integrated with cost sensitive learning has no better results. We design a new pruning algorithm based on the benefit cost analysis theory of economics. We define the concepts of cost gains matrix and unit cost gains. Furthermore, the class labels of decision tree leaves are distributed on the principle of maximizing the gains of unit cost. Pruning the decision tree based on the unit cost gains can solve practical problems well. Experimental results show that the proposed algorithm outperforms current pruning algorithms, which can generate a smaller decision tree and which has a better classification effect in comparison with the REP and EBP algorithms.

Key words: cost;gains;pruning algorithm;decision tree