

![0_image_0.png](0_image_0.png)

pruning examples to label pruned leaves. Using training examples and proceeding bottomup, observe that neither subtree is pruned, since the left one replaced with a negative leaf would make two mistakes instead of the original one mistake. Similarly, the right subtree replaced with a positive leaf would result in an increased number of classification errors.

Nevertheless, the root node—even though its subtrees have not been pruned —can still be pruned.

When pruning examples are used to label pruned leaves, a node with two non-trivial subtrees cannot be pruned unless both its subtrees are collapsed into leaves.  The next section will prove this. In the tree of Figure 1 both subtrees would be collapsed into zeroerror leaves. However, in this case the root node will not be pruned.

A further possibility for labeling the leaf nodes would be to take both training and pruning examples into account in deciding the label of a pruned leaf.  Depending on the relation of the numbers of training and pruning examples this strategy resembles one or the other of the above-described approaches. Usually the training examples are more numerous than the pruning examples, and will thus dominate. In practice it is impossible to discern this labeling strategy from that of using the majority of training examples.

## 2.3 Empty Subtrees

Since REP uses different sets of examples to construct and to prune a decision tree, it is possible that some parts of the tree do not receive any examples in the pruning phase. Such parts of the decision tree, naturally, can be replaced with a single leaf without changing the number of classification errors that the tree makes on the pruning examples. In other words, subtrees that do not obtain any pruning examples are always pruned. Quinlan (1987) already noted that the parts of the original tree that correspond to rarer special cases, which are not represented in the pruning set, may be excised.