How to build a regression tree from scratch

The decision-tree article built a CART classifier in pure Python and left the regression case as two edits: point the same code at a numeric target, replace the impurity measure with the variance of that target, and let each leaf hold the average of its rows instead of a tally of labels. Here we make those edits, and then keep going.

They really are small, which is the good news: candidate generation, the greedy split search, the recursion and the stopping rule all carry over untouched, and none of that machinery is re-derived below. What earns an article of its own is everything downstream of them. Predicting a number instead of a category gives the tree a different question to answer, a different way of failing when you let it grow, and one hard limitation a classifier could never have run into — because a category has no notion of “beyond the range I have seen,” and a number does.

So: two functions, five rows scored by hand, and then the properties that only appear once the target is continuous.

What carries over

Candidate questions are generated exactly as before — every feature paired with every value that feature takes in the rows at hand, one pair per question, with a numeric column asking >= and a categorical column asking ==. Nothing about that generator knows or cares what the target column contains: five rows with two columns of four distinct values each produce eight candidates whether you are predicting a disease or a salary.

Laid out step by step, here is the entire algorithm with the two edits marked:

One row deserves a note, because it is easy to assume that scoring is where regression needs different arithmetic. In our code it does not — info_gain is untouched, and only the function called inside it changes:

# classifier
return current_uncertainty - p * gini(left)     - (1 - p) * gini(right)
# regressor
return current_uncertainty - p * variance(left) - (1 - p) * variance(right)

That is the continuity claim in one line: the scoring scheme was never specific to labels, so swapping the impurity is enough. What the criterion means once the target is a number has a simpler statement than this formula, and we get to it after building the impurity up.

Two rows in bold — and they are not peers, which the third column gives away. Only one of the two edits changes the tree you get.

Look at where the leaf is built:

def build_tree(rows):
    gain, question = find_best_split(rows)
    if gain == 0:
        return RegressionLeaf(rows)          # <- built last, never read
    true_rows, false_rows = partition(rows, question)
    return Decision_Node(question, build_tree(true_rows), build_tree(false_rows))

The leaf is constructed at the bottom of the recursion and its stored value is never consulted again while the tree is being grown. Nothing about mean versus class_counts can influence which question a node asks or when the splitting stops — those decisions come from find_best_split, and find_best_split reads exactly one thing about the target column: the impurity.

So the honest summary is narrower than “two changes.” The impurity function is the tree-building change — swap gini for variance and every split in the tree can move. The leaf statistic is a prediction-time change: it decides what a finished tree says, not what it is. Hand the same tree the two different leaf classes and you get identical questions in identical places, answering with a tally in one case and a number in the other.

They are still a matched pair, though, which is why you would never swap one without the other. Variance is the squared error of predicting the mean — the impurity measures the cost of the summary the leaf is going to store, so the two are two halves of one decision about what a leaf’s answer means. That coupling is exactly what the section on choosing the criterion cashes in: pick absolute error as the impurity and the leaf must hold the median instead, because that is the constant absolute error is minimised by.

The five players

The dataset is five players from the Hitters study — two numeric predictors, one numeric target:

years is seasons played in the major leagues, hits is hits in the previous season, salary is the 1987 salary in thousands of dollars. These are real rows from the real study, checked against the full file.

Rows 1 and 2 are a genuine collision — same years, same hits, different salary. They are the regression counterpart of the two heart patients who produced a 50/50 leaf in the classification article, and they will set a floor no tree can get under.

Measuring the spread of a dataset

We still build the same list of candidate questions, so the thing left to understand is how to score them and decide which one becomes the node’s question. For that we need a measure of how spread out a pile of numbers is, called variance — the counterpart of Gini impurity, which measured how mixed a pile of labels was. And we need a way to score each question by how much of that spread it removes: how much less scattered its two piles come out than the pile they came from. That score is the reduction in total squared error, the counterpart of information gain, and the question with the most of it wins.

Take the measure first. Here are two squads of five, and the thing to notice is that they have the same mean:

Squad B is our five players. Squad A is a hypothetical club where everyone earns about the same. The mean cannot tell them apart — it reports 420 for both — and yet one is a payroll where every player is interchangeable and the other has a twelvefold gap between its best-paid and worst-paid man.

The obvious move is to measure how far each salary sits from the mean:

