Decision tree regression

Split to maximize variance reduction; each leaf predicts the mean of its training targets, giving a step function.

17 min read1303 wordscore33 viewsupdated 2026-10-07

Definition

A regression tree predicts a number by asking yes/no questions of the form is xj≤tx_j \le t? until it reaches a leaf, and then outputs the mean target of the training points that ended up in that leaf. Splits are chosen greedily to make the squared error inside the children as small as possible, so the fitted function is a piecewise-constant step function.

At a glance

Task
Regression (numeric target)
Input → output
feature vector xx → the mean yˉ\bar y stored in the leaf xx lands in
Learns
a feature + threshold per internal node, one constant per leaf
Split criterion
squared error: minimize SSEL+SSER\text{SSE}_L+\text{SSE}_R (equivalently, maximize variance reduction)
Training cost
O(d nlog⁡n)O(d\,n\log n) to sort each feature, then O(d n)O(d\,n) per tree level with running sums
Prediction cost
O(depth)O(\text{depth}) comparisons — independent of nn
Key hyperparameters
max_depth, min_samples_leaf, min_samples_split, max_leaf_nodes, ccp_alpha, criterion
Assumptions
none about distributions or linearity; implicitly that the target is roughly constant inside axis-aligned boxes

The problem

Linear regression assumes the target moves at a constant rate with each feature. Many real targets don't. Bike rentals rise as it warms up, peak on pleasant days and fall again when it gets hot. A straight line through such data is wrong almost everywhere: on the 12-day dataset used below, the least-squares line y^=13.56+0.50 T\hat y = 13.56 + 0.50\,T explains only R2=0.32R^2 = 0.32 of the variance (MSE 56.20).

You can repair a linear model with polynomial terms, splines or hand-made interactions, but you have to guess the right shape in advance. A regression tree takes the opposite approach: it makes no assumption about shape at all and simply chops the input space into regions where the target is roughly constant. With just four regions it reaches R2=0.89R^2 = 0.89 (MSE 9.00) on the same data.

The idea

If you had to summarize a group of numbers by a single value and were scored on squared error, you would pick their mean. A regression tree applies that idea locally. Start with one group (all the data, predict the overall mean). Then look for the one question is xj≤tx_j\le t? that splits the group into two halves whose own means fit them best — the halves should be internally similar and different from each other. Repeat inside each half. Stop when the groups are small or the tree is deep enough.

Each leaf is a box in feature space with a flat prediction, so in one dimension the model is a staircase and in two dimensions a set of flat rectangular plateaus. More depth means more, narrower steps — and eventually one step per training point.

Vocabulary

Node / region
a set of training points defined by the answers on the path from the root; geometrically an axis-aligned box RmR_m
Split
a pair (feature jj, threshold tt) sending points with xj≤tx_j\le t left and the rest right
Candidate threshold
a midpoint between two consecutive distinct sorted values of a feature — the only places a split can change
Leaf value
the constant cmc_m a leaf predicts; under squared error, the mean of the leaf's training targets
SSE
sum of squared errors ∑(yi−yˉ)2\sum (y_i-\bar y)^2 of a node around its own mean — the regression tree's impurity
Variance reduction
parent SSE minus the children's SSE (often divided by n); the score a split is ranked by
Step function
the piecewise-constant function the tree computes: constant inside each leaf, jumping at thresholds

The math

A tree with leaves R1,…,RMR_1,\dots,R_M computes

f^(x)=∑m=1Mcm 1[x∈Rm]\hat f(x)=\sum_{m=1}^{M} c_m\,\mathbf 1[x\in R_m]
RmR_m
the m-th leaf region (an axis-aligned box)
cmc_m
the constant predicted in that leaf
1[⋅]\mathbf 1[\cdot]
indicator: 1 if x falls in the region, else 0
MM
number of leaves

Training minimizes the squared error over both the regions and the constants:

