Choosing a Pruned Tree From Validation Results

Why Tree Selection Requires Validation

Pruning produces candidate subtrees with different numbers of terminal nodes. A larger tree can fit more detail in the training data, but that detail may not improve predictions for new observations. To choose among candidate subtrees, compare their performance on validation data that were not used to grow or prune those candidates. The selection is empirical: the validation results identify a preferred candidate under a stated rule, not a tree guaranteed to be best in the population.

For classification, a common comparison measure is the validation misclassification rate: the fraction of validation observations whose predicted class differs from the observed class. This tutorial uses that measure and the minimum-error rule. Other measures, such as a cost-weighted error, would require a separately stated selection rule; the smallest misclassification rate is not automatically best when error costs differ.

Definition: For a candidate tree $T$ evaluated on $n_{\mathrm{val}}$ validation observations, let $e_T$ be the number of observations assigned an incorrect predicted class. Its validation misclassification rate is $$ \widehat{R}_{\mathrm{val}}(T)=\frac{e_T}{n_{\mathrm{val}}}. $$ Under the minimum-validation-error rule, select a candidate with the smallest $\widehat{R}_{\mathrm{val}}(T)$. If multiple candidates tie, a tie-breaker must be specified; a common transparent choice is to select the tied candidate with fewer terminal nodes.

The denominator matters. If every candidate is evaluated on the same validation cases, comparing error counts and comparing error rates gives the same ranking. If denominators differ, compare rates, not raw counts. A valid comparison also requires the candidates to be evaluated on the same target outcome and with the same definition of an error.

Applying the Minimum-Error Rule

The candidate subtrees are often arranged along a pruning sequence, from a relatively small tree to larger subtrees. Their validation rates need not decrease as the number of leaves increases. A more complex tree may improve, worsen, or leave unchanged its predictions on validation observations. Therefore, do not infer the winner from tree size alone.

Worked Example: Finding the Lowest Validation Rate

A hypothetical insurer uses a classification tree to flag policies for a manual review process. Four candidate subtrees have 2, 4, 7, and 10 terminal nodes. Each is evaluated on the same 200 validation policies. Their respective numbers of incorrect classifications are 31, 24, 27, and 25. Apply the minimum-validation-error rule and compare the selected tree with the 10-leaf candidate.

Method. Divide each error count by the common validation size, then select the candidate with the smallest rate.

For the 2-leaf tree, the rate is $31/200=0.155$, or 15.5%. For the 4-leaf tree, it is $24/200=0.120$, or 12.0%. For the 7-leaf tree, it is $27/200=0.135$, or 13.5%. For the 10-leaf tree, it is $25/200=0.125$, or 12.5%.

\begin{array}{c|c|c} \text{Terminal nodes} & \text{Errors out of 200} & \text{Validation rate}\\ 2 & 31 & 0.155\\ 4 & 24 & 0.120\\ 7 & 27 & 0.135\\ 10 & 25 & 0.125 \end{array}

The minimum rate is 0.120, so the 4-leaf tree is selected. Its validation rate is lower than the 10-leaf tree's by $0.125-0.120=0.005$, which is 0.5 percentage points.

Check. The four rates correspond to the stated counts and share a denominator of 200. The smallest count, 24, also gives the smallest rate in this example. Common mistake avoided: assuming that the largest tree must perform best because it has more possible splits. The validation results, not the number of leaves, determine the selection under this rule.

A tie is a real outcome, not a reason to choose whichever tree looks preferable after inspecting the results. State the tie-breaker before interpreting the table. Choosing the smaller tree among tied candidates favors a simpler representation without claiming that it has a lower error rate.

Worked Example: Resolving a Tie by Tree Size

A hypothetical roadside-assistance program classifies incoming service requests into action categories. Three candidate subtrees have 3, 5, and 8 terminal nodes. On the same 160 validation requests, they make 26, 20, and 20 errors, respectively. Use minimum validation error, breaking ties in favor of fewer terminal nodes.

