Classification et segmentation de textes par arbres de ...lia.univ-avignon.fr/fileadmin/documents/Users/Intranet/fich_art/... · en déduire une segmentation des textes. [YAA 97]

RECHERCHE

Classification et segmentation de textes pararbres de décision

Application à la recherche documentaire

Patrice Bellot — Marc El-Bèze

Laboratoire d’Informatique d’Avignon (LIA)339, ch. des Meinajaries, BP 122884911 Avignon Cedex 9{patrice.bellot,marc.elbeze}@lia.univ-avignon.fr

RÉSUMÉ. La plupart des moteurs de recherche documentaire renvoient en réponse à unerequête une liste ordonnée de documents. Cette liste étant souvent très longue, les utilisateursne peuvent pas examiner tous les documents proposés. De ce fait, il leur arrive de ne pasconsulter des documents pertinents mal positionnés. Après avoir décrit le système derecherche SIAC développé au LIA, nous présentons un algorithme de classificationthématique. Appliqué aux documents ramenés à partir d’une requête, il permet d’organiser laliste des réponses et d’améliorer la pertinence de la recherche. Une évaluation faite durant lacampagne Amaryllis’99 est présentée. À partir de la classification, une segmentationthématique des documents est réalisée. Elle permet d’effectuer une nouvelle recherche surdes zones documentaires plus fines que les documents et d’isoler l’information pertinente àl’intérieur d’un texte. On montre à cette occasion que l’utilisation combinée de mesures desimilarités améliore fortement les résultats de la recherche documentaire.

ABSTRACT. A classical information retrieval system retrieves and ranks documents accordingto distances between texts and a user query. The answer list is often so long that users cannotexamine all the documents retrieved whereas some relevant ones are badly ranked and thusnever examined. We describe an algorithm based on classification trees well-suited forclassifying the set of documents retrieved. This method is evaluated over the Amaryllis’99corpora and queries. We show that it improves the results of the retrieval. In a secondsection, a segmentation algorithm is described that uses the results of the classification tothematically segment the set of retrieved documents and to isolate relevant information.

MOTS-CLÉS : recherche documentaire, classification automatique, segmentation, arbres dedécision, évaluation Amaryllis.

KEY WORDS: information retrieval, clustering, hierarchical classification, classification trees,text decomposition, segmentation, structuring information.

Technique et science informatiques. Volume 20 – n° 1/2001, pages 107 à 134

108 Technique et science informatiques. Volume 20 – n° 1/2001

1. Introduction

Comme la plupart des systèmes de recherche documentaire, le logiciel SIAC(Segmentation et Indexation Automatiques de Corpus) développé au sein duLaboratoire d’Informatique d’Avignon (LIA), fournit en réponse à une requête uneliste de documents classés par ordre de probabilité de pertinence décroissante. Cetteliste est souvent difficilement exploitable à cause de sa longueur. L’utilisateur nepeut lire tous les documents qui lui sont proposés et ne peut ainsi récupérer certainsd’entre eux qui, mal classés, se retrouvent en fin de liste alors qu’ils sont pertinents.Dans cet article, après une présentation de SIAC et une évaluation du système surun corpus extrait de la campagne d’évaluation Amaryllis’99, deux algorithmes declassification et de segmentation employant des méthodes statistiques etprobabilistes sont présentés. La classification a pour but de regrouperthématiquement les textes rapportés par le système de recherche documentaire. Lasegmentation, quant à elle, sert à isoler les parties pertinentes des parties nonpertinentes des textes. L’utilisation de telles méthodes pour la recherchedocumentaire est relativement récente et peut être réalisée grâce notamment à ladisponibilité de corpus de taille importante et de jeux de requêtes, fournis durant lescampagnes d’évaluation Amaryllis et TREC, avec leurs référentiels (liste desdocuments pertinents à trouver). En ce qui concerne la classification automatiqueappliquée à la recherche documentaire, on distingue deux types d’utilisation. Lapremière est destinée à améliorer la rapidité de la recherche grâce à une pré-classification des textes du corpus cible et à guider l’utilisateur dans l’exploration decollections de documents. La seconde utilisation se propose d’organiser la liste desdocuments retrouvés par le système de recherche à partir d’une requête. C’est cettevoie que nous explorons aussi bien pour la classification que pour la segmentation.

1.1. Classification globale et classification locale

Dans une première partie, un algorithme de classification automatique est décrit.Il sert à classer de manière thématique les réponses données à partir d’une requête.L’application de techniques de classification pour la recherche documentaire peutêtre faite sur l’ensemble des documents du corpus (pré-classification ou globalclustering) ou seulement sur les documents trouvés en réponse à une requête (post-classification ou local clustering). La plupart des méthodes de classification ([HEA99], [SCH 97], [SIL 97] et [LOU 98]) utilisent des techniques statistiques prochesde celles employées par les moteurs de recherche pour évaluer la ressemblance d’untexte avec une requête (emploi de distances inter-documents, de classificationhiérarchique, etc.). Ces méthodes sont de type hiérarchique pour la plupart et ont defait des complexités en temps et en mémoire élevées. Ainsi, la plupart desexpériences réalisées à ce jour l’ont été soit avec peu de documents [MAA 94], soiten réduisant la taille des vecteurs représentant les documents [WEI 96] et [ANI 97].

Classification et segmentation 109

Des expériences utilisant une classification globale sans réduction de la taille desvecteurs sont toutefois décrites dans [SCH 97] où sont classés les 74 520 documentsde l’un des corpus de TREC-4 en 400 classes. Pour chacune des 50 requêtes deTREC-4, Schütze et Silverstein [SCH 97] ont construit une liste de documents àl’aide d’un logiciel de recherche. Ils ont ensuite effectué des nouvelles recherchessur chaque classe obtenue par une méthode hiérarchique, à partir des classes les plusproches des requêtes jusqu’aux plus éloignées, et construit ainsi, pour chaquerequête, une liste d’au plus mille documents. Parallèlement, ils ont réalisé, pourchacune des requêtes, une classification locale des mille documents trouvés dans lecorpus. Ces mille documents ont alors été classés avec l’algorithme employé pour laclassification globale. À l’issue de la classification locale, une nouvelle liste estcréée après sélection des meilleures classes qui peut être comparée à celle obtenue àpartir de la classification globale. [SCH 97] montre alors que la classification localeconduit à de meilleurs résultats que la classification globale. Ceci peut s’expliquerpar le fait que la classification locale est réalisée sur des ensembles de documentsdifférents pour chaque requête tandis que la classification globale est indépendantedes requêtes. Par contre, la classification globale, même si elle est coûteuse enressources et en temps machine, n’est effectuée qu’une seule fois et permet unerecherche plus rapide. Enfin, des méthodes de catégorisation permettent d’affecterles documents dans des classes thématiques prédéfinies [MOU 96] [BIG 2000].Cette dernière approche est différente de la notre puisque nous n’avons aucuneconnaissance a priori des thématiques possibles.

L’algorithme que nous décrivons et évaluons dans cet article (cf. section 3),utilise de manière originale des arbres de décision. Sa complexité est très inférieureà celle des méthodes hiérarchiques. Elle permet de classer toutes les phrases quicomposent les documents rapportés (ceci est utile en vue de la segmentation desdocuments décrite plus loin). Cette classification est entièrement automatique. Elleest à distinguer des méthodes globales qui proposent à l’utilisateur un certainnombre de classes plus ou moins figées pour orienter la recherche.

1.2. Segmentation automatique

La plupart des méthodes de segmentation sont destinées à la reconnaissance defrontières thématiques et à la création automatique de résumés. Elles n’ont passouvent été appliquées à la recherche documentaire. Grâce à une segmentation desdocuments rapportés, certains d’entre eux, pertinents mais mal positionnés, peuventêtre remontés en début de liste et ainsi récupérés plus facilement par l’utilisateur. Untel procédé permet d’augmenter la précision du système de recherche documentairesans diminuer le niveau global de rappel puisqu’il ne s’agit que de réordonner laliste des documents trouvés par le système et non d’en créer une nouvelle. Unesegmentation thématique peut également permettre d’isoler l’information pertinente


à l’intérieur d’un texte et de présenter à l’utilisateur seulement la partie du documentsusceptible de l’intéresser.

La plupart des algorithmes de segmentation représentant les textes selon lemodèle vectoriel font l’hypothèse que deux extraits de texte ayant une faiblesimilarité ont de faibles liens thématiques [SAL 91] Cette hypothèse est proche decelle formulée pour la recherche documentaire (qui stipule qu’un document estpertinent vis à vis d’une requête si leur similarité est grande). Suivant cettehypothèse, deux extraits peu similaires (au sens d’une mesure de similarité dont lavaleur est inférieure à un seuil) donnent lieu à une segmentation du document quiles contient. Une méthode de segmentation simple passe donc par le calcul dessimilarités des paragraphes adjacents. [KLA 98] analyse les répétitions de chaînesde mots à l’intérieur des textes pour trouver des frontières thématiques et aider à laconstitution de résumés automatiques.

