lundi 31 mars 2008

Statistiques descriptives comparatives

Le travail du statisticien consiste souvent à calculer des statistiques descriptives comparatives à partir de tris à plat ou tris croisés (à plusieurs niveaux). L’intérêt de ces approches assez frustes est que la lecture de ces résultats ne nécessite pas de compétences particulières. Elles permettent de comparer et de caractériser les spécificités d’une sous-population à partir d’une série de descripteurs.

Dans ce didacticiel, nous montrons l’utilisation de deux composants qui permettent de mettre en œuvre facilement ces opérations de comparaison entre sous-populations.

Pour marquer les différences sur les descripteurs, nous utilisons l’indicateur « valeur test ». Il s’agit de la statistique du test de comparaison de moyennes (variables quantitatives) ou de proportions (variables qualitatives). Il confronte la moyenne (proportion) calculée dans l’échantillon global et dans le sous-échantillon correspondant au groupe.

Bien sûr, il ne s’agit pas d’un test au sens rigoureux du terme, les échantillons ne sont pas indépendants. Il faut surtout le prendre comme une référence qui permet de positionner les différentes variables. En effet, étant souvent exprimés dans des unités différentes, elles ne sont pas directement comparables.

Mots clés : comparaison de populations, tri à plat, tri croisé
Composants : Group characterization, Group Exploration
Lien : fr_Tanagra_Group_Exploration.pdf
Données : autos.xls
Référence : Lebart, Morineau, Piron « Statistique exploratoire multidimensionnelle », Dunod, 2000 ; pages 181 à 184.

Travailler sur les corrélations partielles

Le coefficient de corrélation linéaire mesure l'intensité de la liaison entre deux variables quantitatives. Il est utilisé dans de nombreuses situations, entre autres dans l'analyse en composantes principales (ACP) pour résumer les principales informations portées par un fichier de données.

Pour pratique qu'il soit, le coefficient de corrélation peut être trompeur. L'extrapolation de la corrélation à la causalité doit être faite avec précaution. Notamment parce qu'il peut y avoir une ou plusieurs variables supplémentaires, connues ou inconnues, qui influent sur les variations des variables étudiées, laissant à penser qu'il existe un lien entre ces variables. Ces tierces variables, on parle de facteurs confondants en médecine, sont la cause de bien des problèmes dans les études réelles. Elles induisent des conclusions totalement faussées. Bien souvent, nous devons nous en remettre à l'expertise du domaine pour les circonscrire. Il importe alors de les traiter convenablement.

Dans ce tutoriel, nous montrons le fonctionnement du composant RESIDUAL SCORES de TANAGRA. Son rôle est d'enlever dans les variables cibles la variabilité causée par une série de variables annexes, qui ne semblent pas directement impliquées dans l'étude, mais qui en réalité pèsent significativement sur les résultats. Cela permet de mettre en oeuvre des études « toutes choses égales par ailleurs » où l'on ramène l'ensemble des variables à un référentiel commun.

Nous travaillons sur un fichier qui recense les dimensions de différentes parties du corps (circonférence des chevilles, du coude, du genou, de la taille, des hanches, etc.). L'objectif est de vérifier s'il existe un lien entre les dimensions de ces différentes parties du corps. Trois variables supplémentaires sont disponibles : le poids, la taille et le sexe des individus étudiés. A priori, ces variables n'ont pas de rôle direct à jouer dans notre étude. Nous verrons qu'en réalité, elles tiennent une place centrale.

Mots clés : corrélation partielle, analyse en composantes principales
Composants : Principal Component Analysis, Scatterplot, 0_1_Binarize, Residual Scores, VARHCA
Lien : fr_Tanagra_PartialCorrelation.pdf
Données : body.xls
Références :
D. Garson, « Partial Correlation »
Wikipedia, « Partial Correlation »

Classification de variables

Dans la majorité des ouvrages, la classification de variables est décrite très sommairement. Les auteurs se contentent le plus souvent de la présenter comme un cas particulier de la typologie où le coefficient de corrélation r est utilisé pour mesurer la proximité entre les variables, (1- r) étant alors un indice de dissimilarité naturel.

Pourtant, la classification de variables peut être très utile dans la recherche des structures sous-jacentes dans les données. Elle permet de repérer les groupes de variables redondantes, emmenant le même type d’information ; de distinguer les groupes de variables orthogonales, rapportant des informations complémentaires. Nous disposons ainsi de précieuses indications sur l’architecture des données.

Cette méthode peut également être mise en œuvre dans une stratégie de réduction/sélection des variables. Pour chaque groupe de variables, une variable « moyenne » unique pourra être produite et utilisée dans les analyses ultérieures, en tant que variable prédictive présentée aux méthodes supervisées par exemple, réduisant considérablement la dimensionnalité.

Avec la version 1.4.16, nous introduisons dans TANAGRA plusieurs techniques de classification de variables inspirées par la lecture de l’ouvrage de Nakache et Confais (2005). Nous nous sommes plus particulièrement penchés sur les techniques de classification autour de composantes latentes basées sur les travaux de Vigneau et Qannari (2003), à l’origine notamment de la fameuse procédure VARCLUS (Variable Clustering) implémentée dans le logiciel SAS.

Dans ce didacticiel, nous présentons 3 méthodes de classification de variables, toutes basées sur le principe du regroupement autour des variables latentes. La première VARHCA est algorithme ascendant hiérarchique. Elle est intéressante dans la mesure où nous disposons d’un dendrogramme qui permet de visualiser l’évolution de l’agrégation, et par là de détecter ce qui serait le bon nombre de groupes. La seconde VARKMEANS est une méthode de réallocation. Avec les avantages et inconvénients qui s’y rattachent. La troisième VARCLUS est une méthode descendante, particulière adaptée lorsque le nombre de variables à traiter est important.

Une large partie du tutoriel est consacrée à la l’interprétation. Les outils sont nombreux, il importe de bien comprendre les informations que nous procurent les tableaux de résultats.

Mots clés : classification automatique de variables, variable clustering, composantes latentes
Composants : VARHCA, VARKMeans, VARCLUS
Lien : fr_Tanagra_VarClus.pdf
Données : crime_dataset_from_DASL.xls
Références :
E. Vigneau et E. Qannari, « Clustering of variables around latent components », Simulation and Computation, 32(4), 1131-1150, 2003.
J.P. Nakache et J. Confais, « Approche Pragmatique de la Classification », TECHNIP, 2005, chapitre 9, pages 219 à 239.
SAS OnlineDoc – Version 8, « The VARCLUS Procedure ».

K-Means sur variables qualitatives

L’algorithme des K-Means est une méthode de classification automatique (clustering), on l’appelle également K-Moyennes ou encore Nuées dynamiques (bien que cette dénomination constitue en réalité une généralisation).

L’idée est très simple. On choisit K individus au hasard, qui constituent les noyaux initiaux. On fait passer toutes les observations. On affecte chaque observation au noyau qui lui est le plus proche. Les noyaux sont alors remis à jour. Puis on réitère le passage de tous les individus jusqu’à ce que la solution soit stable.

Sa simplicité fait la popularité de cette approche. Autre avantage notable, il n’est pas nécessaire de calculer au préalable les distances deux à deux entre tous les individus, opération très gourmande en temps et en espace mémoire dans certains algorithmes de clustering.

La méthode des K-Means présente néanmoins des inconvénients. On citera notamment l’obligation de fixer au préalable le nombre de groupes, sans qu’aucune indication ne soit fournie. La CAH – classification ascendante hiérarchique - par exemple ne donne pas non plus le bon nombre de groupes, en revanche avec le dendrogramme, nous disposons des indications sur le partitionnement adéquat. On citera aussi la forte dépendance de la méthode au choix des noyaux initiaux. La méthode peut converger vers un optimum local. C’est pour cette raison que l’on propose dans Tanagra (et dans tous les autres logiciels) de réitérer plusieurs fois le processus complet en changeant les conditions initiales.

Dans ce didacticiel, nous abordons un problème supplémentaire. Les descripteurs sont catégoriels. Nous ne pouvons pas directement lancer les K-Means surtout avec la distance euclidienne usuelle. On propose de travailler en 2 étapes : (1) réaliser une analyse en composante multiple ; (2) lancer les K-Means sur les x premiers axes factoriels. L'étape (1) de construction de variables nous permet d'utiliser par la suite l'algorithme standard des K-Means basé sur la distance euclidienne.

Pour interpréter les groupes, nous utiliserons dans un premier temps les statistiques descriptives comparatives. Malgré (ou grâce à) sa simplicité, elle est foncièrement univariée, cette approche est très populaire. Elle permet de détecter rapidement les principales variables qui différencient fortement les groupes.

Dans un second temps, nous comparons les groupes obtenus avec une variable supplémentaire, qui constituerait les classes « naturelles » des observations. On parle dans ce cas de validation externe. Cette démarche est très utilisée dans la recherche, lorsque l’on veut montrer l’efficacité d’une méthode de classification.

Mots clés : classification automatique, clustering, k-means, k-moyennes, nuées dynamiques, analyse factorielle de correspondances mutliples, validation externe, interprétation des classes
Composants : Multiple Correspondance Analysis, K-Means, Group characterization, Cross Tabulation
Lien : dr_clustering_validation_externe.pdf
Données : dr_vote.bdm
Références :
Wikipédia, « K-means algorithm ».
G. Bisson, « Evaluation & Catégorisation ».

dimanche 30 mars 2008

Régression logistique multinomiale