min⁡{Rm,cm} ∑m=1M ∑i: xi∈Rm(yi−cm)2\min_{\{R_m,c_m\}}\ \sum_{m=1}^{M}\ \sum_{i:\,x_i\in R_m}\big(y_i-c_m\big)^2
yiy_i
target of training point i
xix_i
its feature vector

Leaf values are means. Fix the regions. Each leaf's term depends only on its own cmc_m, so set its derivative to zero: ∂∂cm∑i∈Rm(yi−cm)2=−2∑i∈Rm(yi−cm)=0\frac{\partial}{\partial c_m}\sum_{i\in R_m}(y_i-c_m)^2=-2\sum_{i\in R_m}(y_i-c_m)=0, which gives cm=1nm∑i∈Rmyi=yˉmc_m=\frac{1}{n_m}\sum_{i\in R_m}y_i=\bar y_m. What is left in each leaf is its sum of squared errors around its mean:

SSE(S)=∑i∈S(yi−yˉS)2=∑i∈Syi2−(∑i∈Syi)2nS=nSVar⁡(S)\text{SSE}(S)=\sum_{i\in S}(y_i-\bar y_S)^2=\sum_{i\in S}y_i^2-\frac{\big(\sum_{i\in S}y_i\big)^2}{n_S}=n_S\operatorname{Var}(S)
SS
the set of training points in a node
nS, yˉSn_S,\ \bar y_S
its size and mean target
Var⁡(S)\operatorname{Var}(S)
variance of the targets in S (dividing by n)

Choosing a split. Searching over all partitions is intractable, so CART grows the tree greedily: at a node SS it tries every feature jj and threshold tt, splits SS into L={xj≤t}L=\{x_j\le t\} and R={xj>t}R=\{x_j>t\}, and keeps the pair with the smallest SSE(L)+SSE(R)\text{SSE}(L)+\text{SSE}(R). Equivalently it maximizes the drop

Δ(j,t)=SSE(S)−SSE(L)−SSE(R)=nL nRnS (yˉL−yˉR)2\Delta(j,t)=\text{SSE}(S)-\text{SSE}(L)-\text{SSE}(R)=\frac{n_L\,n_R}{n_S}\,\big(\bar y_L-\bar y_R\big)^2
L, RL,\ R
points with xj≤tx_j\le t and xj>tx_j>t
nL, nRn_L,\ n_R
how many points go each way
yˉL, yˉR\bar y_L,\ \bar y_R
the two children's means (their future leaf values)

The right-hand form follows from expanding the SSE identity above (it is the between-group sum of squares from ANOVA) and says exactly what the tree looks for: two big groups with very different means. Dividing by nSn_S gives the variance reduction Var⁡(S)−nLnSVar⁡(L)−nRnSVar⁡(R)\operatorname{Var}(S)-\tfrac{n_L}{n_S}\operatorname{Var}(L)-\tfrac{n_R}{n_S}\operatorname{Var}(R), the regression analogue of information gain. Because the parent term is fixed, minimizing children's SSE is also the same as maximizing (∑Ly)2nL+(∑Ry)2nR\tfrac{(\sum_L y)^2}{n_L}+\tfrac{(\sum_R y)^2}{n_R}, which needs only running sums — this is what makes an O(n)O(n) scan per sorted feature possible.

How each hyperparameter acts on this objective. Every split can only lower training SSE, so without limits the greedy search continues until each leaf has one distinct target and training error is 0. The hyperparameters cap that:

Hyperparameters, mathematically

