Definition
A regression tree predicts a number by asking yes/no questions of the form is ? 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 → the mean stored in the leaf lands in
- Learns
- a feature + threshold per internal node, one constant per leaf
- Split criterion
- squared error: minimize (equivalently, maximize variance reduction)
- Training cost
- to sort each feature, then per tree level with running sums
- Prediction cost
- comparisons — independent of
- 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 explains only 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 (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 ? 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
- Split
- a pair (feature , threshold ) sending points with 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 a leaf predicts; under squared error, the mean of the leaf's training targets
- SSE
- sum of squared errors 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 computes
- the m-th leaf region (an axis-aligned box)
- the constant predicted in that leaf
- indicator: 1 if x falls in the region, else 0
- number of leaves
Training minimizes the squared error over both the regions and the constants:
- target of training point i
- its feature vector
Leaf values are means. Fix the regions. Each leaf's term depends only on its own , so set its derivative to zero: , which gives . What is left in each leaf is its sum of squared errors around its mean:
- the set of training points in a node
- its size and mean target
- 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 it tries every feature and threshold , splits into and , and keeps the pair with the smallest . Equivalently it maximizes the drop
- points with and
- how many points go each way
- 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 gives the variance reduction , the regression analogue of information gain. Because the parent term is fixed, minimizing children's SSE is also the same as maximizing , which needs only running sums — this is what makes an 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 leaves; the step function has at most jumps per path. Lower → higher bias, lower variance.
- min_samples_leaf = k
- only thresholds with and are candidates. Each leaf mean then averages at least targets, so its noise variance is at most .
- 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 ( = training-set size): a minimum variance reduction per split
- max_leaf_nodes
- grow best-first (largest anywhere in the tree) and stop at that many leaves
- ccp_alpha = α
- after growing, prune to minimize — every leaf must buy at least of training MSE
- number of leaves of tree T
- training MSE contribution of node t if it were collapsed into a leaf
- contribution of the subtree rooted at t, as grown
- 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 in °C) and the target (bike rentals, in hundreds). Rentals climb until the mid-20s and drop on hot days. Overall: , , so the root mean is and the root SSE is (variance 83.14).
| Day | T (°C) | Rentals y |
|---|---|---|
| 1 | 2 | 8 |
| 2 | 5 | 10 |
| 3 | 8 | 13 |
| 4 | 11 | 19 |
| 5 | 14 | 24 |
| 6 | 17 | 30 |
| 7 | 20 | 33 |
| 8 | 23 | 35 |
| 9 | 26 | 34 |
| 10 | 29 | 29 |
| 11 | 32 | 22 |
| 12 | 35 | 17 |
Growing a depth-2 tree by hand
- 1Candidates. The 12 sorted temperatures give 11 midpoints: 3.5, 6.5, …, 33.5.
- 2Score one. For : left has mean and SSE ; right has mean and SSE . Children SSE , so . Check with the shortcut: .
- 3Score all 11 (table below). has the smallest children SSE, so it becomes the root. Training MSE drops from to .
- 4Recurse left (4 cold days, SSE 69). Candidates 3.5, 6.5, 9.5 leave SSE 42.00, 20.00, 12.67. Best: → leaves (mean 10.33) and (mean 19).
- 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: → leaves (mean , SSE 82.83) and (mean 19.5, SSE 12.5).
- 6Stop at max_depth 2. Total leaf SSE , so training MSE and .
- 7Predict a 27 °C day: → right; → left. Prediction 30.83 hundred rentals (the straight line would say 27.09).
| Split | n left | Left mean (SSE) | Right mean (SSE) | Children SSE | Drop Δ |
|---|---|---|---|---|---|
| T ≤ 3.5 | 1 | 8.00 (0.00) | 24.18 (757.64) | 757.64 | 240.03 |
| T ≤ 6.5 | 2 | 9.00 (2.00) | 25.60 (536.40) | 538.40 | 459.27 |
| T ≤ 9.5 | 3 | 10.33 (12.67) | 27.00 (360.00) | 372.67 | 625.00 |
| T ≤ 12.5 | 4 | 12.50 (69.00) | 28.00 (288.00) | 357.00 | 640.67 |
| T ≤ 15.5 | 5 | 14.80 (174.80) | 28.57 (269.71) | 444.51 | 553.15 |
| T ≤ 18.5 | 6 | 17.33 (367.33) | 28.33 (267.33) | 634.67 | 363.00 |
| T ≤ 21.5 | 7 | 19.57 (577.71) | 27.40 (241.20) | 818.91 | 178.75 |
| T ≤ 24.5 | 8 | 21.50 (786.00) | 25.50 (169.00) | 955.00 | 42.67 |
| T ≤ 27.5 | 9 | 22.89 (924.89) | 22.67 (72.67) | 997.56 | 0.11 |
| T ≤ 30.5 | 10 | 23.50 (958.50) | 19.50 (12.50) | 971.00 | 26.67 |
| T ≤ 33.5 | 11 | 23.36 (960.55) | 17.00 (0.00) | 960.55 | 37.12 |
| Leaf (rule) | Days | Prediction (mean) | Leaf SSE |
|---|---|---|---|
| T ≤ 9.5 | 2, 5, 8 °C | 10.33 | 12.67 |
| 9.5 < T ≤ 12.5 | 11 °C | 19.00 | 0.00 |
| 12.5 < T ≤ 30.5 | 14 … 29 °C | 30.83 | 82.83 |
| T > 30.5 | 32, 35 °C | 19.50 | 12.50 |
- 1grow(node, depth):
- 2 if depth=max or n<2: leaf ← mean(y)
- 3 for each midpoint t between sorted x:
- 4 SSE(t) ← SSE(left) + SSE(right)
- 5 t* ← argmin SSE(t)
- 6 split at t*; grow(left); grow(right)
- 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.
The algorithm, step by step
Grow(node)
- 1Leaf value. Store the mean of the node's targets (it is the prediction if the node stays a leaf).
- 2Stop? Make it a leaf if depth =
max_depth, the node has fewer thanmin_samples_splitpoints, or all its targets are equal (SSE = 0). - 3Sort and scan. For each feature, sort the node's points by that feature and sweep left to right, keeping running (the right side is total minus left). At each midpoint between distinct values with at least
min_samples_leafpoints on each side, compute in . - 4Choose the (feature, threshold) with the smallest children SSE. If its drop is below
min_impurity_decrease, make a leaf instead. - 5Recurse on the left and right subsets.
- 6(Optional) prune the grown tree with cost-complexity pruning, choosing
ccp_alphaby cross-validation. - 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: per level after an sort (or per level if re-sorting). A balanced tree has levels, a degenerate one up to .
- Prediction
- per query, at most for a balanced tree with leaves
- Memory
- one threshold, feature index and value per node — at most 2n − 1 nodes
- Histogram variant
- bin each feature into buckets once; split search becomes per node — the trick LightGBM and XGBoost's hist mode use
Variants and tuning
| criterion | Impurity of a node | Leaf value | When to use |
|---|---|---|---|
squared_error (default) | SSE / variance | mean | the standard choice; fast O(n) scan |
friedman_mse | improvement score | mean | the default split score inside scikit-learn's gradient boosting; rarely worth choosing for a single tree |
absolute_error | median | heavy-tailed targets or outliers; much slower to fit | |
poisson | Poisson deviance | mean (must be > 0) | counts and rates, e.g. claims, visits |
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.
| Setting | Leaves | Train MSE | CV MSE |
|---|---|---|---|
| max_depth = 1 | 2 | 0.397 | 0.402 |
| max_depth = 3 | 8 | 0.138 | 0.158 |
| max_depth = 5 | 29 | 0.067 | 0.111 |
| max_depth = 8 | 138 | 0.027 | 0.134 |
| no limit | 300 | 0.000 | 0.147 |
| min_samples_leaf = 10 | 23 | 0.072 | 0.109 |
| min_samples_leaf = 50 | 5 | 0.201 | 0.234 |
Practical tuning
- Start with
min_samples_leaf(try 5–50 or 1–5% of n) andmax_depth(3–10); they matter far more than the criterion- Pruning
- compute
cost_complexity_pruning_pathon the training set and cross-validate over its alphas - On the bike data
- the pruning path has = 4.69 (collapsing the cold node: ), 16.06 (the warm node: ) and 53.39 (the root). So
ccp_alpha=5keeps 3 leaves (train MSE 13.69) andccp_alpha=20keeps 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
1import numpy as np23def 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 points11 if xs[i] == xs[i + 1]:12 continue # cannot split between equal x13 nL, nR = i + 1, n - i - 114 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 / n17 if sse < best[0]:18 best = (sse, (xs[i] + xs[i + 1]) / 2)19 return best2021def 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 node25 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 = best32 if j is None:33 return node34 L = X[:, j] <= t35 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 node3940def 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"]4445def 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']})")5152T = 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))5960# 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.068# T = 27 -> 30.831import numpy as np2from sklearn.tree import DecisionTreeRegressor, export_text3from sklearn.metrics import mean_squared_error, r2_score45T = 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.])78tree = 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))1314# How depth changes the fit15for 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}")1819# 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}")2526# |--- temp <= 12.5027# | |--- temp <= 9.5028# | | |--- value: [10.33]29# | |--- temp > 9.5030# | | |--- value: [19.00]31# |--- temp > 12.5032# | |--- temp <= 30.5033# | | |--- value: [30.83]34# | |--- temp > 30.5035# | | |--- value: [19.50]36# train MSE: 9.0 R2: 0.891737# T = 27 -> [30.83] T = 45 -> [19.5]38# max_depth=1: 2 leaves, train MSE 29.7539# max_depth=2: 4 leaves, train MSE 9.0040# max_depth=3: 7 leaves, train MSE 2.4041# max_depth=None: 12 leaves, train MSE 0.0042# 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.6944# ccp_alpha=20: 2 leaves, train MSE 29.75Use 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: , with each leaf predicting the mean of its training targets (the minimizer of squared error).
- ✓Splits are chosen greedily to minimize ; the drop equals , 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_leafor 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.