Random Forests are a powerful ensemble learning method used for classification and regression tasks. In this post, we'll build a Random Forest model from scratch in Python, exploring the key concepts and algorithms behind it.
Understanding Decision Trees
Before diving into Random Forests, it's essential to understand Decision Trees. A Decision Tree is a flowchart-like structure where each internal node represents a feature (or attribute), each branch represents a decision rule, and each leaf node represents an outcome (or class label).
Building a Decision Tree
To build a Decision Tree, we use algorithms like ID3, C4.5, or CART. The basic idea is to split the dataset into subsets based on the feature that results in the highest information gain (or lowest Gini impurity).
Random Forests: The Ensemble Method
A Random Forest is an ensemble of Decision Trees. It combines the predictions of multiple trees to improve accuracy and reduce overfitting. Each tree is trained on a random subset of the data and a random subset of features.
Implementing Random Forests from Scratch
Here's a simplified implementation of Random Forests in Python:
Random Forest Classifier vs Random Forest Regressor
Although both algorithms are based on the same ideaβcombining multiple decision treesβthey solve different types of problems.
Random Forest Classifier
A Random Forest Classifier is used when the target is a category (class label).
Imagine we have the following training data:
| House Size (mΒ²) | House Type |
|---|---|
| 50 | Apartment |
| 60 | Apartment |
| 150 | Villa |
| 180 | Villa |
Now suppose we want to predict the type of a new house with a size of 160 mΒ².
Each decision tree in the forest makes its own prediction:
- Tree 1 β Villa
- Tree 2 β Villa
- Tree 3 β Apartment
- Tree 4 β Villa
- Tree 5 β Villa
We then count the votes:
- Villa: 4 votes
- Apartment: 1 vote
Since Villa receives the most votes, the final prediction is:
Prediction: Villa
This process is called Majority Voting.
Random Forest Regressor
A Random Forest Regressor is used when the target is a continuous numerical value.
Instead of predicting the house type, suppose we want to predict its price.
Our training data looks like this:
| House Size (mΒ²) | Price (DH) |
|---|---|
| 50 | 500,000 |
| 60 | 600,000 |
| 150 | 1,800,000 |
| 180 | 2,200,000 |
Now we want to estimate the price of a 160 mΒ² house.
Each tree predicts a different price:
- Tree 1 β 1,900,000 DH
- Tree 2 β 2,000,000 DH
- Tree 3 β 1,850,000 DH
- Tree 4 β 1,950,000 DH
- Tree 5 β 2,100,000 DH
Unlike classification, we cannot use majority voting because every prediction is a different number.
Instead, we compute the average:
(1,900,000 + 2,000,000 + 1,850,000 + 1,950,000 + 2,100,000) / 5 = 1,960,000
Therefore, the final prediction is:
Prediction: 1,960,000 DH
Key Difference
| Random Forest Classifier | Random Forest Regressor |
|---|---|
| Predicts categories (classes) | Predicts continuous numerical values |
| Example: Apartment or Villa | Example: House price |
| Final prediction = Majority Vote | Final prediction = Average of all tree predictions |
Conclusion
In this post, we explored the fundamentals of Decision Trees and how they form the basis of Random Forests. We also provided a simple implementation of Random Forests from scratch in Python. While this implementation is basic, it serves as a great starting point for understanding the mechanics behind ensemble learning methods.
Random Forest From Scratch
The real implementation β BaseModel, LabelEncoderSimple, Calculate, _Decision_Tree, RandomForest β with every formula worked by hand, an entropy-vs-Gini comparison, and a reusable project structure for any ML pipeline.
- Decision trees
- Bootstrap sampling
- Feature bagging
- Gini impurity
- Prediction voting
Pipeline
Class map:We'll follow one running example all the way through, matching the shape of a typical test case:
Three samples belong to class 0, five belong to class 1. Every formula below is computed on this exact data so the numbers are traceable end to end.
Part 1 β The Formulas (with worked comparisons)
1.1 Entropy β H_parent, H_left, H_right
Formula:
Why we need it: entropy is a single number that tells us how "mixed" a node is. A pure node (one class only) has entropy 0; a 50/50 mix has maximum entropy. Trees use this number to decide whether a split actually helped.
Worked example (from the code's own docstring: y = [1, 2, 2, 4, 1]):
| class | count | probability |
|---|---|---|
| 1 | 2 | 2/5 = 0.4 |
| 2 | 2 | 2/5 = 0.4 |
| 4 | 1 | 1/5 = 0.2 |
Why three named methods (H_parent, H_left, H_right) instead of one generic _entropy? All three call the exact same formula underneath β the split exists so the code reads like the math. H_parent(y) next to H_left(y_left) and H_right(y_right) mirrors the whiteboard notation H(parent), H(left), H(right) directly, which makes debugging a specific split far easier than one anonymous call.
1.2 Gini Impurity
Formula:Why it exists as an alternative to entropy: entropy needs a logarithm per class, per node, per candidate threshold β for large datasets that adds up. Gini gives almost the same ranking of "which split is better" using only squaring and subtraction, which is why it's the faster default in many implementations (including scikit-learn's).
Same example, computed with Gini:
1.3 Mo9arana (Comparison): Entropy vs. Gini
| Entropy | Gini | |
|---|---|---|
| Formula | -Ξ£ p_iΒ·log2(p_i) |
1 - Ξ£ p_iΒ² |
| Range (binary) | 0 β 1 | 0 β 0.5 |
| Computation | needs log2 |
only multiplication |
| Speed | slower | faster |
| Sensitivity to class mix | slightly more sensitive to rare classes | slightly smoother |
| Typical use | classic ID3/C4.5 trees | CART, scikit-learn default |
Practical takeaway: they almost always pick the same split as "best" β the difference in outcome is usually tiny. This is exactly why the real implementation exposes criterion="entropy" or criterion="gini" as a constructor option instead of hard-coding one.
1.4 Before vs. After Split β the Real Comparison
This is the core comparison that drives every decision the tree makes.
Before the split (entropy of the parent, using our running dataset β 3 samples of class 0, 5 of class 1):
After the split at age <= 3:
- Left child β ages
[1,2,3]β all class0β pure βH_left = 0 - Right child β ages
[4,5,6,7,8]β all class1β pure βH_right = 0
Weighted average ("H_after"):
Comparison:
| Entropy | |
|---|---|
Before split (H_parent) |
0.954 |
After split (H_after) |
0.000 |
| Reduction | 0.954 |
The split completely separated the two classes β impurity dropped from 0.954 to 0, the best possible outcome.
1.5 Information Gain β IG(D)
Formula:
Why it matters: entropy alone only tells you how mixed one node is. Information Gain tells you how much a specific candidate split improved things. The tree tries many (feature, threshold) pairs and keeps whichever gives the highest IG β that's the actual decision rule behind growing the tree.
Worked example (continuing from above):
The Gini equivalent (gini_gain) follows the identical pattern, just swapping gini(...) in for every _entropy(...) term.
Part 2 β BaseModel: A Shared Foundation
Every class in this codebase inherits from BaseModel, which does two things:
- Defines the common
fit(X, y)/predict(X)interface (raisingNotImplementedErrorif a subclass forgets to override them) β so every model in the project is guaranteed to expose the same two methods. - Provides a colored
log()utility, gated behind adebugflag (read from theDEBUGenvironment variable), so training can be traced without littering the code withprint()statements:
LabelEncoderSimple, Calculate, _Decision_Tree, and RandomForest all inherit from it, so every part of the pipeline can be debugged the same way: RandomForest(debug=True).
Part 3 β The Code, Function by Function (with "why" and examples)
3.1 LabelEncoderSimple β why encode labels at all?
Trees compare values numerically (x[feature] <= threshold). A label like "cat" can't be compared with <=. The encoder maps each unique class to an integer and remembers the mapping so predictions can be decoded back:
Example: y = ["cat","dog","cat"] β class_to_index = {"cat":0, "dog":1} β encoded [0, 1, 0]. After prediction, inverse_transform([0, 1, 0]) gives back ["cat","dog","cat"]. This round-trip is why the class stores both dictionaries instead of just one.
The forest wrapper doesn't force you to encode labels manually β it detects the label dtype itself:
and decodes predictions back automatically in predict() if _needs_encoding was set. This means RandomForest transparently accepts y = [0, 1, 1, 0] or y = ["cat", "dog", "dog", "cat"] with no manual preprocessing.
3.2 Utils.candidate_thresholds β why not test every value?
Why: if a numeric column has 10,000 unique values, testing every one as a threshold means 10,000 impurity calculations per feature, per node. That's wasteful, since most nearby thresholds give nearly identical splits.
Example: column [10, 12, 15, 40, 42, 100] β midpoints [11, 13.5, 27.5, 41, 71]. If that's β€ 32, all are kept as candidates; if there were thousands, only an evenly-spaced subset of 32 would be tried.
3.3 Calculate β Entropy, Gini, Gain, and Bootstrap in One Place
This class holds every formula from Part 1, plus bootstrap sampling and the majority-class rule.
These are exactly the formulas from Part 1 β _entropy and gini implement H(S) and Gini(S), H_after/gini_after implement the weighted post-split average, and information_gain/gini_gain implement IG(D) = H(parent) - H_after.
Why bootstrap sampling, and why with replacement: Random Forest needs each tree to see a slightly different dataset β otherwise every tree learns the same patterns and voting wouldn't reduce error at all. Sampling with replacement (the same row can be picked more than once) creates that diversity cheaply:
Example: with 8 rows, a bootstrap sample might draw indices [0,0,2,3,5,5,6,7] β row 0 appears twice, rows 1 and 4 are missing entirely. Those missing rows are the out-of-bag (OOB) samples this function also returns β the standard way to validate a Random Forest without a separate held-out test set, since each tree naturally has "unseen" data available. (This implementation returns OOB data but doesn't score it yet β a natural next step.)
Majority class, used whenever a node stops splitting and becomes a leaf:
3.4 _Tree_Node β why a class and not a dict?
Why: a node is one of exactly two things β a decision (feature + threshold + two children) or a leaf (value). A small class makes both cases representable with the same object, and node.value is not None is enough to tell them apart during traversal:
3.5 _Decision_Tree.fit and _grow_tree β why recursive, and why stop?
Why recursive: a tree is a split, whose children are themselves smaller trees. Recursion mirrors that structure directly β _grow_tree calls itself on the left subset and the right subset.
Why three stopping conditions:
depth >= max_depthβ prevents the tree from growing forever (overfitting control).n_labels == 1β the node is already pure (matchesH(S) = 0from Part 1); splitting further can't improve it.n_samples < min_samples_splitβ too few samples left to trust a further split statistically.
Without these, a tree would keep splitting until every leaf has exactly one sample β memorizing the training data instead of generalizing.
3.6 _Find_Best_Split β the split function, with feature bagging built in
This is where Random Forest randomness actually happens β not in the forest wrapper, but inside every single tree's split search:
Why it randomly samples features first: this is feature bagging β instead of considering every column at every node, only a random subset (typically sqrt(total_features)) is considered. Combined with bootstrapping, this is what makes trees in the forest disagree with each other β and disagreement is exactly what majority voting needs in order to cancel out individual mistakes. Notice this happens at every node, not just once per tree β that's a stronger decorrelation effect than bagging features only at the root.
Why it loops feature β threshold β gain: it's an exhaustive-but-bounded search β try every allowed (feature, threshold) combination from candidate_thresholds, keep whichever gives the highest information_gain/gini_gain. This is "best split": no shortcut, just a bounded brute-force search guided directly by the IG formula from Part 1.
Worked example, using our running dataset: at the root, trying feature=age, threshold=3 gives left=[0,0,0] (pure), right=[1,1,1,1,1] (pure) β IG = 0.954 - 0 = 0.954, the maximum possible β so this becomes the root split.
3.7 _traverse and predict β prediction traversal
Why separate from training: growing a tree happens once; predicting happens for every new sample, potentially thousands of times. Keeping traversal as its own lightweight recursive function means prediction is just "follow the arrows" from root to leaf.
Example: sample x = [5, 24] on the tree trained above, with root threshold age <= 3 β 5 > 3 β go right β reaches a leaf with value = 1.
3.8 RandomForest β the ensemble wrapper
Why a wrapper class at all, instead of training trees in a loop wherever needed: it centralizes everything that only makes sense at the forest level β shared randomness (rng), automatic label encoding, and the final voting step β so every individual tree can stay a simple, self-contained decision tree.
Training β bootstrap + bagging, one tree at a time:
Two defaults worth calling out:
- If
n_featuresisn't specified, it defaults tosqrt(total_features)β the standard Random Forest heuristic for classification. - All trees share one
rng(np.random.default_rng(random_state)), passed down from the forest, so the whole forest is reproducible from a singlerandom_stateβ not just the bootstrap step, but every feature-bagging draw inside every tree too.
Predicting β majority vote across trees:
Why majority voting reduces error: if individual trees are only somewhat accurate but make different mistakes (thanks to bootstrapping + feature bagging), their errors don't line up. Voting cancels out the noise while keeping the shared signal β the statistical reason a Random Forest usually outperforms any single tree inside it.
Example: 5 trees predict [1, 1, 0, 1, 1] for the same sample β 4 votes for class 1, 1 vote for class 0 β final prediction is 1.
3.9 Putting It All Together
Full flow:
Part 4 β A Reusable Project Structure (Any Project, scikit-learn Included)
Whether you use this custom RandomForest or sklearn.ensemble.RandomForestClassifier, the surrounding workflow is always the same shape:
This structure is what makes the custom RandomForest "drop-in": it exposes fit(X, y) and predict(X) just like scikit-learn's estimators, so it slots into the exact same 10-step pipeline without changing anything else.
Conclusion
Every piece of this implementation earns its place:
BaseModelgives every component a sharedfit/predictcontract and a debug-logging system.- Entropy and Gini quantify impurity β two roads to (almost) the same destination, one exact, one fast β exposed as a
criterion="entropy"|"gini"choice. - Comparing before vs. after a split (
H_parentvs.H_after) is the actual mechanism behind every decision a tree makes; Information Gain turns that comparison into a single number the tree can maximize. LabelEncoderSimpleplus automatic dtype detection means the forest accepts raw string labels with zero manual preprocessing.candidate_thresholdskeeps that maximization affordable on real-sized data by capping and evenly sampling threshold candidates instead of scanning every unique value.- Bootstrap sampling (with OOB tracking) and feature bagging at every node are what make the trees disagree with each other in useful ways.
- Recursive growing with stopping conditions keeps trees from memorizing noise.
- Majority voting turns many imperfect, uncorrelated trees into one Random Forest that's more accurate than any of them alone.
- The load β clean β split β scale/encode β train β predict β evaluate β tune β save structure is the same regardless of which model sits inside it β from-scratch or scikit-learn.
The result is a Random Forest that behaves like scikit-learn's from the outside (fit, predict, string or numeric labels, criterion="gini"|"entropy") while being fully transparent β formula by formula β on the inside.
Full implementation available on GitHub: Random_Forest_From_Scratch
