Regression Trees

How a tree predicts a number. Why each leaf predicts its mean, the residual-sum-of-squares split criterion and the identity that makes it a comparison of two means, recursive binary splitting worked by hand on eight patients, the depth-2 tree for 442 diabetes patients, cost-complexity (weakest-link) pruning derived and worked, and choosing the tree size by cross-validation.

A regression tree predicts a numerical outcome by sorting each case into one of a few groups and predicting the group's average. Introduction to Decision Trees showed the result for the diabetes study of 442 patients (Efron, Hastie, Johnstone and Tibshirani, 2004): four groups, defined by two thresholds on BMI and one on the serum measurement S5, with average disease progression ranging from 96 to 226. This article derives how such a tree is found. It works the algorithm by hand on eight patients, applies it to all 442, and then takes up the question every tree method has to answer: how large the tree should be.

The method is the regression half of CART (Breiman, Friedman, Olshen and Stone, 1984), presented here following James, Witten, Hastie and Tibshirani (2021, §8.1.1), and the squared-error loss that defines it is the same one that defines least squares.

What a leaf should predict

Suppose the tree has already divided the inputs into regions $R_1, \dots, R_M$, and every case that falls in region $R_m$ will receive the same prediction $c_m$. Judged by squared error, the best choice of $c_m$ is the one that minimizes

$$\sum_{i \in R_m} (y_i - c_m)^2,$$

the sum over the training cases in the region. Setting the derivative with respect to $c_m$ to zero gives $-2 \sum_{i \in R_m} (y_i - c_m) = 0$, so $n_m c_m = \sum_{i \in R_m} y_i$ and

$$c_m = \bar{y}_{R_m},$$

the mean outcome of the $n_m$ training cases in the region. The second derivative is $2 n_m > 0$, so this is a minimum. A regression tree predicts the leaf mean for the same reason the least-squares line passes through the point of means: it is what squared error asks for. The quantity that remains, the sum of squared deviations from the leaf mean, is the leaf's contribution to the residual sum of squares, and the RSS of the whole tree is

$$\mathrm{RSS} = \sum_{m=1}^{M} \sum_{i \in R_m} \bigl(y_i - \bar{y}_{R_m}\bigr)^2$$

(James et al., 2021, eq. 8.1). A good tree has small RSS, and the job of the algorithm is to choose regions that make it small.

Choosing one split

Searching over all possible collections of regions is computationally infeasible, so the tree is grown one split at a time (see the introduction). A single split takes the cases in a node and divides them by one input $X_j$ and a threshold $s$ into

$$R_1(j, s) = \{X \mid X_j \le s\} \quad\text{and}\quad R_2(j, s) = \{X \mid X_j > s\},$$

and the best split is the pair $(j, s)$ that minimizes the RSS of the two halves,

$$\sum_{i:\, x_i \in R_1(j,s)} \bigl(y_i - \bar{y}_{R_1}\bigr)^2 + \sum_{i:\, x_i \in R_2(j,s)} \bigl(y_i - \bar{y}_{R_2}\bigr)^2$$

(James et al., 2021, eqs. 8.2 and 8.3, which put the boundary case $X_j = s$ on the right; scikit-learn puts it on the left, as here). For each input, only thresholds between adjacent distinct values need to be tried, so an input with $k$ distinct values in the node offers $k - 1$ candidates.

A split compares two means

The criterion has a cleaner form. Write $n$ for the number of cases in the node, $\bar{y}$ for their mean, and $n_L, \bar{y}_L$ and $n_R, \bar{y}_R$ for the counts and means on the left and right. Split each deviation from the node mean into a deviation from the side's mean plus the side's offset, $y_i - \bar{y} = (y_i - \bar{y}_L) + (\bar{y}_L - \bar{y})$ for a case on the left. Squaring and summing over the left side, the cross term vanishes because deviations from $\bar{y}_L$ sum to zero, leaving $\sum_L (y_i - \bar{y}_L)^2 + n_L(\bar{y}_L - \bar{y})^2$. Doing the same on the right and adding,