La régression logistique est très répandue pour les problèmes de prédiction ou d’explication d’une variable dépendante binaire (malade oui/non, défaillance oui/non, client potentiel oui/non, etc.) à partir d’une série de variables explicatives continues, binaires ou binarisées (dummy variables). On parle dans de cas de régression logistique binaire.

Lorsque la variable dépendante possède plusieurs catégories non ordonnées (K > 2), on parle de régression logistique multinomiale (on parle aussi de Régression logistique polytomique à variable dépendante nominale). Elle est peu (ou moins) connue, pourtant cette configuration est finalement assez courante. De plus, elle est directement traitée par les autres méthodes d’apprentissage telles que l’analyse discriminante prédictive, les arbres de décision, etc.

Grosso modo, la régression logistique multinomiale consiste à désigner une catégorie de référence, la dernière (Kème) par exemple pour fixer les idées, et à exprimer chaque logit (ou log-odds) des (K-1) modalités par rapport à cette référence à l’aide d’une combinaison linéaire des variables prédictives.

Dans ce didacticiel, nous montrons la mise en œuvre de la régression logistique multinomiale dans TANAGRA. Nous voulons expliquer, pour une série de produits de même catégorie, la marque (3 marques possibles) choisie par 735 consommateurs à partir de leur age et de leur sexe. Ces données ont déjà été traitées par ailleurs à l’aide du logiciel R. Les données et les résultats associés sont disponibles en ligne.

Mots clés : régression logistique multinomiale
Composants : Supervised Learning, Multinomial Logistic Regression
Lien : fr_Tanagra_Multinomial_Logistic_Regression.pdf
Données : brand_multinomial_logit_dataset.xls
Référence : A. Slavkovic, « Multinomial Logistic Regression Models – Baseline-Category Logit Model », in « STAT 504 – Analysis of Discrete Data », Pensylvania State University, 2007.

Stepdisc – Analyse discriminante

La sélection de variables est un processus très important en apprentissage supervisé. Nous disposons d’une série de variables candidates, nous cherchons les variables les plus pertinentes pour expliquer et prédire les valeurs prises par la variable à prédire. Les objectifs sont bien souvent multiples : nous réduisons le nombre de variables à recueillir pour le déploiement du système ; nous améliorons notre connaissance du phénomène de causalité entre les descripteurs et la variable à prédire, ce qui est fondamental si nous voulons interpréter les résultats pour en assurer la reproductibilité ; enfin, mais pas toujours, nous améliorons la qualité de la prédiction, le ratio nombre d’observations / dimension de représentation étant plus favorable.

Dans ce tutoriel, nous présentons la méthode STEPDISC (Stepwise Discriminant Analysis). Elle repose le critère du LAMBDA de WILKS. Géométriquement, il s’agit de trouver le sous-espace de représentation qui permet un écartement maximal entre les barycentres des nuages de points conditionnels c.-à-d. les nuages de points associés à chaque valeur de la variable à prédire. Elle est donc particulièrement bien adaptée à l’analyse discriminante linéaire qui utilise également le même critère, d’où son appellation. Elles sont systématiquement associées dans les logiciels.

TANAGRA implémente deux stratégies. L’approche FORWARD consiste à partir de l’ensemble vide, choisir la variable induisant la meilleure amélioration du LAMBDA, et la sélectionner si amélioration est statistiquement significative ; nous procédons itérativement en ajoutant unes à unes les variables jusqu’à ce que l’adjonction d’une variable n’apporte plus d’amélioration. A l’inverse, l’approche BACKWARD, part de l’ensemble des variables candidates, recherche la variable dont le retrait entraînerait la dégradation la plus faible du LAMBDA, et la retire effectivement si cette dégradation n’est pas statistiquement significative.

Dans notre exemple, nous partons de 60 descripteurs candidats pour arriver à un modèle à 7 variables, tout en conservant le même niveau de performances. Autre résultat important, les procédures FORWARD et BACKWARD peuvent aboutir à des sous-ensembles différents. La stratégie d’exploration n’étant pas la même, il ne faut pas s’en émouvoir. Ces techniques fournissent avant tout des scénarios de résultats. Charge à nous, en accord avec les connaissances du domaine, de déterminer la solution la plus adaptée.

Mots clés : stepdisc, sélection de variables, analyse discriminante prédictive
Composants : Supervised Learning, Linear discriminant analysis, Bootstrap, Stepdisc
Lien : fr_Tanagra_Stepdisc.pdf
Données : sonar_for_stepdisc.xls
Référence : SAS/STAT User’s Guide, « The STEPDISC Procedure »

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 ».

Listes de décision (vs. arbres de décision)

Les listes de décision (decision list en anglais) font partie des méthodes d’apprentissage supervisé très en vogue au début des années 90. La méthode est très proche de l’induction par arbres, elle produit des règles de production triées et mutuellement exclusives du type « Si condition_1 Alors conclusion_1 Sinon Si condition_2 Alors conclusion_2 Sinon Si… ».

Si le biais de représentation est très proche des arbres de décision, les DL construisent des hyper-rectangles les plus homogènes possibles du point de vue de la variable à prédire, le biais de préférence est différent, elles procèdent par « Separate-and-conquer » et non par « Divide-and-conquer », elles disposent donc un degré de liberté supplémentaire pour mettre en avant les solutions les plus spécialisées. Cette liberté a un prix, cette méthode est souvent sujette au sur apprentissage à force de vouloir détecter à tout prix les sous populations les plus intéressantes, son paramétrage est alors primordial pour éviter qu’elle ne produise des règles couvrant trop peu d’individus et de ce fait non significatives.

La méthode que nous avons implémentée dans TANAGRA est très largement inspirée de CN2 (Clark & Niblett, ML-1989). Nous avons pris quelques libertés : (1) en simplifiant l’exploration de l’espace des hypothèses, nous utilisons un « hill-climbing » simple plutôt qu’un « best-first search », nettement plus coûteux en CPU mais pas vraiment plus efficace ; (2) en introduisant un paramètre supplémentaire, le support de la règle, pour éviter que des règles sur-spécialisées et non-significatives apparaissent.

Dans ce didacticiel, nous comparons les performances de CN2 avec CART. Notons que CN2 ne sait pas manipuler directement les attributs continus, nous devons les discrétiser au préalable, nous utilisons la méthode MDLPC (Fayyad et Irani, 1993) pour cela. Les taux d’erreur sont mesurés par bootstrap. On constate que les méthodes se valent. Ce qui n’est pas étonnant, les biais de représentation sont (quasiment) identiques.

Mots clés : CN2, decision list, listes de décision, arbres de décision, CART, discrétisation
Composants : Supervised Learning, MDLPC, Decision List, C-RT, Bootstrap
Lien : fr_Tanagra_DL.pdf
Données : dr_heart.bdm
Référence : P. Clark, « CN2 – Rule induction from examples ».

vendredi 28 mars 2008

Support vector machine (SVM) multi-classes

Les machines à vecteurs de support (ou machine à vaste marge) ont été définies à l’origine pour les problèmes à 2 classes c.-à-d. les cas où la variable à prédire prend 2 modalités (les positifs contre les négatifs). Notre composant SVM ne traite que ce type de problème d’ailleurs.

Pour passer à des problèmes multi-classes, il faut proposer de nouvelles solutions. TANAGRA fait appel au module externe LIBSVM (libre et open source) dans ce cas. J’y vois essentiellement 2 avantages : on dispose d’une solution directe, déjà débuguée, leur bibliothèque est largement diffusée ; LIBSVM, avec un algorithme ad hoc, propose un niveau de performances (rapidité) que je n’ai jamais pu approcher avec mes propres implémentations (dérivées de l’algorithme de Platt, 1998).

Notre tutoriel traite d’un problème à deux classes. Mais le composant C-SVC que nous présentons peut directement traiter un problème multi-classes, sans qu’aucune préparation des données ne soit nécessaire.

Dans notre exemple, on ne peut que s’extasier devant les performances de l’implémentation, quelques secondes suffisent pour produire un classifieur sur un jeu de données comptant une centaine d’observations et plusieurs milliers de variables. Ce problème de classement de protéines est par ailleurs traité dans un autre didacticiel où nous utilisons une approche différente, basée sur une construction de variables à l’aide de l’algorithme NIPALS.

Mots clés : SVM, support vector machine, machine à vaste marge, SVM multi-classes, classement de protéines
Composants : Supervised Learning, C-SVC, Bootstrap
Lien : fr_Tanagra_CSVC_LIBSVM.pdf
Données : Tanagra_Nipals.zip
Référence : C.C. Chang, C.J. Jin, « LIBSVM – A library for Support Vector Machine »

Support vector machine (SVM)

Les machines à vecteurs de support (ou machine à vaste marge) sont des techniques d’apprentissage supervisé qui reposent sur deux idées fortes : (1) il repose sur le principe de la maximisation de la marge ; (2) lorsque les données ne sont pas linéairement séparables, il est possible, par le principe des noyaux, de se projeter dans un espace de plus grande dimension pour trouver la solution adéquate, sans avoir à former explicitement ce nouvel espace de représentation (Wikipedia, voir références).

Dans ce tutoriel, nous montrons la mise en œuvre des SVM de TANAGRA. Notre implémentation reprend l’algorithme de Platt (1998 - Algorithme SMO), directement inspiré du code source en Java de Weka, un logiciel très populaire dans la communauté « apprentissage automatique ». Nous montrons que dans un problème avec un ratio nombre d’individus/nombre de variables défavorable, les SVM résistent mieux à la dimensionnalité que l’analyse discriminante. Nous verrons également qu’en passant à un noyau polynomial de degré 2, les performances sont encore améliorées.

