The TREESPLIT Procedure
Pruning
The TREESPLIT procedure creates a classification or regression tree by first growing a tree as described in the section Splitting Criteria. This usually results in a large tree that provides a good fit to the training data. The problem with this tree is its potential for overfitting the data: the tree can be tailored too specifically to the training data and not generalize well to new data. The solution is to find a smaller subtree that results in a low error rate on the validation data.
It is often prohibitively expensive to evaluate the error on all possible subtrees of the full tree. A more practical strategy is to focus on a sequence of nested trees that are obtained by successively pruning leaves from the tree. Figure 21.11 shows an example of pruning in which node 3’s leaves (terminal nodes 4 and 5) are removed to create a nested subtree of the full tree. In the nested subtree, node 3 is now a leaf that contains all the observations that were previously in nodes 4 and 5. This process is repeated until only the root node remains.
Figure 21.11: Tree and Pruned Subtree
Full Tree | Nested Subtree (Node 3 Pruned) |
| |
Many different methods have been proposed for pruning in this manner. These methods address both how to select which nodes to prune to create the sequence of subtrees and how then to select the optimal subtree from this sequence as the final tree. You can use the PRUNE statement in PROC TREESPLIT to specify which pruning method to apply and related options. Several well-known pruning methods, described in this section, are available, and you can override the final selected tree based on your preferences or domain knowledge.
Cost-Complexity Pruning
Cost-complexity pruning is a widely used pruning method that was originally proposed by Breiman et al. (1984). You can request cost-complexity pruning for either a categorical or continuous response variable by specifying the following statement:
prune costcomplexity;
The cost-complexity pruning method helps prevent overfitting by making a trade-off between the complexity (size) of a tree and the error rate Thus large trees with a low error rate are penalized in favor of smaller trees. The cost complexity of a tree T is defined as
where R(T) represents T’s error rate, |T| represents the number of leaves on T, and the complexity parameter represents the cost of each leaf. For a categorical response variable, the misclassification rate is used for the error rate, R(T); for a continuous response variable, the residual sum of squares (RSS), also called the sum of square errors (SSE), is used for the error rate. Only the training data are used to evaluate cost complexity. Breiman et al. (1984) show that for each value of , there is a subtree of T that minimizes cost complexity. When , this is the full tree, . As increases, the corresponding subtree becomes progressively smaller, and the subtrees are in fact nested. Then, at some value of , the root node has the minimal cost complexity for any greater than or equal to that value. Because there are a finite number of possible subtrees, each subtree corresponds to an interval of values of ; that is,
PROC TREESPLIT uses weakest-link pruning, as described by Breiman et al. (1984), to create the sequence of values and the corresponding sequence of nested subtrees, .
Finding the optimal subtree from this sequence is then a question of determining the optimal value of the complexity parameter . This is performed either by using the validation partition (when you use the PARTITION statement to reserve a validation holdout sample) or by using cross validation. In the first case, the subtree in the pruning sequence that has the lowest validation error rate is selected as the final tree. When there is no validation partition, k-fold cross validation can be applied to cost-complexity pruning to select a subtree that generalizes well and does not overfit the training data (Breiman et al. 1984; Zhang and Singer 2010). The algorithm proceeds as follows after creating the sequence of subtrees and values by using the entire set of training data as described earlier:
Randomly divide the training observations into k approximately equal-sized parts, or folds.
Define a sequence of values as the geometric mean of the endpoints of the intervals (that is, ) to represent the intervals.
For each of the k folds, hold out the current fold for validation and use the remaining folds for the training data in the following steps:
Grow a tree as is done using the full training data set with the same splitting criterion.
Using the values that are calculated in step 2, create a sequence of subtrees for each as described in the pruning steps given earlier, but now using as a fixed value for and minimizing the cost complexity, CC(T), to select a subtree at each pruning step.
For each , set to be the subtree that has the minimum cost complexity from the sequence for the jth fold.
Calculate the error for each by using the current (jth) fold (the one omitted from the training).
Now the error rate can be averaged across folds, and the that has the smallest average error is selected. The tree from pruning the complete training data that corresponds to the selected is the final selected subtree.
Because the k-fold cross validation is done sequentially, the process can take a long time for deep trees or for large amounts of data. Consider using the PARTITION statement for pruning large amounts of data.
The TREESPLIT procedure provides two plots that you can use to tune and evaluate the pruning process: the cost-complexity analysis plot and the cost-complexity pruning plot.
When performing cost-complexity pruning with cross validation (that is, no PARTITION statement is specified), it is recommended that you examine the cost-complexity analysis plot that is created by default. This plot displays the error as a function of the complexity parameters , and it uses a vertical reference line to indicate the that minimizes the error. You can use this plot to examine alternative choices for . For example, you might prefer to select a smaller tree that has only a slightly higher error rate. You can specify LEAVES=SE to use the 1-SE rule developed by Breiman et al. (1984).
When you specify validation data by using the PARTITION statement, the cost-complexity pruning plot displays the error rate R(T) as a function of the number of leaves |T| for both the training and validation data. This plot indicates the final selected tree, the tree with the minimum R(T) for the validation data, by using a vertical reference line. Like the cost-complexity analysis plot that is produced when you perform cross validation, this plot can help you identify a smaller tree that has only a slightly higher validation error rate. For an example of this plot, see Output 21.1.5 in Example 21.1: Creating a Binary Classification Tree with Validation Data.
You can use the LEAVES= option in the PRUNE statement to select a tree that has a specified number of leaves. Alternatively, you can use the ALPHA= option in the PRUNE statement to select a tree that has a specified value of the cost-complexity value .
C4.5 Pruning
Quinlan (1987) first introduced pessimistic pruning as a method of pruning classification trees. In this method, the estimate of the true error rate is increased by using a statistical correction in order to prevent overfitting. C4.5 pruning (Quinlan 1993) evolved from pessimistic pruning to employ an even more pessimistic (that is, higher) estimate of the true error rate. An advantage of methods such as pessimistic and C4.5 pruning is that they enable you to use all the data for training instead of requiring a holdout sample. In C4.5 pruning, the upper confidence limit of the true error rate based on the binomial distribution is used to estimate the error rate. PROC TREESPLIT implements a C4.5 algorithm variant that uses the beta distribution in place of the binomial distribution to estimate the upper confidence limit. This pruning method is available only for categorical response variables and it uses only training data for tree pruning. It is implemented by the following statement:
prune C45;
The C4.5 pruning method follows these steps:
Grow a tree from the training data table, and call this full, unpruned tree .
Set , and do the following until is only the root node:
For each leaf (terminal node) in the tree , solve the following equation for (which is the adjusted prediction error rate for leaf l):
Here the confidence level is the value of the CONFIDENCE= option in the PRUNE statement, is the number of failures (misclassified observations) at leaf l, is the number of observations at leaf l, and the function is defined as
Given these values of , use the following formula for the prediction error of tree :
For each node in tree that has only leaves as children, create a candidate subtree by pruning those leaves.
For each candidate subtree, use the equations from steps 2 and 3 to calculate its prediction error. Then select the candidate subtree that has the largest decrease (or smallest increase) in prediction error, . Let this be the next subtree in the sequence, .
Calculate the change in error between each pair of consecutive subtrees, for each i = 1, …, m.
Reduced-Error Pruning
Quinlan’s reduced-error pruning (1987) performs pruning and subtree selection based on minimizing the error rate in the validation partition at each pruning step and then in the overall subtree sequence. The error rate is based on the misclassification rate for a categorical response variable and on the ASE for a continuous response. The following PRUNE statement implements reduced-error pruning:
prune reducederror;
Reduced-error pruning creates a sequence of subtrees from the largest tree, , to the root node, . The subtree that has the smallest validation error is then selected as the final subtree. Pruning could be stopped as soon as the error begins to increase in the validation data as originally described by Quinlan; continuing to prune to create a subtree sequence back to the root node enables you to select a smaller tree that still has an acceptable error rate, as discussed in the next section.
User Specification of Subtree
You might want to select a different tree from the one selected by default when you use cost-complexity or reduced-error pruning to create the sequence of subtrees. For example, you might have a subtree that has a slightly larger error but is smaller, and thus simpler, than the subtree that has the minimum error according to reduced-error pruning. You can override the selected subtree and instead select the subtree that has n leaves and was created by cost-complexity or reduced-error pruning, where n is specified in the LEAVES= option in the PRUNE statement. In addition, if you are using cost-complexity pruning, you can override the selected subtree by using the ALPHA= option in the PRUNE statement.
Alternatively, you might want to select the largest tree that is created in one of the following ways:
Specify LEAVES=ALL in the PRUNE statement to still see the statistics for the sequence of subtrees that are created according to the specified pruning error measure, even though the largest (unpruned) tree is selected as the final subtree.
Specify the following statement to select the largest tree with no pruning performed:
prune none;
Statistics are not calculated and plots are not created for a sequence of subtrees.