$$\underbrace{\sum_{i} (y_i - \bar{y})^2}_{\text{RSS before}} = \underbrace{\sum_{L} (y_i - \bar{y}_L)^2 + \sum_{R} (y_i - \bar{y}_R)^2}_{\text{RSS after}} + n_L (\bar{y}_L - \bar{y})^2 + n_R (\bar{y}_R - \bar{y})^2.$$

The node mean is the weighted average of the side means, $\bar{y} = (n_L \bar{y}_L + n_R \bar{y}_R)/n$, so $\bar{y}_L - \bar{y} = n_R (\bar{y}_L - \bar{y}_R)/n$ and $\bar{y}_R - \bar{y} = -n_L (\bar{y}_L - \bar{y}_R)/n$. Substituting, the last two terms become $(n_L n_R^2 + n_R n_L^2)(\bar{y}_L - \bar{y}_R)^2 / n^2$, and since $n_L + n_R = n$,

$$\text{RSS before} - \text{RSS after} = \frac{n_L\, n_R}{n} \bigl(\bar{y}_L - \bar{y}_R\bigr)^2.$$

Three things follow. A split can never increase the RSS, because the reduction is a square times a positive number, which is why training error always falls as a tree grows. Minimizing the RSS after a split is the same as maximizing this reduction. And the reduction rewards two things at once: a large gap between the two sides' means, and a balanced split, since $n_L n_R / n$ is largest when $n_L = n_R$. A threshold that peels off a single extreme case produces a large gap but a factor of only $(n-1)/n \approx 1$, while an even split multiplies the squared gap by $n/4$.

The identity also makes the search fast. Sort the node's cases by $X_j$ and move the threshold from left to right one case at a time, keeping running totals of $n_L$ and $\sum_L y_i$; each candidate's reduction then costs a constant amount of work, so all thresholds on one input are scored in a single pass after an $O(n \log n)$ sort.

Eight patients by hand

The first eight patients in the diabetes data have these values of BMI, S5 (described in the scikit-learn documentation as possibly the logarithm of the serum triglycerides level) and progression after one year:

Patient BMI S5 Progression $y$
1 32.1 4.8598 151
2 21.6 3.8918 75
3 30.5 4.6728 141
4 25.3 4.8903 206
5 23.0 4.2905 135
6 22.6 4.1897 97
7 22.0 3.9512 138
8 26.2 4.2485 63

The mean progression is 125.75, and the RSS of predicting that mean for all eight is 14,885.50. With eight distinct values, each input offers seven thresholds. For each, the table gives the patients on the left, the two means and the RSS after the split. Thresholds are midpoints between adjacent values.

BMI ≤ Left Means (left, right) RSS after
21.8 2 75.00, 133.00 11,942.00
22.3 2, 7 106.50, 132.17 13,897.33
22.8 2, 7, 6 103.33, 139.20 12,473.47
24.15 + 5 111.25, 140.25 13,203.50
25.75 + 4 130.20, 118.33 14,621.47
28.35 + 8 119.00, 146.00 13,792.00
31.3 + 3 122.14, 151.00 14,156.86
S5 ≤ Left Means (left, right) RSS after
3.9215 2 75.00, 133.00 11,942.00
4.07045 2, 7 106.50, 132.17 13,897.33
4.2191 2, 7, 6 103.33, 139.20 12,473.47
4.2695 + 8 93.25, 158.25 6,435.50
4.48165 + 5 101.60, 166.00 7,109.20
4.7663 + 3 108.17, 178.50 7,465.33
4.87505 + 1 114.29, 206.00 7,525.43

The first three rows agree because patients 2, 7 and 6 have the three lowest values of both inputs. After that the inputs diverge. On BMI, no threshold does better than isolating patient 2, which removes 2,943.50. On S5, the threshold 4.2695, halfway between patients 8 and 5, separates four patients with mean progression 93.25 from four with mean 158.25, and leaves an RSS of 3,264.75 on the left plus 3,170.75 on the right, 6,435.50 in all. The identity confirms the reduction: $\frac{4 \times 4}{8}(158.25 - 93.25)^2 = 2 \times 65^2 = 8{,}450$, which is $14{,}885.50 - 6{,}435.50$. That is the best of the fourteen candidates, so the root asks whether S5 is at most 4.2695, and the split removes 0.568 of the RSS.

