Tree-Based Methods: Classification and Regression Trees (CART)

Intuition Beginner

A decision tree predicts by asking a short series of yes/no questions about a case and reading off an answer at the end. Is the applicant's income above 50 thousand? If yes, is their account more than three years old? If no, how many late payments do they have? Each answer sends you down one branch, and when you reach a leaf at the bottom you stop and give the prediction stored there. The whole model is a flowchart you could follow with pencil and paper.

The questions are not chosen by hand. The tree is grown from data by a simple rule: at each step, look at every feature and every place you could split it, and pick the single split that best separates the cases into more similar groups. "More similar" means closer in the value you are trying to predict. For a number you want to predict, like a house price, similar means the prices in each group are close together. For a category, like spam or not spam, similar means each group is as pure as possible, mostly one class.

A tree gives a piecewise prediction: it carves the space of features into rectangular boxes, and inside each box it predicts one fixed value, the average of the training cases that fell in that box. The boxes are the leaves. Big leaves make a coarse, steady model; many small leaves make a detailed, jumpy one.

The appeal of trees is that you can read them. A doctor can follow the path that led to a diagnosis and check whether each question makes sense. The cost is that a single tree is twitchy: change a few training cases and the top split can flip, redrawing every box below it. That twitchiness is the reason people average many trees together, which later units take up.

Visual Beginner

Picture the two-feature plane with income across the bottom and age up the side. The first split draws a vertical line at income equals 50; the left part splits again with a horizontal line at age equals 30; the right part splits at income equals 80. You end up with four rectangular boxes, and the tree predicts one value in each box.

Where you are	Question asked	What happens
Root	income above 50?	go left if no, right if yes
Left child	age above 30?	reach a leaf either way
Right child	income above 80?	reach a leaf either way
Any leaf	none	predict the box's stored value

Reading the flowchart and reading the carved plane are two views of one model: every path from the root to a leaf names one rectangular box, and the prediction is constant inside it.

Worked example Beginner

Six houses, each with a lot size (in thousands of square feet) and a sale price (in thousands of dollars). We grow one split of a regression tree.

House	Lot size	Price
1	2	150
2	3	160
3	4	200
4	6	310
5	7	330
6	8	350

Step 1. The do-nothing baseline. The average price of all six is $(150+160+200+310+330+350)/6=1500/6=250$. The total squared error around this single average is $(150-250{)}^2+(160-250{)}^2+(200-250{)}^2+(310-250{)}^2+(330-250{)}^2+(350-250{)}^2=10000+8100+2500+3600+6400+10000=40600$.

Step 2. Try splitting at lot size 5. Left group is houses 1, 2, 3 with prices 150, 160, 200, averaging $510/3=170$. Right group is houses 4, 5, 6 with prices 310, 330, 350, averaging $990/3=330$.

Step 3. Score this split by its squared error. Left error is $(150-170{)}^2+(160-170{)}^2+(200-170{)}^2=400+100+900=1400$. Right error is $(310-330{)}^2+(330-330{)}^2+(350-330{)}^2=400+0+400=800$. The split's total is $1400+800=2200$.

Step 4. Compare. The split drops the squared error from 40600 to 2200, an enormous reduction. A scan over the other candidate split points (between 3 and 4, between 6 and 7, and so on) would find none that beats this one, so the tree splits at lot size 5.

What this tells us: the tree found, on its own, that small lots and large lots are two clean groups, and it predicts 170 for small lots and 330 for large ones. The split point was chosen by the one number it cares about, the within-group squared error, with no formula supplied in advance.

Check your understanding Beginner

Formal definition Intermediate+

Let $(X,Y)$ have joint law on $\mathcal{X}\times \mathcal{Y}$ with $\mathcal{X}\subseteq {\mathbb{R}}^p$, and write a training sample $\{(x_i,y_i){\}}_{i=1}^n$. A tree $T$ encodes a recursive binary partition of $\mathcal{X}$ into axis-aligned rectangles $R_1,\dots ,R_{|T|}$, one per leaf (terminal node), where $|T|$ is the number of leaves. Each internal node carries a split $s=(j,c)$ sending a case to the left child if $x_j\le c$ and to the right child otherwise (for an ordered predictor $j$ and threshold $c$); for a categorical predictor a split is a partition of its level set into two groups. A node $t$ owns the subset $R_t\subseteq \mathcal{X}$ reached by its ancestral splits and the index set $\{i:x_i\in R_t\}$ of size $N_t$.

