Random forests

Average many trees trained on bootstrap samples with random feature subsets, reducing variance.

18 min read1846 wordscore21 viewsupdated 2026-10-07

Definition

A random forest classifier is a collection of TT 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 mm of the dd features. To classify xx, 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
x∈Rdx\in\mathbb R^d → class probabilities p^(c∣x)=1T∑tpt(c∣x)\hat p(c\mid x)=\tfrac1T\sum_t p_t(c\mid x) and the label arg⁡max⁡cp^(c∣x)\arg\max_c \hat p(c\mid x)
Learns
TT deep, unpruned classification trees. Each leaf stores the class proportions of the bootstrap rows that land in it.
Training cost
about O(T⋅m⋅nlog⁡2n)O(T\cdot m\cdot n\log^2 n) for balanced trees. The trees are independent, so training runs fully in parallel.
Prediction cost
O(T⋅depth)O(T\cdot\text{depth}) comparisons per point
Key hyperparameters
n_estimators TT, max_features mm (default d\sqrt d), 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 P(class)=1P(\text{class})=1, 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 m=30→5m=\sqrt{30}\to5 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:

  1. 1Bagging (rows). Each tree sees a bootstrap sample: nn 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.
  2. 2Feature subsampling (columns). At every split the tree may only choose among m<dm<d 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.
  3. 3Vote. Each tree reports the class proportions in the leaf xx 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
nn indices drawn uniformly with replacement from {1,…,n}\{1,\dots,n\}. 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. m=dm=d is plain bagging. The classification default is ⌊d⌋\lfloor\sqrt d\rfloor.
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 tt have bootstrap multiplicities wtiw_{ti}. Let ℓt(x)\ell_t(x) be the leaf that xx lands in. The tree's probability for class cc is the weighted share of class cc in that leaf:

pt(c∣x)=∑i: xi∈ℓt(x)wti 1[yi=c]∑i: xi∈ℓt(x)wtip_t(c\mid x)=\frac{\sum_{i:\,x_i\in\ell_t(x)} w_{ti}\,\mathbb 1[y_i=c]}{\sum_{i:\,x_i\in\ell_t(x)} w_{ti}}
wtiw_{ti}
number of times row ii was drawn into tree tt's bootstrap sample (0 = out-of-bag)
ℓt(x)\ell_t(x)
the leaf of tree tt that xx falls into
1[yi=c]\mathbb 1[y_i=c]
1 if row ii has class cc, 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 F⊂{1..d}\mathcal F\subset\{1..d\} with ∣F∣=m|\mathcal F|=m. A node picks the feature j∈Fj\in\mathcal F and threshold τ\tau that minimise the weighted Gini impurity nLnG(L)+nRnG(R)\tfrac{n_L}{n}G(L)+\tfrac{n_R}{n}G(R), where G=1−∑cpc2G=1-\sum_c p_c^2 and every count includes the multiplicities.

p^(c∣x)=1T∑t=1Tpt(c∣x),y^(x)=arg⁡max⁡c p^(c∣x)\hat p(c\mid x)=\frac1T\sum_{t=1}^{T}p_t(c\mid x),\qquad \hat y(x)=\arg\max_c\ \hat p(c\mid x)
p^(c∣x)\hat p(c\mid x)
forest probability of class c (soft vote)
TT
number of trees
y^(x)\hat y(x)
predicted label

The hard vote instead counts Vc(x)=1T∑t1[arg⁡max⁡kpt(k∣x)=c]V_c(x)=\tfrac1T\sum_t\mathbb 1[\arg\max_k p_t(k\mid x)=c]. 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 yy, the log-loss of a probability pp is −log⁡p(y)-\log p(y). The function −log⁡-\log is convex, so by Jensen's inequality the loss of the average is at most the average loss:

−log⁡(1T∑tpt(y∣x)) ≤ 1T∑t(−log⁡pt(y∣x))-\log\Big(\frac1T\sum_t p_t(y\mid x)\Big)\ \le\ \frac1T\sum_t\big(-\log p_t(y\mid x)\big)
pt(y∣x)p_t(y\mid x)
probability tree t gives the true class
−log⁡-\log
per-example cross-entropy (log-loss)

The inequality is strict whenever the trees disagree. If a single tree is confidently wrong (pt(y)=0p_t(y)=0), 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 xx and treat each tree's output ht=pt(c∣x)h_t=p_t(c\mid x) as a random variable over the bootstrap and feature draws. Each has variance σ2\sigma^2, and each pair has correlation ρ\rho. The variance of their mean follows by expanding the square:

Var⁡(1T∑tht)=1T2(Tσ2⏟diagonal+T(T−1)ρσ2⏟off-diagonal)=ρσ2+1−ρT σ2\operatorname{Var}\Big(\frac1T\sum_t h_t\Big)=\frac1{T^2}\Big(\underbrace{T\sigma^2}_{\text{diagonal}}+\underbrace{T(T-1)\rho\sigma^2}_{\text{off-diagonal}}\Big)=\rho\sigma^2+\frac{1-\rho}{T}\,\sigma^2
σ2\sigma^2
variance of one tree's output at x
ρ\rho
correlation between two trees' outputs

Adding trees shrinks only the second term. The floor ρσ2\rho\sigma^2 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.

mg(x,y)=PΘ(h(x,Θ)=y)−max⁡j≠yPΘ(h(x,Θ)=j),s=Ex,y mg(x,y)\text{mg}(x,y)=P_\Theta\big(h(x,\Theta)=y\big)-\max_{j\ne y}P_\Theta\big(h(x,\Theta)=j\big),\qquad s=\mathbb E_{x,y}\,\text{mg}(x,y)
Θ\Theta
the random draws (bootstrap + feature subsets) that define one tree
h(x,Θ)h(x,\Theta)
class predicted by a tree built with draws Θ
mg\text{mg}
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.
ss
strength: the average margin
PE∗ ≤ ρˉ 1−s2s2PE^{*}\ \le\ \bar\rho\,\frac{1-s^2}{s^2}
PE∗PE^{*}
generalisation error of the infinite forest (T → ∞)
ρˉ\bar\rho
mean correlation between the trees' raw margins

The bound says you want strong trees (large ss) that are uncorrelated (small ρˉ\bar\rho), and mm trades one against the other. A larger mm lets each node use its best feature, so each tree is more accurate and ss rises. But all trees then pick the same top features, so ρˉ\bar\rho rises too. With m=1m=1 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 1−1n1-\tfrac1n, so it is missed by all nn draws with probability (1−1n)n→e−1≈0.368(1-\tfrac1n)^n\to e^{-1}\approx0.368. With n=12n=12 this is 0.3520.352, or 4.24.2 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:

p^oob(c∣xi)=1∣Oi∣∑t∈Oipt(c∣xi),Oi={t: wti=0}\hat p^{\text{oob}}(c\mid x_i)=\frac{1}{|O_i|}\sum_{t\in O_i}p_t(c\mid x_i),\qquad O_i=\{t:\ w_{ti}=0\}
OiO_i
the trees that never saw row ii
p^oob\hat p^{\text{oob}}
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 (1−ρ)σ2/T(1-\rho)\sigma^2/T and the Monte-Carlo noise in p^\hat p. Error falls and then plateaus, and it never rises. More trees cost time, not accuracy.
m (max_features)
Raising mm increases strength ss and correlation ρˉ\bar\rho together. Smaller mm also makes each split cheaper: O(m nlog⁡n)O(m\,n\log n) instead of O(d nlog⁡n)O(d\,n\log n).
Depth / min_samples_leaf
Deeper trees have lower bias and higher σ2\sigma^2, which the averaging absorbs. Larger leaves give each tree smoother, less extreme ptp_t, at some cost in bias.
max_samples
Smaller bootstrap samples make the trees more different (lower ρ\rho) and cheaper to grow, but individually weaker.
class_weight
Multiplies each row's wtiw_{ti} 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 x1x_1 and sleep hours x2x_2. Seven passed. We grow a tiny forest by hand: T = 3 stumps (depth-1 trees), each with m=1m=1 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 q=(5, 6.5)q=(5,\ 6.5): 5 hours of study and 6.5 hours of sleep.

