Title

A K-Norm Pruning Algorithm For Decision Tree Classifiers Based On Error Rate Estimation

Keywords

Decision tree; Law of succession; Pruning

Abstract

Decision trees are well-known and established models for classification and regression. In this paper, we focus on the estimation and the minimization of the misclassification rate of decision tree classifiers. We apply Lidstone's Law of Succession for the estimation of the class probabilities and error rates. In our work, we take into account not only the expected values of the error rate, which has been the norm in existing research, but also the corresponding reliability (measured by standard deviations) of the error rate. Based on this estimation, we propose an efficient pruning algorithm, called k-norm pruning, that has a clear theoretical interpretation, is easily implemented, and does not require a validation set. Our experiments show that our proposed pruning algorithm produces accurate trees quickly, and compares very favorably with two other well-known pruning algorithms, CCP of CART and EBP of C4.5. © 2008 Springer Science+Business Media, LLC.

Publication Date

4-1-2008

Publication Title

Machine Learning

Volume

71

Issue

1

Number of Pages

55-88

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s10994-007-5044-4

Socpus ID

40849088010 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/40849088010

This document is currently not available here.

Share

COinS