1 La forêt aléatoire
La forêt aléatoire (random forests) est une méthode ensembliste puissante, largement utilisée pour les tâches de classification et de régression. Elle combine la simplicité des arbres de décision et l’échantillonnage des observations et des variables avec la puissance de l’agrégation pour améliorer les performances prédictives et réduire le risque de surapprentissage (overfitting).
1.1 Principe de la forêt aléatoire
La forêt aléatoire est une extension du bagging, présenté dans la section ?@sec-bagging-detail. Elle introduit un niveau supplémentaire de randomisation dans la construction des arbres, puisqu’à chaque nouvelle division (noeud), le critère de séparation est choisi en considérant uniquement un sous-ensemble de variables sélectionné aléatoirement. Cette randomisation supplémentaire réduit la corrélation entre les arbres, ce qui permet de diminuer la variance des prédiction du modèle agrégé.
Les forêts aléatoires reposent sur quatre éléments essentiels:
Les arbres CART: Les modèles élémentaires sont des arbres CART non élagués, c’est-à-dire autorisés à pousser jusqu’à l’atteinte d’un critère d’arrêt défini en amont.
L’échantillonnage bootstrap: Chaque arbre est construit à partir d’un échantillon aléatoire du jeu de données d’entraînement tiré avec remise (ou parfois sans remise).
La sélection aléatoire de variables : Lors de la construction d’un arbre, à chaque nœud de celui-ci, un sous-ensemble aléatoire de variables est sélectionné. La meilleure division est ensuite choisie parmi ces caractéristiques aléatoires.
L’agrégation des prédictions : Comme pour le bagging, les prédictions de tous les arbres sont combinées. On procède généralement à la moyenne (ou à la médiane) des prédictions dans le cas de la régression, et au vote majoritaire (ou à la moyenne des probabilités prédites pour chaque classe) dans le cas de la classification.
1.3 Pourquoi les forêts aléatoires sont-elles performantes?
Les propriétés théoriques des forêts aléatoires permettent de comprendre pourquoi (et dans quelles situations) elles sont particulièrement robustes et performantes.
1.3.1 Réduction de la variance par agrégation
L’agrégation de plusieurs arbres permet de réduire la variance globale du modèle, ce qui améliore la stabilité des prédictions. Lorsque les estimateurs sont (faiblement) biaisés mais caractérisés par une variance élevée, l’agrégation permet d’obtenir un estimateur avec un biais similaire mais une variance réduite. La démonstration est identique à celle présentée dans la section ?@sec-bagging-detail.
1.3.2 Convergence et limite théorique au surapprentissage
Bien qu’elle s’avèrent très performantes en pratique, il n’est pas prouvé à ce stade que les forêts aléatoires convergent vers une solution optimale lorsque la taille de l’échantillon tend vers l’infini (Louppe (2014)). Plusieurs travaux théoriques ont toutefois fourni des preuves de convergence pour des versions simplifiées de l’algorithme (par exemple, Biau (2012)).
Par ailleurs, une propriété importante des forêts aléatoires démontrée par Breiman (2001) est que leur erreur de généralisation, c’est-à-dire l’écart entre les prédictions du modèle et les résultats attendus sur des données jamais vues (donc hors de l’échantillon d’entraînement), diminue à mesure que le nombre d’arbres augmente et converge vers une valeur constante. Autrement dit, la forêt aléatoire ne souffre pas d’un surapprentissage croissant avec le nombre d’arbres. La conséquence pratique de ce résultat est qu’inclure un (trop) grand nombre d’arbres dans le modèle n’en dégrade pas la qualité, ce qui contribue à la rendre particulièrement robuste. En revanche, une forêt aléatoire peut souffrir de surapprentissage si ses autres hyperparamètres sont mal choisis (des arbres trop profonds par exemple).
1.3.3 Facteurs influençant l’erreur de généralisation
L’erreur de généralisation des forêts aléatoires est influencée par deux facteurs principaux :
La puissance prédictrice des arbres individuels : Les arbres doivent être suffisamment prédictifs pour contribuer positivement à l’ensemble, et idéalement sans biais.
La corrélation entre les arbres : Moins les arbres sont corrélés, plus la variance de l’ensemble est réduite, car leurs erreurs tendront à se compenser. Inversement, des arbres fortement corrélés auront tendance à faire des erreurs similaires, donc agréger un grand nombre d’arbres n’apportera pas grand chose.
On peut mettre en évidence ces deux facteurs dans le cas d’une forêt aléatoire utilisée pour une tâche de régression (où l’objectif est de minimiser l’erreur quadratique moyenne). Dans ce cas, la variance de la prédiction du modèle peut être décomposée de la façon suivante:
\[ \text{Var}(\hat{f}(x)) = \rho(x) \sigma(x)^2 + \frac{1 - \rho(x)}{M} \sigma(x)^2 \]
où \(\rho(x)\) est le coefficient de corrélation moyen entre les arbres individuels, \(\sigma(x)^2\) est la variance d’un arbre individuel, \(M\) est le nombre d’arbres dans la forêt. Cette décomposition fait apparaître l’influence de la corrélation entre les arbres sur les performance de la forêt aléatoire:
- Si \(\rho(x)\) est proche de 1 (forte corrélation entre les arbres) : la première composante \(\rho \sigma^2\) domine et la réduction de variance est moindre lorsque le nombre d’arbres augmente.
- Si \(\rho(x)\) est proche de 0 (faible corrélation entre les arbres) : la seconde composante \(\frac{1 - \rho}{M} \sigma^2\) et la variance est davantage réduite avec l’augmentation du nombre d’arbres \(M\).
L’objectif de l’entraînement des forêts aléatoires est donc de minimiser la corrélation entre les arbres tout en maximisant leur capacité à prédire correctement, ce qui permet de réduire la variance globale sans augmenter excessivement le biais. La sélection aléatoires des caractéristiques (features) à chaque nœud joue un rôle majeur dans cet arbitrage entre puissance prédictive des arbres et corrélation entre arbres.
1.4 Evaluation des performances par l’erreur Out-of-Bag (OOB)
La forêt aléatoire présente une particularité intéressante et très utile en pratique: il est possible d’évaluer les performances d’une forêt aléatoire directement à partir des données d’entraînement, grâce à l’estimation de l’erreur Out-of-Bag (OOB). Cette technique repose sur le fait que chaque arbre est construit à partir d’un échantillon bootstrap, c’est-à-dire un échantillon tiré avec remise. Cela implique qu’une part conséquente des observations ne sont pas utilisées pour entraîner un arbre donné. Ces observations laissées de côté forment un échantillon dit out-of-bag, que l’on peut utiliser pour évaluer la performance de chaque arbre. On peut donc construire pour chaque observation du jeu d’entraînement une prédiction qui agrège uniquement les prédictions des arbres pour lesquels cette observation est out-of-bag; cette prédiction n’est pas affectée par le surapprentissage (puisque cette observation n’a jamais été utilisée pour entraîner ces arbres). De cette façon, il est possible d’évaluer correctement la performance de la forêt aléatoire en comparant ces prédictions avec la variable-cible à l’aide d’une métrique bien choisie.
La procédure d’estimation de l’erreur OOB se déroule comme ceci:
- Entraînement de la forêt aléatoire: la forêt aléatoire est entraînée sur les données d’entraînement selon la procédure détaillée ci-dessus.
- Prédiction out-of-bag : Pour chaque observation \((x_i, y_i)\) des données d’entraînement, on calcule la prédiction de tous les arbres pour lesquels elle fait partie de l’échantillon out-of-bag.
- Agrégation des prédictions : La prédiction finale est obtenue en agrégeant les prédictions selon la procédure standard détaillée ci-dessus (moyenne pour la régression, vote majoritaire pour la classification).
- Calcul de l’erreur OOB : L’erreur OOB est ensuite calculée en comparant les prédictions avec la variable-cible \(y\) sur toutes les observations, à l’aide d’une métrique (précision, rappel, AUC, erreur quadratique moyenne, score de Brier…).
L’utilisation de l’erreur OOB présente de multiples avantages:
- Approximation de l’erreur de généralisation: L’erreur OOB est en général considérée comme une bonne approximation de l’erreur de généralisation, comparable à celle obtenue par une validation croisée.
- Pas besoin de jeu de validation séparé : L’un des principaux avantages de l’erreur OOB est qu’elle ne nécessite pas de réserver une partie des données pour la validation. Cela est particulièrement utile lorsque la taille du jeu de données est limitée, car toutes les données peuvent être utilisées pour l’entraînement tout en ayant une estimation fiable de la performance. Ceci dit, il est malgré tout recommandé de conserver un ensemble de test si la taille des données le permet, car il arrive que l’erreur OOB sous
- Gain de temps : Contrairement à la validation croisée qui requiert de réentraîner plusieurs fois le modèle pour un jeu donné d’hyperparamètres, l’erreur OOB ne nécessite qu’un seul entraînement du modèle. Cela induit un gain de temps appréciable lors de l’optimisation des hyperparamètres.
1.5 Interprétation et importance des variables
Les forêts aléatoires sont des modèles d’apprentissage performants, mais leur complexité interne les rend difficiles à interpréter, ce qui leur vaut souvent le qualificatif de “boîtes noires”. Comprendre l’influence des variables explicatives sur les prédictions est crucial pour interpréter les résutlats et être en mesure d’extraire des connaissances.
L’objectif des méthodes d’interprétabilité (ou d’importance des variables) est d’identifier les variables les plus influentes sur la variable cible, de comprendre les mécanismes prédictifs sous-jacents, et potentiellement d’extraire des règles de décision simples et transparentes. Plusieurs méthodes d’importance des variables existent, mais il est important de comprendre leurs forces et faiblesses.
1.5.1 Mesures d’importance classiques (et leurs biais)
- Réduction moyenne de l’impureté (Mean Decrease in Impurity - MDI) : Cette méthode quantifie l’importance d’une variable par la somme des réductions d’impureté qu’elle induit dans tous les arbres de la forêt. Plus spécifiquement, pour chaque variable, on s’intéresse à la moyenne des réductions d’impureté qu’elle a engendrées dans tous les nœuds de tous les arbres où elle est impliquée. Les variables présentant la réduction moyenne d’impureté la plus élevée sont considérées comme les prédicteurs les plus importants.
La MDI présente des biais importants. Elle est notamment sensible aux variables catégorielles avec de nombreuses modalités, qui peuvent apparaître artificiellement importantes (même si leur influence réelle est faible), ainsi qu’aux variables avec une échelle de valeurs plus étendues, qui obtiennent des scores plus élevés, indépendamment de leur importance réelle. Elle est également fortement biaisée en présence de variables explicatives corrélées, ce qui conduit à surestimer l’importance de variables redondantes. Les interactions entre variables ne sont pas non plus prises en compte de manière adéquate.
- Importance par permutation (Mean Decrease Accuracy - MDA) : Cette méthode évalue l’importance d’une variable en mesurant la diminution de précision du modèle après permutation aléatoire de ses valeurs. Plus spécifiquement, pour chaque variable, les performances du modèle sont comparées avant et après la permutation de ses valeurs. La différence moyenne de performance correspond à la MDA. L’idée est que si l’on permute aléatoirement les valeurs d’une variable (cassant ainsi sa relation avec la cible), une variable importante entraînera une hausse significative de l’erreur de généralisation.
Comme la MDI, la MDA présente des biais lorsque les variables sont corrélées. En particulier, la MDA peut surévaluer l’importance de variables qui sont corrélées à d’autres variables importantes, même si elles n’ont pas d’influence directe sur la cible (Bénard, Da Veiga, and Scornet (2022)).
Plusieurs stratégies peuvent aider à réduire les biais d’interprétation :
- Prétraitement des variables: Standardisation des variables, regroupement des modalités rares des variables catégorielles, réduction de la cardinalité des variables catégorielles.
- Analyse des corrélations: Identification et gestion des variables fortement corrélées, qui peuvent fausser les mesures d’importance.
- Choix de méthodes robustes: Privilégier les méthodes moins sensibles aux biais, comme les CIF ou la Sobol-MDA, et, le cas échéant, SHAFF pour les valeurs de Shapley. Ces méthodes sont présentées dans la sectio suivante.
1.5.2 Méthodes d’importance avancées
Pour pallier les limites des méthodes traditionnelles, des approches plus sophistiquées ont été développées.
Valeurs de Shapley: Les valeurs de Shapley permettent de quantifier la contribution de chaque variable explicative à la variance expliquée de la variable cible, en tenant compte des interactions entre les variables. Elles attribuent à chaque variable une contribution marginale moyenne à la performance du modèle, en considérant toutes les combinaisons possibles de sous-ensembles de variables. Cependant, l’estimation des valeurs de Shapley est computationnellement coûteuse (complexité exponentielle avec le nombre de variables). Des méthodes approximatives existent, mais peuvent introduire des biais. L’algorithme SHAFF (Bénard et al. (2022)) propose une solution rapide et précise à ce problème, en tirant parti des propriétés des forêts aléatoires.
Conditional Inference Forests (CIF): Les CIF (Strobl et al. (2007)), implémentées dans le package party de R (cforest), corrigent certains biais de la MDI en utilisant des tests statistiques conditionnels pour sélectionner les variables et les seuils de coupure dans les arbres. Elles sont particulièrement robustes face aux variables hétérogènes et aux corrélations entre variables. Couplées à un échantillonnage sans remise, les CIF fournissent des mesures d’importance plus fiables.
Sobol-MDA: La Sobol-MDA combine l’idée de la MDA avec une approche basée sur les indices de Sobol, permettant de gérer efficacement les variables dépendantes. Au lieu de permuter les valeurs, elle projette la partition des arbres sur le sous-espace excluant la variable dont on souhaite mesurer l’importance, simulant ainsi son absence. Elle est plus efficace en calcul que les méthodes MDA classiques tout en fournissant une mesure d’importance cohérente, convergeant vers l’indice de Sobol total (la mesure appropriée pour identifier les covariables les plus influentes, même avec des dépendances) (Bénard, Da Veiga, and Scornet (2022)).
1.2 Comment construit-on une forêt aléatoire?
L’entraînement d’une forêt aléatoire est très similaire à celui du bagging et se résume comme suit:
Pour construire la prédiction de la forêt aléatoire une fois celle-ci entraînée, on agrège les arbres selon une méthode qui dépend du problème modélisé:
Les principaux hyper-paramètres des forêts aléatoires (détaillés dans la section ?@sec-guide-rf) sont les suivants: le nombre d’arbres, la méthode et le taux d’échantillonnage, le nombre (ou la proportion) de variables considérées à chaque nœud, le critère de division des nœuds (ou mesure d’hétérogénéité), et les critères d’arrêt (notamment la profondeur de l’arbre, le nombre minimal d’observations dans une feuille terminale, et le nombre minimal d’observations qu’un nœud doit comprendre pour être divisé en deux).