Classification and Regression Trees (CART)

Definition

CART (Classification And Regression Trees; Breiman-Friedman-Olshen-Stone 1984) is a nonparametric method that predicts an outcome by recursively partitioning the predictor space into rectangular regions and fitting a constant in each. The result is a binary decision tree: at each internal node a single predictor is split at a threshold to most reduce a node-impurity criterion; terminal nodes give the fitted class or value. The rpart package is the canonical R implementation (Therneau-Atkinson 2023).

Key Ideas

• Recursive binary splitting (greedy). Starting from the root, choose the predictor and split point that most reduce impurity, then recurse on the two children — a greedy, locally-optimal search that yields axis-aligned rectangular regions.
• Splitting criteria. Classification: the Gini index (or information/entropy) node impurity; regression (anova method): within-node sum of squares. rpart also provides poisson (event rates) and survival (exp) methods, and can incorporate losses via a generalized Gini or altered priors.
• Cost-complexity pruning. A large tree overfits, so grow-then-prune: for complexity parameter $\alpha\ge0$, minimize $R_\alpha(T)=R(T)+\alpha|T|$ (risk plus a penalty on the number of terminal nodes $|T|$). Increasing $\alpha$ yields a nested sequence of subtrees; $\alpha$ (rpart's cp) is chosen by cross-validation, often with the 1-SE rule (the smallest tree within one standard error of the CV-minimizing tree).
• Surrogate splits for missing data. rpart's distinctive feature: at each node it stores surrogate splits — alternative variables that mimic the primary split — so cases missing the primary predictor are still sent down the tree, and surrogate agreement doubles as a variable-association measure.
• Variable importance. Summed impurity reduction attributable to each predictor (including its role as a surrogate), giving a ranking of predictor relevance. Caveat (Strobl et al. 2007): in random forests, impurity-based (and bootstrap-based) importance is biased — it artificially favours predictors with more categories or a finer measurement scale (more possible split points), so it is unreliable for variable selection when predictors are of mixed type (a common trap in genomics).

Why It Matters

• Interpretable, assumption-light nonlinearity. A tree captures nonlinear effects and interactions automatically and reads as a flowchart — no functional form, monotone-transformation-invariant, and robust to outliers in predictors.
• The building block of ensembles. Single trees are high-variance; averaging many (random forests, gradient-boosted trees) is what wins in practice — including for the cross-section of returns (Gu-Kelly-Xiu trace ML's edge to tree/neural-net nonlinear interactions).
• Handles messy data. Native support for mixed-type predictors, missing values (surrogates), and unequal misclassification costs makes it a practical default.

Open Questions

• Instability. Small data changes can produce very different trees; a single tree trades interpretability for high variance, which ensembling fixes at the cost of interpretability.
• Greedy suboptimality and selection bias. Greedy splitting need not find the globally best tree, and impurity-based splitting is biased toward predictors with many possible split points. Strobl et al. (2007) trace this to two mechanisms — bootstrap sampling with replacement and the CART splitting criterion's variable-selection bias — and show it corrupts random-forest variable-importance rankings; their fix is an alternative forest of conditional-inference trees (which separate variable selection from split-point choice via significance tests, cforest/party) grown with subsampling without replacement, yielding unbiased selection and reliable importance even for mixed-type predictors. For single trees the same bias is addressed by algorithms that choose the split variable by a statistical test before searching split points — Loh (2011) reviews this lineage (his GUIDE, QUEST, CRUISE) alongside CART and C4.5, comparing their handling of selection bias, missing values, and interaction detection.
• Tuning. Choice of cp/1-SE rule, minimum node sizes, and loss/prior specification all shape the fitted tree.

Related

• Machine Learning in Asset Pricing
• Random Forest
• Cross-Validation
• Frailty Model
• Therneau-Atkinson (2023) An Introduction to Recursive Partitioning Using the RPART Routines
• Strobl et al. (2007) Bias in Random Forest Variable Importance Measures
• Loh (2011) Classification and Regression Trees
• Terry M. Therneau
• Wei-Yin Loh
• Elizabeth J. Atkinson
• Carolin Strobl
• Torsten Hothorn