Toward a Theoretical Understanding of Why and When Decision Tree Pruning Algorithms Fail

T. Oates and D. Jensen (1999). Toward a theoretical understanding of why and when decision tree pruning algorithms fail. Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99). pp. 372-378.

Abstract

Recent empirical studies revealed two surprising pathologies of several common decision tree pruning algorithms. First, tree size is often a linear function of training set size, even when additional tree structure yields no increase in accuracy. Second, building tress with data in which the class label and the attributes are independent often results in large trees. In both cases, the pruning algorithms fail to control tree growth as one would expect them to. We explore this behavior theoretically by constructing a statistical model of reduced error pruning. The model explains why and when the pathologies occur, and makes predictions about how to lessen their effects. The predictions are operationalized in a variant of reduced error pruning that is shown to control tree growth far better than the original algorithm.

Text

A PDF version of this paper is available.

---

Feedback Fineprint