max_depth = D
at most 2D2^D leaves; the step function has at most 2D−12^D-1 jumps per path. Lower DD → higher bias, lower variance.
min_samples_leaf = k
only thresholds with nL≥kn_L\ge k and nR≥kn_R\ge k are candidates. Each leaf mean then averages at least kk targets, so its noise variance is at most σ2/k\sigma^2/k.
min_samples_split
a node with fewer points is not split at all (a weaker, parent-side version of the leaf limit)
min_impurity_decrease = δ
split only if Δ/N≥δ\Delta/N\ge\delta (NN = training-set size): a minimum variance reduction per split
max_leaf_nodes
grow best-first (largest Δ\Delta anywhere in the tree) and stop at that many leaves
ccp_alpha = α
after growing, prune to minimize MSE(T)+α ∣T∣\text{MSE}(T)+\alpha\,|T| — every leaf must buy at least α\alpha of training MSE
Rα(T)=1N∑m=1∣T∣SSE(Rm)+α ∣T∣,αeff(t)=R(t)−R(Tt)∣Tt∣−1R_\alpha(T)=\frac{1}{N}\sum_{m=1}^{|T|}\text{SSE}(R_m)+\alpha\,|T|,\qquad \alpha_{\text{eff}}(t)=\frac{R(t)-R(T_t)}{|T_t|-1}
∣T∣|T|
number of leaves of tree T
R(t)R(t)
training MSE contribution of node t if it were collapsed into a leaf
R(Tt)R(T_t)
contribution of the subtree rooted at t, as grown
αeff(t)\alpha_{\text{eff}}(t)
error added per leaf removed when t is collapsed; the smallest one is pruned first (weakest link)

Worked example: bike rentals vs temperature

Twelve days, one feature (noon temperature TT in °C) and the target (bike rentals, in hundreds). Rentals climb until the mid-20s and drop on hot days. Overall: ∑y=274\sum y=274, ∑y2=7254\sum y^2=7254, so the root mean is 274/12=22.83274/12=22.83 and the root SSE is 7254−2742/12=997.677254-274^2/12=997.67 (variance 83.14).

DayT (°C)Rentals y
128
2510
3813
41119
51424
61730
72033
82335
92634
102929
113222
123517
Training data. Highlighted: the 4 cold days that the first split will separate.

Growing a depth-2 tree by hand

  1. 1Candidates. The 12 sorted temperatures give 11 midpoints: 3.5, 6.5, …, 33.5.
  2. 2Score one. For T≤12.5T\le 12.5: left {8,10,13,19}\{8,10,13,19\} has mean 12.512.5 and SSE 4.52+2.52+0.52+6.52=694.5^2+2.5^2+0.5^2+6.5^2=69; right {24,30,33,35,34,29,22,17}\{24,30,33,35,34,29,22,17\} has mean 2828 and SSE 288288. Children SSE =357=357, so Δ=997.67−357=640.67\Delta=997.67-357=640.67. Check with the shortcut: 4⋅812(12.5−28)2=640.67\tfrac{4\cdot 8}{12}(12.5-28)^2=640.67.
  3. 3Score all 11 (table below). T≤12.5T\le 12.5 has the smallest children SSE, so it becomes the root. Training MSE drops from 83.1483.14 to 357/12=29.75357/12=29.75.
  4. 4Recurse left (4 cold days, SSE 69). Candidates 3.5, 6.5, 9.5 leave SSE 42.00, 20.00, 12.67. Best: T≤9.5T\le 9.5 → leaves {8,10,13}\{8,10,13\} (mean 10.33) and {19}\{19\} (mean 19).
  5. 5Recurse right (8 warm days, SSE 288). The 7 candidates leave SSE 269.71, 285.33, 283.20, 238.00, 151.47, 95.33, 149.71. Best: T≤30.5T\le 30.5 → leaves {24,30,33,35,34,29}\{24,30,33,35,34,29\} (mean 185/6=30.83185/6=30.83, SSE 82.83) and {22,17}\{22,17\} (mean 19.5, SSE 12.5).
  6. 6Stop at max_depth 2. Total leaf SSE =12.67+0+82.83+12.5=108=12.67+0+82.83+12.5=108, so training MSE =108/12=9.00=108/12=9.00 and R2=1−9/83.14=0.89R^2=1-9/83.14=0.89.
  7. 7Predict a 27 °C day: 27>12.527>12.5 → right; 27≤30.527\le 30.5 → left. Prediction 30.83 hundred rentals (the straight line would say 27.09).