RowStudy x₁ (h)Sleep x₂ (h)Result
115fail
227.5fail
334.5fail
43.58pass
546pass
655fail
75.57pass
868.5pass
96.54.5fail
1076pass
1185.5pass
1297.5pass
Training data. Highlighted: rows 6, 7 and 9, which happen to be in-bag for all three trees and so get no OOB vote.
TreeBootstrap rows (12 draws)Out-of-bagFeature drawnClass counts
11, 2, 2, 3, 6, 6, 7, 9, 10, 12, 12, 124, 5, 8, 11sleep x₂7 fail / 5 pass
22, 2, 2, 4, 5, 5, 6, 7, 8, 8, 9, 111, 3, 10, 12sleep x₂5 fail / 7 pass
33, 3, 3, 3, 6, 6, 7, 7, 7, 8, 9, 111, 2, 4, 5, 10, 12study x₁7 fail / 5 pass
The random draws for each tree: 12 row indices with replacement, and the one feature the root may use.

Tree 1, by hand

  1. 1Parent Gini with multiplicities: 7 fail, 5 pass out of 12, so G=1−(712)2−(512)2=0.486G=1-(\tfrac7{12})^2-(\tfrac5{12})^2=0.486.
  2. 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. 3x2≤5.5x_2\le5.5 sends rows 1, 3, 6, 6, 9 left: 5 fail / 0 pass, a pure node with GL=0G_L=0. Rows 2, 2, 7, 10, 12, 12, 12 go right: 2 fail / 5 pass, with GR=1−(27)2−(57)2=0.408G_R=1-(\tfrac27)^2-(\tfrac57)^2=0.408.
  4. 4Weighted Gini =512(0)+712(0.408)=0.238=\tfrac5{12}(0)+\tfrac7{12}(0.408)=0.238. This is the lowest of the four candidates (table below), a decrease of 0.486−0.238=0.2480.486-0.238=0.248.
  5. 5Leaves: P(pass)=0/5=0P(\text{pass})=0/5=0 on the left and 5/7=0.7145/7=0.714 on the right. The query has x2=6.5>5.5x_2=6.5>5.5, so tree 1 says P(pass) = 0.714.
ThresholdLeftRightG leftG rightWeighted Gini
x₂ ≤ 4.752/05/50.0000.5000.417
x₂ ≤ 5.55/02/50.0000.4080.238
x₂ ≤ 6.55/12/40.2780.4440.361
x₂ ≤ 7.255/22/30.4080.4800.438
Tree 1's candidate thresholds on sleep (counts are fail/pass, including repeats).

Trees 2 and 3, the vote, and OOB

  1. 1Tree 2 (sleep, parent 5 fail / 7 pass, G=0.486G=0.486). Its best threshold is x2≤5.25x_2\le5.25: left 2/0, right 3/7, weighted Gini 0.3500.350. The runner-up x2≤7.75x_2\le7.75 scores 0.3700.370. Since qq has x2=6.5x_2=6.5, it goes right: P(pass) = 7/10 = 0.700.
  2. 2Tree 3 may only use study hours. Its best threshold is x1≤5.25x_1\le5.25: left 6 fail / 0 pass (row 3 four times, row 6 twice), right 1/5, weighted Gini 0.1390.139. Since qq has x1=5≤5.25x_1=5\le5.25, it goes left: P(pass) = 0.
  3. 3Hard vote: trees 1 and 2 say pass and tree 3 says fail, so the majority says pass (2–1).
  4. 4Soft vote: p^(pass∣q)=13(0.714+0.700+0)=0.471<0.5\hat p(\text{pass}\mid q)=\tfrac13(0.714+0.700+0)=0.471<0.5, so the forest says fail. Tree 3 is certain, the other two are only mildly sure, and certainty outweighs the head-count.
  5. 5OOB. Score each row only with the trees that did not see it. Row 4 (3.5,8)(3.5,8) is OOB for trees 1 and 3: 12(0.714+0)=0.357\tfrac12(0.714+0)=0.357, so the prediction is fail, which is wrong. Row 10 (7,6)(7,6) is OOB for trees 2 and 3: 12(0.700+0.833)=0.767\tfrac12(0.700+0.833)=0.767, 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 qq is still swinging from tree to tree. With the same draws continued to 100 stumps, p^(pass∣q)\hat p(\text{pass}\mid q) 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

