Decision Trees, and Why They Overfit, carrying the kNN exposure

Context

A decision tree prices a listing by asking a short chain of questions about its columns, each comparing one value with a threshold, and returns the mean price of the training listings that gave the same answers. kNN keeps the training listings themselves and prices a new one as the mean price of the few most like it, which makes it the model with no training step.

A listings site quotes a seller the prices of comparable listings, which is kNN's question, and a pricing team that must say why a listing got its price can read a tree's answer one question at a time. The next two lessons build their models out of many trees.

What goes wrong is quiet. A tree grown without a limit reproduces every training price and prices new listings worse than a linear model on the same columns, a kNN on raw columns lets area and build year decide which listings count as alike, and a tree asked about a listing of 5,000 square meters quotes the price it gives the same listing at 278.5, without a warning. Lesson 3.3.2 chose a setting on validation rows carved from the training rows, and this lesson chooses k, a depth and a leaf size the same way.

Goal

• Fit KNeighborsRegressor behind a scaled pipeline, trace a prediction to its neighbors' prices with kneighbors, and choose k on validation rows.
• Diagnose what scaling does for kNN by removing the columns the raw scale silences.
• Trace a DecisionTreeRegressor with export_text, and reproduce its first question and one leaf's price by hand, gaps included.
• Measure how max_depth and min_samples_leaf trade the training score against the validation score, choose a setting, and score the refitted tree once on the test rows.
• Identify what a tree cannot do: price past its training range, keep a fully grown tree's prices through a scaler, or keep its questions when its rows change.

Prerequisites

None of this is required, and the lesson stands on its own. Both are here if you want a tree grown by hand, or kNN in scikit-learn's own words, before you start.

• YouTube - "Regression Trees, Clearly Explained!!!" by StatQuest with Josh Starmer. A tree grown on a small table by hand: every threshold scored by the sum of squared residuals it leaves, each leaf predicting the average of its rows, and a minimum number of rows a node must hold before it is split, to keep it from chasing single points.
• Official docs - scikit-learn 1.9 User Guide, "Nearest Neighbors", the section "Nearest Neighbors Regression". A prediction as the mean of the nearest neighbors' targets, KNeighborsRegressor beside a regressor that uses every neighbor within a fixed radius, and the weights keyword.

Table of Contents

• kNN, the Model With No Training Step
• How a Tree Splits
• Growing a Tree Until Its Leaves Are Pure
• Depth, Leaf Size and the Overfitting They Hold Back
• What a Tree Cannot Do

Theory

Nothing to install: KNeighborsRegressor and DecisionTreeRegressor arrived with Lesson 3.1.1's scikit-learn. The first Theory block is a module, price_models.py, saved in ~/dev/bootcamp beside listings.csv and imported by every script of the lesson, as Lesson 3.1.2's scripts imported memorizer.py. Every other Theory block goes into one script, trees.py, each block added under the one before it and run with python3 trees.py.

Choosing k, a depth or a leaf size is a choice about the model, so the rows are split three ways, as in Lesson 3.3.2: the 600 test listings held out of all 3,000, then a quarter of the 2,400 training rows held back as 600 validation rows, which every comparison is scored on, leaving 1,800 to fit. The test rows score each model once, after its settings are fixed.

kNN, the Model With No Training Step

What. KNeighborsRegressor, from sklearn.neighbors, is the kNN of Lesson 3.2.1: it prices a listing as the plain mean price of the k training listings nearest to it by Lesson 2.3.3's Euclidean distance, with k set by n_neighbors, 5 unless you choose. Its fit chooses no parameter. It keeps the training rows and their prices, and the distances are computed in predict. Why. Everything kNN knows is the rows it kept, so k decides how many listings answer for each new one, and the scale of each column decides which listings count as near. When. For a price read off the listings most like a new one, the comparables a pricing team shows a seller, always behind a step that fills its gaps.

Save the first block as price_models.py:

import pandas as pd
from sklearn.compose import ColumnTransformer
from sklearn.impute import SimpleImputer
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import OneHotEncoder, OrdinalEncoder, StandardScaler
from sklearn.tree import DecisionTreeRegressor

listings = pd.read_csv("listings.csv")
numeric = ["area_sqm", "year_built", "distance_km", "rooms", "bathrooms"]
nominal = ["neighborhood", "property_type", "energy_rating"]
levels = ["poor", "fair", "good", "excellent"]
X = listings[numeric + nominal + ["condition"]]
y = listings["price"]
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)
# a quarter of the 2,400 training rows held back to validate on
X_fit, X_val, y_fit, y_val = train_test_split(
    X_train, y_train, test_size=0.25, random_state=42
)


def make_prep(num_step, cats=True):
    # cats=False drops the one-hot columns
    cat_step = OneHotEncoder(sparse_output=False) if cats else "drop"
    return ColumnTransformer([
        ("num", num_step, numeric),
        ("cat", cat_step, nominal),
        ("cond", OrdinalEncoder(categories=[levels]), ["condition"]),
    ])


def fill():
    return SimpleImputer(strategy="median", add_indicator=True)


def fill_scale():
    return make_pipeline(fill(), StandardScaler())


def make_tree(max_depth=None, min_samples_leaf=1, num_step="passthrough"):
    tree = DecisionTreeRegressor(
        max_depth=max_depth, min_samples_leaf=min_samples_leaf, random_state=42
    )
    return make_pipeline(make_prep(num_step), tree)

