Deriving the Pruning Threshold for a Subtree

Why a Pruning Threshold Can Be Calculated

A classification tree can fit the training data more closely as it grows, but retaining more terminal leaves also makes the model more complex. Cost-complexity pruning expresses this trade-off by adding a penalty for the number of leaves to a tree’s risk. For a particular subtree, the key comparison is local: does that subtree have a lower penalized cost than replacing it with a single leaf?

The threshold is the penalty value at which those two choices tie. Below the threshold, a subtree that improves the unpenalized risk enough can remain preferable; above it, the penalty for its extra leaves can make the single leaf preferable. The calculation is exact once the risk measure and the number of leaves are specified.

Definition: Let $T_t$ be a subtree rooted at node $t$, and let $L_t$ be its number of terminal leaves. Let $R(T_t)$ be the risk of the subtree, calculated by adding the risks of its terminal leaves. Let $R(t)$ be the risk when the whole subtree is replaced by a single leaf at $t$. For a nonnegative complexity penalty $\alpha$, the two local penalized costs are $$ C_\alpha(T_t)=R(T_t)+\alpha L_t \qquad\text{and}\qquad C_\alpha(t)=R(t)+\alpha. $$

The risk may be the number of training misclassifications, the proportion misclassified, or a total based on specified misclassification costs. The risk measure must be the same on both sides of the comparison. Consequently, the units of $\alpha$ match the units of risk per additional leaf: for example, errors per leaf if risk is an error count, or loss units per leaf if risk is a weighted loss.

In this tutorial, a leaf predicts the class that gives it the smallest risk under the chosen risk measure. Thus $R(t)$ is the risk of the best single-leaf prediction at $t$, not the risk of an arbitrary prediction. A proper subtree has at least two leaves, so $L_t-1$ is positive. If the node is already a leaf, there is no subtree-versus-leaf comparison to make.

Deriving the Threshold

The threshold follows by setting the two penalized costs equal. The derivation also shows why the denominator is the number of leaves removed, rather than the number of leaves in the original subtree.

Write the equality.
At the tie, $C_\alpha(T_t)=C_\alpha(t)$, so $R(T_t)+\alpha L_t=R(t)+\alpha$.

Collect the penalty terms.
Subtract $R(T_t)$ and $\alpha$ from both sides to obtain $\alpha(L_t-1)=R(t)-R(T_t)$.

Solve for the tie value.
Since $L_t>1$, divide by $L_t-1$. The threshold is the risk improvement from keeping the subtree, divided by the number of additional leaves it uses.

\alpha_t = \frac{R(t)-R(T_t)}{L_t-1}

This equality is a comparison of two fixed risks plus a penalty, not a claim about future data. To see which choice has lower cost on either side of the threshold, subtract the single-leaf cost from the subtree cost:

C_\alpha(T_t)-C_\alpha(t) = R(T_t)-R(t)+\alpha(L_t-1) = (L_t-1)(\alpha-\alpha_t).

Because $L_t-1>0$, the sign of this difference is the sign of $\alpha-\alpha_t$. If $\alpha<\alpha_t$, the subtree has lower penalized cost; if $\alpha=\alpha_t$, the costs are equal; and if $\alpha>\alpha_t$, the collapsed leaf has lower penalized cost. These conclusions assume the same risk calculation is used for the subtree and the collapsed leaf.

If $R(t)>R(T_t)$, then $\alpha_t$ is positive: the subtree reduces risk, and a positive penalty is needed to offset its extra leaves. If the risks are equal, the threshold is zero. If $R(t)<R(T_t)$, the formula gives a negative value. Since a cost-complexity penalty is normally restricted to $\alpha\geq 0$, in that case the subtree is already worse in unpenalized risk and no nonnegative penalty makes it preferable.

Worked Example: A Subtree Measured in Training Errors

Suppose a hypothetical claims-screening tree has a subtree with four terminal leaves. Those leaves make $1$, $1$, $0$, and $2$ training misclassifications, respectively. If the whole subtree is replaced by one leaf, that leaf makes $9$ misclassifications. Find the threshold and compare the two choices at three penalty values. Use error counts as the risk measure.

Method. Add the terminal-leaf errors to get the subtree risk, then apply the threshold formula. This method avoids comparing only the error counts while overlooking the extra leaves.

The subtree risk is

$$ R(T_t)=1+1+0+2=4. $$

The collapsed-leaf risk is $R(t)=9$, and $L_t=4$. The subtree reduces risk by $9-4=5$ errors and uses $4-1=3$ extra leaves. Therefore,

\alpha_t=\frac{9-4}{4-1}=\frac{5}{3} =1.6667\text{ errors per additional leaf}.

At $\alpha=1$, the subtree cost is $4+1(4)=8$, while the collapsed-leaf cost is $9+1=10$; the subtree is cheaper. At the threshold, the costs are $4+(5/3)(4)=32/3$ and $9+5/3=32/3$, so they tie. At $\alpha=2$, the costs are $4+2(4)=12$ and $9+2=11$; the collapsed leaf is cheaper.

Check. The difference in unpenalized risks is $5$, and the subtree has three additional leaves. At the threshold their penalty contribution is $(5/3)(3)=5$, exactly offsetting that risk improvement.

Using Weighted Misclassification Risk

The threshold is not restricted to counting every error equally. If the analysis assigns different costs to different types of mistakes, define risk using those costs and use the same threshold calculation. The resulting penalty is measured in those cost units per additional leaf. It should not be interpreted as a number of errors unless risk was defined as an error count.

