dimanche 30 mars 2008

Random Forests

RANDOM FOREST (forêts d'arbres) est une technique d’apprentissage supervisé qui combine une technique d’agrégation, le BAGGING, et une technique particulière d’induction d’arbres de décision.

Lors de la construction de l’arbre, pour initier la segmentation d’un nœud, la méthode effectue dans un premier temps une sélection aléatoire parmi les variables candidates ; sélection à partir de laquelle, dans un deuxième temps, elle cherche la variable de segmentation. La taille de la sélection est un paramètre de l’algorithme. Si elle n’est pas spécifiée, on propose généralement la formule « partie entière de log2 (J)+1 », où J est le nombre total de variables.

L’idée est assez simple, et déjà présente dans les premiers articles de BREIMAN (1996) sur le BAGGING : en exacerbant la variabilité de la technique d’apprentissage, nous augmentons l’efficacité de la technique d’agrégation.

L’implémentation dans Tanagra est un peu particulière. Plutôt que de fournir un composant dédié, une méthode de construction d’arbre « aléatoire » est proposée. La méthode Random Forest revient à l’utiliser conjointement avec le composant BAGGING. L’utilisateur bénéficie ainsi d’une meilleure souplesse d’utilisation, il pourra aussi introduire ses propres variantes, BOOSTING + RANDOM TREE par exemple, etc.

Dans ce didactciel, nous comparons les performances de C4.5 (Quinlan, 1993), élaborant un arbre unique, avec random forest. Cette dernière améliore sensiblement la qualité de la prédiction. Le taux d’erreur est mesuré en validation croisée.

Mots clés : random forest, agrégation de classifieurs, arbres de décision, validation croisée
Composants : Bagging, Rnd Tree, Supervised Learning, Cross-validation, C4.5
Lien : fr_Tanagra_Random_Forest.pdf
Données : dr_heart.bdm
Référence : L. Breiman, A. Cutler, « Random Forests ».