Random Forest, c'est quoi ?

Introduction

Les Forêts Aléatoires ou Random Forest sont parmi les méthodes de Machine Learning les plus populaires grâce à leur précision, leur robustesse et leur facilité d'utilisation. Elles fournissent également deux méthodes pour la sélection de variables: la diminution moyenne de l'impureté et la diminution moyenne de précision (que nous verrons dans un prochain ). Random forest est un cas particulier de la méthode dite de Bagging.

Le Bagging (Bootstrap Aggregating)

Le Bagging (Bootstrap Aggregating) a été proposé par Leo Breiman en 1994 pour améliorer la classification en combinant les classifications d'ensembles d'entraînement générés aléatoirement.

Cette méthode peut réduire considérablement la variance des procédures instables (comme les arbres de décision), ce qui permet d'améliorer les prévisions, mais toute structure de modèle simple et interprétable (comme celle d'un arbre de décision) est perdue.

Soit un ensemble de $N$ observations indépendantes $$X1, \dots, XM$$, chacune de variance $\sigma^2$, la variance de la moyenne vaut ${\sigma^2}/N$. Donc faire la moyenne d'un ensemble d'observation permet de réduire la variance. Partant de cette observation, le bagging réduit la variance (et donc améliore la précision de prédiction) des méthodes de Machine Learning en utilisant ce principe.

L'idée serait alors de prendre plusieurs échantillons d'entraînement à partir de la population, créer un modèle sur chacun de ces échantillons et faire la moyenne des prédictions. En pratique, nous n'avons pas accès à ces échantillons d'entraînement, à la place nous créons des échantillons Bootstrap.

Qu'est-ce que le Bootstrapping ?

Le Bootstrapping est une méthode échantillonnage aléatoire avec remise. En statistique, cette méthode est utilisée pour calculer l'erreur type et les intervalles de confiance d'une statistique (comme la moyenne) afin d'obtenir une mesure de sa précision.

Pour créer un échantillon bootstrap la méthode est la suivante :

Soit $X$ un ensemble de données de $N$ éléments. Nous pouvons créer un nouvel échantillon appelé échantillon bootstrap à partir de $X$ en tirant $N$ éléments aléatoirement et uniformément, avec remise.

En d'autres termes, on sélectionne un élément aléatoirement à partir du jeu de données initial de taille $N$, et nous faisons ça $N$ fois.

bootstraping-schema

Fonctionnement du Bagging

La méthode est la suivante :

soit $X$ le jeu de données que l'on souhaite modéliser. En utilisant la méthode de bootstrapping, nous pouvons créer des échantillons $X1, \dots, XN$ similaires au jeu de données initial

  • pour chaque échantillon bootstrap, nous entraînons un modèle $a_i(x)$
  • le modèle final $a(x)$ agrège les sorties de tous les modèles individuels. Dans le cas de la classification, cette technique correspond à effectuer un vote $a(x) = \frac{1}{N}\sum{i = 1}^N ai(x)$

bagging-schema


Note

Dans le cas particulier de l'algorithme Random Forest, les modèles $a_i$ utilisés sont des arbres de décision, mais dans le cas général cette méthode peut s'appliquer avec n'importe quels modèles.


Random Forest

Principe

Les arbres de décision sont des algorithmes très utilisés mais qui présentent un défaut majeur : leur variance élevée càd (...).

L'algorithme Random Forest est donc un cas particulier de Bagging avec cependant une amélioration : chaque arbre de décision va utiliser un sous-ensemble de variables (aléatoire) pour s'entrainer. C'est un processus permettant de décorréler les arbres entre eux permettant ainsi une diminution significative de la variance par rapport à un seul arbre.


Note

Soit $m$ le nombre de variables utilisées par chaque arbre de décision et $n$ le nombre total de variables :

  • Les valeurs par défaut de $m$ recommandées sont $m = n/3$ pour les problèmes de régression et $m = \sqrt{n}$ pour les problèmes de classification
  • la valeur optimale pour $m$ dépend du problème, c'est donc un paramètre à ajuster

Avantages et inconvénients

Exemple

Implémentation en python

Dans cette partie nous allons voir une implémentation simple des concepts vus précédemment.


Note

En pratique, pour utiliser l'algorithme Random Forest en Python on ne l'implémente pas de zéro, on l'importe directement depuis la bibliothèque scikit-learn. Ici nous le faisons pour l'exercice.