Regression tree. The estimator is piecewise constant, $\hat{f}(x)={\sum }_{m=1}^{|T|}{\hat{c}}_{m}1\{x\in R_m\}$, and on a fixed partition the within-leaf sum of squared errors ${\sum }_{x_i\in R_m}(y_i-c_m{)}^2$ is minimised at the leaf mean ${\hat{c}}_m={\bar{y}}_m=\frac{1}{N_m}{\sum }_{x_i\in R_m}{y}_i$. The node impurity is the within-node mean squared error $Q_m(T)=\frac{1}{N_m}{\sum }_{x_i\in R_m}(y_i-{\bar{y}}_m{)}^2$.

Classification tree. With $K$ classes, let ${\hat{p}}_{mk}=\frac{1}{N_m}{\sum }_{x_i\in R_m}1\{y_i=k\}$ be the node class proportions and $k(m)=\arg {\max }_k{\hat{p}}_{mk}$ the majority class. Three node impurity measures are standard:

$$\text{misclassification: }{Q}_m=1-{\hat{p}}_{m,k(m)},\text{Gini: }{Q}_m=\sum _{k=1}^K{\hat{p}}_{mk}(1-{\hat{p}}_{mk}),\text{entropy: }{Q}_m=-\sum _{k=1}^K{\hat{p}}_{mk}\log {\hat{p}}_{mk}.$$

All three vanish at a pure node (${\hat{p}}_{mk}\in \{0,1\}$) and are maximal at the uniform distribution; Gini and entropy are strictly concave in the vector $({\hat{p}}_{m1},\dots ,{\hat{p}}_{mK})$, while misclassification error is concave but piecewise linear.

Greedy split selection. For a node $t$ with impurity $i(t):=Q_t$, a split $s$ into children $t_L,t_R$ with proportions $p_L=N_{t_L}/N_t$, $p_R=N_{t_R}/N_t$ has impurity reduction

$$\Delta i(s,t)=i(t)-p_{L}i(t_L)-p_{R}i(t_R).$$

CART grows the tree by choosing, at each node, the split $s^{\star }=\arg {\max }_s\Delta i(s,t)$ over all predictors and all candidate thresholds, then recursing on the children, stopping when nodes are pure or fall below a minimum size.

Cost-complexity. For $\alpha \ge 0$ and a subtree $T\subseteq T_{\max }$ obtained by pruning, the cost-complexity criterion is

$$C_{\alpha }(T)=\sum _{m=1}^{|T|}{N}_m{Q}_m(T)+\alpha |T|,$$

the total node cost penalised by $\alpha$ times the number of leaves. Writing $R(T)={\sum }_m{N}_m{Q}_m(T)$ for the resubstitution cost, $C_{\alpha }(T)=R(T)+\alpha |T|$.

The notation here — $1\{\cdot \}$ for indicators, ${\bar{y}}_m$ for a leaf mean, ${\hat{p}}_{mk}$ for node class proportions, $|T|$ for leaf count, and $\arg \max$ — is recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "Misclassification error is the best criterion to grow by, since it is what we ultimately care about." Misclassification error is insensitive: a split that moves a node from $(0.5,0.5)$ to two children at $(0.7,0.3)$ and $(0.3,0.7)$ leaves the misclassification impurity weighted sum unchanged at $0.3$, so the split looks worthless, whereas Gini and entropy both record a strict gain. The strict concavity of Gini and entropy is what makes any non-degenerate split register progress; misclassification error is reserved for pruning, where the objective genuinely is error.

• "A bigger tree always has lower cost, so growth never overshoots." Resubstitution cost $R(T)$ decreases monotonically with growth and is minimised by the fully grown tree, which typically interpolates the training data. It is the complexity penalty $\alpha |T|$, not $R(T)$, that creates an interior optimum; without it the criterion selects the overfit maximal tree.

