La multiplication des sources de donn�es, souvent h�t�rog�nes, au niveau du Web a suscit� un regain d?int�r�t pour l?int�gration des donn�es. Notre travail s?inscrit dans ce contexte. Nous proposons une solution pour rechercher les sources pertinentes au vu d?une requ�te utilisateur.
Cette solution peut �tre per�ue aussi bien comme un composant interne d?un syst�me de m�diation que comme un syst�me de recherche d?information sp�cialis�.
Les sources de donn�es que nous consid�rons sont toutes du m�me domaine (le tourisme). Nous les avons annot�es � l?aide de termes issus d?une ontologie de ce domaine. Nous avons propos� pour la recherche un algorithme bas� sur les treillis de Galois. Cet algorithme permet une classification formelle des sources de donn�es et les r�sultats qu?il retourne sont class�s par ordre de pertinence.
Pour valider notre solution, nous l?avons impl�ment�e � l?aide du langage Java pour un cas d?�tude d?une trentaine de sources de donn�es et d?une vingtaine de termes de l?ontologie.
The multiplicity of data sources, often heterogeneous, like the ones used for the web renews interest in data integration. In this context, we present a solution that searches multiple data sources and extracts relevant information as a response to a client query. Our solution can be either seen as an internal component of a mediation system or as a stand-alone information retrieval system.
The data sources we have considered are all related to the same domain; which is ?Tourism?. We annotated them according to this domain ontology. The search method we adopted used a clustering technique based on concept lattices. This algorithm allows formal classification of data sources and the results it returns are ordered by degree of pertinence.
To validate our solution, we implemented it as a Java application for a case study with about thirty data sources and twenty terms issued from the ontology.
L?utilisateur des syst�mes d?information, tant au niveau du Web qu?au niveau de l?entreprise, se trouve face � une multiplicit� de sources de donn�es souvent h�t�rog�nes, distribu�es et autonomes. De ce fait, il est contraint d?assembler et de synth�tiser les r�sultats retourn�s avant de pouvoir les exploiter. Dans ce contexte, l?utilisation des syst�mes de m�diation peut s?av�rer une solution appropri�e.
Un syst�me de m�diation classique a pour objectif de fournir un acc�s int�gr� aux donn�es ind�pendamment de leur localisation mais tout en supportant leur h�t�rog�n�it� (Gardarin, 2002). Il se pr�sente comme une couche interm�diaire entre l?application utilisateur et les sources de donn�es (Wiederhold, 1992).
Avant d?interroger effectivement les sources de donn�es, le m�diateur doit d�terminer celles qui, parmi elles, contiennent des informations pertinentes au vu de la requ�te de l?utilisateur. Cette fonction est assur�e par un composant interne qui s?apparente beaucoup � un syst�me de recherche d?information.
L?objectif de notre travail est de proposer une m�thode pour l?�laboration de ce dernier composant en utilisant une technique de classification bas�e sur les treillis de Galois.
Au pr�alable nous associons des annotations � chacune des sources. Une annotation est un ensemble de termes issus de l?ontologie servant � d�crire les sources de donn�es. Nous traitons ce point dans la section 2.
La classification est bas�e sur les annotations. La section 3 pr�sente notre solution pour la classification des sources � l?aide des treillis de Galois.
La section 4 explique l?algorithme utilis� pour la recherche des sources de donn�es. L?id�e est d?utiliser le treillis qui classe les sources de donn�es pour rechercher les sources pertinentes pour une requ�te utilisateur. Si les r�sultats ne sont pas satisfaisants, l?utilisateur a la possibilit� d?affiner sa requ�te (Section 5).
Dans la derni�re section, nous donnons un aper�u du prototype que nous avons d�velopp� pour le test et la validation de notre solution.
Nous terminons par une conclusion dans laquelle nous donnons un bilan de ce travail et les perspectives qu?il permet d?entrevoir.
L?annotation est une phase importante du processus de recherche d?information. Il s?agit d?associer aux sources de donn�es des m�ta-donn�es d�crivant leurs contenus respectifs. Ces m�ta-donn�es vont servir � la classification et � la recherche des sources de donn�es pour r�pondre aux requ�tes des utilisateurs.
Dans notre cas, les m�ta-donn�es sont conformes � un vocabulaire issu de l?ontologie de domaine.
Nous avons choisi le ��tourisme�� comme domaine d?application de notre solution. C?est un domaine qui se caract�rise par une multitude de sources de donn�es r�parties (notamment sur le Web). Dans ce cas, un syst�me de m�diation pourrait avoir comme objectif de fournir � l?utilisateur final une r�ponse int�gr�e construite � partir des offres existantes.
Nous avons utilis� un prototype d?ontologie qui comporte uniquement la partie terminologique �(pas de partie d�ductive). Celle-ci se pr�sente sous forme de trois arborescences�: les destinations, les types d?h�bergement et les activit�s (Cf. figure 1).
Nous nous inscrivons dans un contexte ouvert (e.g. le Web), c?est pourquoi nous supposons que les sources de donn�es sont multiples, distribu�es, h�t�rog�nes et autonomes. Elles peuvent �tre structur�es (relationnel, objet,?), semi-structur�es (XML, HTML,?) ou plates (texte).
Nous avons privil�gi� pour notre prototype les donn�es de type XML. Ce mod�le a �t� retenu parce qu?il est de plus en plus utilis� comme mod�le pivot dans les syst�mes de m�diation.
Le processus d?annotation se base sur les sch�mas des sources de donn�es structur�es, sur les tags pour les fichiers XML et sur le contenu pour les sources non structur�es.
L?annotation consiste en l?attribution de termes sp�cifiques de l?ontologie aux sources de donn�es.
Au pr�alable, une liste des termes-candidats susceptibles de servir pour l?annotation est extraite de l?ontologie. Il s?agit ensuite d?associer un sous-ensemble des termes de cette liste � chacune des sources de donn�es.
Cette op�ration peut �tre faite de mani�re automatique ; nous l?avons impl�ment�e pour les donn�es de type XML, ou manuelle quand c?est l?administrateur qui choisit manuellement les termes de l?annotation.
Un exemple de source de donn�es et de l?annotation correspondante est montr� sur la figure 2.
Comme nous l?avons propos� en introduction, nous allons utiliser la classification formelle � l?aide des treillis de Galois comme base de notre solution. Nous allons, dans ce qui suit, pr�senter les treillis de Galois puis leur application concr�te � notre cas d?�tude.
Soit deux ensembles E (ensemble des individus) et E? (ensemble des propri�t�s) et une relation binaire R entre ces deux ensembles. Le treillis de Galois correspondant au triplet (E, E?,R) est �un ensemble de classes dans lequel chaque classe est un couple (X, X?) avec X un sous-ensemble de E et X? un sous-ensemble de E?. X et X? sont appel�s respectivement extension et intension du couple (X, X?). Le couple (X, X?) est �galement appel� concept formel. (E, E?,R) est appel� contexte formel.
Chaque couple (X, X?) est complet. Cela signifie que X? contient seulement les propri�t�s partag�es par tous les individus appartenant � X et sym�triquement, les �l�ments de X contiennent les individus partageant toutes les propri�t�s appartenant � X?.
Il existe une relation d?ordre partiel ��<�� entre les concepts formels (X, X?). Soit C1 = (X1, X1?) et C2 = (X2, X2?), on a C1<C2 <=> X1 X2 et C1<C2 <=> X2? X1?. Cette relation est aussi appel�e relation de subsomption. Cette relation d?ordre partiel permet de repr�senter le treillis de Galois sous forme de graphe dont les n?uds sont les concepts formels. Un arc entre deux concepts C1 et C2 signifie que C2 est un subsumant directe de C1 c.a.d C1<C2 et il n?existe aucun concept C? du treillis tel que C1<C? et C?<C2.
Dans notre �tude, les objets sont des sources de donn�es et les attributs sont un sous-ensemble des termes de l?ontologie ��Tourisme��.
Nous consid�rons que nous disposons de 5 sources de donn�es soit E = {S1, S2, S3, S4, S5} et nous restreignons les termes candidats � 9 soit�(en abr�viations) :
E? = {VL, CN, HO, CG, PG, MT, YG, NT, TN} avec, VL pour ville, CN pour campagne, HO pour h�tel, CG pour camping, PG pour plage, MT pour montagne, YG pour yoga, NT pour natation, TN pour tennis.
La relation R est repr�sent�e sous forme matricielle dans le tableau 1 ci-dessous.
Tableau 1. �Repr�sentation matricielle �de la relation R1
R | VL | CN | HO | CG | PG | MT | YG | NT | TN |
S1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
S2 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
S3 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
S4 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
S5 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Le treillis de Galois correspondant au contexte formel du tableau 1 est pr�sent� dans la figure 3.
Figure 3. �Treillis2 de Galois correspondant � la relation R
Le treillis de Galois �tablit une classification des sources de donn�es. Chaque concept formel du treillis repr�sente en fait une classe. Par exemple, le concept ({S2, S3}, {VL, YG, TN})3 met dans la m�me classe les sources de donn�es 2 et 3. Ces deux sources sont dans cette classe parce qu?elles sont les seules � partager les propri�t�s VL, YG et TN i.e., que ce sont des destinations situ�es en ville et qu?on peut y pratiquer le tennis ou se d�tendre durant des s�ances de Yoga. Le treillis �tablit aussi une hi�rarchie entre les classes. On peut y lire que le concept formel ({S2, S3},{VL, YG, TN}) est plus particulier que ({S1, S2, S3},{VL})4 dans le sens o� il poss�de plus de propri�t�s c?est ce qui se traduit par le fait que {S2, S3}{S1, S2, S3}. Nous constatons que cette hi�rarchie est � double sens, i.e., le treillis est une sorte d?��arborescence�� � deux ��racines���: ({S1, S2, S3, S4, S5}, �) et (�,{VL, CN, HO, CG, PG, T, YG, NT, TN}) que nous appellerons respectivement top et bottom.
Le d�placement vers top correspond � la g�n�ralisation et celui vers bottom � la sp�cialisation.
Le treillis est construit � l?aide de l?algorithme de construction incr�mentale de Godin (Godin, Missaoui et al., 1995).
Requ�te utilisateur et treillis de Galois�: Notre id�e est de consid�rer la requ�te utilisateur comme une nouvelle source dont les propri�t�s sont les termes de la requ�te. Cette ��source�� va �tre ajout�e au treillis de mani�re incr�mentale (Godin, Missaoui et al., 1995.) Cet ajout transformera le treillis ; de nouveaux n?uds vont �tre ajout�s et d?autres seront modifi�s.
Exemple de requ�te�: Supposons que l?utilisateur formule la requ�te suivante�: Campagne, H�tel, Montagne, Tennis. Il est � la recherche de destinations en campagne situ�es en montagne et o� il peut loger dans un h�tel et pratiquer son sport favori le ��tennis��.
Cette requ�te va �tre repr�sent�e comme suit: ({Q},{CN, HO, MT, TN}). Elle peut s?apparenter � une nouvelle source Q qui a les propri�t�s�: CN, HO, MT, TN.
Le treillis, apr�s ajout de la requ�te, va se transformer comme ci-dessous (figure 4).
A pr�sent, il s?agit de voir comment r�pondre � la requ�te en utilisant ce nouveau treillis. Il faut d?abord remarquer que dans tous les cas, il existe un n?ud qui contient exactement les termes de la requ�te dans sa partie intension. Ceci provient des propri�t�s du treillis de Galois. En effet, il y a une nouvelle instance qui n?existait pas dans le treillis (la ��source�� Q dans notre exemple). Si la requ�te de l?utilisateur, i.e., l?intension n?est contenue dans aucune paire extension/intension (concept formel) alors la nouvelle ��source�� est la seule � correspondre � cette intension et il y aura donc forc�ment un nouveau n?ud constitu� de la paire�: (Num�ro source, termes de la requ�te). Dans la cas contraire, i.e., il existe d�j� une paire qui a comme intension les termes de la requ�te alors cette paire va �tre modifi�e par l?adjonction de la nouvelle source dans sa partie ��extension��. Dans tous les cas, on va se retrouver avec un n?ud qui a comme intension exactement les termes de la requ�te. Ce n?ud est �videmment unique du fait des propri�t�s du treillis. Ce dernier, �tant complet, il ne peut y avoir de n?ud avec la m�me intension et avec une extension diff�rente.
Cette constatation est fondamentale car elle est � la base de l?algorithme de recherche. En effet, c?est ce n?ud unique dont nous venons de parler qui va servir de point de d�part pour l?exploration du treillis � la recherche des sources pertinentes. C?est d?ailleurs le n?ud qui contient les sources les plus pertinentes. Le parcours du treillis va continuer de mani�re ascendante jusqu?au sommet (top). A chaque fois, il y aura dans la partie extension des n?uds visit�s de nouvelles sources pertinentes dans le sens o� ils partagent des propri�t�s avec la requ�te. Le nombre de ces propri�t�s va diminuant, en remontant le treillis et les sources rencontr�es sont de moins en moins int�ressantes.
En r�sum�, le treillis va nous fournir la liste des sources de donn�es par ordre d�croissant de pertinence.
Nous donnons ci-dessous, une pr�sentation plus formelle de cet algorithme�:
Recherche (Requ�te, Treillis) { Ins�rer dans le treillis la requ�te consid�r�e comme source de donn�e fictive. Parcourir le treillis � partir de bottom jusqu?� trouver le n?ud qui a comme intension les termes de la requ�te. Ajouter les sources de donn�es retrouv�es dans l?extension de ce n?ud dans une liste FIFO. Remonter dans le treillis � partir de ce noeud; ajouter � chaque fois les sources de donn�es non encore rencontr�es dans la liste FIFO. Cette liste va contenir les sources de donn�es par ordre de leur insertion et qui correspond en m�me temps � leur ordre de pertinence. } |
Illustration�: Dans notre exemple5 (cf. figure 4), la requ�te utilisateur va g�n�rer les r�ponses suivantes�:
Au premier niveau du n?ud ({Q},{CN,HO,MT,TN}), il n?y a aucune r�ponse�; la partie extension ne comportant aucune source r�elle.
Au second niveau, les r�ponses fournies seront les sources S4 et S2. La source S4 a en commun avec la requ�te les propri�t�s CN, HO et MT, i.e., que cette destination est dans une campagne situ�e en montagne, qu?elle offre un h�tel mais qu?elle n?offre pas la possibilit� de pratiquer le tennis. La source S2 est situ�e en campagne et dispose d?un terrain de tennis.
Au troisi�me niveau, on retrouve les sources S1, S3 et S5. La destination 1 offre un h�tel et la possibilit� de jouer au tennis, la destination 3 offre un terrain de tennis et la �destination 5 est situ�e en campagne.
On remarque, qu?en effet, les sources retourn�es sont toutes pertinentes dans le sens o� elles poss�dent au moins une propri�t� souhait�e par l?utilisateur et qu?elles ont �t� fournies en ordre d�croissant de pertinence.
Une am�lioration possible de cet algorithme concerne l?affinement des requ�tes. Il se peut, en effet, que la requ�te retourne peu ou pas de r�sultats.
L?affinement se traduit souvent par l?enrichissement s�mantique de la requ�te (Bidault, Froideveaux �et al., 2002) ; il s?agit de transformer la requ�te en rempla�ant ses termes par des termes plus g�n�raux ou plus sp�cifiques.
C?est ce principe que nous avons appliqu� ici. La partie taxonomique de l?ontologie est organis�e sous forme de hi�rarchie et l?enrichissement va consister en l?ajout des termes li�s aux termes de la requ�te par des liens de g�n�ralisation/sp�cialisation. L?id�e est d?ajouter les termes subsumants i.e., les anc�tres dans l?arborescence �dans le cas de la g�n�ralisation et les termes subsum�es i.e., les descendants dans l?arborescence dans le cas de la sp�cialisation.
Dans le cas de la g�n�ralisation, si l?utilisateur exprime une requ�te contenant le terme ��h�tel de luxe��, par exemple, celle-ci va �tre enrichie par l?ajout du terme ��H�tel�� et va retourner par cons�quent toutes les destinations annot�es par ce terme. �A l?oppos�, si l?utilisateur introduit pour la formulation de sa requ�te le terme ��h�tel��, sa requ�te va �tre enrichie par sp�cialisation par les termes ��h�tel de luxe�� et ��h�tel �conomique��.
Pour tester la validit� de notre solution, nous l?avons impl�ment�e � l?aide du langage Java. Notre prototype a �t� test� sur un jeu d?essai comprenant une trentaine de sources de donn�es. Nous avons retenu, par ailleurs, une vingtaine de termes-candidats (Cf. 2.4) pour l?annotation.
La premi�re partie de notre programme porte sur l?annotation des sources de donn�es. Il a fallu, dans un premier temps, choisir une repr�sentation interne des objets manipul�s � savoir, l?ontologie et les sources de donn�es. Nous avons adopt�, pour le faire, des structures � base de HashSet6.
Comme nous n?utilisons que la partie taxonomique de l?ontologie, celle-ci est repr�sent�e simplement par un ensemble de termes-candidats retenus pour l?annotation et stock�s dans un HashSet. Ces termes alimentent une structure arborescente qui va servir pour l?affinement des requ�tes. Les sources de donn�es quant � elles sont stock�es dans une structure d�di�e persistante. Elle est bas�e, elle aussi, sur les HashSet et contient pour chaque source les m�tadonn�es correspondantes. Cette structure est aliment�e au fur et � mesure de l?exploitation du programme lors de l?ajout de nouvelles sources.
Une autre structure repr�sente le treillis de Galois dans lequel les sources de donn�es sont classifi�es. En interne, le treillis est un graphe dont les n?uds repr�sentent les classes et les arcs repr�sentent les relations de subsomption (g�n�ralisation/sp�cialisation) qui lient les classes.
Toutes ces structures (ontologie, sources de donn�es et treillis) sont s�rialis�es7.
L?utilisateur a la possibilit� d?ajouter des sources de donn�es. L?ajout peut �tre automatique ou manuel. �
Dans le cas de l?ajout automatique, le processus se d�roule ainsi�:
L?utilisateur choisit un fichier8 repr�sentant une source de donn�es�;
Le programme extrait les tags qui vont servir comme propri�t�s de la source�(Cf. 2.4) ;
L?objet s�rialis� ��source de donn�es�� est mis � jour (Ajout de la nouvelle source)�;
L?objet s�rialis� ��treillis�� est mis � jour par insertion incr�mentale (Godin, Missaoui et al., 1995) de la source�;
par g�n�ralisation ou par sp�cialisation au cas o� les r�sultats retourn�s ne sont pas satisfaisants. Dans le cas de l?ajout manuel, c?est l?utilisateur qui annote la source ajout�e et le programme ex�cute les autres �tapes du processus expliqu� ci-dessus (Mise � jour du treillis notamment)
Le programme impl�mente, par ailleurs, la fonction de recherche. Pour ce faire,� l?utilisateur doit formuler une requ�te constitu�e d?un ensemble de termes de pr�f�rence appartenant � l?ontologie ��tourisme��. C?est pour cela que le programme offre une interface permettant de naviguer dans l?arborescence de l?ontologie et de choisir ainsi les termes appropri�s (figure 5). Une fois la requ�te soumise, le programme retourne le r�sultat qui est l?ensemble des sources class�es par ordre de pertinence (figure 6). Il impl�mente � cet effet l?algorithme de la section 5.
Enfin, l?utilisateur a la possibilit� d?affiner sa requ�te
Dans ce travail nous avons r�alis� un composant ��recherche d?information�� destin� � un syst�me de m�diation. Pour ce faire, nous avons fait appel � une technique de classification formelle bas�e sur les treillis de Galois. Notre prototype nous a permis de v�rifier la validit� de cette solution et la pertinence des r�sultats qu?il retourne.
Les extensions possibles pour ce travail se situent � divers niveaux. Il s?agit, entre autres, de l?impl�mentation, de la technique de classification et de l?annotation.
Au niveau de l?impl�mentation, il serait int�ressant d?�tendre notre prototype au Web, i.e., permettre aux utilisateurs d?acc�der � l?application via le navigateur. Cela peut �tre r�alis� gr�ce � la technologie J2EE notamment.
En ce qui concerne la classification, il va falloir tester notre solution dans un contexte plus r�aliste o� le nombre de sources � traiter est important (plusieurs centaines voire plusieurs milliers de sources). Il est � noter que des am�liorations ont �t� apport�es � l?algorithme de construction incr�mentale des treillis de Galois que nous avons impl�ment� pour tenir compte de cette contrainte (Godin, Missaoui et al., 1995.) Par ailleurs, on peut explorer les nouveaux algorithmes de construction des treillis comme (Van der Merwe et Obiedkov, 2004) et des propositions pour combiner les techniques de classification statistiques avec les treillis de Galois (Valtchev et Missaoui, 2000).
S?agissant de l?annotation des donn�es, une premi�re am�lioration serait la prise en compte, pour les sources de donn�es, des formats de donn�es dominantes du Web (HTML et PDF). On peut, par ailleurs, am�liorer le processus d?annotation du prototype en s?inspirant des techniques utilis�es par la recherche d?information (Manning, Raghavan et al., 2008) et des recherches sur les correspondances des sch�mas de donn�es (Noy, 2004)(Rahm et Bernstein, 2001)( Shvaiko et Euzenat, 2005).
Bidault, A., Froidevaux, C., Gagliardi, H., Goasdou�, F., Reynuad, C., Rousset, M.C. et al. (2002). Construction de m�diateurs pour int�grer des sources d?informations multiples et h�t�rog�nes�: le projet PICSEL. Revue I3�: Information-Intercation-Intelligence, 9-59.
Gardarin, G. (2002). XML des bases de donn�es aux services Web. Paris : Dunod.
Godin, R., Missaoui, R., Alaoui, H. (1995). Incremental concept formation algorithms based on Galois (concept) lattices, Computational Intelligence, 11(2), 246-267.
Manning, C.D., Raghavan, P., Sh�tze, H. (to appear 2008): Introduction to Information Retrieval, Cambridge University Press.
Noy, N. Semantic Integration (2004): A Survey on ontology-based approaches. SIGMOD Record, Special Issue on Semantic Integration, 33(4), December 2004, 65-70
Rahm, E., Bernstein, P. (2001): A survey of approaches to automatic schema matching approaches, VLDB Journal, 10, 334-350
Shvaiko, P., Euzenat, J. (2005): A survey of schema-based matching approaches. Journal on Data semantics IV, 146-171
Valtchev, P., Missaoui, R., (2000): Similarity-based clustering versus Galois lattice building: Strengths and weaknesses, European Conference on Object-Oriented Programming, Sophia-Antipolis: June 2000
Van der Merwe, D., Obiedkov, A., Kourie, D. G. AddIntent (2004): A New Incremental Algorithm for Constructing Concept Lattices, Proceedings of ICFCA 2004, Sydney, Australia: February 23-26, 372-385
Wiederhold, G. (1992), Mediators in the architecture of future information systems. Computer, 25, 38-49.