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

  • 61 trang
  • file .pdf
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 Problématique et motivation .................................................................................... 1
1.2 Méthode de travail ..................................................................................................... 3
1.3 Environnement de travail ......................................................................................... 3
1.4 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, co-
clustering, 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
2
Le site : http://en.wikipedia.org/wiki/Minkowski_distance
3
Le site : http://fr.wikipedia.org/wiki/Algorithme_des_k-moyennes
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 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. 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 co-
classification 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.
mi
… …. … ….
Xj … 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) :
- 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.
6
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/
8
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/
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 prédites
l1 l2 l3 … lK
l1 c11 c12 c13 … c1K
l2 c21 c22 c23 … c2K
Classes
l3 c31 c32 c33 … c3K
réelles
… … … … … …
lK cK1 cK2 cK3 … cKK
Tableau 3: La matrice de confusion
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 :
12
Figure 7 : La matrice de confusion de m5_8 de NG20-SMI
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’est-
12
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://membres-
lig.imag.fr/grimal/data.html.
11