T = 3 · shade = mean P(pass) · pass fail0246810456789study hours x₁ →↑ sleep hours x₂123456789101112each tree's P(pass) at ★00.51123mean = 0.471forest says FAILas trees are added · OOB accuracy · P(pass) at ★00.511255075100number of trees T
max_depthmax_features
voteshowforest
trees T = 3
★ = (5, 6.5): P(pass) = 0.471, votes 2–1OOB acc 6/9 = 67%train acc 10/12 = 83%tree correlation ρ̄ 0.29
fig.The 12 students from the table; ★ is q = (5, 6.5). It opens on the hand-built forest: 3 stumps, max_features = 1. Two trees vote pass (dots at 0.714 and 0.700) and one votes fail (0), so the mean is 0.471 and the forest says FAIL, with OOB accuracy 6/9. Drag T to 100: the mint curve settles and P(pass) = 0.723, OOB 11/12. Press ▶ to inspect one tree: its split lines, bootstrap repeats (×k) and hollow out-of-bag rows. Switch max_features 1 → 2 (plain bagging) at T = 100 and the mean tree correlation ρ̄ rises from 0.41 to 0.52 for stumps (0.53 → 0.64 at full depth). Drag ★ anywhere, and compare soft and hard voting.

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.

▸ random forest · baggingstep 1/14
tree 1tree 2tree 3tree 4tree 5
trees 0out-of-bag —test acc (single tree) 79.2%
  1. 1for t = 1 … T:
  2. 2 S ← n draws with replacement
  3. 3 grow tree on S; each split
  4. 4 tries a random feature subset
  5. 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.

fig.The same algorithm on 50 noisy two-moon points: each tree sees a bootstrap sample and one random feature per split. Alone the trees are jagged; their vote is smooth — test accuracy 79% for one full tree, 92% for 25.

The algorithm, step by step

fit(X, y, T, m)

  1. 1For t=1…Tt=1\ldots T (in parallel): draw nn row indices with replacement and record the multiplicities wt⋅w_{t\cdot}. Rows with wti=0w_{ti}=0 are this tree's OOB set.
  2. 2Grow a tree on the weighted rows. At each node, draw mm 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.
  3. 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.
  4. 4OOB (optional): for every row ii, average pt(⋅∣xi)p_t(\cdot\mid x_i) over the trees in OiO_i. Compare the argmax with yiy_i to get the OOB accuracy.
  5. 5predict_proba(x): route xx down every tree, average the leaf proportions, and take the argmax.

Complexity

Training
One node costs O(m nnodelog⁡nnode)O(m\,n_{\text{node}}\log n_{\text{node}}) for sorting. Summed over a balanced tree's log⁡n\log n levels this is O(m nlog⁡2n)O(m\,n\log^2 n) per tree, times TT. Trees are independent, so the wall-clock time divides by the number of cores.
Prediction
O(T⋅depth)O(T\cdot\text{depth}), roughly O(Tlog⁡n)O(T\log n) for balanced trees
Memory
Fully grown trees have up to nn leaves each, so the model size is O(T n)O(T\,n) 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 (d=30d=30; 398 training rows, 171 test rows). Tree accuracy is the mean test accuracy of the individual trees, a proxy for strength. ρˉ\bar\rho is Breiman's raw-margin correlation, measured on the test set.

