Cost-Sensitive Decision Tree Pruning: Use of the ROC Curve
Andrew P. Bradley, Brian C. Lovell · Australian Joint Conference on Artificial Intelligence · 1995
This paper discusses a revised form of decision tree pruning that is sensitive to the relative costs of the misclassification of examples. A brief overview of existing decision tree pruning methods is given together with the rationale behind these techniques. Then, the two types of misclassifications, false negatives and false positives, are defined and related to three concepts from statistical pattern recognition: the receiver operating characteristic (ROC) curve; statistical hypothesis testing; and the Neyman-Pearson method. Details of the implementation of two cost-sensitive pruning algorithms, based on the well known Pessimistic and Minimum Error pruning techniques, are discussed. Results are then presented for both these techniques on two machine learning datasets and related to ROC curves and the Neyman-Pearson method. Thus we show that decision trees can be made to conform to specified operating criteria given in terms of the probabilities of false negatives and false positives. As a result of this analysis, it is noted that, on the data sets chosen, unequal misclassification costs actually increased the overall accuracy of the classification scheme. It is concluded that the application of the ROC curve, from statistical pattern recognition to machine learning, and to decision tree pruning in particular, can provide increased flexibility and accuracy