Both sum to zero, and that is not a coincidence about these numbers — it is what the mean is. The mean is the balance point of the set, so whatever sits above it exactly cancels whatever sits below. Averaging raw deviations gives 0 for every set that has ever existed, which makes it useless as a measure of anything.

So we need the magnitudes, discarding the signs. Two ways to do that: take absolute values, or square. Squaring is the conventional choice, for two reasons — it is smooth and differentiable everywhere, where the absolute value has a corner at zero, and it punishes one large miss far more than several small ones. (Absolute values are a real alternative, and choosing them changes the model in a specific way; that is the subject of a later section.)

Square the deviations and average them:

Two sets the mean declared identical are 431 times apart on this measure. Written down, it is:

Which variance this is

We have arrived at variance by construction, but it is a standard statistical quantity and it is worth being explicit about which version of it a tree uses, because there are three and they are easy to run together.

Variance is a property of a probability distribution. For a random variable $Y$ with mean $\mu = E[Y]$, it is

— the expected squared distance of $Y$ from its own mean. That is the theoretical object, defined by probabilities rather than by any dataset.

Given actual observed numbers you compute the same idea directly, which is the formula above. So the three readings are:

A regression tree uses the middle one. It treats the target values inside a node as an empirical distribution in their own right — it is describing the rows it is holding, not estimating a parameter of some larger population those rows were drawn from. Nothing downstream is inferential: the leaf will answer with the mean of exactly these rows, and the impurity has to be the cost of exactly that answer.

Which is why the $n$ denominator is the correct choice here rather than a shortcut, and why $s^2$ with its $n-1$ would be the wrong tool — it answers a question about a population nobody asked about. Bessel’s correction exists to remove the bias in estimating an unknown population variance; a node has no unknown population.

Why this is the right impurity

Now read that formula a second time, not as a description of spread but as a statement about prediction.

$\bar{y}$ is a guess — one number offered for the whole set. Each $(y_i - \bar{y})$ is how wrong that guess is for one member. Squaring and averaging gives the typical squared error of that one guess across everybody. So variance is not merely describing the pile; it is scoring the best single answer available for it.

That is exactly the job an impurity measure has to do, because a leaf gives every row that reaches it the same prediction. The classification article put the question this way: if I had to summarise this pile of rows with a single answer, how badly would I do? For a pile of labels, the best single answer is the class proportions and Gini is what predicting them costs. For a pile of numbers, the best single answer is the mean and variance is what predicting it costs.

So class_counts/gini and mean/variance are the same pair in two currencies — a summary of a pile, and the cost of using that summary. Which is also why swapping one without the other makes no sense, and why the split criterion and the leaf statistic always arrive together.

def mean(rows):
    return sum(row[-1] for row in rows) / float(len(rows))

def variance(rows):
    targets = [row[-1] for row in rows]
    m = sum(targets) / len(targets)
    return sum((t - m) ** 2 for t in targets) / len(targets)

Those are the two edits from the table above. What we have now is a number for a single node — the regression counterpart of Gini. Turning it into a score for a split is the next step, and the counterpart of information gain.

RSS reduction — scoring a split

A split takes one pile and makes two, and each child will answer with its own mean. So the question is simply how much squared error is left over afterwards, added up across both children:

The best question is the one that leaves this smallest. That is the whole criterion, and it is the one the standard reference states — equation 8.1 of An Introduction to Statistical Learning, written there over all $J$ boxes of a finished tree rather than the two in front of us.

Two things are worth noticing about how little it asks for.

There is no weighting to argue about. The classification article had to make a case for weighting each child by its share of the rows — without it, a split that peels off one already-pure row looks as good as one that cleans up half the dataset. Here that problem cannot arise, because we are adding up totals rather than averaging: a child holding one row contributes one row’s worth of error, and a child holding a hundred contributes a hundred rows’ worth. Counting is the weighting.

And there is no parent term. Every candidate at a node is scored against the same pile, so the parent’s error is a constant that shifts all the scores equally and changes no ranking. It can be subtracted or ignored.

Why removing spread is the right thing to want

