The Random Forest model

Author(s): Sandeepkumar Racherla

Originally published on Towards AI.

Ensemble Learning: From Decision Tree to Random Forest

Discover the power of ensemble learning

In this article, we’ll discuss and describe ensemble learning.

We’ll start our discussion with the Decision Tree model. We’ll, then, explain the ensemble learning and, finally, we’ll describe the Random Forest model as an ensemble created on top of Decision Trees.

For both the Decision Tree and the Random Forest, we’ll provide Python code to show how we can implement them in the case of a classification task.

The Decision Tree model

A Decision Tree (DT) is a very versatile Machine Learning model which is capable of performing regression and classification tasks, having the possibility to work with both numerical and categorical variables.

Here, we’ll explain the DT model, showing its learning process with a little math, and we’ll implement one.

Explaining the DT model

A Decision Tree model is a flow-chart-like Machine Learning model which is built somehow like an actual tree. It has leaves, nodes, roots, and branches.

Let’s see how it works and its features with an actual example. Suppose a DT needs to decide for us if remaining in the office or go out, based on the work we have to do:

So, we have:

• The root node. This is where everything begins and represents the entire dataset.
• The ends are called leaf nodes (all the orange rectangles) because are like leaves for trees: they are at the very end.
• Internal nodes. These are nodes that have been split by the previous nodes.
• Branches. They are a set of internal nodes and leaves, just like in actual trees.
• The maximum depth represents how deep a DT is; in other words, it represents how many splits we need before we arrive at the last leaves (“go home/go to a pub”), starting from the root node.

The basic idea behind Decision Tree models is to use the features of the dataset to make decisions and split the data into smaller subsets. Each internal node in the tree represents a feature or attribute, and the branches represent the different decisions or rules based on the values of that feature.

The leaf nodes represent the final output: a class (in a classification problem) or a value (in a regression problem).

This process is really similar to how we, as humans, make decisions. So a question may arise: how do DTs split the nodes? In other words: how do DTs make decisions?

Well, the DTs go on splitting until all the leaves are pure, which means that all the internal nodes have at least one leaf.

In practice, this may lead to very deep DTs with a lot of nodes, which can easily lead to overfitting. So, what we typically do is prune the tree by setting a limit for the maximum depth (which is one of the DTs’ hyperparameters).

Impurity and Information Gain

To understand how DTs split until the leaves are pure, that is how they make decisions, we need to use some mathematics to explain the concepts of Impurity and Information Gain.

In particular, there are two kinds of Impurity: Entropy and Gini Impurity.

Entropy

In thermodynamics, entropy represents a measure of molecular disorder: entropy is 0 when the molecules are still and well-ordered.

In Machine Learning, we use entropy to measure impurity, following a similar idea. We define entropy as follows [Ref. 2, page 88]:

Where, in the case of a classification problem, we have that p(iU+007Ct) is the proportion of the examples that belong to the class i for the node t.

So, entropy is 0 if all the examples at a particular node belong to the same class, and it is maximal (its maximal value is 1) if, at a particular node, we have a uniform class distribution.

Gini Impurity

Gini impurity is a measure of how well a feature separates the data into different classes. It is defined as the probability of misclassifying a randomly chosen example in a dataset. We define it as follows [Ref. 1, page 169]:

So, given the fact that, in the case of a classification problem, p(iU+007Ct) is the proportion of the examples that belong to the class i for the node t, this is why Gini impurity can be seen as a criterion to minimize the probability of misclassification. This is because if we have:

So, given the fact that, in the case of a classification problem, p(iU+007Ct) is the proportion of the examples that belong to the class i for the node t, this is why Gini impurity can be seen as a criterion to minimize the probability of misclassification. This is because if we have:

which means that all the examples belong to the same class, then:

which means that the node is pure (so, the instances belong to the same class, as said before).

So, Gini impurity ranges from 0 to 1, where 0 represents a pure dataset (all the examples belong to the same class), and 1 represents an impure dataset (the examples belong to multiple classes).

Let’s make an example. Suppose we have a dataset with two classes, A and B, and we have two features, P and Q, to choose from to split the data. If feature P results in a Gini impurity of 0.2 and feature Q results in a Gini impurity of 0.3, we would choose feature P to split the data because it results in a lower impurity, and thus a purer subset of the data.

Which one to use?

sklearn uses Gini impurity as default, but we can set entropy as a criterion ( this is a hyperparameter of DTs). The truth is there there is not a great difference between the two: training a DT with entropy and training another one with Gini impurity is not worth the effort.

Maximizing information gain

Information gain is a measure of the decrease in the impurity of a dataset after a feature is chosen to split the data. The goal of a decision tree, in fact, is to select the most “meaningful” feature so that it will result in the purest subsets of the data. So, we use information gain to determine the relative quality of a feature for this purpose.

So, since information gain is a measure of how well a feature separates the data into different classes, we want to maximize it.

We define it as follows [Ref. 2, page 88]:

where we have:

• f is the feature to split,
• Dp and Dn are, respectively, the dataset of the parent and the n-th child node.
• I is the impurity.
• Np and Nn are, respectively, the total number of training examples at the parent and at the n-th child node.

We introduced the concepts of “parent node” and “child node” above. These are relative terms: any node that falls under another node is a child node or sub-node, and any node which precedes those child nodes is called a parent node

So, for the above formula, the Information Gain is the difference between the impurity of the parent note and the sum of the child nodes’ impurities; this means that the lower the impurity of the child nodes, the higher the Information Gain.

This means that a DT takes decisions with the aim to maximize the Information Gain, which means reducing the impurity at each node.

Implementing a DT in the case of a classification problem

Let’s create a dataset, standardize the data, split it into the train and the test set, fit the train set with a DT model and calculate the confusion matrix on the test set:

from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import confusion_matrix

# Create a classification dataset
X, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_classes=2, random_state=42)

# Standardize the data 
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Split the dataset into train and test sets
X_train, X_test, y_train, y_test = train_test_split(X_scaled, y, test_size=0.2, random_state=42)

# Fit the train set with a Decision Tree model
dt_model = DecisionTreeClassifier(random_state=42)
dt_model.fit(X_train, y_train)

# Calculate the confusion matrix for test set
y_test_pred = dt_model.predict(X_test)
test_confusion_matrix = confusion_matrix(y_test, y_test_pred)
print("Confusion Matrix (Test Set):\n", test_confusion_matrix)

And we get:

Confusion Matrix (Test Set):
 [[103 9]
 [ 12 76]]

This is a pretty good result because the non-diagonal values, representing false positives and false negatives, are very few.

Ensemble learning

When we’re solving an ML problem, we generally test different ML models on the data to find the one that makes better predictions or classifications on new, unseen data.

A way to improve the solution to an ML problem is to combine some models, typically the models that perform the best, on a single, unique model: we call this ensemble learning.

The group, or ensemble, will always perform better than the best individual model.

Let’s see how this works.

The voting principle

Let’s consider a classification example: we’ve trained a Support Vector Machine and a Decision Tree in the case of a binary classification problem, and the accuracy we get is about 80% for both classifiers. This means that both classifiers predict the correct class in 80% of the cases, which can be pretty good.

The goal of ensemble methods is to combine different methods into a single classifier that has better generalization performances than each individual classifier alone. But how can this be possible? How can a meta-classifier, created by combining somehow different classifiers, have better generalization performance than the individual classifiers?

Ensemble learning works on the so-called “law of large numbers”; let’s make an example to understand it [Ref.1, page 183]:

“Suppose we have a biased coin that has a 51% chance of coming up heads, and a 49% chance of coming up tails. If we toss the coin 1'000 times, then will get more or less 510 heads and 490 tails, hence a majority of heads. Doing the math, if we toss the coin 1'000 times, the probability of coming up heads is close to 75%. This is due to the law of large numbers: as we keep tossing the coin, the ratio of heads gets closer and closer to the probability of heads (51%).”

Ensemble learning takes advantage of this principle when combining different classifiers. In fact, a simple way to create an ensemble classifier is to aggregate the predictions of each classifier we have trained and predict the class that gets the most votes: we call this the majority voting principle.

Let’s create a diagram for a better understanding of the majority voting principle. Suppose we have trained an SVM and a DT on a given set of data that is a binary classification problem. This is how the majority voting principle works:

While we can combine any kind of classifiers, this kind of principle works better with independent classifiers because each independent classifier makes uncorrelated errors with the other classifiers. In other words, each classifier in the ensemble is able to capture a different aspect of the data, and by combining their predictions, we can make a more accurate prediction than any of the individual classifiers.

The mathematics Behind the voting principle

Let’s use a classification example to mathematically show how the majority voting principle works.

We want to implement an algorithm that allows us to combine different classifiers, each one associated with a weight for confidence. Our goal is to build a meta-classifier that balances the individual classifiers’ weaknesses (i.e., high bias or high variance) on a set of data. We can create a weighted majority vote as follows [Ref. 2, page 209]:

Where we have:

• “y” that represents the predicted class of our ensemble.
• “Wj” that represents a weight associated with a certain classifier, “Cj”
• “Fa” is a function that returns 1 if the predicted class of the jth classifier matches i, so in the case of “Cj(x)=i”

The arg max function returns the maximum argument.

In the case we have equal weights for every classifier we simply have the following:

Remember that in statistics, the mode is the value that appears most often in a set of data, in this case, y^ is simply the mode of all the output by our classifiers.

So, suppose we have a binary classification problem with three classifiers and we have:

• C1(x) → 1
• C2(x) → 0
• C3(x) → 0

We have:

Now, let’s assign some weights to our classifiers like that:

• C1(x) → 1, W1=0.6
• C2(x) → 0, W2=0.2
• C3(x) → 0, W3=0.2

So, in this case, the prediction made by C1 has more weight than the others, and the class predicted by the ensemble is 1.

In other words, W1=0.6 is three times the weights of C2​ and C3; that is to say: 0.6=3⋅0.20.6. So, what we want to say is that C1 has three times the weight of the other two classifiers, and we can even calculate the prediction of the ensemble with the following formula:

Ensembling with bagging and pasting

Bagging is a short way to say bootstrap aggregating.

In statistics, bootstrap aggregation is any test that uses random sampling with replacing. Replacing means that an individual data point can be chosen more than once.

Instead, pasting is a random sampling technique that doesn’t use the replacement. The fact that pasting doesn’t apply replacement means that an individual data point can be chosen just once.

Let’s use a scheme to clarify the process of bagging:

So, in the above case, we have taken 5 samples from the training set and we’ve fed three classifiers/regressors with them, using the bagging technique; that is to say, we can use the same sample taken from the training set multiple times.

Note that each subset contains a certain number of duplicate subsets and some of the original subsets do not appear in all the resampled subsets, because of the replacement. For clarity: we fed the classifier/regressor 1 with data where the subset n°5 is not present. And so on for the other classifiers/regressors.

Unfortunately, DTs suffer from high variance and we can limit their variance by limiting their depth.

Also, DTs adjust their predictions to every single split of the data. This means that the deeper they are, the more they may overfit.

To avoid having to manage too much with the high variance of DTs, a solution to empower DTs is by creating an ensemble: this is how a Random Forest model borns.

Building an RF model on top of DTs

Ensemble methods have reached a good grade of popularity in the last years in the field of ML, thanks to their good performance towards overfitting.

A random forest (RF) is an ML model that can perform both classification and regression tasks and it is built as an ensemble of decision trees via the bagging method. This means that the RF has all the hyperparameters of a DT, but also it has all the hyperparameters of a bagging classifier/regressor to control the ensemble itself.

Let’s visualize the process of creation of an RF model:

So, here we are growing a forest of decision trees trained on subsamples, with replacement, of the initial training data.

Also, the RF model introduces some extra randomness when growing the trees because, instead of searching for the best feature when splitting a node (as it happens in the DT models), it searches for the best feature between a random subset of the features. This results in a higher bias and lower variance, so a better model with respect to a single DT.

In other words, when splitting a node, DTs consider every possible feature and pick the one that produces the most separation between the subnodes. Instead, in the case of an RF model, each tree can only pick a random subset of the features. This increases randomness and variation between the trees, resulting in more independence between each tree and so more diversification.

Let’s visualize this concept:

So, suppose we have a set of data with 5 features. Checking the trees of our RF model we can see that:

• DT 1 considers feature 1, feature 3, and feature 5.
• DT 2 considers feature 1, feature 4, and feature 5.
• DT 3 considers feature 2, feature 3, and feature 4.

All of these features are randomly selected for each DT of our RF.

Suppose we’ve trained before a single DT on all the features and found that the best feature for splitting the node is feature 2. However, DT 1 and DT 2 can not be trained on feature 2, and they are forced to be trained, respectively, on feature 3 and feature 4 (both in bold in the above image).

We end up with trees that are trained on different random subsets of the initial data, but even on a randomly selected subset of the features, without replacement.

Generally speaking, RFs don’t have the same level of interpretability as DTs, but a big advantage of RFs is that we don’t have to worry too much about their hyperparameters. For example, we typically don’t have to prune a RF, because the ensemble is robust to noise from averaging the predictions of the DTs that create the model.

The typical parameter we should care about is the number of trees that create the RF. We can reach better performances with a higher number of trees at the expense of a higher computational cost (we need more time and hardware resources).

Implementing an RF

Let’s use the same dataset we used for the Decision Tree to compare the results when we’re using a Random Forest:

from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import confusion_matrix

# Create a classification dataset
X, y = make_classification(n_samples=1000, n_features=10, n_informative=5, n_classes=2, random_state=42)

# Standardize the data with the StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Split the dataset into train and test sets
X_train, X_test, y_train, y_test = train_test_split(X_scaled, y, test_size=0.2, random_state=42)

# Fit the train set with a Random Forest model
rf_model = RandomForestClassifier(n_estimators=100, random_state=42)
rf_model.fit(X_train, y_train)

# Calculate the confusion matrix for test set
y_test_pred = rf_model.predict(X_test)
test_confusion_matrix = confusion_matrix(y_test, y_test_pred)
print("Confusion Matrix (Test Set):\n", test_confusion_matrix)

And we get:

Confusion Matrix (Test Set):
 [[106 6]
 [ 5 83]]

As we can see, the performance of the RF is better than the one of a single DT because this confusion matrix has fewer non-diagonal elements (FP & FN) and more diagonal elements (TP & TN), as we’d like.

Conclusions

In this article, we’ve discussed how ensemble learning can improve the performance of a single ML model, by starting from a DT model and ending with a RF.

References:

[1]: Hands-On Machine Learning with Scikit-Learn & Tensorflow. Aurelien Gueron

[2]: Machine Learning with PyTorch ans Scikit-learn. Sebastian Raschka, Yuxi Liu, Vahid Mirjalili

NOTE: even where not specifically expressed with a page number, references must be considered as per [1] and [2].

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI