Forêt d'arbres décisionnels

Forêt d'arbres décisionnels

Illustration du principe de construction d'une forêt aléatoire comme agrégation d'arbre aléatoires.

Type	Algorithme
Inventeur	Leo Breiman
Décrit par	Random Forests (d), The Elements of Statistical Learning (d)

En intelligence artificielle, plus précisément en apprentissage automatique, les forêts d'arbres décisionnels (ou forêts aléatoires de l'anglais random forest classifier) forment une technique d'apprentissage à base d'arbres de décision. Elles ont été premièrement proposées par Ho en 1995 et ont été formellement proposées en 2001 par Leo Breiman et Adele Cutler (en).

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. Cet algorithme combine les concepts de bagging (méthodes ensemblistes parallèles) pour la phase de sélection des données, et de sous-espaces aléatoires.

Arbres de décision

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). 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

La base du calcul repose sur l'apprentissage par arbre de décision. La proposition de Breiman 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 ${B}$ 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

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 ${B}$ 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

Considérons un ensemble de ${N}$ observations (${N}$ personnes décrites avec leurs ${p}$ 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 ${N}$ données s'effectue comme suit. On crée ${B}$ arbres de décision. Pour chaque arbre à créer :

1. On crée un échantillon en tirant avec remise ${N}$ 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 ${p}$ attributs, on n'en retient qu'un nombre ${q}$ inférieur ou égal à ${p}$. 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 ${q=2}$ 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 préconisent une valeur égale de q égale à environ ${\sqrt {p}}$, notamment pour des problèmes de classification. 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.

Voir aussi

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

Logiciels

• Programme RF original de Breiman et Cutler
• Random Jungle, une mise en œuvre rapide (C++, calcul parallèle, structures creuses) pour des données sur des espaces de grandes dimensions
• Paquetage randomForest pour R, module de classification et de régression basée sur une forêt d'arbres à l'aide de données aléatoires. Basé sur le programme original en Fortran de Breiman et Cutler.
• STATISTICA Forêts Aléatoires est un module dédié de forêts d'arbres décisionnels intégré dans Statistica Data Miner.

Notes

(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).

Bibliographie

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