The idea
Judge a model only on data it didn’t learn from. In k-fold cross-validation the rows are dealt into k folds; each fold is held out once while the others train the model, so every row is predicted exactly once, by a model that never saw it. Score with AUC, the chance a random “yes” scores above a random “no” (0.5 is a coin flip), which accuracy can’t match when one class is rare.
A decision tree asks one question at a time, choosing the split that leaves the two sides purest. Grown deep, it memorises noise: a big gap between training and held-out scores is overfitting. A random forest grows many deep trees, each on a bootstrap sample and shown a random few columns at each split, then averages them. k-nearest neighbours predicts from the most similar rows, so columns must be standardised first.
Permutation importance shuffles one column among the held-out rows and measures how far AUC falls. It shows what the model uses, not what matters in the world: two correlated columns share the credit.
The formula
G = 1 − Σk pk2, ΔG = Gparent − nLnGL − nRnGR, Var(forest) = ρσ2 + (1 − ρ)σ2B
- G
- Gini impurity of a node: 0 when every row is the same class, 0.5 at most for two classes
- pk
- share of the node’s rows in class k
- ΔG
- how much a split lowers impurity; the tree takes the split with the largest
- B, ρ, σ
- number of trees, correlation between their predictions, and one tree’s spread; averaging only removes the (1 − ρ) part
A worked example
A tree is choosing its first question for 100 customers, 30 of whom churned. It can split on tenure ≤ 12 months (40 customers, 20 churned; and 60 with 10 churned) or on fee ≤ $30 (50 with 18 churned; 50 with 12).
- Impurity before splitting: 1 − 0.30² − 0.70² = 0.420.
- Tenure split: left 1 − 0.5² − 0.5² = 0.500; right 1 − (1/6)² − (5/6)² = 0.278. Weighted: 0.4 × 0.500 + 0.6 × 0.278 = 0.367, a fall of 0.053.
- Fee split: left 1 − 0.36² − 0.64² = 0.461; right 1 − 0.24² − 0.76² = 0.365. Weighted: 0.413, a fall of only 0.007.
- The tree splits on tenure, then repeats the search inside each side until it reaches its depth limit or its minimum leaf size.
Tenure separates churners about 7 times as well as fee here. The same greedy search, run to full depth, is why a single tree overfits and why forests average many of them.
Try it
Why a forest averages different trees
- With unlimited trees (the floor)
- 55%
- Trees to get within 5% of the floor
- 23
With 100 trees the forest is already near its floor; more trees cost time and buy little. Lowering the correlation would help more.
The common mistake
Choosing a model by its score on its own training rows
A deep tree can score an AUC of 0.95 on the rows it was grown on and 0.68 on held-out folds, while a logistic regression scores 0.76 held out. Picking the tree because of its 0.95 picks the worse model: the 0.27 gap is noise it memorised. Compare models only on held-out scores, and shrink an overfitting tree’s depth or raise its minimum leaf size.
Remember
- Cross-validation predicts every row once, from a model that never saw it. Compare models on those held-out scores.
- Forests beat single trees by averaging trees made different by bootstrap samples and random columns. k-NN needs standardised columns.
- Permutation importance shows what a model leans on; correlated columns share the credit.
Check yourself
Three questions from the Learn room’s bank. Your answers update your mastery of this skill, the same as in Practise.
Use it on real numbers
Open Compare models, in Business analytics › Supervised learning and try the idea on your own numbers.