Therneau-Atkinson (2023) An Introduction to Recursive Partitioning Using the RPART Routines

Summary

The reference vignette for the rpart package: a practical introduction to recursive partitioning (CART). It covers how a tree is grown (splitting criteria, losses, variable importance), how it is pruned (cost-complexity, cross-validation), how missing data are handled (surrogate variables), and the several response methods rpart supports — classification, regression (anova), Poisson, and survival — illustrated on worked examples (prostate cancer, digit recognition, auto and kyphosis data).

Key Claims

• Recursive partitioning. A tree is built by recursively splitting nodes to reduce impurity, giving axis-aligned rectangular regions with a constant fit in each terminal node; $|T|$ (number of terminal nodes) plays the role of degrees of freedom and $R(T)$ (node risk) the role of residual sum of squares.
• Splitting criteria and losses. Classification uses the Gini index; regression uses within-node sum of squares; losses can be incorporated via a generalized Gini index or altered priors. Poisson and survival (exponential) methods are also provided.
• Cost-complexity pruning. Minimize $R_\alpha(T)=R(T)+\alpha|T|$ over subtrees; increasing the complexity parameter $\alpha$ yields a unique nested sequence of subtrees, and $\alpha$ is selected by cross-validation.
• Surrogate variables. Missing predictors are handled by surrogate splits that mimic the primary split, which also quantify variable association; variable importance aggregates (surrogate-adjusted) impurity reduction.
• Software. Implements these methods in rpart (S-Plus/R), the canonical CART implementation, with extensive worked examples.

Concepts Introduced or Extended

• Classification and Regression Trees (CART)

Entities Mentioned

• Terry M. Therneau
• Elizabeth J. Atkinson

Quotes

"Let $\alpha$ be some number between 0 and $\infty$ which measures the 'cost' of adding another variable to the model … Define $R_\alpha(T) = R(T) + \alpha|T|$ to be the cost for the tree, and define $T_\alpha$ to be that sub tree of the full model which has minimal cost."

My Take

A vignette rather than a research paper, but the clearest concise statement of how CART actually works in practice — and, since rpart is the implementation most people use, the de facto reference. Two things it explains better than the original CART book for applied users: the cost-complexity path as a degrees-of-freedom-versus-fit trade-off pruned by cross-validation, and the surrogate-split machinery that lets trees cope with missing data gracefully (a genuinely distinctive rpart feature). It anchors the single-tree end of the wiki's machine-learning material — the interpretable building block whose ensembles (random forests, boosting) drive the gains documented in Gu-Kelly-Xiu (2020) — and connects the pruning step back to cross-validation.