Classification and Regression Trees (CART)
On this page
2.6 — Classification and Regression Trees (CART)
Recall first. What changes between a classification tree and a regression tree: the split idea, the leaf prediction, the impurity/loss, or all three?
One recursive framework, two targets
CART (Classification and Regression Trees) recursively creates binary splits. At each node it searches a feature and threshold, partitions the data, and repeats. The framework is shared; the target criterion and leaf prediction differ:
| Classification CART | Regression CART | |
|---|---|---|
| Leaf output | Majority class or class probabilities | Mean target (usual squared-error criterion) |
| Node criterion | Gini or entropy | MSE/variance reduction |
| Typical loss | Misclassification/log-loss for evaluation | Squared error for fitting |
For a candidate split, the generic objective is weighted child loss:
L_split = (n_L/n)L(L) + (n_R/n)L(R)Choose the split that reduces the parent loss most. The classification Gini formula belongs to the first column; it is not a regression criterion.12
Growing, stopping, pruning
A fully grown tree can create tiny leaves and fit noise. CART controls complexity in two stages:
- Pre-pruning: stop early with limits such as maximum depth, minimum samples per split, or minimum samples per leaf.
- Post-pruning: grow a larger tree, then remove branches whose complexity is not worth their fit improvement. Cost-complexity pruning uses an objective of the form
R_α(T)=R(T)+α|T|, whereR(T)is leaf loss and|T|is number of leaves; largerαfavors smaller trees.
Select controls using validation or cross-validation, never by training fit alone. scikit-learn exposes both tree criteria and cost-complexity pruning.1
Worked regression split
A regression node has targets [2, 4, 10, 12], mean 7. Parent SSE is (2−7)²+(4−7)²+(10−7)²+(12−7)²=68. Split after the second value gives left [2,4] mean 3, SSE 4; right [10,12] mean 11, SSE 2. Child SSE is 6, so reduction is 68−6=62. The leaves predict 3 and 11. A candidate with lower child SSE would be preferred.
The same arithmetic is not used for classification: replace the leaf statistic/criterion with class proportions and an impurity such as Gini.
Strengths and limitations
Trees need little preprocessing, express interactions, and provide paths that are easy to inspect. They are unstable: a small change near the root can change all descendants. Axis-aligned splits can require many levels to approximate a diagonal boundary. A single tree may therefore have high variance; bagging and random forests (Module III) reduce this instability, while boosting builds sequential corrective trees.
Tree “importance” must be interpreted cautiously. A split’s predictive usefulness is not a causal effect, and impurity-based importance can favor high-cardinality features.1
Exercise
A classification node has 8 samples. A candidate split leaves 5 samples in a pure left child and 3 samples in a right child with class proportions 1/3,2/3. Compute weighted Gini. Would a pure 5-sample child automatically make this the best split?
Revealed answer
Right Gini is 1−(1/3)²−(2/3)²=4/9. Weighted impurity is (5/8)(0)+(3/8)(4/9)=1/6≈0.167. No: compare its parent impurity and gain with every candidate, and remember that a tiny pure child can be less useful than a balanced split that improves generalization.
Exam lens
A strong CART answer compares classification and regression in a table, gives the recursive algorithm, explains greedy split selection and pruning, then states the variance/interpretability trade-off. Do not call Gini a regression measure.
Rapid revision checklist
- Can I distinguish classification and regression leaf outputs?
- Can I write weighted child loss?
- Can I explain pre-pruning and post-pruning?
- Can I calculate a regression SSE reduction?
- Can I state why one tree is unstable?
Key takeaways
- CART is binary recursive partitioning for both categorical and numeric targets.
- Classification uses impurity; regression usually uses squared-error/variance reduction.
- Leaves predict a class/proportion or a numeric mean.
- Pruning and validation control a tree’s variance.