Training several trees and then bagging them together makes up for several the issues with decision trees. Thanks to that the Random Forest, a forest of randomized decision trees, is a very powerful ensemble classifier.
Such ensembles are some of the most powerful classifiers, these can draw very fluid decision boundaries between several classes at once.
For a start we import the usual stuff and also two ensemble models. Ensemble models will train several models instead of a single one, and then predict from each model and average the results. There are several ways in which groups of models can be trained, and different ensemble techniques perform often very different schemes.
The Random Forest trains trees on subsamples of data, whilst Ada Boost trains several model one based on the results of the previous model. Most commonly Ada Boost is used with trees but other models are also possible.
import numpy as np import pandas as pd import matplotlib.pyplot as plt %matplotlib inline plt.style.use('seaborn-talk') from sklearn.datasets import make_moons from sklearn.tree import DecisionTreeClassifier from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier
Is the technique of training several trees on subsamples of the data,
i.e. each tree does not see the full dataset.
Then we take the majority vote when predicting.
Apart from varying the number of samples each tree will see only a subset of features,
A random forest trains several trees each on a sub-sample of the data
and a sub-sample of the features.
The sub-sampling can be performed bootstrapped (the default in
sklearn) or not.
Bootstrapping means selecting from the dataset with replacement.
The bootstrapped means that each tree sees as many points as the dataset has
but some of the points are likely duplicates since the selection
of the subsamples is with replacement.
The higher randomization increases the variance of the model. But the fact that we train several models and then take the majority vote reduces the variance again. The big advantage of random forests and bagging is the fact that each ensemble model can be trained separately. Which also means that it is easy to parallelize the algorithm across processes or even machines. When using several trees at once we lose the capacity of explaining what the model is doing (white-box), hence the random forest is a black-box model - a model which classification decision is hard to explain by looking at the model itself.
Boosting algorithms take a slightly different approach. They train a very simple model, e.g. a tree that can only split the data once (also called a tree stump). Then the boosting algorithm finds the samples that the very simple model got wrong, and updates the data set to put more weights to these samples. Remember that in most cases in machine learning we have equations where we sum over the data, to put more weight on certain data points we just add a multiplier higher than $1$ against these data points.
Then the boosting algorithm trains a new very simple model (e.g. stump) on the new, updated, dataset. It is likely that the new model will classify/regress the weighted samples correctly, at the expense of the other samples. On the next step the boosting algorithm again evaluates the just trained simple model, and find the samples that this new model got wrong. Now the algorithm puts more weight on the samples badly predicted by the newest model and trains yet another simple model on that set. The algorithm repeats until the maximum number of simple models is reached.
The final answer from the algorithm is either a majority vote, or a weighted vote (weighted by amount of error of each model or by predicted probabilities).
Ada Boost is the original algorithm, with several variants following it. In general, boosting produces a good representation of the dataset structure, which means that is produces very good generalization to new datasets. Yet, the fact that the ensemble construction by boosting cannot be parallelized makes the algorithm less practical for use with very big datasets.
In order to look at a non-linear problem we again we build our four moon data generator.
def make_four_moons(n, noise): X_left, y_left = make_moons(n//2, noise=noise) X_right, y_right = make_moons(n//2, noise=noise) X_right[:, 0] += 3 y_right[:] += 2 X = np.vstack((X_left, X_right)) y = np.hstack((y_left, y_right)) return X, y
And we can have a look at it.
X, y = make_four_moons(2048, noise=.2) fig, ax = plt.subplots(figsize=(16, 9)) colors = ['crimson', 'navy', 'forestgreen', 'indigo'] for i in range(4): ax.plot(X[y == i, 0], X[y == i, 1], 'o', c=colors[i])
We build graphs similar to what we did for decision tress because we will us the decision tree as the basic model of our ensembles. The Random Forest will split the trees for as long as possible, resulting in overfitting in each tree. But the result of averaging several trees that overfit in different places of the datasset produces a very good classification. On thing to note is that we achieve boundaries between classes (i.e. the decision function) that is not straight everywhere as it was with a single decision tree. We use $30$ trees in the Random Forest constructions, provided in the argument.
The Ada Boost attempts to find a good representation
hence it will keep the straight lines.
We explicitly give the type of model Ada Boost should use,
a tree that can split only thrice (
Since our data has several places where three classes are present
at the same time,
splitting only once would never be able to capture the dataset structure.
We use $20$ such trees.
model_l = RandomForestClassifier(n_estimators=30) model_r = AdaBoostClassifier(DecisionTreeClassifier(max_depth=3), n_estimators=20) model_l.fit(X, y) model_r.fit(X, y) fig, (ax_l, ax_r) = plt.subplots(1, 2, figsize=(16, 9)) gx = np.linspace(-2, 6, 256) gy = np.linspace(-2, 2, 256) gx, gy = np.meshgrid(gx, gy) gx, gy = gx.reshape(-1), gy.reshape(-1) y_hat = model_l.predict(np.c_[gx, gy]) ax_l.scatter(gx, gy, c=plt.cm.plasma(y_hat / 4), alpha=0.2, s=10) ax_l.scatter(X[:, 0], X[:, 1], s=60, c=y, cmap='plasma'); ax_l.axis('off') y_hat = model_r.predict(np.c_[gx, gy]) ax_r.scatter(gx, gy, c=plt.cm.plasma(y_hat / 4), alpha=0.2, s=10) ax_r.scatter(X[:, 0], X[:, 1], s=60, c=y, cmap='plasma'); ax_r.axis('off');
At first sight the model produce by the random forest looks better. Both models certainly overfit a lot less than the single decision tree. The Ada Boost ensemble model attempted to identify the structure but straight lines are not a good way of separating this dataset.
Instead we can try a base model that does not separate using straight line.
We did see the logistic regression and that it has a decision function that is curved.
We will take the logistic regression and use it as the base model for boosting,
C=0.7 is slight regularization for the logistic regression.
And we train $20$ such logistic regressions in Ada Boost scheme.
from sklearn.linear_model import LogisticRegression model = AdaBoostClassifier(LogisticRegression(C=0.7), n_estimators=10) model.fit(X, y) fig, ax = plt.subplots(figsize=(14, 7)) gx = np.linspace(-2, 6, 256) gy = np.linspace(-2, 2, 256) gx, gy = np.meshgrid(gx, gy) gx, gy = gx.reshape(-1), gy.reshape(-1) y_hat = model.predict(np.c_[gx, gy]) ax.scatter(gx, gy, c=plt.cm.plasma(y_hat / 4), alpha=0.2, s=10) ax.scatter(X[:, 0], X[:, 1], s=60, c=y, cmap='plasma'); ax.axis('off');