make_prep is Lesson 3.2.3's, with the step for the numeric columns passed in, because the models of this lesson differ only there. fill() is that lesson's imputer with its indicator, so make_prep(fill()) is 3.2.3's make_prep(numeric), and fill_scale() puts a StandardScaler after it, 3.2.3's last numeric group, for kNN. A tree gets the string "passthrough", which hands its columns on unchanged, gaps included, as remainder="passthrough" did in Lesson 3.2.3, and cats=False puts "drop" in the one-hot group's place, which drops those columns. make_tree builds the tree pipelines of the last four subtitles. trees.py opens with the linear pipeline, the reference every model here is measured against:

import numpy as np
from sklearn.compose import ColumnTransformer
from sklearn.linear_model import LinearRegression
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.tree import export_text
from price_models import (
    X_fit, X_test, X_train, X_val, y_fit, y_test, y_train, y_val,
    fill, fill_scale, make_prep, make_tree, numeric,
)

linear = make_pipeline(make_prep(fill()), LinearRegression())
linear.fit(X_fit, y_fit)
print(len(X_fit), len(X_val), len(X_test))   # 1800 600 600
print(round(linear.score(X_val, y_val), 3))  # 0.84
# 0.766, the same fitted pipeline on the test rows
print(round(linear.score(X_test, y_test), 3))

One fitted pipeline scores 0.84 on the validation rows and 0.766 on the test rows, so these 600 validation listings are easier to price than the 600 test listings. A validation score is compared only with other validation scores, and while a setting is chosen the line to beat is the linear pipeline's 0.84. kNN refuses a gap, as LinearRegression does, and the second line of its message names it:

try:
    KNeighborsRegressor().fit(X_fit[numeric], y_fit)
except ValueError as err:
    lines = str(err).splitlines()
    print(lines[0])
    print(lines[1].split(". ")[0])

Input X contains NaN.
KNeighborsRegressor does not accept missing values encoded as NaN natively

The imputer at the front of fill_scale() answers it. kNN in the pipeline, with k at its default:

knn = make_pipeline(make_prep(fill_scale()), KNeighborsRegressor())
knn.fit(X_fit, y_fit)
model = knn[-1]
# 5 1800
print(model.n_neighbors, model.n_samples_fit_)
print(model.effective_metric_)  # euclidean

first = X_val.iloc[[0]]
dist, pos = model.kneighbors(knn[:-1].transform(first))
print(np.round(dist, 3))
print(y_fit.iloc[pos[0]].to_numpy())
print(y_fit.iloc[pos[0]].mean(), knn.predict(first), y_val.iloc[0])

[[1.447 1.564 1.753 1.837 1.849]]
[312000 213000 508000 357000 343000]
346600.0 [346600.] 346000

n_samples_fit_ counts the rows fit kept, all 1,800, and effective_metric_ names the distance, Lesson 2.3.3's. kneighbors takes rows already prepared, which knn[:-1].transform gives as in Lesson 3.2.3, and returns the distances to the k nearest kept rows and their positions among them. The first validation listing, a 69.9 square meter Lakeview house, gets 346,600, the plain mean of five prices that run from 213,000 to 508,000, against its own price, 346,000. Every k on a list, scored on the fit rows and on the validation rows:

knn_val = {}
for k in [1, 2, 5, 10, 20, 50, 100]:
    knn = make_pipeline(
        make_prep(fill_scale()), KNeighborsRegressor(n_neighbors=k)
    )
    knn.fit(X_fit, y_fit)
    knn_val[k] = round(knn.score(X_val, y_val), 3)
    print(k, round(knn.score(X_fit, y_fit), 3), knn_val[k])

1 1.0 0.588
2 0.866 0.66
5 0.792 0.765
10 0.753 0.771
20 0.724 0.759
50 0.67 0.712
100 0.639 0.672

At k=1 every fit listing is its own nearest neighbor, at distance 0, so it gets its own price back and the fit rows score 1.0, Lesson 3.1.2's memorizer again, while the validation rows score 0.588. Each larger k averages more listings: the fit score falls at every step, and the validation score climbs to 0.771 at k=10 and falls to 0.672 at 100, where every price averages a hundred listings. The validation rows choose k with Lesson 3.3.2's max, then rejoin the training rows, and the chosen pipeline is refitted on all 2,400 and scored on the test rows once:

best_k = max(knn_val, key=knn_val.get)
final_knn = make_pipeline(
    make_prep(fill_scale()), KNeighborsRegressor(n_neighbors=best_k)
)
final_knn.fit(X_train, y_train)
# 10 0.702
print(best_k, round(final_knn.score(X_test, y_test), 3))

kNN scores 0.702 on the 600 test listings, where Lesson 3.2.3's linear pipeline scored 0.766, and the validation rows had ranked the two the same way, 0.771 against 0.84. Lesson 3.2.1 said that a column's scale decides how much it counts in a distance. How much, at k=10, with every column, then without the one-hot columns, then on area and year alone and on area and rooms alone, each scaled and raw:

def knn_score(prep):
    knn = make_pipeline(prep, KNeighborsRegressor(n_neighbors=best_k))
    return round(knn.fit(X_fit, y_fit).score(X_val, y_val), 3)


def only(step, columns):
    return ColumnTransformer([("num", step, columns)])


print(X_fit[numeric].std(ddof=0).round(1).tolist())
for name, step in [("scaled", fill_scale()), ("raw", fill())]:
    print(
        name,
        knn_score(make_prep(step)),
        knn_score(make_prep(step, cats=False)),
        knn_score(only(step, ["area_sqm", "year_built"])),
        knn_score(only(step, ["area_sqm", "rooms"])),
    )

