dimanche 21 septembre 2008

Traitement de gros volumes – Comparaison de logiciels

La gestion de la volumétrie est une des pierres angulaires du Data Mining. Toute présentation du domaine passe par le sempiternel « depuis quelques années, les entreprises amassent une quantité considérable de données, l’enjeu n’est plus comment les stocker mais plutôt comment les exploiter pour en tirer de l’information », etc., etc. Ok, ok, n’en jetez plus, on est d’accord.

Si le traitement des grandes bases est un enjeu important, on est curieux de savoir comment se comportent les logiciels libres (gratuits) dans ce contexte. Ils sont nombreux dans le Data Mining. J’essaie de suivre un peu leur évolution. La capacité à analyser des grands fichiers est un critère que je regarde souvent pour situer mes propres implémentations. La plupart chargent l’ensemble de données en mémoire centrale. De fait, la différenciation en termes de performances repose essentiellement sur la technologie utilisée (compilé ou pseudo-compilé) et la programmation. Le goulot d’étranglement est la mémoire disponible.

Dans ce didacticiel, nous comparons les performances de plusieurs implémentations de l’algorithme C4.5 (Quinlan, 1993) lors du traitement d’un fichier comportant 500.000 observations et 22 variables. Un fichier somme toute assez raisonnable.

Les logiciels mis en compétition sont les suivants : KNIME, ORANGE, R (package RPART), RAPIDMINER (anciennement YALE), SIPINA, TANAGRA et WEKA.

Ce document vient un complément d’un ancien didacticiel où nous montrions les performances de ID3 de Tanagra sur un fichier encore plus volumineux. Nous retiendrons 2 critères pour comparer les logiciels : le temps de traitement et surtout l’occupation mémoire. Ils sont essentiels dans notre contexte.

On retiendra entre autres que tous les logiciels ont pu mener à bien les calculs dans cette expérimentation. Ce qui confirme, si besoin était, l’excellente tenue des logiciels libres en matière de performances.

Mots clés : c4.5, arbres de décision, grandes bases de données, comparaison de logiciels, knime, orange, r, rapidminer, sipina, tanagra, weka
Composants : SUPERVISED LEARNING, C4.5
Lien : fr_Tanagra_Perfs_Comp_Decision_Tree.pdf
Données : wave500k.zip
Références :
R. Quinlan, « C4.5 : Programs for Machine Learning », Morgan Kaufman, 1993.

vendredi 19 septembre 2008

Tanagra : Spécifications, Développement, Promotion

Un séminaire au sein de l'UMR Sensométrie et Chimiométrie (ENITIAA/INRA) à Nantes en avril 2008 a été l'occasion de faire un peu le bilan du projet Tanagra, 5 ans presque après son lancement.

L'objectif était de tracer les grandes lignes du projet en mettant en avant les différentes réflexions que nous avons eu à mener, les pistes qui ont permis d'élaborer un cahier des charges raisonnable.

Il fallait notamment : essayer de cerner les utilisateurs types ; définir les spécifications fonctionnelles, en nous situant par rapport aux outils que nous avions programmés auparavant et les logiciels existants ; définir les spécifications techniques, de manière entre autres à ce que la mise à jour ne devienne pas un parcours du combattant ; choisir le mode de documentation du logiciel, aspect crucial dès lors que l'on souhaite le diffuser à grande échelle, j'ai beaucoup pêché sur le sujet par le passé ; et enfin, poser la question de la promotion du logiciel auprès des utilisateurs. En effet, il s'agit d'un outil totalement libre, c'est entendu. Mais si je suis le seul à l'utiliser, l'intérêt est plutôt limité. Je pense que la documentation joue un rôle très important dans ce domaine.

C'est donc le support visuel de l'exposé qui est mis en ligne ici. Quelques transparents ont été réactualisés pour refléter les chiffres de la version 1.4.27 (fin août 2008).

Lien : R. Rakotomalala, "Tanagra : Spécifications, Développement et Promotion", Séminaire USC, ENITIAA/INRA, Nantes, Avril 2008.

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/

lundi 15 septembre 2008

La méthode SIPINA

SIPINA est un logiciel. Mais c'est aussi une méthode d'apprentissage. Elle généralise les arbres en introduisant une opération supplémentaire, la fusion, lors de l'induction du modèle de prédiction. On parle de " Graphes d'Induction ".

L'idée de fusion des sommets existe déjà dans des méthodes telles que CART ou CHAID. Mais dans ce cas, il s'agit de procéder au regroupement des feuilles issues du même nœud père lors d'une segmentation. Pour une variable explicative discrète comportant K modalités, CART effectue des regroupements de manière à proposer 2 super modalités, l'arbre est binaire ; CHAID effectue un regroupement sélectif en comparant les profils des distributions, il y a bien regroupement mais l'arbre n'est pas forcément binaire. SIPINA généralise cette idée en permettant le regroupement de 2 feuilles quelconques de la structure. La fusion peut donc s'appliquer à deux feuilles géographiquement éloignées dans le graphe.

Schématiquement, à chaque étape du processus de construction du graphe, la méthode évalue et met en compétition la segmentation d'un nœud et la fusion de deux nœuds. Elle choisit l'opération qui améliore la mesure d'évaluation globale de la partition. Cela est possible car le critère pénalise les nœuds à faibles effectifs. Dans certaines situations, il peut être avantageux de fusionner des sommets avant de segmenter à nouveau. L'objectif est d'explorer plus finement des sous-groupes d'individus, sans tomber dans un des inconvénients récurrents des arbres de décision, la tendance au sur-apprentissage consécutive à l'éparpillement excessif des observations.

La méthode SIPINA n'est disponible que dans la version 2.5 du logiciel (SIPINA version 2.5). Ce dernier concentre bien des défauts. Mais c'est néanmoins le seul logiciel à proposer la méthode SIPINA telle qu'elle est décrite dans la littérature (voir Références). C'est la raison pour laquelle je le mets encore en ligne d'ailleurs. Sinon, si l'on veut utiliser d'autres algorithmes d'induction d'arbres (C4.5, CHAID, etc.), il est préférable de se tourner vers la " Version Recherche " , nettement plus performante et fiable.

Dans ce didacticiel, nous montrons la mise en œuvre de la méthode SIPINA dans le logiciel éponyme, version 2.5. Le problème traité est l'explication du faible poids de certains bébés à la naissance à partir des caractéristiques de la mère. L'interprétation des résultats est anecdotique dans notre contexte. On cherche surtout (1) à montrer la prise en main de cette version du logiciel qui est très peu documentée, (2) à mettre en avant les avantages de la méthode lorsque l'on traite des fichiers comportant peu d'observations.

Mots clés : arbres de décision, graphes d'induction
Lien : fr_sipina_method.pdf
Données : low_birth_weight_v4.xls
Références
Zighed, J.P. Auray, G. Duru, SIPINA : Méthode et logiciel, Lacassagne, 1992.
R. Rakotomalala, Graphes d’induction, Thèse de Doctorat, Université Lyon 1, 1997 (URL : http://eric.univ-lyon2.fr/~ricco/publications.html).
D. Zighed, R. Rakotomalala, Graphes d’induction : Apprentissage et Data Mining, Hermès, 2000.