2.1 – Analyse formelle de concepts

4L’AFC est une approche mathématique pour l’analyse de données qui exploite la théorie des treillis. Un contexte formel est un triplet , où G est un ensemble d’objets, M un ensemble de propriétés et I la relation sur G × M exprimant qu’un objet possède une propriété (Ganter et al., 1999). Le tableau 1 donne un exemple de contexte : G est un ensemble de 6 documents (d₁,…,d₆) et M un ensemble de 7 propriétés qui sont des mots-clés décrivant les documents. Un concept formel est une paire (I, E), où E est l’ensemble maximal d’objets (appelé extension) possédant toutes les propriétés de I, et I est l’ensemble maximal des propriétés (appelé intension) partagées par tous les objets de E. Par exemple, la paire ({IR, MoteurDeRecherche, Web}, {d₁, d₂, d₃}) correspondant au concept formel 3, présenté en figure 1.

Tableau 1

Un contexte formel de 6 documents décrits par 7 propriétés

d1 d2 d3 d4 d5 d6 Web × × × × IR × × × × × MoteurDeRecherche × × × × × Annuaire × × Yahoo! × Altavista × Google ×

Un contexte formel de 6 documents décrits par 7 propriétés

5De plus, l’ensemble de tous les concepts formels du contexte est partiellement ordonné par l’inclusion des extensions. Cette relation dite de spécialisation entre concepts est notée est un treillis complet, appelé treillis de concepts. Le treillis peut être représenté par un diagramme de Hasse dans lequel les nœuds sont les concepts et les arêtes, les liens de spécialisation/généralisation.

Figure 1

Le treillis de concepts correspondant au contexte formel donné dans le tableau 1

Le treillis de concepts correspondant au contexte formel donné dans le tableau 1

6La figure 1 illustre le treillis de concepts correspondant au contexte formel donné dans le tableau 1. Le concept le plus général (le concept 0) contient tous les documents ; son intension est vide car aucune propriété n’est commune à tous les documents. De façon duale, le concept le plus spécifique (le concept 7) est défini par l’ensemble de toutes les propriétés. Dans notre exemple, son extension est vide, car aucun document n’est décrit par toutes les propriétés. De nombreux algorithmes ont été proposés pour la construction de treillis de concepts (cf. (Ganter et al., 1999)). Pour notre application, nous utilisons la plate-forme Coron [1], qui implémente une large collection d’algorithmes pour la fouille de données symboliques, incluant des algorithmes de construction de treillis de concepts (Szathmary et al., 2005).

2.2 – L’analyse formelle de concepts pour la recherche d’information

7L’AFC a été appliquée pour résoudre des problèmes importants liés à la mise en œuvre des SRI ; un état de l’art concernant l’utilisation de l’AFC en RI est présenté dans (Carpineto et al., 2004). L’idée phare est que l’intension d’un concept est vue comme une requête et son extension contient les documents, réponses à la requête. De plus, les concepts voisins d’un concept requête peuvent être vus comme les changements minimaux pour une reformulation de requête. Le système Refiner (Carpineto et al., 1998) exploite ces propriétés pour ne construire que la partie du treillis autour d’un concept requête et la présenter à l’utilisateur.

8Les treillis de concepts sont également de bons candidats pour des systèmes de recherche d’information hybrides exploitant conjointement un accès par requête et un accès par navigation. La requête de l’utilisateur est classifiée dans le treillis. Ce concept est le point d’entrée pour naviguer dans la structure hiérarchique.Un avantage de la navigation à partir de treillis est qu’un concept—et les documents qui lui sont associés—sont accessibles par plusieurs chemins, en raison de l’héritage multiple entre les concepts. Cette approche a été appliquée à la gestion de courriers électroniques par les systèmes CEM (Conceptual Email Manager) (Cole et al., 2000) et MailSleuth (Cole et al., 2003), à la gestion d’images par les systèmes ImageSleuth (Ducrou et al., 2006) et Camelis (Ferré, 2007), ou encore à la consultation de catalogues de DVD (Ducrou, 2007). Dans le cadre d’une navigation à partir de treillis, (Carpineto et al., 1996) et (Cole et al., 2003) proposent également d’améliorer la structure du treillis, en exploitant une hiérarchie de spécialisation (thésaurus) sur l’ensemble des termes décrivant les documents.

