Comprendre la forêt aléatoire

Comment l’algorithme fonctionne et pourquoi il est si efficace

Une grande partie de l’apprentissage automatique est la classification – nous voulons savoir à quelle classe (ou groupe) appartient une observation. La capacité à classer précisément des observations est extrêmement précieuse pour diverses applications commerciales, comme prédire si un utilisateur particulier achètera un produit ou prévoir si un prêt donné fera défaut ou non.
La science des données offre une pléthore d’algorithmes de classification tels que la régression logistique, la machine à vecteurs de support, le classificateur de Bayes naïf et les arbres de décision. Mais au sommet de la hiérarchie des classificateurs se trouve le classificateur de la forêt aléatoire (il y a aussi le régresseur de la forêt aléatoire, mais c’est un sujet pour un autre jour).
Dans cet article, nous examinerons le fonctionnement des arbres de décision de base, la manière dont les arbres de décision individuels sont combinés pour former une forêt aléatoire et, enfin, nous découvrirons pourquoi les forêts aléatoires sont si efficaces.

 

Il est probablement plus facile de comprendre le fonctionnement d’un arbre de décision à travers un exemple.
Imaginons que notre ensemble de données soit constitué des chiffres figurant en haut de la figure de gauche. Nous avons deux 1 et cinq 0 (les 1 et les 0 sont nos classes) et nous souhaitons séparer les classes en utilisant leurs caractéristiques. Ces caractéristiques sont la couleur (rouge ou bleu) et le fait que l’observation soit soulignée ou non. Comment pouvons-nous faire cela ?
La couleur semble être une caractéristique assez évidente pour séparer les classes, car tous les 0 sauf un sont bleus. Nous pouvons donc utiliser la question « Est-ce rouge ? » pour diviser notre premier nœud. Dans un arbre, un nœud est le point où le chemin se divise en deux : les observations qui répondent aux critères sont placées sur la branche Oui et celles qui ne le font pas sur la branche Non.
La branche « Non » (les bleus) contient tous les 0, nous en avons donc terminé, mais notre branche « Oui » peut encore être divisée. Nous pouvons maintenant utiliser la deuxième fonction et demander « Est-ce souligné ? » pour effectuer une deuxième division.
Les deux 1 qui sont soulignés descendent dans la sous-branche Oui et le 0 qui n’est pas souligné descend dans la sous-branche Droite et nous avons terminé. Notre arbre de décision a pu utiliser les deux caractéristiques pour diviser parfaitement les données. Victoire !
Bien entendu, dans la vie réelle, nos données ne seront pas aussi propres, mais la logique employée par un arbre de décision reste la même. À chaque nœud, il se demande –
Quelle caractéristique me permettra de diviser les observations en question de manière à ce que les groupes résultants soient aussi différents les uns des autres que possible (et que les membres de chaque sous-groupe résultant soient aussi semblables les uns aux autres que possible) ?

Le classificateur Random Forest

La forêt aléatoire, comme son nom l’indique, se compose d’un grand nombre d’arbres décisionnels individuels qui fonctionnent comme un ensemble. Chaque arbre individuel de la forêt aléatoire émet une prédiction de classe et la classe ayant reçu le plus de votes devient la prédiction de notre modèle (voir la figure ci-dessous).

Le concept fondamental de la forêt aléatoire est simple mais puissant : la sagesse des foules. En termes de science des données, la raison pour laquelle le modèle de forêt aléatoire fonctionne si bien est la suivante :
Un grand nombre de modèles (arbres) relativement non corrélés fonctionnant comme un comité sera plus performant que n’importe lequel des modèles individuels qui le composent.
La faible corrélation entre les modèles est la clé. Tout comme les investissements à faible corrélation (comme les actions et les obligations) se regroupent pour former un portefeuille qui est plus grand que la somme de ses parties, les modèles non corrélés peuvent produire des prédictions d’ensemble qui sont plus précises que toutes les prédictions individuelles. Cet effet merveilleux s’explique par le fait que les arbres se protègent mutuellement de leurs erreurs individuelles (tant qu’ils ne se trompent pas tous constamment dans la même direction). Si certains arbres peuvent se tromper, de nombreux autres arbres auront raison, de sorte qu’en tant que groupe, les arbres sont capables d’évoluer dans la bonne direction. Les conditions préalables à une bonne performance de la forêt aléatoire sont donc les suivantes :
• Il doit y avoir un signal réel dans nos caractéristiques pour que les modèles construits à l’aide de ces caractéristiques soient plus performants que les suppositions aléatoires.
• Les prédictions (et donc les erreurs) faites par les arbres individuels doivent avoir de faibles corrélations entre eux.