It is worth being clear that this is not a heuristic that happens to correlate with good trees. The spread is what a single answer costs, so removing spread is removing prediction error, in the same units, with nothing lost in translation. Before the split every row is answered with $\bar{y}_P$ and the model is wrong by $\text{SSE}_P$; afterwards each side is answered with its own mean and the model is wrong by $\text{SSE}_L + \text{SSE}_R$. The difference is exactly how much the question bought.

That difference can never be negative. Each child could have kept the parent’s mean, and instead it uses its own — which by definition is the constant minimising its own squared error. So splitting is always weakly better on the training rows, which is why gain == 0 means “no question helps at all” rather than “some questions hurt”. It is also the reason training error can never tell a tree when to stop, a bill that comes due later.

Now for what the score actually rewards, which is easier to see once the drop is rewritten. Subtract the children from the parent and the whole thing collapses to:

On our winning split that is $\frac{3 \times 2}{5}(645.83 - 81.25)^2 = 382{,}505.21$ — the same number the impurity arithmetic gave, from a formula that never mentions impurity.

Read as two demands on a good question:

• Separation. $(\bar{y}_L - \bar{y}_R)^2$ rewards questions that put high salaries on one side and low ones on the other. A question that divides the rows without divorcing their targets scores zero, however tidy the division looks.
• Balance. $n_L n_R$ is largest when the split is even, so peeling one row off the edge is penalised no matter how pure that one row is.

Both show up in the candidate table two sections from now. The best question there manages $n_L n_R = 3 \times 2 = 6$, the most five rows allow, alongside the widest gap between child means. A candidate that instead isolates the top earner gets $n_L n_R = 1 \times 4 = 4$ and scores less than half as well — a perfectly pure child, bought too cheaply.

One thing this criterion does not do is search for the best tree. It scores the two boxes at one node, greedily, and then recurses. Equation 8.1 describes a whole finished tree, and minimising it properly would mean choosing all $J$ boxes at once — which is intractable, since finding the optimal tree is NP-complete. Splitting one node at a time is the tractable approximation.

What the criterion is and is not doing

Seen purely mechanically — a formula evaluated once per candidate, lowest number wins — it is easy to read this as doing something it is not. Two natural misreadings are that the criterion is trying to keep the tree small, or that it is clustering the rows into tidy groups.

It does neither. Gini gain and variance reduction do not directly minimise the number of splits, and they are not clustering objectives. They greedily search for feature-defined divisions that make the targets in each child easier to predict with a single leaf value — less class heterogeneity in classification, less squared variation around the mean in regression.

The division of labour between the two columns is worth stating exactly, because the impurity function reads only the target and it is tempting to conclude the features are irrelevant to the score. They are not. Features generate the candidate partitions; the targets decide how useful those partitions are. A question about hits is what puts three particular players on one side; their salaries are what make that a good idea. Neither column alone scores anything.

That also means the criterion is closer to a constrained clustering of the target values than to clustering as usually meant: it does form groups, but by similarity in $y$, and only among groupings that can be expressed as thresholds on $x$. Two players with nothing in common in the feature columns will share a leaf if their salaries agree and no available question separates them profitably.

And whether an improvement is worth the extra complexity is a separate question entirely — one the criterion has no opinion about. Every split it can find, it takes. Deciding that a tree has grown far enough is settled by tree-size controls and pruning, which we come to after seeing what happens when nothing settles it at all.

Clarifying a common confusion: RSS, variance, and MSE

RSS, variance and mean squared error are often presented as competing splitting criteria for regression trees. They are not. All three measure the same underlying quantity — the spread of the target values inside a node — and differ only in whether they are stated as a total or as an average.

If a node predicts the mean $\bar{y}$ of the rows that reach it, its residual sum of squares is

and dividing by the number of observations gives the node’s MSE, which is also its variance:

On our five players, all three are the same arithmetic stopped at different points:

np.var(salaries)                 # 86207.50   ddof=0 by default — matches the tree
np.var(salaries, ddof=1)         # 107759.375
statistics.variance(salaries)    # 107759.375 — n-1 by default
statistics.pvariance(salaries)   # 86207.50

Why the totals and the averages are not interchangeable

Because RSS is an unnormalised total while MSE and variance are averages, node size has to enter the calculation somewhere when you combine two children. Minimising the combined child RSS

is equivalent to minimising the size-weighted child MSE