Left: the eight patients' progression against S5, with the root split (dashed) and the mean on each side; the green segments are the residuals whose squares make up the RSS. Right: the RSS after each of the seven possible splits on each input. S5 and BMI order the first three patients identically, so the curves start together; S5 then finds a split that halves the error, while BMI never does better than its first threshold.
Left: the eight patients' progression against S5, with the root split (dashed) and the mean on each side; the green segments are the residuals whose squares make up the RSS. Right: the RSS after each of the seven possible splits on each input. S5 and BMI order the first three patients identically, so the curves start together; S5 then finds a split that halves the error, while BMI never does better than its first threshold.

The procedure now repeats inside each half, independently. The left node holds patients 2, 6, 7 and 8, with RSS 3,264.75. Its best split, among both inputs, is BMI at most 24.4, which separates patient 8 (BMI 26.2, progression 63) from the other three (mean 103.33) and leaves an RSS of 2,044.67. The right node holds patients 1, 3, 4 and 5, with RSS 3,170.75. Its best split is S5 at most 4.87505, which separates patient 4 (progression 206) from the other three (mean 142.33) and leaves an RSS of 130.67. The resulting depth-2 tree has four leaves, two of them holding a single patient, and its RSS of 2,175.33, against the starting 14,885.50, gives an $R^2$ of 0.854 on these eight patients. With eight patients, a tree of this size is mostly describing the eight patients. Leaves with one case are exactly the fragile predictions that the rest of this article is about controlling.

The tree for 442 patients

On all 442 patients the root search covers ten inputs. The best threshold for each, and the share of the total sum of squares (2,621,009) it removes:

Input Best root split Share of RSS removed
S5 ≤ 4.6 0.292
BMI ≤ 27.25 0.278
S4 ≤ 3.705 0.179
BP ≤ 101.5 0.170
S3 ≤ 45.5 0.149
S6 ≤ 99.5 0.130
S1 ≤ 193.5 0.060
S2 ≤ 126.5 0.046
age ≤ 50.5 0.039
sex ≤ 1.5 0.002

S5 wins narrowly over BMI. The ranking resembles the ranking of the inputs by their correlation with progression in Introduction to Regression, but it measures something different: the best that one threshold can do, not how well a straight line fits. Splitting again within each half gives the depth-2 tree.

The depth-2 regression tree for the 442 patients, with the number of patients, mean progression and RSS in every node. The four leaves' RSS add up to 1,485,142, down from 2,621,009 at the root.
The depth-2 regression tree for the 442 patients, with the number of patients, mean progression and RSS in every node. The four leaves' RSS add up to 1,485,142, down from 2,621,009 at the root.

Both second-level splits use BMI, at slightly different thresholds: 26.95 among patients with low S5, 27.75 among those with high S5. The leaves' RSS add up to 1,485,142, so the tree's $R^2$ on the training data is $1 - 1{,}485{,}142 / 2{,}621{,}009 = 0.433$. Each further level reduces the training RSS: depth 1 reaches $R^2 = 0.292$, depth 3 (8 leaves) 0.501, depth 4 (16 leaves) 0.576, depth 6 (55 leaves) 0.745, depth 10 (278 leaves) 0.965, and the fully grown tree, with 432 leaves, reproduces the training data exactly. None of these later gains says anything about new patients.

A staircase instead of a line

With BMI as the only input, the tree's prediction is a step function of BMI. The first split, at 27.25, divides the patients into those predicted 120.8 and those predicted 204.8, an $R^2$ of 0.278. Depth 2 adds thresholds at 24.35 and 33.15 and reaches 0.366, slightly better than the straight line's 0.344; depth 4, with 16 leaves, reaches 0.408.

