Overblog Suivre ce blog
Administration Créer mon blog

Présentation

  • : Sipina - Arbres de décision
  • Sipina - Arbres de décision
  • : Sipina : fonctionnalités et références
  • Contact

Recherche

30 octobre 2013 3 30 /10 /octobre /2013 16:06
Outre les arbres de décision qui restent quand même son véritable terrain de prédilection, le logiciel SIPINA intègre d’autres méthodes supervisées. Certes, les mêmes sont disponibles dans Tanagra (qui – lui - ne propose pas les arbres graphiques interactifs), elles y sont mieux mises en valeur, nous pouvons les enchaîner (ex. réaliser une régression sur facteurs de l’ACP), récupérer les résultats dans un tableur pour des calculs ultérieurs (ex. effectuer des calculs supplémentaires à partir des coefficients fournis par la régression logistique), etc. Dans les faits,  en mettant à part les arbres toujours, je me sers avant tout de SIPINA comme laboratoire d’idées pour l’optimisation des implémentations des algorithmes de data mining ces dernières années (dump des données sur le disque pour réduire l’occupation mémoire, échantillonnage, multithreading, …).

Dernièrement, je me suis intéressé à l’analyse discriminante prédictive, plus précisément à l’exploitation des threads pour tirer parti des capacités des machines multi-cœurs ou multiprocesseurs. Deux stratégies – décrites dans deux tutoriels –  ont été mises au point : la première, implémentée dans Sipina 3.10, est parcimonieuse en  mémoire, mais ses performances sont dépendantes des caractéristiques des données traitées et non de la machine utilisée (certains cœurs peuvent rester inactifs) ; la seconde, implémentée dans Sipina 3.11, s’adapte aux capacités de la machine utilisée, mais s’avère plus gourmande en mémoire (les matrices de calcul sont dupliquées autant de fois qu’il y a de threads lancés). Quoiqu’il en soit, une chose est sûre, sauf gestion calamiteuse de la synchronisation des calculs et de la manipulation des données, une stratégie multithread devrait toujours être plus rapide qu’une approche purement séquentielle.

Mots-clés : analyse discriminante linéaire, analyse discriminante prédictive, threads, multithreading, processeurs multi-coeurs, ordinateur multiprocesseur
Repost 0
30 décembre 2011 5 30 /12 /décembre /2011 21:38
Triturer des très grands fichiers était de fantasme ultime du data miner a-t-on coutume de dire. Etant passé récemment à un système 64 bits (mieux vaut tard que jamais), je me propose d’étudier le comportement des outils spécifiquement dédiés à ce système, principalement Knime 2.4.2 et RapidMiner 5.1.011.

Ce document vient compléter l'étude précédente où nous traitions une base moyennement volumineuse avec 500.000 observations et 22 variables. Nous poussons le curseur un peu plus loin en reprenant un tutoriel où le fichier à traiter comportait 9.634.198 observations et 41 variables, (quasiment) impossible à faire tenir en mémoire sur un système 32 bits. L’idée était alors de montrer qu’un système de swap adapté aux algorithmes d’apprentissage, l’induction d’un arbre de décision en l’occurrence, permettait d’appréhender de très grandes bases avec des temps de traitement raisonnables. La procédure avait été implémentée dans Sipina.

Dans ce tutoriel, nous constatons que le passage aux 64 bits augmente considérablement les capacités de calcul des logiciels de Data Mining. C’est indéniable. Mais il faut disposer d’une machine à l’avenant pour en tirer réellement parti.