so RSS reduction, weighted MSE reduction and weighted variance reduction all select the same split. What is not equivalent — and this is the actual trap — is adding or averaging the two children’s variances without weighting them.

Take the candidate Is hits >= 77?, which sends Davis, Marshall and Moseby one way and the two collided players the other. Its children have variances of 16,051.39 and 189.06. Average them as they stand:

That number is wrong, and wrong in the direction that matters. The two-player child is nearly pure and gets an equal vote despite holding only 40% of the data, so the split looks better than it is — the same failure the classification article had to guard against, where peeling off one already-pure row scores as well as cleaning up half the dataset. Weight each variance by its share of the rows and it repairs itself:

landing exactly on the combined child RSS divided by the five rows. Variance has to be told about group sizes; RSS already knows, because adding totals counts every observation once by construction.

Which to use, and the classification parallel

The two vocabularies line up with the classification article role for role:

So the practical advice is to let the purpose choose the form:

• Implementing split selection → RSS reduction, $\text{RSS}_P - (\text{RSS}_L + \text{RSS}_R)$. Group sizes are already inside the numbers, the children combine by plain addition, and there is no weighting to remember.
• Explaining a node → variance or MSE, because an average says something about a typical player in that node rather than about how many players happen to be standing in it. A node of 3 and a node of 300 with the same variance are equally dispersed; their RSS values differ by a factor of a hundred and mostly report headcount.

Every split scored

The root holds all five players. Its mean is $2100/5 = 420.0$ and its variance is 86,207.50, so the total squared error we are trying to reduce is $5 \times 86{,}207.50 = 431{,}037.5$.

Candidate questions are generated exactly as before — every feature paired with every value it takes. Two columns with four distinct values each gives eight candidates, of which two fail to divide the rows at all:

The two skipped candidates are the smallest value in each column: every row clears them, so one child gets everything and the other gets nothing. That is not a split, and the same len(true_rows) == 0 guard from the classifier drops them.

The gain column is what the code reports, since info_gain is the function we inherited. Read the winner as total squared error instead and the criterion is easier to see. Is hits >= 77? sends Davis, Marshall and Moseby one way and the two collided players the other:

against the root’s $431{,}037.50$. One question disposes of 89% of the squared error in the dataset, and no other question on offer leaves less behind. (The gain column is the same fact per-observation: $76{,}501.0417 \times 5 = 382{,}505.21$ removed, and $431{,}037.5 - 382{,}505.21 = 48{,}532.29$.)

Two candidates tie exactly at the top — Is years >= 3? and Is hits >= 77?, both 76501.0416666667, because they cut the five players into the same two groups. The >= in find_best_split hands the win to whichever column is scanned last, exactly as it did in the classification article. Here that costs nothing in accuracy, since identical partitions give identical predictions; what it costs is the explanation, and the tree ends up telling a story about hitting when it could equally have told one about seniority.

The tree, and the leaf that is a mean

Run the recursion to completion and it stops when no pile can be divided any further:

Three leaves hold exactly one player each and reproduce his salary perfectly. The fourth holds the collided pair and predicts 81.25, the mean of 67.5 and 95.0.

BillyJo Robidoux     actual    67.5   predicted   81.25
Jack Howell          actual    95.0   predicted   81.25
Alvin Davis          actual   480.0   predicted  480.00
Mike Marshall        actual   670.0   predicted  670.00
Lloyd Moseby         actual   787.5   predicted  787.50

That is textbook memorisation — the tree kept splitting until almost every row had a leaf to itself, exactly as the classifier did, and for the same reason: gain == 0 is the only thing that stops it.

The 81.25 is worth dwelling on, because it is where the “leaf holds the mean” rule earns itself. Why the mean and not, say, the smaller of the two salaries? Because the leaf must emit one number and the loss is squared error, and the constant minimising $\sum_i (y_i - c)^2$ is $\bar{y}$ — differentiate, set to zero, and $c = \bar{y}$ falls out. The leaf statistic is not a convention; it is the solution to the same minimisation the split criterion is running. Impurity and leaf value come from one loss function.

And 81.25 is the floor. No model reading only years and hits can separate these two players, so 378.125 of squared error survives no matter how deep you grow. The tree reports irreducible error by simply landing on it.