• "Splitting a $k$-level categorical predictor requires examining all $2^{k-1}-1$ binary groupings." For two-class problems (and for squared-error regression), ordering the levels by their mean response and splitting on that order finds the optimal binary partition in $k-1$ comparisons — the Fisher/Breiman ordering result — so the exponential search is avoided in the cases that matter most.

Key theorem with proof Intermediate+

The signature structural fact is that cost-complexity pruning produces, from a single grown tree, a finite nested sequence of subtrees indexed by a finite increasing sequence of penalties — the object cross-validation then searches over. Everything operational about CART model selection rests on this.

Theorem (weakest-link pruning; Breiman-Friedman-Olshen-Stone). Fix a grown tree $T_{\max }$. For each $\alpha \ge 0$ there is a unique smallest subtree $T(\alpha )⪯T_{\max }$ (smallest in number of leaves) minimising $C_{\alpha }(\cdot )$. As $\alpha$ increases from $0$ to $\infty$ the minimisers are nested,

$$T_{\max }⪰T({\alpha }_1)⪰T({\alpha }_2)⪰\cdots ⪰\{\text{root}\},0={\alpha }_0<{\alpha }_1<\cdots <{\alpha }_M,$$

so the entire family $\{T(\alpha ):\alpha \ge 0\}$ collapses to a finite chain obtained by repeatedly pruning the weakest-link branch. ^{[Breiman 1984]}

Proof. For a node $t$ of $T$, let $T_t$ be the branch rooted at $t$ and $\{t\}$ the subtree got by collapsing $t$ to a leaf. Define the resubstitution cost of a single node $R(t)=N_t{Q}_t$ and of its branch $R(T_t)={\sum }_{m\in \text{leaves}(T_t)}{N}_m{Q}_m$. Because each split chooses children minimising the weighted child impurity, growing never increases cost: $R(T_t)\le R(t)$, with $|T_t|\ge 1$ leaves under $t$. The cost of keeping the branch versus collapsing it crosses as $\alpha$ rises. Collapsing $t$ is at least as cheap under $C_{\alpha }$ when

$$R(t)+\alpha \le R(T_t)+\alpha |T_t|⟺\alpha \ge g(t):=\frac{R(t)-R(T_t)}{|T_t|-1},$$

the per-extra-leaf cost saving of the branch. The function $g(t)$ is the link strength of node $t$: small $g(t)$ marks a branch that buys little accuracy per leaf, the weakest link.

Define ${\alpha }_1={\min }_{t}g(t)$ over internal nodes of $T_{\max }$, and let $T({\alpha }_1)$ be $T_{\max }$ with every branch attaining this minimum collapsed to its root. For $\alpha <{\alpha }_1$ no collapse lowers $C_{\alpha }$, so $T(\alpha )=T_{\max }$; at $\alpha ={\alpha }_1$ the collapsed tree has cost equal to $T_{\max }$ and fewer leaves, hence is the *smallest* minimiser. Recomputing $g(\cdot )$ on $T({\alpha }_1)$ and taking its minimum gives ${\alpha }_2>{\alpha }_1$ and $T({\alpha }_2)\prec T({\alpha }_1)$; iterating terminates at the root. Uniqueness of the smallest minimiser at each $\alpha$ follows because if two distinct subtrees both minimise $C_{\alpha }$, their intersection (the larger common pruned subtree) also minimises it and is smaller, so the minimiser of least size is unique. The breakpoints ${\alpha }_1<\cdots <{\alpha }_M$ are finite because each step removes at least one node from a finite tree. $\square$

Bridge. This theorem is the foundational reason CART can be tuned with a single one-dimensional cross-validation: instead of searching the astronomically large space of subtrees of $T_{\max }$, one searches the finite chain $T({\alpha }_1)\succ \cdots \succ T({\alpha }_M)$, and this is exactly the move that makes pruning practical. The weakest-link quantity $g(t)=(R(t)-R(T_t))/(|T_t|-1)$ generalises the simple per-split impurity drop used during growth — growth maximises the drop locally, pruning charges the accumulated drop of a whole branch against its leaf budget — so the bridge is that the same cost-versus-complexity ledger drives both phases of CART, read forward to grow and backward to prune. The nested sequence appears again in the cross-validation step of the Advanced results, where each ${\alpha }_k$ is scored on held-out folds and the one-standard-error rule picks the sparsest tree within noise of the best; it builds toward the instability analysis that motivates averaging trees in 45.08.05 and 45.08.06, since the very greediness that makes the chain finite is what makes each individual tree high-variance.

