of the tree grows linearly with the size of the training set, even though after a while no accuracy is gained through the increased tree complexity. Obviously, pruning is intended to fight this effect. Another defect is observed when the data contains no relevant attributes; i.e., when the class labels of the examples are independent of their attribute values. Clearly, a single-node tree predicting the majority label of the examples should result in this case, since no help can be obtained by querying the attribute values. In practice, though, often large decision trees are built from such data.

Many alternative pruning schemes exist (Mingers, 1989a; Esposito, Malerba, & Semeraro, 1997; Frank, 2000.  They differ, e.g., on whether a single pruned tree or a series of pruned trees is produced, whether a separate set of pruning examples is used, which aspects (classification error and tree complexity) are taken into account in pruning decisions, how these aspects are determined, and whether a single scan through the tree suffices or whether iterative processing is required. The basic pruning operation that is applied to the tree is the replacement of an internal node together with the subtree rooted at it with a leaf. Also more elaborated tree restructuring operations are used by some pruning techniques (Quinlan, 1987, 1993). In this paper, the only pruning operation that is considered is the replacement of a subtree by the majority leaf, i.e., a leaf labeled by the majority class of the examples reaching it. Hence, a pruning of a tree is a subtree of the original tree with just zero, one, or more internal nodes changed into leaves.

Reduced Error Pruning (subsequently REP for short) was introduced by Quinlan (1987) in the context of decision tree learning.  It has subsequently been adapted to rule set learning as well (Pagallo & Haussler, 1990; Cohen, 1993). REP is one of the simplest pruning strategies.

In practical decision tree pruning REP is seldom used, because it has the disadvantage of requiring a separate set of examples for pruning. Moreover, it is considered too aggressive a pruning strategy that overprunes the decision tree, deleting relevant parts from it (Quinlan, 1987; Esposito et al., 1997). The need for a pruning set is often considered harmful because of the scarceness of the data. However, in the data mining context the examples are often abundant and setting a part of them aside for pruning purposes presents no problem.

Despite its shortcomings REP is a baseline method to which the performance of other pruning algorithms is compared (Mingers, 1989a; Esposito, Malerba, & Semeraro, 1993; Esposito et al., 1997). It presents a good starting point for understanding the strengths and weaknesses of the two-phased decision tree learning and offers insight to decision tree pruning. REP has the advantage of producing the smallest pruning among those that are the most accurate with respect to the pruning set. Recently, Oates and Jensen (1999) analyzed REP in an attempt to explain why and when decision tree pruning fails to control the growth of the tree, even though the data do not warrant the increased size. We approach the same subject, but try to avoid restricting the analysis with unnecessary assumptions. We also consider an explanation for the unwarranted growth of the size of the decision tree.

In this paper we analyze REP in three different settings. First, we explore the basic algorithmic properties of REP , which apply regardless of the distribution of examples presented to the learning algorithm. Second, we study, in a probabilistic setting, the situation in which the attribute values are independent of the classification of an example. Even though this pure noise fitting situation is not expected to arise when the whole pruning set is considered, it is encountered at lower levels of the tree, when all relevant attributes have already been exhausted. We further assume that all subtrees receive at least one pruning example, so that