Forêt d'arbres décisionnels

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. 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. Ils ont été premièrement proposées par Ho en 1995 et ont été formellement proposées en 2001 par Leo Breiman et Adele Cutler. 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. 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 

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  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 
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)  :
 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".
 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  d'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. On crée  arbres de décision. Pour chaque arbre à créer : 
 On crée un échantillon en tirant avec remise  observations (technique connue sous le nom de bootstrap),
 Sur les  attributs, on n'en retient qu'un nombre q inférieur ou égal à p
 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.
Certains auteurs préconisent une valeur égale de q égale à environ , 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

Bibliographie 
.

Apprentissage automatique
Exploration de données
Structure de données probabiliste
Science des données
Arbre de décision