Splitn leftLeft mean (SSE)Right mean (SSE)Children SSEDrop Δ
T ≤ 3.518.00 (0.00)24.18 (757.64)757.64240.03
T ≤ 6.529.00 (2.00)25.60 (536.40)538.40459.27
T ≤ 9.5310.33 (12.67)27.00 (360.00)372.67625.00
T ≤ 12.5412.50 (69.00)28.00 (288.00)357.00640.67
T ≤ 15.5514.80 (174.80)28.57 (269.71)444.51553.15
T ≤ 18.5617.33 (367.33)28.33 (267.33)634.67363.00
T ≤ 21.5719.57 (577.71)27.40 (241.20)818.91178.75
T ≤ 24.5821.50 (786.00)25.50 (169.00)955.0042.67
T ≤ 27.5922.89 (924.89)22.67 (72.67)997.560.11
T ≤ 30.51023.50 (958.50)19.50 (12.50)971.0026.67
T ≤ 33.51123.36 (960.55)17.00 (0.00)960.5537.12
Every root candidate. Children SSE = SSE(left) + SSE(right); the drop is 997.67 minus it. The peak split at 27.5 is almost worthless.
Leaf (rule)DaysPrediction (mean)Leaf SSE
T ≤ 9.52, 5, 8 °C10.3312.67
9.5 < T ≤ 12.511 °C19.000.00
12.5 < T ≤ 30.514 … 29 °C30.8382.83
T > 30.532, 35 °C19.5012.50
The fitted depth-2 tree as rules. Each row is one leaf, one step of the step function.
▸ regression tree · squared errorstep 1/20
22.8rentals (hundreds) vs temperature (°C) · — leaf means · | residuals0102030400°10°20°30°SSE drop per candidate — shown while a node is being split
leaves 1train MSE 83.14
  1. 1grow(node, depth):
  2. 2 if depth=max or n<2: leaf ← mean(y)
  3. 3 for each midpoint t between sorted x:
  4. 4 SSE(t) ← SSE(left) + SSE(right)
  5. 5 t* ← argmin SSE(t)
  6. 6 split at t*; grow(left); grow(right)
  7. 7predict(x): walk down; return leaf mean

Start with one leaf: every day predicts the mean, 22.83. The red residuals add up to SSE = 997.67.

fig.The tree growing on the 12 days. Top: the tree, each node drawn above the region of temperature it owns. Middle: data, the current step function (green) and residuals (red). Bottom: the SSE drop of each candidate threshold of the node being split. The root scan visits all 11 midpoints and keeps T ≤ 12.5 (drop 640.67); the cold node then splits at 9.5 (56.33) and the warm node at 30.5 (192.67). At depth 2 the train MSE is 9.00 and a 27 °C day gets 30.83; depth 3 gives 7 leaves (MSE 2.40); no limit gives 12 one-day leaves, depth 7, MSE 0.

The algorithm, step by step

Grow(node)

  1. 1Leaf value. Store the mean of the node's targets (it is the prediction if the node stays a leaf).
  2. 2Stop? Make it a leaf if depth = max_depth, the node has fewer than min_samples_split points, or all its targets are equal (SSE = 0).
  3. 3Sort and scan. For each feature, sort the node's points by that feature and sweep left to right, keeping running nL, ∑Ly, ∑Ly2n_L,\ \sum_L y,\ \sum_L y^2 (the right side is total minus left). At each midpoint between distinct values with at least min_samples_leaf points on each side, compute SSEL+SSER\text{SSE}_L+\text{SSE}_R in O(1)O(1).
  4. 4Choose the (feature, threshold) with the smallest children SSE. If its drop is below min_impurity_decrease, make a leaf instead.
  5. 5Recurse on the left and right subsets.
  6. 6(Optional) prune the grown tree with cost-complexity pruning, choosing ccp_alpha by cross-validation.
  7. 7Predict by walking from the root, comparing one feature per node, and returning the leaf mean.

Complexity