Mots clés : gros volumes, très grands fichiers, grandes bases de données, arbre de décision, échantillonnage, sipina, knime, rapidminer, tanagra, windows 7 - 64 bits
Lien : Arbres de décision sur les "très" grandes bases (suite)
Repost 0
13 décembre 2011 2 13 /12 /décembre /2011 09:14
S’endormir sur ses lauriers est impossible en informatique. Tout évolue très vite : matériel, système, logiciel. C’est un de ses principaux attraits d’ailleurs. La vérité d’aujourd’hui n’est pas celle d’hier, elle sera peut être différente demain, il faut être sur le qui-vive. Ayant changé de système, je suis passé à Windows 7 en 64 bits (avec un Quad Core Q9400 à 2.66 Ghz), j’étais curieux de voir le nouveau comportement des outils analysés dans un ancien document dont l'objet était l'analyse comparative des performances des différents logiciels de data mining durant l'apprentissage d'un arbre de décision. Surtout que plusieurs de ces outils sont passés à une version 64 bits (Knime, RapidMiner, R).

J’ai donc reproduit la même analyse avec les mêmes données et mesuré les mêmes critères : temps de traitement et occupation mémoire. J’ai constaté que la grande majorité des outils ont bien progréssé en termes de temps de traitement, à des degrés divers néanmoins. En revanche, les évolutions ne sont pas manifestes concernant l’occupation mémoire. Nous détaillons tout cela dans la dernière section de cette nouvelle version de notre tutoriel. Finalement, SIPINA s'en sort pas trop mal face à des outils pourtant,pour certains, très sophistiqués.

Mots-clés : c4.5, arbres de décision, grandes bases de données, comparaison de logiciels, knime2.4.2, orange 2.0b, r 2.13.2, rapidminer 5.1.011, sipina 3.7, tanagra 1.4.41, weka 3.7.4, windows 7 - 64 bits
Lien : Arbres de décision sur les très grandes bases (suite)
Repost 0
2 décembre 2010 4 02 /12 /décembre /2010 08:12
Une grande partie des PC modernes sont équipés de processeurs multi-cœurs. Dans les faits, l'ordinateur fonctionne comme s'il disposait de plusieurs processeurs. Certains d'ailleurs, les gros serveurs notamment, en disposent effectivement. Les logiciels et les algorithmes de data mining doivent être aménagés pour pouvoir en tirer profit. A l'heure actuelle, rares sont les outils à large diffusion qui exploitent ces nouvelles caractéristiques des machines.

En effet, l'affaire n'est pas simple. Il est impossible de mettre en place une démarche générique qui serait valable quelle que soit la méthode d'apprentissage utilisée. Pour une technique donnée, décomposer un algorithme en tâches que l'on peut exécuter en parallèle est un domaine de recherche à part entière. Les publications scientifiques regorgent de propositions en tous genres, tant au niveau méthodologique (modification des algorithmes) qu'au niveau technologique (implémentation sur les machines). Une grande majorité d'entre elles s'intéressent surtout à l'implantation sur de gros systèmes. Il y a très peu de propositions de solutions légères que l'on peut introduire facilement sur des logiciels destinés aux ordinateurs personnels.

Dans ce didacticiel, une solution basée sur les threads est mise en avant. Elle est implantée dans la version 3.5 de Sipina.

Mots-clés : multithreading, thread, threads, arbres de décision, chaid, sipina 3.5, knime 2.2.2, rapidminer 5.0.011
Lien : Multithreading
Repost 0
15 septembre 2008 1 15 /09 /septembre /2008 10:30
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 l'ancienne 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 : graphes d'induction, SIPINA version 2.5
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.
Repost 0
28 mars 2008 5 28 /03 /mars /2008 15:38
Description. Dans une analyse, les coûts de mauvais classement sont rarement unitaires et symétriques. Dans un problème à 2 classes (malade vs. non-malade par exemple), diagnostiquer l'absence de la maladie chez une personne souffrante n'a pas les mêmes implications que la situation inverse. Il faudrait en tenir compte durant la construction du modèle de prédiction.

Cette méthode est une variante de C4.5 intégrant explicitement la matrice de coûts de mauvais classement lors de l'exploration de l'espace de solutions. Elle a été mise en œuvre dans le cadre d'une étude réelle en partenariat avec une entreprise. Les résultats ont été publiés.

