
## 2.4 The Analyzed Pruning Algorithm

Let us briefly reiterate the details of the REP algorithm that is analyzed subsequently. As already stated, the control strategy of the algorithm is the single-sweep bottom-up processing. First, a top-down traversal drives the pruning examples through the tree to the appropriate leaves. The counters of the nodes en route are updated. Second, during a bottom-up traversal the pruning operations indicated by the classification errors are executed. The errors can be determined on the basis of the node counter values. In the bottom-up traversal each node is visited only once. The pruned leaves are labeled by the majority of the pruning set (see Table 1).

## 3. Previous Work

Pruning of decision trees has recently received a lot of analytical attention; existing pruning methods have been analyzed (Esposito et al., 1993, 1997; Oates & Jensen, 1997, 1998, 199) and new analytically-founded pruning techniques have been developed (Helmbold & Schapire, 1997; Pereira & Singer, 1999; Mansour, 1997; Kearns & Mansour, 1998). Also many empirical comparisons of pruning have appeared (Mingers, 1989a; Malerba, Esposito,
& Semeraro, 1996; Frank, 2000). In this section we review earlier work that concerns the REP algorithm. Further related research is considered in Section 7.

Esposito et al. (1993) viewed the REP algorithm, among other pruning methods, as a sseerch process in the state space. In addition to noting that the iterative version of REP cannot produce the optimal result required by Quinlan (1987), they also observed that even though REP is a linear-time algorithm in the size of the tree, with respect to the height of the tree REP requires exponential time in the worst case. In their subsequent comparative analysis Esposito et al. (1997) sketched a proof for Quinlan's (1987) claim that the pruning produced by REP is the smallest among the most accurate prunings of the given decision tree.

The bias of REP was briefly examined by Oates and Jensen (1997, 1998). They observed that the error, r L , of the best majority leaf that could replace a subtree T only depends on (the class distribution of) the examples that reach the root N of T . In other words, the tree structure above T and N decides the error r L . Let r T denote the error of the subtree T at the moment when the pruning sweep reaches N ; i.e., when some pruning may already have taken place in T . All pruning operations performed in T have led either r T to decrease from the initial situation or to stay unchanged. In any case, pruning that has taken place in T
potentially decreases rr, but does not affect rL. Hence, the probability that rr < rL —i.e., that T will not be pruned - increases through pruning in T . This error propagation bias is inherent to REP . Oates and Jensen (1997, 1998) conjecture that the larger the original tree and the smaller the pruning set, the larger this effect, because a large tree provides more pruning opportunities and the high variance of a small pruning set offers more random chances for r t ≤ r t . Subsequently we study some of these effects exactly.

In a follow-up study Oates and Jensen (1999) used REP as a vehicle for explaining the problems that have been observed in the pruning phase of top-down induction of decision trees. They analyzed REP in a situation in which the decision node under consideration fits noise —i.e., when the class of the examples is independent of the value of the attribute tested in the node at hand - and built a statistical model of REP in this situation. It indicates,