Forêt d'arbres décisionnels

Pour les articles homonymes, voir Arbre (homonymie).

Cet article ne cite pas suffisamment ses sources (mai 2019).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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)

modifier - modifier le code - modifier Wikidata

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. Elles ont été premièrement proposées par Ho en 1995^[2] et ont été formellement proposées en 2001 par Leo Breiman^[3] et Adele Cutler (en)^[4].

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^[5]) pour la phase de sélection des données, et de sous-espaces aléatoires.

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^[5]). 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.

La base du calcul repose sur l'apprentissage par arbre de décision. La proposition de Breiman^[3] 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 ${\displaystyle {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.

Le modèle est constitué de ${\displaystyle {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 ».

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

1. On crée un échantillon en tirant avec remise ${\displaystyle {N}}$ observations (technique connue sous le nom de bootstrap),

   

2. Sur les ${\displaystyle {p}}$ attributs, on n'en retient qu'un nombre ${\displaystyle {q}}$ inférieur ou égal à ${\displaystyle {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 ${\displaystyle {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 ne 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^[7],[5] préconisent une valeur égale de q égale à environ ${\displaystyle {\sqrt {p}}}$, notamment pour des problèmes de classification^[5]. 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^[5].

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.

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

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

v · m Apprentissage automatique et exploration de données
Paradigmes d'apprentissage	Apprentissage supervisé auto-supervisé semi-supervisé ou non supervisé Apprentissage par renforcement, par transfert ou incrémental
Problèmes	Classement Clustering Détection d'anomalies Optimisation en ligne Modèle génératif Régression Règle d'association Réduction de dimensions Analyse factorielle Sélection de caractéristique Extraction de caractéristique
Apprentissage supervisé	Classement Arbre de décision k-NN U-matrix CRF Régression logistique Régression Modèle linéaire généralisé Régression linéaire Régression de Poisson Modèle probit Analyse discriminante linéaire Machine à vecteurs de support Prédiction structurée Modèle graphique Classification naïve bayésienne Réseau bayésien Modèle de Markov caché Réseau de neurones artificiels récurrents (+ Rétropropagation à travers le temps) Calcul par réservoir à action directe (+ Rétropropagation du gradient) Apprentissage profond Perceptron Perceptron multicouche Réseau neuronal convolutif à impulsions
Apprentissage non supervisé et auto-supervisé	Clustering Regroupement hiérarchique K-moyennes Algorithme espérance-maximisation DBSCAN OPTICS Réduction de dimensions ACP ACP à noyaux Analyse en composantes indépendantes Analyse canonique des corrélations Analyse canonique à noyaux t-SNE Réseau de neurones artificiels Auto-encodeur IA générative et Modèle génératif Réseau de neurones artificiels Réseaux antagonistes génératifs (classique ou de Wasserstein) Auto-encodeur variationnel Réseau de Hopfield Machine de Boltzmann restreinte Cartes de Kohonen Transformeur
Métaheuristique d'optimisation	Stratégie d'évolution et génétique NEAT HyperNEAT Essaims Apprentissage ensembliste Forêts aléatoires Boosting
Théorie	Apprentissage PAC Complexité de Rademacher Dilemme biais-variance Hypothèse de la variété Théorie de Vapnik-Chervonenkis pulvérisation Dimension de Vapnik-Chervonenkis Théorème de Cover
Logiciels	Keras Microsoft Cognitive Toolkit Scikit-learn TensorFlow Theano Weka PyTorch

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l’informatique
• Portail des probabilités et de la statistique