43  Regression Trees, Ensembles, and Nearest Neighbors

Decision trees represent a family of rule-based supervised learning methods. Unlike global linear models that describe an entire dataset using a single global equation, a decision tree partitions predictor space into smaller regions and fits a simple localized prediction in each one. This approach is particularly effective when relationships between explanatory variables and continuous target responses are non-linear, vary across feature space subregions, or involve complex interactions (Breiman et al. 1984; Hastie et al. 2009).

In regression tasks, the objective is predicting a numerical response. For example, we might estimate laptop prices based on RAM, screen size, processor specs, and brand; or forecast housing prices based on surface area, location, and property age. A regression tree learns decision rules of the form “if a feature falls below a specific threshold, follow one branch; otherwise, follow another”. At the end of each branch lies a terminal leaf node, where the response prediction is typically the average of training observations reaching that specific region.

This chapter develops the core logic of regression trees, their geometric interpretation as piecewise constant functions, split evaluation criteria, pruning techniques to prevent overfitting, and basic evaluation metrics. Subsequently, tree-based ensemble methods are introduced, specifically bagging, random forests, and boosting. Finally, the nearest neighbor algorithm is presented as a contrast to decision trees: a memory-based, distance-driven lazy learning method.

1 From Linear Regression to Region-Based Models

Multiple linear regression models a continuous target \(y\) as a global linear combination of predictor features \(x_1, \ldots, x_p\):

\[ y_i = \beta_0 + \beta_1 x_{i1}+\dots+\beta_p x_{ip}+\varepsilon_i. \]

Its primary advantage is coefficient interpretability: each \(\beta_j\) quantifies the expected change in \(y\) given a one-unit increase in \(x_j\), holding all other features constant. However, this structure enforces a global functional form. When the true relationship between \(X\) and \(y\) varies across different regions of feature space, a single linear equation can prove overly restrictive.

Regression trees address this limitation through recursive partitioning. Rather than fitting a single global surface, they divide predictor space into disjoint regions and assign a constant prediction to each region, producing a flexible, non-parametric, and interpretable model (James et al. 2021).

Definition. A regression tree is a model that partitions predictor feature space into disjoint regions \(R_1,\ldots,R_J\) and predicts a constant value \(c_h\) within each region: \[ \hat f(x)=\sum_{h=1}^{J} c_h\,\mathbb{I}(x\in R_h). \tag{1}\]

Here, \(x\) represents an input observation; \(R_h\) denotes region \(h\) in feature space; \(c_h\) is the prediction assigned to that region (typically the mean observed target response within \(R_h\)); and \(\mathbb{I}(x\in R_h)\) is an indicator function taking value one if \(x \in R_h\) and zero otherwise.

Definition. The indicator function for region \(R_h\) is defined as: \[ \mathbb{I}(x\in R_h)= \begin{cases} 1, & \text{if } x\in R_h,\\ 0, & \text{if } x\notin R_h. \end{cases} \tag{2}\]

2 Non-Linear Classifiers and Piecewise Models

In classification problems, linear classifiers separate classes using decision hyperplanes. When data are linearly separable, this approach is sufficient. However, in real-world applications, class boundaries are often curved, disjoint, or driven by non-linear feature interactions. In these scenarios, two main strategies exist: retaining a linear classifier while tolerating classification errors, or employing non-linear classifiers capable of learning flexible decision boundaries.

A intuitive way to construct non-linearity is combining linear pieces. The core concept involves partitioning a class into sub-classes or local sub-regions and assigning a local linear discriminant to each sub-region. The resulting global boundary transitions from a single hyperplane into a composite union of linear segments or faces. This logic directly foreshadows two key frameworks: decision trees (which split feature space via recursive orthogonal cuts) and nearest neighbors (which carry local decision making to its logical extreme by treating every training sample as a local reference point) (Duda et al. 2001; Hastie et al. 2009).

Definition. A piecewise linear classifier assigns to each class \(\omega_i\) a set of sub-classes \(\omega_i^1,\dots,\omega_i^{\ell_i}\), each possessing a linear discriminant \(g_i^\ell(x)\), defining the class discriminant function as a local maximum: \[ g_i(x)=\max_{\ell=1,\dots,\ell_i} g_i^\ell(x),\qquad \hat y(x)=\arg\max_{i=1,\dots,c} g_i(x). \tag{3}\]