Method. Compute each rate before applying the tie-breaker. For the 3-leaf tree, $26/160=0.1625$, or 16.25%. For each of the 5- and 8-leaf trees, $20/160=0.125$, or 12.5%.

The minimum rate is 0.125, shared by the 5- and 8-leaf candidates. The stated tie-breaker selects the 5-leaf tree because it has fewer terminal nodes. It is not selected because its observed rate is lower: the two tied rates are exactly equal.

Check. The validation size is 160 for each candidate, so both tied counts give the same rate. The 3-leaf tree's rate is $0.1625-0.125=0.0375$, or 3.75 percentage points higher. Common mistake avoided: reporting the 5-leaf tree as having a better validation rate than the 8-leaf tree. It wins only under the specified simplicity tie-breaker.

Why Validation Error Estimates Predictive Error

For a fixed candidate tree, validation error has a direct interpretation if the validation observations are representative of future observations and were not used to construct that tree. Let $p_T$ denote the probability that $T$ misclassifies a new observation from the target population. For each validation observation $i$, define $I_i=1$ if $T$ makes an incorrect prediction and $I_i=0$ otherwise. Then $\widehat{R}_{\mathrm{val}}(T)$ is the average of these indicators.

If the validation observations are independent draws from the target population, and $T$ is fixed independently of them, each indicator has expected value $p_T$. Linearity of expectation gives the justification:

\widehat{R}_{\mathrm{val}}(T)=\frac{1}{n_{\mathrm{val}}}\sum_{i=1}^{n_{\mathrm{val}}} I_i, \qquad E\!\left[\widehat{R}_{\mathrm{val}}(T)\mid T\right] =\frac{1}{n_{\mathrm{val}}}\sum_{i=1}^{n_{\mathrm{val}}}E[I_i\mid T] =\frac{1}{n_{\mathrm{val}}}\sum_{i=1}^{n_{\mathrm{val}}}p_T =p_T.

Thus, for a fixed candidate, the validation rate is an unbiased estimate of its population misclassification probability under those conditions. The result does not say that the observed rate equals the population probability, nor that a validation sample is representative merely because it is called a validation sample. A change in the population, dependence among observations, or leakage of validation outcomes into tree construction can undermine the interpretation.

There is an additional issue when validation results are used to choose the winner. The candidates may each have a reasonable validation estimate when considered separately, but the minimum among several noisy estimates tends to favor a candidate whose result was unusually good by chance. In particular, the minimum observed rate is no greater than any individual rate, so choosing the minimum adapts the choice to the validation sample. The selected rate should not be presented as an unbiased estimate of the selected tree's future error.

This distinction is central: validation results can guide selection, while uncertainty remains about whether the selected tree will perform as well on new data. A single validation split provides only one comparison. The next step in a broader modeling workflow may assess how sensitive the selection is to the data split, but the minimum-error calculation itself does not quantify that sensitivity.

Worked Example: Interpreting a Small Difference and Its Uncertainty

A hypothetical agricultural cooperative classifies fields for follow-up inspection. Three candidate trees with 2, 6, and 9 terminal nodes make 18, 12, and 15 errors on the same 120 validation fields. Select by minimum validation rate, then assess whether the observed margin should be treated as decisive. Use the approximate binomial standard error for the fixed 6-leaf tree's rate, $ \sqrt{\widehat{p}(1-\widehat{p})/n_{\mathrm{val}}} $, as a rough measure of sampling variability, not as a selection rule.

Method. The rates are $18/120=0.150$ for 2 leaves, $12/120=0.100$ for 6 leaves, and $15/120=0.125$ for 9 leaves. The minimum-validation-error rule selects the 6-leaf tree.

The gap between the 9-leaf and 6-leaf rates is $0.125-0.100=0.025$, or 2.5 percentage points. For the selected candidate, the approximate standard error is $ \sqrt{0.100(1-0.100)/120}=\sqrt{0.090/120}=\sqrt{0.00075}\approx0.0274$, or about 2.74 percentage points.