Sur notre fichier, nous réduisons significativement le taux d’erreur, il passe de 25% (analyse discriminante) à 15% (SVM – Noyau polynomial). Le SVM linéaire propose un taux de 20%. Ce n’est qu’un exemple illustratif bien entendu, ça n’a pas valeur de preuve. Quoiqu'il en soit, il est avéré que les SVM, surtout linéaires, résistent fort bien à la fameuse « malédiction de la dimensionnalité ». Contrairement à l’analyse discriminante qui peut s’effondrer dramatiquement dans ce contexte.

Les taux d’erreur sont mesurés par bootstrap.

Mots clés : SVM, support vector machine, machine à vaste marge, analyse discriminante linéaire, fonction noyau
Composants : Supervised Learning, SVM, Linear discriminant analysis, Bootstrap
Lien : fr_Tanagra_SVM.pdf
Données : sonar.xls
Références:
Wikipédia (FR) – « Machine à vecteurs de support »
Wikipedia (US) – « Support vector machine »
Weka – « Weka 3: Data Mining Software in Java »

jeudi 27 mars 2008

Construction de variables avec NIPALS

Nous avons déjà parlé par ailleurs de la régularisation en apprentissage supervisé. L’idée est de réduire la dimensionnalité tout en préservant l’information utile dans les données. L’apprentissage supervisé subséquent ne peut qu’en bénéficier.

Nous voulons mettre en œuvre la méthode des plus proches voisins (K-PPV) dans un problème de prédiction où nous disposons d’une centaine d’observations, et… plusieurs milliers de descripteurs. Avant même de lancer les calculs, nous savons que ça ne donnera rien de bon, surtout pour cette méthode. Les estimations locales des probabilités, dans le voisinage des points à classer, sont très mauvaises. Les performances en classement seront désastreuses.

Nous voulons réduire la dimensionnalité, en utilisant l'analyse en composantes principales par exemple. L’ACP permet de projeter les individus dans un sous-espace, tout en préservant les proximités entre eux. Si l’idée est bonne, elle est impraticable. En effet, calculer une matrice de variance covariance de taille 6740 x 6740 n’est déjà pas très malin (au mieux, on utilise 173 Mo de mémoire vive en double précision). Tenter de la diagonaliser relève d’un optimisme forcené.

La méthode NIPALS paraît tout indiquée dans ce contexte. Elle permet de retrouver les axes factoriels de l’ACP, avec une précision moindre certes, sans avoir à former explicitement la matrice de variance covariance. L’avantage est double : moindre occupation mémoire et temps de calculs autrement plus accessibles. L’inconvénient, infime au regard des avantages, est que nous devons fixer à l’avance le nombre de facteurs à retenir.

Dans ce didacticiel, nous montrons comment élaborer les facteurs avec la méthode NIPALS, puis les présenter aux K-PPV. Le gain de temps est énorme. Il s’accompagne de surcroît d’une amélioration des performances en prédiction. L’amélioration du rapport entre le nombre d’observations et le nombre de variables est primordiale dans ce contexte.

Le taux d’erreur est mesuré par bootstrap.

Mots clés : NIPALS, analyse en composantes principales, ACP, méthode des plus proches voisins, K-PPV, K-NN, méthodes de ré échantillonnage, bootstrap
Composants : Supervised Learning, NIPALS, K-NN, Bootstrap
Lien : fr_Tanagra_NIPALS.pdf
Données : Tanagra_Nipals.zip
Références :
M. Tenenhaus, « La régression PLS – Théorie et pratique », Technip, 1998 ; Chapitre 6, « L’algorithme NIPALS », pages 61 à 73.
R. Rakotomalala, « Autres méthodes supervisées extrapolées du schéma bayesien – La méthode des plus proches voisins »

Tanagra en ligne de commande

L’expérimentation est indissociable du data Mining. Une grande partie de notre travail est de déterminer les paramètres adaptés, tester des configurations différentes, comparer des performances d’algorithmes sur les mêmes données, reproduire des traitements sur des fichiers de données similaires.

A l’évidence, la définition de traitements sous forme de diagramme, appelé pompeusement « programmation visuelle », n’est absolument pas adaptée dans ce contexte. Il faudrait disposer d’un langage de programmation avec tous les attributs associés : boucles, branchement conditionnel, etc.

Avant d’en arriver à ce stade, nous pouvons quand même tirer parti de certaines fonctionnalités de Tanagra pour monter des expérimentations. En effet, il est possible de lancer directement le logiciel en ligne de commande. Il nous suffit donc de définir un diagramme type, enregistré au format TDM (qui est un fichier texte rappelons-le, aisément manipulable en dehors du logiciel), et de le transmettre à Tanagra.

On peut même aller plus loin en définissant des traitements par lots dans un fichier .BAT (pour le DOS). Différentes sessions de Tanagra sont lancés, les résultats sont sauvegardés régulièrement. C’est la démarche que nous proposons dans ce didacticiel. Nous étudions les performances comparées du modèle bayesien naïf, avec et sans sélection de variables, sur des fichiers de structure similaire.

Enfin, nous ne l’abordons pas dans ce tutoriel, mais si nous souhaitons véritablement monter des expérimentations à grande échelle. La solution passe par l’écriture d’un programme simple qui génère automatiquement les fichiers TDM avec les configurations souhaités, et qui les transmet à Tanagra. Les résultats sont collectés au fur et à mesure. Le nombre de variantes que l’on peut tester ainsi devient très important.

Mots clés : traitements automatisés, expérimentation
Composants : Supervised Learning, Naive bayes, Cross validation, FCBF filtering
Lien : dr_utiliser_tanagra_en_mode_batch.pdf
Données : tanagra_batch_execution.zip

Echantillonnage dans les arbres de décision

Stratégie d'échantillonnage pour les arbres de décision. Dans tous les algorithmes d'induction d'arbres, SIPINA introduit une option d'échantillonnage. L'idée est la suivante : plutôt que de travailler sur l'ensemble des individus disponibles sur chaque noeud pour choisir la variable de segmentation, nous proposons d'extraire un sous-échantillon et de calculer sur ces observations les indicateurs appropriés (gain d'entropie, statistique du khi-2, indice de Gini, etc.).

L'expérimentation montre que l'ordonnancement des variables de segmentation sur chaque noeud reste le même, et de fait, les caractéristiques des arbres produits, notamment les performances en prédiction, sont préservées.

L'intérêt de cette approche est le gain de temps lors de la construction de l'arbre. Il peut être déterminant sur les grandes bases, surtout lorsqu'elles comportent un nombre important de variables continues, nécessitant la répétition du tri des données lors de la discrétisation.

L'échantillonnage sur un noeud est toujours sans remise. Il peut être représentatif (aléatoire simple), équilibré (le même nombre d'observations pour chaque modalité de la variable à prédire), ou stratifié (respectant les proportions de la totalité des observations sur le noeud).

Changement de stratégie dans Tanagra. Notons que par la suite, dans TANAGRA, nous avons adopté une autre stratégie. Toutes les variables continues sont triées une fois pour toutes avant l'induction. Un tableau d'index permet de conserver l'ordre des observations. Lors du traitement d'un noeud, nous y puisons les individus présents. La phase de tri n'est donc plus nécessaire puisque les observations sont déjà ordonnées. Le prix de cette approche est la nécessité de conserver en mémoire le tableau d'index, à savoir 4 octets par observation et par variable. Pourquoi ce revirement ? La raison est simplement pragmatique. En 1998, on disait d'une machine qu'elle était performante lorsqu'elle disposait de 256 Mo de RAM. En 2004, et plus récemment encore, un ordinateur avec 2Go de RAM est tout à fait courant.

Mots clés : arbres de décision, échantillonnage, optimisation des calculs, traitement des grandes bases de données
Référence : J.H. Chauchat, R. Rakotomalala, « A new sampling strategy for building decision trees from large databases », Proc. of IFCS-2000, pp. 199-204, 2000.

mercredi 26 mars 2008

Analyse discriminante sur axes principaux

L’analyse discriminante linéaire possède des qualités évidentes, maintes fois décrites dans de nombreuses publications. Elle souffre toutefois d’une faiblesse criante, elle nécessite l’inversion de la matrice de variance covariance intra-classes. Lorsque la matrice est singulière, le logiciel plante, au moins on sait à quoi s’en tenir. La situation est plus complexe lorsqu’elle est quasi singulière, la technique est très instable et propose des solutions erratiques. Cette situation arrive fréquemment lorsque le nombre de variables se rapproche dangereusement du nombre d’observations, ou lorsque certains prédicteurs sont fortement corrélés.

La régularisation permet de contrôler cette instabilité. Dans leur ouvrage, Lebart et al. (2000) présentent plusieurs techniques. Nous retenons l’analyse discriminante sur axes principaux dans ce didacticiel.

La démarche est la suivante : nous réalisons une analyse en composantes principales sur les variables initiales, nous éliminons les axes correspondant à des valeurs propres nulles ou proches de 0, puis nous réalisons une analyse discriminante sur les facteurs qui ont été retenus.

L’idée sous jacente est de procéder à un lissage où l’on essaie d’épurer les données pour ne retenir que l’information « utile ». Les perturbations annexes, correspondant aux fluctuations d’échantillonnage, traduites par les derniers axes à très faible variance, sont éliminées.

