Decision Tree Regression

You have a house. You know its square footage. How much is it worth? You could draw a straight line through the data — that's linear regression, and it works well when the relationship is smooth. But what if the housing market has sharp breakpoints? Houses under 1000 sq ft all sell in a narrow range, then jump at 1200 sq ft because of a zoning change.

A regression tree handles this naturally — it splits the data into regions and predicts the average price within each region, creating a staircase instead of a line.

Anchor dataset: 6 houses with sq_ft and price — the same anchor from the linear regression section.

import numpy as np

X = np.array([650, 850, 1100, 1400, 1600, 1900]).reshape(-1, 1)
y = np.array([180, 220, 280, 340, 370, 430])
# True OLS: ŷ = 53.33 + 0.20×sq_ft (from linear regression section)

What It Is

A regression tree is the same algorithm as a classification tree, but it predicts numbers instead of categories. Instead of measuring impurity with entropy or Gini, it measures how spread out the target values are using variance. At each leaf, instead of a majority vote, it predicts the average of the samples that reached it. This is not the same as linear regression — the tree doesn't assume the relationship is a straight line. It produces a piecewise constant prediction that can handle sharp jumps and nonlinear patterns.

The algorithm skeleton — threshold search, stopping conditions, pruning — is identical to classification trees.

The Plan — Three Levels to a Regression Tree

We'll walk through how a regression tree builds its staircase. First we compute variance at the root, then find the best split for sq_ft, then build two more levels, and finally compare against linear regression.

Level 1: Compute Root Variance

Here's the goal: measure how spread out house prices are at the root node. The variance is the squared error of predicting the mean for every sample:

$\text{Var}(S)=\frac{1}{n}{\sum }_i(y_i-\bar{y}{)}^2$

At the root: $\bar{y}=(180+220+280+340+370+430)/6=1820/6=303.33$

$\text{Var}(\text{root})=\frac{(180-303.33{)}^2+(220-303.33{)}^2+(280-303.33{)}^2+(340-303.33{)}^2+(370-303.33{)}^2+(430-303.33{)}^2}{6}$

$=\frac{15210.9+6943.9+544.3+1344.3+4444.9+16045.3}{6}=\frac{44533.6}{6}=7422.3$

The root variance is 7422.3. If we predict $303.3k for every house, our average squared error is this number.

✓ Level 1 complete. Root variance = 7422.3.

Threshold Search for sq_ft

Split criterion for regression:

${\text{IG}}_{\text{reg}}(S,t)=\text{Var}(S)-\frac{|S_l|}{|S|}\text{Var}(S_l)-\frac{|S_r|}{|S|}\text{Var}(S_r)$

5 midpoint candidates: 750, 975, 1250, 1500, 1750.

Best split: $t=1250$ with ${\text{IG}}_{\text{reg}}=6078$. The split at sq_ft = 1250 reduces the total variance from 7422 to 1344 — an 82% reduction.

✓ Level 2 complete. Best threshold found: sq_ft ≤ 1250 with IG_reg = 6078.

Level 3: Split Left Child (sq_ft ≤ 1250, samples [650, 850, 1100])

Goal: the left child is still impure (Var=1555). Can we split further?

$y=[180,220,280]$, $\bar{y}=226.7$, $\text{Var}=1555$.

Test thresholds $t=750$ and $t=975$:

• $t=750$: Left=[180], Var=0; Right=[220,280], $\bar{y}=250$, Var=900. Weighted: $(1/3)(0)+(2/3)(900)=600$. ${\text{IG}}_{\text{reg}}=1555-600=955$.
• $t=975$: Left=[180,220], $\bar{y}=200$, Var=400; Right=[280], Var=0. Weighted: $(2/3)(400)+(1/3)(0)=267$. ${\text{IG}}_{\text{reg}}=1555-267=1288$.

Best: $t=975$. Splits into:

• Left-Left (sq_ft ≤ 975): [650, 850] → $\bar{y}=200$ — predict $200k
• Left-Right (975 < sq_ft ≤ 1250): [1100] → $\bar{y}=280$ — predict $280k

✓ Left child complete. Split at t=975 with IG_reg=1288.

Level 2: Right Child (sq_ft > 1250, samples [1400, 1600, 1900])

$y=[340,370,430]$, $\bar{y}=380$, $\text{Var}=1133$.

Test thresholds $t=1500$ and $t=1750$:

• $t=1500$: Left=[340], Var=0; Right=[370,430], $\bar{y}=400$, Var=900. Weighted: $(1/3)(0)+(2/3)(900)=600$. ${\text{IG}}_{\text{reg}}=1133-600=533$.
• $t=1750$: Left=[340,370], $\bar{y}=355$, Var=225; Right=[430], Var=0. Weighted: $(2/3)(225)+(1/3)(0)=150$. ${\text{IG}}_{\text{reg}}=1133-150=983$.

Best: $t=1750$. Splits into:

• Right-Left (1250 < sq_ft ≤ 1750): [1400, 1600] → $\bar{y}=355$ — predict $355k
• Right-Right (sq_ft > 1750): [1900] → $\bar{y}=430$ — predict $430k

✓ Right child complete. Split at t=1750 with IG_reg=983.

The 4-Leaf Staircase

The orange staircase shows tree predictions: constant within each leaf region. The blue dashed line is the linear regression fit. For this near-linear dataset, the linear model tracks the data better; the tree's staircase has visible errors at the leaf boundaries.

Predictions vs Actual — Tree vs Linear

$\text{Tree MSE}=(400+400+0+225+225+0)/6=208.3$ $\text{Linear MSE}=(9+9+49+49+9+9)/6=22.3$

