Random Forest in Python: Bagging, Feature Sampling and OOB From Scratch
A random forest trains many decision trees on random samples of the data and lets them vote. We built one from scratch in Python on a customer churn example, measured how accuracy changes from 1 to 100 trees, used out-of-bag rows as a free validation set, and compared two feature importance measures, one of which gave pure noise columns 10 percent of the credit.
- A random forest combines many decision trees, each trained on a bootstrap sample and choosing splits from a random subset of features.
- One unlimited tree scored 74.5 percent on test data; a 100-tree forest scored 78.0 percent.
- The out-of-bag estimate, 77.7 percent with 100 trees, came within a point of the real test score without using any test data.
- Impurity-based importance gave three pure-noise features about 10 percent each; permutation importance put them near zero.
A single decision tree is readable but unstable: small changes in the data produce a different tree, and grown deep it memorises noise. A random forest turns that weakness into a strength. It grows hundreds of deliberately different trees and averages their votes, so individual mistakes cancel out. It is one of the most reliable models for tabular data, needs little tuning and rarely overfits badly.
We implemented it from scratch in Python 3.13.6 with NumPy 2.5.5 on synthetic, seeded data. scikit-learn’s RandomForestClassifier does the same far faster; we did not run it here. Our pure-Python forest took about 25 seconds for all experiments.
What is a random forest?
A random forest is an ensemble of decision trees with two sources of randomness. Each tree is trained on a bootstrap sample, rows drawn at random with replacement, and at each split it may only consider a random subset of features. To predict, every tree votes and the majority wins (for regression, the trees’ predictions are averaged). Leo Breiman introduced the method in 2001 by combining bagging with random feature selection.
Why many trees beat one
Each deep tree has low bias but high variance: it fits its sample closely, including the noise. If the trees make different mistakes, a majority vote cancels much of that variance while keeping the low bias. The two kinds of randomness exist to make the trees different from each other. Averaging identical trees would gain nothing.
Our churn dataset
rng = np.random.default_rng(11)
X = rng.uniform(0, 1, (1200, 6))
# tenure, support_calls, monthly_bill, noise_a, noise_b, noise_c
logit = (6 * (X[:, 0] - 0.5)
+ 5 * (X[:, 1] - 0.5) * ((X[:, 0] > 0.5) * 2 - 1) # interaction
+ 1.5 * (X[:, 2] - 0.5)) # weak effect
y = (rng.uniform(size=1200) < 1 / (1 + np.exp(-logit))).astype(int)
# 800 rows to train, 400 to test
Six features: tenure matters most, support_calls matters in opposite directions depending on tenure (an interaction a linear model cannot capture without help), monthly_bill has a weak effect, and three columns are pure noise. Labels are random draws from the true probability, so even a perfect model cannot reach 100 percent.
Bagging: bootstrap samples
idx = rng.integers(0, len(train), len(train)) # 800 draws with replacement
oob = np.setdiff1d(np.arange(len(train)), idx) # rows never drawn
# on average 1 - (1 - 1/800)**800 = 63.2% of rows appear in a sample, 36.8% are out-of-bag
Drawing 800 rows with replacement from 800 produces a sample with duplicates: on average only 63.2 percent of distinct rows appear, and the remaining 36.8 percent are “out-of-bag” (OOB) for that tree. Each tree therefore sees a slightly different dataset, and each row is unseen by about a third of the trees, which we use for validation below.
Feature sampling at each split
feats = rng.choice(X.shape[1], mtry, replace=False) # e.g. 2 of 6 features
g, f, t = best_split(X, y, feats)
At every split, a tree may only choose among mtry randomly chosen features. A common default for classification is the square root of the number of features, here about 2 of 6. Without this, every tree would split first on the strongest feature, and the trees would look alike. Forcing some trees to start elsewhere makes them more diverse.
The forest code
def fit_forest(T, mtry):
trees = []
for _ in range(T):
idx = rng.integers(0, n_train, n_train) # bootstrap
trees.append(build(X_train[idx], y_train[idx], depth=0,
max_depth=None, mtry=mtry)) # full-depth tree
return trees
def forest_predict(trees, x):
return Counter(predict(t, x) for t in trees).most_common(1)[0][0] # majority vote
The tree builder is the same Gini-based CART algorithm as in our decision tree article, with two changes: it picks candidate features at random for each split, and, to keep pure Python fast enough, it tests 40 quantile thresholds per feature instead of every possible value. Trees are grown to full depth; the averaging, not pruning, controls overfitting.
One tree vs a forest
| Model | Train accuracy | Test accuracy |
|---|---|---|
| Single full-depth tree, all rows, all features | 1.000 | 0.745 |
| Forest, 100 trees, bootstrap, mtry = 2 | 1.000 | 0.780 |
Both models fitted the training data perfectly, so training accuracy says nothing here. On new data the forest was 3.5 points better. That is a typical gain on a small, noisy dataset; on larger and more complex data the gap is often wider.
How many trees?
| Trees | Train | Test | OOB estimate |
|---|---|---|---|
| 1 | 0.868 | 0.682 | n/a |
| 10 | 0.988 | 0.720 | 0.720 |
| 50 | 1.000 | 0.780 | 0.762 |
| 100 | 1.000 | 0.780 | 0.777 |
A single bootstrapped tree with restricted features was the worst model of all (68.2 percent), because it saw fewer distinct rows and had to make weaker splits. Accuracy rose quickly as trees were added and levelled off between 50 and 100. Unlike tree depth, adding trees does not cause overfitting; it only costs time. Stop when the OOB or validation score stops improving.
Out-of-bag evaluation: free validation
for each training row:
collect votes only from trees whose bootstrap sample did not include it
OOB accuracy = share of rows where that vote matches the label
# 100 trees: OOB 0.777 vs test 0.780
Because every row is out-of-bag for about a third of the trees, we can score each row using only the trees that never saw it. The resulting OOB accuracy was 77.7 percent with 100 trees, within 0.3 points of the score on the held-out test set. That gives a fair estimate of generalisation without setting data aside, which is valuable when data is scarce. With only 10 trees, many rows had very few OOB votes, so the estimate was noisier.
Does feature sampling always help?
bagging only (mtry = all 6 features, 50 trees): test 0.790
random forest (mtry = 2, 50 trees): test 0.780
Honest result: on this dataset, plain bagging was slightly better. With only six features, two of which carry most of the signal, restricting each split to two features often forced trees to use noise. Feature sampling shines when there are many features and several strong, correlated ones; with few features, try larger mtry values. Treat mtry as a hyperparameter to tune, using the OOB score.
Feature importance: two measures, two stories
| Feature | Impurity importance | Permutation importance (drop in test accuracy) |
|---|---|---|
| tenure | 0.367 | 0.293 |
| support_calls | 0.199 | 0.120 |
| monthly_bill | 0.134 | 0.023 |
| noise_a | 0.098 | 0.010 |
| noise_b | 0.099 | 0.005 |
| noise_c | 0.103 | -0.015 |
Impurity importance adds up how much each feature reduced Gini impurity across all splits. It is free to compute but biased: full-depth trees eventually split on noise to separate the last few training rows, and continuous noise features offer many split points, so the three noise columns received about 30 percent of the total credit between them. Permutation importance shuffles one feature in the test data and measures how much accuracy drops. Shuffling tenure cost 29 points, support calls 12, and the noise columns essentially nothing, which matches how we generated the data. Use permutation importance on held-out data when the ranking matters, and remember that neither measure tells you the direction of an effect.
Tip: add a column of random numbers to your data before computing importances. Any real feature that ranks below it is probably not useful.
Votes as probabilities
first test row: 56 of 100 trees voted churn, true label: no churn
The share of trees voting for a class is a rough probability. For our first test customer, 56 percent of trees predicted churn, a borderline case that the forest got wrong at the default 0.5 threshold. Treat such scores as rankings rather than exact probabilities; if you need calibrated probabilities, as logistic regression gives, calibrate the forest’s scores on validation data. Choosing a threshold from the cost of each error works just as it does for any classifier.
Practical tips
- Start with defaults: a few hundred trees, full depth, square-root feature sampling, then tune
mtryand minimum leaf size with the OOB score. - No scaling needed, unlike k nearest neighbors, because trees compare features with thresholds.
- Use regression forests for numbers: averaging the trees’ predictions gives a non-linear alternative to linear regression.
- Train in parallel: trees are independent, so forests use every CPU core easily.
- Watch memory: hundreds of full-depth trees on large data can be big; limit depth or leaf size if needed.
- Try gradient boosting next when you need the last few points of accuracy; it builds trees sequentially, each correcting the last, and usually needs more tuning.
- Compare with simple baselines such as naive Bayes or logistic regression; on small, mostly linear problems they can match a forest.
Final thoughts
A random forest is many decision trees made different on purpose, by bootstrap sampling and random feature choice, then combined by voting. In our test it beat a single tree by 3.5 points, the out-of-bag score predicted test accuracy within a third of a point, and permutation importance correctly identified the noise columns that impurity importance overrated. Grow enough trees, tune feature sampling with the OOB score, and check importances with permutation before trusting them.
Frequently asked questions
How does a random forest work?
It trains many decision trees, each on a random bootstrap sample of the rows and choosing each split from a random subset of features, then combines their predictions by majority vote or averaging.
What is the difference between bagging and a random forest?
Bagging trains trees on bootstrap samples using all features at every split. A random forest adds random feature selection at each split, which makes the trees more different from each other.
What is out-of-bag error?
Each tree leaves out about a third of the rows. Scoring every row with only the trees that never saw it gives an estimate of test accuracy without a separate validation set.
Can a random forest overfit?
Adding more trees does not cause overfitting, but each tree can still memorise noise. On very noisy or small data, limit leaf size or depth and check the out-of-bag score.
Which feature importance should I trust?
Permutation importance on held-out data is usually more reliable. Impurity-based importance is fast but tends to favour features with many split points, including pure noise.
Keep learning
Need help with testing, WordPress or SEO?
We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.