9Deux fonctionnalités spécifiques pour interroger et naviguer dans un treillis sont proposées par le système ImageSleuth (Ducrou et al., 2006). La première fonctionnalité est la requête par l’exemple. Cette fonctionnalité calcule les propriétés communes à un ensemble d’objets, qui représente l’ensemble des exemples. Puis, les objets qui possèdent toutes les propriétés communes sont retournés à l’utilisateur. La seconde fonctionnalité est une mesure de similarité entre concepts. La similarité entre deux concepts est mesurée à partir des intensions et extensions des deux concepts. Deux concepts sont proches, si peu d’objets et peu de propriétés n’appartiennent qu’à l’un des deux concepts. Ainsi, étant donnés deux concepts C₁(I₁, E₁) et C₂(I₂, E₂) d’un contexte formel , (Ducrou et al., 2006) définissent la similarité par 1 – d(C₁, C₂), avec :

10

11Cette mesure de similarité est utilisée par ImageSleuth pour calculer une liste ordonnée de concepts similaires à un concept donné.

12Des approches à partir de treillis ont également été proposées pour le classement de documents (ranking, en anglais) (Carpineto et al., 2000), considérant que plus les concepts du treillis sont proches du concept représentant la requête, plus les documents appartenant à leur extension sont pertinents. Dans ce but, (Carpineto et al., 2000) utilisent une distance fondée sur la structure du treillis. La mesure de similarité proposée par (Ducrou et al., 2006) pour classer tous les concepts d’un treillis, par comparaison avec le concept requête est une autre possibilité.

13Dans la section suivante, nous détaillons des systèmes, tels que Credo (Carpineto et al., 2004), Fooca (Koester, 2006) et SearchSleuth (Ducrou et al., 2007), qui exploitent les treillis pour la ré-organisation et la fouille de documents du web.

2.3 – Le web : un cadre particulier d’application de l’AFC à la recherche d’information

Figure 2

Un document Google retourné pour une requête sur “leopard”

Un document Google retourné pour une requête sur “leopard”

14Le web est un terrain attractif pour la RI à partir d’AFC. Le système Credo (acronyme de conceptual reorganisation of documents) (Carpineto et al., 2004) (ou son adaptation Credino pour les PDA (Carpineto et al., 2006)) exploitent les treillis pour organiser l’ensemble des documents retournés par Coogle à une requête donnée et permettre à l’utilisateur de naviguer dans cet ensemble. Chaque document fourni en réponse par Google, tel que celui donné en illustration en figure 2, est caractérisé d’un titre, d’un extrait et d’un URL. Les mots qui constituent le titre et l’extrait des documents font office de propriétés.

15Un problème de la construction de treillis à partir de données textuelles est la génération d’un trop grand nombre de concepts. Ce problème résulte d’une combinatoire élevée dans la cooccurence de mots dans les documents, qui, dans Credo, a été traité par un processus de construction de la hiérarchie en deux étapes :

1. Le niveau le plus élevé de la hiérarchie est le premier niveau du treillis construit à partir du contexte (documents, mots des titres, I) où I est la relation statuant qu’un document possède un mot dans son titre. Ainsi, les mots du titre sont également considérés comme étant plus significatifs comparés aux mots des extraits.
2. Un autre contexte (documents,(mots des titres et des extraits),I’) où I’ est la relation statuant qu’un document possède un mot dans son titre ou dans son extrait, considère également les mots de l’extrait pour construire les niveaux suivant de la hiérarchie.

16Une exploitation par AFC des documents retournés en réponse par un moteur de recherche du web, avec l’objectif d’améliorer la RI sur le web, est également mise en œuvre dans deux autres systèmes :

• FooCA (Koester, 2006) permet d’appréhender le contexte associé aux documents, le présentant sous la forme d’un tableau comme celui présenté en tableau 1. Le treillis obtenu à partir du contexte est également visualisable sous la forme d’un graphique. De nombreuses options permettent de contrôler la création de ce contexte (nombre de documents demandés au moteur de recherche, nombre minimum d’objets par propriétés, utilisation ou non d’une lemmatisation, suppression ou non de mots vides, etc.). L’utilisateur peut reformuler son besoin en modifiant sa requête initiale. Il peut ainsi ajouter un mot supplémentaire connecté par l’opérateur booléen ET pour préciser sa requête, ou l’opérateur SAUF pour réaliser un filtrage. Le processus de construction du contexte et du treillis est réitéré sur l’ensemble de documents obtenu en réponse à la nouvelle requête.
• SearchSleuth (Ducrou et al., 2007) se focalise exclusivement sur la reformulation de requête. La classique interface de recherche— à un champ— des moteurs de recherche du web est étendue pour proposer des reformulations potentielles à l’utilisateur. La requête de l’utilisateur est soumise à un moteur de recherche du web. Les documents retournés servent à construire un treillis qui est exploité pour proposer des reformulations de la requête. Soit R la requête de l’utilisateur et C_R le concept représentant la requête dans le treillis. À l’instar de Refiner, les concepts génériques les plus spécifiques de C_R et les concepts spécifiques les plus généraux de C_R servent à proposer des termes pour généraliser ou spécialiser la requête. La mesure de similarité entre concepts introduite dans (Ducrou et al., 2006) sert à proposer d’autres reformulations potentielles.