Dans notre exemple, la solution semble idyllique. Cela n’est pas étonnant, nous avons utilisé le fichier « ondes » de Breiman et al. (1984) qui sont en réalité des données synthétiques. La solution est particulièrement adaptée.

Dans la pratique, si cette technique de régularisation permet de stabiliser l’apprentissage, éliminant le problème d’inversion de matrice hasardeuse, elle ne constitue pas pour autant la solution miracle. En effet, les axes principaux de l’ACP sont construits sans tenir compte de l’étiquette des observations. Il y a des cas où cela peut être totalement inapproprié.

Mots clés : régularisation, analyse discriminante linéaire, analyse discriminante prédictive, analyse en composantes principales, ACP
Composants : Supervised Learning, Linear discriminant analysis, Principal Component Analysis, Scatterplot, Train-test
Lien : dr_utiliser_axes_factoriels_descripteurs.pdf
Données : dr_waveform.bdm
Références :
L. Lebart, A. Morineau, M. Piron, « Statistique exploratoire multidimensionnelle », Dunod, 2000 ; pages 269 à 275.
Wikipédia , « Analyse discriminante linéaire »

Validation croisée, bootstrap, leave one out

L’évaluation des classifieurs est une question récurrente en apprentissage supervisé. Parmi les différents indicateurs existants, la performance en prédiction calculée à l’aide du taux d’erreur (ou son complémentaire à 1, le taux de bon classement) est un critère privilégié. Du moins dans les publications scientifiques car, dans les études réelles, d’autres considérations sont au moins aussi importantes : l’évaluation des performances en intégrant les coûts de mauvaise affectation, l’interprétation des résultats, les possibilités de mise en production, etc.

Le taux d’erreur théorique est défini comme la probabilité de mal classer un individu dans la population. Bien entendu, il est impossible de le calculer directement, essentiellement parce qu’il n’est pas possible d’accéder à toute la population. Nous devons produire une estimation. Qui dit estimation dit utilisation d’un échantillon, un estimateur de bonne qualité doit être le moins biaisé possible (en moyenne, on tombe sur la bonne valeur du taux d’erreur théorique), et le plus précis possible (la variabilité autour de la vraie valeur est petite).

Dans la pratique, on recommande de subdiviser l’échantillon en 2 parties : la première, dite échantillon d’apprentissage pour créer le classifieur ; la seconde, dite échantillon test, pour calculer la proportion des erreurs en classement (voir Comparaison de classifieurs). L’erreur ainsi mesurée est non biaisée.Lorsque la base initiale de petite taille, cette démarche n’est plus adaptée. Il faut réserver toutes les données disponibles pour la construction du modèle. Comment alors évaluer les performances du classifieur ainsi produit ?

Les techniques de ré échantillonnage permettent de répondre à cette question. Nous étudierons plus particulièrement la validation croisée, le leave one out, et le bootstrap. Il s’agit de répéter plusieurs fois, sous des configurations pré définies, le schéma apprentissage test. Attention, il s’agit bien d’une estimation de l’erreur du modèle construit sur l’ensemble des données. Les modèles intermédiaires, élaborés lors des apprentissages répétés, servent uniquement à l’évaluation de l’erreur. Ils ne sont pas accessibles à l’utilisateur, ils n’ont pas d’utilité intrinsèque.

Ce didacticiel vise à compléter le cours décrivant les techniques de ré échantillonnage accessible en ligne (voir Référence). L’idée est la suivante : sur des données synthétiques, nous comparons l'erreur évaluée à l'aide des techniques de ré échantillonnage avec le cas, hypothétique, où nous disposons d’un échantillon test de taille virtuellement infinie. Nous pourrons ainsi situer le comportement et la précision des différentes techniques.

Nous utiliserons l’analyse discriminante linéaire (LDA) et les arbres de décision (C4.5) pour illustrer notre propos.

Mots clés : méthodes de ré échantillonnage, évaluation de l’erreur, validation croisée, bootstrap, leave one out, analyse discriminante linéaire
Composants : Supervised Learning, Cross-validation, Bootstrap, Test, Leave-one-out, Linear discriminant analysis, C4.5
Lien : fr_Tanagra_Resampling_Error_Estimation.pdf
Données : wave_ab_err_rate.zip
Référence : R. Rakotomalala, "Estimation de l'erreur de prédiction - Les techniques de ré échantillonnage"

Comparaison de classifieurs – Validation croisée

Comparer les performances en prédiction est souvent mis en avant pour sélectionner le modèle le plus intéressant en apprentissage supervisé. Pour cela, il nous faut donc produire une mesure du taux d’erreur fiable, non biaisée.

Dans la majorité des cas, on subdivise l’échantillon en 2 parties : la première, dite échantillon d’apprentissage pour créer le classifieur ; la seconde, dite échantillon test, pour calculer la proportion des erreurs en classement (voir Comparaison de classifieurs)

Lorsque la base initiale est de petite taille, cette démarche n’est plus adaptée. Il faut réserver toutes les données disponibles pour la construction du modèle. Comment alors évaluer les performances du classifieur ainsi produit ?

Les méthodes de ré échantillonnage apportent une réponse à ce problème. Par une série d’apprentissages-tests répétés sur des fractions de l’échantillon global, elles produisent une estimation de l’erreur en classement du modèle construit sur la totalité des données. Il faut bien entendu que cette estimation soit le moins biaisé possible, et avec une variance faible.

Dans ce didacticiel, nous montrons comment comparer les performances de deux algorithmes d’apprentissage supervisé (K-NN et ID3) à l’aide de l’erreur calculée en validation croisée.

Mots clés : validation croisée, méthodes de ré échantillonnage, comparaison de classifieurs, méthode des plus proches voisins, k-ppv, k-nn, arbres de décision, id3
Composants : Supervised Learning, K-NN, Cross-validation
Lien : dr_comparer_spv_learning.pdf
Données : dr_heart.bdm
Référence : R. Rakotomalala, "Estimation de l'erreur de prédiction - Les techniques de ré échantillonnage"

mardi 25 mars 2008

Courbe ROC pour la comparaison de classifieurs

Une courbe ROC permet de comparer des algorithmes d’apprentissage supervisé indépendamment (1) de la distribution des modalités de la variable à prédire dans le fichier test, (2) des coûts de mauvaises affectations.

La courbe ROC est avant tout définie pour les problèmes à deux classes (les positifs et les négatifs), elle indique la capacité du classifieur à placer les positifs devant les négatifs. Elle met en relation dans un graphique les taux de faux positifs (en abscisse) et les taux de vrais positifs (en ordonnée).

Sa construction s’appuie donc sur les probabilités d’être positif fournies par les classifieurs. Il n’est pas nécessaire que ce soit réellement une probabilité, une valeur quelconque dite « score » permettant d’ordonner les individus suffit amplement.

Il est possible de dériver un indicateur synthétique à partir de la courbe ROC, il s’agit de l’AUC (Area Under Curve – Aire Sous la Courbe), elle indique la probabilité d’un individu positif d’être classé devant un individu négatif. Il existe une valeur seuil, si l’on classe les individus au hasard, l’AUC sera égal à 0.5.

Dans ce didacticiel, nous construisons les courbes ROC de deux méthodes d’apprentissage que nous voulons comparer sur un problème de détection de maladies cardio-vasculaires : l’analyse discriminante linéaire (LDA) et les machines à vecteur de supports (SVM).

Dans la version actuelle (1.4.21 et + récente), le graphique de la courbe est directement construite dans TANAGRA, il n’est plus nécessaire de passer par un tableur.

Mots clés : courbe roc, auc, comparaison de classifieurs, analyse discriminante, svm, support vector machine, scoring
Composants : Sampling, 0_1_Binarize, Supervised Learning, Scoring, Roc curve, SVM, Linear discriminant analysis
Lien : fr_Tanagra_Roc_Curve.pdf
Données : dr_heart.bdm
Références :
R. Rakotomalala – « Courbe ROC »
T. Fawcet – « ROC Graphs : Notes and Practical Considerations of Researchers »

Statistiques descriptives avec SIPINA

SIPINA propose des fonctionnalités de statistiques descriptives. Peu de personnes le savent. En soi l'information n'est pas éblouissante, il existe un grand nombre de logiciels libres capables de produire les indicateurs de la description statistique.

L'affaire devient plus intéressante lorsque l'on couple ces outils avec l'induction d'un arbre de décision. La richesse de la phase exploratoire est décuplée. En effet, chaque nœud d'un arbre correspond à une sous population décrite par une règle. Ce groupe a été constitué de manière à ce que seule une des modalités de la variable à prédire soit représentée. C'est l'objectif de l'apprentissage. Mais qu'en est-il des autres variables ?

L'arbre a une qualité rare, elle met en avant les meilleures variables dans l'induction. Mais elle a le défaut de ses qualités, elle ne donne pas directement d'informations sur les variables qui ont été écartées, encore moins sur les relations entre ces variables. La possibilité de calculer simplement des statistiques descriptives sur les sous populations permet à l'utilisateur d'étudier finement les spécificités de ces groupes, et par là même de mieux caractériser la règle produite par l'induction. C'est ce que nous essayions de mettre en valeur dans ce didacticiel.

Nous utilisons les données HEART_DISEASE_MALE.XLS . Il s'agit de prédire l'occurrence d'un maladie cardiaque (DISEASE) à partir des caractéristiques des individus (AGE, SUCRE dans le sang, etc.). Les données, 209 observations, sont restreintes aux individus de sexe masculin

Mots clés : statistiques descriptives, arbres de décision, exploration interactive
Lien : fr_sipina_descriptive_statistics.pdf
Données : heart_disease_male.xls

