Grow decision trees with Gini impurity and combine many of them into a random forest.
Why this matters
Linear models draw straight boundaries. Real data often has thresholds and interactions: a loan is risky if income is low and debt is high; a machine fails above a certain temperature. Decision trees capture these patterns naturally, and random forests, which average many trees, are one of the most reliable models for tabular data. They need little preprocessing, handle mixed feature types, and are a strong default when you need a good model fast.
How a decision tree predicts
A tree is a flowchart of yes/no questions about features:
income <= 42,000 ?
├── yes: debt_ratio <= 0.35 ?
│ ├── yes: predict "repaid"
│ └── no: predict "default"
└── no: predict "repaid"
Each leaf predicts the majority class of the training rows that ended up there (or their mean, for regression trees).
How a tree is grown
Training is greedy. At each node, the algorithm tries every feature and every candidate threshold, and picks the split that makes the two child groups as pure as possible. Purity is usually measured with Gini impurity:
gini = 1 - sum over classes of p_k^2
A pure node (all one class) has gini 0. A 50/50 node of two classes has gini 1 - (0.5^2 + 0.5^2) = 0.5.
Worked example: choosing a split
Ten rows, labels [0,0,0,0,1,1,1,1,1,1] sorted by feature x. The parent gini is 1 - (0.4^2 + 0.6^2) = 0.48.
Candidate split after the 4th row (left = four 0s, right = six 1s):
left gini = 0, right gini = 0
weighted = (4/10)*0 + (6/10)*0 = 0 -> perfect split
Candidate split after the 2nd row (left = two 0s, right = two 0s and six 1s):
right gini = 1 - (0.25^2 + 0.75^2) = 0.375
weighted = (2/10)*0 + (8/10)*0.375 = 0.30
The first split wins. Candidate thresholds are the midpoints between consecutive sorted unique values. The tree then repeats the search inside each child until it reaches a stopping rule.
Overfitting and depth
Left alone, a tree keeps splitting until every leaf is pure, which memorises the training data, noise included. You control this with:
max_depth: the maximum number of questions from root to leaf.min_samples_leaf: the smallest allowed leaf, such as 20 rows.
A single deep tree has high variance: change a few training rows and the tree can look completely different.
Random forests: many trees, one vote
A random forest reduces that variance by averaging many different trees:
- Bootstrap: each tree trains on a random sample of rows drawn with replacement (the same size as the training set, so about 63% of distinct rows appear).
- Random features: at each split, the tree may only consider a random subset of features (often the square root of the feature count). This stops every tree from splitting on the same strong feature first.
- Vote: for classification, each tree predicts and the majority wins (or the probabilities are averaged).
Individual trees are noisy, but their errors are partly independent, so the average is much more stable. Rows left out of a tree's bootstrap sample (out-of-bag rows) give a free validation estimate.
In scikit-learn
from sklearn.ensemble import RandomForestClassifier
forest = RandomForestClassifier(
n_estimators=300, max_depth=None, min_samples_leaf=2,
max_features="sqrt", oob_score=True, random_state=0)
forest.fit(X_train, y_train)
print(forest.oob_score_) # out-of-bag accuracy
print(forest.feature_importances_) # average impurity decrease per feature
Trees do not need feature scaling, because a threshold on income works the same in dollars or thousands. Impurity-based feature importances are biased toward features with many unique values; permutation importance (sklearn.inspection.permutation_importance) is a more trustworthy check.
Boosting, briefly
Gradient boosting (XGBoost, LightGBM, HistGradientBoostingClassifier) also combines trees, but builds them one after another, each fixing the previous ones' errors. It often wins on tabular benchmarks but needs more tuning. Random forests are the easier, safer first ensemble.
Common mistakes
- Growing one deep tree and trusting its training accuracy. It will be close to 100% and meaningless.
- Too few trees. Results vary with the seed; more trees never overfit, they only cost time.
- Reading feature importance as cause.
- Ordinal-encoding categories without thinking. Trees can split on arbitrary integer codes, but a meaningless order can need extra splits (see Lesson 10).
Quick recap
- A tree asks greedy yes/no questions that minimise weighted Gini impurity.
- Depth limits control overfitting; a single tree is high variance.
- A random forest = bootstrap samples + random feature subsets + majority vote.
- Start tabular problems with a logistic regression baseline and a random forest.
Try it
On the Do tab, write Gini impurity, the best-threshold search and the majority vote, then train a small random forest from scratch.