[44.2, 22.8, 3.1, 1.7, 0.8]
scaled 0.771 0.694 0.583 0.562
raw 0.634 0.63 0.583 0.588

Raw, the area spreads with a standard deviation of 44.2 square meters and the year 22.8 years, while a one-hot column holds 0s and 1s. With every column, scaling lifts kNN from 0.634 to 0.771, and without the one-hot columns the gap shrinks from 0.137 to 0.064: those columns lift the scaled model from 0.694 to 0.771 and the raw one only from 0.63 to 0.634, so in the raw distance the neighborhood, type and rating barely decide which listings are near. On area and year alone, at this k, scaling changes nothing the validation rows can see, 0.583 both ways. On area and rooms it costs 0.026, and rooms is the column Lesson 3.3.2 found to be area's near twin. Scaling helps kNN only where the raw scale silences a column that carries information the louder columns lack.

DON'T:

• DON'T fit kNN on raw columns beside one-hot columns. Raw, the one-hot columns moved its validation R² from 0.63 to 0.634, where scaled they moved it from 0.694 to 0.771.
• DON'T read k=1's 1.0 on the fit rows as a good fit. Every fit listing found itself at distance 0, and the validation rows scored 0.588.
• DON'T expect a scaler to help wherever columns differ in scale. On area and rooms it lowered the validation R² from 0.588 to 0.562.

How a Tree Splits

What. DecisionTreeRegressor, from sklearn.tree, is the tree of Lesson 3.2.1: it prices a listing through a chain of questions, each comparing one column with a threshold, a value at or below it going left and a value above it going right. Where the questions stop is a leaf (an end of the tree, which gives one price to every listing that reaches it), the mean price of the training listings that reached it, and the depth of a tree (the largest number of questions any listing answers on its way to a leaf) grows each time a question is added below the deepest one. Why. Each question is chosen by Lesson 3.1.3's squared error, the default criterion: of every column and every threshold, the split whose two sides, each predicted by its own mean price, leave the smallest sum of squared residuals. A tree multiplies no weight, so it reads from the training rows which column to ask about first and where to cut it, and every price it gives traces back to the answers one listing gave. When. Whenever a price must be explained question by question from the listing's own values, and as the piece the next two lessons build their models from.

make_tree builds every tree in the Theory: the three groups with the numeric columns passed through unless num_step names a step, gaps included, because scikit-learn 1.9.1's DecisionTreeRegressor accepts a missing value, and random_state=42, because the tree tries the columns in a random order at each split, and when two splits lower the error by exactly as much, that order decides which one it keeps. A tree held to two questions, fitted on the 2,400 training rows:

small = make_tree(max_depth=2).fit(X_train, y_train)
names = list(small[0].get_feature_names_out())
print(len(names))  # 24
# the text ends in a line break of its own
print(export_text(small[-1], feature_names=names), end="")

|--- num__area_sqm <= 109.20
|   |--- num__area_sqm <= 66.55
|   |   |--- value: [210976.07]
|   |--- num__area_sqm >  66.55
|   |   |--- value: [350646.65]
|--- num__area_sqm >  109.20
|   |--- num__distance_km <= 6.65
|   |   |--- value: [657851.43]
|   |--- num__distance_km >  6.65
|   |   |--- value: [462251.67]

export_text, from sklearn.tree, prints a fitted tree one branch per line, each question once with <= and once with >, and a value at each leaf, the price it predicts. The tree is handed 24 columns: the five numbers, with no indicator columns because nothing filled them, and the 19 encoded columns. Its first question is whether the area is at most 109.20 square meters, the smaller side asks about the area again, the larger side about the distance, and each leaf gives its one price to every listing that reaches it. export_text never says which side a gap goes to, and predict shows where the 90 training listings with no area went:

area = X_train["area_sqm"]
no_area = area.isna()
print(no_area.sum())                      # 90
print(np.unique(small.predict(X_train[no_area])))
in_leaf = ((area > 66.55) & (area <= 109.2)) | no_area
print(in_leaf.sum())                      # 1016
print(round(y_train[in_leaf].mean(), 2))  # 350646.65

[350646.65354331]

All 90 reached the leaf for 66.55 to 109.2 square meters with no imputer anywhere, because at each question the tree learned which side its gaps go to. That leaf holds 926 listings with an area in its range and the 90 with none, and its value is their mean price, which pandas computes to the cent. The first question came from a scan, Lesson 3.1.3's search over candidates run over thresholds instead of weights: every midpoint between two neighboring values of a column, tried with the gaps on each side, scored by the sum of squared residuals its two sides leave, each side predicted by its own mean price:

prep = make_prep("passthrough").set_output(transform="pandas")
seen = prep.fit_transform(X_train)  # the 24 columns the tree saw
price = y_train.to_numpy()


def sse(prices):
    return ((prices - prices.mean()) ** 2).sum()


def best_split(values):
    gap = np.isnan(values)
    known = np.unique(values[~gap])
    best = (sse(price), None, None)
    for t in (known[:-1] + known[1:]) / 2:
        for gap_left in (False, True):
            left = (values <= t) | (gap & gap_left)
            total = sse(price[left]) + sse(price[~left])
            if total < best[0]:
                best = (total, t, gap_left)
    return best