2.4 – Un processus de recherche d’information itératif et interactif

17L’objectif d’un SRI est de fournir à un utilisateur de l’information relative à un certain besoin. Dans la plupart des SRI, et en particulier dans les moteurs de recherche du web, le processus de RI consiste à soumettre une requête représentant le besoin de l’utilisateur. Mais, comme une requête est une représentation réduite du besoin de l’utilisateur, certains SRI exploitent de l’information additionnelle. Le contrôle de pertinence (relevance feedback, en anglais) (Rocchio, 1971), dans lequel l’utilisateur émet des jugements à partir d’un premier résultat du SRI, est une façon de fournir des informations supplémentaires qui permettent d’améliorer la précision de la recherche (Salton et al., 1990).

18Il existe deux grandes catégories de contrôle de pertinence : le contrôle de pertinence explicite et le contrôle de pertinence implicite. Dans le cas d’un contrôle de pertinence explicite, l’utilisateur doit explicitement exprimer son contrôle au système, par exemple, en entrant des mots-clés complémentaires, en répondant à des questions spécifiques, en identifiant des sous-ensembles de documents pertinents et/ou non pertinents (Kassab et al., 2005), en annotant des documents (Dmitriev et al., 2006), etc. Dans le cas d’un contrôle de pertinence implicite, les SRI ne proposent pas d’interactions spécifiques pour le contrôle. Le contrôle de pertinence est déduit par le SRI à partir de toutes les interactions implicites de l’utilisateur (Shen et al., 2005). Par exemple, dans un système utilisant une formulation du besoin par requête, les résultats retournés en réponse à la première requête peuvent ne pas être satisfaisants. Souvent, l’utilisateur va interagir avec le système pour modifier sa requête initiale ou visualiser certains documents dans la liste des réponses produite. Toutes ces interactions peuvent être exploitées pour le contrôle de pertinence. La reformulation de requête peut, par exemple, désambiguïser le contexte de mots polysémiques (Dumais et al., 2004). Nous renvoyons à (Kelly et al., 2003) pour une classification des techniques de contrôle de pertinence implicite et leur exploitation dans les travaux majeurs du domaine.

19Le processus de RI proposé dans Crechaindo implémente un contrôle de pertinence explicite. L’utilisateur interagit itérativement avec le système pour évaluer si un concept du treillis est pertinent ou non, par rapport à son besoin. Son jugement sert à modifier le contexte utilisé pour construire le treillis.

3.1 – Principes

20Pourmettre en œuvre l’itérativité et l’interactivité du processus de RI, Crechaindo [2] intègre une modification dynamique du contexte. À la première étape du processus de RI, l’utilisateur soumet une requête et un treillis est construit. Par la suite, l’utilisateur va émettre une appréciation sur certains concepts du treillis. Dans ce but, Crechaindo propose des possibilités d’interaction, à l’instar des SRI dans lesquels l’utilisateur peut accepter/rejeter des documents ou ensembles de documents. Avec Crechaindo, l’utilisateur peut sélectionner, dans le treillis, les concepts qui sont pertinents et ceux qui ne le sont pas.

21

Définition 1 Un concept C est pertinent, si l’utilisateur estime qu’une requête Q, formée de la conjonction de tous les mots composant l’intension de C, est susceptible de retourner de nouveaux documents pertinents.

22L’idée sous-jacente de cette définition est que le treillis ne contient pas forcément, à un instant donné, tous les documents pertinents qui pourraient être trouvés sur le web, et qu’une nouvelle interrogation d’un moteur de recherche avec la requête Q peut retourner de nouveaux documents pertinents. En effet, la requête initiale n’est souvent pas parfaite ; l’utilisateur doit la reformuler et/ou la compléter pour préciser son besoin. La navigation dans le treillis guide par ailleurs l’utilisateur pour cette reformulation.

23

Définition 2 Un concept est non pertinent si l’utilisateur estime que tous les documents contenus dans son extension ne sont pas pertinents.

24Crechaindo propose à l’utilisateur de sélectionner les concepts pertinents et non pertinents. Dans l’interface (cf. figure 3) chaque concept de la hiérarchie est précédé de deux icônes ; l’utilisateur pourra cliquer sur :

25

26Chacune des actions de l’utilisateur modifie le contexte et un nouveau treillis est calculé. Dans Crechaindo, le processus de RI est ainsi une succession de contexte : K₀ ? K₁ ? … ? K_i ? K_i+1 ? …, avec K_i = (G_i, M_i, I_i), le contexte de l’étape i. K₀ = (G₀,M₀, I₀) est le contexte initial vide : G₀ = Ø, et par conséquent M₀ = Ø et I₀ = Ø.

27Nous détaillons maintenant comment le contexte est modifié durant le processus de RI.

3.2 – Extension de contexte

28L’objectif d’une extension de contexte est d’améliorer la précision de la RI, par la recherche de nouveaux documents, ainsi que d’affiner la structuration de la hiérarchie par la prise en compte de ces nouveaux documents dans la construction du treillis.

29Soit Q une requête utilisateur. Q est un ensemble non vide de mots : Q = {mot_i | i > 0}. Soit DOC(Q) l’ensemble des documents retournés par un moteur de recherche pour la requête Q : DOC(Q) = {doc_j | j ? 0}.

30

Définition 3 L’extension du contexte K_i au contexte K_i+1, noté , est réalisée en ajoutant les réponses retournées par un moteur de recherche pour la requête Q :

• les nouveaux documents sont ajoutés à l’ensemble d’objets du contexte : G_i+1 = G_i ? DOC(Q) ;
• les nouveaux mots sont ajoutés à l’ensemble des propriétés du contexte :M_i+1 = M_i ? {mot_i|i ? DOC(Q)} ;
• la relation I_i entre G_i et M_i est étendue à la relation I_i+1 d’appartenance des mots (de M_i+1) aux documents (de G_i+1).

31Dans un contexte K_i+1 qui vient d’être étendu, les objets de G_i sont décrits exactement avec les mêmes propriétés. C’est pourquoi, pour tous les (g,m) ? I_i, si g ? G_i+1 alors (g,m) ? I_i+1. Pour tous les concepts (g_i,m) ? K_i, il existe un concept (g_i+1,m) ? K_i+1 avec g_i ? g_i+1. Ainsi, on retrouve à l’étape i + 1 tous les concepts de l’étape i modifiés éventuellement par une augmentation de leur extension en raison des nouveaux documents introduits dans le contexte, et par conséquent, dans le treillis. Cette évolution progressive du treillis entre deux étapes permet à l’utilisateur de retrouver les concepts vus à l’étape précédente.

32Il y a deux cas dans lesquels le contexte est étendu :

1. l’utilisateur soumet une nouvelle requête : la requête définit un nouveau contexte, mais l’utilisateur peut également introduire à n’importe quel moment du processus de RI une nouvelle requête Q_i entre deux étapes ( K_i+1), ajoutant de nouveaux mots dans la formulation de sa recherche ;
2. l’utilisateur évalue un concept C comme étant pertinent pour sa recherche : une requête composée de la conjonction de tous les mots de l’intension de C est soumise à un moteur de recherche, le contexte est étendu par .

3.3 – Réduction de contexte

33L’objectif d’une réduction de contexte est d’éliminer dans le treillis, les informations — concepts et documents — non pertinentes pour l’utilisateur. Une réduction est appliquée à chaque fois que l’utilisateur évalue un concept comme étant non pertinent. Les documents rattachés à ce concept, qui par définition ne sont plus pertinents, ne sont plus pris en compte dans la construction de la hiérarchie ; ce qui est un moyen de la nettoyer.

34(Nauer et al., 2007) proposent une réduction de contexte également sur les propriétés. Ainsi, les mots qui sont spécifiques à l’intension d’un concept non pertinent sont ajoutés à la liste des mots vides et sont supprimés du contexte pour toujours. Cependant, comme il est extrêmement difficile pour l’utilisateur de statuer, a priori, du rôle qu’un mot peut jouer dans les documents qui pourraient satisfaire son besoin—et, par extension, dans la construction du treillis —, nous avons choisi de réduire le contexte uniquement par élimination des documents non pertinents. Plusieurs raisons font que l’utilisateur est incapable de juger de la non-pertinence d’un mot : par exemple, un mot peut être polysémique (i.e avoir plusieurs sens dans des contextes différents), ou encore, l’utilisateur peut ignorer le sens d’un mot ou peut ne pas comprendre pourquoi un mot apparaît dans un concept.