Writing \(g_i^\ell(x)=w_{i\ell}^{\top}x+w_{i\ell,0}\), each sub-class contributes a linear boundary. The maximum operator selects the sub-region that best explains query point \(x\). As the number of sub-classes increases, the decision boundary can approximate complex non-linear shapes. However, this flexibility requires deciding how many sub-classes to instantiate, how to initialize them, and how to avoid overfitting noise.

From this perspective, decision trees construct piecewise constant approximations with axis-aligned boundaries. KNN, on the other hand, can be viewed as an extreme local classifier: rather than learning explicit sub-classes, it stores training examples directly and makes decisions based on local distances.

3 Step Functions

A regression tree produces a piecewise step function. For a single predictor \(x\), a simple model can be expressed as:

\[ \hat f(x)= \begin{cases} 100, & x<10,\\ 200, & 10\le x<20,\\ 300, & x\ge 20. \end{cases} \]

Rather than fitting a continuous line, this model partitions the \(x\)-axis into intervals and assigns a constant target prediction to each interval. In two dimensions, regions form rectangular boxes; in \(p\) dimensions, they form hyper-rectangles. For instance, with age, income, and experience, a decision rule might read:

\[ \text{age}<30 \quad \text{and} \quad \text{income}>5000. \]

Such explicit rules are easily human-readable, explaining the popularity of decision trees in domain-sensitive applications. However, axis-aligned splits impose a geometric constraint: linear diagonal or smooth oblique relationships require many step splits to approximate effectively (Hastie et al. 2009).

4 Prediction Within a Region

Once a tree defines region \(R_h\), the optimal prediction under squared-error loss is the arithmetic mean of target values residing in that region. Given observations within region \(R_h\) with target responses \(y_1, \ldots, y_{n_h}\), constant prediction \(c_h\) is chosen to minimize Sum of Squared Errors:

\[ \sum_{i:x_i\in R_h}(y_i-c_h)^2. \]

Setting the derivative with respect to \(c_h\) to zero yields the sample mean.

Definition. Under squared-error loss, the optimal leaf prediction \(\hat c_h\) for region \(R_h\) in a regression tree is the mean of target responses falling into that leaf: \[ \hat c_h = \frac{1}{|R_h|}\sum_{i:x_i\in R_h} y_i. \tag{4}\]

For example, if a region contains actual values \(\{20, 40, 100, 120\}\), its un-split prediction is:

\[ \hat c=\frac{20+40+100+120}{4}=70. \]

If this region is partitioned into two sub-regions, \(R_1=\{20,40\}\) and \(R_2=\{100,120\}\), the new regional predictions become:

\[ \hat c_1=30,\qquad \hat c_2=110. \]

Partitioning improves accuracy because each sub-region is represented by a mean that far better reflects its localized values.

5 Total Error and Split Criteria

A decision tree evaluates candidate splits by quantifying the reduction in error achieved when partitioning a region. In regression, the standard split criterion is the Residual Sum of Squares (RSS) within leaf nodes (Breiman et al. 1984; James et al. 2021).

Definition. The total squared error of a regression tree with regions \(R_1,\dots,R_J\) is: \[ D(T)=\sum_{h=1}^{J}\sum_{i:x_i\in R_h}(y_i-\hat c_h)^2. \tag{5}\]

When evaluating a candidate split of region \(R\) into left (\(R_L\)) and right (\(R_R\)) sub-regions, the algorithm compares total error before and after splitting:

\[ D_{\text{split}} = \sum_{i:x_i\in R_L}(y_i-\hat c_L)^2+ \sum_{i:x_i\in R_R}(y_i-\hat c_R)^2. \]

Definition. The gain of a split is defined as the absolute error reduction achieved by the partition: \[ \text{Gain}=D_{\text{before}}-D_{\text{after}}. \tag{6}\]

A candidate split is selected if it yields a large reduction in RSS. During training, the algorithm evaluates all candidate split points across all features (e.g., evaluating threshold cuts across age, income, experience) and selects the split maximizing gain.

