Classification de documents médicaux l’aide de cartes auto-organisatrices (SOM) basée sur une ontologie Mémoire de fin d’études rédigé par PHAM Minh Hai, promotion IX-IFI 20 novembre 2005 sous la direction de: Michel SIMONET Delphine BERNHARD Equipe OSIRIS Laboratoire TIMC-IMAG Institut d'Ingénierie de l'Information de Santé Faculté de Médecine, 38700 La Tronche – France Le travail décrit dans ce mémoire a été effectué dans le cadre du projet européen NOESIS auquel participe l’équipe OSIRIS (IST-2002-507960-NOESIS) Table des matières REMERCIEMENTS I RESUME II ABSTRACT III LISTE DES FIGURES IV LISTE DES TABLEAUX VI CHAPITRE 1: INTRODUCTION I PROBLEMATIQUE II MOTIVATION III CONTRIBUTION IV ENVIRONNEMENT DE STAGE CHAPITRE 2: ETAT DE L’ART I INTRODUCTION II METHODES DE REGROUPEMENT Introduction Etat de l’art Notre choix III METHODES DE REPRESENTATION DE DOCUMENTS Modèle de l'espace vectoriel [12] 10 Latent Semantic Indexing –LSI [13] 11 Méthodes particulières aux SOM 13 a Cartes de catégories de mots 13 b Correspondance aléatoire 16 c Autre approche 18 Méthodes d’indexation multilingue 18 Ontologie pour la représentation de documents 19 IV VISUALISATION DES RESULTATS DE LA RECHERCHE 19 Motivation 19 Etiquetage des groupes générés par la SOM 21 a Étiquetage manuel 21 b Étiquetage basé sur des groupes prédéfinis 22 c Etiquetage par les étiquettes des entrées 24 d Méthode LabelSOM[6] 25 CHAPITRE 3: CLASSIFICATION DE DOCUMENTS MEDICAUX A L’AIDE DE SOM EN UTILISANT UNE ONTOLOGIE 30 I REGROUPEMENT DE DOCUMENTS BASE SUR LA SOM 30 Introduction de l’algorithme de SOM 30 a Structure de SOM 30 b Apprentissage 33 c Classification 35 SOM pour regrouper des documents : Etat de l’art 36 a SOM classique 36 b SOM de taille flottante 37 c SOM hiérarchique 39 d Remarque 41 II SOM ET ONTOLOGIE: TRAVAUX CONCERNES 43 Introduction 43 Ontologie pour la représentation de documents 44 III UTILISATION D’UNE ONTOLOGIE POUR LA CLASSIFICATION DE DOCUMENTS BASEE SUR LA SOM 45 Introduction 45 Sources de documents 46 Prétraitement 47 CHAPITRE 4: EVALUATION 50 I RÉSULTATS 50 II CONCLUSION 53 REFERENCES 55 i Remerciements J’adresse tout d’abord mes remerciements Michel Simonet, responsable de l’équipe OSIRIS du laboratoire TIMC, qui m’a accueilli et m’a donné des conseils précieux Sans lui, mon stage n’aurait pas existé Je souhaite ensuite remercier spécialement Delphine Bernhard qui a bien voulu écouter avec attention toutes mes idées et m’a donné des conseils très concrets Les discussions entre nous étaient très ouvertes et efficaces Je remercie Michel et Delphine aussi pour leur relecture de ce rapport et pour m’avoir proposé des corrections nécessaires Je voudrais aussi remercier Severine Gedzelman, Radja Messai, Gayo Diallo et Rémi Patriarch qui m’ont beaucoup aidé pendant ce stage Grenoble Leurs idées sur les points importants autour de mon stage m’ont fait mieux comprendre mon sujet Enfin, je tiens remercier mes soeurs, mon père et mon frère qui m’ont énormément encouragé pendant mon stage en France et spécialement ma mère pour tout l’amour qu’elle a réservé pour moi jusqu’à son dernier souffle ii Résumé Pour regrouper un ensemble de documents médicaux au format numérique, trois aspects importants peuvent affecter l’efficacité de la méthode: la méthode de représentation des documents, l’algorithme de regroupement et la méthode de représentation des résultats La méthode de regroupement doit être suffisamment puissante pour pouvoir grouper un grand ensemble de documents et permettre l’utilisateur de visualiser des résultats Les cartes auto-organisatrices – SOM - ont été choisies pour cette raison La méthode de représentation de documents doit produire des vecteurs de documents de faible dimension et posséder la capacité d'indexer des documents multilingues C’est la raison pour laquelle la méthode basée sur une ontologie a été choisie La méthode LabelSOM a quant elle été choisie pour étiqueter des groupes de SOM Nous prouvons par des expériences que la méthode qui combine la SOM et une ontologie peut aider réduire les dimensions et produire des résultats encourageants avec des documents multilingues iii Abstract Clustering similar documents is a difficult task for text data mining Difficulties stem especially from the way documents are numerically encoded In this paper, we will present a method which uses Self Organizing Map (SOM) to cluster medical documents The originality of the method is that it does not rely on the words shared by documents but rather on concepts taken from an ontology Our goal is to cluster various medical documents in thematically consistent groups (e.g grouping all the documents related to cardiovascular diseases) Before applying the SOM algorithm, documents have to go through several pre-processing steps First, textual data have to be extracted from the documents, which can be either in the PDF or HTML format Documents are then indexed, using several kinds of indexing units: words, stems, and concepts After indexing, documents can be numerically represented by vectors whose dimensions correspond to indexing units These vectors store the weight of the indexing unit within the document they represent They are given as inputs to a SOM which arranges the corresponding documents on a two-dimensional map We have compared the results for two indexing schemes: stem-based indexing and conceptual indexing We will show that using an ontology for document clustering has several advantages It is possible to cluster documents written in several languages since concepts are languageindependent This is especially helpful in the medical domain where research done is often presented in several languages Another advantage is that the use of concepts helps reduce the size of the vectors, which, in turn, reduces processing time iv Liste des figures Figure : La recherche sur google.com avec le mot clé «vélo» Figure 2: Représentation de chaque document sous forme de vecteur d’éléments sémantiques Ce vecteur est établi en se basant sur le dictionnaire et le document original Figure 3: Représentation des documents par des vecteurs des termes 11 Figure : Une décomposition en valeurs singulières 12 Figure 5: Un exemple de représentation du contexte du mot « aime » 14 Figure 6: Carte de catégories de mots avec des mots des contes de Grimm 15 Figure 7: extraite partir de [15] L'architecture de base de la méthode Websom La carte de documents est construite partir des documents indexés par des catégories de mots générées par la carte de catégories de mots Les deux cartes sont produites avec l'algorithme SOM 16 Figure 8: Formes d'I et de ε : I a des valeurs pour les composants qui ne sont pas sur sa diagonale Les composants sur la diagonale d'I correspondent ceux de la diagonale de R T R ε a des valeurs pour les composantes situées sur sa diagonale Ses composants qui ne sont pas sur la diagonale sont ceux qui ne sont pas sur la diagonale de R T R 17 Figure 9: Un exemple de recherche : c'est la SOM résultante avec différents groupes de documents Avec le mot-clé «vélo», comment peut-on savoir quel groupe pour sujet les vélos (c'est dire les bicyclettes)? Si chaque groupe a sa propre étiquette il sera plus facile pour l'utilisateur de choisir 20 Figure 10 : Un exemple d’étiquetage manuel extrait partir de [27] Le but de ceci est de déterminer si l'organisation des documents sur la carte est bien faite ou pas Ce n'est pas utile du tout dans le but de la recherche d’information 21 Figure 11: Structure des vecteurs en entrée 22 Figure 12: Un exemple de l’étiquetage basé sur les groupes prédéfinis extrait du site Web du projet de WEBSOM : http://websom.hut.fi/websom/comp.ai.neural-netsnew/html/root.html 23 Figure 13:Un exemple des cartes de catégories de mots Cette figure est extraite de [28] 25 Figure 14: Erreurs de quantisation avec M=2 26 v Figure 15: deux types de seuil 27 Figure 16 : Le composant représentant un terme trop commun devrait être exclu de la liste de candidat 28 Figure 17: Le premier composant est plus petit que T2 celui-ci est donc éliminé 28 Figure 18 : Une 7x8 SOM de topologie carrée 31 Figure 19: Une 8x8 SOM de topologie hexagonale 31 Figure 20: Un exemple d'une carte de topologie carrée Les vecteurs de neurones ont M dimensions La carte a deux dimensions avec neurones verticaux et neurones horizontaux Chaque neurone a une couleur différente des autres Ceci signifie que les vecteurs de neurones sont différents 32 Figure 21: La forme du chapeau mexicain 34 Figure 22: Dans cet exemple, 10 données d'entrée (cercles) sont classifiées dans deux groupes L’espace de données a dimensions et, après l'apprentissage, deux neurones (carrés) ont des positions montrées dans le graphique Après la classification, une entrée a une couleur du groupe auquel elle appartient La ligne dans la figure sépare deux groupes 36 Figure 23: La carte finale d'un processus d’apprentissage (extraite de [9]) Il y a beaucoup de noeuds mais seulement groupes (chaque groupe est dans un modèle de fond différent) Il y a un groupe dont les noeuds ne se relient aucun noeud d'autres groupes 39 Figure 24: Une hiérarchie des cartes auto-organisatrices (Extraite de [10]) 40 Figure 25: Une SOM hiérarchique croissante (Extraite partir de [11]) Sur la couche 1, il y a groupes au début Chaque noeud de la carte de la première couche a une SOM indépendante la deuxième couche Cependant, seulement deux noeuds d'une carte de la deuxième couche ont des cartes indépendantes de la troisième couche 41 Figure 26: Une partie de la structure hiérarchique de l'ontologie dans le domaine de "cancer." 43 vi Liste des tableaux Tableau 1: La carte obtenue avec l’ontologie 51 Tableau 2: La carte obtenue avec la pleine représentation 52 44 Les relations entre des concepts dans la hiérarchie ontologique d'un domaine donné sont basées sur leurs relations sémantiques qui sont spécifiques ce domaine L’algorithme SOM a été depuis longtemps proposé et appliqué dans le domaine du regroupement de documents textuels Les recherches concernant la SOM sont très nombreuses aujourd’hui Le terme «ontologie» est aussi apparu depuis une vingtaine d’années en informatique Cependant, la combinaison entre SOM et ontologie n’a pas été beaucoup étudiée Dans cette section, on va voir quelques combinaisons possibles entre ces deux approches Ontologie pour la représentation de documents Pour utiliser des ontologies dans le domaine du regroupement de textes, deux étapes de prétraitement sont nécessaires Une ontologie qui décrit le domaine cible doit d’abord être construite, en utilisant un corpus de textes ou des définitions manuelles, ou les deux Les documents peuvent être indexés travers cette structure pour produire des vecteurs qui les représentent Ces vecteurs seront utilisés par une méthode de regroupement comme des entrées Pour la première tâche – la construction de l'ontologie, plusieurs outils peuvent être utilisés pour déterminer les concepts et leurs inter-relations Pour la seconde, un indexeur est nécessaire pour produire des vecteurs caractéristiques de documents Les ontologies ont récemment été utilisées pour représenter des documents La première recherche de ce genre a été réalisé par A Hotho et ses collègues avec l'article texte "Ontology-based text clustering" [18] Pour étayer leur proposition, ils ont utilisé le K-Means comme méthode de regroupement Leur approche, nommée COSA (Concept Selection and Aggregation), utilise une ontologie noyau pour restreindre l'ensemble de traits de documents et proposer automatiquement des agrégations appropriées Les concepts qui sont sélectionnés depuis l’ensemble de documents doivent représenter un domaine prédéfini Ensuite, parce que le nombre de concepts est élevé, l’agrégation est réalisée de manière générer pour des concepts de même catégorie un concept qui les recouvre Ils proposent par conséquent une méthode heuristique basée sur une hétérarchie qui fournit des vues de concepts afin que le nombre de dimensions de vecteurs résultants puisse être réduit Cette recherche est très intéressante et les résultats obtenus sont encourageants 45 En suivant cette proposition, des recherches ont été réalisées pour appliquer des ontologies domaine-spécifiques au regroupement de texte Par exemple, dans [19] une ontologie est utilisée pour regrouper des clients et des demandes dans la Gestion du Service après-vente Dans [20], la tâche de regroupement se base sur une ontologie dans l’analyse de l'expression du gène Ces exemples ont été publiés récemment III Utilisation d’une ontologie pour la classification de documents basée sur la SOM Introduction Nous avons examiné certaines méthodes de représentation du texte Certaines sont basées sur la pleine représentation et ont été traitées par des transformations mathématiques qui rendent impossible l'explication des résultats obtenus La projection aléatoire fait par exemple usage d'une matrice aléatoire afin que les vecteurs résultants soient simplement des collections de nombres qui n'ont aucune signification Si deux documents sont arrangés dans un groupe, la seule chose que nous pouvons dire est que leurs vecteurs correspondants sont semblables: il n'y a aucune conclusion concernant leur contenu Les Cartes de catégories de mots peuvent être utiles dans ce cas Cependant, les vecteurs résultants ont encore beaucoup de dimensions En outre, le contexte n'est pas suffisant pour grouper correctement des mots qui ont le même sens Bien que la pleine représentation soit utilisée largement, c'est une méthode de base pour la représentation du document Les vecteurs de mots ou stems représentent des documents, donc le nombre de dimensions peut être très élevé Cette méthode n'est pas utilisable quand la collection de documents est volumineuse Bien que les résultats obtenus par les méthodes précédentes soient encourageantes, ils ont des limitations qui ne peuvent pas être dépassées, surtout dans le domaine médical où les documents multilingues sont abondants Nous avons également examiné certaines directions d’indexation multilingue pour lesquelles plusieurs méthodes sont proposées Il y a des techniques qui se basent directement sur des corpus de documents Bien que les techniques nous permettent d’appliquer un processus d’indexation automatique partir des corpus, beaucoup de calcul est nécessaire et les résultats ne sont pas interprétables (voir [29]) On peut 46 aussi traduire des textes multilingues dans une langue intermédiaire pour une indexation monolingue Cependant, cela dépend strictement de systèmes de traduction automatique qui ont leurs propres contraintes (voir [29]) Pour cette raison, nous utilisons une méthode de représentation de documents basée sur l’ontologie c.à.d sur des thésaurus multilingues Comme indiqué dans section III du chapitre 2, l'ontologie doit être construite d’abord Quand une ontologie est disponible, les documents sont indexés pour être représentés par des vecteurs Dans notre cas, une ontologie du domaine cardio-vasculaire a été développée dans le cadre du projet NOESIS Cette ontologie est basée sur le thésaurus Subject Headings) [25] avec l’enrichissement du vocabulaire MeSH (Medical au travers du metathésaurus d'UMLS (Unified Medical Language System)[26] L'ontologie va être encore enrichie par le vocabulaire extrait d’articles dans le domaine cardio-vasculaire Ce travail est décrit dans [30] Une ontologie comprend plusieurs concepts Chaque concept peut être désigné par plusieurs termes Pour l'indexation de documents, les étapes nécessaires sont l’extraction de termes et la traduction de concepts Pour un document concret, les termes sont extraits Un terme peut être un mot ou une expression (qui ont une signification limitée) Une liste de termes avec leur fréquence est produite pour chaque document Un concept peut être dénoté par plusieurs termes afin que sa fréquence dans un document soit calculée comme la somme totale des fréquences des termes qui le dénotent de ses dénotant termes dans le document Donc, un concept a sa propre fréquence dans un document Comme l’ontologie a été construite avant l’indexation de documents, il y a des concepts de l’ontologie qui n’apparaissent dans aucun document de la collection Pour cette raison, seulement les concepts qui ont été utilisés une fois au moins pour indexer la collection sont inclus dans le dictionnaire de la collection Basés sur ce dictionnaire, les vecteurs de caractéristiques sont construits pour les documents Dans les expériences que nous avons réalisées, nous avons testé l'usage d'une ontologie et comparés les résultats avec ceux produits par la pleine représentation Cela sera présenté dans prochaines sections Sources de documents Nous utilisons deux corpus dans nos expériences Le premier contient des articles scientifiques dans le domaine cardio-vasculaire et le second comprend des articles sur 47 le cancer du sein Le premier contient seulement des articles en anglais et peut être trouvé et téléchargé sur le site Web http://www.biomedcentral.com, le second inclut des textes en anglais et en français qui ont été téléchargés depuis plusieurs sources Le corpus sur les maladies cardio-vasculaires contient 430 documents groupés dans les sections suivantes : • • • • • • • Cardiovascular diabetology (41 documents) Cardiovascular ultrasound (44 documents) BMC cardiovascular disorders (94 documents) Current interventional cardiology reports (119 documents) Current controlled trials in cardiovascular medicine (120 documents) Thrombosis journal (25 documents) Nutrition journal (11 documents) Les sections pour les documents ont été choisies par les auteurs des articles la soumission et ont été examinées par les éditeurs du site web D'après la procédure de la soumission, la classification des documents dans les sections a été accomplie avec soin Nous avons choisi par conséquent ces sections comme groupes pre-définis de nos expériences Ces documents sont dans le format de fichier pdf Le nombre de mots dans chaque document va de 1,200 8,000 Le nombre moyen de mots est supérieur 4,100 Il peut y avoir de 15 pages pour un document Le corpus sur le cancer du sein contient 440 documents en anglais et 574 en français La collection contient des documents de type texte ou au format HTML Les sources de documents sont aussi très variées et il n'y a aucun groupe prédéfini Le corpus a été utilisé d’abord pour extraire des concepts pour construire une ontologie du cancer du sein Pour cette raison, il y a des documents de plusieurs types: définitions, information générale, événements courants, et articles scientifiques sur le cancer du sein La plupart des documents sont courts et le nombre moyen de mots dans chaque document est d’environ 1200 Prétraitement Les documents en pdf ou au format HTML doivent être convertis d’abord au format texte L'indexation du document est alors réalisée afin que les vecteurs de concepts 48 représentent des documents CF-IDF est utilisé pour mesurer l'importance de concepts dans les documents Les vecteurs résultants doivent être normalisés pour devenir des entrées pour la SOM Convertir des documents pdf au format texte peut conserver le texte original naturellement Cependant, il peut y avoir des erreurs lors de la conversion dans certains cas Ces erreurs dépendent du module de conversion utilisé Tout d’abord, dans un article, les mots longs peuvent être tronqués la fin d'une ligne Par exemple, "international" est un mot long Il peut être récrit comme "inter-national" afin que "inter-" soit la fin d'une ligne alors que le mot "national" est au début de la ligne suivante Quand le texte est converti, ce mot sera transformé en deux mots distincts Cela se passe très fréquemment dans les documents pdf et plusieurs termes peuvent ne pas être comptés En conséquence, le processus d'indexation n'est pas effectué correctement De plus, un document peut contenir plusieurs colonnes En convertissant un document, les colonnes dans le document résultant (au format texte) peuvent ne pas paraître dans le bon ordre Comme un terme peut contenir plusieurs mots s’étendant sur deux colonnes il peut arriver que l'ordre des mots dans le terme ne soit pas maintenu Une autre cause possible d'erreur est que pendant la conversion, les mots qui paraissent dans l'en-tête, le pied de page ou une légende, sont insérés entre les mots d'un terme et le terme n’apparaîtra pas dans le document résultant Il est important de noter que les erreurs pendant la conversion ont un impact négatif sur la qualité de l'indexation Les documents du texte sont alors indexés pour obtenir une liste de concepts et leurs fréquences d’occurrence Une liste des concepts qui paraissent dans la collection du document est produite L'ordre des concepts dans cette liste est le même que l'ordre de concepts dans les vecteurs du document Nous appelons cette liste un dictionnaire En construisant le vecteur du document pour un document, nous considérons chaque concept et vérifions si le concept apparaît dans le document Si c’est le cas, la fréquence du concept dans le document est utilisée pour mettre jour le vecteur du document Cependant, il peut y avoir quelques concepts qui apparaissent dans tous les documents de la collection et ils ne sont pas utiles pour le regroupement des documents Ces concepts sont exclus du dictionnaire avant de construire des vecteurs du document Nous utilisons alors la méthode CF-IDF pour représenter l’importance d’un concept dans un document L’élément sémantique dans ce cas est le concept 49 Ensuite, les vecteurs de documents doivent être normalisés afin que la ressemblance entre deux vecteurs du document soit mesurée par le cosinus de l'angle des deux vecteurs dans l'espace des données Dans nos expériences, la pleine représentation est aussi implémentée afin qu'au lieu d'un dictionnaire de concepts, nous ayons un dictionnaire de stems Cette méthode sera comparée la méthode basée sur l’ontologie Cependant, seulement la dernière est utilisée pour indexer le deuxième corpus concernant le cancer du sein parce que les documents sont dans deux langues Après la tâche du prétraitement, nous avons pour chaque méthode de représentation de documents, un ensemble d'entrées qui sont des vecteurs normalisés du document Les entrées seront utilisées dans le processus de la formation de la SOM 50 Chapitre 4: Evaluation I Résultats Pour le corpus sur les maladies cardio-vasculaires, avec groupes prédéfinis de documents, nous avons utilisé une carte 7x7 du carré, c.-à-d 49 groupes possibles sur la SOM La pré-classification de documents dans groupes a été faite manuellement Nous comparerons les groupes obtenus par la SOM ces groupes prédéfinis Supposons que nous avons des documents de plusieurs des groupes prédéfinis qui tombent dans un groupe de la SOM Nous pouvons alors dire que le sujet principal de ce groupe est cela du groupe prédéfini qui a le plus de documents dans le groupe Par exemple, s'il y a documents sur les deux sujets "diabétologie Cardio-vasculaire" (4 documents) et "ultrason Cardio-vasculaire" (3 documents), alors le groupe est dit avoir le sujet "diabétologie Cardio-vasculaire." Nous pouvons dire qu'il y a documents touchés et documents manqués pour le groupe Dans [4], d'après Kohonen et ses collègues, tous les documents qui ont représenté un groupe de la minorité en tout point de la grille ont été comptés comme des erreurs de classification Dans nos expériences, les groupes sont des sections prédéfinies Nous avons la table de résultat suivante après les expériences avec l'ontologie Dans chaque cellule de la table, il y a les valeurs suivantes: • • Position de noeud sur la carte (x,y) Nombre total de documents-Nombre_de_touchés-Nombre_de_manqués(touchés-manqués) 51 (0,0): (0,1): (0,2): (0,3): (0,4): (0,5): (0,6): 43-23-20- 8-3-5-(- 28-10-18- 14-7-7-0 24-16-8-8 4-4-0-4 5-2-3-(- 2) (-8) (1,0): (1,1): (1,2): (1,3): (1,4): (1,5): (1,6): 4-3-1-2 5-3-2-1 3-2-1-1 18-5-13- 1-1-0-1 4-4-0-4 0-0-0-0 (2,5): (2,6): 1) (-8) (2,0): (2,1): (2,2): (2,3): (2,4): 29-23-6- 3-2-1-1 5-5-0-5 4-4-0-4 7-7-0-7 0-0-0-0 17 (3,0): 6-3-3-0 11-5-6-(1) (3,1): (3,2): (3,3): (3,4): (3,5): (3,6): 1-1-0-1 21-19-2- 8-6-2-4 0-0-0-0 10-8-2-6 3-2-1-1 17 (4,0): (4,1): (4,2): (4,3): (4,4): (4,5): (4,6): 26-9-17- 8-5-3-2 7-6-1-5 3-1-2-(- 14-7-7-0 2-2-0-2 3-2-1-1 (-8) 1) (5,0): (5,1): (5,2): (5,3): (5,4): (5,5): (5,6): 20-8-12- 2-1-1-0 2-1-1-0 8-5-3-2 12-7-5-2 0-0-0-0 11-6-5-1 (6,0): (6,1): (6,2): (6,3): (6,4): (6,5): (6,6): 5-2-3-(- 1-1-0-1 8-4-4-0 0-0-0-0 14-7-7-0 8-5-3-2 7-2-5-(- (-4) 1) 3) Tableau 1: La carte obtenue avec l’ontologie On a la somme totale de (Touchés-Manqués)=68 Pour les expériences avec la pleine représentation, (0,0): (0,1): (0,2): (0,3): (0,4): (0,5): (0,6): 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 (1,0): (1,1): (1,2): (1,3): (1,4): (1,5): (1,6): 0-0-0-0 1-1-0-1 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 0-0-0-0 (2,0): (2,1): (2,2): (2,3): (2,4): (2,5): (2,6): 0-0-0-0 16-8-8-0 10-5-5-0 13-7-6-1 10-6-4-2 0-0-0-0 0-0-0-0 (3,0): (3,1): (3,2): (3,3): (3,4): (3,5): (3,6): 34-18-16- 5-3-2-1 9-4-5-(- 8-4-4-0 8-4-4-0 0-0-0-0 0-0-0-0 1) 52 (4,0): (4,1): (4,2): (4,3): (4,4): (4,5): (4,6): 27-7-20- 9-5-4-1 27-14-13- 14-5-9-(- 16-6-10- 0-0-0-0 0-0-0-0 4) (-4) (-13) (5,0): (5,1): (5,2): (5,3): (5,4): (5,5): (5,6): 20-11-9-2 12-7-5-2 6-3-3-0 5-5-0-5 18-12-6-6 4-2-2-0 0-0-0-0 (6,0): (6,1): (6,2): (6,3): (6,4): (6,5): (6,6): 58-23-35- 12-6-6-0 23-13-10- 26-14-12- 38-20-18- 0-0-0-0 0-0-0-0 2 (-12) Tableau 2: La carte obtenue avec la pleine représentation En utilisant la même méthode d’évaluation, on a la somme totale de (Touchés- Manqués)= -3 Ce résultat est nettement inférieur celui produit par utilisation de l'ontologie Cela veut dire qu’en utilisant une ontologie pour représenter des documents, nous pouvons obtenir des groupes qui séparent la collection du document Du point de vue du temps de traitement, le nombre de dimensions du vecteur pour la pleine représentation est 25762 et le traitement a pris plusieurs jours Avec la méthode basée sur l’ontologie, le nombre de dimensions du vecteur est 4315; le processus d’apprentissage a été complété en quelques heures De plus, la SOM essaie de minimiser la fonction objective suivante: N G F = ∑∑ d i − c k i =1 k =1 Plus la valeur de F est petite, mieux la SOM peut grouper des entrées Dans nos expériences, cette valeur avec la pleine représentation est 545.19 tandis qu'avec l’ontologie c'est 508.57 Cela indique de meilleurs résultats avec l'usage de méthode de la représentation du document basée sur l’ontologie : en utilisant une ontologie, les coordonnées des centres sont mieux distribuées dans l'espace des données Pour le deuxième corpus, qui concerne le cancer du sein, c'est plus difficile d'évaluer les résultats parce qu’il sont dans deux langues et aucun groupe de documents prédéfinis n'est disponible Par contraste avec le corpus sur les maladies cardiovasculaires qui contiennent des articles scientifiques et sont très spécifiques, ce 53 deuxième corpus contient de l’information générale au sujet du cancer du sein ainsi que de la connaissance spécialisée Ce que nous attendons en regroupant ce corpus est d’examiner la possibilité de représenter des documents bilingues par les concepts d'une ontologie Nous avons pris deux documents du corpus, un en anglais, et l'autre en français Leurs titres sont semblables: “What Are the Risk Factors for Breast Cancer?" et "Généralités et facteurs de risque" Cependant, ils sont mis dans deux groupes différents Le premier, sur les facteurs de risque de cancer du sein pour les femmes est assez général et synthétique Le second est plus spécifique et concerne une seule recherche Nous avons examiné deux autres documents, qui sont groupés dans un même groupe: “Does Weight Gain Increase Breast Cancer Risk?" et "Cancer et hormones: de l’espoir la menace?" Étonnamment, le document anglais mentionne «la thérapie de l'hormone ménopausique" comme une méthode de traitement et le document français confirme qu'utiliser l'hormone peut traiter le cancer du sein Cependant, un document en français intitulé "Dix kilos perdus et le risque de cancer du sein diminuerait” n'est pas mis dans ce groupe bien que ce document mentionne la relation entre le poids du corps et le cancer du sein comme le document anglais Ce document est reécrit en français partir du document original "Intentional Weight Loss of 20 Pounds or More Linked to Decreased Cancer Risk", écrit en anglais Ce n'est pas simplement une traduction d'anglais en français mais ces documents sont encore arrangés dans le même groupe parce que les deux expriment la même idée L'évaluation dans le regroupement de texte en général est un problème notoire Évaluer la performance de la méthode dans l’expérience avec l'ontologie sur le cancer du sein est plus difficile Cependant, en exploitant manuellement la carte obtenue, nous avons obtenu des résultats très encourageants II Conclusion Par rapport autres méthodes de représentation du document, la méthode basée sur l’ontologie a les avantages suivants: • Produire des vecteurs caractéristiques de dimensionnalité faible Le nombre de dimensions de ces vecteurs est contrôlable Une ontologie est dépendante du domaine afin que tous les concepts qui apparaissent dans un document soient 54 extraits Pour cette raison, les concepts non apparentés ne sont pas considérés et cela réduit considérablement le nombre de dimensions du vecteur En revanche, un concept peut être représenté par beaucoup de termes afin que le nombre d’occurrences de ce concept puisse être élevé Pour quelques ontologies, basé sur les concepts, les vues sont construites (voir [18]) Une vue peut contenir plusieurs concepts qui sont apparentés • Etre une approche efficace pour grouper des documents multilingues Les termes sont dépendants de la langue mais les concepts en sont indépendants Pour cette raison, un document A en anglais peut être représenté par le même vecteur que le document B en français qui est une traduction de A Dans une langue, un concept peut aussi avoir beaucoup de termes qui le représentent Donc il est normal que le concept soit représenté par plusieurs termes dans plusieurs langues En utilisant des concepts, l'indexation du document ne doit pas être basé sur une langue particulière • Pouvoir fournir l'explication Quand deux vecteurs de documents sont arrangés dans un groupe, ils doivent être très semblables et donc partager beaucoup de concepts qu’il est possible de lister Ceci est contraire la projection aléatoire par exemple : quand la projection aléatoire est appliquée, il est difficile de savoir pourquoi les documents sont considérés comme semblables Il y a aussi des inconvénients pour la méthode basée sur l’ontologie Tout d’abord, il est difficile de construire et maintenir une ontologie, surtout quand de nouveaux concepts et de nouveaux termes apparaissent constamment dans les domaines spécialisés Quelques termes peuvent aussi être ambigus et dénoter plusieurs concepts De plus, utiliser une ontologie pour l'indexation des documents n'est pas une tâche facile Dans nos expériences, les termes sont extraits et ensuite affectés leurs concepts correspondants Dans plusieurs cas, un terme plus long inclut un autre plus court Quand un tel cas se produit, nous extrayons le premier et ignorons le second 55 Références [1] Kohonen, T (1982) Self-organized formation of topologically correct feature maps Biological Cybernetics, 43:59-69 [2] Kaski, S., Oja, M., Kohonen, T, Bibliography of Self-Organizing Map (SOM) Papers: 1998-2001 Addendum (2002) [3] Timo Honkela, Samuel Kaski, Krista Lagus and Teuvo Kohonen: WEBSOM - SelfOrganizing Maps of Document Collections Proceedings of WSOM'97, Workshop on Self-Organizing Maps, Espoo, Finland, June 4-6 Helsinki University of Technology, Neural Networks Research Centre, 1997 [4] Teuvo Kohonen, Samuel Kaski, Krista Lagus, Jarkko Salojarvi, Jukka Honkela, Vesa Paatero and Antti Saarela, Self organization of a massive document collection IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL 11, NO.3, May 2000 [5] Ahmad, K., Vrusias, B L., and Ledford, A (2001) Choosing feature sets for training and testing selforganising maps: A case study Neural Computating & Applications, 10(1):56 66 [6] A Rauber, and D Merkl Automatic Labeling of Self-Organizing Maps for Information Retrieval In Journal of Systems Research and Information Systems (JSRIS), 10(10):23–45 December 2001 [7] A Ultsch,: Maps for the Visualization of high-dimensional Data Spaces , in Proc Workshop on Self organizing Maps, pp 225 - 230, Kyushu, Japan, 2003 [8] B Fritzke, Let it grow - self-organizing feature maps with problem dependent cell structure, In Kohonen T et al (eds.), Artificial Neural Networks, Vol 1, North-Holland, 1991 56 [9] J Blackmore and R Miikkulainen, Incremental grid growing: Encoding highdimensional structure into a two-dimensional feature map, In Proc IEEE Int’l Conf on Neural Networks (ICNN’93), San Francisco, CA, 1993 [10] Dieter Merkl, Exploration of Text Collections with Hierarchical Feature Maps, in Research and Development in Information Retrieval, 186-195, 1997 [11] M Dittenbach, and A Rauber, and D Merkl: Recent Advances with the Growing Hierarchical Self-Organizing Map Allinson, N and Yin, H and Allinson, L and Slack, J (eds.) Advances in Self-Organizing Maps: Proceedings of the 3rd Workshop on Self-Organizing Maps June 13-15 2001, Lincoln, England, Springer, 2001 [12] G Salton, A Wong, and C S Yang 1975 A vector space model for automatic indexing Communications of the ACM, 18(11): 613–620 [13] Deerwester S, Dumais S, Furnas G, Landauer K Indexing by latent semantic analysis J Am Soc Inform Sci, 1990; 41: 391-407 [14] Honkela T., Pulkki V and Kohonen T., Contextual Relation of Words in Grimm Tales, Analyzed by Self-oranizing Map, Proceedings of International Conference on Artificial Neural Networks, ICANN-95, Ec2 et Cie, Paris, pp 3-7, 1995 [15] Timo Honkela, Samuel Kaski, Krista Lagus and Teuvo Kohonen Newsgroup Exploration with WEBSOM Method and Browsing Interface [16] S.Kaski Dimensionality Reduction by Random Mapping In Proc of the International Joint Conference on Neural Networks, pages 413–418, Anchorage, Alaska, May 1999 [17] T R Gruber A translation approach to portable ontologies Knowledge Acquisition, 5(2):199-220, 1993 [18] Hotho, A., Maedche, A., & Staab, S (2001) Ontology-based text clustering In Proceedings of the IJCAI-2001 Workshop "Text Learning: Beyond Supervision", August, Seattle, USA 57 [19] Smirnov A., Pashkin M., Chilov N., Levashova T., Krizhanovsky A., Kashevnik A 2005 Ontology-Based Users and Requests Clustering in Customer Service Management System In: (Gorodetsky, V., Liu, J., Skormin, V., eds.) Autonomous Intelligent Systems: Agents and Data Mining: International Workshop, AIS-ADM 2005 [20] Haiying Wang, Francisco Azuaje, Olivier Bodenreider An Ontology-Driven Clustering Method for Supporting Gene Expression Analysis, cbms, pp 389394, 18th IEEE Symposium on Computer-Based Medical Systems (CBMS'05), 2005 [21] Fabrizio Sebastiani, Consiglio Nazionale delle Ricerche, Italy, Machine Learning in Automated Text Categorization [22] Pavel Berkhin, Accrue Software, San Jose, CA, 2002, Survey Of Clustering Data Mining Techniques [23] Yong Wang, A Dissertation Submitted to the Faculty of Mississippi State University, Incorporating semantic and syntactic information into document representation for document clustering [24] Wen-Cheng Lin and Hsin-Hsi Chen, Department of Computer Science and Information Engineering, National Taiwan University Merging Mechanisms in Multilingual Information Retrieval [25] Medical Subject Heading Browser http://www.nlm.nih.gov/mesh/MBrowser.html [26] The Unified Medical Language System http://umlsks.nlm.nih.gov [27] Lagus, K (1997) Map of WSOM'97 abstracts alternative index In Proceedings of WSOM'97, Workshop on Self-Organizing Maps, Espoo, Finland, June 4-6, pages 368- 372 Helsinki University of Technology, Neural Networks Research Centre, Espoo, Finland [28] Honkela, T., Kaski, S, Lagus K, Kohonen T (1996), Exploration of full-text database with self-organizing maps In IEEE International Conference on Neural Networks-ICNN’96, p 56-61 58 [29] Douglas W Oard and Bonnie J Dorr University of Maryland, College Park A Survey of Multilingual Text Retrieval [30] Simonet M., Bernhard D., Diallo G., Gedzelman S (2005) Building an ontology of Cardio-Vascular diseases for Concept-Based Information Retrieval In: Computers in Cardiology, Lyon [...]... représentation de documents basée sur une ontologie En outre, les méthodes de représentation des résultats sur la carte discutées seront aussi limitées aux méthodes proposant des solutions sur les cartes obtenues par la SOM 8 III Méthodes de représentation de documents Les documents ne peuvent pas être interprétés directement par une méthode de regroupement À cause de cela, une procédure d'indexation qui fait... est extraite à partir [15] Figure 7: extraite à partir de [15] L'architecture de base de la méthode Websom de La carte documents construite des indexés à est partir documents par des catégories de mots générées par la carte de catégories de mots Les deux cartes sont produites avec l'algorithme SOM b Correspondance aléatoire Pour une grande collection de documents, la dimension des vecteurs de document... suivantes : 1 Étude de la carte auto organisatrice (la SOM) Il s’agit de comprendre le fonctionnement de l’algorithme et son application pour le regroupement de documents 2 Étude de certaines méthodes de représentation de documents et leur utilisation avec la SOM 3 Étude de l’application d une ontologie pour la représentation des documents Le processus de construction d ontologie n’est pas intégré à cette tâche... Étude de certaines méthodes de représentation de groupes de documents pour faciliter l’exploitation de la carte après le processus d’apprentissage Le but de 4 cette tâche est de visualiser les résultats sur la SOM 5 Implémentation d’un programme de regroupement de documents médicaux dont l’algorithme de regroupement est la SOM Deux méthodes de représentation de documents ont été implémentées dont une. .. meilleurs résultats Dans le cadre de mon stage, je me suis concentré sur les deux derniers aspects: la méthode de regroupement de documents et la méthode d’étiquetage des groupes de documents La SOM – une méthode de regroupement – est le centre de mon stage alors que la méthode d’étiquetage a pour but de faciliter la visualisation des résultats de la SOM Au niveau de l’implémentation, j’ai implémenté... représentent au mieux Deuxièmement, les résultats produits par la méthode de représentation de documents doivent être traités par une méthode de regroupement efficace pour distribuer les documents dans des groupes Troisièmement, il faut que les groupes de documents obtenus soient automatiquement étiquetés par des descriptions créées à partir des caractéristiques des documents appartenant à chaque groupe... figure est extraite de [28] d Méthode LabelSOM[6] C'est l 'une des recherches pionnières sur l'étiquetage des groupes sur la SOM Le but de cette méthode est d'extraire l'étiquette la plus descriptive pour le groupe de documents en se basant sur les caractéristiques communes des documents appartenant à un groupe Pour cela, la pleine représentation des documents employant le modèle de l'espace vectoriel... vecteur de document peut être multiplié avec une matrice aléatoire pour produire un autre vecteur de plus petite dimension Pour plus de détails, voir [16] 4 Méthodes d’indexation multilingue Il y a deux types de collection de documents multilingues [24] La première contient certaines collections de documents monolingues La deuxième contient des documents multilingues Une vue d’ensemble des méthodes d’indexation... d’étiquetage des résultats ont été proposés pour aider l’utilisateur à facilement exploiter l’ensemble des documents Les méthodes de représentation de documents abordées dans ce rapport sont celles qui ont été utilisées avec la SOM ou qui sont très courantes dans le domaine du regroupement de textes ou qui concernent l’indexation multilingue Une de ces méthodes sera comparée à la méthode de représentation de documents. .. III.2 de ce chapitre) est aussi une technique de ce genre Une limite de ces techniques est que le nombre de calculs mathématiques est grand 5 Ontologie pour la représentation de documents Il faut noter qu une ontologie peut être utilisée pour indexer des documents La définition d une ontologie et les détails de son utilisation seront donnés plus tard dans la section II du chapitre 3 IV Visualisation des