max_features mTree accuracyCorrelation ρ̄Strength sOOB accuracyTest accuracy
10.8850.3060.7710.9650.936
20.9010.3590.8030.9650.942
5 (√d)0.9110.4110.8230.9650.953
100.9140.4400.8280.9700.947
30 (bagging)0.9150.4840.8300.9600.930
Raising max_features makes every tree stronger but the trees more alike. Test accuracy peaks at m = 5 = ⌊√30⌋, the default. All differences here are within a few test rows.
Trees T151025100500
Test accuracy0.8890.9420.9360.9360.9530.953
Test log-loss3.840.730.520.320.330.32
Same data, max_features = √d, growing T. Accuracy plateaus by about 100 trees; log-loss mostly falls because the probabilities stop being 0/1.

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 {d/2, d, 2d}\{\sqrt d/2,\ \sqrt d,\ 2\sqrt d\} or a few fractions. This is the hyperparameter that matters most. With many irrelevant features, raise mm so that a useful one is usually among the candidates: a given feature is available at a node with probability m/dm/d.
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
gini or entropy (log-loss). They rarely differ, as with single trees.

Relatives

Plain bagging
m=dm=d: 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

python
1import numpy as np
2
3def gini(counts):
4 n = counts.sum()
5 return 0.0 if n == 0 else 1.0 - ((counts / n) ** 2).sum()
6
7def 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] <= t
14 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 best
20
21def 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 leaf
26 if features is None: # fresh random subset at every node
27 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 leaf
32 L = X[:, j] <= t
33 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)}
36
37def 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"]
41
42def 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) # bootstrap
47 forest.append((grow(X, y, w, max_features, rng, max_depth), w))
48 return forest
49
50def predict_proba(forest, x): # soft vote
51 return np.mean([proba(tree, x) for tree, _ in forest])
52
53def oob_accuracy(forest, X, y):
54 right = seen = 0
55 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 += 1
59 right += (np.mean(ps) > 0.5) == y[i]
60 return right / seen
61
62# ---- 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 = pass
66q = np.array([5, 6.5])
67
68# 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, study
73three = [(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))
80
81# 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))
From scratch in NumPy: weighted Gini trees with a fresh random feature subset at every node, soft voting, OOB accuracy. The demo replays the article's three draws, then grows a real forest. Prints: 0.714 / 0.700 / 0.000, soft 0.471, 2 of 3 hard votes, OOB 0.667; then 200 trees: P(pass | q) = 0.84, OOB 0.75.
python
1import numpy as np
2from sklearn.ensemble import RandomForestClassifier
3from sklearn.tree import DecisionTreeClassifier
4
5X = 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]])
9
10# 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))
20
21# 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))
scikit-learn. Part 1 reproduces the hand-built stumps, with the bootstrap passed as sample weights: thresholds 5.5, 5.25 and 5.25, soft vote 0.471. Part 2 is the library forest (500 full trees, max_features = 1): P(pass | q) = 0.868, OOB accuracy 0.75, importances 0.431 (study) and 0.569 (sleep).

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 P(pass∣x)=0.9, 0.4, 0.4P(\text{pass}\mid x) = 0.9,\ 0.4,\ 0.4. What do soft and hard voting predict?

Check yourself

Tree outputs have pairwise correlation ρ=0.3\rho=0.3 and variance σ2=1\sigma^2=1. 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 ρσ2+(1−ρ)σ2/T\rho\sigma^2+(1-\rho)\sigma^2/T. More trees never overfit, but only decorrelation (smaller mm) lowers the floor.
  • ✓Breiman's bound PE∗≤ρˉ(1−s2)/s2PE^*\le\bar\rho(1-s^2)/s^2: max_features trades tree strength against tree correlation, and d\sqrt d is a good default.
  • ✓About e−1≈37%e^{-1}\approx37\% 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.
← back to ML Algorithms roadmap