Training
each level touches every point once per feature: O(d n)O(d\,n) per level after an O(d nlog⁡n)O(d\,n\log n) sort (or O(d nlog⁡n)O(d\,n\log n) per level if re-sorting). A balanced tree has O(log⁡n)O(\log n) levels, a degenerate one up to O(n)O(n).
Prediction
O(depth)O(\text{depth}) per query, at most O(log⁡2M)O(\log_2 M) for a balanced tree with MM leaves
Memory
one threshold, feature index and value per node — at most 2n − 1 nodes
Histogram variant
bin each feature into B≈256B\approx256 buckets once; split search becomes O(d B)O(d\,B) per node — the trick LightGBM and XGBoost's hist mode use

Variants and tuning

criterionImpurity of a nodeLeaf valueWhen to use
squared_error (default)SSE / variancemeanthe standard choice; fast O(n) scan
friedman_msenLnRnL+nR(yˉL−yˉR)2\tfrac{n_Ln_R}{n_L+n_R}(\bar y_L-\bar y_R)^2 improvement scoremeanthe default split score inside scikit-learn's gradient boosting; rarely worth choosing for a single tree
absolute_error∑∣yi−median⁡∣\sum\lvert y_i-\operatorname{median}\rvertmedianheavy-tailed targets or outliers; much slower to fit
poissonPoisson deviancemean (must be > 0)counts and rates, e.g. claims, visits
Split criteria available in scikit-learn's DecisionTreeRegressor.

On the bike data, criterion="absolute_error" with depth 2 picks the same four regions but predicts medians: 10.00, 19.00, 31.50 and 19.50 instead of 10.33, 19.00, 30.83 and 19.50.

SettingLeavesTrain MSECV MSE
max_depth = 120.3970.402
max_depth = 380.1380.158
max_depth = 5290.0670.111
max_depth = 81380.0270.134
no limit3000.0000.147
min_samples_leaf = 10230.0720.109
min_samples_leaf = 5050.2010.234
Tuning on a larger, noisy problem: 300 points, y=sin⁡x+εy=\sin x+\varepsilon, ε∼N(0,0.32)\varepsilon\sim\mathcal N(0,0.3^2), so the best achievable MSE is 0.09. 5-fold cross-validated MSE; best rows highlighted.

Practical tuning

Start with
min_samples_leaf (try 5–50 or 1–5% of n) and max_depth (3–10); they matter far more than the criterion
Pruning
compute cost_complexity_pruning_path on the training set and cross-validate over its alphas
On the bike data
the pruning path has α\alpha = 4.69 (collapsing the cold node: (69−12.67)/12(69-12.67)/12), 16.06 (the warm node: (288−95.33)/12(288-95.33)/12) and 53.39 (the root). So ccp_alpha=5 keeps 3 leaves (train MSE 13.69) and ccp_alpha=20 keeps only the root split (29.75)
Watch
the gap between train and validation MSE; a deep tree's training MSE is near 0 and tells you nothing
Need more accuracy?
average many trees (see Random forest regression) or fit trees to residuals (see Gradient boosting regression and AdaBoost regression)

In code

python
1import numpy as np
2
3def best_split(x, y, min_leaf=1):
4 """Best threshold on one feature, scanning sorted x with prefix sums: O(n)."""
5 order = np.argsort(x)
6 xs, ys = x[order], y[order]
7 n = len(ys)
8 csum, csq = np.cumsum(ys), np.cumsum(ys ** 2)
9 best = (np.inf, None) # (SSE_L + SSE_R, threshold)
10 for i in range(min_leaf - 1, n - min_leaf): # left = first i+1 points
11 if xs[i] == xs[i + 1]:
12 continue # cannot split between equal x
13 nL, nR = i + 1, n - i - 1
14 sL, sR = csum[i], csum[-1] - csum[i]
15 qL, qR = csq[i], csq[-1] - csq[i]
16 sse = (qL - sL ** 2 / nL) + (qR - sR ** 2 / nR) # SSE = sum y^2 - (sum y)^2 / n
17 if sse < best[0]:
18 best = (sse, (xs[i] + xs[i + 1]) / 2)
19 return best
20
21def grow(X, y, depth=0, max_depth=None, min_leaf=1):
22 node = {"value": y.mean(), "n": len(y)}
23 if (max_depth is not None and depth >= max_depth) or len(y) < 2 * min_leaf or np.ptp(y) == 0:
24 return node
25 parent_sse = ((y - y.mean()) ** 2).sum()
26 best = (parent_sse, None, None) # (SSE, feature, threshold)
27 for j in range(X.shape[1]):
28 sse, t = best_split(X[:, j], y, min_leaf)
29 if t is not None and sse < best[0]:
30 best = (sse, j, t)
31 sse, j, t = best
32 if j is None:
33 return node
34 L = X[:, j] <= t
35 node.update(feature=j, threshold=t, gain=parent_sse - sse,
36 left=grow(X[L], y[L], depth + 1, max_depth, min_leaf),
37 right=grow(X[~L], y[~L], depth + 1, max_depth, min_leaf))
38 return node
39
40def predict(node, x):
41 while "threshold" in node:
42 node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
43 return node["value"]
44
45def show(node, pad=""):
46 if "threshold" in node:
47 print(f"{pad}x{node['feature']} <= {node['threshold']} (SSE drop {node['gain']:.2f})")
48 show(node["left"], pad + " "); show(node["right"], pad + " ")
49 else:
50 print(f"{pad}leaf: {node['value']:.2f} (n={node['n']})")
51
52T = np.array([2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35.])
53y = np.array([8, 10, 13, 19, 24, 30, 33, 35, 34, 29, 22, 17.])
54tree = grow(T[:, None], y, max_depth=2)
55show(tree)
56pred = np.array([predict(tree, [t]) for t in T])
57print("train MSE:", ((pred - y) ** 2).mean())
58print("T = 27 ->", round(predict(tree, [27]), 2))
59
60# x0 <= 12.5 (SSE drop 640.67)
61# x0 <= 9.5 (SSE drop 56.33)
62# leaf: 10.33 (n=3)
63# leaf: 19.00 (n=1)
64# x0 <= 30.5 (SSE drop 192.67)
65# leaf: 30.83 (n=6)
66# leaf: 19.50 (n=2)
67# train MSE: 9.0
68# T = 27 -> 30.83
From scratch in NumPy: prefix-sum split search, recursive growth, prediction. Prints the depth-2 tree from the worked example.
python
1import numpy as np
2from sklearn.tree import DecisionTreeRegressor, export_text
3from sklearn.metrics import mean_squared_error, r2_score
4
5T = np.array([2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35.]).reshape(-1, 1)
6y = np.array([8, 10, 13, 19, 24, 30, 33, 35, 34, 29, 22, 17.])
7
8tree = DecisionTreeRegressor(max_depth=2, random_state=0).fit(T, y)
9print(export_text(tree, feature_names=["temp"]))
10pred = tree.predict(T)
11print("train MSE:", mean_squared_error(y, pred), " R2:", round(r2_score(y, pred), 4))
12print("T = 27 ->", tree.predict([[27]]).round(2), " T = 45 ->", tree.predict([[45]]).round(2))
13
14# How depth changes the fit
15for d in [1, 2, 3, None]:
16 m = DecisionTreeRegressor(max_depth=d, random_state=0).fit(T, y)
17 print(f"max_depth={d}: {m.get_n_leaves()} leaves, train MSE {mean_squared_error(y, m.predict(T)):.2f}")
18
19# Cost-complexity pruning path (alphas are in MSE units)
20path = DecisionTreeRegressor(random_state=0).cost_complexity_pruning_path(T, y)
21print("ccp alphas:", [round(float(a), 2) for a in path.ccp_alphas])
22for a in [5, 20]:
23 m = DecisionTreeRegressor(ccp_alpha=a, random_state=0).fit(T, y)
24 print(f"ccp_alpha={a}: {m.get_n_leaves()} leaves, train MSE {mean_squared_error(y, m.predict(T)):.2f}")
25
26# |--- temp <= 12.50
27# | |--- temp <= 9.50
28# | | |--- value: [10.33]
29# | |--- temp > 9.50
30# | | |--- value: [19.00]
31# |--- temp > 12.50
32# | |--- temp <= 30.50
33# | | |--- value: [30.83]
34# | |--- temp > 30.50
35# | | |--- value: [19.50]
36# train MSE: 9.0 R2: 0.8917
37# T = 27 -> [30.83] T = 45 -> [19.5]
38# max_depth=1: 2 leaves, train MSE 29.75
39# max_depth=2: 4 leaves, train MSE 9.00
40# max_depth=3: 7 leaves, train MSE 2.40
41# max_depth=None: 12 leaves, train MSE 0.00
42# ccp alphas: [0.0, 0.04, 0.13, 0.17, 0.89, 1.0, 1.04, 1.07, 4.67, 4.69, 16.06, 53.39]
43# ccp_alpha=5: 3 leaves, train MSE 13.69
44# ccp_alpha=20: 2 leaves, train MSE 29.75
scikit-learn on the same data: the same tree, the same prediction, the effect of depth and the pruning path.