vendredi 21 mars 2008

Scoring avec la régression logistique

Un autre exemple de ciblage marketing, l’objectif toujours est d’associer un score à chaque individu permettant de les trier selon leur appétence à un produit.

Par rapport au didacticiel précédent, nous avons deux particularités : on utilise la régression logistique binaire, une méthode très populaire dans le scoring ; le ratio nombre de variables sur nombre d’individus est très élevé, nous imposant une sélection de variables sévère.

L’échantillon est subdivisé en 2 parties, nous construisons le modèle sur la partie apprentissage, nous l’évaluons sur la partie test. Nous utilisons la courbe lift pour comparer les approches. Plus précisément, nous comptabilisons le nombre de positifs que nous arrivons à détecter dans une cible de 300 individus.

Deux conclusions s’imposent dans cet exemple. (1) La sélection de variables diminue considérablement le nombre de descripteurs sans dégrader la qualité du scoring. (2) Selon que l’on adopte une recherche forward ou backward, nous n’obtenons, ni le même nombre de variables, ni les mêmes variables. Mais la qualité du ciblage est quasi identique.

Ce dernier résultat laisse souvent perplexe les praticiens : quel modèle choisir au final ? On pourrait déjà adopter la solution comportant le plus petit nombre de variables. Ca a le mérite de trancher. Mais, à mon sens, il faut surtout voir ces approches comme des outils fournissant des scénarios. Charge à nous, avec une expertise autre que purement statistique (banquier, médecin, etc.), de choisir par la suite la solution la plus appropriée, en adéquation avec les connaissances et les contraintes du domaine.

Mots clés : scoring, ciblage marketing, régression logistique
Composants : Supervised learning, Binary logistic regression, Select examples, Scoring, Lift curve, Forward-logit, Backward-logit
Lien : fr_Tanagra_Variable_Selection_Binary_Logistic_Regression.pdf
Données : dataset_scoring_bank.xls
Références :
R. Rakotomalala – « Ciblage marketing – Construire la courbe Lift »
R. Rakotomalala – « Régression logistique »

jeudi 20 mars 2008

Ciblage marketing (scoring) – Coil challenge

Le ciblage en Data Mining consiste à constituer des groupes d’individus dans lequel nous maximisons le nombre d’éléments « positifs ». L’exemple le plus souvent cité est l’entreprise qui veut faire la promotion d’un produit en envoyant un courrier à ses clients. Les « positifs » sont les personnes qui vont répondre positivement à l’offre. La cible constitue les prospects, les individus contactés. Pour des questions de coûts, il n’est pas possible de solliciter tous les clients. Il faut que dans la cible souhaitée, limitée par un budget souvent, la proportion de personnes positives soit le plus élevé possible.

Parfois, la démarche est inversée : l’entreprise fixe un objectif en parts de marchés, nombre de clients positifs à retrouver, on s’appuiera sur le scoring pour déterminer la cible de plus petite taille possible afin d’obtenir ce résultat.

Au final, nous sommes bien dans un problématique d’apprentissage supervisé à 2 classes : on veut différencier les positifs des négatifs. A la différence qu’il ne s’agit pas prédire absolument l’étiquette des individus, mais plutôt de leur attribuer un score (de positivité) qui permet de trier la base selon l’appétence du client au produit proposé. La matrice de confusion et le taux d’erreur n’ont plus de sens dans ce contexte. On préfèrera un outil spécifique, la COURBE LIFT (GAIN CHART), pour définir la part de marché obtenue à budget fixé, ou inversement, déterminer le budget nécessaire pour obtenir une part de marché fixée.

Ce didacticiel montre la mise en œuvre du scoring dans Tanagra à l’aide de l’analyse discriminante. Les données proviennent d’une compétition qui a été organisée en 2000 (CoIL Challenge 2000) : il s’agissait de repérer parmi les clients d’une compagnie d’assurance, ceux qui vont prendre une police d’assurance pour leur caravane.

Les résultats du concours ont montré que les méthodes avec un biais de représentation linéaire (type analyse discriminante, régression logistique ou modèle d’indépendance conditionnelle [Naive Bayes]) se comportent très bien dans le scoring. C’est par ailleurs ce que constatent tous les jours les chargés d’études qui travaillent dans le domaine. Les méthodes plus complexes sont rarement meilleures. De plus, elles pâtissent d’un défaut rédhibitoire, il est difficile de discerner le rôle des variables dans la détection des positifs.

Enfin, par rapport au descriptif proposé dans le didacticiel, Tanagra (version 1.4.21 et +) affiche directement maintenant la courbe lift dans un onglet supplémentaire de la fenêtre d'affichage.

Mots clés : scoring, ciblage marketing, analyse discriminante, courbe lift, gain chart
Composants : Supervised learning, Linear discriminant analysis, Select examples, Scoring, Lift curve
Lien : fr_Tanagra_Scoring.pdf
Données : tcidata.zip
Référence : R. Rakotomalala – « Ciblage marketing – Construire la courbe Lift »

Déploiement de modèles avec Tanagra

Le déploiement des modèles est une activité clé du Data Mining. Dans le cas de l’apprentissage supervisé, il s’agit de classer de nouveaux individus à partir des valeurs connues des variables prédictives introduites dans le modèle. Dans le cas de l’analyse factorielle, il s’agit de fournir les coordonnées factorielles d’un individu à partir de la description dans l’espace initial. Dans le cas de la classification automatique (clustering), il s’agit de définir le groupe d’appartenance d’un individu supplémentaire, etc.

Sipina s’appuie sur un dispositif relativement simple pour cette tâche. On peut appliquer un arbre de décision sur un nouveau fichier. Comme les données ne subissent pas de transformations intermédiaires avant l’apprentissage supervisé, la correspondance entre les variables du fichier de données servant à élaborer le modèle et les variables disponibles pour le déploiement est relativement aisée.

Dans le cas de Tanagra, la situation est autrement plus complexe pour deux raisons : c’est un logiciel généraliste, intégrant des techniques de nature différentes ; le concept de la chaîne de traitements implique une succession de transformations. Prenons un exemple d’apprentissage supervisé pour fixer les idées. Les descripteurs sont initialement composés de variables quantitatives et qualitatives. Nous discrétisons tout d’abord les variables quantitatives. Puis, nous intégrons les variables discrétisées et les variables déjà qualitatives dans une analyse en composantes multiples. Les axes factoriels deviennent alors les entrées de l’analyse discriminante.

Lorsque nous voulons déployer le modèle sur un nouveau fichier de données, seules les variables originelles sont décrites. Il nous faudrait donc reproduire la séquence des opérations en effectuant le déploiement à partir de tous les opérateurs intermédiaires c.-à-d. appliquer la discrétisation sur les variables quantitatives en utilisant les paramètres calculés en apprentissage, calculer les coordonnées factorielles, effectuer la prédiction de l’analyse discriminante enfin. Cela peut être très rapidement inextricable...

Tanagra réalise bien toutes ces opérations lors du déploiement d’une chaîne de traitements complexe. Mais pour éviter de tomber dans un dispositif qui ressemblerait rapidement à une usine à gaz, le fichier doit être préparé d’une manière particulière, afin que les opérations intermédiaires soient correctement réalisées.

Ce didacticiel montre comment doit être organisé le fichier de données pour que le déploiement soit réalisé efficacement. Nous illustrons notre propos avec un exemple assez simple. Mais la démarche peut être généralisée à des chaînes de traitements complexes.

Mots clés : déploiement de modèles, arbres de décision, CART, exportation des données
Composants : Supervised learning, C-RT, Select examples, View dataset, Export dataset
Lien : fr_Tanagra_Deployment.pdf
Données : tanagra_deployment_files.zip

Sélection de variables – Bayesien naïf

La sélection de variables est une étape primordiale du Data Mining. Dans le cadre de l’apprentissage supervisé, parmi les objectifs de la fouille de données figure, en très bonne place, la recherche des causalités entre les variables prédictives et la variable à prédire. Plus le nombre de variables retenu est faible, meilleure sera la lisibilité du modèle prédictif. De plus, il est avéré qu’un modèle simple sera plus robuste lorsqu’il sera déployé dans la population.

Ce didacticiel décrit la mise en œuvre du composant MIFS (Battiti, 1994) dans l’apprentissage du modèle d’indépendance conditionnelle (Bayesien Naïf). Il est intéressant à double titre car cette phase de sélection est précédée d’un recodage où les descripteurs continus sont préalablement discrétisées avec la méthode MDLPC.

L’efficacité de la sélection est évaluée en comparant les performances en validation croisée du modèle avec et sans sélection de variables. Nous traitons le fameux fichier des IRIS de Fisher (1936).

Mots clés : sélection de variables, discrétisation, modèle d’indépendance conditionnelle
Composants : Supervised learning, Naive Bayes, MDLPC, MIFS filtering, Cross validation
Lien : Feature_Selection_For_Naive_Bayes.pdf
Données : iris.bdm
Référence : R. Battiti, « Using the mutual information for selecting in supervised neural net learning », IEEE Transactions on Neural Networks, 5, pp.537-550, 1994.

Traitement des grands fichiers

Une des principales nouveautés de ces dernières années est l’évolution quasi-exponentielle du volume des fichiers que nous sommes emmenés à traiter. Il y a une dizaine d’années encore, un tableau de 5000 observations avec 22 variables, les fameuses « ondes de Breiman », faisait figure de « gros fichier » au sein de la communauté de l’apprentissage automatique. Aujourd’hui, les tailles de fichiers connaissent une inflation galopante avec une augmentation importante du nombre d’observations (les bases marketing) et/ou du nombre de descripteurs (en bio-informatique, en réalité tous les domaines où les descripteurs sont générés automatiquement).