Worked Example: Unequal Costs for Two Error Types

Consider a hypothetical screening tree with $30$ records at node $t$: $8$ positive cases and $22$ negative cases. A false negative has cost $2$ units and a false positive has cost $1$ unit. A proposed subtree divides the records into three leaves: leaf A has $5$ positives and $2$ negatives, leaf B has $2$ positives and $8$ negatives, and leaf C has $1$ positive and $12$ negatives. Find the threshold using total weighted misclassification cost.

Method. At each leaf, compare the cost of predicting positive with the cost of predicting negative, then sum the minimum costs. This ensures that the risk reflects the stated unequal error costs.

At the collapsed node, predicting positive would misclassify all $22$ negatives, for cost $22(1)=22$. Predicting negative would misclassify all $8$ positives, for cost $8(2)=16$. The better single-leaf prediction is negative, so $R(t)=16$.

For leaf A, predicting positive costs $2(1)=2$, while predicting negative costs $5(2)=10$. Its risk is $2$. For leaf B, predicting positive costs $8(1)=8$, while predicting negative costs $2(2)=4$. Its risk is $4$. For leaf C, predicting positive costs $12(1)=12$, while predicting negative costs $1(2)=2$. Its risk is $2$. Thus,

R(T_t)=2+4+2=8,\qquad L_t=3.

The threshold is

\alpha_t=\frac{16-8}{3-1}=4 \text{ cost units per additional leaf}.

Check. At $\alpha=4$, the subtree cost is $8+4(3)=20$, and the collapsed-leaf cost is $16+4=20$. The tie is verified. The calculation avoids treating a false negative as if it had the same cost as a false positive.

Risk as a Proportion and a Common Denominator Trap

Risk may instead be expressed as a proportion of the observations. If both risks are divided by the same sample size, the threshold is also divided by that sample size. The choice of scale changes the numerical value and units of the penalty, but not the underlying comparison when the penalty is scaled consistently.

Worked Example: Calculating the Threshold From Error Rates

A hypothetical retention model is assessed on $80$ records. A five-leaf subtree makes $6$ errors, while its collapsed leaf makes $14$ errors. Calculate the threshold when risk is the proportion of records misclassified. Then determine the cheaper choice at $\alpha=0.020$, where the penalty is stated in error-rate units per leaf.

Method. Divide each error count by $80$ to put both risks on a proportion scale, then use the number of leaves removed in the denominator.

The subtree and collapsed-leaf risks are $R(T_t)=6/80=0.075$ and $R(t)=14/80=0.175$. There are $5-1=4$ additional leaves, so

\alpha_t=\frac{0.175-0.075}{4} =\frac{0.100}{4}=0.025.

At $\alpha=0.020$, the subtree cost is $0.075+0.020(5)=0.175$; the collapsed-leaf cost is $0.175+0.020=0.195$. The subtree is cheaper. At the threshold, the costs are $0.075+0.025(5)=0.200$ and $0.175+0.025=0.200$, confirming equality.

Common mistake. A tempting but incorrect calculation is to divide the risk improvement by all five subtree leaves: $0.100/5=0.020$. This is not the tie value. Collapsing the subtree removes four leaves, not five, because one leaf remains at node $t$. At the incorrect value $0.020$, the costs are $0.175$ and $0.195$, which are not equal. The correct denominator is $L_t-1=4$, giving $0.025$.

Interpreting the Result Carefully

The threshold is specific to the subtree, the risk definition, and the data used to calculate that risk. It tells you where the two local penalized costs tie; it does not by itself establish that either choice will predict better on new observations. Nor does a threshold calculated from error counts automatically apply to a weighted-cost risk or a proportion-based risk. Changing the risk scale requires changing the penalty scale accordingly.

A reliable calculation can be checked in two ways: verify that the unpenalized risk difference equals $\alpha_t(L_t-1)$, and substitute $\alpha_t$ into both penalized costs. In either check, retain the single leaf at $t$ when counting the leaves removed. These checks catch both a reversed risk difference and the common off-by-one denominator error.

Key takeaway: For a subtree with $L_t$ leaves, the tie penalty is the risk of the collapsed leaf minus the risk of the subtree, divided by $L_t-1$. A positive threshold is the subtree’s risk improvement per additional leaf.

Check Your Understanding

For each problem, use the stated risk scale consistently and compare the subtree with the single leaf at node $t$.

A three-leaf subtree has $6$ training errors, while the collapsed leaf has $10$. Calculate the threshold in errors per additional leaf. (Answer: $2$ errors per additional leaf.)
A four-leaf subtree has an error rate of $0.09$, and the collapsed leaf has an error rate of $0.18$. Find the threshold in error-rate units per additional leaf. (Answer: $0.03$.)
Under a specified weighted-loss measure, a three-leaf subtree has risk $19$ units and the collapsed leaf has risk $31$ units. Calculate the threshold and state which choice is cheaper at $\alpha=5$. (Answer: Threshold $=6$ loss units per additional leaf; the subtree is cheaper at $\alpha=5$.)
A five-leaf subtree has risk $12$, and the collapsed leaf has risk $18$. Calculate the threshold and verify equality by evaluating both costs at that penalty. (Answer: Threshold $=1.5$; both costs equal $19.5$.)
A three-leaf subtree has risk $9$, while the collapsed leaf has risk $7$. Find the algebraic tie value and explain what it implies when $\alpha\geq0$. (Answer: Tie value $=-1$; the collapsed leaf is cheaper for every nonnegative $\alpha$.)

What You'll Learn