The estimated standard error is of similar magnitude to the 2.5-percentage-point gap. This calculation does not establish that the trees have equal population errors; it shows why a modest observed difference from 120 cases should not be treated as a precise, conclusive separation. The approximation describes the rate for a fixed tree under binomial-style sampling assumptions. It does not correct for selecting the apparent winner on the same validation sample.

Check. The errors and rates agree: $12/120=0.100$, $15/120=0.125$, and $18/120=0.150$. The selected tree has the lowest observed rate, but that fact alone does not prove it has the lowest population error. Common mistake avoided: interpreting “lowest validation error” as “certainly best in the population.” Selection is based on evidence, and its strength depends in part on sample size and the size of the observed differences.

Reading the Results Carefully

A useful comparison table should show the tree size, number of validation errors, validation sample size, and resulting rate. Keeping the counts visible allows a reader to check the arithmetic and judge whether a percentage is based on a substantial or small number of cases. Report rates in a consistent form, such as proportions or percentages, and identify the chosen rule.

Use validation performance for the selection. A training error can keep falling as a tree grows, even when the additional fit does not transfer to new observations.
Compare like with like. Candidate trees should be assessed on the same observations with the same outcome definition and prediction procedure.
Report ties honestly. If rates are equal at the stated precision, apply the declared tie-breaker rather than implying a performance advantage.
Do not overstate small gaps. The minimum observed rate is a selection result, not a guarantee of a meaningful population improvement.
Keep the criterion aligned with the task. If false positives and false negatives have different consequences, ordinary misclassification rate may not represent the relevant objective.

Rounding also affects apparent ties. If rates are displayed only to one decimal percentage point, two distinct underlying rates may look identical. When a decision depends on the ranking, calculate from the exact counts and denominator first, then round for presentation. State the tie-breaker if the exact rates are equal.

Key takeaway: Under the minimum-validation-error rule, calculate each candidate's validation error rate and select the smallest. A stated tie-breaker can resolve equal rates, but neither the winner nor its observed rate removes uncertainty about performance on future data.

Check Your Understanding

For each problem, use the stated selection rule and distinguish the observed validation result from a claim about population performance.

A hypothetical claims team evaluates 3-, 5-, and 7-leaf trees on 250 validation records. Their error counts are 34, 29, and 31. Which tree is selected by minimum validation error, and what is its rate? (Answer: The 5-leaf tree; $29/250=0.116$, or 11.6%.)
Three candidate trees with 4, 6, and 10 terminal nodes make 16, 14, and 14 errors on the same 140 cases. If ties go to the smaller tree, which tree is selected, and what is the validation rate? (Answer: The 6-leaf tree; $14/140=0.100$, or 10.0%.)
A hypothetical equipment-maintenance classifier has candidate validation results of 9 errors out of 80 cases and 10 errors out of 100 cases. Which candidate has the lower validation rate, even though it has more errors? (Answer: The candidate with 10 errors out of 100; its rate is 10.0%, compared with $9/80=11.25\%$.)
On 200 validation cases, a 2-leaf tree makes 27 errors and an 8-leaf tree makes 22 errors. What is the 8-leaf tree's rate, and by how many percentage points is it lower than the 2-leaf tree's rate? Does this alone prove a population advantage? (Answer: $22/200=11.0\%$; it is lower by $13.5\%-11.0\%=2.5$ percentage points; no, the observed comparison alone does not prove a population advantage.)
A fixed candidate tree makes 15 errors on 150 independent validation observations drawn from the target population. Under the fixed-tree and representative-sampling assumptions, what is the estimated misclassification probability, and what is its approximate binomial standard error? (Answer: The estimated rate is $15/150=0.100$; the approximate standard error is $\sqrt{0.100(0.900)/150}=\sqrt{0.0006}\approx0.0245$, or 2.45 percentage points.)

What You'll Learn