Why Cross-Validation Helps Select a Pruned Tree
A classification tree can be pruned to several candidate sizes, such as 2, 4, or 6 terminal nodes. A single validation split can compare these candidates, but its conclusion may depend on which observations happen to fall into that one validation set. K-fold cross-validation repeats the held-out evaluation across several splits, so every observation in the available training data is used for validation once.
The purpose is to estimate how well each candidate pruning level predicts observations not used to fit that fold’s tree. Cross-validation does not make the error rate exact, and it does not turn training error into validation error. It provides a data-based comparison for selecting a pruning level. The calculation below uses the ordinary misclassification rate; a different loss measure must be specified if errors have unequal consequences.
The same candidate sizes should be compared across folds. In practice, the tree grown and pruned within a fold must be based only on that fold’s training portion. If a candidate size cannot be attained in every fold, the comparison rule needs to be specified in advance—for example, by using a common set of feasible sizes or a consistent pruning parameter. A candidate must not be evaluated on a fold that influenced how its tree was fitted.
How to Aggregate Fold Errors
A fold-specific error rate is \(r_{km}=M_{km}/n_k\). The pooled cross-validation error is a weighted mean of these rates, with fold sizes as weights:
This follows directly from \(M_{km}=n_k r_{km}\). Substituting into the pooled definition gives $$ \frac{\sum_k M_{km}}{\sum_k n_k} =\frac{\sum_k n_k r_{km}}{\sum_k n_k}. $$ Thus, a fold containing 50 observations contributes more to the record-level error rate than a fold containing 20 observations. The unweighted mean, \(\sum_k r_{km}/K\), instead gives each fold the same influence regardless of its size. It can be a meaningful summary when the target is explicitly an average across folds, but it is not generally the pooled record-level misclassification rate.
Worked Example: Pooling Errors Across Unequal Folds
A hypothetical insurer uses a tree to classify applications into two review categories. The training data are divided into folds of 20, 30, and 50 applications. For each candidate leaf count, the listed values are the numbers misclassified in the held-out fold. Choose the candidate with the smallest pooled cross-validation error, and compare that result with the unweighted mean of fold rates.
| Candidate leaves | Errors in 20-record fold | Errors in 30-record fold | Errors in 50-record fold |
|---|---|---|---|
| 2 | 4 | 9 | 12 |
| 4 | 3 | 6 | 8 |
| 6 | 2 | 7 | 9 |
Method. Add the held-out misclassifications for each candidate and divide by the total number of validation records, \(20+30+50=100\).
For 2 leaves, the total is \(4+9+12=25\), so the pooled error is \(25/100=0.2500\). For 4 leaves, the total is \(3+6+8=17\), giving \(17/100=0.1700\). For 6 leaves, the total is \(2+7+9=18\), giving \(18/100=0.1800\). The pooled criterion selects the 4-leaf tree.
Now calculate the unweighted fold-rate means. For 4 leaves, the rates are \(3/20=0.15\), \(6/30=0.20\), and \(8/50=0.16\); their mean is \((0.15+0.20+0.16)/3=0.1700\). For 6 leaves, they are \(2/20=0.10\), \(7/30=0.2333\ldots\), and \(9/50=0.18\); their mean is approximately \(0.1711\). For 2 leaves, the rates are \(0.20\), \(0.30\), and \(0.24\), with mean approximately \(0.2467\). The unweighted mean also selects 4 leaves in this example, although unweighted averaging can give a different selection in other examples.
Check. The pooled rates are the weighted fold-rate averages: for 4 leaves, \((20(0.15)+30(0.20)+50(0.16))/100=0.1700\). The calculations use all 100 held-out records exactly once. The common mistake this example avoids is claiming that an unweighted mean must select a different tree; its effect depends on the fold rates and sizes.
The Target Determines the Appropriate Average
The pooled rate answers: among all held-out records combined, what fraction were misclassified? An unweighted fold-rate mean answers a different question: what is the average of the \(K\) fold-specific rates when each fold counts equally? These summaries coincide when all folds have the same size. With unequal folds, they need not coincide, so state which quantity is being used.
Worked Example: When Pooled and Unweighted Rankings Differ
A hypothetical research team compares two pruned trees using three validation folds of sizes 10, 30, and 60. Candidate A misclassifies 0, 9, and 30 records, respectively. Candidate B misclassifies 2, 12, and 24. Find both aggregation summaries and select a tree using the pooled record-level error.
Candidate A. Its fold rates are \(0/10=0.00\), \(9/30=0.30\), and \(30/60=0.50\). Its total errors are \(0+9+30=39\) among \(10+30+60=100\) records, so its pooled error is \(39/100=0.3900\). Its unweighted mean is \((0.00+0.30+0.50)/3=0.2667\), rounded to four decimal places.
Candidate B. Its fold rates are \(2/10=0.20\), \(12/30=0.40\), and \(24/60=0.40\). Its total errors are \(2+12+24=38\), so its pooled error is \(38/100=0.3800\). Its unweighted mean is \((0.20+0.40+0.40)/3=0.3333\), rounded to four decimal places.
For the stated record-level objective, choose candidate B because \(0.3800<0.3900\). The unweighted fold means rank candidate A lower instead. Neither calculation is an arithmetic error: they summarize different targets. The common mistake is to call the unweighted mean the pooled error when fold sizes differ.
Check. The pooled rates can also be recovered by weighting the fold rates: candidate A gives \((10(0.00)+30(0.30)+60(0.50))/100=0.3900\); candidate B gives \((10(0.20)+30(0.40)+60(0.40))/100=0.3800\). Thus the selected tree follows the criterion requested.
Selecting a Pruning Level Without Leakage
For each candidate size, the fold-specific tree is trained on the other \(K-1\) folds and scored only on its held-out fold. The predicted class label must follow the same classification rule for every candidate and fold. If the model uses a classification threshold or a preprocessing step, that rule or step must be determined without using the held-out fold. Otherwise, information from the validation observations can influence the predictions being evaluated.
After comparing the pooled errors, select the candidate with the smallest value. If multiple candidates have exactly the same minimum, a simple pre-specified tie rule is to choose the smaller tree. That rule favors the less complex candidate among those with equal estimated error; it does not prove that the smaller tree will always perform better. If errors are close but not identical, the smallest-error rule still selects the numerical minimum unless another selection rule was established beforehand.
Choose candidate pruning levels and partition the available training data. Use the same folds to compare all candidates.
For fold \(k\), fit and prune each candidate using the other \(K-1\) folds only. Do not use the held-out fold to choose splits, preprocessing, or class-label rules.
Predict the labels in \(F_k\), count its misclassifications, and repeat for every fold and candidate.
Pool the misclassification counts and divide by the total held-out records. Select the candidate with the smallest stated criterion, applying a pre-specified tie rule if needed.
Once the pruning level is selected, fit the chosen tree using the full training data. Keep a separate test set untouched if an independent final performance assessment is required.
Worked Example: Selecting a Size and Refitting the Tree
A hypothetical safety program classifies equipment inspections as routine or priority. A training set of 100 inspections is split into four folds of 25. For each fold, the tree is trained on the other 75 inspections. The following counts are the held-out misclassifications at three candidate leaf counts.
| Candidate leaves | Fold 1 errors | Fold 2 errors | Fold 3 errors | Fold 4 errors |
|---|---|---|---|---|
| 2 | 6 | 5 | 6 | 4 |
| 4 | 4 | 5 | 4 | 4 |
| 6 | 3 | 5 | 5 | 4 |
Method. Since each fold contains 25 records, there are \(4(25)=100\) held-out predictions per candidate. Sum each row and divide by 100. The 2-leaf candidate has \(6+5+6+4=21\) errors, so its cross-validation error is \(21/100=0.21\). The 4-leaf candidate has \(4+5+4+4=17\) errors, giving \(17/100=0.17\). The 6-leaf candidate has \(3+5+5+4=17\) errors, also giving \(17/100=0.17\).
The minimum is tied between 4 and 6 leaves. Applying the stated tie rule of choosing the smaller candidate selects 4 leaves. The fold-specific 4-leaf trees were each trained on 75 records; after selection, fit the selected pruning level on all 100 training records. The value \(0.17\) is a cross-validation estimate used in selection, not the training error of that final refitted tree.
Check. The four fold rates for the selected candidate are \(4/25=0.16\), \(5/25=0.20\), \(4/25=0.16\), and \(4/25=0.16\). Their mean is \((0.16+0.20+0.16+0.16)/4=0.17\), matching \(17/100\). The common mistake this example avoids is selecting 6 leaves because its first fold has fewer errors: selection uses the total criterion, and the tie rule then favors 4 leaves.
What the Cross-Validation Result Does—and Does Not—Say
Cross-validation uses held-out predictions within the available training data to compare candidate pruning levels. Once the minimum is selected, however, that minimum was chosen partly because it performed well on these folds. Its reported error can therefore be optimistic as an assessment of the selected model’s future performance: selection has used the same cross-validation results being reported. For an independent final assessment, evaluate the refitted model on a test set that played no part in fitting, preprocessing, or selecting the pruning level.
The fold partition also matters. The usual interpretation assumes observations are representative of the prediction setting and that the fold assignments do not create inappropriate dependence between training and validation records. For example, if multiple records come from the same individual, placing related records on both sides of a fold split may make validation performance look better than performance on genuinely new individuals. The split should match the intended prediction task.
Misclassification rate gives every observation the same cost for a correct or incorrect label. If the application assigns different consequences to false positives and false negatives, use a clearly defined loss for each held-out prediction and aggregate those losses consistently instead. The candidate selected by a different criterion may differ. In either case, keep the central distinction intact: fit within the training portion, evaluate on the held-out portion, and select using the declared aggregate criterion.
Check Your Understanding
For each problem, use the stated selection criterion and distinguish held-out error from training error.
- Three equal folds each contain 20 records. A 3-leaf tree makes 4, 5, and 3 errors; a 5-leaf tree makes 3, 4, and 4 errors. Compute each pooled error and choose the lower-error candidate. (Answer: 3 leaves: \(12/60=0.2000\); 5 leaves: \(11/60=0.1833\); select 5 leaves.)
- Folds contain 12, 28, and 60 records. Candidate A has 1, 8, and 24 held-out errors; candidate B has 3, 7, and 21. Compute pooled errors and select by pooled error. (Answer: A: \(33/100=0.3300\); B: \(31/100=0.3100\); select B.)
- Two folds contain 10 and 30 records. A candidate makes 1 and 9 errors. Find the pooled rate and the unweighted mean of fold rates. (Answer: pooled \(10/40=0.2500\); unweighted mean \((0.1000+0.3000)/2=0.2000\).)
- A team uses the held-out fold’s labels to decide which predictors to keep before fitting the fold’s tree. Is its fold error a valid held-out estimate under the procedure described here? State the correction. (Answer: No; predictor selection must be done using only that fold’s training portion, then predictions are evaluated on the untouched held-out fold.)
- Four equal folds produce pooled errors of 14% for a 3-leaf candidate, 12% for a 5-leaf candidate, and 12% for a 7-leaf candidate. With a tie rule that selects the smaller tree among tied minima, which size is selected, and what does 12% represent? (Answer: Select 5 leaves; 12% is the minimum cross-validation error used for selection, not an independent test-set assessment.)