Use when

  • +The relationship is non-linear, non-monotonic or full of thresholds and interactions you can't specify in advance.
  • +You need a model a person can read: each prediction is a short rule ending in an average of real training cases.
  • +Features are on wildly different scales or mixed with ordinal codes — splits only use the order of values, so no scaling is needed.
  • +You want a fast baseline, or the base learner for a forest or a boosted ensemble.

Avoid when

  • −The target is smooth in the features: a staircase needs many leaves (and much data) to approximate even a straight line.
  • −You must extrapolate: predictions are always averages of training targets, so they never leave the observed range.
  • −Stability matters: a small change in the data can move the root split and rewrite the whole tree.
  • −You need the best accuracy from one model: a single deep tree has high variance — use an ensemble.

Where it's used

Demand forecasting baselines

Bike, taxi and energy demand vs weather, hour and weekday — strongly non-monotonic, threshold-heavy relationships.

Pricing and valuation rules

Explainable price bands for houses, insurance premiums or used cars, where each band is an auditable rule.

Exploratory analysis

A shallow tree on a KPI shows which variables and cut-points explain most of its variance.

Base learner of ensembles

Every random forest, gradient boosting, XGBoost, LightGBM and CatBoost regressor is a sum or average of regression trees.

Check yourself

A leaf contains training targets 4, 6 and 11. Under squared error, what does it predict, and what is its SSE?

Check yourself

A node has 12 points. Split A sends 4 points with mean 12.5 left and 8 with mean 28 right. Split B sends 9 points with mean 22.89 left and 3 with mean 22.67 right. Which reduces SSE more, and by how much?

Check yourself

The depth-2 bike tree was trained on temperatures 2–35 °C. What does it predict for a 45 °C day?

Check yourself

With max_depth = 3, what is the maximum number of distinct values a regression tree can predict?

Remember

  • ✓A regression tree is a step function: f^(x)=∑mcm1[x∈Rm]\hat f(x)=\sum_m c_m\mathbf 1[x\in R_m], with each leaf predicting the mean of its training targets (the minimizer of squared error).
  • ✓Splits are chosen greedily to minimize SSEL+SSER\text{SSE}_L+\text{SSE}_R; the drop equals nLnRn(yˉL−yˉR)2\tfrac{n_Ln_R}{n}(\bar y_L-\bar y_R)^2, i.e. variance reduction.
  • ✓Running sums of y and y² make the threshold scan O(n) per sorted feature.
  • ✓Without limits the tree reaches zero training error; control it with max_depth, min_samples_leaf or cost-complexity pruning (ccp_alpha), chosen by cross-validation.
  • ✓Trees need no scaling and capture thresholds and interactions, but they cannot extrapolate and have high variance — the reason forests and boosting exist.
← back to ML Algorithms roadmap