Schématiquement, par rapport à l'algorithme de base C4.5, nous pouvons tenir compte des coûts de 2 manières : (1) durant la phase d'expansion de l'arbre, lors du calcul du critère de segmentation, les expérimentations montrent que cette phase n'est pas très déterminante (Drumond et Holte, 2000) ; (2) durant la phase de post élagage, nous ne calculons plus une erreur pessimiste pour décider de la suppression des feuilles, mais plutôt un coût pessimiste, qui tient compte du poids des sommets.

Il existe un grand nombre de techniques permettant d'introduire les coûts de mauvais classement lors de l'induction. Notre méthode s'est beaucoup inspirée des travaux de Bradford et al. (1998), citée en référence. Elle a le mérite de produire le classifieur en un seul passage sur les données, à la différence des approches basées sur la (re)pondération des observations.

L'intérêt de cette méthode est mis en avant dans un didacticiel traitant de la détection automatique de spams dans les courriels. Nous y apprenons également comment procéder pour introduire les informations sur les coûts dans Sipina.

Paramètres.

CL (confidence level) for pessimistic pruning et Size of Leaves sont les mêmes paramètres que pour C4.5.
Handling costs Growing : Tenir compte des coûts durant la phase d'expansion de l'arbre.
Handling costs Pruning : Tenir compte des coûts durant la phase de post élagage de l'arbre.

Références.

J.H. Chauchat, R. Rakotomalala, M. Carloz, C. Pelletier, « Targeting customer groups using gain and cost matrix : a marketing application », Proc. of Data Mining for Marketing Applications Workshop, PKDD'2001, pp. 1-13, 2001.
J. Bradford, C. Kunz, R. Kohavi, C. Brunk, C. Brodley, « Pruning decision trees with misclassification costs », Proc of 10th ECML, pp. 131-136, 1998.
C. Drummond, R. Holte, « Exploiting the cost of (in)sensitivity of decision tree splitting criteria », Proc. of ICML, pp.239-246, 2000.

Repost 0
28 mars 2008 5 28 /03 /mars /2008 09:40
Description. C'est une généralisation de C4.5 où, plutôt que d'utiliser l'entropie de Shannon pour le calcul du gain ratio, nous introduisons les entropies généralisées de type beta.

L'algorithme de base reste donc C4.5, intégrant notamment le post élagage avec l'erreur pessimiste. Seul la phase d'expansion est modifiée, le choix de la variable de segmentation repose sur l'entropie généralisée.

En modulant le paramètre « beta », nous retrouvons les mesures usuelles (indice de gini, entropie de shannon, distance de Mantaras, etc.).

Paramètres.

CL (confidence level) for pessimistic pruning
: Niveau de confiance pour le calcul de l'erreur pessimiste, qui est simplement la borne haute de l'intervalle de confiance de l'erreur.
Beta
: Paramètre associé à l'entropie généralisée. Beta = 1, entropie de Shannon ; Beta = 2, indice de Gini, etc.
Improved Gain Ratio
: Lorsque cette option est cochée, le gain d'information est normalisée avec l'entropie marginale des feuilles, exactement à la manière du Gain ratio de Quinlan (1993).

Références.

R. Rakotomalala, S. Lallich, "Handl.ing noise with generalized entropy of type beta in induction graphs algorithm", Proc. Int. Conf. on Computer Science and Informatics, pp. 25-27, 1998.
R. Rakotomalala, S. Lallich, S. Di Palma, « Studying the behavior of generalized entropy in induction trees using a m-of-n concept », Proc. of 3rd European Conf. on KDD, pp. 510-517, 1999.
I. Taneja, « Generalized Information Measures and their Applications » ; voir en particulier le chapitre 3 « Entropy-type Measures - Entropy of Degree s and Degress (r,s) », Departemento de Matematica, UFSC, Brazil, 2001.

 

Repost 0
28 mars 2008 5 28 /03 /mars /2008 06:59
Description. La méthode de référence au sein de la communauté « apprentissage automatique ». Vers la fin des années 1980, Quinlan a publié d'innombrables variantes de son algorithme de base, ID3 (Quinlan, 1979). Avec C4, puis C4.5, il est arrivé à une sorte d'aboutissement dont il a résumé les grandes lignes dans son ouvrage « C4.5: Programs for Machine Learning ».

