What the Complexity Parameter Measures
A fully grown tree can fit its training data closely by making many splits, but a large tree is harder to interpret and may fit noise. Cost-complexity pruning makes this trade-off explicit: it compares a tree’s lack of fit with a penalty for its size. The complexity parameter, often written \(cp\) in rpart output, controls the strength of that penalty. Larger values favor simpler trees.
The risk used in the calculation depends on the tree method. For a regression tree, it may be residual sum of squares; for a classification tree, it may be a classification loss or deviance. In the formulas below, \(R(T)\) denotes the training risk of tree \(T\), and \(R(t)\) denotes the risk when node \(t\) is treated as a single terminal node. The comparison must use the same risk definition throughout.
This scaling explains why the same numerical \(cp\) should not be added directly to raw risks when those risks are measured in a different scale. The relative-error column in an rpart pruning table reports training risk relative to the root-node risk. The \(cp\) values mark changes in the sequence of candidate subtrees; they are not measures of predictive accuracy by themselves.
Why Pruning Produces a Sequence of Nested Trees
Suppose an internal node \(t\) has a descendant subtree \(T_t\) with \(L\) terminal nodes. Replacing that subtree with one terminal node removes \(L-1\) leaves. The pruning decision depends on whether the additional fit from keeping the subtree is worth the additional complexity penalty.
At the point where the two scores are equal, the critical penalty is
These formulas apply when \(R(t)>R(T_t)\), as is expected for a subtree that improves training fit. If the subtree does not reduce risk, it offers no training-fit benefit to offset a positive size penalty. At the critical value, the two choices tie; below it, retaining the subtree has the lower score, and above it, collapsing the subtree has the lower score.
In a binary tree, the number of terminal nodes is one greater than the number of splits. rpart reports nsplit, not the number of leaves. Either size measure can be used for comparing trees if it is used consistently: their difference is a constant across trees in the same sequence. For the local branch calculation above, however, the change in leaves is specifically \(L-1\), not \(L\).
Worked Example: Finding a Branch’s Critical cp
A hypothetical regression tree has root-node risk \(R(T_0)=300\). At one internal node, collapsing the branch gives risk \(R(t)=120\). Retaining it gives risk \(R(T_t)=60\) across three terminal nodes. Find the critical \(cp\), and decide which option is preferred at \(cp=0.08\) and \(cp=0.12\).
Method. Use the cost-complexity comparison for the branch. Here \(L=3\), so retaining the branch adds \(L-1=2\) leaves relative to collapsing it. The reduction in training risk from retaining it is \(120-60=60\).
The critical penalty on the raw-risk scale is \( \alpha_t=60/2=30 \). Therefore, \( cp_t=30/300=0.10 \). At \(cp=0.08\), the raw penalty is \(\alpha=0.08(300)=24\). The collapsed score is \(120+24(1)=144\); the retained score is \(60+24(3)=132\). Retaining the branch is preferred.
At \(cp=0.12\), the raw penalty is \(\alpha=0.12(300)=36\). The collapsed score is \(120+36(1)=156\); the retained score is \(60+36(3)=168\). Collapsing the branch is preferred. The results are consistent with the critical value: retain below \(0.10\), collapse above it.
Check. At the critical value \(cp=0.10\), \(\alpha=30\). Both scores equal \(120+30=150\) and \(60+3(30)=150\). A common mistake is to divide the risk improvement by three leaves rather than by the two additional leaves. That would give the wrong cutpoint.
Reading an rpart Pruning Table
An rpart pruning table commonly includes CP, nsplit, rel error, xerror, and xstd. Each row describes a candidate point in the pruning sequence. A larger CP generally corresponds to a simpler candidate, while increasing nsplit moves toward a larger tree. Exact values and displayed rows depend on the fitted tree and its settings.
| Column | Interpretation | What it does not mean |
|---|---|---|
| CP | A complexity cutpoint associated with a candidate subtree in the pruning sequence. | It is not a test-set accuracy score or a direct count of splits. |
| nsplit | The number of splits in that candidate tree. | It is not the number of terminal nodes; for a binary tree, leaves equal nsplit plus one. |
| rel error | Training risk relative to the root-node risk. | It is not cross-validation error. |
| xerror | An estimate of relative prediction error from cross-validation. | It need not decrease as the tree gets larger. |
| xstd | The estimated standard error associated with the cross-validation error. | It is not another measure of tree size. |
The CP and relative-error columns describe the training-risk pruning sequence. The cross-validation columns provide evidence about predictive performance and may be used to compare candidates. A tree with the smallest xerror is not automatically the largest tree, because cross-validation error can rise as additional splits fit details that do not generalize.
Worked Example: Interpreting a Pruning Table
A hypothetical rpart table for a classification problem reports the following rows. Treat the figures as illustrative; the table is not from a real organization.
| CP | nsplit | rel error | xerror | xstd |
|---|---|---|---|---|
| 0.18 | 0 | 1.00 | 1.08 | 0.12 |
| 0.07 | 1 | 0.62 | 0.79 | 0.10 |
| 0.03 | 3 | 0.39 | 0.68 | 0.09 |
| 0.01 | 5 | 0.31 | 0.75 | 0.10 |
The row with \(cp=0.18\) has zero splits, so it is the root-only candidate and has one terminal node. The row with \(cp=0.03\) has three splits, so it has four terminal nodes if the tree is binary. Its relative training error is \(0.39\), meaning its training risk is 39% of the root-node risk. Its cross-validation error is \(0.68\), lower than the other displayed xerror values.
The five-split candidate has lower training error, \(0.31\), but higher cross-validation error, \(0.75\), than the three-split candidate. This is not contradictory: training fit improves as the tree grows, while estimated out-of-sample performance need not. From this table alone, the three-split candidate has the smallest displayed xerror. That observation does not establish that it is best under every selection rule, nor does it make \(cp=0.03\) a universal choice for other data.
Check. The candidate with the lowest training error has five splits; the candidate with the lowest cross-validation error has three splits. Confusing rel error with xerror would incorrectly identify the five-split candidate as having the best estimated predictive performance.
Worked Branch Comparison and a Penalty-Scaling Trap
Worked Example: Comparing a Branch at cp = 0.08
A hypothetical tree has root-node risk \(R(T_0)=1{,}200\). For a particular branch, the collapsed-node risk is 750. Retaining the branch gives risk 510 across four terminal nodes. At \(cp=0.08\), determine which choice has the lower cost-complexity score.
Method. Convert the relative \(cp\) to the raw-risk penalty: \(\alpha=0.08(1{,}200)=96\). The collapsed option has one leaf, so its local score is \(750+96(1)=846\). The retained option has four leaves, so its score is \(510+96(4)=894\). Since \(846<894\), collapsing the branch is preferred.
The same comparison using normalized scores is collapsed: \(750/1{,}200+0.08(1)=0.625+0.08=0.705\); retained: \(510/1{,}200+0.08(4)=0.425+0.32=0.745\). Again, pruning is preferred.
The branch’s critical \(cp\) is \((750-510)/((4-1)(1{,}200))=240/3{,}600=0.0667\) to four decimal places. Since \(0.08\) is larger than this cutpoint, the collapse is consistent with the critical-value calculation.
Common mistake and correction. It is incorrect to add \(0.08\) directly to raw risk 750 or 510: \(cp\) is a relative penalty, not a raw-risk amount. It is also incorrect to use four as the change in leaves. The comparison may use four leaves for the retained score and one for the collapsed score, as above; the difference in penalty is three leaves. The equivalent calculation uses raw \(\alpha=96\), or normalized risk plus \(cp\) times the leaf count.
How to Use the Sequence Without Overinterpreting It
The pruning sequence answers a structural question: which nested subtrees are candidates as the complexity penalty changes? It does not, by itself, answer which candidate will predict best on new observations. That assessment belongs to validation evidence, such as the cross-validation quantities displayed in the table. Keep these roles distinct when explaining a model.
Determine whether the values are raw risks or relative errors. For relative errors, the root-node risk is the reference value 1.
Use nsplit to identify the number of splits; add one to obtain the number of leaves in a binary tree.
A larger penalty favors a smaller candidate. At a branch cutpoint, collapsing and retaining that branch tie in cost-complexity score.
Use rel error to describe training fit and xerror, with its uncertainty indicated by xstd, to discuss cross-validation performance.
A common exam trap is to treat every row as an unrelated model, rather than recognizing that the candidates come from a nested pruning sequence. Another is to interpret a CP value as the number of splits to keep. CP is a penalty cutpoint; nsplit reports candidate size. A final trap is to claim that a lower relative training error proves better prediction. It only shows lower training risk under the tree’s fitting criterion.
The ideas here are aligned with the SOA Exam PA (Predictive Analytics) syllabus. In a written interpretation, state what CP controls, identify the candidate size from nsplit, and distinguish the training-risk columns from the cross-validation columns.
Check Your Understanding
For each problem, show the risk scale and account for the change in terminal-node count before deciding.
- A tree has root risk 500. A branch’s collapsed risk is 90; its two-leaf subtree has risk 50. Find the critical \(cp\), then state whether to retain the branch at \(cp=0.06\) and at \(cp=0.10\). (Answer: Critical \(cp=0.08\); retain at 0.06 and collapse at 0.10.)
- A tree has root risk 800. A branch has collapsed risk 260 and a four-leaf subtree risk of 140. Find its critical \(cp\) and choose at \(cp=0.04\) and \(cp=0.06\). (Answer: Critical \(cp=0.05\); retain at 0.04 and collapse at 0.06.)
- A binary-tree table has a row with nsplit equal to 6, rel error 0.28, and xerror 0.74. How many leaves does that candidate have, and what do the two error figures describe? (Answer: 7 leaves; 0.28 is relative training risk and 0.74 is cross-validation error.)
- Root risk is 1,000. A branch’s collapsed risk is 400 and its three-leaf subtree risk is 160. At \(cp=0.10\), compare normalized local scores and decide. (Answer: Collapsed \(0.40+0.10=0.50\); retained \(0.16+0.30=0.46\); retain the subtree.)
- A pruning table gives xerror values 0.91, 0.73, 0.66, and 0.70 for candidates with 0, 1, 3, and 5 splits, respectively. Which displayed candidate has the smallest xerror, and does that imply it also has the lowest training error? (Answer: The three-split candidate has the smallest xerror, 0.66; no, the five-split candidate may have lower training error.)