Linear regression wins decisively on this near-linear dataset. The tree is limited by its piecewise-constant prediction: leaves 1 and 4 each contain 2 samples whose true values differ, forcing the average to miss both.

Trace Table: Regression Tree Construction

✓ Tree complete. 4-leaf staircase with Tree MSE = 208.3 vs Linear MSE = 22.3.

sklearn Implementation

Let's verify with sklearn. We use DecisionTreeRegressor instead of DecisionTreeClassifier. We set criterion='squared_error' to use MSE as the split measure (this is the default, but we specify it explicitly). max_depth=2 matches our manual construction. random_state=42 ensures reproducible results.

from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_squared_error

dt_reg = DecisionTreeRegressor(criterion='squared_error', max_depth=2, random_state=42)
dt_reg.fit(X, y)

y_pred = dt_reg.predict(X)
print(f"Tree MSE: {mean_squared_error(y, y_pred):.2f}")
print(f"Tree R²:  {dt_reg.score(X, y):.4f}")
print(f"Predictions:     {y_pred}")
print(f"Unique leaf predictions: {np.unique(y_pred)}")

Tree MSE: 208.33
Tree R²:  0.9720
Predictions: [200. 200. 280. 355. 355. 430.]
Unique leaf predictions: [200. 280. 355. 430.]

The 4 unique prediction values are the mean of each leaf: [200, 280, 355, 430]. Despite high R²=0.972, the MSE of 208 is 9× worse than the linear model's MSE of 22.

max_depth Effect on Regression

print(f"{'depth':>8} {'MSE':>10} {'steps':>8} {'leaves':>8}")
for d in [1, 2, 3, None]:
    dt = DecisionTreeRegressor(max_depth=d, random_state=42)
    dt.fit(X, y)
    y_p = dt.predict(X)
    mse = mean_squared_error(y, y_p)
    steps = len(np.unique(y_p))
    print(f"{str(d):>8} {mse:>10.2f} {steps:>8} {dt.get_n_leaves():>8}")

depth        MSE    steps   leaves
       1    3041.67        2        2
       2     208.33        4        4
       3      22.22        6        6   ← one leaf per sample
    None       0.00        6        6   ← memorizes training set

At depth=3 with 6 samples and 6 leaves: each sample has its own leaf, MSE=22.22 (interpolation errors from single-sample leaves). At depth=None: MSE=0 (perfect memorization). Neither of these generalizes.

When Does a Regression Tree Beat Linear Regression?

The staircase is piecewise constant — it assumes the target is flat within each region. Linear regression assumes a global linear trend. Trees win when:

• The true relationship has sharp breakpoints (e.g., a salary cap at a specific experience level)
• The relationship is nonlinear with different slopes in different regions
• There are strong feature interactions (the effect of feature A depends on feature B)

Linear regression wins when the true relationship is approximately linear (as here).

Related Concepts

Regression trees extend the classification tree (posts 01–04) by replacing entropy with variance reduction — the algorithmic skeleton is identical. This is the direct foundation for gradient boosting: each boosting round fits a regression tree on the residuals from the previous round, and the leaf prediction at each step is the mean of those residuals. Understanding how a regression tree predicts the mean within a leaf region directly explains why the first gradient boosting iteration predicts the global mean of $y$.

Honest Limitations

Here's the thing about regression trees that I've learned the hard way: they predict a constant within each leaf. That means approximating even a simple linear trend requires many splits — each staircase step is a leaf. On this 6-sample dataset, with max_depth=2, the tree already makes visible errors at leaf boundaries, while a two-parameter linear model fits perfectly. For smooth relationships, a regression tree needs $O(n)$ leaves to match linear regression accuracy — and at that point you're basically memorizing.

I've also been caught by the extrapolation problem. At max_depth=None, the tree achieves MSE=0 by assigning every sample its own leaf. But for a query point outside the training range, it just predicts the value of the nearest training point — there's no extrapolation. Linear regression at least extends the fitted line. Neither is correct by default; I now choose based on whether I expect the relationship to continue beyond the training range.

Test Your Understanding

1. At the root, the best threshold was $t=1250$ with ${\text{IG}}_{\text{reg}}=6078$. The threshold $t=750$ produced ${\text{IG}}_{\text{reg}}=2902$. The left node of $t=750$ is pure (1 sample, Var=0), yet its IG is lower. Why does a single-sample pure left node not maximize variance reduction?

2. Leaf 1 (sq_ft ≤ 975) predicts $200kforbothhousesat650s{q}_{f}t(true$180k) and 850 sq_ft (true $220k).Thepredictionerroris$\pm$20k for both. What would the prediction be if you used the median instead of the mean? Would this reduce or increase MSE on this leaf?

3. At depth=3, MSE=22.22 with 6 leaves for 6 samples. Is this the irreducible error of the model, or could a depth=4 tree (if allowed) reduce it further? What would the depth=4 tree's MSE be?

4. The tree with max_depth=None achieves MSE=0 on training data. If you added a 7th house with sq_ft=1100 and price=$290k(differentfromtrainingsample{3}^{\prime }s$280k), what would the depth=None tree predict for sq_ft=1100? How does the presence of two training samples at the same sq_ft affect the tree?

5. DecisionTreeRegressor uses MSE by default (criterion='squared_error'). An alternative is MAE (criterion='absolute_error'). The MAE-optimal leaf prediction is the median instead of the mean. For leaf 1 with $y=[180,220]$: the mean is 200 and the median is also 200 (average of two). For a leaf with $y=[180,220,1000]$ (one outlier): what is the mean vs median, and which leaf prediction minimizes MAE?