470643 c06.qxd 3/8/04 11:12 AM Page 185
Decision Trees 185
The CART Pruning Algorithm
CART is a popular decision tree algorithm first published by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone in 1984. The acronym stands for Classification and Regression Trees. The CART algorithm grows binary trees and continues splitting as long as new splits can be found that increase purity. As illustrated in Figure 6.6, inside a complex tree, there are many simpler subtrees, each of which represents a different trade-off between model complexity and training set misclassification rate. The CART algorithm identifies a set of such subtrees as candidate models. These candidate subtrees are applied to the validation set and the tree with the lowest validation set misclassification rate is selected as the final model.
Creating the Candidate Subtrees
The CART algorithm identifies candidate subtrees through a process of repeated pruning. The goal is to prune first those branches providing the least additional predictive power per leaf. In order to identify these least useful branches, CART relies on a concept called the adjusted error rate. This is a measure that increases each node’s misclassification rate on the training set by imposing a complexity penalty based on the number of leaves in the tree. The adjusted error rate is used to identify weak branches (those whose misclassification rate is not low enough to overcome the penalty) and mark them for pruning.
Figure 6.6 Inside a complex tree, there are simpler, more stable trees.
470643 c06.qxd 3/8/04 11:12 AM Page 186
186 Chapter 6
COMPARING MISCLASSIFICAION RATES ON TRAINING AND
VALIDATION SETS
The error rate on the validation set should be larger than the error rate on the training set, because the training set was used to build the rules in the model.
A large difference in the misclassification error rate, however, is a symptom of an unstable model. This difference can show up in several ways as shown by the following three graphs generated by SAS Enterprise Miner. The graphs represent the percent of records correctly classified by the candidate models in a decision tree. Candidate subtrees with fewer nodes are on the left; with more nodes are on the right. These figures show the percent correctly classified instead of the error rate, so they are upside down from the way similar charts are shown elsewhere in this book.
As expected, the first chart shows the candidate trees performing better and better on the training set as the trees have more and more nodes—the training process stops when the performance no longer improves. On the validation set, however, the candidate trees reach a peak and then the performance starts to decline as the trees get larger. The optimal tree is the one that works on the validation set, and the choice is easy because the peak is well-defined.
This chart shows a clear inflection point in the graph of the percent correctly classified in the validation set.
470643 c06.qxd 3/8/04 11:12 AM Page 187
Decision Trees 187
COMPARING MISCLASSIFICAION RATES ON TRAINING AND
VALIDATION SETS (continued)
Sometimes, though, there is not clear demarcation point. That is, the performance of the candidate models on the validation set never quite reaches a maximum as the trees get larger. In this case, the pruning algorithm chooses the entire tree (the largest possible subtree), as shown in the following illustration:
Proportion Correctly Classified
0.88
0.86
0.84
0.82
0.80
0.78
0.76
0.74
0.72
0.70
0.68
0.66
0.64
0.62
0.60
0.58
0.56
0.54
0.52
0.50
0
20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 380 400 420 440 460 480 500 520 540 560 580
Number of Leaves
In this chart, the percent correctly classified in the validation set levels off early and remains far below the percent correctly classified in the training set.
The final example is perhaps the most interesting, because the results on the validation set become unstable as the candidate trees become larger. The cause of the instability is that the leaves are too small. In this tree, there is an example of a leaf that has three records from the training set and all three have a target value of 1 – a perfect leaf. However, in the validation set, the one record that falls there has the value 0. The leaf is 100 percent wrong. As the tree grows more complex, more of these too-small leaves are included, resulting in the instability seen below:
(continued)
470643 c06.qxd 3/8/04 11:12 AM Page 188
188 Chapter 6
COMPARING MISCLASSIFICAION RATES ON TRAINING AND
VALIDATION SETS (continued)
Proportion of Event in Top Ranks (10%)
1.0
0.9
0.8
0.7
0.6
0.5
0
20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 380 400 420 440 460 480 500 520 540 560 580
Number of Leaves
In this chart, the percent correctly classified on the validation set decreases with the complexity of the tree and eventually becomes chaotic.
The last two figures are examples of unstable models. The simplest way to avoid instability of this sort is to ensure that leaves are not allowed to become too small.
The formula for the adjusted error rate is:
AE( T) = E( T) + α leaf_count( T ) Where α is an adjustment factor that is increased in gradual steps to create new subtrees. When α is zero, the adjusted error rate equals the error rate. To find the first subtree, the adjusted error rates for all possible subtrees containing the root node are evaluated as α is gradually increased. When the adjusted error rate of some subtree becomes less than or equal to the adjusted error rate for the complete tree, we have found the first candidate subtree, α1. All branches that are not part of α1 are pruned and the process starts again. The α1
tree is pruned to create an α2 tree. The process ends when the tree has been pruned all the way down to the root node. Each of the resulting subtrees (sometimes called the alphas) is a candidate to be the final model. Notice that all the candidates contain the root node and the largest candidate is the entire tree.
470643 c06.qxd 3/8/04 11:12 AM Page 189
Decision Trees 189
Picking the Best Subtree
The next task is to select, from the pool of candidate subtrees, the one that works best on new data. That, of course, is the purpose of the validation set.
Each of the candidate subtrees is used to classify the records in the validation set. The tree that performs this task with the lowest overall error rate is declared the winner. The winning subtree has been pruned sufficiently to remove the effects of overtraining, but not so much as to lose valuable information. The graph in Figure 6.7 illustrates the effect of pruning on classification accuracy. The technical aside goes into this in more detail.
Because this pruning algorithm is based solely on misclassification rate, without taking the probability of each classification into account, it replaces any subtree whose leaves all make the same classification with a common parent that also makes that classification. In applications where the goal is to select a small proportion of the records (the top 1 percent or 10 percent, for example), this pruning algorithm may hurt the performance of the tree, since some of the removed leaves contain a very high proportion of the target class.
Some tools, such as SAS Enterprise Miner, allow the user to prune trees optimally for such situations.
Using the Test Set to Evaluate the Final Tree
The winning subtree was selected on the basis of its overall error rate when applied to the task of classifying the records in the validation set. But, while we expect that the selected subtree will continue to be the best performing subtree when applied to other datasets, the error rate that caused it to be selected may slightly overstate its effectiveness. There are likely to be a large number of subtrees that all perform about as well as the one selected. To a certain extent, the one of these that delivered the lowest error rate on the validation set may simply have “gotten lucky” with that particular collection of records. For that reason, as explained in Chapter 3, the selected subtree is applied to a third preclassified dataset that is disjoint with both the validation set and the training set. This third dataset is called the test set. The error rate obtained on the test set is used to predict expected performance of the classification rules represented by the selected tree when applied to unclassified data.
WA R N I N G Do not evaluate the performance of a model by its lift or error rate on the validation set. Like the training set, it has had a hand in creating the model and so will overstate the model’s accuracy. Always measure the model’s accuracy on a test set that is drawn from the same population as the training and validation sets, but has not been used in any way to create the model.