35

Définition 4 La réduction du contexteK_i au contexteK_i+1, notée , est réalisée comme suit :

• les documents appartenant à l’extension de C sont supprimés du contexte : G_i+1 = G_i extension(C) ;
• la relation I_i+1 entre G_i+1 et M_i+1 est obtenue en supprimant de I_i les relations concernant les documents appartenant à extension(C).

36Éliminer seulement les documents, plutôt que les documents et les propriétés, est moins ambigu pour l’utilisateur qui doit décider si un concept est non pertinent. En effet, si tous les documents appartenant à l’extension d’un concept sont non pertinents, il est évident qu’ils peuvent être supprimés du contexte. De plus, le résultat arborescent n’est pas très différent de celui obtenu dans (Nauer et al., 2007) : la branche enracinée sur un concept non pertinent est supprimée, car les documents associés à cette branche ont été supprimés. D’un autre côté, contrairement à (Nauer et al., 2007), un mot peut désormais apparaître, dans un premier temps, dans l’intension d’un concept non pertinent, puis, par la suite, dans l’intension d’un concept pertinent.

3.4 – Réinitilisation du contexte

37Réinitialiser le contexte permet à l’utilisateur de démarrer une nouvelle session de RI. En effet, chaque nouvelle soumission de requête ou chaque jugement d’un concept pertinent étend le contexte par adjonction de documents. Cependant, il est possible de réinitialiser le contexte, pour repartir d’un contexte vide K₀ = (G₀,M₀, I₀), avec G₀ = Ø, M₀ = Ø and I₀ = Ø. Le lien “delete history” dans la partie historique de l’interface (voir section suivante), permet à l’utilisateur d’effectuer cette réinitialisation.

3.5 – Description de l’interface

Figure 3

L’interface de Crechaindo, après la requête “leopard”

L’interface de Crechaindo, après la requête “leopard”

38L’interface utilisateur (cf. figure 3) est divisée en 4 parties :

• tout en haut, l’interface d’interrogation permet à l’utilisateur de soumettre une requête et de spécifier quelques paramètres tels que le nombre de documents souhaités en réponse de l’interrogation Google. Deux paramètres associés à la construction de la hiérarchie et de son affichage sont disponibles : le nombre maximal de concepts (Mnc) affichés à chaque niveau de la hiérarchie et le nombre minimal de documents (mnd) contenus dans l’extension des concepts (cette valeur peut être exprimée par un nombre ou en pourcentage du nombre de documents de contexte). L’objectif de ces 2 paramètres est de restreindre le nombre de concepts qui sont affichés à l’utilisateur ; la taille des treillis construits étant importante (généralement de l’ordre de 300 concepts pour 100 documents retournés en réponse par Google).
• au milieu de l’interface, la hiérarchie résultant d’un parcours en profondeur du treillis présente, sous forme d’arbre, l’intension des concepts précédée du nombre de documents appartenant à leur extension. Tous les concepts du treillis satisfaisant les paramètres Mnc et mnd sont affichés. Certains concepts apparaissent plusieurs fois en raison de l’héritage multiple dans le treillis et du choix d’affichage d’une hiérarchie dépliée,
• dans la partie droite de l’interface, une division est dédiée à l’affichage des documents associés à chacun des concepts. Le contenu de cette division est modifiée dynamiquement quand l’utilisateur passe la souris sur un des concepts de la hiérarchie. Tous les documents appartenant à l’extension du concept survolé sont affichés.
• dans la partie gauche, une division retrace l’historique des actions de l’utilisateur : requêtes soumises, évaluation de concepts pertinents et non pertinents. Dans le futur, cette division a pour objectif de permettre à l’utilisateur de revenir en arrière sur certaines de ses décisions, comme cela est présenté dans le moteur de recherche Exalead [3].

3.6 – Implémentation de Crechaindo

39L’architecture de Crechaindo est donnée en figure 4. Crechaindo interroge Google qui retourne une page HTML contenant le résultat de la requête. Pour l’instant, la langue d’interrogation est obligatoirement l’anglais ; le résultat est constitué d’un ensemble de documents écrits en anglais. La page HTML est analysée pour extraire l’ensemble des documents, tels que celui présenté en figure 2. Pour chaque document, le titre, l’extrait et l’URL sont extraits. Les nouveaux documents sont ajoutés à G_i (l’URL est utilisé comme clé pour éliminer les documents doublons). Crechaindo créé le contexte à partir de données textuelles selon l’approche classique d’indexation automatique proposée par (van Rijsbergen, 1979). Chaque document (titre et extrait) est segmenté en mots. Les variations flexionnelles de type singulier/pluriel sont traitées en utilisant les principales règles de variations de l’anglais : le s terminal (day?days, etc.), an ? en (man ? men, etc.), y ? ies (baby ? babies, etc.), fe? ves (wife ?wives, etc.), etc. Étant donné ces règles, le vocabulaire est normalisé en ne gardant que la forme la plus fréquente des mots apparaissant à la fois au pluriel et au singulier, pour éviter la dispersion du vocabulaire. Le treillis est d’ailleurs directement affecté par une consolidation de certaines extensions de concepts. Pour finir, nous utilisons une liste de mots vides récupérée du projet Snowball (SNO 2008) pour éliminer les mots grammaticaux (comme “a”, “the”, “of”, etc.). Les mots restant sont utilisés pour créer le contexte documents × mots (il n’y a pas de sélection spécifique de mots). Une fois le contexte construit, Coron (Szathmary et al., 2005) est utilisé pour calculer le nouveau treillis et une page HTML/javascript est générée et est envoyée à l’interface web de l’utilisateur.

Figure 4

L’architecture de Crechaindo

L’architecture de Crechaindo

40En cas de réduction de contexte, c’est-à-dire si l’utilisateur évalue un concept C comme étant non pertinent, les documents appartenant à extension(C) sont supprimés de l’ensemble des documents servant à créer le contexte, la procédure de production de la page HTML/javascript résultat étant identique.

4.1 – Rejeter un concept non pertinent

43Supposons que l’utilisateur ne soit pas intéressé par les documents relatifs au système d’exploitation de Macintosh. Par conséquent, le concept C avec intension(C) = {leopard, os}, est un concept non pertinent, car son extension ne contient que des documents relatifs au système d’exploitation de Macintosh. Cliquer sur situé devant “leopard, os” dans l’interface utilisateur produit la hiérarchie K2 présentée en figure 6.

44La hiérarchie K₂ ne contient maintenant plus que 71 documents. Dans une visualisation arborescente du treillis, l’effet obtenu par rejet d’un concept non pertinent C est une suppression de la branche enracinée en C. Mais dans le treillis, les concepts de la branche sont soit détruits, soit ajustés si un héritage multiple les rattache à une autre partie du treillis. L’ajustement prend la forme d’une suppression, dans les concepts de la branche, des mots qui ont disparus du contexte suite à l’élimination des documents non pertinents (il s’agissait de mots uniquement présents dans les documents non pertinents). Éliminer des documents et, par conséquence, des termes du contexte peut affecter l’ensemble de la hiérarchie. Comme illustré en figure 5, tous les sous-arbres encadrés par des pointillés ont été supprimés et certaines extensions de concepts ont été réduites. Par exemple, 3 documents ont été supprimés dans l’extension du concept “leopard, system”. Le concept “leopard, mac” a disparu de la partie de la hiérarchie qui est affichée à l’utilisateur en raison de sa nouvelle extension qui contient quatre documents, ce qui ne satisfait plus les critères d’affichage. Mais le concept est toujours dans le treillis.

4.2 – Accepter un concept pertinent

45Soit C, tel que intension(C) = {leopard, cats} un concept pertinent du treillis issu de K₂. Cliquer sur situé devant C dans l’interface utilisateur produit la hiérarchie K₃ présentée en figure 7.

4698 nouveaux documents ont été ajoutés. Les nouveaux mots introduits par les nouveaux documents ont permis la construction d’un treillis dans lequel le concept “leopard, cats” a été décomposé en plusieurs sous-concepts. De plus, d’autres parties de la hiérarchie ont été structurées plus finement : certaines espèces, origines ou caractéristiques de léopards sont proposées.

4.3 – Soumission d’une nouvelle requête

47Durant le processus de RI, l’utilisateur doit quelquefois reformuler son besoin par lui-même. Dans Crechaindo, chaque nouvelle requête soumise au système va contribuer à ajouter des documents au contexte. Par exemple, la partie de la hiérarchie présentée en figure 8 est obtenue par extension de K₃ par une nouvelle requête sur “leopard species” :

Figure 7

Une partie de hiérarchie de K₃, après

Une partie de hiérarchie de K₃, après

4.4 – Rechercher une aiguille dans une meule de foin

48Crechaindo favorise également l’accès à un grand nombre de documents. Premièrement, le treillis est capable de synthétiser et de structurer ces documents, les rendant plus faciles à appréhender par l’utilisateur. Deuxièmement, le processus itératif de Crechaindo est très utile pour trier et filtrer les résultats retournés par un moteur de recherche sur des requêtes ambiguës. Par exemple, la figure 9 illustre la dynamique du processus de Crechaindo pour gérer 500 documents résultant d’une requête sur “jaguar”, qui, comme “leopard”, est un mot dont les acceptions sont variées. L’utilisateur est satisfait du résultat s’il s’intéresse aux voitures : “jaguar, cars”, “jaguar, models”, “jaguar, club”, “jaguar, prices”, etc. Mais si l’utilisateur recherche des informations sur le système d’exploitation jaguar de Macintosh, sur le système de jeu jaguar d’Atari ou sur le félin nommé jaguar, le résultat est mauvais. Tous les concepts affichés concernent l’acception voiture (en anglais, car) dumot jaguar. Mais, comme l’utilisateur a l’opportunité de rejeter des concepts non pertinents, le treillis peut rapidement être nettoyé pour se focaliser sur des concepts pertinents. Supposons que l’utilisateur n’est pas intéressé par les voitures. La hiérarchie de K₂, dans la partie supérieure droite de la figure 9, est obtenue après rejet du concept “jaguar, cars”. En seulement un clic, l’utilisateur a supprimé 135 documents non pertinents. Un concept avec l’acception félin/chat sauvage apparaît désormais. En rejetant à nouveau des concepts relatifs à l’acception voiture, la hiérarchie se focalise sur les autres sens du mot jaguar. La hiérarchie en bas à droite de la figure 9 présente la hiérarchie après avoir rejetés tous les concepts relatifs à la voiture, tels “jaguar, vehicules”, “jaguar, models”, “jaguar, type”, “jaguar design”, etc. La hiérarchie, plutôt bruitée à l’origine, a été nettoyée en quelques clics. Des concepts sur le système d’exploitation deMacintosh, sur le système de jeu Atari ou encore sur les félins refont surface.

Figure 8

Une partie de hiérarchie de K₄, après

Une partie de hiérarchie de K₄, après

4.5 – Discussion

49Trois types d’interaction potentielle sont disponibles dans Crechaindo.

50Rejeter un concept non pertinent est très utile lorsque le treillis contient des concepts qui ne se focalisent pas immédiatement sur des informations satisfaisant l’utilisateur. Les concepts non pertinents sont souvent issus de requêtes avec des termes polysémiques, ou en raison d’une forte dispersion du vocabulaire dans les extraits de documents retournés par Google. Pour limiter ce problème, construire les concepts à partir d’un ensemble limité de propriétés—tel que cela est fait dans Credo pour le premier niveau de la hiérarchie— est une solution possible. Mais dans ce cas, des documents et des concepts non pertinents sont toujours présents dans la hiérarchie. C’est pourquoi, il y a un réel besoin de nettoyer la hiérarchie. Et, éliminer le bruit permet — indirectement — de se focaliser sur les éléments (concepts et documents) pertinents.

Figure 9

Illustration de la dynamique du processus de filtrage d’un grand ensemble de documents. La hiérarchie de K₁, en partie gauche, est obtenue après K₁, avec 500 documents retournés par Google. La hiérarchie de K₂, dans la partie supérieure, à droite, est obtenue après . La hiérarchieK₉, dans la partie inférieure, à droite, est obtenue après plusieurs étapes, en rejetant les concepts relatifs à l’acception voiture (en anglais car) du mot jaguar, i.e

Illustration de la dynamique du processus de filtrage d’un grand ensemble de documents. La hiérarchie de K₁, en partie gauche, est obtenue après K₁, avec 500 documents retournés par Google. La hiérarchie de K₂, dans la partie supérieure, à droite, est obtenue après . La hiérarchieK₉, dans la partie inférieure, à droite, est obtenue après plusieurs étapes, en rejetant les concepts relatifs à l’acception voiture (en anglais car) du mot jaguar, i.e