That is not an artefact of picking five convenient rows. Across all 263 players in Hitters who have a recorded salary, nine (years, hits) pairs are shared by more than one player, putting 18 players — 7% of the dataset — into a collision. And ours is one of the mildest. The worst is a $310,000 disagreement:

On these two columns alone, a perfect model would still be wrong by an average of $155,000 on Milner and Wilson. The real dataset has seventeen more predictors that would pull them apart; the point is that with any fixed set of features there is a floor, and the leaf mean is how a tree finds it.

The prediction surface is a staircase

A regression tree’s output is piecewise constant. Every row landing in the same leaf gets the same number, so the prediction as a function of the features is a set of flat plateaus with vertical jumps at the thresholds — no slopes anywhere, at any depth.

The figure below fits a full CART regressor to a smooth curve. Drag the depth slider and watch the staircase acquire steps:

At max_depth=1 there are two plateaus and the fit is terrible. By depth 6 there are 27 and the squared error has fallen from 5,816 to 89. The tree is converging on the curve, but it never bends — it approximates a smooth function by chopping it into ever-narrower constant pieces, in the same way a Riemann sum approximates an integral with rectangles.

This is the structural difference from a linear model, and it cuts both ways. A tree needs no assumption that the relationship is linear, monotonic, or smooth, and it picks up interactions between columns for free. What it gives up is the ability to express even the simplest continuous trend compactly: representing $y = 2x$ takes one coefficient in a linear model and an unbounded number of steps in a tree.

With two features, the staircase becomes a terrain

One feature gives a staircase because there is one axis to lay the steps along. Add a second and the same idea becomes a landscape: the tree cuts the plane into rectangles, and the prediction inside each is a flat roof over it.

The two panels below are the same model. On the left, the partition seen from above — the picture the classification article drew for decision regions. On the right, the identical boxes with the predicted value used as height:

Every roof is flat and every wall is vertical, which is the whole content of “piecewise constant” made visible. Raise the depth and the terrain gains blocks the way the staircase gained steps — 2 regions, then 4, 8, 16 — approaching the shape of the data in flat facets, never in slopes.

This pair of views is An Introduction to Statistical Learning’s figure 8.3, which is worth knowing by sight: it is the standard picture of what a regression tree is, and the perspective plot is the one most people remember.

How far does the picture go?

It depends on the number of features, and specifically on the fact that drawing the prediction surface costs one axis per feature plus one for the prediction itself:

Two features is the last case that fits on a page, which is exactly why every textbook picture of a regression tree — including 8.3 — stops there.

The model has no such limit. With $p$ features the tree cuts the space into axis-aligned boxes in $p$ dimensions and predicts a constant inside each one; nothing about the algorithm changes, and every property in this article still holds. It is only the drawing that runs out. The tree we fit on the full Hitters file later on uses nineteen predictors, so its regions are nineteen-dimensional boxes — the same objects as the coloured rectangles above, and just as flat, with no way to put them on a page.

A regression tree cannot extrapolate

Now the property that has no classification analogue, and the most important practical fact in this article.

Look again at the widget and at the shaded band on the right, past the last training point. The staircase does not continue. It goes flat and stays flat, forever, at whatever value the right-most leaf holds.

That is not an artefact of the drawing. It follows directly from how prediction works: a row arriving with $x = 10^6$ answers “yes” to every threshold question on the way down, lands in the right-most leaf, and receives the mean of the training rows that landed there. There is no mechanism by which a leaf value can depend on how far past the threshold the row is.

Here is the sharpest possible demonstration — a perfectly linear relationship with no noise at all, $y = 2.5x + 3$, sampled on $x \in [0, 10]$, fitted by a depth-3 tree and by ordinary linear regression:

X = np.linspace(0, 10, 60).reshape(-1, 1)
y = 2.5 * X.ravel() + 3

tree = DecisionTreeRegressor(max_depth=3).fit(X, y)
linear = LinearRegression().fit(X, y)

The linear model recovers the rule exactly and is correct at $x = 1000$. The tree returns 26.52 at $x = 12$, at $x = 50$, and at $x = 1000$ — one number, for every input beyond its experience, on data with no noise and a relationship a straight line captures with two parameters.

Even inside the training range the tree is never exactly right: it says 7.45 where the truth is 8.00, because it is quantising a continuous line into eight plateaus.