Importons les modules utiles à l'implémentation du Random Forest (pour la classification). Aujourd'hui, nous n'allons pas entrer dans les détails de l'implémentation des arbres de décision, donc nous allons l'importer directement depuis le package scikit-learn.

import random
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score

Initialisation de la classe

Créons une classe pour notre Random Forest. Le constructeur initialisera notre objet avec les variables suivantes:

  • n_estimators : entier désignant le nombre d'arbres de la forêt
  • max_depth : entier désignant la profondeur maximale de chaque arbre de décision
  • max_features : entier désignant le nombre de variables à considérer pour chaque arbre
class RandomForestClassifier:
    def __init__(self, n_estimators=100, max_depth=None, 
                max_features=None):
        self.n_estimators = n_estimators 
        self.max_depth = max_depth 
        self.max_features = max_features             

Phase d'apprentissage : la méthode "fit"

Ajoutons la méthode "fit" à notre classe, c'est elle qui va permettre de construire la forêt en prenant les paramètres suivants:

  • X : array de dimensions (n_samples, n_features) avec n_samples le nombre d'échantillons de données dont nous disposons et n_features le nombre de variables du jeu de données, par exemple dans.
  • y : array de dimensions (n_samples,) contenant les valeurs de la varible cible (ici ...)
def fit(self, X, y):
    #nous allons stocker les arbres dans une liste
    self.trees = [] 
    #pour chaque arbre, nous allons stocker les indices des variables sélectionnées 
    self.feature_ids = []

la sélection de nombreuses variables augmente la force des arbres individuels tandis que la réduction du nombre d'entités conduit à une corrélation plus faible entre les arbres, augmentant la force de la forêt dans son ensemble.

Empiriquement, le nombre de variabes optimal à utiliser vaut $\sqrt{n_features}$ où $n_features$ représente le nombre total de variables du jeu de données

    #nombre de variables total du jeu de données
    self.n_features = X.shape[1]
    if self.max_features == None:
        self.max_features = int(np.sqrt(self.n_features))

Nous allons maintenant faire une boucle sur le nombre d'arbres n_estimators que nous voulons créer

    for k in range(self.n_estimators):
        #nombre aléatoire de variables sans remise
        ids = np.random.choice([k for k in range(self.n_features)],
                               self.max_features, replace=False) 
        self.feature_ids.append(ids) 
        #on génère aléatoirement les indices des échantillons 
        indices = np.random.choice([k for k in range(len(X))], len(X), 
                                    replace=True) 
        #on crée un échantillon bootstrap des données
        bootstrap_sample_X = X[indices, :] 
        bootstrap_sample_y = y[indices] 
        #on entraine un arbre de décision sur cet échantillon puis on le stocke
        tree = DecisionTreeClassifier(max_depth=self.max_depth,
                                      max_features=self.max_features,
                                      random_state=self.random_state)
        self.trees.append(tree.fit(bootstrap_sample_X[:, ids],
                                          bootstrap_sample_y))
            
        return self 

Nous avons utilisé le slicing avec numpy pour facilement selectionner les échantillons que l'on voulait les dans arrays X et y

Maintenant que nous pouvons entrainer notre forêt d'arbres, il ne reste plus qu'a définir comment faire les prédictions.

Faire des prédictions : les méthodes "predict_proba" et "predict"

La méthode predict_proba sert à

Pour l'implémentation, nous allons calculer un vecteur de probabilités pour chaque arbres, puis faire la moyenne de tous ces vecteurs

def predict_proba(self, X):
    probas = []
    #pour chaque arbre, on calcule un vecteur de probabilités
    for k in range(len(self.trees)): 
        #on récupère l'arbre "numéro k"
        tree = self.trees[k]
        #on récupère les indices des variables utilisées par cet arbre
        ids = self.feature_ids[k]
        #on calcule un vecteur de probabilités avec cet arbre
        probas.append(tree.predict_proba(X[:, ids]))

    #on retourne la moyenne
    return np.mean(probas, axis=0) 

La méthode predict sert à prédire les classes, elle retourne un vecteur qui contient les numéros des classes. Pour le calculer c'est simple nous allons utiliser le vecteur de probabilités

def predict(self, X):
    #vecteur de probabilités avec deux colonnes
    p = self.predict_proba(X)
    return np.argmax(p, axis=1)

Lien vers le code

Exemple

Conclusion

Pour résumer,

Soriba

J'écris sur des concepts de Data Science, n'hésitez pas à prendre contact sur mes réseaux !