RSS Split Criterion — Interactive Explorer
Drag the split threshold slider to observe how RSS changes before and after partitioning

RAM Threshold = 6.0 GB

6 Recursive Binary Splitting

Decision tree training employs greedy top-down recursive binary splitting. The algorithm finds the optimal single split for the full training set. It then recursively applies the same splitting procedure to each child region until a stopping criterion is met (e.g., maximum depth, minimum samples per leaf, or minimum error gain).

Workflow steps:

1. Start with all training instances in a single root region.
2. For each predictor feature and candidate threshold cut-point, evaluate the RSS error reduction.
3. Select the single split maximizing RSS error reduction.
4. Recursively repeat steps 2–3 on each child sub-region.
5. Stop growing when stopping constraints or pruning criteria trigger.

Top-down greedy splitting is computationally efficient and generates interpretable rules. However, because it makes greedy local choices at each step without backtracking, it does not guarantee finding globally optimal tree structures (Breiman et al. 1984).

7 Manual Calculation Example: Laptop Pricing by RAM

Consider a toy dataset predicting laptop prices based solely on RAM capacity.

Laptop	RAM	Actual Price
A	4 GB	6,500
B	4 GB	7,200
C	8 GB	10,500
D	8 GB	12,000
E	16 GB	21,000
F	16 GB	24,000

Without splitting, the prediction for all laptops is the global sample mean:

\[ \bar y=\frac{6500+7200+10500+12000+21000+24000}{6}=13,533.33. \]

Unsplit total RSS error is:

\[ D_{\text{unsplit}}=\sum_i(y_i-\bar y)^2=266{,}433{,}333.33. \]

Evaluating candidate split: \(\text{RAM} < 12 \text{ GB}\).

This creates two sub-regions:

\[ R_1=\{6500,7200,10500,12000\},\qquad R_2=\{21000,24000\}. \]

Leaf predictions are regional averages:

\[ \hat c_1=\frac{6500+7200+10500+12000}{4}=9050, \]

\[ \hat c_2=\frac{21000+24000}{2}=22500. \]

Post-split RSS error:

\[ D_{\text{split}}= (6500-9050)^2+(7200-9050)^2+(10500-9050)^2+(12000-9050)^2 +(21000-22500)^2+(24000-22500)^2 = 25{,}230{,}000. \]

Relative error reduction:

\[ \frac{D_{\text{unsplit}}-D_{\text{split}}}{D_{\text{unsplit}}} =\frac{266{,}433{,}333.33-25{,}230{,}000}{266{,}433{,}333.33} \approx 90.53\%. \]

A single split reduces squared prediction error by 90.53%.

8 Python Implementation

import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeRegressor, export_text
from sklearn.metrics import mean_squared_error, r2_score

# Toy dataset
X = pd.DataFrame({
    "RAM_GB": [4, 4, 8, 8, 16, 16]
})
y = np.array([6500, 7200, 10500, 12000, 21000, 24000])

# Depth-1 regression stump
tree = DecisionTreeRegressor(max_depth=1, random_state=42)
tree.fit(X, y)

pred = tree.predict(X)

print(export_text(tree, feature_names=list(X.columns)))
print("Predictions:", pred)
print("MSE:", mean_squared_error(y, pred))
print("R2 Score:", r2_score(y, pred))

Visualizing decision stump predictions vs. actual data points:

import matplotlib.pyplot as plt

ram_grid = np.linspace(3, 17, 200).reshape(-1, 1)
pred_grid = tree.predict(pd.DataFrame(ram_grid, columns=["RAM_GB"]))

plt.figure(figsize=(7, 4))
plt.scatter(X["RAM_GB"], y, color="#1a3a5c", label="Actual Data")
plt.plot(ram_grid, pred_grid, color="#e74c3c", linewidth=2, label="Regression Tree")
plt.xlabel("RAM (GB)")
plt.ylabel("Price ($)")
plt.title("Regression Stump Predictions")
plt.legend()
plt.show()

9 Overfitting and Pruning

Unconstrained trees split recursively until every training sample is isolated into its own leaf node, achieving zero training error. However, this memorizes noise and ruins out-of-sample generalization.