Worse than the flatness is the bound. A leaf holds the mean of the training targets that reached it, and a mean cannot lie outside the values it averages. So every prediction a regression tree can ever make is confined to the range of the training targets. It cannot forecast a record high or a record low, at any depth, on any data.

On the straight line above, the largest value the tree can emit is 26.5169 against a training maximum of 28.0 — it cannot even reach the biggest number it has seen. That last part is not universal, though, and Hitters shows why. Fit a tree to the salaries and its ceiling is 2127.3, which is the training maximum exactly, at every depth down to 2:

depth 2      highest possible prediction  2127.3   reached by 1 player
depth 3      highest possible prediction  2127.3   reached by 1 player
depth 5      highest possible prediction  2127.3   reached by 1 player
depth full   highest possible prediction  2127.3   reached by 1 player

The top earner is such an outlier that the greedy search spends a whole split isolating him into a leaf of his own — even in a four-leaf tree — because removing that much squared error is the best trade available. Where the targets are smooth, the ceiling sits strictly below the maximum; where there is a lone extreme, the tree carves it out and reaches it.

Either way the direction is the same, and it is the part that matters: never above. Ask that same depth-3 tree to price a player with twice the best career totals anyone in the dataset has ever posted:

depth-3 tree       predicts   1169.8
linear regression  predicts   5836.3

The tree answers with a number it has already seen — a perfectly ordinary salary, well inside the observed range — for a player twice as good as the best in history.

The practical consequences are worth naming, because this is where people get hurt:

• Trends and time series. Point a tree at anything with a time index and it will predict the last plateau forever. If a trend is what you care about, detrend first, model the residual with the tree, and add the trend back — or use a model that can express a slope.
• Prices, growth, any quantity that ratchets. A model trained through 2024 cannot forecast a 2026 record no matter how much data you give it.
• The ceiling is inherited. A random forest averages trees and a boosted ensemble sums them, and neither operation invents a slope. XGBoost cannot extrapolate either. This is the one weakness of the tree family that ensembling does not touch.

Mean or median? Choosing the criterion

The article has assumed squared error throughout. It is the default, not the only option, and the choice propagates in a tidy way: the criterion decides the leaf statistic, because both are answers to “what single constant minimises this loss?”

• Minimise squared error → the leaf holds the mean.
• Minimise absolute error → the leaf holds the median.

Take a leaf holding [10, 12, 14, 16, 200], where the 200 is an outlier or a data-entry mistake:

Each constant wins under its own loss, exactly as it should. But look at what the mean is: 50.40, a number larger than four of the five values in the leaf. One outlier has dragged the prediction away from every point it is supposed to serve. The median ignores it completely.

So absolute error is the robust choice — but robustness is not free, and on real data it does not automatically win. On Hitters at depth 3:

The squared-error tree is better here on both metrics, including the one the other criterion was optimising for. That is not a paradox — absolute_error minimises absolute error on the training rows, which is no guarantee about held-out ones, and it gives up statistical efficiency to buy a robustness this data did not need badly enough. Reach for it when you have genuine outliers or heavy tails, not as a default. It is also considerably slower, because a median cannot be updated incrementally the way a running mean can.

One footnote for anyone reading older sklearn docs or tutorials: friedman_mse used to appear as a third option. It is now deprecated and maps to squared_error — scikit-learn’s own warning says the two “were always equivalent” — and it is scheduled for removal in 1.11.

On real data

Everything above is five rows. Now the whole file: all 263 players with a recorded salary, all nineteen predictors rather than the two we have been reading, split 184 for training and 79 for testing.

$R^2$ is the natural score here, and it comes with a built-in reference point: 1.000 is perfect, and 0.000 is what you get by ignoring every feature and predicting the training mean for everybody.

X, y = load_hitters()          # 263 players, 19 predictors
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)

