Forêts d'arbres décisionnels

Une forêt d'arbres aléatoires (RF) est un ensemble d'arbres de décision dans lequel chaque arbre de décision est entraîné avec un bruit aléatoire spécifique. Les forêts d'arbres aléatoires sont la forme la plus populaire d'ensemble d'arbres de décision. Cet article présente plusieurs techniques permettant de créer des arbres de décision indépendants afin d'améliorer les chances de créer une forêt aléatoire efficace.

Mise en sac

Le bagging (bootstrap aggregating) consiste à entraîner chaque arbre de décision sur un sous-ensemble aléatoire des exemples de l'ensemble d'entraînement. En d'autres termes, chaque arbre de décision de la forêt aléatoire est entraîné sur un sous-ensemble d'exemples différent.

Le bagging est particulier. Chaque arbre de décision est entraîné sur le même nombre d'exemples que dans l'ensemble d'entraînement d'origine. Par exemple, si l'ensemble d'entraînement d'origine contient 60 exemples, chaque arbre de décision est entraîné sur 60 exemples. Toutefois, le bagging n'entraîne chaque arbre de décision que sur un sous-ensemble (généralement 67%) de ces exemples. Par conséquent, certains de ces 40 exemples du sous-ensemble doivent être réutilisés lors de l'entraînement d'un arbre de décision donné. Cette réutilisation est appelée "entraînement avec remplacement".

Par exemple, le tableau 6 montre comment le bagging peut distribuer six exemples sur trois arbres de décision. Notez les points suivants :

  • Chaque arbre de décision est entraîné sur un total de six exemples.
  • Chaque arbre de décision est entraîné sur un ensemble d'exemples différent.
  • Chaque arbre de décision réutilise certains exemples. Par exemple, l'exemple 4 est utilisé deux fois dans l'entraînement de l'arbre de décision 1. Par conséquent, le poids appris de l'exemple 4 est effectivement doublé dans l'arbre de décision 1.

Tableau 6. Bagging de six exemples d'entraînement sur trois arbres de décision. Chaque nombre représente le nombre de fois où un exemple d'entraînement donné (1 à 6) est répété dans l'ensemble de données d'entraînement d'un arbre de décision donné (1 à 3).

exemples d'entraînement
#1 #2 #3 #4 #5 #6
ensemble de données d'origine 1 1 1 1 1 1
arbre de décision 1 1 1 0 2 1 1
arbre de décision 2 3 0 1 0 2 0
arbre de décision 3 0 1 3 1 0 1

Dans le bagging, chaque arbre de décision est presque toujours entraîné sur le nombre total d'exemples de l'ensemble d'entraînement d'origine. Entraîner chaque arbre de décision sur un plus grand nombre ou un plus petit nombre d'exemples tend à dégrader la qualité de la forêt aléatoire.

Bien qu'il ne figure pas dans l'article original sur la forêt d'arbres aléatoires, l'échantillonnage d'exemples est parfois effectué "sans remplacement", c'est-à-dire qu'un exemple d'entraînement ne peut pas apparaître plus d'une fois dans un ensemble d'entraînement d'arbre de décision. Par exemple, dans le tableau précédent, toutes les valeurs sont égales à 0 ou à 1.

Code YDF
Vous pouvez activer l'entraînement sans remplacement avec l'affectation suivante dans YDF: bootstrap_training_dataset=False

Échantillonnage des attributs

L'échantillonnage des attributs signifie qu'au lieu de rechercher la meilleure condition pour toutes les fonctionnalités disponibles, seul un sous-ensemble aléatoire de fonctionnalités est testé à chaque nœud. L'ensemble des caractéristiques testées est échantillonné de manière aléatoire à chaque nœud de l'arbre de décision.

L'arbre de décision suivant illustre l'échantillonnage des attributs / caractéristiques. Ici, un arbre de décision est entraîné sur cinq caractéristiques (f1-f5). Les nœuds bleus représentent les fonctionnalités testées, tandis que les nœuds blancs ne sont pas testés. La condition est créée à partir des fonctionnalités les mieux testées (représentées par un contour rouge).

Trois nœuds, chacun affichant cinq éléments. Le nœud racine et l'un de ses nœuds enfants testent trois des cinq fonctionnalités. L'autre nœud enfant teste deux des cinq fonctionnalités.

Figure 21. Échantillonnage des attributs.

 

Le ratio d'échantillonnage des attributs est un hyperparamètre de régularisation important. La figure précédente utilisait un format d'environ ⅗. De nombreuses implémentations de forêts d'arbres aléatoires testent, par défaut, un tiers des caractéristiques pour la régression et la racine carrée(nombre de caractéristiques) pour la classification.

Dans TF-DF, les hyperparamètres suivants contrôlent l'échantillonnage des attributs:

  • num_candidate_attributes
  • num_candidate_attributes_ratio

Par exemple, si num_candidate_attributes_ratio=0.5, la moitié des fonctionnalités sera testée à chaque nœud.

Désactiver la régularisation de l'arbre de décision