51Accepter un concept pertinent est un moyen d’introduire de nouveaux documents, plus spécifiques que ceux déjà obtenus jusqu’à présent, dans le contexte. Ceci est une extension significative de Credo qui produit une hiérarchie limitée en profondeur et dont le degré de spécialisation des concepts est également limité. En effet, dans Credo, le treillis est construit seulement sur 100 documents et le vocabulaire de ces documents ne couvre par nécessairement toute la variété de sujets en lien avec les mots employés pour interroger le système. De plus, l’extension de certains concepts peut être très petite, en raison de la distribution des 100 documents dans l’ensemble des concepts. Dans Crechaindo, si un concept C contient peu de documents—comme cela est le cas pour les concepts les plus bas dans la hiérarchie— accepter C étend la sous-hiérarchie de racine C. Des sous-concepts plus spécifiques que C seront générés par la construction d’un nouveau treillis. Ainsi, la profondeur de la hiérarchie et le degré de spécialisation sont moins limités, en comparaison avec le système Credo.

52Soumettre une nouvelle requête offre à l’utilisateur un moyen de reformuler son besoin par lui-même, sans être restreint par les concepts du treillis initial. Ainsi, l’utilisateur peut soumettre de multiples requêtes au système et toutes les réponses retournées par Google seront synthétisées dans une même hiérarchie. Cette approche semble intéressante pour fusionner les résultats provenant de multiples reformulations de requêtes et peut probablement être appliqué pour fusionner les résultats provenant de multiples sources d’information comme cela est fait, par exemple, par un métamoteur de recherche.

4.6 – Perspectives

53L’AFC fournit une approche intéressante pour gérer des documents du web et améliorer la RI sur le web. Crechaindo, qui est un prototype de recherche, montre l’intérêt d’adapter l’approche de l’AFC à la RI sur le web conjointement à la prise en compte de l’interaction avec l’utilisteur. Cependant, certains de nos choix pour construire un système de RI sur le web exploitant de l’AFC doivent être étudiés. Par exemple, quels sont les impacts de nos choix de modifications de contexte sur le processus de RI ? L’extension de contexte à partir de tous les mots formant l’intension d’un concept pertinent est peut-être trop réductrice : une extension de contexte à partir des mots spécifiques de l’intension du concept pertinent (i.e mots qui ne sont pas hérités des concepts génériques) peut être une alternative. De même, des alternatives existent pour la réduction de contexte qui actuellement se fait par élimination des documents rattachés à un concept non pertinent. Par exemple, une nouvelle interrogation de Google avec une requête composée de termes positifs (termes saisis par l’utilisateur) et de termes négatifs (termes spécifiques que l’utilisateur souhaite éliminer) pourraient enrichir l’ensemble des documents.

54La qualité des hiérarchies, construites par différentes stratégies telles que celles proposées dans Credo et Crechaindo, doit également être étudiée car celles-ci sont au cœur de ce type de processus de RI. L’étude de la similarité des concepts ainsi que de l’organisation spécifique de certains concepts dans le treillis est une façon d’améliorer la qualité de la hiérarchie. Par exemple, dans la figure 5, le concept “leopard, os, mac” et ses sous-concepts apparaissent deux fois car “leopard, os, mac” est subsumé par les deux concepts “leopard, os” et “leopard, mac”. Nous reconnaissons que l’héritage multiple favorise l’accès à un concept, qui est ainsi atteignable par plusieurs chemins. Néanmoins, l’intérêt de présenter à l’utilisateur les deux concepts “leopard, os” et “leopard, mac” peut être discuté en raison de (1) leurs connections avec le concept “leopard, os, mac” et de (2) la forte similarité de leurs extensions (contenant respectivement 29, 28 and 24 documents). De plus, cette situation découle directement de l’exploitation des extraits de documents, dont les limites ne sont pas suffisamment larges pour couvrir les trois mots leopard, mac et os. Mais ces trois mots, absents des extraits, apparaissent dans les 29 et 28 documents intégraux rattachés aux concepts “leopard, os” et “leopard, mac” !

55Finalement, une direction de recherche attractive concerne le potentiel de synthèse des treillis sur un ensemble de résultats de recherche. Cette approche peut être appliquée pour une même requête soumise à plusieurs moteurs de recherche (comme cela est fait par les métamoteurs), ou aussi pour un ensemble de requêtes soumis à un même moteur. Nous envisageons cette dernière possibilité pour mettre en œuvre un contrôle de pertinence implicite (Rieh et al., 2006) dans Crechaindo, à partir des interactions utilisateurs stockées dans l’historique. Par exemple, l’ensemble des mots positifs (extraits des requêtes de l’utilisateur et des concepts pertinents) et l’ensemble des mots négatifs (extraits des concepts non pertinents) pourraient servir à déterminer automatiquement—par conjonction sur les mots positifs et filtrage sur tous les mots négatifs — un ensemble de requêtes pour interroger Google. Nous espérons que l’ensemble des documents retournés par ces requêtes améliore la structure de la hiérarchie.