for depth in (1, 2, 3, 5, 8, None):
    m = DecisionTreeRegressor(max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(depth, m.get_n_leaves(), m.score(X_tr, y_tr), m.score(X_te, y_te))

The shape is the classification article’s, in salary units. Train $R^2$ climbs monotonically to a perfect 1.000 — 165 leaves for 184 players, so most of them end up with a leaf of their own and get their exact 1987 salary read back. Test $R^2$ peaks at depth 3, with seven leaves, and then falls away: by the time the tree is fully grown it has lost 41% of its explanatory power on held-out players, and its typical error has grown from $368k to$434k.

The depth-3 tree gets 30% of its training variance wrong and is the best model on the table. The one that gets none of it wrong is the second worst.

Worth being straight about one thing: the fully grown tree here is still well above the 0.000 baseline, so “worse than useless” would overstate it — on this data, unconstrained growth costs you a third of your performance rather than all of it. How far the collapse goes is a property of the dataset, not a law.

The remedies are the ones the classification article listed, and they are all structural: cap the depth, require a minimum number of rows per leaf, demand a minimum gain, or grow fully and prune back with cost-complexity pruning (ccp_alpha).

Pruning: grow too far, then cut back

In the previous article we mentioned that the one technique against overfitting that applies to a single tree is pruning, and sorted it into two families: pre-pruning, which refuses to grow in the first place, and post-pruning, which grows the tree out and then cuts it back. Cost-complexity pruning was named as the canonical version and described by its shape — the tree’s error, plus a price per leaf — without the formula being written down.

Let’s now write it down, because with RSS already in hand it costs a single term.

Start with the tempting shortcut, which is to refuse any split whose RSS reduction falls below some threshold. It does not work well, and the reason is the greediness we have already met: a mediocre split can be the doorway to an excellent one below it, and a tree stopped at the door never finds out.

So cost-complexity pruning does the opposite. Grow the tree all the way out, then charge rent per leaf and cut back whatever cannot pay. For a tuning parameter $\alpha \ge 0$, score every subtree $T$ by

where $|T|$ is the number of leaves. This is An Introduction to Statistical Learning’s equation 8.4, and every term in it is already familiar: the first is the criterion from earlier summed over all the leaves rather than two, and the second is a flat price per leaf. At $\alpha = 0$ nothing is charged and the full tree wins. Raise $\alpha$ and leaves have to justify themselves, so the winning subtree shrinks. It is the same shape as any other regularised objective — fit plus a penalty on complexity — and it is what ccp_alpha sets in scikit-learn.

The reason this is practical rather than merely definable is that the subtrees come in a nested sequence. As $\alpha$ rises, branches fall away in a fixed, predictable order, so you never enumerate the astronomically many possible subtrees — you walk a list. On our training rows that list has 158 entries, from the full 165-leaf tree down to a stump:

You pick $\alpha$ the way you pick any hyperparameter that cannot be read off the training data: cross-validate. Five-fold CV on the training rows selects the last row — $\alpha \approx 19{,}530$, three leaves — which lifts test $R^2$ from 0.287 to 0.445. Most of the damage the unpruned tree did is undone by a tree with three leaves.

And it still loses to the depth cap, which scored 0.487 with seven leaves. That is worth stating plainly rather than hiding, because the tidy version of this story — principled method beats crude knob — is not what the data says. With 184 training rows the cross-validated estimate is noisy (the CV column tops out at 0.325 against a test score of 0.445, and is near zero for most of the path), and the selection lands on the most aggressive subtree available. Cost-complexity pruning earns its reputation on datasets where there is enough data to estimate $\alpha$ reliably; on a couple of hundred rows a depth cap chosen by the same cross-validation is a perfectly respectable competitor.

What survives regardless is the shape of the fix. Left alone the tree drives its own training error to zero, so the stopping rule has to come from outside it — either as a structural cap, or as a price per leaf paid against held-out performance. There is nothing inside build_tree that could ever have known when to stop.

Where this goes

A regression tree is the previous article’s classifier with two functions swapped, and those two functions buy a model that answers a genuinely different question — with a prediction surface made of flat plateaus that cannot slope, cannot exceed the targets it was trained on, and cannot say anything about inputs beyond its experience.

Almost every practical use of a regression tree is as a component rather than a model. Average hundreds of them, each grown on a different sample, and you get a random forest. Fit them in sequence to each other’s errors, and you get gradient boosting — where these trees do the work even when the problem is classification, because what they are fitted to is a column of real-valued gradients rather than labels. The tree in this article is the unit that ensemble is built from.

The code is in hitters_tree.py and regression_properties.py alongside this article, with the dataset vendored as hitters.csv so every number above is reproducible offline. regression_properties.py checks the five players against the full file before it does anything else.