Exercises Intermediate+

Advanced results Master

Cost-complexity pruning hands cross-validation a finite chain; the remaining theory concerns how to select within it, how categorical and missing data are absorbed, and the variance that single trees pay for their adaptivity — the variance that ensembling spends the rest of the chapter removing.

Theorem 1 (cross-validated selection and the one-standard-error rule). Grow $T_{\max }$ on the full sample and form the penalty chain with geometric midpoints ${\alpha }_k^{\prime }=\sqrt{{\alpha }_k{\alpha }_{k+1}}$. For each fold $v$ of a $V$-fold partition, grow a tree on the complement and prune it to the subtree minimising $C_{{\alpha }_k^{\prime }}$, then estimate its risk on fold $v$; averaging over folds gives a cross-validation risk ${\hat{R}}^{\mathrm{cv}}({\alpha }_k^{\prime })$ with standard error ${\mathrm{SE}}_k$. The one-standard-error rule selects the sparsest tree whose ${\hat{R}}^{\mathrm{cv}}$ lies within $\mathrm{SE}$ of the minimum, $\hat{\alpha }=\max \{{\alpha }_k^{\prime }:{\hat{R}}^{\mathrm{cv}}({\alpha }_k^{\prime })\le {\min }_j{\hat{R}}^{\mathrm{cv}}({\alpha }_j^{\prime })+{\mathrm{SE}}_{j^{\star }}\}$ ^{[Breiman 1984]}. The rule trades a statistically indistinguishable increase in estimated risk for a smaller, more stable, more interpretable tree, and is the CART default.

Theorem 2 (optimal categorical splits by ordering). For a two-class ($K=2$) classification problem with Gini or entropy impurity, and for squared-error regression, the optimal binary split of a categorical predictor with $q$ levels is found by ordering the levels by the response statistic — the proportion ${\hat{p}}_{\ell 1}$ in class 1 for two-class problems, the mean response ${\bar{y}}_{\ell }$ for regression — and considering only the $q-1$ splits that respect this order ^{[Breiman 1984]}. This reduces the search from $2^{q-1}-1$ subsets to $q-1$ thresholds. The result fails for $K\ge 3$ classes, where the full subset search (or the twoing criterion, which groups classes into two superclasses at each node) is required and the favouring of high-cardinality categorical predictors becomes a known bias of impurity-based splitting.

Theorem 3 (instability and the bias-variance decomposition of trees). A fully grown tree is a low-bias, high-variance estimator: its leaves interpolate, so squared bias is small, while the variance is large because the partition itself is a discontinuous function of the data — a perturbation that flips a high split relocates every descendant cell. For a prediction $\hat{f}(x)$ the expected squared error decomposes as $\mathbb{E}[(Y-\hat{f}(x){)}^2]={\sigma }^2+{\mathrm{Bias}}^2(\hat{f}(x))+\mathrm{Var}(\hat{f}(x))$, and for trees the dominant reducible term is the variance ^{[Hastie 2009]}. Averaging $B$ identically distributed trees with pairwise prediction correlation $\rho$ has variance $\rho {\sigma }_T^2+\frac{1-\rho }{B}{\sigma }_T^2$, so bagging (which lowers ${\sigma }_T^2$ by averaging) and random forests (which additionally lower $\rho$ by decorrelating splits) attack exactly the term that dominates a single tree's error; boosting instead grows shallow, high-bias trees and reduces bias by sequential reweighting.

Theorem 4 (trees as adaptive nearest-neighbour estimators). Write a tree prediction as a weighted average of training responses, $\hat{f}(x)={\sum }_{i=1}^n{w}_i(x)y_i$, where $w_i(x)=1\{x_i\in R(x)\}/N_{R(x)}$ and $R(x)$ is the leaf containing $x$; the weights are supported on the leaf neighbourhood of $x$ and sum to one. A tree is thus a nearest-neighbour rule whose neighbourhoods are data-adaptive axis-aligned rectangles rather than fixed Euclidean balls, with the splits choosing both the shape and the local feature directions ^{[Lin 2006]}. Averaging trees over bootstrap samples or random feature subsets yields a forest weight $w_i(x)=\frac{1}{B}{\sum }_{b}1\{x_i\in R_b(x)\}/N_{R_b(x)}$, the potential-nearest-neighbour weighting, and casts the consistency of forests as a question about whether these adaptive neighbourhoods shrink while still containing enough points — the bridge between partition estimators and local averaging.

