Dans ce chapitre nous allons étudier un modèle célèbre : les forêts aléatoires (ou random forests en anglais). Cette méthode est très utilisée par les data scientists car elle permet des performances plus que raisonnables pour la majorité des problèmes rencontrés.
Pour faire une forêt, il faut des arbres (de décision)
Voyons un exemple (plutôt original 😬) ensemble. Étudions l’arbre de décision pour avoir la probabilité de survie des passagers du Titanic. La caractéristique sibsp représente le nombre total de proches (mari, frères et soeurs) :
Comme on peut le voir, effectuer une classification est relativement simple. Il suffit de répondre au questions en descendant dans l'arbre de décision . Par exemple, les garçons de moins de 9 ans et demi qui avaient moins de 3 proches présents sont classés comme ayant survécu. Ou bien une femme sera automatiquement classée comme ayant survécu par l'arbre de décision. On peut voir notamment comment il est facile d'effectuer de l'overfitting sur les données.
On parle surtout des arbres de classification binaire, dont les embranchements représentent des questions auxquelles on peut répondre par “oui” ou “non”. A force d’ajouter ces questions, on peut arriver à un intervalle de confiance assez élevé, même s'il y a un risque d'overfitting.
Les arbres de décision sont des modèles non-paramétriques et trouvent des règles en général assez puissantes. Ils peuvent traiter des très grands datasets et ils peuvent aussi utiliser des prédicateurs mixtes (catégoriques et nombres). Les variables redondantes sont éliminées, parce que l’arbre ne les prend même pas en compte.
Mais, les prédictions des arbres individuels sont souvent très médiocres, essentiellement à cause de la variance de la prédiction (avec beaucoup de bruit) et de la tendance à overfitter. C’est pour ça que les méthodes ensemblistes existent 😀
Intuition du fonctionnement d'un arbre de décision
Construire un arbre de décision binaire se résume au problème suivant : faire grandir un arbre embranchement par embranchement jusqu'à ce que le "gain d'information" soit maximisé. Si on créé un nouvel embranchement à partir de ce point, le gain sera diminué.
Comment trouve-t-on cet arbre ?
C’est fait à la base (algorithme CART, pour Classification And Regression Tree) par greedy, top-down recursive partitioning algorithm. Houla, ça fait beaucoup, voyons comment décomposer cet algorithme.
Première étape : faire grandir l'arbre
A chaque nœud, on doit donc trouver deux choses : quelle feature utiliser et quel est le point de séparation des deux zones, de sorte à minimiser l’erreur quadratique pour la régression et l’impureté pour la classification. On fait ainsi grandir l’arbre de la manière la plus grande possible (d’où l'adjectif greedy).
Impureté? Kesako?
L'impureté est la mesure probabilistique de la performance de l'arbre de décision. La plus utilisée, notamment pour les forêts aléatoires, est l’index d’impureté de Gini. C’est à l’aide de cette impureté que nous allons pouvoir choisir notre point de séparation, en testant toutes les valeurs possibles sur une feature choisie.
Seconde étape : élaguer l'arbre
Comme on peut l’imaginer, l’idée de coller autant aux données d’entraînement pour construire son modèle conduit facilement à l'overfitting. Une des techniques qui permet de réduire cet overfitting pour un arbre, c’est l’élagage. Pour élaguer l’arbre, il s'agit de prendre en compte le coût de la complexité du modèle. En effet, on ne peut faire grandir un arbre jusqu’à identifier chaque observation comme une feuille. On doit donc choisir entre la qualité de l’ajustement de l’arbre sur les observations et la complexité du modèle. Celui-ci ne doit pas être trop complexe sous peine d’overfitting.
Les forêts aléatoires, avantages sur le bagging
L’élagage étudié au chapitre précédent est une manière de réduire l’overfitting. Une autre manière de le réduire est d’utiliser une méthode ensembliste, en l’occurence les forêts aléatoires. Les forêts aléatoires sont donc un ensemble d’arbres de décisions entraînés individuellement, légèrement différents les uns des autres. Pour prédire une nouvelle valeur, on effectue la classification pour chaque arbre de cette forêt. La forêt choisit la valeur ayant le plus de votes parmi tous ses arbres. Ce n'est pas plus compliqué que ça !
L’idée derrière les forêts aléatoires est que chaque arbre de décision overfit (c'est prévu !) sur une partie des données, tout en possédant une bonne capacité de prédiction. Toute la subtilité réside, vous l’avez deviné, dans la sélection de l’échantillon à utiliser pour créer chaque arbre, car on veut qu’ils soient tous différents. Pour cela, on va bootstraper le jeu de données, c’est à dire que si on a un jeu de données de N entrées, alors on créé un échantillon aléatoire de N entrées (mais avec remplacement). Ce sera le jeu données qui nous servira pour cet arbre en question.
Créer notre forêt d'arbres de décision
Pour la création de chaque arbre de décision, on va différer légèrement de CART afin que nos arbres ne se ressemblent pas trop. Si on a M features d’entrée, on choisit un nombre m << M tel qu’a chaque nœud de notre arbre on sélectionne m features parmi les M aléatoirement et le meilleur « point de séparation ». Ce m est gardé constant durant la création de la forêt aléatoire. Tous les arbres sont créés sans élagage, contrairement à CART, on essaie ici de créer l’arbre avec les meilleures performances par validation croisée.
La performance de notre forêt aléatoire dépend alors de deux paramètres :
La corrélation entre n’importe quelle paire de deux arbres de la forêt. Si la corrélation augmente, l’erreur augmente (puisque la variance est plus forte).
La performance de chaque arbre pris individuellement. Plus les performances de l'arbre individuel sont importantes, plus la forêt aura de chance d’être globalement performante.
Vous l’aurez deviné, le mystérieux hyperparamètre m permet à la fois d’augmenter la performance des arbres individuellement, puisque l’augmenter crée un critère de séparation plus précis. Il permet aussi de réduire la corrélation entre les différents arbres, puisque les points de séparation sont moins susceptibles d’être les mêmes. C’est bien sûr au détriment de la vitesse d’exécution de l’algorithme puisque l'on augmente la complexité du modèle.
Quelques-uns des (nombreux) avantages des forêts aléatoires
Les forêts aléatoires sont un algorithme possédant de très bonnes performances assez facilement sur la plupart des problèmes que vous rencontrerez. C’est un go-to à tester dès le départ en abordant un problème de modélisation, sans trop besoin de faire de feature engineering en amont. De plus, il fonctionne bien sur les grosses bases de données, car il ne possède pas une si grosse complexité pour l’entraînement. Ceci-dit si vous êtes en présence d'un dataset volumineux, vous pouvez effectuer une parallélisation des calculs sur plusieurs CPU (avec l'argument n_jobs dans scikit-learn).
Les forêts aléatoires permettent une certaine interprétabilité. Elles forment donc une black-box pas complètement « black » ! On peut en effet effectuer une estimation de l’importance des différentes features (nous verrons cela dans le TP).
Elles permettent de nombreuses applications telles que du clustering, de la détection d’outliers... en exploitant une méthode qui permet le calcul de proximité entre les paires de données.
Encore une fois, ce modèle est rapide. En plus, les forêts n’overfittent pas (!). Le problème de taille mémoire pour de gros jeux de données est le stockage du jeu de données lui-même.
Les forêts aléatoires sont donc à utiliser sans modération !
Conclusion
En raison des nombreux avantages que l'on vient d'évoquer, les forêts aléatoires constituent un outil essentiel de l'arsenal du data scientist. Il convient de l'utiliser avec rigueur, cependant, dans le choix des hyperparamètres afin d'obtenir des performances satisfaisantes. Il faut aussi ajouter une bonne dose de feature engineering pour améliorer la rapidité, si cela est nécessaire.
