Cost-sensitive decision tree with probabilistic pruning mechanism

Cost-sensitive decision trees have a great success in building models for classification tasks in data mining and machine learning. Decision tree pruning technique is regarded as an important component of the optimization of decision tree. However, many previous cost-sensitive decision trees researches focus on minimizing the misclassification rate and removing nodes when the cost of the pruned tree is less than the original one. In this paper, we propose an effective method for building cost-sensitive decision tree and a probabilistic pruning mechanism for the decision tree. There are two major contributions of this paper. Firstly, the cost-sensitive decision tree is built to make predictions to minimize the total cost of test costs and different costs associated with different types of misclassification. Compared with existing models, leaves are labeled by minimizing the total cost instead of the majority class. Secondly, we design a probabilistic pruning mechanism where the pruning probability is related to the change of costs around pruning. The pruning results yield worse performance on the training set, but better performance on the testing set. Therefore, the probabilistic pruning mechanism improves the performance of the cost-sensitive decision tree. Experimental results show the efficiency of the probabilistic pruning mechanism for cost-sensitive decision tree.