Decision Trees and Random Forests
How a decision tree picks its splits using Gini impurity (with the arithmetic done by hand), why a single deep tree overfits, and how a random forest fixes that by averaging many different trees.
A decision tree classifies data with a sequence of yes/no questions on features, choosing each split to reduce impurity such as Gini the most. A random forest trains many trees on bootstrap samples with random feature subsets and takes a majority vote. Interviewers expect the reason it works: averaging diverse trees cuts the high variance of one deep tree.
A decision tree classifies data by asking a sequence of yes/no questions on features, choosing each question to make the groups as pure as possible. A single deep tree overfits. A random forest trains many trees on random samples of rows and features and takes a vote, which cuts variance and is usually far more accurate.
- Gini impurity is 1 minus the sum of squared class proportions; a pure group scores 0 and a 50/50 two-class group scores the maximum of 0.5.
- Splitting the labels [0, 0, 0, 1, 1, 0] into [0, 0, 0] and [1, 1, 0] lowers weighted Gini impurity from 0.444 to 0.222, a gain of 0.222.
- On scikit-learn's wine dataset with a 70/30 split, an unlimited decision tree scored 1.0 on training data and 0.944 on test data, a sign of memorisation.
- A random forest of 200 trees classified all 54 wine test samples correctly on the same split, though one small split is weak evidence.
- Bagging trains models in parallel on resamples and reduces variance, while boosting trains them in sequence on earlier errors and reduces bias.
- Decision trees need no feature scaling, because their splits depend only on the order of the feature values.
01A tree is a set of questions
A decision tree is a flowchart learned from data. To classify a wine, it might ask "is proline above 755?", then "is flavanoids above 2.1?", and end at a leaf that says "class 0". Trees handle numbers and categories, need no feature scaling, capture non-linear patterns and interactions, and the result is easy to read, which is why they are used so widely.
The learning question is: at each node, which feature and which threshold should we split on?
02Gini impurity: measuring a messy group
A common measure is Gini impurity: 1 minus the sum of the squared class proportions. For a group with 3 of class 0 and 2 of class 1, the proportions are 0.6 and 0.4, so Gini = 1 - (0.36 + 0.16) = 0.48. A pure group (all one class) is 0. A 50/50 two-class group is 0.5, the maximum.
See how a split helps. Take six samples labelled [0, 0, 0, 1, 1, 0]. The group is mixed, Gini 0.444. Split it into left [0, 0, 0] (Gini 0, pure) and right [1, 1, 0] (Gini 0.444). The weighted impurity after the split is 3/6 x 0 + 3/6 x 0.444 = 0.222. Impurity fell from 0.444 to 0.222, a gain of 0.222.
The algorithm tries every feature and every candidate threshold, keeps the split with the biggest gain, and repeats on each side until a stopping rule applies. This greedy search is fast, but it does not guarantee the best possible tree. An alternative measure is entropy, which behaves similarly in practice.
03A single tree overfits
Without limits, a tree keeps splitting until each leaf is pure, which means it memorises the training data, noise included. On the wine dataset from scikit-learn (178 samples, three classes), with a 70/30 split:
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
X, y = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)
for depth in (None, 2):
t = DecisionTreeClassifier(max_depth=depth, random_state=0).fit(Xtr, ytr)
print(depth, round(t.score(Xtr, ytr), 3), round(t.score(Xte, yte), 3))
# None 1.0 0.944
# 2 0.919 0.889The unlimited tree gets 100% on training data and 94.4% (51 of 54) on test data. Capping the depth at 2 lowers both numbers. On a dataset this clean the deep tree still wins, but the gap between 1.0 and 0.944 shows the memorisation. On noisier data the gap is larger and the shallow tree wins. Control it with max_depth, min_samples_leaf, or by pruning.
04Random forest: many trees, one vote
Individual deep trees are high-variance: change a few training rows and the tree can look completely different. A random forest turns that weakness into a strength.
It builds many trees, each trained on a bootstrap sample (rows drawn at random with replacement), and at every split each tree may only consider a random subset of the features. The randomness makes the trees different from each other, so their errors are partly independent. Predictions are combined by majority vote (or averaged for regression), and averaging many noisy but unbiased guesses gives a much steadier answer.
from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=200, random_state=0).fit(Xtr, ytr)
print(round(rf.score(Xtr, ytr), 3), round(rf.score(Xte, yte), 3)) # 1.0 1.0On this split the forest classified all 54 test samples correctly. One small split is weak evidence, since 54 rows is a small test, so confirm with cross-validation. Still, it shows the pattern: the forest matches the single tree's low bias and removes much of its variance.
Useful extras: the rows left out of each bootstrap sample give a free validation score (out-of-bag error), and feature_importances_ ranks features. Treat importances with caution, since they can favour high-cardinality features and split credit between correlated ones.
05Strengths, limits and neighbours
Forests need little tuning, handle mixed feature types, resist overfitting far better than one tree, and work well out of the box on tabular data. The costs: they are less interpretable than a single tree, larger and slower to predict than a linear model, and a tree-based model cannot extrapolate beyond the range of target values it saw. On text or images, other methods usually win.
Gradient-boosted trees (XGBoost, LightGBM, CatBoost) are the other big family. They build trees one after another, each correcting the errors of the previous ones, and often beat random forests on tabular benchmarks with more tuning. Bagging reduces variance. Boosting reduces bias.
06Common interview questions
Q: How does a decision tree choose a split?
A: It tries features and thresholds and picks the one that most reduces impurity (Gini or entropy), then repeats recursively.
Q: Why does a deep tree overfit?
A: It keeps splitting until the leaves are pure, memorising noise. Its predictions swing with small changes in the data.
Q: How does a random forest reduce overfitting?
A: Bootstrap sampling and random feature subsets make the trees diverse, and voting averages out their individual errors.
Q: Bagging versus boosting?
A: Bagging trains models in parallel on resamples and averages them, reducing variance. Boosting trains sequentially, each model fixing earlier errors, reducing bias.
Q: Do trees need feature scaling?
A: No. Splits depend only on the order of the values.
Q: What is out-of-bag error?
A: Each tree is tested on the rows its bootstrap sample left out. Averaging this over trees gives a validation estimate without a separate set.