found = {col: best_split(seen[col].to_numpy()) for col in seen.columns}
ranked = sorted(found.items(), key=lambda kv: kv[1][0])
print(f"{sse(price):.4e}")          # 9.2019e+13
for col, (total, t, gap_left) in ranked[:3]:
    print(col, f"{total:.4e}", round(t, 2))
print(found["num__area_sqm"][2])    # True

num__area_sqm 5.9152e+13 109.2
num__rooms 6.2850e+13 3.5
cat__property_type_apartment 6.7151e+13 0.5

One mean price for all 2,400 listings leaves 9.2019e+13. Each column's best split leaves less, and area's at 109.2 leaves least, 5.9152e+13, ahead of rooms at 3.5 and the apartment column, with the gaps cheaper on the left, True: the tree's first question, found by hand. Each question below it is the same scan run on only the rows that reached it, which is where area at 66.55 and distance at 6.65 come from.

DON'T:

• DON'T read a leaf as a price per square meter. The leaf for 66.55 to 109.2 square meters gives 350,646.65 to every listing that reaches it, one of 67 square meters and one of 109 alike.
• DON'T take export_text for the whole tree. It never says where a gap goes, and only predict showed the 90 listings with no area landing in the 350,646.65 leaf.

Growing a Tree Until Its Leaves Are Pure

What. Left at its defaults, max_depth=None and min_samples_leaf=1, a tree keeps asking questions while a leaf holds training listings of more than one price that some question can tell apart. Its leaves end up pure (holding listings that all share one price), unless two listings agree on every column and differ in price. Why. A pure leaf hands its listings their own price back, so a fully grown tree reproduces its training prices, chance and all, and its training score says nothing about listings it has not stored. When. Every time a tree is fitted without a limit, and every time a tree's training score is read.

full = make_tree().fit(X_train, y_train)
tree = full[-1]
# 25 2355
print(tree.get_depth(), tree.get_n_leaves())
leaf_of = tree.apply(full[:-1].transform(X_train))
per_leaf = y_train.groupby(leaf_of).agg(["count", "nunique"])
print(per_leaf["count"].value_counts().to_dict())
print((per_leaf["nunique"] == 1).all())      # True
print(full.score(X_train, y_train))          # 1.0
print(round(full.score(X_test, y_test), 3))  # 0.587

{1: 2311, 2: 43, 3: 1}

get_depth() returns the number of questions on the longest path of a fitted tree, get_n_leaves() its leaves, and apply the number of the leaf each row lands in. Grown without a limit, the tree asked up to 25 questions and made 2,355 leaves for 2,400 listings: 2,311 hold one listing, the 44 that hold two or three hold listings of one price, and every training listing gets its own price back, an R² of exactly 1.0. Scored once on the test listings it reaches 0.587, below kNN's 0.702 and the linear pipeline's 0.766. This is overfitting (learning the noise in the training rows along with the pattern), and it is Lesson 3.1.2's memorizer built out of questions: 2,400 prices stored behind a path that finds each one.

DON'T:

• DON'T read a training R² of 1.0 as skill. The fully grown tree reached it by storing 2,400 prices in 2,355 leaves, and scored 0.587 on the test listings.

Depth, Leaf Size and the Overfitting They Hold Back

What. max_depth caps the number of questions on any path, and min_samples_leaf refuses any question that would leave fewer training listings than that in a leaf. Both are hyperparameters, and both stop the splitting early: min_samples_leaf keeps every leaf's price a mean over at least that many listings, while max_depth only shortens the paths, so a leaf at the end of a short path can still hold one listing. Why. A leaf of one listing repeats that listing's price, noise included, and a leaf of many averages over them. A limit trades training score for prices that carry over to new listings, and only rows the fit never saw can say which limit trades best. When. For every tree that will price listings, chosen on validation rows as Lesson 3.3.2 chose its k. Lesson 3.6.3 searches such settings together.

depth_val = {}
for depth in [1, 2, 3, 4, 5, 6, 8, 10, 15, None]:
    tree = make_tree(max_depth=depth).fit(X_fit, y_fit)
    depth_val[depth] = round(tree.score(X_val, y_val), 3)
    print(depth, round(tree.score(X_fit, y_fit), 3), depth_val[depth])

1 0.348 0.383
2 0.489 0.538
3 0.606 0.628
4 0.704 0.702
5 0.778 0.731
6 0.828 0.714
8 0.886 0.598
10 0.946 0.555
15 0.996 0.611
None 1.0 0.614

Each line holds the depth and the R² on the fit rows and on the validation rows. The fit score climbs at every depth, from 0.348 with one question to 1.0 with no limit. The validation score climbs with it to 0.731 at depth 5, falls after, and from depth 8 on stays between 0.555 and 0.614 while the fit score keeps climbing: every depth past the fifth fits the 1,800 fit rows better and prices the validation listings worse than depth 5 did. At depths 1 to 3 the validation score sits above the fit score, the easier draw at work. The leaf size, from the other side:

leaf_val = {}
for leaf in [1, 2, 5, 10, 20, 50, 100]:
    tree = make_tree(min_samples_leaf=leaf).fit(X_fit, y_fit)
    leaf_val[leaf] = round(tree.score(X_val, y_val), 3)
    print(leaf, round(tree.score(X_fit, y_fit), 3), leaf_val[leaf])

1 1.0 0.614
2 0.943 0.692
5 0.88 0.794
10 0.828 0.766
20 0.78 0.76
50 0.713 0.734
100 0.611 0.595