Synthesis. CART is one ledger — cost against complexity — read in two directions, and the foundational reason the method coheres is that the same per-leaf accounting that greedily grows the tree by maximising local impurity drop is what prunes it by charging each branch's accumulated drop against its leaf budget through the link strength $g(t)$. The weakest-link theorem is exactly this duality made finite: it collapses the uncountable family of penalised subtrees to a nested chain, and putting these together with cross-validation and the one-standard-error rule turns model selection into a one-dimensional search. The impurity choice is not cosmetic — Gini and entropy are strictly concave, which is the central insight that every non-degenerate split registers a strictly positive gain (Exercise 6), whereas piecewise-linear misclassification error is blind to splits that do not flip the majority and is demoted to the pruning objective. The instability this greedy, discontinuous partitioning buys generalises into the variance term that dominates a tree's error, and is dual to the averaging downstream: bagging and random forests in 45.08.05 reduce that variance while boosting in 45.08.06 reduces the bias of deliberately stunted trees. The nearest-neighbour reading is the bridge that unifies the picture — a tree is an adaptive local-averaging estimator whose neighbourhoods are its leaves, so the partition theory of CART, the consistency theory of forests, and classical $k$-nearest-neighbours are three views of one weighted-average estimator, differing only in how the weights are chosen.

Full proof set Master

Proposition 1 (leaf mean minimises within-node SSE; impurity is node variance). For a regression node $t$, $\arg {\min }_c{\sum }_{i\in t}(y_i-c{)}^2={\bar{y}}_t$, and the minimum equals $N_t{\widehat{\mathrm{Var}}}_t(y)$.

Proof. The objective $\varphi (c)={\sum }_{i\in t}(y_i-c{)}^2$ has ${\varphi }^{\prime }(c)=-2{\sum }_{i\in t}(y_i-c)=-2({\sum }_{i\in t}{y}_i-N_{t}c)$, vanishing at $c={\bar{y}}_t=\frac{1}{N_t}{\sum }_{i\in t}{y}_i$, and ${\varphi }^{\prime \prime }(c)=2N_t>0$, so ${\bar{y}}_t$ is the unique minimiser. Substituting, $\varphi ({\bar{y}}_t)={\sum }_{i\in t}(y_i-{\bar{y}}_t{)}^2=N_t\cdot \frac{1}{N_t}{\sum }_{i\in t}(y_i-{\bar{y}}_t{)}^2=N_t{\widehat{\mathrm{Var}}}_t(y)$. $\square$

Proposition 2 (non-negativity of impurity reduction for concave impurity). Let the node impurity be $i(p)=\varphi (p)$ for a concave $\varphi$ on the probability simplex. For any split of node $t$ into $t_L,t_R$ with weights $p_L,p_R=1-p_L$ and class vectors $q_L,q_R$ satisfying $p_L{q}_L+p_R{q}_R=q_t$, the reduction $\Delta i(s,t)=\varphi (q_t)-p_L\varphi (q_L)-p_R\varphi (q_R)\ge 0$; if $\varphi$ is strictly concave, equality holds iff $q_L=q_R=q_t$.

Proof. Apply Jensen's inequality to the concave $\varphi$ and the two-point law placing mass $p_L$ at $q_L$ and $p_R$ at $q_R$, whose mean is $p_L{q}_L+p_R{q}_R=q_t$: $\varphi (q_t)=\varphi (p_L{q}_L+p_R{q}_R)\ge p_L\varphi (q_L)+p_R\varphi (q_R)$, i.e. $\Delta i\ge 0$. For strictly concave $\varphi$, Jensen is strict unless the support is a single point, $q_L=q_R$; combined with $p_L{q}_L+p_R{q}_R=q_t$ this gives $q_L=q_R=q_t$. The Gini index $\varphi (p)={\sum }_k{p}_k(1-p_k)$ and entropy $\varphi (p)=-{\sum }_k{p}_k\log p_k$ are strictly concave, so every non-degenerate split strictly reduces them; misclassification $\varphi (p)=1-{\max }_k{p}_k$ is concave but not strictly, so degenerate-looking splits can leave it unchanged. $\square$

Proposition 3 (weakest-link pruning: existence, uniqueness, nestedness). For a grown tree $T_{\max }$ and each $\alpha \ge 0$ there is a unique smallest subtree $T(\alpha )$ minimising $C_{\alpha }$, and these are nested in $\alpha$, obtained by iteratively collapsing the node of least link strength $g(t)=(R(t)-R(T_t))/(|T_t|-1)$.

Proof. For a node $t$, comparing the branch $T_t$ with its collapse $\{t\}$ under $C_{\alpha }$: keeping the branch is preferred while $R(T_t)+\alpha |T_t|<R(t)+\alpha$, i.e. while $\alpha <g(t)$, and collapsing is (weakly) preferred once $\alpha \ge g(t)$. Hence below ${\alpha }_1:={\min }_{t}g(t)$ no collapse improves $C_{\alpha }$ and $T(\alpha )=T_{\max }$. At $\alpha ={\alpha }_1$, collapsing every node attaining the minimum leaves $C_{{\alpha }_1}$ unchanged while reducing $|T|$, so the collapsed tree $T({\alpha }_1)$ is a minimiser with strictly fewer leaves than $T_{\max }$; it is the smallest minimiser because any subtree with even one of the weakest branches retained has the same $C_{{\alpha }_1}$ but more leaves, and any subtree collapsing a non-weakest branch has strictly larger $C_{{\alpha }_1}$. Uniqueness of the smallest minimiser at general $\alpha$: if $T^{\prime },T^{\prime \prime }$ both minimise $C_{\alpha }$, then on any node where they differ one is a collapse of the other and both have equal $C_{\alpha }$, so their common pruned subtree $T^{\prime }\wedge T^{\prime \prime }$ also minimises $C_{\alpha }$ and has no more leaves than either; the minimiser of least leaf count is therefore unique. Recomputing $g(\cdot )$ on $T({\alpha }_1)$ and repeating yields ${\alpha }_2>{\alpha }_1$ (link strengths only rise after the weakest links are removed) and $T({\alpha }_2)\prec T({\alpha }_1)$; each step deletes at least one node, so after finitely many steps the chain reaches the root, giving the finite nested sequence. $\square$

Proposition 4 (variance of an average of correlated trees). Let ${\hat{f}}_1,\dots ,{\hat{f}}_B$ be identically distributed tree predictions at a point with common variance ${\sigma }_T^2$ and pairwise correlation $\rho \ge 0$. The bagged predictor $\bar{f}=\frac{1}{B}{\sum }_b{\hat{f}}_b$ has variance $\mathrm{Var}(\bar{f})=\rho {\sigma }_T^2+\frac{1-\rho }{B}{\sigma }_T^2$.

Proof. $\mathrm{Var}(\bar{f})=\frac{1}{B^2}({\sum }_b\mathrm{Var}({\hat{f}}_b)+{\sum }_{b\ne b^{\prime }}\mathrm{Cov}({\hat{f}}_b,{\hat{f}}_{b^{\prime }}))=\frac{1}{B^2}(B{\sigma }_T^2+B(B-1)\rho {\sigma }_T^2)=\frac{{\sigma }_T^2}{B}+\frac{B-1}{B}\rho {\sigma }_T^2=\rho {\sigma }_T^2+\frac{1-\rho }{B}{\sigma }_T^2$. As $B\to \infty$ the second term vanishes, leaving the floor $\rho {\sigma }_T^2$: averaging removes the part of the variance that decorrelation, not count, controls — the quantitative case for random forests over plain bagging. $\square$

Connections Master

• The squared-error splitting criterion and the leaf-mean fit specialise the least-squares regression developed in 26.06.01: a regression tree is a sequence of plain constant-mean regressions on adaptively chosen rectangular subsamples, and the within-node SSE the tree minimises is the residual sum of squares of that local constant fit, so the foundational accounting is the same orthogonality-of-residuals identity, applied piecewise rather than globally.

