billparker.ai: Random Forest: A Comprehensive Guide

Random Forest is a highly powerful and versatile machine learning algorithm, often considered the most widely used model among data scientists. Its popularity stems from its reliability and ease of use, making it a common first choice for many tasks. However, to leverage its full potential, it’s crucial to go beyond the basic understanding and explore the underlying mathematical principles, as well as the types of data features and problems where Random Forest truly excels.

At its core, Random Forest enhances the simplicity of decision trees by employing an ensemble approach, which significantly improves prediction accuracy while reducing overfitting. In this post, we’ll walk through the key concepts behind Random Forest, work through a practical example, and examine the mathematical foundations that drive its decision-making process. The example will be implemented in Python using scikit-learn, a library that offers excellent documentation and a well-optimized implementation of Random Forest.

Fundamentally, Random Forest is an ensemble of decision trees. Instead of relying on a single tree, which can be prone to overfitting, it constructs multiple trees using different subsets of both the data and the features. The final prediction is determined by aggregating the outputs of all the trees, either through majority voting (for classification) or averaging (for regression). This ensemble approach allows Random Forest to capture intricate relationships and interactions between variables. For instance, when predicting whether a customer will purchase a product, multiple nonlinear factors such as income, browsing history, and seasonality may influence the decision. Random Forest effectively models these interactions, making it a robust choice for complex datasets.

Random Forest can be used for two types of problems:

For classification: A majority vote among the trees determines the class. In scikit-learn, we can use its RandomForestClassifier module.
For regression: The average of the trees’ predictions is taken. In scikit-learn, we can use its RandomForestRegressor module.

Random Forest is a very flexible algorithm, but it performs best with certain types of data:

Numerical Features (Continuous and Discrete): Random Forest is naturally suited for numerical features since it creates decision tree splits based on thresholds. Some examples would be age, salary, temperature, stock prices.
Categorical Features (Low to Medium Cardinality): Random Forest works well when categories are few and meaningful. Some examples would include “Gender”, “Day of the Week” (Monday-Sunday). If categorical variables have high cardinality (e.g., ZIP codes, product IDs), proper encoding is necessary.

Okay, those are examples of data features where Random Forest works well, but its important that a person explicitly knows what types of data features it doesn't work well with. High cardinal data is problematic like zip codes or product IDs (if there are a lot of them - high cardinality), or something like user IDs. For something like user IDs where every row is a different ID, it should be obvious that shouldn't be a feature, but zip codes and product IDs would be better to group those into smaller segments like regions or product categories.

Sparse data (many zero values) and high dimensional data (too many featues) can also be problematic. For high dimensional data, if the number of features is much larger than the number of samples, Random Forest can become inefficient. In both situations, dimensionality reduction could be the answer. For example, in genomics (e.g., thousands of genes as features), feature selection or dimensionality reduction is needed. Also, be careful with one hot encoding categorical variables such that it creates a large number of columns (large in comparison to the number of samples).

Finally, while Random Forest is very scalable, it can struggle with big data (millions of rows and columns) due to its high computational cost, especially if you set the number of estimators (number of trees in the forest) to a "high" number. If that is the case, then alternatives to be tried include Gradient Boosting Trees (XGBoost, LightGBM) or even Neural Networks could scale better. Also be aware that when saving the model (through pickle) it could create a very large model file, which could be a deployment issue depending on where you are deploying it. A quick solution to that model size problem is to experiment with the number of trees. It is often the case that you can reduce the number of trees and not materially reduce the accuracy. That reduction in the number of trees can greatly reduce the size of the saved model file.

How Does a Random Forest Work?

Random Forest has three main characteristics:

Bootstrapping (Bagging):
Random subsets of the training data are selected with replacement to build each individual tree. This process, known as bootstrapping, ensures that every tree sees a slightly different version of the dataset. This increases the diversity among the trees and helps reduce the variance of the final model.
Random Feature Selection:
At each split instead of considering every feature, a random subset of features is chosen. The best split is determined only from this subset. This approach helps prevent any single strong predictor from dominating the model and increases overall robustness.
Tree Aggregation:
Voting or averaging: once all trees are built, their individual predictions are aggregated. For a classification task, the class that gets the most votes is chosen. In regression, the mean prediction is used.

The Math Behind Random Forests

The most important mathematical concept in Random Forests is the idea behind how decision trees make decisions regarding the splits.

Gini Impurity

A common metric used to evaluate splits in a decision tree is the Gini impurity. It measures how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the node.

The Gini impurity is given by:

\( G = 1 - \sum_{i=1}^{C} p_i^2 \)

Where:

\( C \) is the number of classes.
\( p_i \) is the proportion of samples of class i in the node. \( p_i = \frac{\text{Number of samples in class } i}{\text{Total samples in the node}} \)

A lower Gini impurity means a purer node, which is generally preferred when making splits. But let's not just blow by the formula for the Gini score. Let's try and get an intuitive understanding of why we are using it.

Example Gini Calculation:

Suppose a node contains 10 samples:

6 samples belong to Class 1: \( p_1 \) = 0.6
4 samples belong to Class 2: \( p_2 \) = 0.4

Then, the Gini impurity is:

\( G = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48 \)

The Gini Impurity is a measure of how “impure” or “mixed” a dataset is in terms of class distribution. The goal of this metric is to determine how often a randomly chosen element from the dataset would be incorrectly classified if it were labeled according to the distribution of classes in the dataset.

What Happens When a Node is Pure?

If a node contains only one class, then the probability for that class is 1 and for all other classes is 0.
Example: Suppose a node contains only class “A,” meaning \( p_A = 1 \), and all other \( p_i = 0 \). The Gini impurity calculation is:

\( G = 1 - (1^2) = 0 \)

This correctly indicates that the node is completely pure (no uncertainty).

What Happens When a Node is Impure?

If a node contains multiple classes in equal proportions, the impurity is higher. For example, if a node has two classes with equal probability \( p_1 = 0.5 \), \(p_2 = 0.5\) :

\( G = 1 - (0.5^2 + 0.5^2) = 1 - (0.25 + 0.25) = 0.5 \)

which shows that the node has some level of impurity.

What about \( \sum p_i^2 \) ?

The term:

\( \sum_{i=1}^{C} p_i^2 \)

represents the probability that two randomly chosen samples belong to the same class (this is also known as the probability of a correct classification by a randomly assigned label). If a node is pure (all samples belong to the same class), then one class has probability 1 and all others are 0. In this case, \( \sum p_i^2 = 1 \), meaning that the probability of correct classification is high, and thus impurity is low. If a node is impure (samples are evenly split among classes), then each \( p_i \) is small, making \( \sum p_i^2 \) small, and impurity is higher.

Okay, But Why Do We Subtract from 1?

The impurity should be 0 for pure nodes and higher for mixed nodes. Since \( \sum p_i^2 \) represents the probability of getting two samples from the same class, the complement \( 1 - \sum p_i^2 \) represents the probability of drawing two samples from different classes. Higher values of G indicate more impurity. In essence, subtracting from 1 flips the interpretation, making it a measure of impurity instead of purity.

Gini Final Thoughts

Gini impurity is not the only other criterion that can be used in Random Forests. In fact, scikit-learn has two others: entropy and log loss, but Gini impurity is the default and widely used.

Also, athough Gini impurity is primarily associated with decision trees and Random Forests, it has applications beyond these models, which is another reason why its a great idea to know some of the background around it. For example, Gini impurity is also used in CART algorithms, feature importance calculations, clustering and unsupervised learning, fairness and bias detection, in economics with income inequality measurements, and genetics.

Gini has this core idea of measuring impurity or diversity which makes it useful in any field that involves classification, grouping, or fairness assessment.

Random Forest: An Example

Let’s put all of these ideas together and walk through a simplified example to see these concepts.

Imagine a small dataset with two features and a binary label:

\[ \begin{array}{|c|c|c|c|} \hline \textbf{Sample} & \textbf{Feature1 (X)} & \textbf{Feature2 (Y)} & \textbf{Label} \\ \hline 1 & 2 & 10 & 0 \\ 2 & 3 & 15 & 0 \\ 3 & 4 & 10 & 1 \\ 4 & 5 & 20 & 1 \\ 5 & 6 & 15 & 0 \\ 6 & 7 & 25 & 1 \\ 7 & 8 & 10 & 0 \\ 8 & 9 & 20 & 1 \\ \hline \end{array} \]

Step 1: Bootstrapping

Randomly sample the dataset with replacement to create a bootstrap sample. For example, one such sample might have the indices:

[2, 3, 3, 5, 7, 8, 8, 1]

Extracted bootstrap sample:

\[ \begin{array}{|c|c|c|c|} \hline \textbf{Sample} & \textbf{Feature1 (X)} & \textbf{Feature2 (Y)} & \textbf{Label} \\ \hline 2 & 3 & 15 & 0 \\ 3 & 4 & 10 & 1 \\ 3 & 4 & 10 & 1 \\ 5 & 6 & 15 & 0 \\ 7 & 8 & 10 & 0 \\ 8 & 9 & 20 & 1 \\ 8 & 9 & 20 & 1 \\ 1 & 2 & 10 & 0 \\ \hline \end{array} \]

