Random Forest

Introduction

Random forest is an ensemble method. Ensemble methods combine the predictions of several base estimators built with a given learning algorithm in order to improve generalizability on unseen dataset (reducing overfitting or high variance and reducing underfitting or high bias), by increasing the robustness of the ensemble method over a single estimator. More generally, ensemble models can be applied to any base learner beyond trees, in averaging methods such as bagging methods, model stacking, voting, or in boosting.

Random forest is an averaging algorithm ensemble model, making use of a perturb-and-combine techniques: This means a diverse set of classifiers is created by introducing randomness in the classifier construction. The prediction of the ensemble is given as the averaged prediction of the individual classifiers.

Random Forest classifier

As other classifiers, forest classifiers have to be fitted with two arrays: a sparse or dense array X of shape (n_samples, n_features) holding the training samples, and an array Y of shape (n_samples,) holding the target values (class labels) for the training samples.

from sklearn.ensemble import RandomForestClassifier
X = [[0, 0], [1, 1]]
Y = [0, 1]
clf = RandomForestClassifier(n_estimators=10)
clf = clf.fit(X, Y)

Randomness in Random Forests

In random forests, each tree in the ensemble is built from a sample drawn with replacement (i.e., a bootstrap sample) from the training set: a subset of observations is used. Furthermore, when splitting each node during the construction of a tree, the best split is found through an exhaustive search of the feature values of either all input features or a random subset of size max_features, a proces called feature bagging. By default, random forest perform both bootstrapped sampling of observations and feature bagging at each split of the tree.

Each tree in the ensemble is built "stochastically" independent* of the other trees in the forest.

In addition, note that in random forests, bootstrap samples are used by default (bootstrap=True). This means each tree's training set contains the same number of samples as the original dataset, but some samples may be repeated, and others may not be included at all. On average, a bootstrap sample contains about two-thirds of the original unique samples. When turned off, the whole dataset (all observations) will be used. So no sampling is applied.

When using bootstrap sampling the generalization error can be estimated on the left out or out-of-bag samples. This can be enabled by setting oob_score=True.

Random forests are very similar to the procedure of bagging except that they make use of a technique called feature bagging, which has the advantage of significantly decreasing the correlation between each decision tree and thus increasing its predictive accuracy, on average.

Feature bagging works by randomly selecting a subset of the feature dimensions at each split in the growth of individual decision trees. This may sound counterintuitive, after all it is often desired to include as many features as possible initially in order to gain as much information for the model. However, it has the purpose of deliberately avoiding (on average) very strong predictive features that lead to similar splits in trees (and thus increase correlation). That is, if a particular feature is strong in predicting the response value then it will be selected for many trees. Hence, a standard bagging procedure can be quite correlated.

Random forests avoid this by deliberately leaving out these strong features in many of the grown trees. If all values are chosen in splitting of the trees in a random forest ensemble then this simply corresponds to standard bagging. A rule-of-thumb for random forests is to use features, suitably rounded, at each split.

The purpose of these two sources of randomness (max_features and n_estimators) is to decrease the variance of the forest estimator. Indeed, individual decision trees typically exhibit high variance and tend to overfit. The injected randomness in forests yield decision trees with somewhat decoupled prediction errors. By taking an average of those predictions, some errors can cancel out. Random forests achieve a reduced variance by combining diverse trees, sometimes at the cost of a slight increase in bias. In practice the variance reduction is often significant hence yielding an overall better model.

Parameter setting

Explainability

Naive implementation

As discussed, random forest perform both bootstrap sampling of observations and feature bagging. In this naive implementation, we will only look at bootstrapped sampling to see how four decision trees make up a forest and how a random forest uses multiple trees with high variance to come to final vote that has less variance.

Decision trees are deterministic, so with the same dataset, each tree should give the same output. However, when random sampling the observations, the tree can learn a different pattern. Let's look at a practical example.

Dataset for naive Random Forest implementation

#	feature_1	feature_2	label
1	0	4	1
2	0	5	1
3	1	1	1
4	1	2	1
5	1	6	0
6	1	4	1
7	1	3	1
8	2	0	1
9	2	2	1
10	3	5	0
11	3	3	0
12	3	0	1
13	3	1	1
14	3	6	0
15	4	1	1
16	4	2	0
17	4	4	0
18	5	0	1
19	5	2	0
20	5	5	0
21	6	1	0
22	6	6	0
23	6	4	0
24	6	2	0
25	6	0	0

For this example, we'll look at a dataset with 25 instances and two features feature_1 and feature_2 in the context of a binary classification problem. In the image below we can see our dataset. the X axis shows the value for feature_1 and the Y axis shows the value for feature_2 Each dot in the image below represent an instance its color defines the label: a green label represents the positive class (label=1) and a red label represents the negative class (label=0). There are 12 positive labelled instances and 13 negative labelled instances in our dataset.

Image 1: Data distribution

Decision Tree

If we were to train a decision tree model tree.DecisionTreeClassifier(criterion='entropy', max_depth=1) to find the best split in the data to distinguish between a positive and a negative class, it would create a single split line, using the information of feature_1 and feature_2 to split the data.

