mercredi 17 septembre 2008

La méthode CART dans Tanagra et R (package rpart)

CART (Breiman et al, 1984) est une méthode très populaire d’induction d’arbres de décision, peut-être la plus répandue, tout du moins au sein de la communauté francophone du Data Mining. A juste titre. CART intègre tous les bons ingrédients d’un apprentissage maîtrisé : arbitrage biais – variance via avec le post-élagage, le mécanisme de coût complexité permet de « lisser » l’exploration de l’espace des solutions, intégration de la préférence à la simplicité avec la règle de l’écart type, préférence que le praticien peut modifier en modulant les paramètres en fonction des objectifs de l’étude et des caractéristiques des données, etc.

La Société Salford Systems détient les droits d’utilisation du nom CART. De fait, même si la méthode est implantée dans de nombreux logiciels commerciaux, elle n’est jamais désignée nommément. Que cela ne nous induise pas en erreur, une lecture rapide de la documentation ne laisse généralement aucun doute quant à l’origine de la technique.

La situation est un peu différente en ce qui concerne les logiciels libres. Ils sont nettement plus rares à proposer CART, une grande majorité d’entre eux lui préférant ID3 ou C4.5, nettement plus faciles à programmer au demeurant.

Dans ce didacticiel, nous comparons deux implémentations libres de CART : le composant C-RT de Tanagra et le package RPART du Logiciel R. A la lecture de la documentation, ils s’appuient tous les deux sur les mêmes schémas génériques (Breiman et al, 1984 ; chapitres 3, 10 et 11). La principale différence apparaît lors du post-élagage. Tanagra ne propose que le post élagage basé sur un échantillon spécifique dit « échantillon d’élagage » (section 11.4). RPART lui s’appuie plus volontiers sur la validation croisée (section 11.5), bien qu’il soit possible d’utiliser également un échantillon d’élagage, au prix de manipulations (un peu beaucoup) compliquées il est vrai.

Pour mener la comparaison, nous utilisons les données artificielles WAVEFORM de Breiman (section 2.6.2). La variable à prédire (CLASS) comporte 3 modalités, les 21 variables prédictives (V1 à V21) sont toutes continues. Nous essayons de reproduire l’expérimentation décrite dans l’ouvrage de référence (pages 49 et 50), à savoir utiliser 300 individus en apprentissage et 5000 en test.

Mots clés : arbres de décision, méthode cart, apprentissage supervisé, comparaison de logiciels, logiciel R, package rpart
Composants : DISCRETE SELECT EXAMPLES, C-RT, SUPERVISED LEARNING, TEST
Lien : fr_Tanagra_R_CART_algorithm.pdf
Données : wave5300.xls
Références :
Breiman, J. Friedman, R. Olsen, C. Stone, Classification and Regression Trees, Chapman & Hall, 1984.
"The R project for Statistical Computing" - http://www.r-project.org/