Decision Trees, Random Forests, and K-Nearest Neighbors

Ask an experienced loan officer how they decide, and they will not hand you an equation. They will draw something on a whiteboard:

Has a prior default?├── yes ──> Decline└── no  ──> Debt-to-income above 45%?            ├── yes ──> Employed more than 2 years?            │            ├── no  ──> Decline            │            └── yes ──> Approve, higher rate            └── no  ──> Approve

Nobody taught them to think in weighted sums. They think in questions, asked in order, where the answer to one determines which question comes next. That structure captures things a linear model finds awkward: the effect of employment length depends entirely on the debt-to-income branch you are standing in, and there is no "coefficient on employment" that holds across the whole population.

Three of the most useful algorithms in practical machine learning come from taking this seriously — one that builds such a tree automatically, one that builds hundreds and averages them, and one that skips rules entirely and just looks at who else resembles you.

Decision trees: learning the questions

The tree above was written by a human. A decision tree algorithm writes one from data by answering, at every node, a single question: of all possible splits, which one best separates the classes?

To make "best" precise you need a measure of how mixed a group is. Two are used.

Gini impurity

where $p_k$ is the proportion of class $k$ in the node. It is the probability of misclassifying a randomly chosen item if you labelled it by drawing randomly from the node's class distribution.

Entropy

Entropy measures the same thing in bits of surprise, peaking at 1.0 for a 50/50 binary split rather than 0.5. In practice the two produce nearly identical trees; Gini is the default because it avoids computing logarithms.

A split, worked through

A node holds 100 applicants: 40 defaulted, 60 repaid. Its Gini is $1 - 0.4^2 - 0.6^2 = 0.48$.

Candidate split: debt_to_income > 45%.

Weighted impurity after the split: $\frac{40}{100}(0.375) + \frac{60}{100}(0.278) = 0.150 + 0.167 = 0.317$.

Gain = 0.48 − 0.317 = 0.163.

Now a competing split, owns_home = yes, which happens to divide 50/50 with 20 defaults on each side. Both branches have Gini 0.48, weighted impurity is 0.48, and the gain is zero — the split told us nothing.

The algorithm evaluates every feature and, for numeric features, every threshold between adjacent observed values, computes this gain for each, takes the winner, and recurses into both branches. It is greedy: it takes the best split now without considering whether a slightly worse split might enable two excellent ones below. That greediness means trees are not guaranteed optimal, and finding the truly optimal tree is computationally intractable.

Why an unrestricted tree is useless

Left alone, the algorithm keeps splitting until every leaf is pure. With enough features it will always succeed — in the worst case producing one leaf per training row.

That tree has 100% training accuracy and has learned nothing. It has built a lookup table. A leaf containing a single applicant says "people exactly like this one default", based on a sample of one.

Worse, trees are unstable. Change a handful of training rows and the top split may change; every split below it is then computed on different data, and the entire tree below reorganises. Two trees grown on 95%-overlapping data can look completely different and disagree on many predictions. That is high variance in its purest form.

min_samples_leaf is the one to reach for first. It directly forbids the "leaf of one" failure, and it does so in a way you can explain: no prediction is made from fewer than 20 examples.

A single decision tree is best understood as an explanation tool, not a prediction tool. Constrained to depth 4 it produces a diagram a compliance officer can read. Left unconstrained it produces a memorised training set.

Random forests: many bad trees make one good model

Averaging independent estimates reduces their variance. Average $n$ predictions each with variance $\sigma^2$ and you get variance $\sigma^2/n$ — as long as they are independent.

A random forest exploits this by growing hundreds of deep, overfitted trees and averaging them. Each tree individually is high-variance and low-bias. The average keeps the low bias and sheds most of the variance.

Two sources of randomness make the trees different enough for averaging to help:

Bootstrap sampling (bagging). Each tree is trained on a sample drawn with replacement from the training data, the same size as the original. Because of replacement, each sample contains about 63% of the unique rows, with some appearing multiple times. Different trees see different data.

Random feature subsets. At every split, each tree considers only a random subset of features — typically $\sqrt{p}$ for classification. This is the less obvious idea and the more important one. Without it, if one feature is strongly predictive, every tree splits on it first and the trees end up highly correlated, which destroys the benefit of averaging. Forcing trees to sometimes ignore the best feature makes each tree slightly worse and the ensemble substantially better.

Out-of-bag scoring, for free

Each tree omits about 37% of rows. For any given row, roughly a third of the trees never saw it — so you can predict that row using only those trees and get an honest held-out estimate without a separate validation set.