Un exemple qui montre pourquoi les résultats non corrélés sont si importants
Les effets merveilleux de l’existence de nombreux modèles non corrélés sont un concept si important que je souhaite vous montrer un exemple pour vous aider à le comprendre. Imaginez que nous jouions au jeu suivant :
J’utilise un générateur de nombres aléatoires uniformément distribués pour produire un nombre.
Si le nombre que je génère est supérieur ou égal à 40, vous gagnez (vous avez donc 60 % de chances de gagner) et je vous verse de l’argent. S’il est inférieur à 40, je gagne et vous me versez la même somme.
Je vous propose maintenant les choix suivants. Nous pouvons soit :
Jeu 1 – jouer 100 fois, en misant 1 $ à chaque fois.
Jeu 2 – jouer 10 fois, en misant 10 $ à chaque fois.
Jeu 3 – jouer une fois, en misant 100 $.
Lequel choisiriez-vous ? La valeur attendue de chaque jeu est la même :
Valeur attendue du jeu 1 = (0,60*1 + 0,40*-1)*100 = 20
Valeur attendue du jeu 2 = (0,60*10 + 0,40*-10)*10 = 20
Valeur attendue du jeu 3 = 0,60*100 + 0,40*-100 = 20

 

Qu’en est-il des distributions ? Visualisons les résultats à l’aide d’une simulation de Monte Carlo (nous allons effectuer 10 000 simulations de chaque type de jeu ; par exemple, nous allons simuler 10 000 fois les 100 parties du jeu 1). Regardez le graphique de gauche – quel jeu choisiriez-vous ? Même si les valeurs attendues sont les mêmes, les distributions des résultats sont très différentes, allant de positives et étroites (bleu) à binaires (rose).
Le jeu 1 (où nous jouons 100 fois) offre les meilleures chances de gagner de l’argent – sur les 10 000 simulations que j’ai effectuées, vous gagnez de l’argent dans 97 % d’entre elles ! Pour le jeu 2 (où nous jouons 10 fois), vous gagnez de l’argent dans 63% des simulations, ce qui représente une baisse drastique (et une augmentation drastique de votre probabilité de perdre de l’argent). Et pour le jeu 3 que nous ne jouons qu’une fois, vous gagnez de l’argent dans 60% des simulations, comme prévu.

Ainsi, même si les jeux ont la même valeur attendue, leurs distributions de résultats sont complètement différentes. Plus nous divisons notre mise de 100 $ en différents jeux, plus nous sommes sûrs de gagner de l’argent. Comme indiqué précédemment, cela fonctionne parce que chaque jeu est indépendant des autres.
Il en va de même pour la forêt aléatoire : chaque arbre est comme un jeu dans notre partie précédente. Nous venons de voir comment nos chances de gagner de l’argent augmentent avec le nombre de fois où nous jouons. De même, avec un modèle de forêt aléatoire, nos chances de faire des prédictions correctes augmentent avec le nombre d’arbres non corrélés dans notre modèle.
Si vous souhaitez exécuter le code pour simuler le jeu vous-même, vous pouvez le trouver sur mon GitHub ici.

S’assurer que les modèles se diversifient les uns les autres

Comment la forêt aléatoire s’assure-t-elle que le comportement de chaque arbre individuel n’est pas trop corrélé avec le comportement des autres arbres du modèle ? Elle utilise les deux méthodes suivantes :
Bagging (agrégation bootstrap) – Les arbres de décision sont très sensibles aux données sur lesquelles ils sont formés – de petites modifications de l’ensemble de formation peuvent entraîner des structures d’arbre significativement différentes. La forêt aléatoire tire parti de ce phénomène en permettant à chaque arbre individuel d’échantillonner aléatoirement l’ensemble de données avec remplacement, ce qui donne des arbres différents. Ce processus est connu sous le nom de bagging.
Notez qu’avec la mise en sac, nous ne sous-ensemblons pas les données d’entraînement en petits morceaux et n’entraînons pas chaque arbre sur un morceau différent. Au contraire, si nous disposons d’un échantillon de taille N, nous alimentons toujours chaque arbre avec un ensemble d’apprentissage de taille N (sauf indication contraire). Mais au lieu des données d’apprentissage originales, nous prenons un échantillon aléatoire de taille N avec remplacement. Par exemple, si nos données d’apprentissage étaient [1, 2, 3, 4, 5, 6], nous pourrions donner à l’un de nos arbres la liste suivante [1, 2, 2, 3, 6, 6]. Remarquez que les deux listes ont une longueur de six et que « 2 » et « 6 » sont tous deux répétés dans les données d’apprentissage sélectionnées au hasard que nous donnons à notre arbre (parce que nous échantillonnons avec remplacement).

 

Cet article a été inspiré par : Understanding Random Forest de Tony Yiu