dimanche 9 mars 2008

CART - Détermination de la taille de l'arbre

Déterminer la bonne taille de l'arbre est une opération cruciale dans la construction d'un arbre de décision à partir de données. Elle détermine ses performances lors de son déploiement dans la population1. Il y a deux extrêmes à éviter : l'arbre sous dimensionné, trop réduit, captant mal les informations utiles dans le fichier d'apprentissage ; l'arbre sur dimensionné, de taille exagérée, captant les spécificités du fichier d'apprentissage, spécificités qui ne sont pas transposables dans la population. Dans les deux cas, nous avons un modèle de prédiction peu performant.

La popularité de la méthode CART repose en grande partie sur sa capacité à proposer une démarche efficace de détermination de la bonne (je n'ose dire " optimale ") taille de l'arbre. Ce didacticiel montre comment se manifeste cette stratégie, quelles en sont les conséquences sur (1) la complexité de l'arbre (nombre de feuilles c.-à-d. nombre de règles) ; et (2) ses performances en prédiction (évaluation sur un fichier test n'ayant pas participé à l'élaboration du modèle).

Quelques pistes sont alors proposées pour fixer de manière raisonnée les paramètres de l'algorithme d'apprentissage, plus particulièrement la règle de l'écart type qui permet de réduire considérablement la taille de l'arbre sans dégrader les performances.

L'exemple traité consiste à prédire le niveau de revenu annuel des individus (supérieur à 50000 $ ou non) à partir de caractéristiques signalétiques (niveau d'étude, type d'emploi, etc.).

Mots clés : arbres de décision, CART, apprentissage et évaluation des classifieurs, principe de parcimonie, règle de l'écart type (1-SE Rule)
Composants : Discrete select examples, Supervised Learning, C-RT, Test
Lien : fr_Tanagra_Tree_Post_Pruning.pdf
Données : adult_cart_decision_trees.zip
Références :
L. Breiman, J. Friedman, R. Olshen, C. Stone, " Classification and Regression Trees ", California : Wadsworth International, 1984.
R. Rakotomalala, " Arbres de décision ", Revue Modulad, 33, 163-187, 2005 (tutoriel_arbre_revue_modulad_33.pdf)