Les arbres de décision individuels d'une forêt aléatoire sont entraînés sans élagage. (voir Surajustement et élagage). Cela produit des arbres trop complexes avec une qualité prédictive médiocre. Au lieu de régulariser des arbres individuels, les arbres sont regroupés pour produire des prédictions globales plus précises.

Nous attendons que la précision d'entraînement et de test d'une forêt aléatoire soit différente. La précision d'entraînement d'une forêt d'arbres aléatoires est généralement beaucoup plus élevée (parfois égale à 100%). Toutefois, une précision d'entraînement très élevée dans une forêt d'arbres aléatoires est normale et n'indique pas que la forêt d'arbres aléatoires est suradaptée.

Les deux sources d'aléatoire (bagging et échantillonnage des attributs) assurent une indépendance relative entre les arbres de décision. Cette indépendance corrige le surajustement des arbres de décision individuels. Par conséquent, l'ensemble n'est pas suradapté. Nous illustrerons cet effet non intuitif dans l'unité suivante.

Les forêts aléatoires pures sont entraînées sans profondeur maximale ni nombre minimal d'observations par feuille. En pratique, il est utile de limiter la profondeur maximale et le nombre minimal d'observations par feuille. Par défaut, de nombreuses forêts aléatoires utilisent les valeurs par défaut suivantes:

  • profondeur maximale d'environ 16
  • Nombre minimal d'observations par feuille d'environ 5.

Vous pouvez régler ces hyperparamètres.

Code YDF
Le tuner de YDF est un moyen simple de régler les hyperparamètres. Pour en savoir plus, consultez le tutoriel de réglage de YDF.

Clarté du bruit

Pourquoi le bruit aléatoire améliore-t-il la qualité d'une forêt d'arbres décisionnels aléatoires ? Pour illustrer les avantages du bruit aléatoire, la figure 22 montre les prédictions d'un arbre de décision classique (élagué) et d'une forêt d'arbres aléatoires entraînés sur quelques exemples de problèmes bidimensionnels simples avec un motif en ellipse.

Les modèles d'ellipses sont particulièrement difficiles à apprendre pour les algorithmes d'arbre de décision et de forêt de décision avec des conditions alignées sur les axes. Ils constituent donc un bon exemple. Notez que l'arbre de décision élagué ne peut pas obtenir la même qualité de prédiction que la forêt d'arbres aléatoires.

Trois illustrations. La première illustration, intitulée "Vérité terrain", est une ellipse parfaite. La deuxième illustration, intitulée "Arbre de décision élagué", se situe entre une ellipse et un rectangle. Une troisième illustration, intitulée "Forêt aléatoire", n'est pas tout à fait une ellipse, mais est beaucoup plus proche d'une ellipse que l'illustration intitulée "Arbre de décision élagué".

Figure 22. Vérité terrain par rapport aux prédictions générées par un seul arbre de décision élagué et aux prédictions générées par une forêt aléatoire.

Le graphique suivant montre les prédictions des trois premiers arbres de décision non élagués de la forêt d'arbres aléatoires. Autrement dit, les arbres de décision sont tous entraînés avec une combinaison des éléments suivants:

  • bagging
  • Échantillonnage d'attributs
  • désactiver l'élagage

Notez que les prédictions individuelles de ces trois arbres de décision sont pires que celles de l'arbre de décision élagué de la figure précédente. Toutefois, comme les erreurs des arbres de décision individuels ne sont que faiblement corrélées, les trois arbres de décision se combinent en ensemble pour créer des prédictions efficaces.

Trois ellipses très bruyantes.

Figure 23. Trois arbres de décision non élagués qui créeront un ensemble efficace.

Étant donné que les arbres de décision d'une forêt aléatoire ne sont pas élagués, l'entraînement d'une forêt aléatoire ne nécessite pas d'ensemble de données de validation. En pratique, et en particulier sur de petits ensembles de données, les modèles doivent être entraînés sur toutes les données disponibles.

Lorsque vous entraînez une forêt d'arbres aléatoires, l'erreur diminue presque toujours à mesure que vous ajoutez des arbres de décision. Autrement dit, la qualité du modèle s'améliore presque toujours. Oui, ajouter des arbres de décision réduit presque toujours l'erreur de la forêt aléatoire. En d'autres termes, l'ajout d'arbres de décision ne peut pas entraîner une suradaptation de la forêt aléatoire. À un moment donné, le modèle cesse de s'améliorer. Leo Breiman a déclaré : Les forêts aléatoires ne surajustent pas, à mesure que des arbres sont ajoutés.

Par exemple, le graphique suivant montre l'évaluation du test d'un modèle de forêt aléatoire à mesure que d'autres arbres de décision sont ajoutés. La précision s'améliore rapidement jusqu'à atteindre un plateau d'environ 0,865. Toutefois, l'ajout d'arbres de décision ne fait pas baisser la précision. En d'autres termes,le modèle ne surajuste pas. Ce comportement est (généralement) toujours vrai et indépendant des hyperparamètres.

Graphique de la précision par rapport au nombre d'arbres de décision décrit dans le paragraphe précédent.

Figure 24. La précision reste constante à mesure que des arbres de décision sont ajoutés à la forêt d'arbres décisionnels.