République Algérienne Démocratique et Populaire Ministère de l’Enseignement Supérieur et de la Recherche Scientifique Université des Sciences et de la Technologie - Mohamed Boudiaf - Oran Mémoire présenté en vue de l'obtention du diplôme de Magistère en Informatique Option : Reconnaissance des Formes et Intelligence Artificielle. Utilisation des Ressources Textuelles Semi-Structurées dans la Recherche Intelligente sur le Web. Présentée par : BOUHADIBA Mohamed el Amine. Composition du jury : Président Mohamed BENYETTOU Professeur USTO-MB Rapporteur Abdelkader BENYETTOU Professeur USTO-MB Examinateur Hafida BELBACHIR Professeur USTO-MB Examinateur Lynda ZAOUI Maître de conf."A" USTO-MB Invité Abderrezak BRAHMI Maître de conf."B" Univ. Mostaganem Année universitaire 2014-2015 Remerciements C’est un grand plaisir pour moi de remercier toutes les personnes qui ont permis à ce travail d’être ce qu’il est. Je remercie tout d’abord mon professeur BENYETTOU Abdelkader de m’avoir encadré durant ce projet de magistère. Il a su me transmettre sa passion pour le domaine de la Recherche d’Information et je lui en suis profondément reconnaissant. Je tiens ensuite à remercier Dr BRAHMI Abderrezak d’avoir accepté de codiriger mon travail de recherche. Sa patience et ses nombreuses remarques très pertinentes m’ont été des plus précieuses durant ce travail. J’exprime ma gratitude et mes sincères remerciements aux honorables membres du jury, en l’occurrence, au Pr. Benyettou Mohamed d’avoir accepté de présider mon jury ainsi qu’au Pr. Hafida Belbachir et au Dr Lynda Zaoui pour avoir pris le soin d’examiner mon travail. Je remercie les membres du laboratoire SIMPA, en particulier Mr. NEGGAZ Nabil et Mr. BENDAHMANE Abderrahmane, pour leurs conseils et leurs soutiens. Résumé La forte augmentation des documents textuels disponibles sur internet a créé un besoin urgent dans la précision des systèmes de recherche d’informations (SRIs). Toutefois, la représentation en Sac de Mots (BOW) utilisée dans ces SRIs traditionnels, qui ne présente que la fréquence des termes dans les documents, est souvent insatisfaisante. Ce modèle ignore les relations sémantiques entre les termes importants qui ne co-produisent pas littéralement. Par ailleurs, les ressources textuelles semi-structurées telles que Wikipedia intègrent une conceptualisation assez intéressante qui peut être exploitée pour des constructions sémantiques assimilées. Notre travail vise à remédier aux insuffisances du modèle classique BOW en intégrant la connaissance externe provenant de Wikipedia dans un noyau sémantique. Il s’agit de construire automatiquement un thésaurus de concepts pour enrichir la représentation des documents. Les résultats expérimentaux sur plusieurs ensembles de données montrent une amélioration significative des performances de la recherche d’information ad-hoc. Mots clés : Recherche d’information, Indexation sémantique, Wikipedia, Noyau sémantique. Abstract The sharp increase in textual documents available on the Internet has created an urgent need in the precision of information retrieval systems (IRS). However, the bag of words representation (BOW) used in these traditional IRS, which presents only the frequency of terms in the documents, is often unsatisfactory. This models ignores the semantic relationships between the important terms that do not co-occur literally. Otherewise, the semi- structured textual resources such as Wikipedia incorporate an interesting conceptualization that can be exploited for assimilated semantic constructions. Our work aims to address the shortcomings of traditional BOW model by integrating external knowledge from Wikipedia into a semantic core. This is automatically build a concepts thesaurus to enhance the representation of documents. Experimental results on several sets of data show a significant improvement in the performance of ad-hoc information retrieval. Table des matières Introduction générale……………………………………………...……………………….1 1. Contexte et problématique……………………………………………………………..1 2. Objectifs et contributions………………………………………………………………3 3. Organisation du mémoire…..…………………………………………………………..4 Chapitre 1 : Etat de l’art sur la Recherche d’Information…...………….5 1.1. Introduction………………………………………………………..…………………..6 1.2. Le processus de la Recherche d’Information : Processus en U……………………….7 1.2.1. Requête en RI………………………………………….……………….………….8 1.2.2. Représentation des résultats de requêtes………………………………..…………9 1.2.3. Le processus d’indexation…………………………….…………………….……10 1.2.3.1. L’analyse lexicale…………………………………………………….……...11 1.2.3.2. L’élimination des mots vides…………………………………………..……11 1.2.3.3. La lemmatisation……………………………………..……………………...12 1.2.3.4. La pondération des termes…………………………………….…………….13 1.2.4. L’appariement document-requête…………………….………………………….14 1.2.5. La reformulation de la requête……………………….……………….………….15 1.2.6. Propriétés du processus en U…………………………….………………………16 1.3. Les différents modèles de la Recherche d’Information……………………….……..16 1.3.1. Le modèle booléen…………………………………….……………….………...17 1.3.2. Le modèle vectoriel……………………………………………….…….…….….18 1.3.3. Le modèle probabiliste.…...……………………………………….…….…….…20 1.4. Evaluation des Systèmes de Recherche d’Information…………………….………...21 1.4.1. Protocole d’évaluation des systèmes de recherches d’information……………....22 1.4.2. Corpus de test (Collection de tests)……………………………………….……...23 1.4.3. Rappel et précision…………………………………………………….………....25 1.5. Conclusion…………………………………………………………………………...30 Chapitre 2 : Indexation sémantique en RI.…………………..…………..31 2.1. Introduction…………………….…………………………………………………….32 2.2. L’indexation sémantique : apports et difficultés…………………….……………….33 2.3. Les différentes ressources sémantiques et leurs utilisations en indexation…………..37 2.3.1. Le thésaurus……………………………………………………………….……..37 2.3.2. La base lexicale ou réseau sémantique WordNet…………………………….….38 2.3.3. Ontologies…………………………………………..…….……..……………….39 2.4. Les systèmes de recherche d’information utilisant une ressource sémantique..…..…40 2.4.1. Les travaux de Guarino N. : le système OntoSeek………………….………….40 2.4.2. Les travaux de Khan L.………………………………………………….….….41 2. 4.3. Les travaux de Baziz M.……………………………………...………………..42 2.4.4. Les travaux de Radhouani S.…………………………….……………………..43 2.4.5. Les travaux de Boubekeur F.………………………………….………………..44 2.4.5. Les travaux de Maisonnasse L..………………………….…………………….46 2.4.6. comparaison.………………………………………………………….….…….46 2.5. Les systèmes d’indexation sémantique sans ressource externe……………………...47 2.5.1. Le Model Vectoriel Généralisé GVSM …………………………………..…...48 2.5.1. Latent Semantic Indexing LSI ……………………………...……………..…...50 2.6. Conclusion…………………………………………………………………………...53 Chapitre 3 : Construction d’un noyau sémantique pour la Recherche d’information en utilisant Wikipedia ……………………………………55 3.1. Introduction...……………………….………………………………………………..56 3.2. Wikipedia………………………………………….…………………………………57 3.2.1. Wikipedia comme thesaurus……………………….…...……….……………….58 3.2.1.1. Synonymie…………………………………………………….……………..58 3.2.1.2. Polysémie………………………………………….………….……………...59 3.2.1.3. Hyponymie (relations hiérarchiques)……………….………….…………….59 3.2.1.4. Relation Associative……………………………………………….………...59 3.3. Similarité de la relation associative entre les articles de Wikipedia………………...60 3.4. La représentation des documents avec des Concepts et noyau sémantique issus de Wikipedia………………………………………………………………………...62 3.4.1. Méthodes à noyau de la recherche d’information….……………….……………63 3.4.2. Noyaux sémantique dérivé Wikipedia.…………………………………………..65 3.5. Conclusion……………...……………………………………………………………70 Chapitre 4 : Expérimentations et évaluations…………………………...71 4.1. Introduction………………………………………………………...………….…….72 4.2. Méthodologie …………………………………………………………………….….72 4.2.1. Environnement………...……..…………………………………………….…….72 4.2.2. Architecture générale.....……………..…………………………………….…….73 4.3. La collection du test…………………………………………………………….……75 4.4. La ressource externe : Wikipedia……………………………………………….……77 4.4.1. Description du corpus………….………………………………………………...78 4.4.1.1. Les Collections Principales…………………….……..……………………...78 4.4.1.2. Les Catégories………….. ………..………………………….……………...81 4.4.2. Filtrage des concepts de Wikipedia……….……………………………………..82 4.5. Prétraitement linguiste…..…………………………………………………………...83 4.6. Expérimentation……………………………………………………….……………..85 4.6.1. Prétraitement..…………………...………………….…………….……………..86 4.6.2. Indextation……………………………………….……………….……………..86 4.6.3. appariement et mesure de pertinence ……………...……………….……….…..87 4.6.4. Discussion……………………...……………………...………….……………..90 4.7. Conclusion ……………..……………………………………………………………90 5. Conclusion général et perspective……………...………………………………………91 Bibliographie……………………………………………...………………..92 Table des figures Figure 1.1. Processus en U de recherche d’information………………………………………8 Figure 1.2. Appariement document-requête……………………………….…………………15 Figure 1.3. Représentation vectorielle de deux documents ( et ) et d’une requête (q) (cid:1) (cid:1) (cid:2) (cid:3) dans un espace compose de trois termes ( , , )………………….………………………19 (cid:4) (cid:4) (cid:4) (cid:2) (cid:3) (cid:5) Figure 1.4. Bruit et Silence………………………………………….……………………….26 Figure 1.5. Précision aux 11 points standards de rappel ……………..………………….….29 Figure 2.1. Le thésaurus utilisé pour l’indexation de l’exemple…………………………….35 Figure 2.2. Matrices des minterms et des composantes orthogonales de (cid:3)(cid:7)……………….48 (cid:6) Figure 2.3. Matrices des relations termes-documents………………………………………51 Figure 2.4. Réduction informationnelle par l’algorithme SVD……………………………...51 Figure 2.5. Représentation d'un espace vectoriel classique (1) et d'un espace réduit LSI (2).53 Figure 3.1. Un fragment de la taxonomie de Wikipedia……………………………………..60 Figure 3.2. Les catégories des liens sortants des concepts “Machine Learning”, “Data Mining” et “Computer Network”……………………………………………………………..62 Figure 3.3. Le processus de l’indexation sémantique en utilisant Wikipedia ……………….69 Figure 4.1. Architecture générale…………………………………………………………….74 Figure 4.2. Exemple d’un fichier dans la base ADI…………………………………….……76 Figure 4.3. Exemple d’une requête dans la base ADI………………………………….…….77 Figure 4.4. (A) Exemple de wiki. (B) Transformation XML pour l'article Anarchism (12.xml) ………………………………………….……………………………………………….…….80 Figure 4.5. Les courbes précision rappel pour les tests sur les bases MED(A), CF(B), CACM(C) repectivement ……………………………………………...…………..…………89 Table des tableaux Tableau 1.1. Quelques collections de documents de test en RI………………………..……24 Tableau 1.2. Liste des documents restitués par un SRI pour la requête Q………..…………28 Tableau 2.1. Les représentations de quatre documents dans le modèle vectoriel…………....34 Tableau 2.2. Les représentations par les concepts des quatre documents dans le modèle vectoriel ……………………………………………………………………………………....35 Tableau 2.3. Similarité entre documents selon la stratégie d’indexation…….......................36 Tableau 2.4. Les statistiques sur le nombre des mots et de concepts dans WordNet 3.0…...39 Tableau 2.5. Récapitulatif de quelques travaux de la recherche sémantique ………………..47 Tableau 3.1. Exemple de vecteurs de termes de documents…………………………………63 Tableau 3.2. Exemple d’une matrice de proximité………………………………………….65 Tableau 3.3. Exemple de vecteurs de termes « enrichi »…………………………………….65 Tableau 3.4. Vecteur de termes BOW traditionnel…………………………………………..66 Tableau 3.5. Vecteur des concepts candidats et des termes………………………………….67 Tableau 3.6. Matrice de Proximité…………………………………………………………...68 Tableau 4.1. Statistiques générales sur les collections principales…………………………..78 Tableau 4.2. Les statistiques sur la structure des documents des collections principales…...79 Tableau 4.3. Statistiques sur les catégories des principales collections……………………..81 Tableau 4.4. Racines obtenues par l’algorithme de Porter ………………………………….85 Tableau 4.5. Résultats de la recherche ad-hoc dans trois corpus …………………………....87 Introduction Générale Introduction générale 1. Contexte et problématique De nos jours on assiste à un développement incessant des technologies de l’information. Ces nouvelles technologies ont permis l’évolution rapide des techniques et des matériels de production et de gestion de l’information. Le progrès des outils de production d’information tels que les éditeurs de textes a permis la production quotidienne d’une énorme masse d’information. L’évolution des médias électroniques a permis le stockage de cette vaste quantité d’information. Cette augmentation rapide du volume d’information a engendré le problème de « comment retrouver une information qui nous intéresse dans cette grande masse d’information ? ». Afin de traiter ce problème une discipline toute entière est née. Cette discipline est appelée Recherche d’Information (RI). Elle s’intéresse au développement des techniques et des outils qui permettent de retrouver une information intéressante afin de satisfaire un besoin en information, dite information pertinente. Ces outils sont appelés des Systèmes de Recherche d’Information (SRI). Ainsi, un SRI permet de sélectionner parmi un volume d’information, les informations pertinentes vis-à-vis d’un besoin en information. Dans ce système, le besoin en information est exprimé sous forme de requête. Dans un SRI, chaque document est représenté selon un formalisme intermédiaire. Cette représentation est directement exploitée par le SRI. Elle décrit le contenu du document par des descripteurs. Ces descripteurs sont des unités significatives dans le document. Cette description est appelée l’indexation du document. De la même manière le contenu de la requête est décrit par un ensemble de descripteurs. Pour retrouver les documents pertinents vis-à-vis d’une requête, le SRI compare la représentation de cette requête à la représentation de chaque document. Cette comparaison est réalisée au moyen d’une fonction de correspondance (Retrieval Status Value: RSV) et un score de pertinence est affecté à chaque document. Ces scores permettent de présenter à l’utilisateur les documents pertinents dans un ordre de pertinence. Le processus de recherche est donc composé de deux processus : une phase d’indexation et une phase de mise en correspondance. L’indexation permet de décrire un document par un ensemble de descripteurs. Cette indexation est issue des Traitements Automatiques de la Langue Naturelle (TALN). Elle 1 Introduction Générale constitue un compromis entre la performance et la faisabilité. En effet une indexation manuelle est plus efficace qu’une indexation automatique, mais cette indexation n’est pas toujours possible surtout quand il s’agit des corpus volumineux. Dans le cas où l’indexation automatique est guidée par l’utilisateur, on parle de l’indexation semi-automatique ou supervisée. Les SRIs classiques, considèrent les documents comme des ensembles de mots, appelés sac de mots. Ces mots sont utilisés dans ces SRIs pour décrire le contenu d’un document. Ainsi, ces SRIs considèrent les mots comme des graphies sans sens. De ce fait, ils permettent de retrouver seulement des documents qui sont décrit par les mêmes mots que la requête. Par exemple, un document indexé par un mot synonyme d’un autre mot qui décrit la requête ne sera jamais renvoyé par ces SRIs, malgré que ce document soit pertinent. Afin de remédier à ces limites il est devenu indispensable de prendre en considération le sens du mot. Les descripteurs sont alors les sens des mots : les concepts. Ce type d’indexation est appelé indexation conceptuelle ou sémantique. L’indexation sémantique caractérise le contenu du document par des descripteurs sémantiques. Elle permet d’améliorer la performance des systèmes de recherche d’information. Néanmoins, l’obtention et l’exploitation du support sémantique présente une réelle difficulté. Les approches d’indexation sémantique peuvent être classées selon deux grandes approches : la première consiste à reproduire, par une analyse interne et autonome, une sémantique latente à travers l’ensemble des documents de la collection. La deuxième approche fait recours à des ressources linguistiques externes pour exploiter les relations taxonomiques dans le processus d’indexation et de reformulation de la requête. WordNet représente une ressource type pour cette approche. Cependant, l’extension, vers de nouveaux concepts ou vers d’autres langues, n’est pas toujours évidente vu le coût élevé de construction manuelle. Par ailleurs, certaines ressources collaboratives telles que Wikipedia offre une conceptualisation à la fois évolutive et multilingue sur l’ensemble des sujets et des concepts traités. La faisabilité de cette alternative mérite d’être étudiée dans les tâches de recherche d’information intelligente exploitant la sémantique réelle échangée par le grand public de l’Internet. 2