Definition
A random forest classifier is a collection of decision trees. Each tree is grown on a bootstrap sample of the rows (drawn with replacement). At every split it may only look at a random subset of of the features. To classify , the forest averages the trees' class-probability estimates and outputs the most probable class. Breiman (2001) called this soft voting.
At a glance
- Task
- Classification (binary or multi-class). For the regression version see Random forest regression.
- Input → output
- → class probabilities and the label
- Learns
- deep, unpruned classification trees. Each leaf stores the class proportions of the bootstrap rows that land in it.
- Training cost
- about for balanced trees. The trees are independent, so training runs fully in parallel.
- Prediction cost
- comparisons per point
- Key hyperparameters
n_estimators,max_features(default ),max_depth/min_samples_leaf,max_samples,class_weight- Assumptions
- None about distributions. The boundaries are unions of axis-aligned boxes. The model works best when many features each carry some signal.
The problem
A single fully grown tree (see Decision trees) has low bias and high variance. It fits the training set exactly. But change a few rows and the root split can change, and the whole tree below it changes too. The tree's probabilities are a second problem. A pure leaf says , so a fully grown tree outputs only hard 0/1 confidences. One confident mistake makes the log-loss infinite.
Concretely, on the 569-row breast-cancer dataset (398 rows for training, 171 for testing), one fully grown tree scores 90.6% test accuracy. A forest of 100 trees with scores 95.3%. Test log-loss drops from 3.23 for the single tree to 0.33. We want to keep the trees' flexibility and remove their instability.
The idea
Averaging many noisy estimates cancels their noise, but only the part of the noise they do not share. If you grew 100 trees on the same data you would get 100 copies of one tree, and averaging would do nothing. So the forest injects two kinds of randomness to make the trees disagree:
- 1Bagging (rows). Each tree sees a bootstrap sample: rows drawn with replacement. Some rows appear two or three times and about a third are missing. Each tree therefore overfits a different version of the data.
- 2Feature subsampling (columns). At every split the tree may only choose among randomly drawn features. A dominant feature then cannot sit at the top of every tree. Other features get their turn, and the trees' errors become less correlated.
- 3Vote. Each tree reports the class proportions in the leaf falls into. The forest averages these. The average is a smoother, better-calibrated probability than any single tree's 0/1 answer.
Vocabulary
- Bootstrap sample
- indices drawn uniformly with replacement from . A row's multiplicity is how many times it was drawn: 0, 1, 2, …
- In-bag / out-of-bag (OOB)
- For one tree, rows with multiplicity ≥ 1 are in-bag (used to grow it). Rows with multiplicity 0 are out-of-bag: the tree never saw them.
- OOB estimate
- Score each training row using only the trees for which it was out-of-bag, then measure accuracy. This gives a validation estimate without a held-out split.
- max_features (m, mtry)
- How many features are drawn at random, afresh at each node, as split candidates. is plain bagging. The classification default is .
- Soft vote
- Average the trees' probability vectors and take the argmax. scikit-learn does this.
- Hard vote
- Each tree casts one vote for its predicted class and the majority wins. This is Breiman's original formulation.
- Strength s
- How strongly the forest favours the correct class on average: the expected margin (below).
- Correlation ρ̄
- How similar two trees' errors are. Low correlation means averaging cancels more of the error.
The math
Leaf probabilities. Let tree have bootstrap multiplicities . Let be the leaf that lands in. The tree's probability for class is the weighted share of class in that leaf:
- number of times row was drawn into tree 's bootstrap sample (0 = out-of-bag)
- the leaf of tree that falls into
- 1 if row has class , else 0
Each tree is grown greedily, exactly as in Decision trees. The only difference is that the candidate features at each node are restricted to a random subset with . A node picks the feature and threshold that minimise the weighted Gini impurity , where and every count includes the multiplicities.
- forest probability of class c (soft vote)
- number of trees
- predicted label
The hard vote instead counts . The two rules usually agree. They differ when a minority of trees is very sure and the majority is only mildly sure. The worked example below is one such case.
Why averaging probabilities helps log-loss
For a point with true class , the log-loss of a probability is . The function is convex, so by Jensen's inequality the loss of the average is at most the average loss:
- probability tree t gives the true class
- per-example cross-entropy (log-loss)
The inequality is strict whenever the trees disagree. If a single tree is confidently wrong (), its own loss is infinite. Inside an average it costs only a finite amount, as long as some other tree gives the true class positive probability. This is why a forest's probabilities are usable even though every one of its trees is a 0/1 overfitter.
Why decorrelation matters more than T
Fix a point and treat each tree's output as a random variable over the bootstrap and feature draws. Each has variance , and each pair has correlation . The variance of their mean follows by expanding the square:
- variance of one tree's output at x
- correlation between two trees' outputs
Adding trees shrinks only the second term. The floor can be lowered only by making the trees less alike, and that is the job of max_features. The regression article (Random forest regression) works through this formula in detail with squared error. For classification, Breiman proved a bound stated in terms of margins instead.
- the random draws (bootstrap + feature subsets) that define one tree
- class predicted by a tree built with draws Θ
- margin: share of trees voting for the right class minus share for the best wrong class. mg > 0 means the forest is correct at x.
- strength: the average margin
- generalisation error of the infinite forest (T → ∞)
- mean correlation between the trees' raw margins
The bound says you want strong trees (large ) that are uncorrelated (small ), and trades one against the other. A larger lets each node use its best feature, so each tree is more accurate and rises. But all trees then pick the same top features, so rises too. With the trees are weak but nearly independent. The table in Tuning measures this trade-off on real data.
Out-of-bag rows. A given row is missed by one draw with probability , so it is missed by all draws with probability . With this is , or rows per tree on average. Each row is therefore out-of-bag for roughly a third of the trees, and those trees give an honest vote on it:
- the trees that never saw row
- OOB probability; the OOB accuracy is the share of rows where its argmax equals yᵢ
What each hyperparameter does to the formulas
- T (n_estimators)
- Shrinks only and the Monte-Carlo noise in . Error falls and then plateaus, and it never rises. More trees cost time, not accuracy.
- m (max_features)
- Raising increases strength and correlation together. Smaller also makes each split cheaper: instead of .
- Depth / min_samples_leaf
- Deeper trees have lower bias and higher , which the averaging absorbs. Larger leaves give each tree smoother, less extreme , at some cost in bias.
- max_samples
- Smaller bootstrap samples make the trees more different (lower ) and cheaper to grow, but individually weaker.
- class_weight
- Multiplies each row's by a class weight inside the Gini counts and leaf proportions. This shifts the leaf probabilities toward rare classes.
Worked example: will the student pass?
Twelve students, two features: study hours and sleep hours . Seven passed. We grow a tiny forest by hand: T = 3 stumps (depth-1 trees), each with random feature. Real forests grow deep trees. Stumps keep the hand calculation short, and the figure below lets you switch to full depth. The new student is : 5 hours of study and 6.5 hours of sleep.
| Row | Study x₁ (h) | Sleep x₂ (h) | Result |
|---|---|---|---|
| 1 | 1 | 5 | fail |
| 2 | 2 | 7.5 | fail |
| 3 | 3 | 4.5 | fail |
| 4 | 3.5 | 8 | pass |
| 5 | 4 | 6 | pass |
| 6 | 5 | 5 | fail |
| 7 | 5.5 | 7 | pass |
| 8 | 6 | 8.5 | pass |
| 9 | 6.5 | 4.5 | fail |
| 10 | 7 | 6 | pass |
| 11 | 8 | 5.5 | pass |
| 12 | 9 | 7.5 | pass |
| Tree | Bootstrap rows (12 draws) | Out-of-bag | Feature drawn | Class counts |
|---|---|---|---|---|
| 1 | 1, 2, 2, 3, 6, 6, 7, 9, 10, 12, 12, 12 | 4, 5, 8, 11 | sleep x₂ | 7 fail / 5 pass |
| 2 | 2, 2, 2, 4, 5, 5, 6, 7, 8, 8, 9, 11 | 1, 3, 10, 12 | sleep x₂ | 5 fail / 7 pass |
| 3 | 3, 3, 3, 3, 6, 6, 7, 7, 7, 8, 9, 11 | 1, 2, 4, 5, 10, 12 | study x₁ | 7 fail / 5 pass |
Tree 1, by hand
- 1Parent Gini with multiplicities: 7 fail, 5 pass out of 12, so .
- 2Distinct in-bag sleep values: 4.5, 5, 6, 7, 7.5. The candidate thresholds are the midpoints 4.75, 5.5, 6.5 and 7.25.
- 3 sends rows 1, 3, 6, 6, 9 left: 5 fail / 0 pass, a pure node with . Rows 2, 2, 7, 10, 12, 12, 12 go right: 2 fail / 5 pass, with .
- 4Weighted Gini . This is the lowest of the four candidates (table below), a decrease of .
- 5Leaves: on the left and on the right. The query has , so tree 1 says P(pass) = 0.714.
| Threshold | Left | Right | G left | G right | Weighted Gini |
|---|---|---|---|---|---|
| x₂ ≤ 4.75 | 2/0 | 5/5 | 0.000 | 0.500 | 0.417 |
| x₂ ≤ 5.5 | 5/0 | 2/5 | 0.000 | 0.408 | 0.238 |
| x₂ ≤ 6.5 | 5/1 | 2/4 | 0.278 | 0.444 | 0.361 |
| x₂ ≤ 7.25 | 5/2 | 2/3 | 0.408 | 0.480 | 0.438 |
Trees 2 and 3, the vote, and OOB
- 1Tree 2 (sleep, parent 5 fail / 7 pass, ). Its best threshold is : left 2/0, right 3/7, weighted Gini . The runner-up scores . Since has , it goes right: P(pass) = 7/10 = 0.700.
- 2Tree 3 may only use study hours. Its best threshold is : left 6 fail / 0 pass (row 3 four times, row 6 twice), right 1/5, weighted Gini . Since has , it goes left: P(pass) = 0.
- 3Hard vote: trees 1 and 2 say pass and tree 3 says fail, so the majority says pass (2–1).
- 4Soft vote: , so the forest says fail. Tree 3 is certain, the other two are only mildly sure, and certainty outweighs the head-count.
- 5OOB. Score each row only with the trees that did not see it. Row 4 is OOB for trees 1 and 3: , so the prediction is fail, which is wrong. Row 10 is OOB for trees 2 and 3: , pass, which is correct. Rows 6, 7 and 9 were in every bag and get no OOB vote. Over the 9 rows that do, 6 are correct: OOB accuracy 6/9 = 67%. The misses are rows 4, 5 and 11.
Three stumps are not really a forest. The soft vote at is still swinging from tree to tree. With the same draws continued to 100 stumps, settles at 0.723 (pass) and OOB accuracy reaches 11/12. A scikit-learn forest of 500 fully grown trees on these 12 rows gives 0.868 (see In code). The final answer is driven by the many trees, not by any one of them.
See it work
Things to try: set max_depth to full and step through trees 1–5. Each tree's regions are jagged and different, while the forest's colouring changes gradually. Then switch to hard voting. The colouring becomes the share of trees voting pass, and at T = 3 the colour at ★ flips to pass.
- 1for t = 1 … T:
- 2 S ← n draws with replacement
- 3 grow tree on S; each split
- 4 tries a random feature subset
- 5predict: majority vote of trees
50 training points, two noisy interleaved moons. One fully grown tree fits them exactly but scores only 79.2% on 600 held-out points.
The algorithm, step by step
fit(X, y, T, m)
- 1For (in parallel): draw row indices with replacement and record the multiplicities . Rows with are this tree's OOB set.
- 2Grow a tree on the weighted rows. At each node, draw features without replacement. For each, scan the sorted values and pick the threshold with the lowest weighted Gini (or entropy). Split on the best (feature, threshold) pair.
- 3Stop a node when it is pure or hits
max_depth/min_samples_leaf. The default is to grow until pure, with no pruning. Store the leaf's class proportions. - 4OOB (optional): for every row , average over the trees in . Compare the argmax with to get the OOB accuracy.
- 5predict_proba(x): route down every tree, average the leaf proportions, and take the argmax.
Complexity
- Training
- One node costs for sorting. Summed over a balanced tree's levels this is per tree, times . Trees are independent, so the wall-clock time divides by the number of cores.
- Prediction
- , roughly for balanced trees
- Memory
- Fully grown trees have up to leaves each, so the model size is nodes. Large forests can take gigabytes on big datasets.
Tuning and variants
Real data shows the strength–correlation trade-off directly. Below: 500 trees on the breast-cancer data (; 398 training rows, 171 test rows). Tree accuracy is the mean test accuracy of the individual trees, a proxy for strength. is Breiman's raw-margin correlation, measured on the test set.
| max_features m | Tree accuracy | Correlation ρ̄ | Strength s | OOB accuracy | Test accuracy |
|---|---|---|---|---|---|
| 1 | 0.885 | 0.306 | 0.771 | 0.965 | 0.936 |
| 2 | 0.901 | 0.359 | 0.803 | 0.965 | 0.942 |
| 5 (√d) | 0.911 | 0.411 | 0.823 | 0.965 | 0.953 |
| 10 | 0.914 | 0.440 | 0.828 | 0.970 | 0.947 |
| 30 (bagging) | 0.915 | 0.484 | 0.830 | 0.960 | 0.930 |
| Trees T | 1 | 5 | 10 | 25 | 100 | 500 |
|---|---|---|---|---|---|---|
| Test accuracy | 0.889 | 0.942 | 0.936 | 0.936 | 0.953 | 0.953 |
| Test log-loss | 3.84 | 0.73 | 0.52 | 0.32 | 0.33 | 0.32 |
Practical tuning, in order of importance
- n_estimators
- Use as many as you can afford (200–1000). Plot OOB error against T and stop adding trees once it is flat. T is not a regularizer, so there is nothing to cross-validate.
- max_features
- Try or a few fractions. This is the hyperparameter that matters most. With many irrelevant features, raise so that a useful one is usually among the candidates: a given feature is available at a node with probability .
- min_samples_leaf / max_depth
- The default (grow until pure) is usually fine for accuracy. Raise
min_samples_leaf(e.g. 3–10) for smoother probabilities, smaller models and noisy labels. - class_weight
- Use
"balanced_subsample"for imbalanced classes. It reweights classes inside each bootstrap sample. - max_samples
- Sample a fraction of rows per tree (e.g. 0.3–0.7) on large datasets. This is faster and the trees are more diverse.
- criterion
giniorentropy(log-loss). They rarely differ, as with single trees.
Relatives
- Plain bagging
- : only the bootstrap provides randomness. It is the max_features = 2 setting in the figure.
- Extra Trees
- Also draws the split thresholds at random and usually skips the bootstrap, which makes it even less correlated and faster. See Extra Trees.
- Balanced random forest
- Each tree draws a bootstrap sample with equal class counts (imbalanced-learn's
BalancedRandomForestClassifier). - Boosting
- Builds trees sequentially, each one fitting the current errors. It reduces bias where forests reduce variance. See Gradient boosting and AdaBoost.
- Isolation forest
- Uses random trees for anomaly detection instead: anomalies are isolated in fewer splits.
In code
1import numpy as np23def gini(counts):4 n = counts.sum()5 return 0.0 if n == 0 else 1.0 - ((counts / n) ** 2).sum()67def best_split(X, y, w, features):8 """Lowest weighted Gini over the given features; w = bootstrap multiplicities."""9 best = (np.inf, None, None)10 for j in features:11 v = np.unique(X[w > 0, j])12 for t in (v[:-1] + v[1:]) / 2:13 L = X[:, j] <= t14 cl = np.bincount(y, w * L, minlength=2)15 cr = np.bincount(y, w * ~L, minlength=2)16 score = cl.sum() * gini(cl) + cr.sum() * gini(cr)17 if score < best[0] - 1e-12:18 best = (score, j, t)19 return best2021def grow(X, y, w, max_features, rng, max_depth=None, depth=0, features=None):22 counts = np.bincount(y, w, minlength=2)23 leaf = {"p": counts[1] / counts.sum()} # leaf stores P(class 1)24 if counts.min() == 0 or depth == max_depth:25 return leaf26 if features is None: # fresh random subset at every node27 usable = [j for j in rng.permutation(X.shape[1]) if np.unique(X[w > 0, j]).size > 1]28 features = usable[:max_features]29 _, j, t = best_split(X, y, w, features)30 if j is None:31 return leaf32 L = X[:, j] <= t33 return {"j": j, "t": t,34 "L": grow(X, y, w * L, max_features, rng, max_depth, depth + 1),35 "R": grow(X, y, w * ~L, max_features, rng, max_depth, depth + 1)}3637def proba(node, x):38 while "j" in node:39 node = node["L"] if x[node["j"]] <= node["t"] else node["R"]40 return node["p"]4142def fit_forest(X, y, T=100, max_features=1, max_depth=None, seed=0):43 rng, n = np.random.default_rng(seed), len(y)44 forest = []45 for _ in range(T):46 w = np.bincount(rng.integers(0, n, n), minlength=n).astype(float) # bootstrap47 forest.append((grow(X, y, w, max_features, rng, max_depth), w))48 return forest4950def predict_proba(forest, x): # soft vote51 return np.mean([proba(tree, x) for tree, _ in forest])5253def oob_accuracy(forest, X, y):54 right = seen = 055 for i in range(len(y)):56 ps = [proba(tree, X[i]) for tree, w in forest if w[i] == 0]57 if ps:58 seen += 159 right += (np.mean(ps) > 0.5) == y[i]60 return right / seen6162# ---- the worked example ----------------------------------------------------63X = np.array([[1, 5], [2, 7.5], [3, 4.5], [3.5, 8], [4, 6], [5, 5],64 [5.5, 7], [6, 8.5], [6.5, 4.5], [7, 6], [8, 5.5], [9, 7.5]])65y = np.array([0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]) # 1 = pass66q = np.array([5, 6.5])6768# Replay the article's three bootstrap draws and feature draws (stumps).69boots = [[1, 2, 1, 0, 0, 2, 1, 0, 1, 1, 0, 3],70 [0, 3, 0, 1, 2, 1, 1, 2, 1, 0, 1, 0],71 [0, 0, 4, 0, 0, 2, 3, 1, 1, 0, 1, 0]]72feats = [[1], [1], [0]] # sleep, sleep, study73three = [(grow(X, y, np.array(b, float), 1, None, max_depth=1, features=f), np.array(b))74 for b, f in zip(boots, feats)]75for k, (tree, _) in enumerate(three, 1):76 print(f"tree {k}: x{tree['j'] + 1} <= {tree['t']} P(pass | q) = {proba(tree, q):.3f}")77print("soft vote P(pass | q) =", round(predict_proba(three, q), 3))78print("hard vote: passes =", sum(proba(t, q) > 0.5 for t, _ in three), "of 3")79print("OOB accuracy (3 stumps) =", round(oob_accuracy(three, X, y), 3))8081# A real forest: 200 fully grown trees, one random feature per split.82rf = fit_forest(X, y, T=200, max_features=1, seed=0)83print("200 trees: P(pass | q) =", round(predict_proba(rf, q), 3),84 " OOB accuracy =", round(oob_accuracy(rf, X, y), 3))1import numpy as np2from sklearn.ensemble import RandomForestClassifier3from sklearn.tree import DecisionTreeClassifier45X = np.array([[1, 5], [2, 7.5], [3, 4.5], [3.5, 8], [4, 6], [5, 5],6 [5.5, 7], [6, 8.5], [6.5, 4.5], [7, 6], [8, 5.5], [9, 7.5]])7y = np.array([0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1])8q = np.array([[5, 6.5]])910# 1) The three hand-built stumps: bootstrap = sample weights, feature = one column.11boots = [[1, 2, 1, 0, 0, 2, 1, 0, 1, 1, 0, 3],12 [0, 3, 0, 1, 2, 1, 1, 2, 1, 0, 1, 0],13 [0, 0, 4, 0, 0, 2, 3, 1, 1, 0, 1, 0]]14ps = []15for w, j in zip(boots, [1, 1, 0]):16 stump = DecisionTreeClassifier(max_depth=1).fit(X[:, [j]], y, sample_weight=w)17 ps.append(stump.predict_proba(q[:, [j]])[0, 1])18 print(f"x{j + 1} <= {stump.tree_.threshold[0]} P(pass|q) = {ps[-1]:.3f}")19print("soft vote:", round(np.mean(ps), 3))2021# 2) The library forest.22rf = RandomForestClassifier(n_estimators=500, max_features=1, oob_score=True,23 random_state=0).fit(X, y)24print("P(fail, pass | q) =", rf.predict_proba(q).round(3))25print("OOB accuracy =", round(rf.oob_score_, 3))26print("impurity importances (study, sleep) =", rf.feature_importances_.round(3))Use when
- +Tabular classification where you want a strong model with almost no tuning. The defaults are usually within a point or two of the best.
- +You want a built-in validation estimate (OOB), robustness to outliers and monotone transforms, and no feature scaling.
- +Many weak or noisy features, including more features than rows (genomics).
- +Training must parallelize, or you need a dependable baseline before trying boosting.
Avoid when
- −You need the last percent of accuracy on tabular data: tuned gradient boosting (XGBoost, LightGBM, CatBoost) usually wins.
- −Tight latency or memory budgets: hundreds of deep trees are large and slow to evaluate.
- −You need calibrated probabilities out of the box: forest probabilities are pulled away from 0 and 1, so calibrate them (isotonic or Platt) first.
- −Very high-dimensional sparse data such as text, where linear models are faster and often better. Or a smooth or diagonal boundary that a linear model captures directly.
Where it's used
Remote sensing
Land-cover classification of satellite pixels from spectral bands. Random forests are a standard method here, valued for robustness and OOB error.
Genomics & medicine
Disease classification from thousands of gene-expression or SNP features with few patients, where the many-weak-features setting suits feature subsampling.
Fraud & credit risk
A strong first model on mixed tabular data, with class_weight for the rare positive class.
Bioacoustics & ecology
Species identification from audio or habitat features, plus permutation importances to see which variables drive the predictions.
Check yourself
Three trees give . What do soft and hard voting predict?
Check yourself
Tree outputs have pairwise correlation and variance . What is the variance of a 10-tree average, and the best any number of trees can do?
Check yourself
Going from max_features = √d to max_features = d (plain bagging) typically…
Check yourself
With n = 12 rows, what is the probability that a given row is out-of-bag for one tree?
Remember
- ✓A random forest grows deep trees on bootstrap samples, with a fresh random subset of max_features candidates at every split.
- ✓It predicts by averaging leaf class proportions (soft vote). By Jensen's inequality, averaged probabilities never have a higher log-loss than the trees' average log-loss.
- ✓Variance falls to . More trees never overfit, but only decorrelation (smaller ) lowers the floor.
- ✓Breiman's bound : max_features trades tree strength against tree correlation, and is a good default.
- ✓About of rows are out-of-bag for each tree, which gives a free validation estimate. Judge the forest by that or held-out data, never by training accuracy.