Forêt d'arbres décisionnels

Un article de Wikipédia, l'encyclopédie libre.
Illustration du principe de construction d'une forêt aléatoire comme agrégation d'arbre aléatoires.

En intelligence artificielle, plus précisément en apprentissage automatique, les forêts d'arbres décisionnels[1] (ou forêts aléatoires de l'anglais random forest classifier) forment une technique d'apprentissage à base d'arbres de décision. Elle apprend plusieurs arbres de décision et de ce fait, elle fait partie des méthodes d'apprentissage ensembliste, c'est-à-dire des méthodes qui utilisent la sagesse des foules[2]. Ils ont été premièrement proposées par Ho en 1995[3] et ont été formellement proposées en 2001 par Leo Breiman[4] et Adele Cutler[5]. Cet algorithme combine les concepts de bagging (méthodes ensemblistes parallèles[2]) pour la phase de sélection des données, et de sous-espaces aléatoires. L'algorithme des forêts d'arbres décisionnels effectue un apprentissage sur de multiples arbres de décision entraînés sur des sous-ensembles de données légèrement différents.

Arbres de décision[modifier | modifier le code]

Exemple d'un arbre de décision.

Un arbre décisionnel ou arbre de décision est une structure qui prend la forme d'un arbre, dans laquelle on pose des questions sur des attributs (dans certains ouvrages, on parle plutôt de variables[2]). La figure donne un exemple d'un arbre de décision. Il y a deux attributs : l'âge et le fait que la personne soit fumeuse. On pose d'abord la question de l'âge. Si on a moins de 30 ans, il y a peu de risque. Si on a plus de 30 ans, on pose la question si la personne est fumeuse. Si non, peu de risque. Si oui, le risque est grand.

Dans la méthode des forêts aléatoires, nous allons considérer plusieurs arbres de décision en même temps.

Algorithmes[modifier | modifier le code]

La base du calcul repose sur l'apprentissage par arbre de décision. La proposition de Breiman[4] vise à corriger plusieurs inconvénients connus de la méthode initiale, comme la sensibilité des arbres à l'ordre des attributs. Au lieu de n'avoir qu'un unique arbre, le modèle est une collection de arbres de décision partiellement indépendants. Malheureusement, avec la méthode des arbres aléatoires, on perd l'aspect visuel de n'avoir qu'un seul arbre.

Prédiction[modifier | modifier le code]

Pour prédire avec un modèle de Random Forest, on calcule les prédictions intermédiaires pour chaque arbre, puis on réalise un vote majoritaire.

Le modèle est constitué de arbres de décision. Pour prédire la classe d'une observation (par exemple, prédire si une personne fumeuse de 35 ans a un grand risque ou non d'avoir un accident cardiovasculaire)  :

  1. On calcule le résultat pour chaque arbre. Si par exemple, on dispose de 3 arbres, on peut imaginer obtenir "peu de risque", "grand risque" et "grand risque".
  2. La prédiction finale de la forêt aléatoire est un simple vote majoritaire (Ensemble learning). Dans l'exemple, il y a deux fois "grand risque" mais qu'un seul "peu de risque". La prédiction finale est donc "grand risque".

Apprentissage[modifier | modifier le code]

Considérons un ensemble de observations ( personnes décrites avec leurs attributs, comme l'âge, le fait que la personne fume, etc.) munis de leur classe (on donne l'information pour chaque personne si elle est à risque ou non). L'apprentissage à partir de ces données s'effectue comme suit[6]. On crée arbres de décision. Pour chaque arbre à créer :

  1. On crée un échantillon en tirant avec remise observations (technique connue sous le nom de bootstrap),
    Tirage avec remise. A partir de N observations (représentées par les bonhommes de différentes couleurs, à gauche), on tire au hasard N observations (plusieurs même éléments peuvent apparaître plusieurs fois).
  2. Sur les attributs, on n'en retient qu'un nombre inférieur ou égal à . Par exemple, on pourrait imaginer que l'ensemble des attributs sont : l'âge (moins de 30 ans, ou plus de 30 ans), un excès de glycémie (oui/non), le poids (moins de 90kg, plus de 90kg), buveur de café (oui/non), fumeur (oui/non), activité physique (oui/non). Sur ces attributs, on n'en sélectionne que au hasard, par exemple l'âge et le fait d'être fumeur.
  3. On entraîne un arbre de décision selon une des techniques connues (comme C4.5 ou CART), à partir de l'échantillon créé en 1. et en tenant compte que des attributs sélectionnés en 2. On limite la croissance de l'arbre de décision par validation croisée.
    Exemple d'un arbre de décision que l'on pourrait apprendre.

Certains auteurs[7],[2] préconisent une valeur égale de q égale à environ , notamment pour des problèmes de classification[2]. L'avantage est de réduire le temps de calcul car on considère moins de variables. Par exemple, on ne considère que 5 attributs pour un problème de 30 attributs, 31 pour un problème qui comprend 1000 attributs, etc. S'il s'agit d'un problème de régression on utilise pour q plutôt une valeur proche de p/3[2].

Voir aussi[modifier | modifier le code]

Le modèle uplift est une application des forêts d'arbres décisionnels pour la détection des populations sensibles aux opérations de marketing ciblées.

Liens externes[modifier | modifier le code]

Logiciels[modifier | modifier le code]

Notes[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Random forest » (voir la liste des auteurs).
  1. Robert Nisbet, John Elder, Gary Miner, Handbook for Statistical Analysis And Data Mining, Academic Press, Page 247 Edition 2009
  2. a b c d e et f Chloé-Agathe Azencott, Introduction au Machine Learning - 2e éd., Dunod, (ISBN 978-2-10-083476-1, lire en ligne), Chapitre 9, 9.3 Méthodes ensemblistes : la sagesse des foules p. 140
  3. Ho, Tin Kam, « Random Decision Forests », Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, QC,‎ 14-16 august 1995, p. 278-282 (lire en ligne)
  4. a et b Leo Breiman, « Random Forests », Machine Learning, vol. 45, no 1,‎ , p. 5–32 (DOI 10.1023/A:1010933404324)
  5. Andy Liaw, « Documentation for R package randomForest »,
  6. Pirmin Lemberger, Marc Batty, Médéric Morel et Jean-Luc Raffaëlli, Big Data et Machine Learning, Dunod, , pp 130-131.
  7. Vincent Barra, Laurent Miclet et Antoine Cornuéjols, Apprentissage artificiel - 3e édition: Concepts et algorithmes, Eyrolles, (lire en ligne), Section 3.3 p. 468

Bibliographie[modifier | modifier le code]

(en) Breiman, Leo, « Statistical Modeling: The Two Cultures », Statistical Science, vol. 16, no 3,‎ , p. 199-231 (lire en ligne).