Partant du constat que, lorsqu’un même concept est exprimé par des termesdifférents, la seule analyse de la répétition des termes n’est pas suffisante pourdétecter les marques de transition thématique, [KOZ 93] et [FER 98] proposent decalculer un coefficient de cohésion lexicale pour chaque zone de texte en fonctionde la ressemblance des mots présents. Cette cohésion entre termes est évaluéesuivant un réseau sémantique construit d’après les définitions des entrées d’undictionnaire. Elle correspond au calcul d’une similarité en fonction de la quantitéd’information de chacun des termes et de leur usage commun dans les textes àsegmenter. La cohésion d’une zone de texte dépend des cohésions de ses termes.Une segmentation thématique est réalisée en fonction des zones de faible cohésion.[KOZ 93] calcule des similarités entre mots en utilisant un réseau sémantique afinde déterminer les zones fortement informatives de celles qui le sont moins et ainsien déduire une segmentation des textes.

[YAA 97] réalise une segmentation grâce à l’utilisation d’un algorithme declassification hiérarchique. Tant qu’il reste des segments non classés, les deuxsegments adjacents les plus proches sont regroupés hiérarchiquement (au plus basniveau, les segments sont les paragraphes des textes). Les seules distances calculéespour construire cette hiérarchie sont les distances séparant un paragraphe de celuiqui le suit. Les frontières thématiques sont déduites de la hiérarchie suivant lesprofondeurs respectives des segments adjacents dans le texte.

La méthode Text-Tiling décrite dans [HEA 97] calcule des similarités entre blocsde textes dans une fenêtre, comme suggéré par [SAL 94] en étudiant la distributiondes termes selon plusieurs critères (notamment le nombre de mots communs et lenombre de mots nouveaux).

Dans cet article, une nouvelle méthode de segmentation des documents estprésentée (cf. section 4). Elle est déduite directement de l’algorithme declassification en fonction de l’appartenance des phrases des documents à telle outelle classe (exploration des classes obtenues). Elle est de complexité inférieure auxautres méthodes existantes et met en lumière la dualité existant entre classification


et segmentation. De manière à évaluer la méthode dans le cadre de son application àla recherche documentaire, une seconde recherche est effectuée sur les segmentsobtenus. Elle permet d’attribuer un nouveau score à chaque document.

2. Le système de recherche documentaire SIAC

2.1. Description

Afin de permettre l’accès aux immenses banques de données textuellesexistantes, les outils de recherche documentaire se doivent de respecter un certainnombre de critères : les meilleures performances possibles en termes de précision etde rappel, la capacité à traiter des domaines variés, la rapidité d’adaptation etl’indépendance vis-à-vis de la langue. C’est dans cette optique multiple que nousdéveloppons, au sein du LIA, le logiciel de Segmentation et d’IndexationAutomatiques de Corpus (SIAC).

Un processus de recherche documentaire en texte intégral se décompose en troisétapes principales :

- l’indexation des textes sur lesquels portent les interrogations ;- la recherche proprement dite à partir d’une requête de l’utilisateur ;- la présentation des résultats de la recherche.

Tout d’abord le système doit être capable d’indexer la base documentaire.Durant cette étape, le logiciel parcourt les textes du corpus afin d’en relever lestermes (mots, groupes de mots, etc.) les plus importants. Cela donne lieu à lacréation d’une liste de termes auxquels sont associés les documents les contenantainsi que leur poids dans chacun d’eux.

L’étape de recherche se fait à partir d’une requête exprimée en langage naturel(SIAC est indépendant de la langue utilisée). Il s’agit de mesurer, grâce auxinformations enregistrées dans l’index, la ressemblance entre chaque texte du corpuset la requête au moyen de distances ou de similarités telles les mesures Cosine ouOkapi que nous décrivons plus loin. Seuls sont retenus à l’issue de cette étape lesdocuments suffisamment proches de la requête –dont la ressemblance ou le scoresont positifs. Pour terminer, les documents trouvés sont ordonnés en fonction deleurs scores et une liste est proposée à l’utilisateur.

Au travers de SIAC, on se propose d’aborder les techniques d’indexation,l’évaluation de différentes mesures de similarités entre un document et une requêteainsi que la mise en place de différents post-traitements sur la liste de documentsrenvoyés pour une requête. Ce logiciel a participé aux campagnes d’évaluationAmaryllis’97 et 99 [BEL 97] [BEL 2000b] pour la recherche documentaire ainsiqu’à TREC-7 [LOU 98] pour des expériences en classification automatique.


2.2. La campagne d’évaluation « Amaryllis’99 »

Notre participation à la campagne francophone Amaryllis’99 d’évaluation dessystèmes de recherche documentaire était l’occasion de tester en grandeur naturel’algorithme de classification et de segmentation que nous décrivons ci-après. Lesdonnées de base de cet algorithme sont une liste de documents trouvés en réponse àune requête. Afin d’obtenir la meilleure liste possible, nous avons choisi d’utiliserdes méthodes de recherche ayant déjà fait leurs preuves pour le calcul desressemblances entre un document et une requête.

2.2.1. Présentation de la campagne Amaryllis’99

Le projet Amaryllis [LES 99] est le résultat de l’appel d’offres effectué parl’AUF (Agence Universitaire de la Francophonie). Les deux campagnes Amarylliseffectuées à ce jour (1997 et 1999) ont été organisées par l’INIST (INstitut del’Information Scientifique et Technique). Les référentiels (liste des bonnesréponses) correspondent à des jugements formulés par des experts du domaine(documentalistes, fournisseurs des corpus). En outre, ces référentiels sont révisés enfonction des réponses données par les systèmes participant à la campagne de test.Les révisions sont effectuées par les fournisseurs de corpus eux-mêmes. Pour lacampagne d’évaluation Amaryllis’99, les fournisseurs des corpus pour la tâche ad-hoc sont : l’OFIL (Observatoire Français et International des Industries de laLangue), l’INIST et le LRSA (Laboratoire de Recherches Sémiographiques enAnthropologie —Université de Laval au Québec). La campagne Amaryllis’99 aduré un peu moins d’un an (de septembre 1998 à juillet 1999). Elle a réuni onzeéquipes issues de cinq pays différents (France, Canada, Suisse, Thaïlande, USA).Les expériences décrites dans ce document ont été effectuées sur le corpus OD1 del’OFIL (11 016 articles du quotidien Le Monde, plus de 2,4 millions de mots).

2.2.2. Poids des termes

Le logiciel ECSTA développé au Laboratoire d’Informatique d’Avignon permet,grâce à l’utilisation conjointe d’un dictionnaire des formes fléchies du français,d’obtenir l’étiquette syntaxique1 et le lemme de chaque terme du corpus [ELB 95].Grâce à l’étiquetage syntaxique il est possible de résoudre quelques ambiguïtés surles termes et d’éliminer automatiquement un certain nombre de mots vides tels lesarticles, pronoms, déterminants, etc., sans être obligé d’employer une listeprédéfinie de termes inutiles. La lemmatisation permet quant à elle de représenterles différentes formes fléchies d’un mot par leur lemme : forme au singulier pour lesmots employés au pluriel et forme à l’infinitif pour les verbes conjugués. Ainsi la

1 Le taux d’erreur d’ECSTA est de 6,2% (3,5% si l’on exclut les mots inconnus, i.e. absents dudictionnaire utilisé) [ELB 95].


taille de l’index est réduite de moitié2 et il est inutile que la requête contienne lamême forme fléchie d’un terme que celle utilisée dans les documents pour qu’il soitreconnu. Il est par exemple possible de distinguer « marches – nom féminin pluriel»de « marches – verbe 2è personne du singulier » et de représenter ces deux formespar leurs lemmes « marche – nom féminin singulier » et « marcher – verbeinfinitif ». De la même manière, « Noir – nom patronymique » est distingué de« noir – adjectif ».

Une fois ce premier traitement effectué sur l’intégralité du corpus, les lemmesdes textes doivent être relevés. Afin de déterminer quels sont les termes les plusimportants, un poids est attribué à chacun d’eux et ceci pour chaque texte du corpus.La formulation du poids que l’on choisit, appelée TFIDF (Term Frequency, InverseDocument Frequency) tient compte du nombre d’apparitions du terme dans ledocument et du nombre de documents qui contiennent ce terme dans le corpus :

TFIDF w d TF

DFNw

w( , ) . log= − +

2 1 [1]

avec : w un terme, d un document, TFw le nombre d’apparitions de w dans d, DFw lenombre de documents du corpus qui contiennent w et N le nombre total dedocuments dans le corpus.

Autrement dit, pour un document donné, un terme est important s’il apparaîtsouvent dans ce document et que peu de documents le contiennent.

2.2.3. Calcul des similarités

La recherche proprement dite s’effectue en calculant une mesure de similaritéentre chaque document du corpus et la requête posée par l’utilisateur. La requêtesubit tout d’abord les mêmes traitements que les textes du corpus en débutd’indexation : ses mots sont étiquetés puis lemmatisés et un poids est attribué àchacun d’eux en utilisant de nouveau3 TFIDF. L’index du corpus permet d’obtenirla liste des documents qui contiennent les termes de la requête. En fonction du poidsdes termes dans les documents et dans la requête, les similarités entre chaquedocument et la requête sont calculées.

Selon le modèle vectoriel [SAL 89] (un texte est représenté par un vecteur dontles valeurs des composantes –les entrées de l’index– sont les poids TFIDF), lasimilarité utilisée correspond au calcul du cosinus de l’angle des vecteursreprésentant les documents et la requête (mesure Cosine [SAL 83]) :

2 À titre indicatif l’indexation du corpus OD1 de l’OFIL dure environ 5mn (PowerPC G3, 300 MHz, 128Mo de RAM). La taille de l’index égale 22Mo (la taille du corpus est de 33 Mo).3 Dans ce cas : TFw est le nombre d’apparitions de w dans la requête.


cosine( , ), ,

, ,

d r

TFIDF TFIDF

TFIDF TFIDF

w d w rw d r

w dw d

w rw r

=⋅

⋅

∈ ∩

∈ ∈

∑

∑ ∑2 2[2]

avec : w un terme, d un document, r la requête, TFIDFw,d le poids de w dans d etTFIDFw,r celui de w dans la requête4.

2.2.4. Évaluation

Pour la campagne Amaryllis, le corpus d’entraînement de l’OFIL « OD1 » estdistribué avec 26 requêtes « OT1 » et le référentiel correspondant (la liste desdocuments pertinents pour chaque requête). Ce corpus est la réunion de 11 016articles du quotidien français « Le Monde ». Les requêtes sont structurées enplusieurs champs : un titre, une description brève, une phrase plus détaillée et uneliste de mots clés. Dans toutes les expériences décrites ici, pour chaque requête tousces champs ont été réunis pour constituer l’écriture finale des requêtes.

0

0 , 1

0 , 2

0 , 3

0 , 4

0 , 5

0 , 6

0 , 7

0 0 , 1 0 , 2 0 , 3 0 , 4 0 , 5 0 , 6 0 , 7 0 , 8 0 , 9 1

Exhaus t i v i té

Figure 1. Évaluation de SIAC durant Amaryllis’99 (courbe rappel/précision)

Grâce au logiciel TrecEval (identique à celui utilisé durant les campagnesTREC), une évaluation des listes fournies par SIAC peut être effectuée. La figure 1 etle tableau 1 donnent des indications sur le rappel des réponses et leur précision

4 Si la requête et un document n’ont aucun terme en commun, la similarité est nulle. À l’opposé, si larequête r et le document d sont deux textes identiques, s(d,r)=1.

rappel

préc

isio

n


selon leur définition classique. Le rappel est le taux de documents pertinents trouvéspar rapport au nombre de documents pertinents à trouver. La précision est le rapportdu nombre de documents pertinents trouvés avec celui de documents ramenés.

Des indications sur le rappel et la précision peuvent être obtenues également enarrêtant la liste des documents proposés par SIAC à différents niveaux (tableau 1).

Nombre de documents Précision5 0,3710 0,3115 0,2920 0,2730 0,24100 0,12200 0,08500 0,03

Précision moyenne : 0,235Nombre de documents pertinents à trouver = 587

Nombre total de documents rapportés = 6454Nombre de documents pertinents trouvés = 418

Tableau 1. Évaluation de SIAC durant Amaryllis’99 avec TFIDF et Cosine

3. Classification par arbres de décision

3.1. Introduction et hypothèses

Certaines hypothèses sont posées par tous les systèmes de recherchedocumentaire représentant les documents selon le modèle vectoriel.

Hypothèse 1 : À toute thématique correspond un modèle de langage particulier :en fonction de son utilisation dans les textes, l’importance d’un terme peut êtremesurée statistiquement.

L’hypothèse 1 est habituellement utilisée pour calculer des distances entre undocument et une requête, on l’étend au calcul entre deux documents, entre deuxensembles de documents ou bien entre un ensemble de documents et une requête.

Hypothèse 2 : Si deux documents sont « proches »5 l’un de l’autre, ils abordentla (ou les) même(s) thématique(s).

5 Dans le modèle vectoriel, la « proximité» correspond à la distance entre les vecteurs des documents.


Cette hypothèse n’est pas toujours vérifiée. Deux documents peuventeffectivement employer des termes identiques mais avec des sens différents. Laquantité des termes pris en compte permet toutefois de minimiser le problème puisque le nombre de termes communs à deux documents est un facteur fortementindicatif de cohésion thématique permettant de masquer en partie les ambiguïtéscréées par le phénomène d’homonymie. Le problème n’est généralement visiblequ’en présence de documents courts.

Hypothèse 3 [Cluster hypothesis] : Si l’on greffe sur l’hypothèse 2 la notion depertinence tout en considérant une requête comme un document, on aboutit à unetroisième hypothèse : « Les documents proches tendent à être pertinents pour lesmêmes requêtes. » [VAN 79].

Si cette hypothèse était totalement vérifiée, une pré-classification de tous lesdocuments du corpus permettrait d’accélérer sans perte de qualité les moteurs derecherche en ne confrontant plus les requêtes à tous les documents mais seulement àl’une ou l’autre des classes auxquelles ils appartiennent.

Une quatrième hypothèse est formulée. Elle est en quelque sorte la réciproque dela troisième mais est souvent confondue avec elle :

Hypothèse 4 : Pour une requête donnée, les documents pertinents ont tendance àêtre proches les uns des autres et éloignés des non pertinents (ou : deux documentsproches ont tendance à être pertinents si l’un d’entre eux est pertinent6).

Suivant ces hypothèses, une classification adéquate des documents ramenés parle système de recherche permet d’isoler en classes distinctes ceux qui sont pertinentsde ceux qui ne le sont pas. Les récentes expérimentations faites sur les volumineuxcorpus de TREC tendent à valider le fait qu’il existe bien une séparation entre lesdocuments pertinents et les documents non pertinents [HEA 99].

Cependant, il n’est envisageable de regrouper en une seule classe l’ensemble desdocuments pertinents que s’ils abordent une seule et même thématique générale. Àpartir de la requête « Je cherche des textes sur la résistance », peuvent être ramenésdes documents traitant des mouvements de résistance durant la seconde guerremondiale et d’autres évoquant les caractéristiques de conducteurs ohmiques…Comme il est fort probable que seule l’une des thématiques intéresse l’utilisateur, ilest nécessaire que le moteur de recherche puisse faire la distinction entre ces deuxfamilles de documents en les présentant en deux listes séparées. Une classificationintéressante consiste à subdiviser les documents pertinents en autant de classes qu’ily a de thématiques abordées dans la requête7 (ces thématiques correspondent auxdifférents sens de chacun des termes de la requête).

6 Par effet de chaîne, il se peut alors que deux documents éloignés soient considérés pertinents.7 Ces classes peuvent être réunies en supra classes de manière hiérarchique si le vocabulaire commun àtoutes ces thématiques est suffisamment important.


Par exemple, à une requête sur « les Droits de l’Homme et de la Femme dans lemonde » peuvent correspondre des documents sur la liberté d’expression et depensée, des textes sur le travail des enfants ou traitant d’autres sujets comme lesactes de torture commis dans certains pays. Il est intéressant que le moteur derecherche puisse regrouper, en autant de classes que de thématiques citées, lesdocuments correspondants (ils sont éventuellement tous pertinents).

3.2. Algorithme de classification par arbres de décision

Lors de notre participation à la campagne d’évaluation des systèmes derecherche documentaire TREC 7, nous avons proposé un algorithme de classificationutilisant des méthodes hiérarchiques et de partitionnement [LOU 98] (de type« nuées dynamiques » [DID 82]). Les résultats obtenus sont comparables avec lesmeilleurs résultats observés à ce jour à l’aide d’autres méthodes : améliorationd’environ 7 % de la précision des 10 premiers documents des listes après avoir isolémanuellement les classes contenant le plus de documents pertinents. Cependant, lesméthodes hiérarchiques comportent plusieurs inconvénients. Tout d’abord, lenombre de classes dans lesquelles les documents sont distribués doit être fixé apriori alors que la valeur optimale est variable d’une requête à l’autre8. Ensuite,elles nécessitent le calcul des distances entre tous les documents pris deux à deux cequi constitue une opération très coûteuse en temps machine. Enfin, la classificationest remise en cause lorsqu’un nouveau document vient s’adjoindre à la collection9.