Cost-complexity pruning penalizes tree size during structure selection (Breiman et al. 1984; Pedregosa et al. 2011).

Definition. The cost-complexity objective penalizes total empirical error with a complexity term scaled by leaf count \(J\): \[ C_{\alpha}(T)=\sum_{h=1}^{J}D_h+\alpha J. \tag{7}\]

Here \(D_h\) is RSS error in leaf \(h\), \(J\) is the total leaf count, and \(\alpha \ge 0\) controls the penalty weight. Small \(\alpha\) allows deeper trees; large \(\alpha\) forces compact trees.

from sklearn.model_selection import train_test_split
from sklearn.datasets import fetch_california_housing
from sklearn.metrics import mean_absolute_error, r2_score

housing = fetch_california_housing(as_frame=True)
X_h, y_h = housing.data, housing.target

X_tr, X_te, y_tr, y_te = train_test_split(
    X_h, y_h, test_size=0.25, random_state=42
)

for alpha in [0.0, 0.001, 0.01, 0.05]:
    model = DecisionTreeRegressor(random_state=42, ccp_alpha=alpha)
    model.fit(X_tr, y_tr)
    y_pred_h = model.predict(X_te)
    print({
        "ccp_alpha": alpha,
        "n_leaves": model.get_n_leaves(),
        "MAE": round(mean_absolute_error(y_te, y_pred_h), 4),
        "R2": round(r2_score(y_te, y_pred_h), 4)
    })

Tree Depth and Overfitting
Increase max depth to observe how deep decision trees overfit training noise

Max Depth = 2

10 Regression Tree Evaluation Metrics

Definition. The coefficient of determination \(R^2\) is defined as: \[ R^2=1-\frac{SSE}{SS_{TOT}}, \qquad SSE=\sum_i(y_i-\hat y_i)^2, \qquad SS_{TOT}=\sum_i(y_i-\bar y)^2. \tag{8}\]

An \(R^2 = 0.90\) means the model explains 90% of target response variance relative to a baseline mean predictor. In addition to \(R^2\), Mean Absolute Error (MAE) and Root Mean Squared Error (RMSE) provide absolute error bounds in target units.

11 Bagging: Bootstrap Aggregating

Bagging reduces variance by training decision trees independently on multiple bootstrap samples of the training set and averaging their predictions (Breiman 1996).

Definition. A size-\(n\) bootstrap sample \(\mathcal{D}^{*(b)}\) is generated by sampling \(n\) instances uniformly at random with replacement from original training set \(\mathcal{D}\): \[ \mathcal{D}^{*(b)}=\{(x_1^{*(b)},y_1^{*(b)}),\dots,(x_n^{*(b)},y_n^{*(b)})\}. \tag{9}\]

Definition. The bagging ensemble prediction for regression is the arithmetic mean across \(B\) bootstrap-trained trees: \[ \hat f_{bag}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat f^{*(b)}(x). \tag{10}\]

from sklearn.ensemble import BaggingRegressor

bag = BaggingRegressor(
    estimator=DecisionTreeRegressor(random_state=42),
    n_estimators=100,
    random_state=42,
    n_jobs=-1
)

bag.fit(X_tr, y_tr)
y_pred_bag = bag.predict(X_te)

print("Bagging MAE :", round(mean_absolute_error(y_te, y_pred_bag), 4))
print("Bagging R2  :", round(r2_score(y_te, y_pred_bag), 4))

12 Random Forests

Random Forests extend bagging by injecting feature randomization into node split evaluation (Breiman 2001). At each split candidate, only a random subset of \(m \le p\) features is considered (typically \(m = \sqrt{p}\) for classification and \(m = p/3\) for regression), decorrelating trees and maximizing variance reduction.

Definition. A Random Forest is an ensemble of decorrelated decision trees built on bootstrap samples, where each node split considers only a random feature subset: \[ \hat f_{RF}(x)=\frac{1}{B}\sum_{b=1}^{B}\hat f_b(x). \tag{11}\]

from sklearn.ensemble import RandomForestRegressor

rf = RandomForestRegressor(
    n_estimators=300,
    max_features="sqrt",
    random_state=42,
    n_jobs=-1
)

rf.fit(X_tr, y_tr)
y_pred_rf = rf.predict(X_te)