Progression against BMI with regression trees of depth 1, 2 and 4 fitted to BMI alone, and the least-squares line (dotted). The trees' predictions are flat between thresholds. The depth-4 tree spends some of its 16 leaves on narrow intervals, such as the spike near BMI 25, that follow a few patients rather than a trend.
Progression against BMI with regression trees of depth 1, 2 and 4 fitted to BMI alone, and the least-squares line (dotted). The trees' predictions are flat between thresholds. The depth-4 tree spends some of its 16 leaves on narrow intervals, such as the spike near BMI 25, that follow a few patients rather than a trend.

The steps reveal two properties of trees. Within the data, the depth-4 tree uses narrow intervals to chase a handful of patients, and its gain in training $R^2$ is not evidence of a real pattern. Outside the data the tree is flat: for a BMI of 60, far beyond the largest observed value of 42.2, the depth-1 tree predicts 204.8 and the depth-4 tree 242.0, the means of their last leaves, while the line predicts 496.2. Neither answer is supported by data (see extrapolation), but the tree's failure is of a particular kind: it can never predict outside the range of the training outcomes, because every prediction is an average of training outcomes.

How large a tree?

The training RSS always prefers the largest tree, so it cannot choose the size. One option is to stop growing early: stop when no split reduces the RSS by more than some amount, or when nodes become small. James et al. (2021, §8.1.1) call the first rule "too short-sighted", because a split that looks worthless can make way for a very good split below it.

A synthetic example shows how short-sighted. Draw 400 points uniformly in the square $[-1, 1]^2$ and set $y = 10 + 5\,\mathrm{sign}(x_1 x_2) + \varepsilon$, with $\varepsilon$ normal with standard deviation 1. The outcome is high in two opposite quadrants and low in the other two, a checkerboard. Any single vertical or horizontal cut leaves both sides with roughly equal shares of high and low, so the best first split removes only 0.011 of the RSS, and in this sample the second level adds almost nothing (training $R^2$ 0.018; in other random samples the jump comes one level earlier or later, but the first split is always weak). A rule that stopped at the first unproductive split would return a tree that predicts the mean everywhere. Allowed to continue, the tree finds the structure: training $R^2$ jumps to 0.351 at depth 3 and 0.816 at depth 4, and on 2,000 fresh test points a depth-4 tree scores 0.815, against a ceiling of $25/26 = 0.962$ set by the noise. The splits that matter only become visible after splits that do not.

Cost-complexity pruning

The remedy is to grow a large tree $T_0$ first and then cut it back. The candidates are the subtrees of $T_0$, trees obtained by collapsing some internal nodes into leaves. There are far too many to evaluate each by cross-validation, so CART orders them by a penalized criterion (Breiman et al., 1984; James et al., 2021, §8.1.1). For a tuning parameter $\alpha \ge 0$, the cost complexity of a subtree $T$ is

$$C_\alpha(T) = \sum_{m=1}^{|T|} \sum_{i:\, x_i \in R_m} \bigl(y_i - \bar{y}_{R_m}\bigr)^2 + \alpha\, |T|,$$

where $|T|$ is the number of leaves (James et al., 2021, eq. 8.4). The first term is the training RSS; the second charges $\alpha$ for every leaf. At $\alpha = 0$ the best subtree is $T_0$ itself. As $\alpha$ grows, leaves become more expensive and the best subtree shrinks, until for large enough $\alpha$ it is the root alone. The construction parallels the lasso, which adds a penalty on the size of the coefficients to the RSS of a linear model.

Which subtrees appear as $\alpha$ grows can be worked out exactly. Take an internal node $t$, write $R(t)$ for the RSS if $t$ were collapsed into a single leaf, and $R(T_t)$ for the RSS of the leaves of the branch $T_t$ below it, which has $|T_t|$ leaves. Collapsing $t$ changes the cost complexity by