Au premier abord, cet ouvrage laisse perplexe. Près de 60% du texte (pages 109 à 288) est constitué du code source en C de son programme. On se sent un peu spolié de l'avoir payé aussi cher.

Pour ce qui est du texte utile (pages 1 à 107), on est étonné dans un premier temps du faible niveau technique, avec très peu de formules ou de démonstrations.

Dans un second temps, on se rend compte que l'auteur a réellement pris beaucoup de recul par rapport à la méthode, allant avant tout à l'essentiel, sans essayer de noyer tout cela dans un charabia pseudo-mathématique comme on le voit trop souvent hélas dans les monographies. L'exposé est très clair, accessible pour des non spécialistes. L'auteur s'attache à mettre en évidence la quintessence de l'induction par arbres. Il aborde les sujets clés tels que le choix des variables de segmentation, le post-élagage, l'extraction des règles à partir d'un arbre, la discrétisation floue lors du traitement des variables continues, etc.

Notre implémentation s'appuie sur deux aspects essentiels de C4.5, décrits dans l'ouvrage : le choix de la variable de segmentation avec le gain ratio ; le post élagage avec le principe de l'erreur pessimiste. Notons que Quinlan lui même avait mis en ligne le code source de son application. Au fil des versions, un nombre très important d'options destinées à bonifier l'apprentissage, mais ne remettant pas en cause le principal, se sont greffées (jusqu'à la Release 8). Nous ne les avons pas implémentées.

Les qualités de C4.5 ne sont plus à démontrer. Par rapport aux autres techniques, nous dirons qu'elle a tendance à produire des arbres plus grands, plus profonds. Ceci d'autant plus que l'effectif du fichier est important.

Une version commerciale C5.0 a vu le jour par la suite, son contenu scientifique n'est pas connu.

Paramètres.

CL (confidence level) for pessimistic pruning
: Niveau de confiance pour le calcul de l'erreur pessimiste, qui est simplement la borne haute de l'intervalle de confiance de l'erreur.
Size of leaves
: Taille minimum des feuilles issues de la segmentation. Il faut que 2 des feuilles au moins ait un effectif supérieur ou égal à ce seuil pour que la segmentation soit acceptée.

Références.

R. Quinlan, « C4.5: Programs for Machine Learning », Morgan Kaufman Publishers, 1993.
R. Kohavi, R. Quinlan, « Decision Tree Discovery », in Handbook of Data Mining and Knowledge Discovery, Klosgen & Zytkow Editors, Chapter 16.1.3, pages 267-276, Oxford University Press, 2002.
Repost 0
27 mars 2008 4 27 /03 /mars /2008 16:58
Description. Ma méthode préférée, celle que je présente en priorité dans mes enseignements. Elle est directement dérivée de CHAID. Elle apporte quelques améliorations : le critère t de Tschuprow est substitué au KHI-2, essentiellement parce qu'il est normalisé ; des paramètres supplémentaires sont introduits pour mieux contrôler la taille de l'arbre.