1from sklearn.ensemble import RandomForestClassifier23rf = RandomForestClassifier(4    n_estimators=500,          # more is better until it plateaus; never overfits5    max_features="sqrt",       # the decorrelation knob6    min_samples_leaf=2,7    oob_score=True,8    class_weight="balanced_subsample",9    n_jobs=-1,10    random_state=42,11).fit(X_train, y_train)1213print("OOB score:", round(rf.oob_score_, 4))

An important property: increasing n_estimators cannot cause overfitting. More trees means a more stable average, and performance flattens rather than degrading. The only cost is time and memory. This is unlike almost every other hyperparameter and makes forests unusually forgiving.

Feature importance, and the trap in it

Forests report which features mattered, and the default measure is misleading in a specific way.

Impurity-based importance (rf.feature_importances_) sums the impurity reduction each feature achieved. It is fast and computed during training. It is also biased towards high-cardinality features: a column with many distinct values offers more possible split points, so it wins splits by chance more often. Give a forest a random ID column with 10,000 unique values and it may rank among the top features.

Permutation importance measures what you actually care about — how much performance drops when a feature is scrambled:

1from sklearn.inspection import permutation_importance2import pandas as pd34result = permutation_importance(rf, X_test, y_test,5                                n_repeats=20, random_state=42, n_jobs=-1)6print(pd.Series(result.importances_mean, index=X_test.columns)7      .sort_values(ascending=False))

It is slower but computed on held-out data and directly interpretable: "shuffling this column costs 0.043 of accuracy". Both measures share one weakness — with two correlated features, either can substitute for the other, so both appear unimportant when the pair is jointly essential.

K-nearest neighbours: skip the model entirely

Trees and forests learn rules. KNN learns nothing at all.

To classify a new point: find the $k$ closest training points, and let them vote. That is the entire algorithm. "Training" consists of storing the dataset.

This makes it a lazy learner — training is instant, prediction is expensive, which is the reverse of every other algorithm here. With 1 million stored points, each prediction requires computing 1 million distances.

Distance, and the mistake that ruins it

Standard choice is Euclidean:

and here is the failure mode, with numbers. Two customers:

Total squared distance: 4,001,105. The income term contributes 99.97% of it. A 33-year age gap and a fourfold difference in product holdings are, as far as the algorithm is concerned, noise. KNN has silently become a one-feature model.

Standardise and the picture inverts: in standard-deviation units the income gap might be 0.08 while the age gap is 1.7. Feature scaling is not a refinement for KNN; without it the algorithm does not work.

1from sklearn.pipeline import make_pipeline2from sklearn.preprocessing import StandardScaler3from sklearn.neighbors import KNeighborsClassifier45knn = make_pipeline(6    StandardScaler(),7    KNeighborsClassifier(n_neighbors=15, weights="distance"),8).fit(X_train, y_train)

weights="distance" makes nearer neighbours count more, which usually helps and reduces sensitivity to the exact choice of $k$.

Choosing k

Use an odd $k$ for binary problems to avoid ties, and choose it by cross-validation rather than folklore.

The curse of dimensionality

KNN degrades badly as features multiply, and the reason is worth seeing concretely.

Points uniformly scattered in a unit hypercube. To capture 1% of them, how wide must a small cube be along each side?

In 100 dimensions, your "nearest neighbours" span 95% of the range of every feature. They are not near you in any meaningful sense. Simultaneously, the distances to the nearest and furthest points converge, so the ranking that KNN depends on becomes noise.

Practically: KNN is strong up to roughly 10–20 informative features and unreliable well beyond that unless you reduce dimensions first.

Choosing between them

The "cannot extrapolate" row applies to all three and matters. A tree predicts the average of a leaf; no leaf can contain a value outside the training range. Train on houses up to £800,000 and the model will never predict £1.2m, no matter how large the inputs. Linear models extrapolate — often badly, but they do it. Tree-based models simply flatten out.

Where the boundaries fall

  Logistic regression        Decision tree            KNN       \                    ┌──────┐              .-~-.        \                   │      │             (  o  )     A   \   B          A   │  B   │          A   `-~-'   B          \                 └──────┘   one straight cut    axis-aligned boxes    follows the data

Trees can only cut parallel to the axes. A genuinely diagonal boundary — "approve if income minus debt exceeds £20,000" — has to be approximated by a staircase of many splits, which is why trees sometimes underperform a linear model on problems a linear model suits perfectly.

Comparing them properly

1import pandas as pd2from sklearn.model_selection import cross_val_score, StratifiedKFold3from sklearn.tree import DecisionTreeClassifier45cv = StratifiedKFold(5, shuffle=True, random_state=42)67candidates = {8    "tree (depth 4)": DecisionTreeClassifier(max_depth=4, min_samples_leaf=20,9                                             random_state=42),10    "tree (unlimited)": DecisionTreeClassifier(random_state=42),11    "forest": RandomForestClassifier(n_estimators=500, max_features="sqrt",12                                     min_samples_leaf=2, n_jobs=-1,13                                     random_state=42),14    "knn (k=15)": make_pipeline(StandardScaler(),15                                KNeighborsClassifier(15, weights="distance")),16}1718for name, clf in candidates.items():19    s = cross_val_score(clf, X_train, y_train, cv=cv, scoring="roc_auc")20    print(f"{name:20s} AUC {s.mean():.3f} +/- {s.std():.3f}")

A representative result on tabular customer data:

The forest row is the interesting one. Its training AUC of 0.999 looks identical to the overfitted single tree — and yet it generalises far better. Training-set performance tells you nothing about a bagged ensemble, because overfitting each component is the design.

What this means when you build something

On tabular data, start with a random forest with 500 trees and default settings. It requires no scaling, no encoding decisions for numeric data, handles interactions for free, tolerates irrelevant features, and is nearly impossible to break through bad hyperparameters. As a first serious model it is difficult to beat with the same amount of effort.

Fit a depth-3 or depth-4 tree alongside it, not for accuracy but for the picture. Printing that tree tells you which two or three features carry the decision and where the thresholds fall, and it is the artefact you show to a domain expert who will immediately tell you whether the splits make sense — or whether that suspiciously powerful feature is leaking the answer.

Reach for KNN when your feature count is modest and locality is genuinely meaningful: recommendation by similarity, or a problem where the useful output is "here are the fifteen most similar past cases" rather than a probability. And when you do, put a scaler in the pipeline before anything else. An unscaled KNN is not a weaker model; it is a model measuring distance in whichever unit happens to have the biggest numbers.