Notice some samples appear multiple times (e.g., Sample 3 and Sample 8), while some samples from the original dataset (e.g., Sample 4 and 6) don’t appear at all..

Step 2: Building a Single Decision Tree

For the bootstrap sample, a decision tree is built by considering various splits. Suppose first we consider a split on Feature1 at X = 5:

Left Node (X ≤ 5): Contains samples 2, 3, 3, 1.

Total samples = 4

Class 0 count = 2
Class 1 count = 2

Right Node (X > 5): Contains samples 5, 7, 8, 8.

Total samples = 4

Class 0 count = 2
Class 1 count = 2

Result:

The tree evaluates multiple such splits (e.g., other features, thresholds) and chooses the split that results in the lowest Gini impurity.

Here is an example of another one of the many other possible trees shown graphically.

The samples value represents the number of training data points (observations) that reached that particular node. At the root node (the topmost node), this number is equal to the total number of observations in the dataset used for training the tree. As the tree splits at each step, the number of samples in child nodes decreases because the dataset is divided based on feature conditions. The value represents how many training samples from each class are in the node. This helps determine how “pure” the node is. If all samples belong to a single class, the node is pure and doesn’t need further splitting. For example, in the node that has value = [5, 1] means 5 samples belong to class 0 and 1 sample belongs to class 1.

What is visualized here is a single decision tree, but in a Random Forest, multiple decision trees are built, each using a different subset of the data and features. The final prediction is determined by aggregating the outputs from all these trees.

Step 3: Aggregation of Trees

In a Random Forest model, this process is repeated multiple times with different bootstrap samples. After multiple decision trees are created:

Classification: Each tree independently votes for a class label with majority voting deciding the final predicted label. If there’s a tie, the class with lower numerical label (e.g., 0) might be chosen by convention, or other tie-breaker methods applied.
For example, if 5 trees predict class “1” and 2 trees predict class “0,” the final prediction is class 1.
For Regression: The average of all tree predictions is taken.

Hypothetical Aggregation Example If we had multiple trees (e.g., 5 trees):

\[ \begin{array}{|c|c|} \hline \textbf{Tree #} & \textbf{Prediction (for new input X=5, Y=15)} \\ \hline 1 & 0 \\ 2 & 1 \\ 3 & 0 \\ 4 & 1 \\ 5 & 1 \\ \hline \end{array} \]

Votes:

Class 0: 2 votes
Class 1: 3 votes

Final prediction: Class 1 (since it has majority votes).

Summary: This process leverages the randomness of bootstrap sampling and ensemble learning to improve predictive accuracy and generalization compared to just using a single decision tree.

Python Example Using scikit-learn

Okay now that we have the concepts, let's put this example into some Python code that demonstrates how to implement a Random Forest classifier on our small dataset:

from sklearn.ensemble import RandomForestClassifier
import pandas as pd

# Define the dataset
data = pd.DataFrame({
    'Feature1': [2, 3, 4, 5, 6, 7, 8, 9],
    'Feature2': [10, 15, 10, 20, 15, 25, 10, 20],
    'Label':    [0, 0, 1, 1, 0, 1, 0, 1]
})

X = data[['Feature1', 'Feature2']]
y = data['Label']

# Train a Random Forest with 5 trees
clf = RandomForestClassifier(n_estimators=5, random_state=42)
clf.fit(X, y)

# Predict for a new sample
new_sample = [[5, 15]]
prediction = clf.predict(new_sample)
print("Predicted Label:", prediction[0])

Output: Predicted Label: 0

This code creates a simple dataset and trains a Random Forest classifier with 5 trees. It predicts the label for a new sample where Feature1 is 5 and Feature2 is 15 with a prediction of label 0.

Conclusion

Random Forest is a popular ensemble learning method that leverages multiple decision trees to create a model that is both robust and accurate. By using bootstrapping and random feature selection, it reduces overfitting and captures complex patterns in the data. The mathematical principles, such as the calculation of Gini impurity, provide insight into how individual trees decide on the best splits, ensuring that the final model is well-tuned and reliable.

Whether you’re doing classification or regression problems, understanding the inner workings of Random Forest can strengthen your approach to machine learning in general.

billparker.ai

Sunday, March 9, 2025

Random Forest: A Comprehensive Guide