Résumé. Les approches de la recherche d'information (RI) actuelles ne saisissent pas formellement la signification explicite d'une requête à base de mots-clés mais fournissent une voie confortable pour l'utilisateur qui spécifie ces besoins en informations sur la base des mots-clés. La recherche sémantique promet de fournir des résultats plus précis que la traditionnelle recherche par mots-clés. Toutefois, les progrès de la recherche sémantique ont été retardés en raison de la complexité de ses langages de requête. Dans ce document, nous explorons une nouvelle approche pour l'adaptation des requêtes motsclés pour pouvoir interroger le web sémantique en se basant sur les annotations sémantiques: l'approche traduit automatiquement des requêtes mots clés en des requêtes formelles, afin de permettre aux utilisateurs finaux familiarisés avec l'utilisation des mots clés d'utiliser ces mots-clés pour effectuer des recherches sémantiques. Un prototype de système a été mis en oeuvre sur la lumière de cette approche. Etant donné une requête mots clés, notre système donne en résultats une liste classé de requêtes SPARQL en tant que résultat de la traduction. La traduction dans notre système se compose de trois grandes étapes: Mapping des mots clés aux éléments de la B.C., Construction des graphes requêtes et Classement des requêtes. Avec les premiers tests notre système a réalisé des résultats de traduction encourageant.
La quantité d’information disponible sur internet est aujourd’hui gigantesque et sa
croissance est exponentielle, le nombre d’usagers d’internet double chaque année. On
estime que la taille du Web couvert par les moteurs de recherche est estimée à au
moins 24 milliards de pages1. Mais la spécificité de telles sources d’informations les
rend difficilement exploitables. La raison principale est que les documents sont
fragmentés, dispersés, hétérogènes et sont souvent très peu structurés. Cependant,
grâce aux efforts de la communauté du Web sémantique (W3C), une deuxième
génération est établie dont la vision initiée en 1998 par Sir Tim Berners-Lee [
De même, que de nombreux langages de requêtes sémantiques (par exemple, RQL
[
Dans le contexte de Web sémantique il existe des travaux sur la traduction des
requêtes mots-clés en requêtes sémantiques. Royo et al. [
Sur la base des travaux présentés ci-dessus, nous présentons une approche qui permet de traduire automatiquement des requêtes mots-clés en requêtes formelle SPARQL en vertu de la base de connaissances (base d’annotations sémantiques). Les étapes principales de traduction sont: 1) Le mapping des mots clés aux éléments de la BC, 2) Construction des graphes requêtes et 3) Classement des requêtes. De cette façon, les utilisateurs peuvent garder l'habitude de saisir les mots-clés pour interroger le Web sémantiques sur la base d’annotation sémantique d'une manière transparente, ce qui augmentent l'utilisation sociale de la recherche sémantique.
Le reste de ce document est organisé comme suit: section 2 définit le problème de la construction des requêtes formelles. Section 3 décrit les principales étapes de construction de requête formelle SPARQL. L’implémentation et les résultats expérimentaux sont présentés dans la section 4. Nous donnons la conclusion et les travaux futurs dans la dernière section.
Dans une base de connaissances RDF, une requête sémantique correspond à un graphe requête avec des noeuds objets et des arcs propriété. Ainsi, nous pouvons réduire le problème de la traduction des requêtes mots clés en requêtes formelles conjonctives au problème de la construction des graphes requêtes équivalent. Pour clarifier le problème, nous donnons la définition formelle comme suit: Base de connaissances (B.C) D :(C, I, L, R, ) est un graphe orienté GD où : C et R définis respectivement des ensemble de concepts (classes) et de relations (propriétés). I et L définis respectivement des ensembles d’individus (ressources) et de littéraux. La fonction :(C I) X (C I L) R définit tous les triples de D. En outre, nous utilisons le symbole éléments (entités) {e} :{C R I L} pour représenter toutes les concepts (classes), individus (ressources), relations (propriétés), et les littéraux.
Requête mots clés Qu est un ensemble de mots-clés {k1,…,kn}.
Requête formelle Qs :(C’, R’, I’, L’, V, ’) de D est un graphe GF subsumé par GD.. V est l'ensemble des noeuds variable. ’ : (I’ C’ V) X (I’ C’ V
L’) R’ définit l'ensemble des triples de Qs.
Dans la section suivante, nous illustrerons notre approche en détaille. 3
L’infrastructure de notre système se compose de deux modules (fig. 2) : Le module prétraitement a pour rôle d’indexer automatiquement les entités de la base de connaissances pour obtenir un index qui sera utilisé dans l’étape de Mapping des mots clés aux éléments de la B.C. Alors que Le module de construction des requêtes formelles prend en entrée les mots-clés, et renvoie en sortie une liste classées de requêtes conjonctives SPARQL. Dans les sections suivantes, nous détaillerons ces déférentes étapes.
Le but de ce mapping est de trouver les éléments de la B.C. (c'est-à-dire concepts,
individus, relations et littéraux) correspondants à chaque mot clé de la requête de
l’utilisateur. Les noms et les étiquettes (labels) des éléments de la B.C. sont utilisées
pour le mapping. Dans notre approche, deux types de méthodes de mapping peuvent
être utilisées: 1) le mapping morphologique emploie les techniques de comparaison
de chaîne de caractères, tels que le stemming, Sub-String et Levenshtein Distance
pour trouver les mots morphologiquement semblables; 2) Le mapping sémantique
utilise principalement des dictionnaires généraux comme WordNet [
Voir http://lucene.apache.org/java/docs/ Ce processus construit les graphes requête candidats avec les éléments mots clés trouvés dans l’étape précédente. Tout d'abord, les éléments mots clés sont répartis en différentes ensembles de requêtes. Le but de cette répartition est d’attribuer un sens à chaque requête formelle par l’énumération de toutes les combinaisons possibles des différents sens pour chaque terme ki de Qu. Ensuite, un certain nombre d’algorithmes sont appliqués pour construire de possible graphes requêtes pour chaque ensemble de requêtes. 3.2.1
Dans notre approche, l’exploration des relatons se limite aux relations de type : (i, c), (i1, R, i2) et (i, U, j) où i, i1, i2 I, j L, c C, R R , U U avec I (Individus), L (littéraux), C (Concepts), R (propriétés d’objets) et U (propriétés de données) Par l'utilisation de ces axiomes, nous explorons touts les éléments de la B.C. liées aux éléments de Dm identifiés dans la première étape selon l'algorithme montré à la Fig. 3. Le processus du calcule des graphes de connexions se déroule comme suit : 1.
Explorer les liens entre les éléments de la B.C :.Fondamentalement, l'exploration comprend la traversée des voisins pour chacun des éléments de Dm. Ensuite, selon le type de l'élément particulier em Dm, différents parcours sont effectués pour construire un graphe connectant em à tous ces voisins sur une distance spécifique d. Soit un concept, tous les individus sont recherchés par l'intermédiaire de l’axiome (i, c). Compte tenu une relation, les axiomes (i1, R, i2) et (i, U, j) sont utilisées pour naviguer vers les individus et les littéraux, respectivement. La figure 4, montre le pseudocode de l’algorithme pour la traversée récursif d'un individu ou d’un littéral particulier à ses voisins concepts, individus et littéraux. La valeur de d est réduite de un à chaque étape de récusions pour assurer à ce que cette traversée sera limitée à une certaine distance. En fin de compte, nous obtenons
un graphe g contenant touts les éléments de D qui ont une distance graphique qui ne dépasse pas d au moins à un des éléments de Dm. Ainsi, quelques éléments découverts peuvent vraiment ne pas être nécessaires pour connecter des éléments de Dm. Par conséquent, à partir de ce graphe, ont choisis seulement les chemins où le premier et le dernier sommet correspond est un élément de Dm. En particulier, une version modifiée de la procédure DFS (Depth First Search) sur les graphes est utilisé pour le calcul de tous les chemins p P pour chaque paire possible tel que (a, b) Dm tel que p= (a, e1, ..., en, b), et aucun des sommets n’est visité plus d'une fois. Ces chemins seront introduits dans l'étape suivante.
Le calcul des Connexions : Une requête peut être dérivée quand tous les éléments Dm identifiés dans la première étape sont connectés. En fusionnant tous les chemins P calculés dans l'étape précédente, nous obtenons toutefois un graphe qui peut contenir plusieurs différents sous-graphes connectant tous les éléments de Dm. Le sous-graphe connectant les éléments de Dm sont calculés par une procédure récursive montrée dans l'algorithme de la fig.5. L'entrée de l'algorithme est l'ensemble des chemins P calculée précédemment La récusions commence par la sélection d’un certain chemin connectant deux sommets arbitraires et entre d'autres récusions pour ajouter des sommets supplémentaires. De cette façon, tous les sous-graphes en forme d’arbre possibles connectant des éléments de D sont déterminés.
Algorithme Traversé ( i, d, t, g)
Enfin, Chacun des graphes de connexion Gc trouvé précédemment est ensuite traduit en un graphe requête comme suit : une arête dans Gc de la forme type (vi, vc) (représentant la connexion (i, c)) est considéré comme arête dans le graphe requête de la forme Type(x, C), où vi, est un sommet construit au moyen d'un individu, vc est construit en utilisant un concept, et x est un individu ou une variable. Lorsqu’un individu de vi correspond à certains éléments em Dm, il est considéré comme une constante, sinon une variable est utilisé pour ce terme. Comme le même individu peut être utilisé dans beaucoup d’arêtes, la même variable doit être utilisée pour le même individu. Les arêtes construit avec les axiomes de la forme R (vi, vj), où vi (vj) est construit en utilisant soit un individu ou un littérale (connexions (i1, R, i2) et (i, U, j)). Ces arêtes sont considérés comme arêtes dans le graphe requête de la forme R(x, y), où un sommet construits au moyen d'un individu est associé à une variable ou une constante comme décrit ci-dessus. Lorsque vi (vj) est construit en utilisant un littérale, il est tout simplement considéré comme noeud associé à une constant. Dans notre exemple de la Fig.1, il existe un seul graphe de connexion donc un seul graphe requête.
Puisque SPARQL est un langage d'interrogation basé sur les motifs de graphes, il est facile de convertir un graphe requête en une requête SPARQL.
Algorithme Calculer-graphe-connexion (P, C, R, G, g) 1 Entrée l’ensemble de chemins P calculer par DFS pour tous les éléments mots clés de Dm 2 Sortie Tous les sous-graphes connectant les sommets de Dm 4 Alors Pour {i, j} R 5 Faire G=NouveauGraphe 6 Pour chaque chemin p entre i et j (calculer par DFS) 7 Faire ajouter (i, p, j) dans G 8 Calculer-graphe-connexion (P\p, C 9 g=g G 10 Sinon Pour i R 11 Faire Pour j C 12 Faire Pour chaque chemin p entre i et j 13 Faire ajouter (i, p, j) dans G 14 Calculer-graphe-connexion (P\p, C {i, j}, R\{i, j}, G) {i}, R\{i}, G) Après l'étape de la construction des graphes requêtes, plusieurs requêtes formelles candidates peuvent être produites à partir de la requête mots-clés initiale correspondant à toutes les interprétations possibles des mots clés. Un problème se pose: comment prendre la requête formelle qui correspond aux besoins de l’utilisateur?.
Le calcule du score des réponses a été largement discuté dans le domaine de la recherche d'information. Dans le contexte des données structurées en graphe, Les métriques standard souvent utilisés sont "PageRank" (pour calculer le score des sommets) et le plus court chemin (pour calculer le score des chemins). Les graphes sont construits à partir d'un ensemble de chemins P. Le score d'un tel graphe est défini comme agrégation monotonique des scores de ses chemins. En particulier, CG = pi P
Cpi est utilisé, où Cpi et CG dénotent des coûts. En général, le coût d'un mapping des éléments d’un graphe requête. CG = chemin est calculé à partir du coût de ses éléments, c'est-à-dire Cpi= arêtes, où |V| est le nombre total de sommets dans le graphe d’exploration, |vagg| est le nombre des individus qui sont relies au sommet v, |E| est le nombre total d'arêtes et |eagg| est le nombre d’arêtes correspondant à e dans le graphe d’exploration. Notre système est implémenté en Java et Jena5 API. Un utilisateur saisi sa requête mots-clés et il obtient en revanche une liste classée des requêtes SPARQL. Ces requêtes SPARQL traduites peuvent ainsi être directement envoyées à moteur de recherche ARQ6 pour avoir les ressources relatives à sa requête.
Nous allons maintenant discuter les expériences que nous avons réalisées pour évaluer l'efficacité et le rendement de notre approche. Pour évaluer notre approche, nous utilisons une base d’annotation RDF au sujet des publications scientifiques sur l’informatique. Notre expérience a été réalisée sur un PC avec un CPU Pentium de 3,2 GHz et 2 Go de mémoire. Afin d'évaluer l'efficacité de notre approche, nous avons demandé à des collègues de nous fournir des requêtes mots-clés avec leurs descriptions en Langage Naturel (LN). 20 requêtes différentes ont été proposées. Un exemple de requête est : "publications SmartWeb Pascal Hitzler 2002" (retrouver toutes les publications publié par Pascal Hitzler dans SmartWeb en 2002).
Nous avons pris deux métriques pour l'évaluation: Rappel et MRR : Le rappel est défini comme le nombre des requêtes mots-clés correctement traduites divisées par toutes les requêtes mots-clés de l’ensemble d'évaluation (c.-à-d. 20 dans notre cas). Tandis que MRR, se concentre sur les performances globales du système. Pour 5 http://jena.sourceforge.net/ http://jena.sourceforge.net/ARQ/ évaluer l'efficacité de la génération des requêtes et leur classement, une métrique standard en RI appelé Reciprocal Rank (RR), définie comme RR =1/r est utilisé, où r est le rang de la bonne requête. Selon notre définition du problème, une requête est correcte si elle correspond au besoin en information (la description LN fournie). Si aucune des requêtes générées ne correspondent à la description LN, RR est égale à 0. Nous avons calculé MRR qui est la moyenne de RR de toutes les requêtes mots-clés de notre test. Nous avons obtenus un rappel de 0.825 et un MRR de 0.745 (Fig. 6) 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0
Rappel
MRR
Dans ce document, nous avons formalisé le problème de la construction des requêtes formelle et présenter une approche efficace pour le résoudre. Notre système vise à traduire les requêtes mots-clés en requêtes SPARQL en utilisant les connaissances disponibles dans une base de d’annotation pour réduire l'écart entre la recherche sémantique basé sur la logique formelle et les utilisateurs finaux habitué à utiliser les moteur de recherche classique basé sur les mots clé. Notre approche peut se résumé ainsi : Une fois un utilisateur entre une requête mots-clés, la première étape qui est réalisée est le mapping des mots clés aux éléments de la BC, cette étape utilise un ensemble de méthodes de mapping pour trouver les éléments correspondants dans la base de connaissances en fonction des mots-clés de l'utilisateur. Ensuite, l'étape de construction des graphes requête énumère toutes les combinaisons possibles de requête et applique un certain nombre d’algorithmes pour construire les graphes requêtes avec différents sens des éléments mots clés. Enfin, l'étape de classement des requête évalue les requêtes formelles construites à en utilisant un modèle probabiliste de classement des requêtes. Une liste de requêtes SPARQL classée sera remis à l'utilisateur final. Avec les premiers tests notre système a réalisé des résultats de traduction encourageant. La principale contribution de ce document est l’exploitation des annotations sémantiques dans la recherche d’information sur le Web.
Dans les travaux futurs, nous estimons améliorer notre approche de plusieurs façons: 1) élargir la portée des requêtes par l'introduction de certains opérateurs structurés (par exemple, NOT, OR, les filtres etc.) et en améliorant le support d'interaction humaine pour traduire les besoins en informations plus complexes. 2) Les travaux futurs seront axés sur le renforcement de la performance. Nous envisageons d'exploiter la connaissance disponible dans l’ontologie pour une «exploration guidée » des liens entre les entités d'ontologie pour réduire le nombre de requêtes. 3) étendre notre approche sur une base d’annotation plus consistante et reparti sur le Web.