Image 2: Decision tree with max_depth=1 and criterion='entropy' trained on all data.

The image above shows that it would split the data on feature_1 <= 2.5, using the entropy criterion to find the split that gives the most information gain. The grey line defines the split, everything left of the split is considered a positive class and everything right of the split is considered a negative class.

Random Forest

Random forests make use of bootstrapped sampling (with replacement) and feature bagging. In this example, we only apply bootstrapping, but not feature bagging. All decision trees are trained on both feature_1 and feature_2, on a sample drawn with df.sample(fraction=1.0, resample=True).

Image 3: Four decision trees with max_depth=1 and criterion='entropy' trained on bootstrapped sample data.

As can be seen from the image above, each of the decision tree on its own does not perform better than the initial decision tree (shown in the bottom-left image). For instance, the top-left decision tree correctly classifies 3 negative instances as negative (TN), but incorrectly classifies 4 negative instances as positive (FP).

The true power of a random forest becomes visible once we combine our four decision trees in a single classifier. A naive way to visualise this is to increase the max_depth parameter of our decision tree. A decision tree with more depth can consecutively split on the same two features.

Image 4: A decision tree with max_depth=4, criterion='entropy'.

The image above provides a visual representation of a random forest with four trees, each with max_depth=1, where the final classifier uses the predicted probabilities of each single, high-variance tree. As can be seen from the image, this random forest model is able to make a more complex split, making use of the information of all underlying decision trees. This classifier is able to correctly identify negative labelled instances as negative and all positive labelled instances as positive. In the implementation section we will be able to see that this visual representation is the same as that of the random forest implementation.

• Q: Why not use a Decision Tree with more depth instead of a Random Forest?
• A: Controlling the depth of a decision tree is difficult. Too shallow of a tree may lead to high bias (underfitting) and a tree that is too deep leads to high variance (overfitting). Optimal depth analysis is based on heuristics or cross-validation to find the best performing depth that balances bias and variance.
  
  Decision trees with larger depth are very likely to overfit. Random forests are less likely to overfit.
  
  Random forest are more complex as a whole, but each individual tree is less complex than a very deep, single tree. The ensemble approach creates a more robust model.

Implementing a RandomForestClassifier

# max_features='sqrt' is the default for ensemble.RandomForestClassifier
# line 337 in tree.DecisionTreeClassifier shows how max_features='sqrt' works
n_features_in_ = 2 # feature_1, feature_2
print(max(1, int(np.sqrt(n_features_in_))))
1

# since we want both feature_1 and feature_2, we choose max_features=2
from sklearn import ensemble
rf_estimator = ensemble.RandomForestClassifier(n_estimators=4, criterion='entropy', max_features=2, bootstrap=True)
rf_estimator.fit(X=df[['feature_1', 'feature_2']].values, y=df[['label']].values)

If we fit the rf_estimator and visualise the splits using the same method as done in the naive implementation, we get the image below.

Image 5: A RandomForestClassifier with n_estimators=100, criterion='entropy', max_features=2, bootstrap=True.

Missing values

A Random Forest estimator has native support for missing values (NaNs). During training, the tree grower learns at each split point whether samples with missing values should go to the left or right child, based on the potential gain. When predicting, samples with missing values are assigned to the left or right child consequently. If no missing values were encountered for a given feature during training, then samples with missing values are mapped to whichever child has the most samples.

Warm start

When set to True, reuse the solution of the previous call to fit and add more estimators to the ensemble. It will use the number of estimators as defined in the n_estimators parameter to add to the forest.

Final prediction

• Q: How does a random forest aggregate to get the final prediction?
• A: The predicted class of an input sample is a vote by the trees in the forest, weighted by their probability estimates. That is, the predicted class is the one with highest mean probability estimate across the trees.

In a random forest classifier, the final prediction for an input sample is determined by aggregating the individual predictions of all the trees in the forest. Each tree votes for a class, and the predicted class is the one that receives the highest average probability estimate across all trees. This means the final prediction is not just based on the majority vote of the trees, but also considers the confidence (or probability) associated with each tree's prediction.

In other words, random forests aggregate over the predict_proba probability of the predicted class of all individual trees in the forest. This is in contrast to the original publication, which uses majority voting of the classes (i.e. each tree votes for a single class, majority vote chooses the final predicted class).

The predict_proba of a decision tree is the predicted class probability, the fraction of samples of the same class in the final leaf. A random forest, averages over these probabilities and chooses the highest averaged probability as it's final prediction.

This averaging strategy reduces variance and helps to prevent overfitting. By combining multiple individual predictions, which may have their own errors, the ensemble's collective decision-making process leads to a more stable, accurate, and generalizable result.

predicted_probabilities = rf_estimator.predict_proba(df[['feature_1', 'feature_2']].values)
final_prediction = rf_estimator.predict(df[['feature_1', 'feature_2']].values)
# line 961 in ensemble.RandomForestClassifier shows how the final prediction is made
(np.argmax(predicted_probabilities, axis=1) == final_prediction)
[ True  True  True  True  True  True  True  True  True  True  True  True
  True  True  True  True  True  True  True  True  True  True  True  True
  True]