Recherche des objets complexes dans le Web structuré

Nous assistons aujourd’hui à un développement continu et rapide du Web Structuré, dans lequel les documents ne sont plus composés que du texte non structuré mais sont centrés sur les données (data-centric), présentant des contenus structurés et des objets complexes. Les plates-formes de recherche d’information (IR) actuelles s’inspirent des procédures et des techniques utilisées dans les systèmes de recherche documentaire. Le passage à des contenus structurés, avec des schémas prédéfinis, nécessite des techniques d’interrogation plus précises et plus riches, et soulève de nouveaux défis auxquels nous essayons de fournir des réponses. En effet, la recherche par mots-clés n’est pas adaptée pour interroger le Web structuré. De nouveaux moyens de recherche sur le Web sont donc nécessaires, pour permettre à l’utilisateur de cibler des données complexes avec une sémantique précise.

La popularité, le développement du Web et sa large utilisation dans différents domaines font que de nouveaux besoins apparaissent, tels que la recherche d’entités complexes (ou objets complexes). Dans ce contexte, une requête utilisateur peut cibler des entités complexes telles qu’un événement sportif ou culturel, un produit, une œuvre d’art, une vente d’appartement, etc. L’utilisateur s’attend à avoir des résultats bien précis, qui répondent à ses attentes en terme de structure et de sémantique des objets recherchés. Cependant, les moteurs de recherche actuels ne permettent d’obtenir que des pages en utilisant des méthodes traditionnelles de recherche par des mots-clés. Ces méthodes sont sémantiquement pauvres et limitées, elles ne permettent pas une recherche précise des objets et ne tiennent pas compte de la sémantique associée à la requête de l’utilisateur.

Extraction d’information

Afin que les applications puissent exploiter les diverses et nombreuses informations disponibles sur le Web, ces informations doivent être extraites et transformées aux formats de représentation appropriés. Cette tâche est appelée Extraction d’Information. Elle consiste à repérer et à déduire une information structurée et détaillée à partir de sources Web riches, hétérogènes, non structurées, ou faiblement structurées. Dans le Web on peut trouver les informations à extraire dans différentes sources et sous différents formats : le Web non structuré, le Web structuré et le Web caché.

– Pages Web non structurées : aussi connu sous le nom du Web textuel, les informations peuvent être décrites en langage naturel : le texte dans les pages, les blogs, les dépêches, etc. Afin de les extraire, plusieurs tâches doivent être effectuées selon [CM04] : (1) la segmentation et le découpage du texte en segments pour la reconnaissance des entités nommées à extraire, (2) la catégorisation (classification) de ces entités et l’identification des noms, dates, organisations, etc., (3) l’association et l’identification des relations entres les différentes entités et les intégrer dans un seul enregistrement (record), et (4) la classification (clustering) des enregistrements qui référencent le même enregistrement dans le monde réel, i.e., ceux qui ont la même sémantique. Finalement, ces informations sont représentées dans une forme structurée.

– Pages Web structurées : les informations peuvent être présentées sous forme de listes HTML, des tableaux ou des données XML, etc. Contrairement au Web textuel, dans le Web structuré les pages suivent la même mise en page (structure). Cette structure peut être exploitée pour l’identification des informations structurées (objets). Cependant, elle est unique à chaque site et pratiquement il n’existe pas de description (grammaire) générale qui peut décrire tous les schémas de pages possibles. En conséquence, chaque structure peut nécessiter un extracteur spécifique, ce qui rend la programmation manuelle des extracteurs très coûteuse.

– Web caché : aussi connu sous le non du Web caché, les informations peuvent aussi être décrites dans des pages non indexées par les moteurs de recherche (dans des bases de données accessibles par le biais de formulaires Web). Il y a deux problématiques principales à traiter pour l’extraction à partir du Web caché : (1) comment parvenir à comprendre le formulaire et trouver la requête qui permet de remplir les champs de ce formulaire, (2) une fois le formulaire rempli, on se retrouve confronté aux mêmes problématiques liées à l’extraction d’information à partir du Web structuré.

Entités, relations, type d’extraction

On rappelle que l’extraction d’information est le processus de récupération des informations structurées à partir des textes, ces informations pouvant être des entités simples ou relations binaires, n-aires ou imbriquées (nested structure).

– Entités. Elles représentent une seule unité d’information. Elle sont généralement des phrases nominales comprenant un ou plusieurs mots. Les plus populaires sont les entités nommées comme les noms de personnes, les noms de pays, etc. L’identification des entités nommées inclut traditionnellement trois types d’expressions : les noms propres (personne, organisation, lieu), les expressions temporelles (date, période, durée, etc.) et les expressions numériques (poids, nombre, température, etc.).

– Relations binaires. Elles sont définies par l’intermédiaire de deux entités liées d’une manière prédéfinie. Par exemple, la relation “is written by” entre un auteur et un titre de livre, “is price of” entre un prix et un produit, etc.