One listing per leaf is the fully grown tree again, 1.0 and 0.614. Five per leaf scores 0.794 on the validation rows, the best of the column, and 100 per leaf lowers both scores, 0.611 and 0.595, a tree too coarse for either set of rows. Each table has its winner, and the validation rows choose between the two:

best_depth = max(depth_val, key=depth_val.get)
best_leaf = max(leaf_val, key=leaf_val.get)
print(best_depth, depth_val[best_depth])  # 5 0.731
print(best_leaf, leaf_val[best_leaf])     # 5 0.794
chosen = make_tree(min_samples_leaf=best_leaf).fit(X_train, y_train)
print(chosen[-1].get_n_leaves())          # 392
print(round(chosen.score(X_test, y_test), 3))

0.673

The tree with at least 5 listings per leaf beat the depth-limited one on the validation rows, 0.794 against 0.731, so it is kept, and the validation rows rejoin the training rows, as in Lesson 3.3.2. Refitted on all 2,400, the chosen tree makes 392 leaves and scores 0.673 on the test rows, once, against 0.587 for the fully grown tree. Its 0.794 was the best of 17 validation scores on the easier draw, so the test score is the one to report. Leaf size 5 also led leaf size 10 by only 0.028, and depth 5 led depth 6 by 0.017, on 600 rows that are one draw, Lesson 3.1.2's point, so each table picks a setting without proving it the best for every set of listings. Lessons 3.6.2 and 3.6.3 choose over many such draws.

DON'T:

• DON'T choose a depth or a leaf size by the test score. Both tables were read on the validation rows, and the test rows scored only the chosen tree, once.
• DON'T report the winning validation score. 0.794 was the best of 17 on rows easier than the test rows, which gave 0.673.

What a Tree Cannot Do

What. Every price a tree gives is computed from the training prices in one leaf, so no prediction leaves the range of the training prices, and a tree cannot extrapolate (carry a trend past the values its training rows hold). A fully grown tree is also one draw of its rows: fitted on other rows, it asks other questions and gives other prices. Why. A pricing service meets listings larger, farther out and newer than any it was fitted on, and a tree and a linear model fail there in opposite directions. A model whose prices move far when its rows change cannot be trusted listing by listing, the problem the next lesson takes up. When. Before a tree prices a listing outside the range of its training rows, before a scaler goes in front of one, and before one fully grown tree is trusted as the model.

linear.fit(X_train, y_train)       # the 2,400 rows, as full was
print(round(linear[-1].coef_[0]))  # 2822, the area's weight
listing = X_test.iloc[[0]].copy()
for area in [47.0, 200.0, 278.5, 5000.0]:
    listing["area_sqm"] = area
    tree_price = full.predict(listing)[0]
    linear_price = linear.predict(listing)[0]
    print(area, round(tree_price), round(linear_price))
huge = X_test.assign(area_sqm=5000.0)
print(full.predict(huge).max(), y_train.max())

47.0 236000 159471
200.0 675000 591198
278.5 1358000 812705
5000.0 1358000 14135572
1544000.0 1930000

The first test listing is a 47.0 square meter Riverside apartment. From 278.5 square meters, the largest area among the training rows, to 5,000, the fully grown tree prices it at 1,358,000: past the last area question on its path, every larger area lands in the same leaf. The linear pipeline adds about 2,822 to its price for each extra square meter, all the way to 14,135,572, more than seven times the most expensive training listing, 1,930,000. Moved to 5,000 square meters, every one of the 600 test listings gets at most 1,544,000 from the tree. Neither number for 5,000 square meters is a price: no listing near that size reached either fit, and the tree cannot extrapolate where the linear model extrapolates without limit.

Lesson 3.2.1 said that a tree rescales its thresholds with the feature, so scaling offers it the same splits. With a StandardScaler as the numeric step, which passes gaps through as Lesson 3.2.1 showed:

for depth in [4, 8, None]:
    raw = make_tree(max_depth=depth).fit(X_train, y_train)
    scaled = make_tree(max_depth=depth, num_step=StandardScaler())
    scaled.fit(X_train, y_train)
    differ = raw.predict(X_test) != scaled.predict(X_test)
    print(depth, differ.sum())

4 0
8 0
None 14

The trees of depth 4 and 8 price every test listing exactly as they did unscaled, and the fully grown tree prices 14 of the 600 differently. A scaler in front of a tree bought nothing at depth 4 or 8, and after one a fully grown tree cannot be counted on to give the same prices. The last run fits two fully grown trees on the two halves of the fit rows:

halves = [
    make_tree().fit(X_fit.iloc[:900], y_fit.iloc[:900]),
    make_tree().fit(X_fit.iloc[900:], y_fit.iloc[900:]),
]
for half in halves:
    half_names = list(half[0].get_feature_names_out())
    rules = export_text(half[-1], feature_names=half_names)
    print(rules.splitlines()[0], round(half.score(X_val, y_val), 3))
gap = np.abs(halves[0].predict(X_val) - halves[1].predict(X_val))
print(round(gap.mean()), (gap == 0).sum())  # 96927 2

|--- num__area_sqm <= 101.75 0.648
|--- num__area_sqm <= 121.10 0.607

Fitted on the first 900 and the last 900 of the fit rows, the two trees open with different questions, area at 101.75 and at 121.10, score 0.648 and 0.607 on the validation rows, and price the same 600 validation listings 96,927 apart on average, agreeing exactly on 2. Each is one draw from its rows, and the next lesson builds one model out of many such draws.

DON'T:

• DON'T ask a tree for a listing beyond its training rows. 278.5 and 5,000 square meters got the same 1,358,000.
• DON'T read the tree's cap as caution. 1,358,000 for 5,000 square meters is no more a price than the linear pipeline's 14,135,572.
• DON'T expect a fully grown tree to price identically after scaling. 14 of the 600 test listings moved.
• DON'T trust one fully grown tree with one listing's price. Two trees from halves of the same rows priced the validation listings 96,927 apart on average.

Lab Exercises

Lab Exercise 1: Comparables, and One Question About the Year

Work in comparables.py in ~/dev/bootcamp, importing from price_models.py. A seller posts a 95.0 square meter Hillcrest townhouse built in 2004, 3.2 kilometers from the center, with 3 rooms, 2 bathrooms, energy rating C and condition good.

Fit the Theory's scaled kNN pipeline at k=10 on the 2,400 training rows. Print its price for the listing beside the mean price of the 10 training listings kneighbors finds, then the smallest and largest area and build year among those 10, and how many share the seller's neighborhood and how many its property type. Repeat with fill() in place of fill_scale(), and say in a comment which columns chose the raw neighbors.

Then fit a tree with max_depth=1 on year_built alone, gaps included, on the training rows, and print its rule. Print what it predicts for the training listings with no year, check both leaf prices with pandas, and print the sum of squared residuals before and after its one question in the Theory's format, with a comment comparing it with the Theory's first question.

Lab Exercise 2: The Numbers Alone, and a Listing Far From the Center

Work in numbers_tree.py. Build a tree pipeline whose ColumnTransformer passes the five numeric columns through, gaps included, and nothing else. Fit it fully grown on the fit rows, and print its depth, its number of leaves and its R² on the fit rows and on the validation rows.

Choose min_samples_leaf from 1, 5, 10, 20, 50 and 100 on the validation rows, refit the chosen tree on the 2,400 training rows and score it once on the test rows, with a comment comparing its best validation score with the Theory's 0.794.

Finally, refit the Theory's linear pipeline on the 2,400 training rows. Print the largest distance among the training rows, then price the first test listing with its distance set to 4.9, 12.0, 20.0 and 40.0 kilometers by both models, and say in a comment what each does past that largest distance.

import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
from sklearn.pipeline import make_pipeline
from sklearn.tree import DecisionTreeRegressor, export_text
from price_models import X_train, y_train, fill, fill_scale, make_prep

seller = pd.DataFrame({
    "area_sqm": [95.0], "year_built": [2004.0], "distance_km": [3.2],
    "rooms": [3], "bathrooms": [2], "neighborhood": ["Hillcrest"],
    "property_type": ["townhouse"], "energy_rating": ["C"],
    "condition": ["good"],
})
for name, step in [("scaled", fill_scale()), ("raw", fill())]:
    knn = make_pipeline(make_prep(step), KNeighborsRegressor(n_neighbors=10))
    knn.fit(X_train, y_train)
    dist, pos = knn[-1].kneighbors(knn[:-1].transform(seller))
    near = X_train.iloc[pos[0]]
    print(name, round(knn.predict(seller)[0]), y_train.iloc[pos[0]].mean())
    print(near["area_sqm"].min(), near["area_sqm"].max())
    print(near["year_built"].min(), near["year_built"].max())
    same_hood = (near["neighborhood"] == "Hillcrest").sum()
    same_type = (near["property_type"] == "townhouse").sum()
    print(same_hood, same_type)
# Raw, area and year chose the neighbors: all 10 sit within 4 square
# meters and 4 years of the seller, and only 2 are townhouses.

scaled 472800 472800.0
78.5 131.5
1984.0 2021.0
4 10
raw 413000 413000.0
91.4 98.1
2001.0 2008.0
1 2

stump = DecisionTreeRegressor(max_depth=1, random_state=42)
stump.fit(X_train[["year_built"]], y_train)
print(export_text(stump, feature_names=["year_built"]), end="")
year = X_train["year_built"]
no_year = year.isna()
gap_price = stump.predict(X_train.loc[no_year, ["year_built"]])[0]
print(no_year.sum(), round(gap_price, 2))
older = year <= 1970.5
print(older.sum(), round(y_train[older].mean(), 2))
print((~older).sum(), round(y_train[~older].mean(), 2))


def sse(prices):
    return ((prices - prices.mean()) ** 2).sum()


after = sse(y_train[older]) + sse(y_train[~older])
print(f"{sse(y_train):.4e} {after:.4e}")
# The year's best question leaves 8.9454e+13 of 9.2019e+13. Area's
# first question in the Theory left 5.9152e+13, far less.

|--- year_built <= 1970.50
|   |--- value: [313852.02]
|--- year_built >  1970.50
|   |--- value: [397901.23]
110 397901.23
446 313852.02
1954 397901.23
9.2019e+13 8.9454e+13

from sklearn.compose import ColumnTransformer
from sklearn.linear_model import LinearRegression
from sklearn.pipeline import make_pipeline
from sklearn.tree import DecisionTreeRegressor
from price_models import (
    X_fit, X_test, X_train, X_val, y_fit, y_test, y_train, y_val,
    fill, make_prep, numeric,
)


def numbers_tree(min_samples_leaf=1):
    only_numbers = ColumnTransformer([("num", "passthrough", numeric)])
    tree = DecisionTreeRegressor(
        min_samples_leaf=min_samples_leaf, random_state=42
    )
    return make_pipeline(only_numbers, tree)