$$\Delta C_\alpha = \bigl[R(t) + \alpha\bigr] - \bigl[R(T_t) + \alpha |T_t|\bigr] = R(t) - R(T_t) - \alpha \bigl(|T_t| - 1\bigr),$$

which is zero or negative, so collapsing pays, once

$$\alpha \ge g(t) = \frac{R(t) - R(T_t)}{|T_t| - 1}.$$

The quantity $g(t)$ is the reduction in RSS that the branch below $t$ buys per extra leaf. The internal node with the smallest $g(t)$ is the weakest link: as $\alpha$ rises from 0, it is the first branch worth removing. Collapse it, recompute $g$ for the nodes above it (their branches now have fewer leaves), and repeat. The result is a nested sequence of subtrees, each obtained from the previous one by collapsing one weakest link, together with the values of $\alpha$ at which the switches happen; James et al. (2021, §8.1.1) note that this nesting is what makes the whole sequence "easy" to obtain.

The depth-2 diabetes tree is small enough to prune by hand. Its three internal nodes give:

Node $R(t)$ $R(T_t)$ Leaves below $g(t)$
Root, S5 ≤ 4.6 2,621,009 1,485,142 4 378,622
Low S5, BMI ≤ 26.95 706,499 558,148 2 148,351
High S5, BMI ≤ 27.75 1,150,377 926,995 2 223,382

The weakest link is the BMI split among low-S5 patients: it reduces the RSS by 148,351 for its one extra leaf, the least of the three. For $\alpha$ between 0 and 148,351 the best subtree is the full four-leaf tree; at 148,351 that split is collapsed, leaving three leaves. The next link is the other BMI split, collapsed at $\alpha = 223{,}382$. The root now has two leaves below it with RSS 1,856,876, so its $g$ has become $(2{,}621{,}009 - 1{,}856{,}876)/1 = 764{,}133$, and above that value only the root remains. scikit-learn's cost_complexity_pruning_path returns the same breakpoints divided by $n = 442$ (335.64, 505.39 and 1,728.81), because it measures impurity as mean squared error weighted by the fraction of cases in each node, which puts $\alpha$ on a per-observation scale.

Choosing alpha by cross-validation

Pruning turns the choice of tree size into the choice of one number, and that number is chosen the way any tuning parameter is chosen: by estimating prediction error on data not used for fitting. James et al. (2021, Algorithm 8.1) put the steps together:

  1. Grow a large tree on the training data, stopping only when nodes become small.
  2. Compute the sequence of best subtrees as a function of $\alpha$.
  3. Use $K$-fold Cross-Validation to estimate the prediction error for each $\alpha$: for each fold, repeat steps 1 and 2 on the other folds and measure the squared error on the held-out fold. Pick the $\alpha$ with the smallest average error.
  4. Return the subtree of the full-data tree for that $\alpha$.

For the diabetes data, a tree grown until leaves would fall below five patients has 69 leaves and depth 11, and a training $R^2$ of 0.762. Its pruning sequence has 57 subtrees. Ten-fold cross-validation, with the same folds used for the linear models in Multiple Linear Regression, gives these estimates of mean squared prediction error:

Leaves Training MSE Cross-validated MSE (SE)
69 (unpruned) 1,413 4,833 (280)
12 2,601 4,185 (162)
6 3,058 3,932 (201)
5 3,178 3,889 (225)
4 3,360 3,868 (237)
3 3,696 4,103 (235)
2 4,201 4,461 (273)
Training and cross-validated mean squared error along the pruning sequence for the diabetes data. Training error falls steadily as leaves are added. Cross-validated error is lowest at 4 leaves and climbs as the tree grows: the unpruned 69-leaf tree predicts new patients worse than a two-leaf tree.
Training and cross-validated mean squared error along the pruning sequence for the diabetes data. Training error falls steadily as leaves are added. Cross-validated error is lowest at 4 leaves and climbs as the tree grows: the unpruned 69-leaf tree predicts new patients worse than a two-leaf tree.

