# An Analysis Of Reduced Error Pruning

## Tapio  E Lo Maa Matti Kääriäinen

Department of Computer Science P. O. Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland ELOMAA@CS. HELSINKI. FI
MATTI. KAA RIAINEN@CS . HELSINKI. FI

## Abstract

Top down induction of decision trees has been observed to suffer from the inadequate functioning of the pruning phase. In particular, it is known that the size of the resulting tree grows linearly with the sample size, even though the accuracy of the tree does not improve. Reduced Error Pruning is an algorithm that has been used as a representative technique in attempts to explain the problems of decision tree learning.

In this paper we present analyses of Reduced Error Pruning in three different settings.

First we study the basic algorithmic properties of the method, properties that hold independent of the input decision tree and pruning examples. Then we examine a situation that intuitively should lead to the subtree under consideration to be replaced by a leaf node, one in which the class label and attribute values of the pruning examples are independent of each other. This analysis is conducted under two different assumptions. The general analysis shows that the pruning probability of a node fitting pure noise is bounded by a function that decreases exponentially as the size of the tree grows. In a specific analysis we assume that the examples are distributed uniformly to the tree. This assumption lets us approximate the number of subtrees that are pruned because they do not receive any pruning examples.

This paper clarifies the different variants of the Reduced Error Pruning algorithm, brings new insight to its algorithmic properties, analyses the algorithm with less imposed assumptions than before, and includes the previously overlooked empty subtrees to the analysis.

## 1. Introduction

Decision tree learning is usually a two-phase process (Breiman, Friedman, Olshen, & Stone, 1984; Quinlan, 1993). First a tree reflecting the given sample as faithfully as possible is constructed. If no noise prevails, the accuracy of the tree is perfect on the training examples that were used to build the tree. In practice, however, the data tends to be noisy, which may introduce contradicting examples to the training set. Hence, 100% accuracy cannot necessarily be obtained even on the training set. In any case, the resulting decision tree is overfitted to the sample; in addition to the general trends of the data, it encodes the peculiarities and particularities of the training data, which makes it a poor predictor of the class label of future instances. In the second phase of induction, the decision tree is pruned in order to reduce its dependency on the training data. Pruning aims at removing from the tree those parts that are likely to only be due to the chance properties of the training set.

The problems of the two-phased top-down induction of decision trees are well-known and have been extensively reported (Catlett, 1991; Oates & Jensen, 1997, 1998). The size