grown = numbers_tree().fit(X_fit, y_fit)
# 28 1786
print(grown[-1].get_depth(), grown[-1].get_n_leaves())
fit_r2 = grown.score(X_fit, y_fit)
val_r2 = grown.score(X_val, y_val)
print(round(fit_r2, 3), round(val_r2, 3))  # 1.0 0.311

leaf_val = {}
for leaf in [1, 5, 10, 20, 50, 100]:
    tree = numbers_tree(leaf).fit(X_fit, y_fit)
    leaf_val[leaf] = round(tree.score(X_val, y_val), 3)
print(leaf_val)
best_leaf = max(leaf_val, key=leaf_val.get)
chosen = numbers_tree(best_leaf).fit(X_train, y_train)
print(best_leaf, round(chosen.score(X_test, y_test), 3))
# At best 0.657 on the validation rows, against 0.794 with the
# encoded columns: without them, no leaf size comes close.

{1: 0.311, 5: 0.624, 10: 0.657, 20: 0.64, 50: 0.636, 100: 0.594}
10 0.556

linear = make_pipeline(make_prep(fill()), LinearRegression())
linear.fit(X_train, y_train)
print(X_train["distance_km"].max())  # 12.0
listing = X_test.iloc[[0]].copy()
for km in [4.9, 12.0, 20.0, 40.0]:
    listing["distance_km"] = km
    tree_price = chosen.predict(listing)[0]
    linear_price = linear.predict(listing)[0]
    print(km, round(tree_price), round(linear_price))
# Past 12.0 km the tree keeps one leaf's price, 189,600. The linear
# pipeline falls by about 6,171 for each extra kilometer, below zero
# by 40.

4.9 254867 159471
12.0 189600 115659
20.0 189600 66293
40.0 189600 -57122

Theory Assessment

Q1: A Model That Stores Its Rows

Explain what KNeighborsRegressor's fit keeps, where the first validation listing's 346,600 came from, and why k=1 scored 1.0 on the fit rows and 0.588 on the validation rows. Then explain what the run without the one-hot columns, 0.694 scaled against 0.63 raw, says about why raw kNN scored 0.634 with every column where scaled kNN scored 0.771.

Hint: Ask what each fit listing's nearest kept row is at k=1. Then compare how much the one-hot columns added to each of the two models.

Q2: One Question, One Leaf, 2,355 Leaves

Explain how the tree chose num__area_sqm <= 109.20 as its first question, why the 90 training listings with no area all got 350,646.65 though nothing filled their gap, and why export_text alone could not show it. Then explain how the fully grown tree scored exactly 1.0 on its 2,400 training rows with 2,355 leaves, and what its 0.587 on the test rows says about those leaves.

Hint: The scan tried every midpoint of every column, with the gaps on each side. For the second part, ask what a pure leaf hands back to the listings in it.

Q3: Two Tables, Then One Test Score

In the depth table the R² on the fit rows climbs from 0.348 to 1.0, while the validation R² peaks at 0.731 at depth 5 and stays between 0.555 and 0.614 from depth 8 on. Explain both columns, and why min_samples_leaf traces the same shape from the other side. Then explain why the chosen tree was refitted on all 2,400 training rows before the test rows scored it, and why its 0.794 is not the number to report.

Hint: Ask what each extra question, or each smaller leaf, lets the tree do with the fit rows. Then ask which rows chose the setting, and how many settings competed for 0.794.

Q4: Four Claims About Trees and Neighbors

A teammate writes the lesson up in four claims. Say which hold, and correct the ones that do not, with the lesson's numbers.

1. kNN has no training step, so it cannot overfit, and its score on the fit rows is as good a guide to k as the validation score.
2. No price a tree predicts can be above the most expensive listing in the rows it was fitted on.
3. A scaler cannot change a tree's predictions, because Lesson 3.2.1 said scaling offers a tree the same splits.
4. For a listing of 5,000 square meters the fully grown tree's 1,358,000 is the safer price, because it stays inside the prices the market has shown.

Hint: Look at k=1's two scores, at what a leaf predicts, at the fully grown tree's test listings after scaling, and at what the tree gave the same listing at 278.5 square meters.

Assignment

Assignment: A Tree That Answers in Medians

The pricing team's question is how far off a typical quote is, in currency, Lesson 3.1.4's MAE, and the team fixed that metric before any tree was fitted, so every candidate is scored by MAE. Every tree in this lesson chose its splits by squared error and put the mean price in each leaf, the center Lesson 3.1.3 showed a long upper tail pulling. DecisionTreeRegressor takes another criterion: criterion="absolute_error" scores each candidate split by the absolute error its two sides leave, each side predicted by its median price, and puts the median price of its training listings in each leaf, 3.1.3's other center. In scikit-learn 1.9.1 it accepts gaps as the default criterion does.

Write median_tree.py. For both criteria, fit the tree pipeline at every depth of the Theory's depth list on the fit rows, and print the validation MAE in whole units, one line per criterion. Choose the criterion and depth with the smallest validation MAE, refit on the 2,400 training rows, and score the test rows once, by MAE and by R². Prove that every training listing's prediction is the median price of the training listings in its leaf, and that the predictions are not the leaf means. Finally, print the chosen tree's price for the first test listing at 5,000 square meters, the lowest and highest price any of its leaves holds and the training prices' range, with a comment on what those numbers mean for a listing outside the training rows.

Hints:

• A dictionary keyed by (criterion, depth) holds every validation MAE, and min with key= returns the key of the smallest, as max did for the Theory's settings.
• apply gives each training listing's leaf, and Lesson 2.6.2's groupby(...).transform("median") gives each listing the median price of its leaf, ready to compare with predict by np.array_equal.

import numpy as np
from sklearn.metrics import mean_absolute_error, r2_score
from sklearn.pipeline import make_pipeline
from sklearn.tree import DecisionTreeRegressor
from price_models import (
    X_fit, X_test, X_train, X_val, y_fit, y_test, y_train, y_val, make_prep,
)


def tree_for(criterion, depth):
    tree = DecisionTreeRegressor(
        criterion=criterion, max_depth=depth, random_state=42
    )
    return make_pipeline(make_prep("passthrough"), tree)


val_mae = {}
for criterion in ["squared_error", "absolute_error"]:
    row = []
    for depth in [1, 2, 3, 4, 5, 6, 8, 10, 15, None]:
        tree = tree_for(criterion, depth).fit(X_fit, y_fit)
        mae = round(mean_absolute_error(y_val, tree.predict(X_val)))
        val_mae[(criterion, depth)] = mae
        row.append(mae)
    print(criterion, row)
best = min(val_mae, key=val_mae.get)
print(best, val_mae[best])

squared_error [113902, 96959, 86048, 74311, 69040, 67643, 71189, 75486, 77283, 76358]
absolute_error [111074, 95178, 86358, 75638, 66243, 65254, 62636, 68072, 75372, 81945]
('absolute_error', 8) 62636

criterion, depth = best
chosen = tree_for(criterion, depth).fit(X_train, y_train)
test_pred = chosen.predict(X_test)
test_mae = mean_absolute_error(y_test, test_pred)
# 63926 0.693
print(round(test_mae), round(r2_score(y_test, test_pred), 3))

leaf_of = chosen[-1].apply(chosen[:-1].transform(X_train))
by_leaf = y_train.groupby(leaf_of)
train_pred = chosen.predict(X_train)
medians = by_leaf.transform("median").to_numpy()
means = by_leaf.transform("mean").to_numpy()
print(np.array_equal(train_pred, medians))  # True
print(np.array_equal(train_pred, means))    # False

listing = X_test.iloc[[0]].assign(area_sqm=5000.0)
print(chosen.predict(listing))              # [1358000.]
print(train_pred.min(), train_pred.max())   # 65500.0 1544000.0
print(y_train.min(), y_train.max())         # 60000 1930000
# Every leaf holds a median of training prices, so no listing, a
# 5,000 square meter one included, gets a price outside 65,500 to
# 1,544,000: the median changed the center, not the reach.

Additional Resources

Optional, and nothing later depends on either. Worth a look if you want a third way to hold a tree back, or the arrays a fitted tree is stored in.

• YouTube - "How to Prune Regression Trees, Clearly Explained!!!" by StatQuest with Josh Starmer. Cost complexity pruning: a full-sized tree cut back into a sequence of smaller trees, each scored by its sum of squared residuals plus a charge for every leaf, with the charge chosen by cross-validation.
• Official docs - scikit-learn 1.9 example, "Understanding the decision tree structure". The arrays behind a fitted tree, each node's depth and whether it is a leaf, and the path one row takes through the tree with decision_path, beside the apply this lesson used.

Summary

Neither model in this lesson multiplies a weight. kNN keeps its rows and looks them up, a tree keeps its questions and walks them, and both turned out to be ways of remembering: at k=1 and fully grown, each gave back every training price and priced new listings worse than a linear model on the same columns. What made either useful was a limit, more neighbors, fewer questions or larger leaves, and only rows the fit never saw could choose it, the validation rows choosing and the test rows scoring once at the end.

Scale meant different things to the two. For kNN it decides what near means, and the runs showed it helping only where the raw scale silenced a column carrying information the louder ones lacked, changing nothing on area and year at k=10 and costing something on area and its twin. For a tree it moves the thresholds and offers the same splits, and still a fully grown tree priced a few test listings differently after a scaler, so even a sentence that holds for the training rows earns a check on new ones.

What a tree cannot do sets up the rest of the section. It never prices outside the prices it has stored, which spares it the linear pipeline's fourteen million for an absurd listing and leaves it blind to anything past its largest one, and it changes a great deal when its rows change: two trees grown on two halves of the same rows disagreed by nearly a hundred thousand on an average listing. That disagreement is not a defect to fix in one tree. It is the raw material the next lesson averages.

Cheat Sheet

Part A - Reference Table

Part B - Compact Code Block

knn = make_pipeline(
    make_prep(fill_scale()), KNeighborsRegressor(n_neighbors=10)
)
knn.fit(X_fit, y_fit)         # keeps the rows
dist, pos = knn[-1].kneighbors(knn[:-1].transform(X_val.iloc[[0]]))
y_fit.iloc[pos[0]].mean()     # equals the prediction

tree = make_tree(max_depth=2).fit(X_train, y_train)
names = list(tree[0].get_feature_names_out())
print(export_text(tree[-1], feature_names=names))
tree[-1].get_depth(), tree[-1].get_n_leaves()

val = {}
for leaf in [1, 2, 5, 10, 20, 50, 100]:
    fitted = make_tree(min_samples_leaf=leaf).fit(X_fit, y_fit)
    val[leaf] = fitted.score(X_val, y_val)
best = max(val, key=val.get)  # chosen on validation
final = make_tree(min_samples_leaf=best).fit(X_train, y_train)
final.score(X_test, y_test)   # once, at the end