– Relations n-aires ou imbriquées. Elles relient plusieurs entités, ces relations peuvent être plates ou imbriquées. Par exemple, un object concert peut avoir des relations entre le nom de l’artist, la date et l’adresse. L’adresse peut être une relation imbriquée contenant d’autres relations entre le nom de la ville, le nom de la salle de spectacle, la rue, etc.

Annotation sémantique

Une annotation désigne une information “sémantique” associée à un ou plusieurs mots existants dans le texte. Les documents à annoter sont découpés en mots (tokenized) , et la séquence de mots qui correspond au maximum à une entité dans un domaine de connaissance est identifiée. Ce domaine peut être spécifié à l’aide de listes d’instances ou d’expressions régulières (ensemble de patterns). Plus précisément, la tâche d’annotation est effectuée par l’identification des candidats dans le texte, en exploitant un domaine de connaissance. Par la suite, une étiquette (label) est choisie pour chaque candidat. L’annotation est utilisée pour plusieurs applications, dont l’extraction d’information.

Habituellement, les annotations sont réalisées en utilisant une ontologie, qui décrit formellement un domaine de connaissance. Elle consiste à relier une instance existante dans le texte au concept approprié.

Ontologies, Taxonomies 

De nos jours, plusieurs représentations normalisées de connaissances du monde réel sont formalisées sous forme d’un schéma hiérarchisé appelé ontologie. Autrement dit, une ontologie désigne toute collection structurée de connaissances du monde réel attachée à des règles sémantiques. Souvent, ces bases de connaissances ont été construites automatiquement par l’extraction des entités relations à partir de sources Web. Parmi ces bases de données, celles construite à partir de Wikipédia (comme, KnowItAll [CDSE05], DBPedia [ABK+07] et YAGO [SKW07]), des ontologies commerciales (comme, FreeBase.com et OpenCyc.org), ou des ontologies plus spécialisées contenant des données spécifiques à un domaine (comme, MusicBrainz.org pour les données du domaine de musique, Geonames.org pour les données du domaine géographique). Beaucoup de ces ontologies contiennent des données complémentaires. Cependant, puisqu’elles utilisent généralement différents identifiants pour les entités, cette information ne peut pas être connectée facilement. Partant de cette direction, un graphe globale de données regroupant ces ontologies connu sous le nom de Linked Open Data  a été créé, qui permet de connecter et de découvrir de nouvelles sources de données [BHIBL08, Biz10, BHBLH11]. Les entités dans ce graphe sont connectées par des liens, en utilisant les mêmes URIs pour les entités similaires (ce graphe contient environ 26 billion de tuples et 400 millions de liens entre les sources de données, en Septembre 2010).

Table des matières

1 Introduction
1.1 Contexte et Problématique
1.2 Contributions de la thèse
1.3 Organisation du manuscrit
2 Contexte et travaux connexes
2.1 Extraction d’information
2.1.1 Entités, relations, type d’extraction
2.1.2 Annotation sémantique
2.1.3 Extraction d’information à partir du Web textuel
2.1.4 Extraction d’information à partir du Web structuré
2.1.4.1 Sources Web structurées (Encodage)
2.1.4.2 Extracteur Web (Décodage)
2.1.4.3 Types de pages Web structurées
2.1.5 Systèmes de génération de wrappers
2.1.5.1 Alignement de plusieurs records
2.1.5.2 Inférence de grammaires
2.1.5.3 Fréquence d’apparition des tokens
2.1.5.4 Caractéristiques visuelles
2.2 Découverte et sélection de sources
2.3 Synthèse et positionnement
3 Préliminaires et définitions des problèmes
3.1 Définitions, notations
3.1.1 Description d’information structurée
3.1.1.1 Types, SODs
3.1.1.2 Instances d’objets
3.2 Pré-traitement de pages Web
3.3 Définition des problèmes
3.3.1 Le problème de la selection de sources
3.3.2 Le problème d’extraction d’objets
3.4 Les avantages d’une interrogation à deux étapes
3.5 Conclusion
4 Extraction d’Information Ciblée
4.1 Architecture générale
4.2 Algorithme d’extraction
4.2.1 Reconnaisseurs de types
4.2.1.1 Ontologie YAGO
4.2.1.2 Patterns de Hearst
4.2.2 Annotation de pages Web
4.2.3 Génération de wrappers
4.2.3.1 Identification des rôles de tokens
4.2.3.2 Utilisation des annotations
4.2.4 Construction du template
4.2.5 Arrêt du processus de génération du wrapper
4.2.5.1 Pendant la phase d’annotation
4.2.5.2 Pendant la phase de génération du wrapper
4.2.6 Enrichissement des dictionnaires
4.3 Expérimentations
4.3.1 Jeu de données
4.3.2 Résultats
4.3.2.1 L’impact du choix de l’échantillon sur la qualité de l’extraction
4.3.2.2 Comparaison avec les approches existantes
4.3.2.3 Complétude du dictionnaire
4.3.2.4 Variation du paramètre support
4.4 Conclusion
5 Conclusion

Télécharger le rapport complet