Paramètres.
P-level for splitting nodes :
Risque critique du test d'indépendance du KHI-2 lors de la segmentation. Si la p-value du test est supérieur à ce seuil, le partitionnement est refusé. Plus on diminue ce seuil, plus petit sera l'arbre de décision.
P-level for merging nodes
: Risque critique du test d'équivalence distributionnelle (basé aussi sur une statistique du KHI-2) lors de la fusion. Si la p-value du test est plus petit que ce seuil, les sommets ne sont pas fusionnés. Plus le seuil sera grand, moins nous serons enclins à fusionner, plus l'arbre sera large.
Ajustement de Bonferroni
: Les p-value calculées sont faussées car, à chaque étape, nous multiplions les tests pour choisir la meilleure configuration, augmentant ainsi la chance de trouver une segmentation fallacieusement intéressante. Pour contrecarrer cette propension, on peut introduire la correction de Bonferroni, bien connue dans les comparaisons multiples en statistique. A mon sens, mieux vaut ne pas trop s'appuyer sur ce paramètre qui donne l'illusion de « vérité statistique ». Nous sommes dans le cadre de l'induction, si nous souhaitons guider l'apprentissage vers des solutions qui nous conviennent plus (arbre plus petit et/ou moins large), mieux vaut, en toute conscience, manipuler les paramètres « p-level ».
Max. depth
: Ce paramètre permet de limiter la profondeur de l'arbre. Il a une vraie utilité pratique. Dans la majorité des cas, les utilisateurs lancent un premier traitement « pour voir », prendre connaissance des données, comprendre les différentes interactions entre les variables. Il est tout à fait inutile dans cette première étape de construire un arbre qui peut être immense, illisible, qui rebuterait plus qu'autre chose. Par la suite, l'utilisateur peut le modifier pour produire un arbre performant.
Min size of node to split
: Il s'agit de l'effectif minimum pour segmenter. Si un sommet comporte un effectif inférieur à ce seuil, le partitionnement ne sera même pas lancé.
Min size of leaves
: Il s'agit de l'effectif d'admissibilité. Lors de la segmentation d'un nœud, on vérifie si toutes les feuilles produites ont un effectif supérieur ou égal à ce seuil. Dans le cas contraire, la segmentation est refusée, SIPINA choisira la variable suivante (si elle passe les critères de segmentation).

Référence. R. Rakotomalala, " Arbres de décision ", in Revue Modulad, n°33, 2005.


Repost 0
27 mars 2008 4 27 /03 /mars /2008 16:42
Description. CHAID est la variante supervisée (variable à prédire catégorielle) des techniques issues de AID (Morgan et Sonquist, 1963), considérée comme l'ancêtre de toutes les méthodes de segmentation.

Cette méthode se démarque de deux manières : le critère de segmentation est le KHI-2 ; les feuilles produites par un partitionnement peuvent être fusionnées si elles présentent des profils (distributions) identiques.

Ces deux particularités se complètent fort heureusement. En effet, le KHI-2 a la fâcheuse tendance de favoriser les variables comportant un grand nombre de modalités. Avec le processus de fusion, on évite l'élaboration d'arbres trop « larges ».

La méthode CHAID est très largement diffusée, très populaire auprès des statisticiens, elle est présente dans de nombreux logiciels commerciaux. Elle l'est moins souvent en revanche dans les logiciels libres, elle est peu connue de la communauté « machine learning ».

Paramètres.

P-level for splitting nodes : Risque critique du test d'indépendance du KHI-2 lors de la segmentation. Si la p-value du test est supérieur à ce seuil, le partitionnement est refusé. Plus on diminue ce seuil, plus petit sera l'arbre de décision.
P-level for merging nodes : Risque critique du test d'équivalence distributionnelle (basé aussi sur une statistique du KHI-2) lors de la fusion. Si la p-value du test est plus petit que ce seuil, les sommets ne sont pas fusionnés. Plus le seuil sera grand, moins nous serons enclins à fusionner, plus l'arbre sera large.
Ajustement de Bonferroni : Les p-value calculées sont faussées car, à chaque étape, nous multiplions les tests pour choisir la meilleure configuration, augmentant ainsi la chance de trouver une segmentation fallacieusement intéressante. Pour contrecarrer cette propension, on peut introduire la correction de Bonferroni, bien connue dans les comparaisons multiples en statistique. A mon sens, mieux vaut ne pas trop s'appuyer sur ce paramètre qui donne l'illusion de « vérité statistique ». Nous sommes dans le cadre de l'induction, si nous souhaitons guider l'apprentissage vers des solutions qui nous conviennent plus (arbre plus petit et/ou moins large), mieux vaut, en toute conscience, manipuler les paramètres « p-level ».

Référence.
G. Kass, « An exploratory technique for investigating large quantities of categorical data », Applied Statistics, 29(2), pp. 119-127, 1980.

 

Repost 0