Nous proposons une méthode alternative à la classification hiérarchique et auxméthodes de partitionnement. Elle emploie des arbres de décision non supervisés. Ilest montré que cette méthode, tout en étant plus rapide et plus facile à utiliser(moins de paramètres à définir), conduit à de meilleurs résultats lorsqu’elle estappliquée à la recherche documentaire. Dans les sections suivantes, nous décrivonsune utilisation des arbres de décision pour classer thématiquement des segments detextes (phrases, paragraphes, etc.) dans le cadre de la recherche documentaire10. Lesrésultats de cette classification permettent d’isoler un certain nombre de documentsthématiquement proches. Ils permettent en outre de déduire une nouvellesegmentation des documents en apposant à l’intérieur des textes des frontièresthématiques. Ce dernier point sera détaillé en section 4.

8 La plupart des expériences faites à ce jour ([HEA 96], [SIL 97]) utilisent un nombre constant de classescompris entre 5 et 10. Les tests que nous menons actuellement indiquent que le nombre de classesoptimal est fonction de la taille de la requête.9 Pour plus de détails, se référer à [LOU 98] (http://trec.nist.gov).10 Les autres applications des arbres de décisions au langage naturel concernent la modélisation dulangage, l’apprentissage de règles sémantiques, l’étiquetage syntaxique ou la correction orthographique[KUH 95]. Certaines expériences ont également été réalisées pour étiqueter thématiquement des articlesjournalistiques [CRA 91].


Pour construire un arbre de décision, on doit définir un ensemble de questions,une règle pour déterminer la meilleure question à poser aux textes d’un nœud et uncritère d’arrêt déterminant l’ensemble des feuilles de l’arbre.

Souhaitant utiliser les résultats de la classification pour déterminer unesegmentation thématique interne aux documents trouvés durant la recherche (cf.section 4), nous avons pensé qu’il était possible de considérer les phrases ou lesparagraphes des textes comme étant les individus contenus dans les nœuds del’arbre. Les textes du corpus de l’OFIL ne contenant pas de marques deparagraphes, les individus à classer sont des phrases. En ce qui nous concerne, cesphrases sont celles des documents trouvés par SIAC en réponse à une requête. Il està noter que la méthode peut être appliquée en aval des traitements effectués par toutmoteur de recherche documentaire qui renvoie une liste de documents en réponse àune requête et pas seulement par le système SIAC.

3.2.1. Questions posées aux individus

Les mots employés dans les textes permettent de déterminer la ressemblance deces derniers. Le but étant ici de regrouper les individus (les phrases) proches les unsdes autres, on fait en sorte de placer dans la même feuille de l’arbre ceux qui ont encommun le plus grand nombre possible de mots. À chaque nœud de l’arbre, il s’agitdonc de calculer quel est le mot x qui permet de subdiviser au mieux les individusqu’il contient. Une question Qx de la forme : « les individus contiennent-ils le motx ? » est posée à chaque individu. Elle subdivise un nœud N en deux nœuds fils NOUI

et NNON qui comprennent respectivement les individus de N qui contiennent et qui necontiennent pas le mot x.

Dans le cas de questions simples, x désigne n’importe quel terme référencé dansl’index. Des questions « doubles » de la forme « les individus contiennent-ils lesmots x et y ? » peuvent également être posées. En imposant que l’un des deuxtermes x ou y soit issu de la requête, l’utilisation de questions doubles permet unecertaine désambiguïsation des termes de la requête. Par exemple, si la requêtecontient le mot résistance, des questions du type (résistance, nazi) et (résistance,ohm) permettent de départager deux interprétations possibles du mot résistance.Cette restriction permet en outre de limiter le nombre de questions possibles et defaire en sorte que cette réduction dépende des termes de la requête.

3.2.2. Calcul de l’entropie d’un nœud

En ce qui nous concerne, la classification conduit à la partition d’un ensemble endeux classes, celle des phrases ayant répondu « oui » à la question et celle desphrases ayant répondu « non ». Le critère de qualité d’une classe dépend de lapertinence des phrases qu’elle contient, sachant que l’objectif est d’obtenir desclasses ayant le plus possible de phrases issues de documents pertinents et le moinspossible de phrases issues de documents non pertinents. Une des manières de


calculer la pertinence d’une classe est d’évaluer la probabilité que la requêtecorresponde aux phrases contenues dans cette classe.

De manière générale, l’entropie H d’une classe est définie suivant les valeurs deprobabilité des modalités ei d’une variable aléatoire :

H( ) P( ).log P( )classe = − ( )∑

ii ie e [3]

Plus les valeurs de probabilité sont proches, plus l’entropie est grande [JUN 97].En ce qui nous concerne, la probabilité choisie correspond à celle d’une variablealéatoire discrète ayant deux modalités —la requête correspond aux phrases et larequête ne correspond pas aux phrases11—. Une bonne classification coïncide avecla partition des phrases en deux ensembles permettant de déterminer au mieux si lesphrases qu’ils contiennent sont pertinentes ou non. Autrement dit, trouver lameilleure question revient à déterminer quel est le terme qui permet de partitionnerles phrases de telle sorte que les valeurs de probabilité de la correspondance avec larequête (ou de non correspondance) soient aussi grandes que possible. Si un nœudde l’arbre contient des phrases pour lesquelles les valeurs de probabilité decorrespondance avec la requête et de non correspondance sont proches, il estimpossible de choisir si ces phrases sont globalement pertinentes ou non. Laquestion qu’il faut choisir est celle permettant de décider avec le moins d’incertitudede la correspondance ou de la non correspondance de la requête avec les phrases del’une et de l’autre classe. Dans le cas idéal, la question doit permettre de dire« j’avais un ensemble de phrases de pertinence indéterminée, j’ai maintenant deuxensembles de phrases pour lesquelles je peux décider si elles sont pertinentes ounon avec une probabilité nulle de me tromper ». L’entropie permet de mesurerl’incertitude liée à la décision de correspondance ou de non correspondance entre larequête et les phrases —formule [5] avec p défini en formule [4]—. La meilleurequestion est celle qui permet la plus grande perte d’incertitude —formule [7] où ∆Hdésigne le gain en entropie, lui-même fonction de l’entropie moyenne des deuxclasses —formule [6]—.

Ainsi, maximiser le gain en entropie revient à trouver la question qui maximisela différence entre les deux valeurs de probabilité (correspondance ou noncorrespondance entre la requête et les phrases) et ce pour les deux classes à la fois—formule [5]—. Pour cela, sont calculées pour chaque question Q : l’entropie Hliée au nœud considéré N et l’entropie moyenne des nœuds NOUI et NNON résultant dela subdivision entraînée par Q. La question choisie est celle à laquelle correspond laplus grande baisse d’entropie (ou qui maximise ∆H —formule [7]—).

11 La probabilité inverse (probabilité qu’un texte corresponde à la requête) semble plus naturelle face àl’objectif fixé mais elle ne peut être calculée avec fiabilité à cause du trop petit nombre de requêtesdisponibles.


À chaque nœud de l’arbre correspondent les deux valeurs de probabilité citées (ils’agit d’une seule distribution de probabilité établie sur une variable aléatoire Xdiscrète ayant deux modalités). La valeur p correspond à la probabilité que larequête corresponde aux phrases Si du nœud considéré. La seconde valeur (noncorrespondance entre la requête et les phrases) est naturellement le complément dela première, soit 1-p. La probabilité p est calculée suivant un modèle unigramme :

p r w w w S p w S

Z w S

S

ni S N

ij

n

ji S N

i

j iij

i S Ni

n

i i

i

( , , , | ) ( | )

( , )

/ /

/

= =

=

∈ = ∈

∈

∏

∑∏

1 21

K U U

U

[4]

avec r la requête, wj le jè terme de r, N un nœud de l’arbre, Si une phrase et Z() lenombre d’apparitions d’un terme dans une phrase Si donnée. Les barres | | indiquentle nombre de termes (occurrences) apparus dans un ensemble de phrases.

L’entropie d’un nœud N est définie comme suit :

H p p p pN = − − − −log ( ) log( )1 1 [5]

Les entropies correspondant à chacun des deux nœuds fils issus du nœud N sontnotées HOUI,N et HNON,N (ils contiennent respectivement les individus ayant répondu« oui » et « non » à la question considérée).

L’entropie moyenne —formule [6]— correspondant à chacun de ces deux nœudsest fonction de la taille des individus migrant dans HOUI,N et HNON,N –la taille estexprimée par le nombre de termes (occurrences) présents– par rapport à celle detous les individus du nœud père.

HS

SH

S

SHN

i S Ni

i S Ni

OUI Ni S N

i

i S Ni

NON Ni OUI

i

i NON

i

= +∈

∈

∈

∈

U

U

U

U

/

/

,/

/

, [6] ∆H H HN N= − +1 [7]

Enfin, le gain en entropie associé à la question est égal à ∆H —formule [7]—.


3.3. Expérimentation

Une fois le critère d’arrêt vérifié, les individus –les phrases des documentstrouvés en réponse à une requête– sont répartis en un certain nombre de classes. Ils’agit alors de fournir à l’utilisateur une nouvelle vision des solutions proposées parle système de recherche documentaire. Plusieurs parcours des classes sont envisagéspour présenter les résultats de la classification. Si l’on est capable de déterminerautomatiquement la classe qui contient le plus (en proportion ou en quantité) dedocuments pertinents, on peut proposer d’abord les documents de cette classe. Onpeut aussi choisir, en premier lieu, les documents jugés les plus pertinents de chaqueclasse en fonction du score fourni par SIAC. Enfin, il est possible de demander àl’utilisateur de sélectionner la classe de documents qui lui semble le mieux répondreà sa demande. Cela peut se faire en indiquant les titres de chaque document ou enoffrant la possibilité d’explorer les premiers documents de chaque classe.

3.3.1. Exemple 1 : classification des documents issus de la requête n° 23

La requête n°23 porte sur la situation politique au Cambodge. Elle demanded’identifier les forces politiques en présence et de décrire leur attitude face à laminorité vietnamienne. La classification des 12 380 phrases issues des 250documents trouvés par SIAC produit l’arbre schématisé12 sur la figure 2. On ytrouve les questions choisies et la population de chaque feuille.

On remarque qu’un très grand nombre de phrases sont positionnées dans uneseule feuille. Cela s’explique aisément par le fait que la grande majorité des phrasesne contiennent pas les mots des questions choisies. Cette feuille comprendl’ensemble des phrases que l’arbre n’a pas permis de classer. On peut par contreconsidérer que les autres feuilles contiennent des phrases ayant un rapportthématique entre elles puisqu’elles ont répondu par l’affirmative à au moins unequestion. La feuille inférieure gauche F1 comprend 15 individus contenant les mots« CNS » et « khmer ». Ces 15 phrases sont issues de 10 documents différents parmilesquels 7 sont pertinents. La feuille F2 contient 5 phrases issues de 3 documentsdifférents, tous trois pertinents. Ces deux feuilles nous apprennent que si les phrasescontiennent le terme CNS, la présence ou non du terme « khmer » n’apporte rienquant à leur pertinence. Parmi les documents rapportés par SIAC, tous ceuxcontenant le terme CNS sont pertinents. Les individus de la feuille F6 correspondentà tous les documents trouvés (ils ont tous une phrase n’employant pas les termesCNS et Pailin). Parmi eux, 40 documents sont pertinents.

Ces résultats confirment, au moins sur cette requête, la capacité de l’algorithmeà isoler certains documents pertinents et à effectuer une classification thématique.

12 Parmi les questions choisies, CNS représente le « Conseil National Suprême » et Pailin est une ville dusud du Cambodge.


Figure 2. Questions et population de chaque feuille pour la requête 23 (nombre dephrases à nombre de documents (nombre de documents pertinents))

3.3.2. Exemple 2 : classification des documents issus de la requête n° 30

La requête n°30 concerne l’augmentation éventuelle des saisies de drogues enFrance. Les questions choisies lors de la classification des 14 844 phrases des 204documents rapportés par SIAC sont indiquées dans le tableau 2. Les termes de larequête ne sont pas directement pris en compte pour le choix des questions.Cependant, les questions sélectionnées correspondent pour la plupart aux termes dela requête. Ces termes étant utilisés pour le calcul de l’entropie, il est naturel qu’ilssoient choisis en priorité (la présence d’un terme de la requête dans une phrase estsouvent un meilleur indicateur qu’un terme quelconque de la pertinence ou de lanon pertinence d’une phrase).

Question drogue trafiquant cocaïne dealer haschich marijuana

Gain enentropie 0,90 1,41 2,38 4,87 6,80 11,26

Tableau 2. Questions simples choisies pour la requête n° 30

p 1-p p 1-p

oui

oui oui

oui

oui

non

non non

non

non

CNS ?

khmer ? Pailin ?

Cambodge ?

socialiste?

15 à 10 (7) 5 à 3 (3) 12 304 à 250 (40)

51 à 15 (4)

3à 3 (3) 2 à 2 (1)

F1

F2

F3 F4

F5

F6


3.3.3. Évaluation à partir des meilleures classes

Une façon d’évaluer la classification consiste à utiliser les réponses exactes (laliste des documents pertinents) de chaque requête qui sont fournies par lesorganisateurs de la campagne Amaryllis. Ceci permet d’ordonner les classes enfonction de la proportion de documents pertinents qu’elles contiennent. Cetteméthode d’évaluation a également été choisie lors des expériences de classificationautomatique pour la recherche documentaire menées par [HEA 96] et [SIL 97].Dans notre cas, les individus classés étant des phrases et non des documents entiers,la constitution d’une liste à partir du contenu des classes conduit à présenterplusieurs fois les mêmes documents (cas où les phrases d’un même document seretrouvent dans des classes différentes). Nous remédions à cela en ne considérantpour chaque document que sa présence dans la classe occupant le meilleur rang.

Suivant cette méthode d’évaluation, les augmentations absolues (cf. tableau 3)de la précision des 5 et des 10 premiers documents sont égales à 11 % (soit environ29 % d’amélioration relative) et 5 %. Il est clair qu’une amélioration était attenduemais elle n’était pas certaine. Il n’est en effet pas obligatoire que les meilleuresclasses contiennent plus de documents pertinents bien positionnés que la listeoriginelle. Si une classe se retrouve en tête c’est soit qu’elle est beaucoup peupléemais qu’elle contient une grande quantité de documents pertinents soit qu’elle estpeu peuplée mais que la proportion de documents pertinents est grande. Sachant quesur les 26 requêtes la population moyenne de la meilleure classe est de 50documents, une amélioration de la précision pour 5, 10 ou 15 documents n’était pasobligatoire. On peut également noter que l’augmentation constatée de la précisiondépasse celle vue avec d’autres méthodes selon le même type d’évaluation ([LOU98], [HEA 96], [SIL 97]) où seules des améliorations de l’ordre de 5 à 8 % dans lemeilleur des cas étaient relevées. Ce résultat doit néanmoins être tempéré car lesdonnées sont différentes dans toutes ces expériences. La courbe représentée sur lafigure 3 confirme ces résultats en montrant des améliorations de précision pour unniveau de rappel inférieur à 0,4.

On constate (tableau 3) une influence assez nette du choix du critère d’arrêt.Avec un gain d’entropie minimal égal à 0,001, les résultats sont sensiblementmeilleurs qu’avec une valeur de seuil égale à 0,02 (choix empiriques). Cependant,les temps de calcul nécessaires à la classification sont environ trois fois plusimportants à cause d’une forte augmentation de la profondeur des arbres. D’autrepart, ces améliorations peuvent s’expliquer par le plus grand nombre de classesobtenues avec la plus petite valeur de seuil. Le biais introduit par l’utilisation desréférentiels pour l’évaluation est plus grand dans ce cas. Le choix de la valeur seuilpourrait être défini par l’utilisateur du système de recherche en fonction de lafinesse souhaitée de la classification.

L’utilisation de questions doubles —de la forme « les documents contiennent-ilsles mots x et y ? » avec x un mot de la requête– permet d’obtenir de meilleursrésultats qu’avec des questions simples pour un critère d’arrêt identique mais


nécessite des temps de calcul encore plus importants13. Si V est la taille duvocabulaire des documents, si M est le nombre de mots dans la requête et D est lenombre d’individus à classer, la complexité en temps du choix de la question àposer est en O(V.M.D).

Critèred’arrêt(seuil)

Précisionpour un

rappel 0,00

Précisionpour un

rappel 0,10

Précisiondes 5

premiersdocuments

Précisiondes 10

premiersdocuments

Précisionmoyenne

Sans classification 0,63 0,47 0,37 0,31 0,235

Questionssimples

0,02 0,65 (2%) 0,51 (4%) 0,38 (1%) 0,32 (1%)0,24

(0,5%)Questionssimples

0,001 0,75 (12%) 0,55 (8%) 0,48 (11%) 0,36 (5%)0,26

(2,5%)

Questionsdoubles

0,02 0,66 (3%) 0,53 (6%) 0,44 (7%)0,37 (6%)0,26

(2,5%)

Tableau 3. Évaluation avant et après classification (les chiffres entre parenthèsessont des pourcentages d’amélioration absolue)

3.3.4. Répartition des documents pertinents dans les classes

L’étude des classes obtenues en fin de traitement confirme également l’intérêt dela méthode. Pour 20 des 26 requêtes testées, il existe une classe ayant une meilleureprécision globale que la liste renvoyée par SIAC –limitée à 250 documents parrequête–. Ce résultat est significatif car le nombre moyen de classes créées est égal à11 si l’on exclut le cas d’une requête ayant produit 187 classes (il ne s’agit donc pasnécessairement de classes peu peuplées). Une analyse non détaillée ici montre quepour une requête, 50 % des documents pertinents trouvés (11 sur 22) se retrouventdans une classe ne contenant que 13 documents. Pour une autre requête, les 4documents pertinents retrouvés par SIAC se retrouvent dans la même classe(peuplée de 17 textes). Enfin, pour une autre requête, 5 des 14 documents pertinentstrouvés sont réunis dans une classe qui ne comporte pas d’autres documents. Les

13 Avec des questions simples et un seuil d’arrêt égal à 0,02, la classification des 26 requêtes nécessiteenviron 2 minutes de temps de calcul (PowerPC G3, 300 MHz, 128 Mo RAM). Ce temps passe à environ10 minutes pour un seuil égal à 0,001 et à… une dizaine d’heures avec des questions doubles et unevaleur de seuil égale à 0,02. Notons enfin que la proximité et l’ordre des deux mots de la question dansles documents ne sont pas pris en compte. Si cette méthode est appliquée aux moteurs de recherche grandpublic sur le WWW, son utilisation peut se restreindre par exemple aux mille premiers documentstrouvés. Ceci n’est pas un handicap puisque l’utilisateur explore rarement plus de documents !


niveaux de précision atteints par les meilleures classes peuplées de plus de 15documents expliquent les hausses de précision vues en 3.3.3 dans le tableau 3.Globalement, toutes les classes sauf une sont peu peuplées (quelques dizainesd’individus chacune en moyenne). Comme cela a été vu dans l’exemple donné en3.3.1, il existe pour chaque requête, une feuille qui comprend les phrases que laméthode n’a pu classer.

0

0 , 1

0 , 2

0 , 3

0 , 4

0 , 5

0 , 6

0 , 7

0 , 8

0 0 , 1 0 , 2 0 , 3 0 , 4 0 , 5 0 , 6 0 , 7 0 , 8 0 , 9 1

Exhaus t i v i té

Sans Classification Seuil = 0,02 Seuil = 0,001

Figure 3. « Rappel / précision » avant et après classification

4. Segmentation et classification

Lorsqu’on examine la liste des documents rapportés par un système de recherchedocumentaire on s’aperçoit que certains documents pertinents sont mal positionnéscar ils ont été indexés dans leur globalité. Prenons l’exemple d’une encyclopédieavec des articles traitant de sujets multiples. Si le moteur de recherche indexe cetouvrage comme une seule entité documentaire, aucun des mots clés contenus dansles articles ne peut émerger à cause notamment d’une fréquence d’apparition faiblesur l’ensemble de l’encyclopédie. Les mots clés se voient ainsi attribuer un poidsrelativement faible qui tend ensuite à empêcher l’encyclopédie de figurer en tête deslistes de documents ramenés durant la recherche.

Cet exemple est évidemment caricatural : il est rare qu’une encyclopédie soittraitée comme un seul document ! Il arrive cependant que le même phénomène seproduise avec des entités documentaires plus petites. Un article journalistiquetraitant de la guerre au Kosovo peut débuter par des rappels historiques relatifs à lacréation de la Fédération Yougoslave, continuer sur les conflits religieux et

préc

isio

n

rappel


ethniques qui y existent, pour enfin aborder la situation actuelle en évoquant le sortdes réfugiés, la position des dirigeants serbes et occidentaux ou les conséquenceséventuelles des opérations militaires effectuées par l’OTAN. Avec les techniquesd’indexation et de calcul de similarités classiques, ces thématiques sont plus oumoins masquées si l’article est vu seulement dans sa globalité. Dans ce cas, pourune requête ne portant que sur « les conditions de vie des réfugiés », il est peuprobable que cet article soit positionné en début de liste des documents rapportés.Par contre tout article au sujet de réfugiés dans n’importe quel pays durantn’importe quel conflit aura toutes les chances d’être mieux placé même s’il n’est paspertinent. Enfin, si la requête est du type : « Combien y a-t-il de réfugiés Kosovarsen Albanie ? », une segmentation adéquate des documents en zones homogènes peutpermettre d’extraire la (les) zones qui répond(ent) à la question (la segmentation estdifférente pour chaque requête). L’extraction des zones pertinentes s’effectue grâceà une deuxième recherche sur les segments (calcul des ressemblances entre chaquezone et la requête) comme décrit dans la section suivante.

4.1. Méthode de segmentation découlant de la classification

L’application de l’algorithme décrit en 3.2 permet de réunir les phrases issuesdes documents trouvés en réponse à une requête en un certain nombre de classes.Nous avons montré en 3.3.3, en évaluant les taux de pertinence des documentscorrespondant aux phrases de chaque classe, que cette classification permet souventun regroupement thématique correct. Il est donc possible de supposer que deuxphrases issues de la même classe partagent la même thématique (à l’exception decelles issues de la classe des individus ayant répondu par la négative à toutes lesquestions qui leur ont été posées). À l’opposé, si deux phrases se trouvent dans deuxclasses différentes, on suppose qu’elles abordent des sujets différents. Il est décidédans ce cas d’apposer entre elles une marque de frontière thématique et l’on procèdede même pour l’ensemble des documents rapportés. Une segmentation est ainsidirectement déduite de la classification.

4.2. Une deuxième recherche appliquée sur les segments

Il s’agit alors d’effectuer une deuxième recherche documentaire à partir de larequête non plus sur l’ensemble des documents du corpus mais, parmi lesdocuments déjà trouvés, sur les segments homogènes déduits de la classification14.L’ensemble de ces segments est considéré par SIAC comme un nouveau corpus (lessegments sont traités comme s’ils étaient des documents à part entière). La seconderecherche fonctionne selon le même procédé que la première (la valeur de la

14 Les frontières entre documents sont naturellement conservées.


pondération des termes est différente du fait du nouveau découpage desdocuments15). À l’issue de cette seconde recherche, deux listes peuvent êtreproposées à l’utilisateur. La première est une liste de segments ordonnés suivantleur ressemblance avec la requête tandis que la seconde est la liste des documentsoriginels réordonnés suivant les scores de leurs segments (la nouvelle valeur depertinence d’un document correspond au score de son meilleur segment).

4.3. Expérimentation

On se propose d’évaluer la segmentation obtenue à partir de la classificationselon un critère d’arrêt de la construction de l’arbre égal à 0,02 (questions simples).Lors de la première recherche, le nombre de documents que SIAC pouvait rapporterétait limité à 250 par requête16. Il en ressortait une liste de 6 454 documents pourl’ensemble des 26 requêtes. Après segmentation, le nombre de segments (unitésdocumentaires sur lesquelles porte la seconde recherche) est égal17 à 11 310.

4.3.1. Exemple de segmentation d’un document (requête n°4)

Les termes de la requête sont : xénophobie, violence, mouvement, extrême,droite, étranger, décès. L’un des documents trouvés en réponse à la requête évoqueune manifestation contre l’extrême droite en Autriche. Il est segmenté en trois unitésdocumentaires correspondant chacune effectivement à une illustration différente dela thématique du document.

Unité documentaire n° 1 : (description de la manifestation) « Autriche : en réponse àla consultation populaire sur l’immigration : deux cent mille personnes ont manifesté àVienne contre la xénophobie. Les adversaires du racisme et de la xénophobie se sontmassivement mobilisés samedi 23 janvier à Vienne, où deux cent mille personnes ontdéfilé sur le célèbre Ring, le boulevard qui entoure le centre de la capitale autrichienne.Les manifestants ont formé une « mer de lumière », suivant l’exemple des allemands quiprotestent, bougies et lampions à la main, contre les exactions racistes dans leur pays.Cette mobilisation, qui se voulait une réponse à l’ouverture de la consultation populairesur la limitation de l’immigration lancée par le parti de la droite nationaliste FPOE,avait été organisée par le comité SOS-Nos prochains. Les principaux partis politiques –à

15 La pondération utilisée lors de la deuxième recherche pourrait s’intituler TFISF (Inverse SegmentFrequency) à la place de TFIDF puisque l’importance d’un terme est maintenant fonction du nombre desegments qui la contienne et non du nombre de documents. Cette nouvelle pondération est judicieuse si lasegmentation est effectivement thématique (un terme est peu discriminant s’il apparaît dans un grandnombre de segments).16 Il s’agit d’une limitation imposée par les organisateurs de la campagne d’évaluation Amaryllis’99.17 Le nombre de segments est environ 10 fois plus important pour un critère d’arrêt de la classificationégal à 0,001.


l’exception du FPOE–, les Eglises, les organisations patronales et syndicales, avaientappelé à participer à cette manifestation, la plus massive qu’ait connue Vienne depuis1945. Celle-ci s’est achevée sur la Heldenplatz, à l’endroit même où la foule autrichienne avaitacclamé Adolf Hitler venu proclamer l’annexion de l’Autriche au Reich, le 15 mars 1938. »

Unité documentaire n° 2 : (déclaration du Président de la République autrichienne)« « Je suis fier qu’un si grand nombre d’Autrichiens aient décidé qu’il n’y avait pas deplace dans notre pays pour le racisme et la xénophobie », a déclaré M. Thomas Klestil,président de la République. »

Unité documentaire n° 3 : (Résultats des élections municipales) « Le FPO de M. JorgHaider a cependant remporté un nouveau succès électoral à l’occasion des électionsmunicipales qui se sont tenues dimanche à Graz, la deuxième ville du pays. Avec 20% dessuffrages, il double son score de 1988, alors que les deux partis de la coalitiongouvernementale, le Parti social-démocrate et le Parti populaire (démocrate-chrétien),perdent respectivement 8,1 et 6,4% des voix. (AFP, Reuter). »

4.3.2. Évaluation de la segmentation appliquée à la recherche documentaire

Une étude particulière doit être effectuée pour mettre au point des fonctions desimilarité permettant de mesurer la ressemblance d’une requête et d’un extrait–parfois très court– d’un document. Appliquée aux segments déduits à partir de laclassification, la mesure Cosine utilisée par SIAC (cf. 2.2.3) dégrade fortement lesrésultats : baisse absolue de 10 % de la précision à 5 documents et de 4 % à 10documents par rapport à une utilisation sans classification ni segmentation. Commesuggérée dans [WIL 95], une combinaison linéaire de différentes mesures donne debien meilleurs résultats (cf. la figure 4 et le tableau 4). En ce qui nous concerne, lesmesures combinées sont Cosine —formule [2]— et une variante d’Okapi —formule[9]—. Les améliorations constatées avec cette combinaison peuvent s’expliquer parle fait que la mesure Okapi met sur un pied d’égalité les phrases contenant plusieursmots communs avec la requête mais qui n’apparaissent qu’une seule fois, avec lesphrases contenant un seul mot commun mais aux occurrences nombreuses. Cetteseconde catégorie de phrases est avantagée par Cosine : les phrases où un terme estrépété plusieurs fois sont peu nombreuses, mais, lorsque c’est le cas, il s’agitsouvent de termes peu informatifs qu’il ne faut justement pas favoriser.

La définition d’Okapi est la suivante :

okapi( , ) log ,

,

S rN DF

DF

TF

TFS

M

w

ww S r

w S

w SS

= −

⋅

+∈ ∩∑ [8]

avec : r la requête, S un segment, w un terme, TFw,S le nombre d’apparitions de wdans S, DFw le nombre de segments contenant w, N le nombre total de segments, etMS leur taille moyenne.


Mesure[n° formule]

Pr�cisionpour un

rappel 0,00

Pr�cisionpour un

rappel 0,10

Pr�cisiondes 5

premiersdocuments

Pr�cisiondes 10

premiersdocuments

Pr�cisionmoyenne

Avantsegmentation

0,63 0,47 0,37 0,31 0,235

Cosine [2] 0,48 (-15%) 0,37 (-10%) 0,28 (-9%) 0,24 (-7%)0,195(-4%)

Okapi [8] 0,48 (-15%) 0,30 (-17%)0,25

(-12%)0,23 (-8%)

0,16(-7,5%)

OKAbis [9] 0,61 (-2%) 0,4 (-7%) 0,28 (-9%) 0,25 (-6%)0,19

(-4,5%)

Cosine +0,5.OKAbis [10]

0,58 (-5%) 0,48 (+1%) 0,39 (+2%) 0,31 (=)0,22

(-1,5%)

Tableau 4. Évaluation avant et après segmentation (les chiffres entre parenthèsessont des pourcentages d’évolution absolue)

0

0 , 1

0 , 2

0 , 3

0 , 4

0 , 5

0 , 6

0 , 7

0 0 , 1 0 , 2 0 , 3 0 , 4 0 , 5 0 , 6 0 , 7 0 , 8 0 , 9 1

Exhaus t i v i té

Cosine Okapi Okapi sans terme en log Cosine + Okapi sans terme en log

Figure 4. Comparaison de différentes mesures après segmentation

Dans le cas où un terme w apparaît dans plus de la moitié des documents, leterme en log est négatif. Cela a pour conséquence d’écarter certains documents necontenant avec la requête qu’un seul mot en commun et de diminuer le rappel dusystème. Utilisée telle quelle sur les segments déduits de la classification, Okapi

rappel

préc

isio

n


—formule [8]— produit d’aussi mauvais résultats qu’une mesure ne tenant compteque du nombre de mots communs entre la requête et les segments : baisse de 7 % dela précision par rapport à Cosine pour un rappel de 0,1. En supprimant le terme enlog (OKAbis —formule [9]—), la mesure Okapi devient beaucoup plusperformante : amélioration de 10 % et 9 % absolus pour des niveaux de rappelrespectifs de 0,1 et 0,2 par rapport à sa définition originelle et de 3 % par rapport àCosine pour un rappel de 0,1.

OKAbis( , ) ,

,

S rTF

TFS

M

w S

w SS

w S r

=

+∈ ∩∑ [9]

Les meilleurs résultats sont obtenus en additionnant les mesures Cosine et Okapisans le terme en log et en multipliant la valeur de cette dernière par 0,5. Lasimilarité entre un segment S et la requête r est dans ce cas :

s , cosine , , . ,S r S r S r( ) = ( ) + ( )0 5 OKAbis [10]

Pour des niveaux de rappel 0,1 et 0,2, les améliorations de la précision parrapport à Cosine seule sont de 8 % et 4 % absolus. Ces résultats permettentd’améliorer légèrement ceux que l’on obtenait avant classification et segmentation :une amélioration de la précision de 2 % absolus pour les 5 premiers documents et de1 % pour un rappel de 0,1. Par contre, une baisse de 1,5 % de la précision moyenneest constatée. Si l’on analyse les résultats requête par requête, la segmentationpermet d’améliorer très sensiblement le niveau de précision à 10 documents pour 5requêtes sur les 26 testées18. Peu d’améliorations sont relevées sur les autresrequêtes ce qui explique des résultats globaux sensiblement identiques à ceuxconstatés avant segmentation. Les améliorations apportées par la combinaison demesures classiques par rapport à l’emploi de Cosine seule permettent d’espérer demeilleurs résultats dans un avenir proche grâce à d’autres combinaisons de mesures.De plus, l’exploitation de corpus contenant des marques de paragraphes permettraune évaluation avec des unités de segmentation plus longues que les phrasesconsidérées. Cela autorisera une meilleure exploitation des mesures de similaritéspeu efficaces sur des textes courts.

Enfin, il est important de noter que le référentiel employé ne donne que la listedes documents pertinents globalement. Il n’est pas évident qu’un document neprésentant que quelques phrases pertinentes ait été jugé pertinent par les personnesayant créé le référentiel. La combinaison des scores obtenus par les segments d’undocument avec son score initial permet de tenir compte de la pertinence globale

18 La pertinence pour 10 documents de la requête n°21 était de 0,3 ; elle passe à 0,8 après segmentation.


d’un document et d’être plus en adéquation avec la nature du référentiel [BEL2000a]. Dans ce cas, les hausses des résultats obtenus après segmentation sontsignificatives. Elles pourraient l’être encore plus nettement avec un référentieldressant la liste des zones pertinentes des documents.

5. Conclusion

Nous avons décrit le système de recherche documentaire SIAC développé auLaboratoire d’Informatique d’Avignon qui nous a permis de participer auxcampagnes d’évaluation Amaryllis’97 et Amaryllis’99 ainsi qu’à TREC-7. Cesystème, construit autour de techniques éprouvées, exploite des outils d’étiquetagesyntaxique et de lemmatisation. Il autorise la recherche en texte intégral et letraitement de requêtes en langage naturel. Il sert à expérimenter des techniques declassification et de segmentation destinées à améliorer la pertinence des réponsesfournies pour une requête.

Nous avons présenté à ce titre deux algorithmes appliqués sur les documentsrapportés en réponse aux requêtes. Ces algorithmes ont été utilisés conjointement àSIAC mais ils peuvent fonctionner avec n’importe quel autre logiciel fournissantune liste de documents classés par ordre de pertinence à partir d’une requête. Lapremière méthode décrite est destinée à fournir à l’utilisateur une vision plus clairedes réponses en les classant de manière thématique. Cet algorithme, basé surl’exploitation des arbres de décision, est utilisé de manière originale pour larecherche documentaire. Les résultats montrent la capacité de la méthode à isoler lesdocuments pertinents et ceci sans nécessiter des temps machine importants.

La nouvelle méthode de segmentation proposée utilise directement les résultatsdonnés par la classification. Une segmentation des documents rapportés est en effetdéduite à partir du contenu des feuilles de l’arbre de décision : si deux phrasescontiguës d’un document n’appartiennent pas à la même feuille c’est parce qu’ellestraitent de thématiques différentes. Il a ainsi été mis en lumière le fait qu’à touteclassification de sous-unités de documents (les phrases, les paragraphes…)correspond une segmentation des dits documents. En outre, cette nouvellesegmentation dépend du contenu des requêtes. Elle est plus fine que la subdivisiondu corpus en « documents ». Une seconde recherche est effectuée non plus sur lesdocuments mais sur les segments de documents. On offre alors à l’utilisateur lapossibilité d’accéder plus rapidement à l’information qu’il recherche. Si l’onconsidère que la pertinence finale d’un document est égale à la plus grande valeurde pertinence trouvée entre la requête et chacun des segments du document, onobtient une nouvelle liste ordonnée de documents. On montre que la mesure Cosine,utilisée par SIAC au cours de la première étape de recherche, n’est pas adaptée à lamesure de la ressemblance d’une requête et d’une portion de document. Lesmeilleurs résultats sont obtenus en combinant Cosine avec une variante simplifiéede la mesure Okapi. Cette méthode peut être appliquée dans les systèmes de


recherche grand public même s’il ne saurait être question de classer et de segmentertoutes les phrases de quelques dizaines ou centaines de milliers de documentstrouvés en réponse à certaines requêtes sur le WWW. Restreindre cette méthode auxmille premiers documents trouvés ne serait pas dommageable à l’utilisateur qui, detoutes façons, explore rarement une liste de documents dans son intégralité.

6. Bibliographie

[ANI 97] ANICK P.G., VAITHYANATHAN S., « Exploiting Clustering and Phrases for Context-Based Information Retrieval », Actes de ACM/SIGIR Conference on Research andDevelopment in Information Retrieval, Philadelphie, PA, USA, 1997, p. 314 à 323.

[BEL 97] BELLOT P., EL-BEZE M., « Description du système SIAC », atelier de la premièreCampagne d’Evaluation Amaryllis, Avignon, France, 1997, http://www.lia.univ-

avignon.fr/personnel/bellot.html/Recherche/biblioperso.html

[BEL 2000a] BELLOT P., « Méthodes de classification et de segmentation locales nonsupervisées pour la recherche documentaire », Thèse de doctorat, Université d’Avignon.

[BEL 2000b] BELLOT P., DE L OUPY C., « SIAC et IndeXal à Amaryllis’99 », atelier de ladeuxième Campagne d’Evaluation Amaryllis, Paris, Avril 2000.

[BIG 2000] BIGI B., DE M ORI R., EL-BÈZE M., SPRIET T., « A fuzzy decision strategy fortopic identification and dynamic selection of language models », Signal Processing,vol. 80, n° 6.

[CRA 91] CRAWFORD S., FUNG R., APPELBAUM L., TONG R., « Classification trees forinformation retrieval », Actes de 8th International workshop on Machine Learning,Northwestern university, Illinois, USA, 1991.

[DID 82] DIDAY E., LEMAIRE J., POUGET J., TESTU F., Eléments d’Analyse des Données,Dunod Informatique, 1982.

[ELB 95] EL-BÈZE M., SPRIET T., « Intégration de contraintes syntaxiques dans un systèmed’étiquetage probabiliste », T.A.L., vol. 36, n°1-2, 1995, p. 47 à 66.

[FER 98] FERRET O., GRAU B., MASSON N., « Thematic segmentation of texts : two methodsfor two kinds of texts », Actes de COLING-ACL, Montréal, Canada, p. 392 à 396.

[HAR 97] HARMAN D.K., « The TREC Conference », in [SPA 97], 1997, p. 247-256.

[HEA 96] HEARST M.A., PEDERSEN J.O., « Reexamining the Cluster Hypothesis :Scatter/Gather on Retrieval Results », Actes de ACM/SIGIR Conference on Research andDevelopment in Information Retrieval, Zurich, Suisse, 1996, p. 76-84.

[HEA 97] HEARST M.A., « Text Tiling : Segmenting Text into Multi-paragraph SubtopicPassages », Computational Linguistics, vol. 23, n° 1, p. 33 à 64.

[HEA 99] HEARST M.A., « The use of categories and clusters for organizing retrievalresults », Natural language information retrieval, Kluwer, p. 333 à 374.


[JUN 97] JUN B.H., KIM C.S., SONG H.Y., KIM J., « A New Criterion in Selection andDiscretization of Attributes for the Generation of Decision Trees », IEEE Transactions onPattern Analysis and Machine Intelligence , vol. 19, n° 12, 1997, p. 1371 à 1375.

[KLA 98] K LAVANS J., MCKEOWN K.R., KAN M.Y., « Resources for Evaluation ofSummarization Techniques », Actes de First International Conference on LanguageResources & Evaluation (LREC), Grenade, Espagne, 1998, p. 899-902.

[KOW 97] KOWALSKI G., Information Retrieval Systems - Theory and implementation ,Kluwer Academic Publishers, 1997, ISBN-0-7923-9926-9.

[KOZ 93] KOZIMA H., « Text Segmentation Based on Similarity between Words », Actes du31è congrès de Assocation for Computational Linguistics ACL, 1993, p. 286 à 288.

[KUH 95] KUHN R., DE MORI R.; « The Application of Semantic Classification Trees toNatural Language Understanding », IEEE Transactions on Pattern Analysis and MachineIntelligence, vol. 17, n°5, mai 1995, p. 449-460.

[LES 99] LESPINASSE K, KREMER P., SCHIBLER D., SCHMITT L., « Evaluation des outilsd’accès à l’information textuelle, les expériences américaine (TREC) et française(Amaryllis) », Langues, John Libbey, vol. 2, n° 2, 1999, p. 100-109.

[LOU 98] DE LOUPY C., BELLOT P., EL-BÈZE M., MARTEAU P.-F.; « Query Expansion andClassification of Retrieved Documents », Actes de Text REtrieval Conference TREC-7,Gaithersburg, USA, novembre 1998, NIST special publication 500-242, 1999, p. 443-450.

[MAA 94] M AAREK Y.S., WECKER A.J., « The librarian’s assistant : automatically organizingon-line books into dynamic bookshelves », Actes de RIAO’94, 1994, p. 233 à 247.

[MOU 96] MOULINIER I., « Une approche de la catégorisation de textes par l’apprentissagesymbolique », Thèse de doctorat, Université Paris 6.

[SAL 83] SALTON G., Introduction to Modern Information Retrieval, McGraw-Hill, 1983.

[SAL 91] SALTON G., BUCKLEY C., « Automatic Text Structuring and Retrieval -Experiments in Automatic Encyclopedia Searching », Actes de ACM/SIGIR Conference onResearch and Development in Information Retrieval, Chicago, USA, 1991, p. 14 à 20.

[SAL 94] SALTON G., ALLAN J., BUCKLEY C., « Automatic Structuring and Retrieval of LargeText Files », Communications of the ACM, vol.37, n° 2, 1994, p. 97-108.

[SCH 97] SCHÜTZE H., SILVERSTEIN C., « Projections for Efficient Document Clustering »,Actes de ACM/SIGIR Conference on Research and Development in InformationRetrieval, Philadelphie, USA, 1997, p. 74-81.

[SIL 97] SILVERSTEIN C., PEDERSEN J.O., « Almost-Constant-Time Clustering of ArbitraryCorpus Subsets », Actes de ACM/SIGIR Conference on Research and Development inInformation Retrieval, Philadelphie, USA, 1997, p. 60-66.

[SPA 97] Sparck-JONES K., WILLETT P. (eds), « Readings in information retrieval », MorganKaufmann Publishers Inc., 1997, ISBN-1-55840-454-5.

[VAN 79] VAN RIJSBERGEN C. J., Information Retrieval, Buttherwords, London, 1979.


[WEI 96] WEISS R., BIENVENIDO V., SHELDON M.A., NAMPREMPRE C., SZILAGYI P., DUDA

A., GIFFORD D., « A hierarchical network search engine that exploits content-linkhypertext clustering », Actes de ACM Conference on Hypertext, 1996, p. 180 à 193.

[YAA 97] Y AARI Y., « Segmentation of Expository Texts by Hierarchical AgglomerativeClustering », Actes de RANLP-97, Tzigov Chark, Bulgarie, 1997, p. 59 à 65.

Article reçu le 7 juin 1999Version révisée le 30 décembre 1999

Rédacteur responsable : Bernard LEVRAT

Patrice Bellot est docteur et ingénieur en Informatique. Il est actuellement Maître deconférences à l’Université d’Avignon. Ses travaux au sein du Laboratoire d’Informatiqued’Avignon concernent le traitement automatique de la langue naturelle écrite et plusparticulièrement la recherche documentaire, la classification et la segmentation de textes. Ila créé le système de recherche documentaire SIAC qui a participé aux campagnesd’évaluation TREC et Amaryllis.

Marc El-Bèze est actuellement professeur des Universités en Informatique. Après avoirobtenu une maîtrise de lettres en 1977 à Paris 7, il a enseigné dans divers organismes deformation permanente. Ayant intégré l’IIE en 1981, il en est sorti en 1984 avec le diplômed’ingénieur CNAM en Informatique. Les recherches qu’il a menées de 1983 à 1993 au CentreScientifique d'IBM-France lui ont permis de devenir docteur en Informatique Fondamentaleen 1990 et de passer son habilitation à diriger des recherches en 1993. Depuis cette date, lestravaux qu’il encadre au Laboratoire d’Informatique d'Avignon (dont il a assuré la directionde 1997 à 1999) concernent le traitement automatique de la langue naturelle orale et écrite.