La capacité à traiter les gros ensembles de données est un critère important de différenciation entre les logiciels de recherche et les logiciels commerciaux. Très souvent les outils commerciaux disposent de systèmes de gestion de données très performants, limitant la quantité de données chargée en mémoire à chaque étape du traitement. Les outils de recherche en revanche conservent toutes les données en mémoire, en les codant au mieux de manière à ce que l’occupation de la RAM ne soit pas prohibitive. Dès lors, les limites du logiciel sont déterminées par les capacités de la machine utilisée.

TANAGRA se situe précisément dans la seconde catégorie. Il charge toutes les données en mémoire, sous une forme encodée. Il est intéressant d’analyser les temps de traitements sur un fichier de taille (relativement) respectable. Nous décrivons cela dans ce didacticiel en mettant en exergue l’importation des données et l’induction d’un arbre de décision avec la méthode ID3.

Mots clés : temps de traitement, capacité de traitement, grandes bases de données, arbres de décision
Composants : Supervised learning, ID3
Lien : fr_Tanagra_Big_Dataset.pdf
Données : covtype.zip

Sauver et charger des parties du diagramme

Bien souvent, nous utilisons les mêmes séquences de traitements lorsque nous traitons, avec des objectifs identiques, des bases de données présentant des caractéristiques similaires.

Prenons le cas de l’apprentissage supervisé, il s’agit de définir la variable à prédire et les variables prédictives, mettre en place la méthode d’apprentissage, et valider la chaîne à l’aide d’une technique de ré échantillonnage. L’analyse peut être complétée par une étape de sélection de variables. Il s’agit bien là d’une démarche type qui peut être transposée dans tout problème d’apprentissage supervisé. Il serait intéressant de pouvoir créer, une fois pour toutes, ce « super composant » constitué d’un enchaînement standardisé. L’objectif est de pouvoir le reproduire facilement lors de l’exploration d’autres fichiers.

Il est possible de sauvegarder dans un fichier externe une fraction du diagramme dans TANAGRA. On pourra le charger dans un autre contexte pour définir les mêmes traitements types. On peut le voir comme un module de programme partageable. Il faut bien entendu que les configurations soient compatibles.

Dans ce didacticiel, nous traitons un problème de prédiction où tous les descripteurs sont discrets. Nous utilisons le modèle d’indépendance conditionnelle. Nous voulons comparer les performances du classifieur, avec et sans FCBF (Yu et Liu, 2003), une méthode de sélection de variables. Les manipulations sont décomposées en 3 phases : (1) création du diagramme type sur un des fichiers de données ; (2) sauvegarde de la fraction du diagramme que l’on veut partager ; (3) importation de la fraction dans un autre diagramme, traitant un autre fichier de données.

Cette fonctionnalité peut être vue comme une généralisation du copier coller. A la différence que nous pouvons travailler sur plusieurs diagrammes différents. Elle ouvre des perspectives intéressantes. On pourrait demander à des experts de définir des séquences de traitements types qui seront distribuées aux utilisateurs.

Mots clés : sauvegarde du diagramme, copier coller, comparaison de classifieurs, apprentissage supervisé, validation croisée, modèle d’indépendance conditionnelle, sélection de variables, FCBF
Composants : Supervised learning, Naive Bayes, Cross validation
Lien : fr_Tanagra_Diagram_Save_Subdiagram.pdf
Données : congressvote_zoo.zip
Voir aussi : Copier coller dans le diagramme

Copier coller dans le diagramme

A mesure que les calculs deviennent complexes, la taille d’un diagramme enfle rapidement, d’autant plus que certaines séquences d’opérations sont répétitives. Il est important dans ce contexte de disposer d’outils simples pour dupliquer des branches entières du diagramme, un copier coller de composants en quelque sorte.

Dans ce didacticiel, nous voulons comparer 5 méthodes d’apprentissage en validation croisée sur un fichier de données. La construction et le paramétrage de la première branche du diagramme sont réalisés manuellement. Par la suite, pour chaque méthode, les séquences d’opérations sont les mêmes. Pouvoir dupliquer la chaîne de composants simplement est un avantage appréciable.

Dans une deuxième étape, nous avons voulu introduire une construction de variables adéquate pour bonifier l’apprentissage. Nous effectuons une analyse en composantes principales sur les descripteurs. L’apprentissage supervisé est ensuite réalisé sur les axes factoriels les plus significatifs. L’idée est de « lisser » les données de manière à ne conserver que l’information utile pour la modélisation. Dans le contexte de ce fichier, avec un rapport nombre de variables – nombre d’individus élevés, cette préparation est vraisemblablement avantageuse. Nous voulons justement le vérifier en répétant les comparaisons ci-dessus. Dans ce cas, c’est toute une branche du diagramme qu’il faut dupliquer, il est évident que le copier coller est indispensable, ré-insérer manuellement la série de composants est non seulement fastidieuse mais expose le praticien à de multiples erreurs de manipulations.

Mots clés : copier coller, comparaison de classifieurs, apprentissage supervisé, validation croisée, régression logistique, régression pls, svm, analyse discriminante linéaire, k-nn, analyse en composantes principales, régularisation
Composants : Supervised learning, Binary logistic regression, C-PLS, C-SVC, Linear discriminant analysis, K-NN, Principal Component Analysis
Lien : fr_Tanagra_Diagram_New_Features.pdf
Données : sonar.xls
Voir aussi : Comparaison de classifieurs

Importer un fichier Weka dans Tanagra

WEKA est un logiciel de Data Mining libre très populaire dans la communauté « Machine Learning ». Il possède un format de fichier propriétaire (*.ARFF), qui est un format texte, avec des spécifications ad hoc pour documenter les variables. Importer un fichier ARFF ne pose donc pas de problèmes particuliers, dès lors que l’on sait appréhender un fichier texte.

Dans ce didacticiel, nous montrons comment charger un fichier ARFF dans TANAGRA. Lorsque le fichier comporte des données manquantes, une substitution très sommaire est mise en place : la moyenne est utilisée pour les variables continues, une nouvelle modalité est créée pour les variables discrètes.

Les traitements peuvent commencer normalement, un diagramme est automatiquement créé. Si nous décidons de le sauvegarder au format TDM, la référence du fichier est enregistrée. Au prochain chargement du diagramme, l’importation du fichier ARFF est réalisée automatiquement sans manipulations spécifiques.

Mots clés : WEKA, format de fichier ARFF, importation de données
Composants : Dataset
Lien : fr_Tanagra_Handle_WEKA_File.pdf
Données : sick.arff
Voir aussi : Importer un fichier Weka dans Sipina

Codage disjonctif complet

Ce didacticiel est le pendant de celui traitant de la discrétisation des variables continues. Il s’agit de transformer une variable catégorielle (qualitative) en variables numériques (indicatrices).

Lorsque les variables prédictives (variables indépendantes, exogènes, etc.) sont catégorielles, les méthodes d’apprentissage supervisé telles que la régression logistique et l’analyse discriminante ne peuvent pas être mises en oeuvre directement. Il est nécessaire de recoder les variables.

La technique la plus connue est certainement le codage disjonctif complet ou codage 0/1. Chaque modalité de la variable originelle devient une variable binaire qui prend la valeur 1 lorsque la modalité est présente pour un individu, 0 sinon. Puisque la somme de ces nouvelles variables est systématiquement égal à 1, il est d’usage d’omettre la dernière modalité qui peut être déduite des autres c.-à-d. si toutes les variables binaires prennent la valeur 0, on en déduit que l’individu porte la dernière valeur, elle devient la modalité de référence.

Attention, si la variable à recoder est ordinale, ce dispositif peut être utilisé toujours, mais dans ce cas nous perdons de l’information : la méthode d’apprentissage ne tient plus compte du caractère ordinal des modalités. Un codage 0/1 emboîté est plus indiqué si l’on veut la préserver.

Dans ce didacticiel, nous montrons comment utiliser le composant 0_1_ BINARIZE pour transformer une variable catégorielle en une série de variables binaires que nous introduisons dans une régression logistique.

Autre particularité de ce document, nous montrons comment, directement dans TANAGRA, subdiviser de manière aléatoire l’ensemble de données en 2 fractions : la première, l’échantillon d’apprentissage, sert à la construction du modèle ; la seconde, l’échantillon test, sert à son évaluation.

Mots clés : codage disjonctif complet, codage binaire 0/1, régression logistique, échantillon d’apprentissage, échantillon test
Composants : Sampling, 0_1_Binarize, Supervised Learning, Binary Logistic Regression, Test
Lien : fr_Tanagra_Dummy_Coding_for_Logistic_Regression.pdf
Données : categorical_heart.xls

mercredi 19 mars 2008

Discrétisation contextuelle – La méthode MDLPC

La préparation des variables est une étape clé du Data Mining. De la qualité du travail réalisé durant cette phase dépend le succès de la modélisation entreprise par la suite.

La construction de variables nous sert avant tout à mettre en évidence les informations pertinentes dans les données. Mais dans certaines situations, le recodage est une nécessité. Lorsque, par exemple, la technique de fouille subséquente ne sait pas appréhender tel ou tel type de données, nous devons modifier la nature de la variable, en la passant d’un type quantitatif vers un type qualitatif, ou inversement, l’important étant de produire un codage efficace où les pertes d’informations, voire les injections de nouvelles informations, parfois intempestives, sont contrôlées.

Prenons l’exemple du modèle d’indépendance conditionnelle, le modèle bayesien naïf (Naive Bayes en anglais). La méthode s’applique naturellement pour des descripteurs discrets. Il en est autrement lors qu’ils sont continus. On pourrait la mettre en œuvre quand même, mais aux prix d’hypothèses sur les distributions conditionnelles, loi normale le plus souvent, qui peuvent s’avérer inappropriées. Un angle d’attaque simple serait plutôt de découper en intervalles les descripteurs continus. Ce type de recodage s’appelle discrétisation. Il existe un grand nombre de techniques. Dans notre cas, le découpage doit s’effectuer au regard du problème de prédiction que nous voulons résoudre, on parle de discrétisation contextuelle : on veut définir le nombre d’intervalles et les bornes de découpage de manière à ce que les individus situés dans un même intervalle portent majoritairement la même étiquette de la variable à prédire.

La méthode MDLPC de Fayyad et Irani (1993) est disponible dans TANAGRA. Elle est contextuelle, détermine automatiquement le nombre d’intervalles, fournit les bornes de découpages. Il y en a d’autres bien sûr, mais l’expérience montre que la notoriété de MDLPC n’est pas usurpée, elle est robuste et donne satisfaction dans la plupart des cas.

Dans ce didacticiel, nous montrons (1) comment intégrer dans le composant MDLPC dans le diagramme de traitements ; puis (2) comment exploiter les variables discrétisées ainsi produites dans les composants d’apprentissage supervisé qui lui succèdent. L’efficacité de la chaîne complète de traitements (discrétisation + apprentissage supervisé) est évaluée à l’aide d’une méthode de ré échantillonnage, la validation croisée.

Mots clés : discrétisation contextuelle, mdlpc, modèle d’indépendance conditionnelle, bayesien naïf, validation croisée
Composants : MDLPC, Supervised Learning, Naive bayes, Cross-validation
Lien : SupervisedDiscretisation.pdf
Données : breast.bdm
Références :
U. Fayyad et K. Irani, « Multi-interval discretization of continuous-valued attributes for classification learning », in Proc. of IJCAI, pp.1022-1027, 1993.
R. Rakotomalala, « Graphes d’Induction », Thèse de Doctorat Lyon 1, 1997 ; chapitre 9, pp.209-244.

Connexion Open Office Calc

De la même manière qu’il est possible de transférer directement des données d’EXCEL vers TANAGRA via une macro complémentaire (voir Connexion Excel – Tanagra), nous avons mis au point un add-on (ou add-in) pour le tableur Calc d’Open Office (Open Office Calc).

La procédure est la même. Lors de l’installation de TANAGRA, l’add-in est automatiquement installé sur le disque dur. Il nous reste à la brancher dans Open Office Calc en suivant une procédure précise.

L’add-in est disponible depuis la version 1.4.12 de TANAGRA. Le développement et les tests ont été réalisés avec la version 2.1.0 (française) d’Open Office.

Ce didacticiel décrit la démarche à suivre pour installer correctement l’add-in dans Open Office Calc. Deux documents sont disponibles : (1) un pdf classique déroulant les étapes avec des copies d’écran ; (2) une démonstration animée au format flash (en anglais mais les menus sont tous en français).

Mots clés : importation des données, tableur, open office calc, add-in, add-on, création d’un diagramme de traitement
Composants : View Dataset
Lien pdf : fr_Tanagra_OOoCalc_Addon.pdf
Lien démo animée : from_OOoCalc_To_Tanagra.htm
Données : breast.ods

Importer un fichier Weka dans Sipina

WEKA est un logiciel de Data Mining libre très populaire dans la communauté « Machine Learning ». Il intègre un grand nombre de méthodes, articulées essentiellement autour des approches supervisées et non supervisées.

WEKA possède un format de fichier propriétaire (*.ARFF), qui est un format texte, avec des spécifications ad hoc pour documenter les variables. Importer un fichier ARFF ne pose donc pas de problèmes particuliers, dès lors que l’on sait appréhender un fichier texte.

Dans ce didacticiel, nous montrons comment charger un fichier ARFF dans SIPINA. L’importation est directe, il s’agit simplement de connaître la bonne procédure. Nous profitons de cet exemple pour montrer comment subdiviser aléatoirement un ensemble de données pour : construire l’arbre sur l’échantillon d’apprentissage, l’évaluer sur l’échantillon test. Nous utilisons la méthode C4.5 (Quinlan, 1993).

Mots clés : WEKA, format de fichier ARFF, arbres de décision, C4.5, subdivision apprentissage et test, évaluation des classifieurs
Lien : fr_sipina_weka_file_format.pdf
Données : ionosphere.arff

anti_bug_fck

mardi 18 mars 2008

Description de l’interface SIPINA

Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.

Mots-clés : interface SIPINA, arbres de décision
Lien : french_introduction_sipina_research.pdf

lundi 17 mars 2008

Déploiement d'un arbre de décision avec SIPINA

Déploiement de modèles. Le déploiement des modèles est une activité clé du Data Mining. Dans le cas de l’apprentissage supervisé, il s’agit de classer de nouveaux individus à partir des valeurs connues des variables prédictives introduites dans le modèle. SIPINA peut directement appliquer un arbre de décision sur un nouveau fichier non étiqueté. Petite contrainte néanmoins, le processus de déploiement doit être consécutif à l’apprentissage. Il n’est pas possible de distribuer un modèle pour l’appliquer sur de nouveaux individus en dehors de l’environnement SIPINA.

Evaluation des performances. Prédire sur des nouveaux individus, c’est bien. Mais il faut pouvoir annoncer à l’avance les performances à venir. En effet, une affectation erronée produit des conséquences négatives (ex. diagnostiquer l’absence d’une maladie chez une personne souffrante fera qu’elle ne sera pas soignée). Pouvoir évaluer la fiabilité d’un modèle prédictif est primordiale pour la décision de sa mise en production (ou non). Nous utiliserons la méthode bootstrap dans ce didacticiel. Le but est de fournir une mesure crédible de la performance de l’arbre construit sur la totalité des données disponibles.

Ce tutoriel montre comment, avec SIPINA, construire un arbre de décision, l’appliquer sur un fichier de données non étiqueté. Par la suite, les performances en prédiction sont estimées par bootstrap. Le même schéma sera appliqué dans un second temps en utilisant l’analyse discriminante.

Mots clés :
déploiement de modèles, arbres de décision, évaluation des classifieurs, bootstrap, méthodes de ré échantillonnage, analyse discriminante
Lien :
fr_sipina_deployment.pdf
Données :
wine_deployment.xls


dimanche 9 mars 2008

Comparaison de classifieurs

Pour évaluer un algorithme d'apprentissage supervisé, on conseille souvent de subdiviser les données en deux sous-ensembles disjoints : l'ensemble d'apprentissage (learning set) qui sert à élaborer le modèle de prédiction ; l'ensemble test (test set) qui sert à en mesurer les performances. TANAGRA dispose d'outils permettant de construire automatiquement ces sous-ensembles à partir d'un échantillonnage. Mais, dans certains cas, l'utilisateur peut vouloir procéder lui-même à cette subdivision afin d'utiliser les mêmes ensembles d'apprentissage et de test pour comparer les algorithmes d'apprentissage.

Dans ce didacticiel, nous utiliserons un fichier de données dans lequel nous avons introduit une colonne supplémentaire permettant de désigner les individus à utiliser pour l'apprentissage et ceux à utiliser lors de l'évaluation. Nous montrerons alors quels composants utiliser pour désigner les observations qui vont servir à construire les modèles de prédiction, nous utiliserons un autre composant pour comparer leurs performances sur l'ensemble test.

Mots clés : apprentissage supervisé, comparaison de classifieurs, schéma apprentissage test, taux d'erreur, matrice de confusion, analyse discriminante linéaire, support vector machine, algorithme des plus proches voisins
Composants : Select examples, Supervised learning, Linear discriminant analysis, SVM, K-NN
Lien : fr_Tanagra_Compare_Algorithms_On_Predefined_Test_Set.pdf
Données : sonar_with_test_set.xls
Références :
R. Rakotomalala, " Apprentissage supervisé "
R. Rakotomalala, " Estimation de l'erreur de prédiction - Les techniques de ré échantillonnage "

Classification automatique - Algorithme EM

Les modèles de mélanges traduisent une fonction de densité régissant la distribution de données à l'aide d'une combinaison linéaire de fonctions de densité élémentaires. L'approche la plus connue est le modèle de mélange gaussien où les densités élémentaires sont des lois normales multidimensionnelles.

Cette technique peut être utilisée pour décrire la distribution des données en classification automatique. Chaque classe (groupe, cluster, etc.) est décrite par une loi de distribution normale, paramétrée par son centre de gravité et sa matrice de variance covariance. Pour estimer les paramètres des distributions élémentaires, l'algorithme EM (Expectation-Maximization) est certainement le plus connu. L'objectif est de maximiser la logvraisemblance de l'échantillon de données compte tenu d'un nombre de cluster défini au préalable.

Dans ce didacticiel, nous montrons l'intérêt de cette approche sur des données artificielles. Malgré la difficulté du problème proposé, l'algorithme EM trouve parfaitement la solution adéquate. Nous donnons des indications également pour détecter au mieux, de manière raisonnée en tous les cas, le bon nombre de groupes, un problème récurrent de la classification automatique.

