Institut de la Francophonie pour l’Informatique INRIA-LORIA, FRANCE IFI Hanoi Combinaison de méthodes avancées de visualisation et de sélection d’information pour la fouille et l’analyse de données Mémoire de fin d’études présentée et soutenue publiquement le 06 Décembre 2007 pour l’obtention du Master de l’Institut de la Francophonie pour l’Informatique – IFI-Hanoi (spécialité informatique) par Anh-Phuong TA Sous la direction de : Jean-Charles LAMIREL Maı̂tre de Conférence, Université Robert Schuman, Strasbourg Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé La combinaison de méthodes avancées de visualisation et d’étiquetage des clusters joue un rôle important non seulement pour donner un avis global des résultats du clustering, mais aussi pour l’évaluation précise desdits résultats. Mais aujourd’hui encore, aucune solution précise sur la façon de combiner de telles méthodes n’a été proposée. Dans ce rapport, nous présentons une première tentative de combinaison de la visualisation hyperbolique ainsi que de nouvelles approches d’étiquetage afin de visualiser précisément les résultats d’analyses de données issues de méthodes de clustering toutes les fois que les clusters sont à l’origine représentés dans un espace fortement multidimensionnel. Le modèle de visualisation se fonde sur un algorithme hiérarchique qui est employé pour récapituler le contenu de clusters sous forme hiérarchique.
Cet algorithme préserve la densité de données issue de l’espace de description des clusters ori- ginaux. Dans ce mémoire sont présentées différentes stratégies d’étiquetage qui peuvent être employées aussi bien pour décrire le contenu de base des clusters que pour propager précisé- ment les étiquettes dans les différents niveaux de l’hyperbolique résultant. Ce travail s’attache ensuite à améliorer les défauts des méthodes de visualisation hyperbolique en embarquant le modèle de Spring à l’hyperbolique afin de mieux montrer les relations entre les clusters. Plu- sieurs expérimentations sont proposées sur différents types de données documentaires.
Mots-clés : analyse de données multi-vues, fouille de données, clustering numérique, évalua- tion de qualité du clustering, étiquetage des clusters, visualisation hyperbolique, visualisation hiérarchique. Abstract Combining the visualization and the labeling methods plays an important role not only for giving an overall view of the clustering results but also for the precise evaluation of the said results. But at this point, no accurate solution on how to combine such methods has been pro- posed. In this report we present a first attempt of combination of hyperbolic visualization and novel labeling approaches for accurately visualizing data analysis results issued for clustering approach whenever the clusters are originally represented in a highly multidimensional space.
The visualization model relies on a hierarchical algorithm that is used for summarizing the cluster contents in the form on a hypertree in which information on data density issued from the original clusters description space is preserved. The core of this work presents different novel labeling strategies that can be used for describing the basic cluster contents as well as for accurately propagating labels into the different levels of the resulting hypertree. This work then aims to improve the defects of hypertree visualization by embedding the model of Spring to hyperbolic for better showing the relations between the clusters. Several realistic test expe- riments of our proposals are achieved on different kinds of documentary data.
Keywords : multiview data analysis, data mining, clustering, cluster labeling, clustering qua- lity evaluation, hyperbolic visualization, hierarchical visualization. i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Mes premiers remerciements vont à mon encadrant Jean-Charles Lamirel pour le temps qu’il m’a consacré durant ce stage, son soutien, ses conseils scientifiques, sa disponibilité et son aide précieuse pour améliorer et aller jusqu’au bout de ce travail de stage. Il m’a vraiement impressionné de par ses qualités humaines et son esprit ouvert. Je tiens à remercier tous les membre de l’équipe CORTEX : Randa, Maxime, Jéremy pour leur soutien et leur accueil et les membres de l’équipe KIWI, Geoffray, Ilham.
Je tiens à remercier Pascal Cuxac et Claire François de l’INIST pour leurs évaluations. Je tiens à remercier Mohammed Attik, un ancien doctorant de l’équipe Cortex pour sa coopération, sa conversation et son soutien. Je tiens à remercier mes Professeurs de l’IFI, qui m’ont donné des connaissances et m’ont aidé à bien suivre la formation de master de l’IFI. Mes grands remerciement à ma grande famille, en particulier ma femme et mon fils, pour leur encouragement, leurs prières pour réussir ma vie professionnelle.
iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Liste des figures ix Liste des tableaux xi Liste des algorithmes xiii Chapitre 1 Introduction générale 1.2 Contexte et Problématique .4 Plan du mémoire. 3 Chapitre 2 L’état de l’art 2.1 Dimension intrinsèque des données multidimensionnelles .2 Visualisation par projection cartographique linéaire .3 Visualisation par projection cartographique non linéaire .4 Visualisation par l’analyse de graphe .2 Étiquetage des clusters .2 Étiquetage des clusters par la sélection d’information (variable) .3 Traitement de données documentaires multidimensionnels .1 Représentation de données documentaires. 20 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières 2.2 Notion de point de vue. 25 Chapitre 3 Combinaison de méthodes avancées de visualisation et de sélection d’in- formation pour la fouille et l’analyse de données 3.2 Nouvelles mesures de qualité du clustering basées sur la distribution d’éti- quettes .3 Nouvelles stratégies d’étiquetage des clusters .1 Stratégie locale d’étiquetage des clusters .2 Stratégie globale d’étiquetage des clusters .3 Stratégie hybride d’étiquetage des clusters .4 Stratégie d’étiquetage des clusters par les mesures d’entropie .5 Étiquetage des clusters par Gain d’Information .4 Combinaison des méthodes d’étiquetage des clusters et de visualisation hyperbolique .5 Communication multi-vues entre les arbres hyperboliques .1 Modèle de réseau bayésien pour la communication inter-cartes .2 Communication multi-vues entre les arbres hyperboliques .6 Intégration de graphe à l’hyperbolique .7 Organisation des branches de l’hyperbolique.
41 Chapitre 4 Expérimentations et évaluations 4.1 Interprétation des résultats du clustering .2 Communication multi-vues entre les arbres hyperboliques .3 Intégration de modèle de Spring à l’hyperbolique. 46 Conclusion générale vi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Annexe A Description des données pour le Corpus Brevets A.2 Analyse des brevets .1 Définition des points de vue .2 Multi-indexation des brevets. 56 Annexe B Description des données pour le Corpus PASCAL B.2 Extrait de données .1 Définition des points de vue. 59 Bibliographie 61 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des figures 1.1 Paradigme de traitement de l’information orienté par les points de vue (MVDA).1 Distribution du « fer à cheval ».2 évolution du volume de sphère en fonction de nombre de dimensions.3 Distribution en « fer à cheval » : (a) Distribution et plan principal trouvé par l’ACP .4 Projection faite par CCA de IR3 à IR2 de la distribution du « fer à cheval ».5 (a) deux points d’un spirale, (b) la distance euclidienne entre ces deux points et (c) la distance curviligne ou géodésique .6 Approximation de la distance curviligne à l’aide du chemin le plus court par l’intermédiaire des liens entre les centroïdes (ici la distance entre les deux centroïdes noircis) .7 CDA : Projection non-linéaire d’un « nœud de tresse »(de dimension 3 à 1) 14 2.8 Isomap : Exemple du « rouleau suisse »(à droite) et de la projection de 20000 échantillons tirés du rouleau par Isomap.9 BibTechMon : réseau de mots baséesur les relations entre eux.
Ce réseau contient 28 nœuds et 131 connexions .10 Deux types de géodésique : un diamètre passant par O et P et un arc de cercle AB orthogonal au cercle unité.11 La visualisation de l’arbre hyperbolique (Hypertree) .1 Cette figure montre le principe d’étiquetage d’arbre hyperbolique par la stratégie F-leaveOneOut .2 La structure de réseau bayésien pour la communication inter-topographies.3 Deux masses de points et leurs connexions par l’élasticité. cij est l’élement de matrice des indices de Jaccard.1 Méthode Dominant d’étiquetage d’arbre hyperbolique .2 Méthode ThemostFrequent d’étiquetage d’arbre hyperbolique .3 Méthode χ2 d’étiquetage d’arbre hyperbolique .4 Étiquetage d’arbre hyperbolique par la moyenne de F-mesure (F-moyenne) 47 4.5 Étiquetage d’arbre hyperbolique par la F-LeaveOneOut. 48 ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des figures 4.6 Une part vue de l’arbre qui présente le cluster source activé (en blue) pour la propagation .7 Résultat de la propagation du cluster activé dans le figure 4.6, les clusters en blue sont trouvé par la propagation bayesien .8 Cette figure montre le graphe utilisant le modèle de Spring pour visualiser les relations natureles entre les clusters d’enfants d’un père de l’arbre hyperbolique .1 Exemple de notice de brevet. L’indexation qui a été générée pour ce brevet est matérialisé par le contenu du champ «Final indexation».
Ces termes d’indexation sont préfixés par le nom du point de vue auquel ils sont associés : «adv.» pour le point de vue Avantages, «titre» pour le point de vue Titres, «use» pour le point de vue Utilisations, «soc.» pour le point de vue Déposants. 57 x LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des tableaux 2.1 Tableau de contingences pour l’absence ou la présence d’un terme dans les documents d’une classe .2 Notations de DBHC.1 Ce tableau présente un exemple de 6 clusters (C1 ,. , C6 ) annotés par 7 étiquettes, e1 ,. Le cluster C1 est annoté par les étiquettes e1 , e2 ,e3 ,e4 ,e5.
L’étiquette e4 est présente dans les clusters C1 et C4 .1 Ce tableau présente un exemple d’utilisation de la fonction g (cf.2 Ce tableau présente la comparaison de différentes approches d’étiquetage d’arbre hyperbolique .1 Tableau résumé des caractéristiques résultantes de brevets. 57 xi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des algorithmes 1 Algorithme de classification hiérarchique orienté par la densité (DBHC). 26 2 Procédure 1 : élimination de classes parents répétées. 26 3 Procédure 2 : éviter les classes recouvrantes.
27 xiii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des algorithmes xiv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 1 Introduction générale Sommaire 1.2 Contexte et Problématique .4 Plan du mémoire. 3 “ Savoir ce que tout le monde sait, c’est ne rien savoir. Le savoir commence là où commence ce que le monde ignore. ” Remy de Gourmont, “ Promenades philosophiques ” 1.1 Motivation D’un côté, les techniques de visualisation hyperbolique représentent un excellent compromis pour mener à bien de manière parallèle des tâches de fouilles et d’analyse de données.
En effet, ces techniques permettent de répondre à de nombreux problèmes posés par les techniques de visualisation traditionnelles. Elles traitent les problèmes de surcharge cognitive des représentations à base de graphes et ceux liés aux artefacts de représentation des méthodes de projection des données multidimensionnelles sur un plan d’interprétation. Elles permettent de plus d’exploiter les résultats des méthodes de clas- sification très performantes, plutôt que d’utiliser des méthodes moins performantes qui intègrent leur propre fonction de projection. D’un autre côté, l’étude des méthodes d’analyse des étiquettes associées aux classes issues d’une méthode de classification ouvre de nouvelles perspectives en analyse de don- nées.
En effet, les étiquettes qu’il est possible d’associer aux classes peuvent représenter à la fois des propriétés endogènes au processus de classification, et des propriétés exo- gènes, propres aux données qui ont été classifiées. L’analyse de leur distribution dans les 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Introduction générale classes et leur catégorisation permet donc à la fois de résoudre des problèmes de fouille de données, des problèmes de prédiction et des problèmes de filtrage d’information. L’étude de l’optimisation et de la combinaison de ces techniques, qui sont à la fois complémentaires et en synergie l’une avec l’autre dans le contexte général de l’analyse de données, s’avère donc être une voie de recherche extrêmement prometteuse.
Elle doit permettre de résoudre de nombreux problèmes liés à l’analyse des données complexes, comme les données documentaires ou les données bioinformatiques.2 Contexte et Problématique Premièrement, la visualisation des résultats du clustering reste un problème rela- tivement ouvert, malgré l’importance qu’il peut avoir dans la compréhension desdits résultats.