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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com "Petit à petit, l’oiseau fait son nid" Dic. Académie de 1835 I LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com TABLE DES MATIÈRES REMERCIEMENT. IV LISTE DES FIGURES. V LISTE DES TABLEAUX .VIII CHAPITRE I – INTRODUCTION .1 Problématique et motivation .2 Méthode de travail .3 Environnement de travail .4 Plan de ce mémoire.
4 CHAPITRE II – ÉTAT DE L’ART .1 Représentation des données .1 Représentation par une matrice des co-occurrences .2 Représentation par un graphe biparti .2 Classification ascendante hiérarchique (CAH) .1 Matrice de confusion .2 Problème d’affectation et l’algorithme Hongrois .4 Notions de base du graphe .1 Définition de graphe .5 Marches aléatoires et Commute-Time Distance d’un graph .1 Matrice des degrés .4 Commute-Time Distance.6 Méthodes de co-similarité existantes .2 La mesure SNOS, 2004 .4 L’analyse sémantique latente (LSA), 1990 .5 Le noyau du temps d’aller-retour, 2007. 25 CHAPITRE III – CO – SIMILARITE À PARTIR DES MARCHES ALÉATOIRES D’UN GRAPHE BIPARTI .1 Première approche : marches aléatoires d’un graphe biparti .2 Deuxième approche : nouvelle normalisation pour χ-Sim de base .3 Troisième approche : marches aléatoires et nouvelle normalisation .4 Quatrième approche : noyau du temps d’aller-retour d’un graphe. 31 CHAPITRE IV - EXPÉRIMENTATIONS. 33 II LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Préparation des données .4 Différence entre MATLAB et R.
42 CHAPITRE V – CONCLUSION ET PERSPECTIVE. 51 III LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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, co- clustering, apprentissage automatique, fouille de texte.
VII LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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.org/wiki/Similarit%C3%A9_cosinus 2 Le site : http://en.org/wiki/Minkowski_distance 3 Le site : http://fr.org/wiki/Algorithme_des_k-moyennes 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 co- classification 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.