DecisionTree REP( DecisionTree T, ExampleArray S )
{ for ( i = 0 to S.length-1 ) classify( T, S[i] );
return prune( T ); }
void classify( DecisionTree T, Example e )
{ T . t o t a l + ;  i f  ( e . l a b e l == 1 ) T . p o s + + ;
// update node counters if ( !leaf(T) )
if ( T.test(e) == 0 ) classify( T.left, e );
else classify( T.right, e ); }
int prune( DecisionTree T )  // Output classification error after pruning T
{ if ( leaf(T) )
if ( T.label == 1 ) return T.total - T.pos; else return T.pos; else
{ error = prune( T.left ) + prune( T.right );
if ( error < min( T.pos, T.total - T.pos ) )
return error; else
{ replace T with a leaf ;
if ( T.pos > T.total - T.pos )
{ T.label = 1; return T.total - T.pos; }
else
{ T.label = 0; return T.pos; } } } }
Table 1: The REP algorithm. The algorithm first classifies the pruning examples in a top-

down pass using method classify and then during a bottom-up pass prunes the tree using method prune.
Intuitively, it is not clear which is the best-founded strategy for handling empty subtrees, those that do not receive any examples.  On one hand they obtain support from the training set, which usually is more numerous than the pruning set but, on the other hand, the fact that no pruning example corresponds to these parts of the tree would justify drawing the conclusion that these parts of the decision tree were built by chance properties of the training data. In REP, consistently with preferring smaller prunings also otherwise, the latter view is adopted.

The problem of empty subtrees is connected to the problem of small disjuncts in machine learning algorithms (Holte, Acker, & Porter, 1989). A small disjunct covers only a small nmber of the training examples.  Collectively the small disjuncts are responsible for a small number of classification decisions, but they accumulate most of the error of the whole concept. Nevertheless, small disjuncts cannot be eliminated altogether, without adversely affecting other disjuncts in the concept.