The cross-validated error is lowest at four leaves, and the four-leaf subtree is exactly the depth-2 tree derived above. Its estimated error, 3,868, corresponds to an $R^2$ of about 0.348 on new patients, against 0.433 on the training data. The unpruned tree's cross-validated error of 4,833 is worse than that of the two-leaf tree. The standard errors are a reminder that the curve is itself an estimate: the three-leaf tree's error is within one standard error of the minimum, and the one-standard-error rule, which picks the smallest model whose estimated error is within one standard error of the best (James et al., 2021, §6.1.3), would choose it.

Choosing $\alpha$ on the same folds that report the error makes that error slightly optimistic. The honest estimate repeats the whole procedure, including the choice of $\alpha$ by an inner cross-validation, inside each of the ten outer training folds. It gives a cross-validated $R^2$ of 0.342 for the pruned tree, compared with 0.322 for a tree fixed at depth 2, 0.173 for the unpruned 69-leaf tree, and $-0.211$ for a fully grown tree, which predicts new patients worse than their mean does.

Trees compared with linear regression

On the diabetes data a linear regression on all ten inputs reaches a cross-validated $R^2$ of 0.484 with the same folds, well ahead of the best pruned tree. This is the expected result when the relationship is roughly additive and linear, as it appears to be here: a line uses every patient to estimate each slope, while a tree spends its data on locating thresholds and averaging within small groups (James et al., 2021, §8.1.3). The tree's advantages lie elsewhere. It needs no decision about which inputs to transform or which interactions to include, it handles inputs with very different scales without standardization, and its four-leaf version can be explained in one sentence: patients with high S5 and high BMI progressed most, by about 130 units more on average than patients low on both.

Some properties are worth stating carefully because they are often overstated. Trees are insensitive to extreme input values, since a threshold depends only on the order of the inputs. They are not insensitive to extreme outcome values: a leaf predicts a mean and splits are chosen by squared error, so one very large $y$ pulls its leaf's prediction and can attract a split of its own. Using absolute error as the criterion (criterion="absolute_error" in scikit-learn, which predicts leaf medians) reduces that sensitivity. And trees offer no standard errors or confidence intervals for their predictions of the kind that linear regression provides under its assumptions.

The largest weakness is instability: the diabetes tree's thresholds and even its root input would change with a different sample of patients, as the introduction shows for the breast cancer data. Averaging many trees, as random forests do, keeps the flexibility of trees while removing much of that variance; on the diabetes data a random forest reaches a cross-validated $R^2$ of 0.443, between the pruned tree and the linear model.

In Python

import numpy as np
from sklearn.datasets import load_diabetes
from sklearn.model_selection import KFold, cross_val_score
from sklearn.tree import DecisionTreeRegressor, export_text

data = load_diabetes(scaled=False)
X, y = data.data, data.target

tree = DecisionTreeRegressor(max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=data.feature_names))   # s5 <= 4.60, then bmi
print(tree.score(X, y))                                      # 0.433 on the training data

big = DecisionTreeRegressor(min_samples_leaf=5, random_state=0)
path = big.cost_complexity_pruning_path(X, y)                # alphas per observation
folds = KFold(10, shuffle=True, random_state=0)
scores = [cross_val_score(DecisionTreeRegressor(min_samples_leaf=5, random_state=0, ccp_alpha=a),
                          X, y, cv=folds, scoring="neg_mean_squared_error").mean()
          for a in path.ccp_alphas[:-1]]
best = path.ccp_alphas[int(np.argmax(scores))]               # about 181.8 per observation
pruned = DecisionTreeRegressor(min_samples_leaf=5, random_state=0, ccp_alpha=best).fit(X, y)
print(pruned.get_n_leaves())                                 # 4

ccp_alpha applies the pruning after the tree is grown; max_depth, min_samples_split and min_samples_leaf are the stopping rules applied while it grows. Wrapping the search in GridSearchCV and that in cross_val_score gives the honest nested estimate. The numbers in this article are computed by tools/experiments/data-science/regression-trees.py in the site's repository.

References

  • Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth. record · 3 pages
  • Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. record · 12 pages
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages