Passer

Algorithme N°2 – Comprendre comment fonctionne un random forest en 5 min

Le random forest est un algorithme incontournable en machine learning. Random forest signifie « forêt aléatoire ». Proposé par Leo Breiman en 2001, c’est un algorithme qui se base sur l’assemblage d’arbres de décision. Il est assez intuitif à comprendre, rapide à entraîner et il produit des résultats généralisables. Seul bémol, le random forest est une boîte noire qui donne des résultats peu lisibles, c’est-à-dire peu explicatifs.

Il est néanmoins possible de limiter cet inconvénient par d’autres techniques de machine learning : ce sera l’objet de notre article N°7 autour de LIME, un algorithme clé pour rendre un modèle explicable.

 

Principe de fonctionnement du random forest

Un random forest est constitué d’un ensemble d’arbres de décision indépendants. 

Chaque arbre dispose d’une vision parcellaire du problème du fait d’un double tirage aléatoire :

  • un tirage aléatoire avec remplacement sur les observations (les lignes de votre base de données). Ce processus s’appelle le tree bagging,
  • un tirage aléatoire sur les variables (les colonnes de votre base de données). Ce processus s’appelle le feature sampling.

A la fin, tous ces arbres de décisions indépendants sont assemblés. La prédiction faite par le random forest pour des données inconnues est alors la moyenne (ou le vote, dans le cas d’un problème de classification) de tous les arbres.

L’idée de base de cet algorithme est assez intuitive. A titre d’exemple, si votre banque vous refuse votre demande de crédit, il y a fort à parier que vous irez consulter une ou plusieurs autres banques. Effectivement, un seul avis ne suffit pas en général pour prendre la meilleure décision.

Le random forest fonctionne sur ce même principe : plutôt que d’avoir un estimateur complexe capable de tout faire, le random forest utilise plusieurs estimateurs simples (de moins bonne qualité individuelle). Chaque estimateur a une vision parcellaire du problème. Ensuite, l’ensemble de ces estimateurs est réuni pour obtenir la vision globale du problème. C’est l’assemblage de tous ces estimateurs qui rend extrêmement performante la prédiction.

 

Genèse de l’algorithme

Le défaut majeur de l’arbre de décision est que sa performance est fortement dépendante de l’échantillon de données de départ. Par exemple, l’ajout de quelques nouvelles données dans la base d’apprentissage peut modifier radicalement le modèle et les résultats.

Pour lutter contre ce défaut, on peut utiliser une multitude d’arbres : une forêt d’arbres. Vous comprenez maintenant le terme de forest contenu dans l’anglicisme random forest.

Et vous l’aurez compris, le terme “random” vient du processus de double tirage aléatoire que l’on applique à chaque arbre, à la fois sur les variables et sur les observations.

 

Illustration pratique de l’algorithme

Une formule à retenir : Random forest = tree bagging + feature sampling.

 

Tree bagging

Le Bagging signifie “bootstrap aggregation”. C’est un processus de tirage aléatoire sur les observations (lignes de données) déterminé par 3 étapes clés :

  • Construction de n arbres de décisions en tirant aléatoirement n échantillons d’observations,
  • Entraînement de chaque arbre de décision,
  • Pour faire une prévision sur de nouvelles données, il faut appliquer chacun de n arbres et prendre la majorité parmi les n prévisions.

 

Feature sampling

C’est un processus de tirage aléatoire sur les variables (colonnes de données). Par défaut, on tire Racine n variables pour un problème à n variables au total.

Pour reprendre l’exemple précédent de l’acceptation de crédit, l’idée de base du feature sampling c’est de demander à chaque banque d’étudier votre demande de prêt à partir d’un accès limité aux informations du client. L’une des banques rendra sa décision en ayant, par exemple, uniquement accès aux informations relatifs à l’âge, à la CSP et au revenu annuel du client. Une autre banque quant à elle, aura uniquement pris connaissance des informations relatives à la situation maritale, au sexe et au nombre de crédits en cours du client, … 

Ce processus permet de baisser la corrélation entre les arbres qui pourrait perturber la qualité des résultats. En statistique, on dit que le feature sampling permet de réduire la variance de l’ensemble créé.

schéma

 

Critère de division/split

Vous le savez un arbre de décisions construit des sous-populations par séparations successives des feuilles d’un arbre.

Il existe différents critères de séparation pour construire un arbre :

  • Le critère de Gini organise la séparation des feuilles d’un arbre en se focalisant sur la classe la plus représentée dans le jeu de données : il faut la séparer le plus rapidement possible.
  • Le critère d’entropie est basé sur la mesure du désordre (comme en thermodynamique) qui règne dans la population étudiée. La construction de l’arbre vise à baisser l’entropie globale des feuilles de l’arbre à chaque étape.

 

Conclusion

Si vous avez bien compris le fonctionnement du random forest, lancez-vous pour découvrir le gradient boosting qui est également une méthode ensembliste.

Dans notre prochain article, vous comprendrez comment fonctionne l’isolation forest qui est l’un des algorithmes modernes et l’un des plus utilisés pour certains cas d’usage en détection d’anomalies ou de fraude.