Tài liệu Dèinissions de co-similarité,à partir des marches aléatoires d’un graphe biparti

Mémoire de fin d’études Option Systèmes Intelligents & Multimédia Sujet : Définissions de co-similarité, à partir des marches aléatoires d’un graphe biparti Réalisé par DAO Van-Sang (Promotion 16 – IFI) Sous la direction de Thomas BURGER (CEA Grenoble) Gilles BISSON (Laboratoire LIG , Grenoble) Grenoble, Octobre 2013 "Petit à petit, l’oiseau fait son nid" Dic. Académie de 1835 I TABLE DES MATIÈRES REMERCIEMENT ................................................................................................................ IV LISTE DES FIGURES............................................................................................................ V LISTE DES TABLEAUX ...................................................................................................... VI RÉSUMÉ ............................................................................................................................... VII ABSTRACT .........................................................................................................................VIII CHAPITRE I – INTRODUCTION ........................................................................................ 1 1.1 1.2 1.3 1.4 Problématique et motivation .................................................................................... 1 Méthode de travail ..................................................................................................... 3 Environnement de travail ......................................................................................... 3 Plan de ce mémoire .................................................................................................... 4 CHAPITRE II – ÉTAT DE L’ART ........................................................................................ 5 2.1 Représentation des données ...................................................................................... 5 2.1.1 Représentation par une matrice des co-occurrences ............................................................... 5 2.1.2 Représentation par un graphe biparti ...................................................................................... 6 2.2 Classification ascendante hiérarchique (CAH) ............................................................ 7 2.3 Évaluation...................................................................................................................... 10 2.3.1 Matrice de confusion ............................................................................................................ 10 2.3.2 Problème d’affectation et l’algorithme Hongrois ................................................................. 10 2.4 Notions de base du graphe ........................................................................................... 12 2.4.1 Définition de graphe ............................................................................................................. 12 2.4.2 Graphe biparti ....................................................................................................................... 13 2.5 Marches aléatoires et Commute-Time Distance d’un graph .................................... 13 2.5.1 Matrice des degrés ................................................................................................................ 14 2.5.2 Matrice Laplacienne ............................................................................................................. 14 2.5.3 Marches aléatoires ................................................................................................................ 16 2.5.4 Commute-Time Distance...................................................................................................... 17 2.6 Méthodes de co-similarité existantes ........................................................................... 19 2.6.1 L’algorithme χ-Sim, 2008 .................................................................................................... 19 2.6.2 La mesure SNOS, 2004 ........................................................................................................ 22 2.6.3 L’algorithme SIMRANK, 2001............................................................................................ 23 2.6.4 L’analyse sémantique latente (LSA), 1990 ......................................................................... 24 2.6.5 Le noyau du temps d’aller-retour, 2007 ............................................................................... 25 CHAPITRE III – CO – SIMILARITE À PARTIR DES MARCHES ALÉATOIRES D’UN GRAPHE BIPARTI .................................................................................................... 26 3.1 Première approche : marches aléatoires d’un graphe biparti ................................. 26 3.2 Deuxième approche : nouvelle normalisation pour χ-Sim de base .......................... 29 3.3 Troisième approche : marches aléatoires et nouvelle normalisation ....................... 30 3.4 Quatrième approche : noyau du temps d’aller-retour d’un graphe ........................ 31 CHAPITRE IV - EXPÉRIMENTATIONS......................................................................... 33 II 4.1 Préparation des données .............................................................................................. 33 4.2 Environnement d’implémentation .............................................................................. 34 4.3 Implémentation ............................................................................................................. 34 4.4 Différence entre MATLAB et R .................................................................................. 38 4.5 Résultat .......................................................................................................................... 41 4.6 Discussion ...................................................................................................................... 42 CHAPITRE V – CONCLUSION ET PERSPECTIVE ..................................................... 50 5.1 Conclusion ..................................................................................................................... 50 5.2 Perspective ..................................................................................................................... 50 BIBLIOGRAPHIE ................................................................................................................. 51 III REMERCIEMENT Je tiens à remercier tout particulièrement M. Thomas BURGER, mon superviseur de stage au laboratoire EDyP au CEA de Grenoble, et M. Gilles BISSON, mon co-superviseur de stage au laboratoire LIG. Ils ont su m’orienter dans mon travail dans les bonnes directions tout en me laissant une large autonomie. Je les remercie également pour leur gros travail pour corriger ce rapport de stage. Mes remerciements s’adressent également à M. Syed Fawad Hussain qui m’a envoyé son code MATLAB de sa thèse, et M. Clément Grimal qui a extrait les jeux de données que j’ai utilisé pour tester mon algorithme en ce stage. Mon travail bénéficie aussi ses travaux de thèse de la mesure co-similarité pour classifier des données. Je tiens à remercier également tous les membres du laboratoire EDyP qui m’ont accueilli et ont créé un environnement idéal dans lequel j’ai travaillé pendant cinq mois et demi de stage. Je voudrais aussi adresser mes remerciements à tous les professeurs de l’IFI qui m’ont donné des connaissances et des expériences efficaces pendant ma scolarité à l’IFI. Merci également à tous ceux que j’oublie mais qui d’une manière ou d’autre manière m’ont permis de bien terminer mon stage. DAO Van-Sang Grenoble, France, Octobre 2013 IV LISTE DES FIGURES Figure 1: Le but de la classification des données .................................................................................... 1 Figure 2: Le processus de classification complet .................................................................................... 2 Figure 3: Comparaison des mesures classiques de similarité avec l’approche de χ-Sim ........................ 2 Figure 4: Représentation des données par graphe biparti (sans poids).................................................... 7 Figure 5: Dendrogramme s’affiche des clusters différents de 5 documents............................................ 9 Figure 6: Le problème d’affectation ...................................................................................................... 10 Figure 7 : La matrice de confusion de m5_8 de NG20-SMI ................................................................. 11 Figure 8 : La solution de problème d’affectation (le coût maximal) ..................................................... 11 Figure 9: Un graphe simple, non-orienté de 5 sommets ........................................................................ 12 Figure 10: Marches aléatoires d'un graphe ............................................................................................ 17 Figure 11: Schéma de l'algorithme Χ-SIM de base (2008) ................................................................... 21 Figure 12: Illustration de la décomposition en valeurs singulières pour l’analyse sémantique latente . 24 Figure 13: Illustration de co-occurrences d’ordres supérieurs dans un corpus simple, représenté sous la forme d’un graphe biparti. ..................................................................................................................... 26 Figure 14: Schéma de la première appoche........................................................................................... 29 Figure 15: Schéma de la deuxième approche ........................................................................................ 30 Figure 16: Schéma de la troisième approche ......................................................................................... 31 Figure 17: Schéma de la quatrième approche........................................................................................ 32 Figure 18: Diagramme des résultats de M10 avec χ-Sim 2008 et la première approche ...................... 43 Figure 19: Diagramme des résultats de NG2 avec χ-Sim 2008 et la première approche ...................... 43 Figure 20: Diagramme des résultats de X-SIM 2008, 1eme approche et 2eme approche..................... 44 Figure 21: Diagramme des résultats M2 de X-SIM 2008, XSIM 2010, 1eme approche et 2eme approche ................................................................................................................................................ 45 Figure 22: Diagramme des résultats de M5 de X-SIM 2008, XSIM 2010, 1eme approche et 2eme approche ................................................................................................................................................ 45 Figure 23: Diagramme des résultats de M10 de X-SIM 2008, 1eme approche et 2eme approche ....... 46 Figure 24: Diagramme des résultats de NG1 de X-SIM 2008, XSIM 2010, 1eme approche et 2eme approche ................................................................................................................................................ 46 Figure 25: Diagramme des résultats de NG2 de X-SIM 2008, XSIM 2010, 1eme approche et 2eme approche ................................................................................................................................................ 47 Figure 26: Diagramme des résultats de NG3 de X-SIM 2008, XSIM 2010, 1eme approche et 2eme approche ................................................................................................................................................ 47 Figure 27: Comparaison les résultats de la troisième approche et la deuxième approche..................... 48 Figure 28: Comparaison les résultats de la deuxième approche et la quatrième approche ................... 49 Figure 29: Comparaison les résultats de l'algorithme X-SIM 2010 et la quatrième approche .............. 49 V LISTE DES TABLEAUX Tableau 1: Un exemple de données à classifier....................................................................................... 6 Tableau 2: Un exemple de représentation par matrice ............................................................................ 6 Tableau 3: La matrice de confusion ..................................................................................................... 10 Tableau 4: Matrice d'adjacences............................................................................................................ 13 Tableau 5: Matrice des degrés du graphe .............................................................................................. 14 Tableau 6: Matrice Laplacienne ............................................................................................................ 16 Tableau 7: Matrice Laplacienne normalisée.......................................................................................... 16 Tableau 8: Matrice Pseudo-inverse de Moore-Penrose ......................................................................... 18 Tableau 9: Matrice Commute-Temps Distance du graphe .................................................................... 19 Tableau 10 : Les noms des groupes de la base de données 20Newsgroup ............................................ 33 Tableau 11: Les jeux de données extraites de la collection 20Newsgroups .......................................... 33 Tableau 12: Liste des packages R utilisés ............................................................................................. 34 Tableau 13: Matrice SR en MATLAB après la boucle de l'échantillon m5_1 ...................................... 39 Tableau 14: Matrice SR en R après la boucle de l'échantillon m5_1 .................................................... 39 Tableau 15: Résultats dans l'article publié en 2010 par Gilles et al. ..................................................... 41 Tableau 16: Résultats avec la base de données NG20-SMI .................................................................. 42 Tableau 17: Résultats avec la base de données NG20-PAM................................................................. 42 VI RÉSUMÉ La classification de données (apprentissage non-supervisé) a pour but de regrouper un ensemble d'observations sous la forme de classes homogènes et contrastées. Les notions de distances et de similarités sont souvent utilisées dans le domaine d’apprentissage automatique, en particulier des méthodes de classification. La plupart des mesures classiques ne sont pas adaptées pour les bases de données réelles. En effet, lorsque l’on applique ces méthodes à des données réelles, la grande taille de ces données et leur aspect creux rendent le plus souvent ces mesures inappropriées. C’est en partie afin de mieux prendre en compte ces propriétés des données réelles, que des approches de co-classification ont été développées. Ces approches classifient simultanément les attributs d’objets décrits par les données, permettant d’obtenir de bonnes performances, même lorsque celles-ci sont très creuses. Récemment, quelques méthodes co-classification ont étés inventées par des chercheurs dans le monde. Notre but principal dans ce stage est de développer une mesure de co-similarité en se basant sur des marches aléatoires d’un graphe biparti pour classifier des données textuelles. Mots-Clés: Co-similarité, marches aléatoires, graphe biparti, co-classification, coclustering, apprentissage automatique, fouille de texte. VII ABSTRACT Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups in the homogeneous form and contrary classes .The concepts of distance and similarity are often used in the machine for learning, especially in classification methods. Most of conventional measures are not suitable for real databases. Indeed, when these methods are applied to real data, the large size of these data and their hollow appearance often make these inappropriate actions. This is partly in order to better take into account the properties of real data, as co-clustering approaches have been developed. These approaches simultaneously classify attributes of objects described by the data, to obtain good performance, even when there are hollow. Recently, some methods have summers co- classification invented by researchers in the world. Our main goal in this internship is to develop a measure of co -similarity based on a random walk of a bipartite graph to classify the data textual. Keyword: random walk, bipartite graph, co-clustering, co-similarity, machine learning, text mining. VIII CHAPITRE I : INTRODUCTION CHAPITRE I – INTRODUCTION 1.1 Problématique et motivation L’objectif principal des méthodes de classification automatique (apprentissage non-supervisé) est de répartir les éléments d’un ensemble en groupes, c’est-à-dire d’établir une partition de cet ensemble, à condition que, chaque groupe doit être le plus homogène possible, et les groupes doivent être les plus différents possibles entre eux. Les notions de distances et de similarités sont souvent utilisées dans le domaine d’apprentissage automatique, en particulier des méthodes de classification. Avec les méthodes de classification classique, par exemple, nous devons classifier des documents textuels. Au début, on va représenter ces documents dans le modèle vectoriel. C'est-à-dire que l'on va créer une matrice numérique. Les lignes sont considérées comme des documents. Les colonnes sont considérées comme des mots qui apparaissent dans ces documents. Chaque document sera un vecteur de plusieurs dimensions. Maintenant, pour calculer la similarité entre documents, on peut utiliser les similarités Cosinus 1, les distances Euclidiennes, les distances Minkowski 2, etc. De telles mesures de similarité sont fondées sur le nombre de mots qui sont partagés entre les deux documents. Ici, la similarité dépend beaucoup des mots communs entre des documents. Enfin, on va utiliser des algorithmes dans le domaine d’apprentissage automatique pour regrouper des documents. On peut citer quelques algorithmes traditionnels : K-Mean 3, Clustering Ascendante Hiérarchique – CAH (voir Sec. 2.2). Ces étapes peuvent être illustrées dans la figure suivante : Figure 1: Le but de la classification des données Les étapes d’une classification sont comme les suivantes : L’étape (1) consiste à pré-traiter les données brutes, afin de les mettre sous une forme (matrice, graphe, etc.) Dans la tâche de classification de documents, il s’agira de créer la matrice de co-occurrences avec les mots qui les composent. 1 Le site : http://fr.wikipedia.org/wiki/Similarit%C3%A9_cosinus Le site : http://en.wikipedia.org/wiki/Minkowski_distance 3 Le site : http://fr.wikipedia.org/wiki/Algorithme_des_k-moyennes 2 1 CHAPITRE I : INTRODUCTION L’étape (2) est le calcul des similarités ou de distances entre les objets que l’on cherche à classifier. Il existe d’ailleurs différentes fonctions permettant de transformer une similarité en distance et inversement. Classiquement, on peut représenter ces valeurs dans une matrice carrée et symétrique. L’étape (3) consiste à créer les classes d’objets à partir de leurs similarités. L’étape (4) consiste alors à comparer les classes prédites aux classes réelles, grâce à des mesures d’évaluation objectives. On peut considérer cette étape comme la méthode d’évaluation. Figure 2: Le processus de classification complet Comme nous avons mentionné ci-dessus, la méthode de classification classique, les notions de distances et de similarités sont souvent utilisées dans le domaine d’apprentissage automatique. Mais, la plupart des mesures classiques ne sont pas adaptées pour les bases de données réelles. En effet, lorsque l’on applique ces méthodes à des données réelles, la grande taille de ces données et leur aspect creux rendent le plus souvent ces mesures inappropriées. C’est en partie afin de mieux prendre en compte ces propriétés des données réelles, que des approches de coclassification ont été développées. La figure ci-dessous illustre la différence entre la mesure de similarité classique et la mesure de co-similarité χ-Sim (voir Sec. 2.6.1). Figure 3: Comparaison des mesures classiques de similarité avec l’approche de χ-Sim (Réutilisation avec permission de Clément[1] ) Pour la notion de co-classification, on ne fait pas exactement comme la méthode de classification classique. Ici, l’idée fondamentale est deux documents n’ont pas nécessairement besoin d’avoir des mots en communs, mais peut-être ils ont des mots 2 CHAPITRE I : INTRODUCTION similaires. Autrement dit, l’idée est donc de ne pas seulement prendre en compte les mots communs, mais également toutes les paires de mots similaires qui y apparaissent. Respectivement, deux mots sont similaires s’ils apparaissent dans des documents similaires. On remarque immédiatement la dualité entre les documents et les mots, et la symétrie dans leur relation. Le problème qui se dégage immédiatement de cette idée de départ est que les similarités entre documents dépendent des similarités entre mots, et vice versa. χ-Sim est une approche de co-similarité comme cela. Il est proposé par Gilles BISSON et al. [2]. Ce stage s'appuie sur cette idée de base de χ-Sim, mais ici, on va développer d’une autre manière, en se basant le théorique graphe. Plus précisément, ce sont des marches aléatoires d’un graphe biparti. En fait, on peut complètement représenter la relation entre des documents et des mots par un graphe biparti. Pour l’instant, des chercheurs ont développé leurs algorithmes en se basant sur des marches aléatoires pour classifier des données (clustering), on peut citer des articles [3] [4] [5] [6] . Quelques auteurs ont utilisé des marches aléatoires dans le domaine de segmentation d’images [7]. Des marches aléatoires sont le cœur de la classification de spectre très connu [8] (de l’anglais, spectral clustering), particulièrement utilisées dans des articles de l’auteur Luh Yen et al. [9] [10] [11] [12] [13] [14]. Dans ce stage, on va utiliser des marches aléatoires (voir Sec. 2.5.3) pour définir co-similarité. 1.2 Méthode de travail En 2008, Gilles et son étudiant a développé une mesure de co-similarité pour classifier des données. Leur méthode donne le bon résultat avec les jeux de données de test. Cette méthode s’appelle χ-Sim [2]. Ensuite, ils ont créé une nouvelle version de l’algorithme χ-Sim en 2010. Au début, nous faison une bibliographie. C’est-à-dire qu’on étudie des méthodes de co-similarité présentées par des chercheurs du monde. Nous nous concentrons sur la mesure de co-similarité χ-Sim publiée par Gilles et al. Ensuite, nous étudions des notions de base du graphe, surtout des marches aléatoires, le noyau du temps d’aller-retour (de l’anglais, Commute – Time Kernel) (voir Sec. 2.6.5) du graphe. Ainsi, les travaux concrets à réaliser dans le cadre du stage sont les suivants : • Aspects théoriques : o D’étudier et synthétiser ce que sont les méthodes de co-similarité, de co-clustering et ainsi que les approches existantes ; o D’étudier en bref la description du graphe biparti et des connaissances concernant des marches aléatoires d’un graphe ; o De proposer des solutions de co-similarité pour classifier des données. • Productions d’applications : o D’implémenter des solutions proposées en langage R ; o De tester avec des jeux de données réels. 1.3 Environnement de travail 3 CHAPITRE I : INTRODUCTION Le stage est réalisé au laboratoire Étude de la Dynamique des Protéomes (EDyP) 4. L'équipe EDyP développe un ensemble d’approches protéomiques dans le cadre de projets biologiques de grande envergure. Il a consolidé une expertise dans le domaine de l’analyse protéomique d’échantillons biologiques complexes et de quantification des protéines par spectrométrie de masse. Ce savoir-faire est mis en œuvre pour répondre à des problématiques variées en biologie cellulaire, biologie végétale et dans le domaine biomédical. L'équipe EDyP fait partie du Laboratoire de Biologie à grande Echelle (BGE), au sein de l'Institut de la vie Division des sciences Technologies / Vie (iRTSV / DSV) de l'établissement français Commissariat à l'Energie Atomique et aux énergies alternatives (CEA). Le laboratoire est situé dans la soi-disant capitale des Alpes françaises, Grenoble. 1.4 Plan de ce mémoire • Chapitre II - Etat de l’art : ce chapitre présentera des façons pour représenter des jeux de données aux approches d’apprentissage automatiques, les méthodes de classifications classiques, des notions de base concernant le graphe, par exemple : des marches aléatoires, Commute-Time Distance, la matrice de Laplacienne d’un graphe. Dans cette partie, nous allons décrire la méthode d’évaluation, ainsi que des méthodes qui concernent la co-classification. • Chapitre III – Co-similarité à partir des marches aléatoires d’un graphe : ce chapitre décrira les jeux de données que l’on va utiliser dans ce stage pour tester nos algorithmes. De plus, nous allons proposons 4 approches co-similarité qui concernent des connaissances présentées dans le chapitre dernier. • Chapitre IV - Expérimentations : ce chapitre exposera l’environnement d’implémentation, la méthode d’implémentation nos algorithmes, ainsi que les résultats et des discussions sur ces résultats. • Chapitre V - Conclusion et Perspective : Ce chapitre donnera des conclusions sur les travaux ayant été réalisés et des perspectives de ces travaux dans l’avenir. 4 Le site web du laboratoire EDyP au CEA de Grenoble : http://edyp.fr/ 4 CHAPITRE II : ÉTAT DE L’ART CHAPITRE II – ÉTAT DE L’ART Dans ce chapitre, nous allons parler de la méthode de représentation des données dans le domaine d’apprentissage automatique. Ensuite, la classification ascendante hiérarchique – CAH (voir Sec. 2.2) sera décrite. C’est l’algorithme que l’on va utiliser pour classifier des données de test. Nous présenterons la méthode d’évaluation, des notions de base du graphe concernant des marches aléatoires, le noyau du temps d’aller-retour d’un graphe. Enfin, quelques méthodes de coclassification existantes qui se basent des co-similarités seront présentées. 2.1 Représentation des données Les données que nous considérerons dans l’ensemble de ce stage décrivent des relations entre deux types d’objets. Ces types d’objets pourront représenter aussi bien des documents, des mots. Dans ce stage, on s’intéresse seulement à des jeux de données de documents textuels. Chaque document comporte plusieurs mots. En fait, il existe différentes façons de modéliser de telles données, mais, ici, nous allons voir quelles sont les deux principales dans les sections suivantes : représentation des données par une matrice et par un graphe biparti. En ce stage, on s’intéressera à ces deux représentations. 2.1.1 Représentation par une matrice des co-occurrences Sans perte de généralité, nous supposons que l’on a N documents Xi (i : 1-N), et chaque documents comporte mi mots. Nous introduisons la notation suivante : wij est le nombre d’occurrences du mot i (mi)dans le document j (Xj). A partir de cela, on peut créer une matrice des co-occurrences M. Xj mi … …. … …. … wij … … … … … … En effet, nous pouvons considérer cette représentation des données qui est d’origine du modèle vectoriel : chaque document sera un vecteur, qui se compose des mots. En pratique, nous n’utilisons pas tous les mots des documents, on va sélectionner des mots les plus utiles. Deux méthode de choix des mots peuvent être citées : Supervised Mutual Information preprocessing (SMI)[15] et Partitioning Around Medoids preprocessing (PAM)[16]. La pondération TF-IDF (de l’anglais, Term Frequency - Inverse Document Frequency)[17] a aussi été utilisée dans la littérature. Un exemple 5 de représentation des données par une matrice, en utilisant le nombre d’occurrences. 5 Cet exemple est extrait à partir de l’article[18] : "Learning Similarity Measures in Non-orthogonal Space" , par Ning Liu et al. - 2004 5 CHAPITRE II : ÉTAT DE L’ART Tableau 1: Un exemple de données à classifier Tableau 2: Un exemple de représentation par matrice Dans ce stage, nous utiliserons le deuxième modèle. 2.1.2 Représentation par un graphe biparti Dans ce modèle de représentation, on parle de la représentation des données textuelles par un graphe. Chaque instance d’objets est représentée par un sommet d’un graphe. Dans notre cas, le graphe sera plus précisément biparti. Un ensemble des sommets de ce graphe est celui des documents, l’autre est celui des mots. Les liens entre un mot et les documents sont connectés si ce mot apparait dans les documents. Si le mot i n’apparait pas dans le document j, alors, il n’y a pas d’arête entre le sommet i et le sommet j. Les poids des arêtes sont le nombre d’occurrences des mots dans les documents. 6 CHAPITRE II : ÉTAT DE L’ART Figure 4: Représentation des données par graphe biparti (sans poids) 2.2 Classification ascendante hiérarchique (CAH) En fait, il existe plusieurs techniques de classification. En ce stage, on s’intéressera juste à la classification ascendante hiérarchique (CAH). L'objectif de cette méthode (CAH) est de classer des individus en groupes ayant un comportement similaire sur un ensemble de variables. On commence par agréger les 2 individus les plus proches. Puis, on continue en agrégeant les éléments (individus ou groupes d'individus) les plus semblables. Ces agrégations sont effectuées 2 à 2. L'algorithme continue jusqu'à ce que l'ensemble des individus se retrouve dans une unique classe. Les individus sont donc regroupés de façon hiérarchique. C’est parce que cette technique part du particulier pour remonter au général qu’elle est dite «ascendante». Chaque classe d'une partition est incluse dans une classe de la partition suivante. Le principal problème de cette méthode hiérarchique consiste à définir le bon critère de regroupement de deux classes, c'est-à-dire trouver une bonne méthode de calcul des distances entre classes. Algorithme CAH: • Initialisation : les classes initiales sont les n individus. Calculer la matrice de leurs distances deux à deux • Répérer les deux étapes suivantes jusqu’à l’agrégation en une seule classe :  Regrouper les deux éléments (classes) les plus proches au sens de la distance entre groupes choisie  Mettre à jour le tableau de distances en remplaçant les deux classes regroupées par la nouvelle et en calculant sa distance avec chacune des autres classes • Nécessité de définir une distance entre groupes d’individus (appelé stratégie d’agrégation). • Nécessite de choisir le nombre de classes à retenir 7 CHAPITRE II : ÉTAT DE L’ART Dans la méthode CAH, pour calculer les distances entre deux individus, nous pouvons utiliser la Distance Euclidienne ; la Distance de Manhattan; la Distance de Minkowski ; la Distance de Tchebychev 6. Ensuite, pour choisir un indice d’agrégation (Autrement dit, c’est une "distance" entre classes A et B), les choix proposés sont les suivants (des photographies de cette section sont pris du site http://bis.net.vn/forums/t/571.aspx) : 6 - Single linkage (distance minimum): la distance minimum entre toutes les distances entres les points de A et ceux de B. - Complète linkage (distance maximum). Dans cette méthode, les distances entre classes sont déterminées par la plus grande distance existant entre deux objets de classes différentes (c'est-à-dire les "voisins les plus éloignés"). - Moyenne non pondérée des groupes associés. Ici, la distance entre deux classes est calculée comme la moyenne des distances entre tous les objets pris dans l'une et l'autre des deux classes différentes. - Centroïde : Le centroïde d'une classe est le point moyen d'un espace multidimensionnel, défini par les dimensions. Dans cette méthode, la distance entre deux classes est déterminée par la distance entre les centroïdes respectifs. Le site : http://fr.wikipedia.org/wiki/Distance_(math%C3%A9matiques) 8 CHAPITRE II : ÉTAT DE L’ART - Médiane : Cette méthode est identique à la précédente, à une différence près ; une pondération est introduite dans les calculs afin de prendre en compte les tailles des classes (c'est-à-dire le nombre d'objets contenu dans chacune). - Méthode de Ward [19]. Cette méthode tente de minimiser la somme des carrés de tous les couples (hypothétiques) de classes pouvant être formés à chaque étape. Les indices d'agrégation sont recalculés à chaque étape à l'aide de la règle suivante : si une classe M est obtenue en regroupant les classes K et L, sa distance à la classe J est donnée par : Dendrogramme : représentation graphique sous forme d’arbre binaire, d’agrégations successives jusqu’à réunion en une seule classe de tous les individus. La hauteur d’une branche est proportionnelle à la distance entre les deux objets regroupés. Figure 5: Dendrogramme s’affiche des clusters différents de 5 documents (photographie de F.S.Housain[20]) La classification ascendante hiérarchique (CAH) est maintenant très connue et est utilisée dans plusieurs domaines pour classifier des données. Cette méthode a été implémentée dans la plupart logiciels de fouille de données, comme R 7, MATLAB 8, Statistica 9 , WEKA 10, SPSS 11. La classification hiérarchique est décrite complètement 7 Le site : http://www.r-project.org/ Le site : http://www.mathworks.com/products/matlab/ 9 Le site : http://www.statsoft.fr/ 10 Le site : http://www.cs.waikato.ac.nz/ml/weka/ 11 Le site : http://www-01.ibm.com/software/analytics/spss/ 8 9 CHAPITRE II : ÉTAT DE L’ART dans le livre « Algorithms for clustering data » [21], écrit en 1988 par Anil K. Jain et Richard C. Dubes. Nous allons utiliser cette méthode de classification dans tous nos algorithmes de classifications proposées. Dans le logiciel R, on a besoin d’utiliser la fonction hclust. 2.3 Évaluation En fait, il existe de nombreuses mesures d’évaluation de classification. Dans ce stage, nous allons utiliser deux méthodes classiques comme suivantes : la matrice de confusion et la précision micro-moyennée à l’aide de l’algorithme Hongrois. 2.3.1 Matrice de confusion La matrice de confusion est un outil servant à mesurer la qualité d’un système de classification dans l’apprentissage supervisé (pas apprentissage non-supervisé). Dans ces systèmes, les classes ont été bien étiquetées. Généralement, soit K le nombre de classes notées l1 . . . lK. On note la matrice de confusion C de taille KxK pour une classification des objets en K classes. Les lignes de C représentent les classes réelles et les colonnes de C représentent les classes prédites. Le terme cij de C est égal au nombre d’objets appartenant à la classe li et ayant été classifiés à la classe lj . Sur la diagonale, on trouve donc les valeurs bien classées, hors de la diagonale les éléments mal classés. Classes réelles l1 l2 l3 … lK l1 c11 c21 c31 … cK1 Classes prédites l2 l3 … c12 c13 … c22 c23 … c32 c33 … … … … cK2 cK3 … Tableau 3: La matrice de confusion lK c1K c2K c3K … cKK 2.3.2 Problème d’affectation et l’algorithme Hongrois Tout d’abord, le problème d’affectation (de l’anglais, the assignment problem) est celui de déterminer un couplage maximum (de l’anglais, a maximum weight matching) dans un graphe biparti ayant des poids. Figure 6: Le problème d’affectation Nous pouvons mentionner un exemple de ce problème est comme le suivant : 10 CHAPITRE II : ÉTAT DE L’ART on a n employés et n tâches. Chaque employé ne peut être affecté qu’à une seule tâche et chaque couple (tâche, employé), qui a un coût. Le but est de minimiser le coût total d’exécution des tâches. L’algorithme Hongrois[22] (de l’anglais, The Hungarian method) est un algorithme spécialisé permettant de résoudre le problème d’affectation. Normalement, l’algorithme Hongrois sert à déterminer le coût minimal, mais on peut transférer un peu pour faciliter trouver le coût maximal. Pour le problème de maximisation, on doit ajouter une étape initiale. C'est de choisir le plus grand nombre et trouver l’écart de tous les éléments restants par rapport à ce nombre pour trouver la matrice des pénalités. Le problème initial est alors équivalent au problème de minimiser les pénalités. Dans un contexte d’apprentissage non-supervisé (autrement dit, c’est clustering. C’est le cas dans ce sujet de stage), les classes que l’on obtient ne sont pas étiquetées, c’est à dire que lors de la comparaison avec les classes attendues des objets, on ne connaît pas le couplage entre classes prédites et classes réelles. On ne peut pas garantir que la classe prédite i correspond au classe réel li. Donc, on cherche une association : chaque classe prédite à une certaine « meilleure» classe réelle. Ce problème est alors équivalent au problème d’affectation de maximisation, et il peut être résolu par l’algorithme Hongrois [22]. Le but est maintenant de trouver le coût maximal. Par exemple, on a une matrice de coût comme le suivant : Figure 7 : La matrice de confusion de m5_8 de NG20-SMI 12 Nous pouvons considérer cette matrice comme une matrice de coût. Nous allons déterminer le coût maximal. Le résultat est comme suit : Figure 8 : La solution de problème d’affectation (le coût maximal) Maintenant, pour calculer l’exactitude de l’algorithme clustering (de l’anglais, accuracy), nous prenons la somme des valeurs dans les positions ayant le numéro 1 (Elles sont encadrées par un rectangle rouge), qui correspondent aux valeurs dans les mêmes places dans la matrice de confusion au-dessus. Nous divisons cette somme sur le nombre de tous éléments au début. Si le résultat de cette division est égal à 1, c’est12 Pour obtenir ce résultat, on exécute le code R de X-SIM en 2008, avec le nombre d’itérations est de 3. Le jeu de données m5_8.txt de NG20-SMI, qui peut être téléchargé sur le site de Clément http://membreslig.imag.fr/grimal/data.html. 11