• The risk a tree estimates is the conditional expectation $\mathbb{E}[Y\mid X=x]$ of the joint law set up in 37.01.01; the leaf average ${\bar{y}}_{R(x)}$ is the empirical conditional mean over the leaf cell, and consistency of trees and forests is the statement that these adaptive cell-averages converge to the regression function as the cells shrink while retaining points — the partition-estimator face of the law of large numbers on the probability space of that unit.

• Trees are the base learners of the ensemble methods in 45.08.05 (bagging and random forests) and 45.08.06 (boosting): the high-variance, low-bias profile proved in Theorem 3 and Proposition 4 is exactly the regime where bootstrap averaging and split-decorrelation pay off, and the shallow stumps boosting reweights are pruned trees at the small-$|T|$ end of the cost-complexity chain, so this unit supplies the object those units combine.

• The nearest-neighbour reading of Theorem 4 ties CART to the adaptive local-averaging estimators studied in nonparametric regression: a tree, a forest, and a $k$-nearest-neighbour rule are one weighted-average estimator ${\sum }_i{w}_i(x)y_i$ differing only in how the data-dependent weights $w_i(x)$ are formed, which is the central insight that lets the consistency theory of partition estimators and of local averaging be developed together.

Historical & philosophical context Master

Recursive partitioning predates CART — automatic interaction detection (AID) of Morgan and Sonquist (1963) split survey data by variance reduction, and THAID and CHAID followed in the 1970s — but these early programs grew trees without a principled stopping rule and were criticised for overfitting and for greedy selection bias. The decisive synthesis is the 1984 monograph of Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone, Classification and Regression Trees ^{[Breiman 1984]}, which introduced the impurity-reduction splitting criterion, the Gini and twoing rules, surrogate splits for missing data, and — the technical heart — cost-complexity pruning with its weakest-link algorithm and cross-validated tree selection, replacing ad-hoc stopping with grow-then-prune.

The statistical-learning recasting in Hastie, Tibshirani, and Friedman's Elements of Statistical Learning (2001; 2nd ed. 2009) ^{[Hastie 2009]} placed CART within the bias-variance framework and made the instability of single trees the explicit motivation for the ensemble methods Breiman himself went on to develop — bagging (1996) and random forests (2001). The identification of trees and forests as adaptive nearest-neighbour estimators is due to Lin and Jeon (2006) ^{[Lin 2006]}, who introduced the potential-nearest-neighbour weighting that subsequent consistency proofs for random forests rely on. The interpretability-versus-accuracy tension that runs through tree methodology — a single tree is readable but unstable, an averaged forest is accurate but opaque — remains the defining trade-off of the family and the reason both single trees and their ensembles persist side by side in applied practice.

Bibliography Master

@book{breiman1984cart,
  author    = {Breiman, Leo and Friedman, Jerome H. and Olshen, Richard A. and Stone, Charles J.},
  title     = {Classification and Regression Trees},
  publisher = {Wadsworth},
  address   = {Belmont, CA},
  year      = {1984}
}

@book{hastie2009esl,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009}
}

@article{morgansonquist1963,
  author  = {Morgan, James N. and Sonquist, John A.},
  title   = {Problems in the analysis of survey data, and a proposal},
  journal = {Journal of the American Statistical Association},
  volume  = {58},
  number  = {302},
  pages   = {415--434},
  year    = {1963}
}

@article{breiman1996bagging,
  author  = {Breiman, Leo},
  title   = {Bagging predictors},
  journal = {Machine Learning},
  volume  = {24},
  number  = {2},
  pages   = {123--140},
  year    = {1996}
}

@article{breiman2001randomforests,
  author  = {Breiman, Leo},
  title   = {Random forests},
  journal = {Machine Learning},
  volume  = {45},
  number  = {1},
  pages   = {5--32},
  year    = {2001}
}

@article{linjeon2006,
  author  = {Lin, Yi and Jeon, Yongho},
  title   = {Random forests and adaptive nearest neighbors},
  journal = {Journal of the American Statistical Association},
  volume  = {101},
  number  = {474},
  pages   = {578--590},
  year    = {2006}
}