print("Random Forest MAE :", round(mean_absolute_error(y_te, y_pred_rf), 4))
print("Random Forest R2  :", round(r2_score(y_te, y_pred_rf), 4))

13 Boosting

Unlike bagging, boosting builds models sequentially. Each new weak learner is trained to predict residual errors made by preceding trees (Freund and Schapire 1997; Schapire 1990; Friedman 2001).

Definition. Gradient Boosting for regression fits additive models sequentially: \[ F_M(x)=F_0(x)+\sum_{m=1}^{M}\nu h_m(x), \] where each tree \(h_m\) fits pseudo-residuals of \(F_{m-1}\) and \(\nu \in (0, 1]\) is the learning rate shrinking parameter. $$ {#eq-gradient-boosting}

from sklearn.ensemble import GradientBoostingRegressor

gb = GradientBoostingRegressor(
    n_estimators=300,
    learning_rate=0.05,
    max_depth=3,
    random_state=42
)

gb.fit(X_tr, y_tr)
y_pred_gb = gb.predict(X_te)

print("Gradient Boosting MAE :", round(mean_absolute_error(y_te, y_pred_gb), 4))
print("Gradient Boosting R2  :", round(r2_score(y_te, y_pred_gb), 4))

13.1 Comparison: Bagging vs. Boosting

Feature	Bagging (Random Forest)	Boosting (GBDT / XGBoost)
Model Fitting	Independent (parallel)	Sequential (additive)
Core Objective	Reduce variance	Reduce bias & variance
Sample Focus	Uniform bootstrap	Focuses on high-error instances
Parallelization	Trivial parallel execution	Less parallelizable across trees
Noise Sensitivity	Highly robust	Sensitive to extreme outliers

14 Nearest Neighbor Classification (k-NN)

Nearest neighbor classification is a memory-based (lazy learning) method (Cover and Hart 1967; Duda et al. 2001). It stores training data directly without fitting explicit parametric parameters.

Definition. The 1-NN rule assigns query point \(x\) the label of its single nearest training instance under distance metric \(d\): \[ \hat y(x)=\theta_{i^*},\qquad i^*=\arg\min_{i=1,\dots,N} d(x,x_i). \tag{12}\]

Definition. Minimum distance discriminant function for class \(\omega_j\): \[ g_j(x)=\min_{i:\theta_i=j} d(x,x_i),\qquad \hat y(x)=\arg\min_{j=1,\dots,c} g_j(x). \tag{13}\]

14.1 Distance Metrics

Definition. Minkowski distance of order \(s \ge 1\) between \(x, z \in \mathbb{R}^p\): \[ d_s(x,z)=\left(\sum_{j=1}^{p}|x_j-z_j|^s\right)^{1/s}. \tag{14}\]

• Manhattan (\(s=1\)): \(d_1(x,z)=\sum_{j=1}^{p}|x_j-z_j|\) {#eq-manhattan-distance}
• Euclidean (\(s=2\)): \(d_2(x,z)=\sqrt{\sum_{j=1}^{p}(x_j-z_j)^2}\) {#eq-euclidean-distance}
• Chebyshev (\(s=\infty\)): \(d_{\infty}(x,z)=\max_{j=1,\dots,p}|x_j-z_j|\) {#eq-chebyshev-distance}
• Mahalanobis: \(d_Q(x,z)=(x-z)^{\top}\Sigma^{-1}(x-z)\) {#eq-quadratic-distance}

Minkowski Unit Ball — Interactive Explorer
Drag p to observe unit ball shape changes: diamond (p=1), circle (p=2), square (p→∞)

p = 2  

15 k-NN Classifier

Definition. In \(k\)-NN classification, given \(N_k(x)\) containing the set of indices for the \(k\) nearest training points to \(x\): \[ g_j(x)=\sum_{i\in N_k(x)}\mathbb{I}(\theta_i=j),\qquad \hat y(x)=\arg\max_{j=1,\dots,c}g_j(x). \tag{15}\]

Definition. In \(k\)-NN regression, predictions average the responses of the \(k\) nearest neighbors: \[ \hat f(x)=\frac{1}{k}\sum_{i\in N_k(x)}y_i. \tag{16}\]

k-NN Classifier — Interactive Explorer
Click anywhere on the canvas to place a query point; adjust k to observe decision boundary changes

k = 3

Click on canvas to query point

15.1 Cover-Hart Asymptotic Error Bound

Cover and Hart (1967) established that for \(N \to \infty\) i.i.d. samples, the asymptotic 1-NN error rate \(P_1\) is upper-bounded by Bayes error rate \(P^*\):

Definition. For \(c\) classes, Cover-Hart bound states: \[ P^*\le P_1\le P^*\left(2-\frac{c}{c-1}P^*\right) \le 2 P^*. \tag{17}\]

15.2 Consistency Condition

Definition. \(k\)-NN consistency requires: \[ N\to\infty,\qquad k\to\infty,\qquad \frac{k}{N}\to 0. \tag{18}\]

15.3 Curse of Dimensionality

Definition. In a \(p\)-dimensional unit hypercube, a local neighborhood with linear edge length \(r\) occupies relative volume: \[ V(r,p)=r^p. \tag{19}\]

For \(p=10\) and \(r=0.1\), volume fraction is \(10^{-10}\), demonstrating why density estimation decays exponentially in high dimensions (Bellman 1961).

15.4 Computational Optimization and Pruning Rules

• Branch-and-Bound Node Pruning: \(d(x, M_p) - r_p > B\) {#eq-branch-bound-prune}
• Edited Nearest Neighbors: Remove \((x_i, y_i)\) if \(\hat y_{-i}(x_i) \neq y_i\) {#eq-edited-nn-rule}
• Condensed Nearest Neighbors: Find small subset \(\mathcal{S} \subseteq S_N\) preserving decisions {#eq-condensed-nn}

16 Conclusions

Regression trees replace global linear equations with structured hierarchies of localized decision rules. They offer high interpretability but suffer from high variance, instability, and axis-aligned step constraints. Ensembles like Random Forests (bagging + feature randomization) and Gradient Boosted Trees (sequential residual fitting) dramatically improve accuracy and stability. Finally, Nearest Neighbors offers a memory-based distance-driven alternative, completing the spectrum of non-linear decision modeling.

References

Bellman, Richard E. 1961. Adaptive Control Processes: A Guided Tour. Princeton University Press.

Breiman, Leo. 1996. “Bagging Predictors.” Machine Learning 24 (2): 123–40. https://doi.org/10.1007/BF00058655.

Breiman, Leo. 2001. “Random Forests.” Machine Learning 45 (1): 5–32. https://doi.org/10.1023/A:1010933404324.

Breiman, Leo, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. 1984. Classification and Regression Trees. Wadsworth International Group.

Cover, Thomas M., and Peter E. Hart. 1967. “Nearest Neighbor Pattern Classification.” IEEE Transactions on Information Theory 13 (1): 21–27. https://doi.org/10.1109/TIT.1967.1053964.

Duda, Richard O., Peter E. Hart, and David G. Stork. 2001. Pattern Classification. 2nd ed. Wiley.

Freund, Yoav, and Robert E. Schapire. 1997. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting.” Journal of Computer and System Sciences 55 (1): 119–39. https://doi.org/10.1006/jcss.1997.1504.

Friedman, Jerome H. 2001. “Greedy Function Approximation: A Gradient Boosting Machine.” Annals of Statistics 29 (5): 1189–232. https://doi.org/10.1214/aos/1013203451.

Hastie, Trevor, Robert Tibshirani, and Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. Springer Series in Statistics. Springer. https://doi.org/10.1007/978-0-387-84858-7.

James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2021. An Introduction to Statistical Learning with Applications in R. 2nd ed. Springer Texts in Statistics. Springer. https://doi.org/10.1007/978-1-0716-1418-1.

Pedregosa, Fabian, Gaël Varoquaux, Alexandre Gramfort, et al. 2011. “Scikit-Learn: Machine Learning in Python.” Journal of Machine Learning Research 12: 2825–30. https://jmlr.org/papers/v12/pedregosa11a.html.

Schapire, Robert E. 1990. “The Strength of Weak Learnability.” Machine Learning 5 (2): 197–227. https://doi.org/10.1007/BF00116037.