# Pruning tree using REP

i create a decision tree model using c4.5 algorithm. After create the model, i evaluate model using 10 fold cross validation and classify model using test data to get accuracy. And then I run prune tree with REP.

My question is what data should i use to compare accuracy (after prune and before prune) to decide to remove the leaf? and from where i get the accuracy? using cross validation or classify test data?

The reduce error pruning strategy works in the following way:

1. Train a tree on a training data set
2. Fit a pruning data set (which is different than the training data set) to the tree. What you will have is the tree as was learned at step one, but for each node you will have some instances from the pruning data set.
3. Prune each node from the tree if the misclassification error computed for the instances from the pruned data set is not larger than the original misclassification error rate computed on the training data. For example, suppose that you do a binary classification and you build a tree from a training data set. Now you fit data from the pruning data set and some instances arrives in a given non-leaf node. Suppose that at that node arrives $2$ positive instances and $8$ negative instances. This gives an error rate of $0.2$. Now from that node the instances are split given to the criteria already learned into two children node, one will have $2$ positive instances and $2$ negative instances, and in the other child node goes the other $6$ negative instances. The cumulative error on children is also $0.2$. This means that going further with the split would make no sense, since the data varies a lot. That means you can actually cut the child nodes and make the original non-leaf node a leaf node.

The point of using fresh data (pruning data set) is to check if the split is useful or the noise from data covers the signal given by the split.

To evaluate the performance of both models, before and after pruning, you need another different data set, named validation data. To see way you have to understand that pruning is actually also part of extended training. The only difference than usual learning is that in training with REM you learn how to extend using some data and you learn how to unlearn using some other data.

If you use the same data from training to do pruning you simply do not progress (you can stop early). To use for pruning the data set for testing will invalidate you model selection criteria, since it will almost always be the case that the pruning tree performs better (original tree learns from training data set, pruned tree learn from both). I dare to say that if you would like to asset the prediction error, you will have to use a different data set, or envelope everything in a cross validation.