Bellot Patrice
Équipe: Laboratoire d'Informatique d'Avignon
Courriel: patrice.bellot@lia.univ-avignon.fr
Contenu
Mots-clés: recherche documentaire, classification, segmentation, TREC, amaryllis, arbres de décision, nuées dynamiques, k-means, SIAC
Keywords: information retrieval, clustering, hierarchical classification, k-means, decision tree, TREC, amaryllis, SIAC
Résumé
Les systèmes de recherche documentaire employant des méthodes essentiellement statistiques permettent le traitement de requêtes en langage naturel sur des corpus hétérogènes de grande taille, indépendamment de la langue employée. Un système de recherche documentaire, calcule des indices de ressemblance entre la requête et chacun des documents de la collection cible. Suivant les valeurs de ces indices, une liste ordonnée de documents est fournie à l’utilisateur. Cette liste est souvent très longue : certains documents pertinents sont mal positionnés et de ce fait jamais explorés par les utilisateurs. Les sujets abordés dans les uns ou les autres de ces documents sont multiples et certains sont éloignés des thématiques recherchées par l’utilisateur soit parce que ces dernières ne sont pas clairement exprimées dans la requête soit parce que le système n’a pas su les prendre correctement en compte.
La classification thématique des documents rapportés est une manière de structurer l’ensemble des réponses. Elle permet à l’utilisateur d’orienter son exploration en fonction des thématiques générales des classes et d’accéder ainsi plus rapidement à ce qu’il recherche. Appliquée aux phrases ou aux paragraphes des documents, la classification permet de regrouper les extraits de textes traitant de la même thématique. Deux extraits d’un document traitent de thématiques différentes s’ils appartiennent à des classes distinctes. Autrement dit, la classification donne lieu à une segmentation thématique. À partir de cette segmentation, un nouveau calcul des indices de ressemblance est réalisé entre les segments et la requête aboutissant à une nouvelle liste solution. La segmentation permet de présenter à l’utilisateur les segments textuels jugés pertinents et de mieux positionner certains documents longs dans lesquels l’information recherchée ne constitue que l’une des thématiques abordée. Les éléments de cette nouvelle liste peuvent eux-mêmes être classés pour obtenir une segmentation de plus haut niveau et ainsi de suite. À chaque classification correspond une segmentation. À partir de toute segmentation, une classification peut être déduite. Cela démontre une dualité entre les problèmes de classification et de segmentation.
Le système de recherche documentaire SIAC a été construit pour évaluer les solutions proposées dans cette thèse. La manière dont est effectuée la recherche documentaire fournissant les listes de documents à classer et à segmenter est décrite dans un premier chapitre. Dans un second chapitre, une technique de classification employant un algorithme hiérarchique et une méthode de réallocation de type Nuées Dynamiques est présentée et évaluée par le biais de notre participation à la campagne TREC-7. Une nouvelle méthode de classification employant des arbres de décision non supervisés est finalement proposée et évaluée sur les corpus en langue française de la campagne Amaryllis. À partir de cette classification, un algorithme de segmentation est déduit. Il est détaillé et évalué dans le dernier chapitre de ce mémoire.
La classification thématique des documents rapportés est une manière de structurer l’ensemble des réponses. Elle permet à l’utilisateur d’orienter son exploration en fonction des thématiques générales des classes et d’accéder ainsi plus rapidement à ce qu’il recherche. Appliquée aux phrases ou aux paragraphes des documents, la classification permet de regrouper les extraits de textes traitant de la même thématique. Deux extraits d’un document traitent de thématiques différentes s’ils appartiennent à des classes distinctes. Autrement dit, la classification donne lieu à une segmentation thématique. À partir de cette segmentation, un nouveau calcul des indices de ressemblance est réalisé entre les segments et la requête aboutissant à une nouvelle liste solution. La segmentation permet de présenter à l’utilisateur les segments textuels jugés pertinents et de mieux positionner certains documents longs dans lesquels l’information recherchée ne constitue que l’une des thématiques abordée. Les éléments de cette nouvelle liste peuvent eux-mêmes être classés pour obtenir une segmentation de plus haut niveau et ainsi de suite. À chaque classification correspond une segmentation. À partir de toute segmentation, une classification peut être déduite. Cela démontre une dualité entre les problèmes de classification et de segmentation.
Le système de recherche documentaire SIAC a été construit pour évaluer les solutions proposées dans cette thèse. La manière dont est effectuée la recherche documentaire fournissant les listes de documents à classer et à segmenter est décrite dans un premier chapitre. Dans un second chapitre, une technique de classification employant un algorithme hiérarchique et une méthode de réallocation de type Nuées Dynamiques est présentée et évaluée par le biais de notre participation à la campagne TREC-7. Une nouvelle méthode de classification employant des arbres de décision non supervisés est finalement proposée et évaluée sur les corpus en langue française de la campagne Amaryllis. À partir de cette classification, un algorithme de segmentation est déduit. Il est détaillé et évalué dans le dernier chapitre de ce mémoire.
Abstract
Statistical information retrieval systems allow to process natural language queries (whatever the language) on large and heterogeneous corpora. IR software programs compute similarities between a user’s query and documents belonging to the target corpus. According to similarity values, a ranked list of documents is provided to the user. This answer list is often so long that users cannot explore all the documents retrieved. However, some of them are relevant but badly ranked and thus never recovered. The retrieved documents deal with several themes. A few of them are distant from the theme of the query either because the query is not clearly expressed or because the IR software was not able to recognize the theme.
Thematic classification of the retrieved documents may be a way to organize them. It helps users navigate in the list of documents according to the global themes of the clusters. Thus, users can obtain relevant documents faster. If the classification is applied to the paragraphs or to the sentences of the documents, it allows to group together any extracts (segments) dealing with the same theme. Two extracts from a document are about two different themes if they belong to two different clusters. Thus, classification leads to segmentation. From this segmentation, similarity values between query and segments can be computed. This computation allows to provide users with a new ranked list. Segmentation permits to propose the segments considered as relevant to users. It allows to better rank long documents in which the searched theme is one of the themes the documents deal with. The ranked segments may be clustered to obtain a less fine-grained segmentation and so on. Any segmentation is linked to a classification. From any segmentation, a classification can be performed.
The SIAC information retrieval system has been created to evaluate the methods described in this dissertation. In the first chapter, I describe the way SIAC computes the list of documents to be clustered and segmented. In the second chapter, a classification method combining hierarchical classification and a K-Means-like algorithm is presented. This method is evaluated over TREC-7 corpora and queries. In the third chapter, I propose a new classification method which relies on unsupervised decision trees. It is evaluated over the French corpora of the Amaryllis’99 campaign. The last chapter describes a segmentation algorithm using the classification method detailed in the third chapter. This segmentation method is evaluated over the Amaryllis’99 corpora.
Thematic classification of the retrieved documents may be a way to organize them. It helps users navigate in the list of documents according to the global themes of the clusters. Thus, users can obtain relevant documents faster. If the classification is applied to the paragraphs or to the sentences of the documents, it allows to group together any extracts (segments) dealing with the same theme. Two extracts from a document are about two different themes if they belong to two different clusters. Thus, classification leads to segmentation. From this segmentation, similarity values between query and segments can be computed. This computation allows to provide users with a new ranked list. Segmentation permits to propose the segments considered as relevant to users. It allows to better rank long documents in which the searched theme is one of the themes the documents deal with. The ranked segments may be clustered to obtain a less fine-grained segmentation and so on. Any segmentation is linked to a classification. From any segmentation, a classification can be performed.
The SIAC information retrieval system has been created to evaluate the methods described in this dissertation. In the first chapter, I describe the way SIAC computes the list of documents to be clustered and segmented. In the second chapter, a classification method combining hierarchical classification and a K-Means-like algorithm is presented. This method is evaluated over TREC-7 corpora and queries. In the third chapter, I propose a new classification method which relies on unsupervised decision trees. It is evaluated over the French corpora of the Amaryllis’99 campaign. The last chapter describes a segmentation algorithm using the classification method detailed in the third chapter. This segmentation method is evaluated over the Amaryllis’99 corpora.
Informations administratives
Jury
- M. Yves Chiaramella - rapporteur
- M. Christian Jacquemin - rapporteur
- M. Renato de Mori - examinateur
- M. Gregory Grefenstette - examinateur
- M. Jacques Le Maitre - examinateur
- M. Marc El-Bèze - directeur de thèse
Université: Université d'Avignon et des Pays de Vaucluse
Discipline: Informatique
Date de soutenance: 27 janvier 2000
Lieu de soutenance: IUP Génie Mathématiques et Informatique - Avignon