Malgré sa puissance, cette technique est peu diffusée, peu utilisée, peu enseignée, peut être parce qu'elle est rarement implémentée dans les logiciels de Data Mining.

Mots clés : classification automatique, algorithme EM, modèle de mélange gaussien, maximisation de la vraisemblance, choix du nombre de classes
Composants : EM-Clustering, K-Means, EM-Selection, scatterplot
Lien : fr_Tanagra_EM_Clustering.pdf
Données : two_gaussians.xls
Références :
Wikipédia (fr) -- Algorithme espérance-maximisation
Wikipédia (en) -- Expectation-maximization algorithm

La complémentarité CAH et ACP

L'appréhension d'un problème de fouille de données est rarement monolithique. Certes, nous identifions rapidement si nous devons mettre en œuvre des techniques descriptives, des techniques de classification ou des techniques de prédiction pour répondre au cahier de charges d'une étude. Il n'en reste pas moins que dans la grande majorité des cas, nous devons faire coopérer ces approches pour obtenir des résultats performants et interprétables.

Dans ce didacticiel, nous cherchons à regrouper des véhicules à partir de leurs caractéristiques (poids, consommation, etc.). La combinaison d'une technique de visualisation, l'analyse en composantes principale, avec une technique de typologie, la classification ascendante hiérarchique, amplifie la portée des résultats. Il faut dire que l'exemple s'y prête bien. L'interprétation des groupes produits par la classification automatique est un problème crucial, souvent malaisé. Bénéficier des lumières d'une technique de visualisation nous permet de mieux délimiter ce que nous produisons.

L'exemple nous montre qu'il faut se méfier des résultats automatisés, basés uniquement par des procédures numériques. L'interprétation des résultats, l'expertise que nous pouvons apporter par ailleurs, nous permet de guider les résultats vers des solutions plus en harmonie avec les connaissances du domaine.

Mots clés : CAH, classification automatique, ACP, analyse factorielle, techniques de visualisation
Composants : HAC, Group characterization, Principal component analysis, correlation scatterplot, scatterplot
Lien : fr_Tanagra_hac_pca.pdf
Données : cars.xls
Références :
M. Gettler-Summa, C. Pardoux, " La classification automatique " -- Classification.pdf
A. Baccini, P. Besse, " Data Mining I - Exploration Statistique " -- Explo_stat.pdf

Analyse discriminante descriptive - Vins de Bordeaux

L'analyse discriminante est une technique statistique qui cherche à décrire, expliquer et prédire l'appartenance à des groupes prédéfinis (classes, modalités de la variable à prédire, ...) d'un ensemble d'observations (individus, exemples, ...) à partir d'une série de variables prédictives (descripteurs, variables exogènes, ...).

On distingue généralement deux approches, qui peuvent se rejoindre : l'analyse discriminante descriptive, que nous étudions dans ce didacticiel, et l'analyse discriminante prédictive que nous étudierons dans d'autres circonstances.

L'analyse factorielle discriminante, ou analyse discriminante descriptive, vise à produire un nouveau système de représentation, des variables latentes formées à partir de combinaisons linéaires des variables prédictives, qui permettent de discerner le plus possible les groupes d'individus. En ce sens, elle se rapproche de l'analyse factorielle car elle permet de proposer une représentation graphique dans un espace réduit, plus particulièrement de l'analyse en composantes principales calculée sur les centres de gravité conditionnels des nuages de points avec une métrique particulière. On parle également d'analyse canonique discriminante, notamment dans les logiciels anglo-saxons.

Ce didacticiel, nous cherchons à décrire la qualité des vins du beaujolais à partir de variables météorologiques. TANAGRA indique à la sortie les axes factoriels significatifs, les corrélations totales, intra et inter groupes, qui permettent de les interpréter. Cet exemple est tiré de l'ouvrage de M. Tenenhaus (1996).

Mots clés : analyse factorielle discriminante, analyse discriminante descriptive
Composants : Canonical discriminant analysis, Scatterplot
Lien : fr_Tanagra_Canonical_Discriminant_Analysis.pdf
Données : wine_quality.xls
Références :
M. Tenenhaus, " Méthodes statistiques en gestion ", Dunod, 1996 ; page 244.
Wikipédia -- Analyse discriminante

Sélection forward - Crime dataset

La sélection de variables est une opération primordiale dans la régression linéaire multiple. Il s'agit tout d'abord d'écarter les variables non pertinentes dans le processus d'explication de la variable endogène. Mais il s'agit également de traiter le cas des variables redondantes, emmenant le même type d'information, fortement corrélées au point d'empêcher le calcul correct des coefficients et de leurs caractéristiques (écart type notamment). C'est le problème de la colinéarité des exogènes.

Ce didacticiel montre la mise en œuvre d'une technique simple de sélection de variables. La sélection est séquentielle, en ajoutant au fur et à mesure une explication additionnelle significative au regard des variables déjà introduites : on parle de sélection forward. Ce processus peut s'interpréter de différentes manières. Une lecture en termes de corrélation partielle est peut être la plus séduisante : à chaque étape on cherche la variable exogène la plus corrélée avec l'endogène après soustraction de l'information emmenée par les variables sélectionnées à l'étape précédente.

Dans ce didacticiel, nous voulons expliquer la criminalité dans 47 états des USA en 1960 à partir des indicateurs socio-économiques (taux de chômage, revenu moyen, etc.).

Mots clés : régression linéaire multiple, économétrie, sélection de variables, sélection forward, stepwise, colinéarité, corrélation partielle
Composants : View Dataset, Multiple linear regression,
Lien : fr_Tanagra_Forward_Selection_Regression.pdf
Données : crime_dataset_from_DASL.xls
Références :
Cours économétrie L3 IDS Lyon 2-- Cours Econométrie
Pratique de la régression -- La régression dans la_pratique

Régression - Expliquer la consommation des véhicules

La régression linéaire multiple est une technique statistique qui vise à modéliser la relation entre une variable dépendante quantitative (endogène) avec une ou plusieurs variables indépendantes quantitatives (exogènes, elles peuvent être qualitatives mais doivent être recodées). C'est une technique très populaire. Son domaine d'application est très large. Une des applications privilégiées est la modélisation des phénomènes économiques. Elle rentre dans un cadre plus large qu'est l'économétrie dans ce cas.

La régression peut être à vocation prédictive, c.-à-d. à partir de la connaissance des valeurs prises par les exogènes, on essaie de prédire les valeurs prises par l'endogène. Elle peut être à vocation explicative c.-à-d. essayer de délimiter le rôle des variables exogènes dans l'explication de l'endogène. Dans tous les cas, l'étude et l'interprétation des résultats tiennent une place prépondérante dans l'analyse.

Dans ce didacticiel, nous voulons expliquer la consommation des véhicules automobiles à partir de leurs caractéristiques (poids, puissance, etc.).

Mots clés : régression linéaire multiple, économétrie, variable endogène, variables exogènes
Composants : View Dataset, Multiple linear regression
Lien : Regression.pdf
Données : autompg.bdm
Références :
Wikipédia -- Régression linéaire multiple
Cours économétrie L3 IDS Lyon 2-- Cours Econométrie

CAH Mixte - Le fichier Iris de Fisher

La CAH (classification ascendante hiérarchique) est une technique de classification automatique. Elle vise à produire un regroupement des individus de manière à ce que les individus dans un même groupes soient similaires, les individus dans des groupes différents soient dissemblables.

La CAH a de particulier qu'elle propose une série de partitionnement emboîtés, avec une représentation graphique, le dendrogramme, qui donne des indications sur les solutions alternatives à évaluer. La détermination du bon nombre de groupes est un problème récurent en typologie, le nombre de solutions à étudier est ainsi réduit.

La CAH pose problème dès que la taille de la base augmente. L'obligation de calculer les distances entre les individus deux à deux est très vite rédhibitoire. Dans un contexte où les bases contiennent plusieurs milliers d'individus, il est inepte de vouloir construire le dendrogramme en partant directement des observations. Même si le calcul était possible, la lecture des parties basses de l'arbre est impossible, et de toute manière inutile.

LA CAH - MIXTE permet de dépasser élégamment cet écueil en effectuant un pré regroupement des individus, assez fruste, avec une méthode de réallocation par exemple, de manière à ce que ce premier partitionnement soit le point de départ de la création du dendrogramme.

Le premier regroupement en un nombre assez important de classes (une vingtaine) a peu d'intérêt en tant que tel. Sa lecture et son interprétation n'ont pas de sens. En revanche, elle permet de réduire considérablement les calculs lorsque l'on met en œuvre par la suite une construction de l'arbre selon la méthode de Ward. Il n'est pas nécessaire de recalculer les distances entre les couples d'individus, le calcul de proche en proche des centres de gravité des groupes suffit.

Ce didacticiel décrit le traitement du fameux fichier IRIS (Fisher, 1936). On cherche à produire un regroupement en 3 classes des iris à partir de leur morphologie. On confrontera par la suite les classes obtenues avec l'espèce, connue, de la fleur. On parle dans ce cas de validation externe. On connaît une classe d'appartenance a priori. On regarde si les classes produites " en aveugle ", sur la base uniquement des descripteurs, sont concordantes.

Mots clés : classification, typologie, CAH, nuées dynamiques, K-Means, validation externe
Composants : HAC , K-Means, Group characterization
Lien : HAC_IRIS.pdf
Données : iris_hac.bdm
Référence : L. Lebart, A. Morineau, M. Piron, " Statistique exploratoire multidimensionnelle ", Dunod, 2000 ; pages 177 à 184.

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)