Cours Systèmes de RI PDF

Systèmes de RI Pr. Bouzid Génie informatique – 5ème année Année universitaire 2023- 2024 1 SRI & Big Data  Plan Introduction: Définitions autour de la RI Do...

Systèmes de RI Pr. Bouzid Génie informatique – 5ème année Année universitaire 2023- 2024 1 SRI & Big Data  Plan Introduction: Définitions autour de la RI Domaines de la RI Historique Problématique de la RI L’indexation Les modèles de RI L’évaluation d’un SRI La RI sur le web 2 SRI & Big Data  Introduction 3 SRI & Big Data  Introduction Le domaine de la recherche d’information remonte au début des années 1950 : explosion des informations après la seconde guerre mondiale Avènement de l’informatique (et de l’utilisation des ordinateurs) popularisation de l’internet Les pionniers de l’époque étaient enthousiastes à utiliser l’ordinateur pour automatiser la recherche d’information, dépassant la capacité humaine Les informations étaient principalement contenues dans des documents textuels Problématique abordée: comment rechercher des informations dans une base de documents volumineuse de 4 manière rapide et efficace SRI & Big Data  Définition - RI Définition de la RI: La recherche d’information (RI) est une branche de l’informatique qui s’intéresse a l’acquisition, l’organisation, le stockage, la recherche et la sélection d’information [salton, 1968] Terminologies utilisées: Recherche d’information (RI) - Information Retrieval (IR) Recherche de document – Document Retrieval Finalité: Sélectionner dans une collection (de documents) les informations pertinentes répondant à un besoin précis 5 SRI & Big Data  Définition - RI Trois notions clés se dégagent : Document (quels documents) Requête (comment correspondre la requête et les documents) Pertinence (comment évaluer le résultat) La notion de document en RI: Document textuel Page web (fichiers web , mail, …) Images, Vidéos Mélange de types (textes, images, …) dans un format précis => On appelle « document » dans la RI toute ressource d’information qui peut constituer une réponse à une requête d‘un utilisateur 6 SRI & Big Data  Définition - RI Remarques: Dans la RI: l’information recherchée est textuelle, mais peut être retrouvée dans différents formats de documents / fichiers Pour les images et les vidéos (ou tout autre fichier multimédia), leurs métadonnées sont utilisées en premier Il existe une autre branche de la RI (recherche d’image - image retrieval) qui se focalise sur la recherche d’image à partir d’une requête sous forme d’image (comparaison d’images…). Il ne s’agit pas d’une recherche textuelle (hors sujet de ce cours). 7 SRI & Big Data  Domaines de la RI Domaines d’applications: GED (gestion électroniques de documents) Recherche sur le web Réseaux sociaux Bibliothèques numériques Monde de l’entreprise (toute activité métier produisant des documents) Recherche scientifique Nos propres ordinateurs (bureautique et autre) … 8 SRI & Big Data  Domaines de la RI Domaines d’application connexes : Classification / catégorisation (clustering) Web sémantique (semantic web) Systèmes de Questions-réponses (Query Answering) Systèmes de Recommandation (Recommendation systems) L’IA (intelligence artificielle) Fouille de textes (Text mining) Gestion des connaissances (knowledge management) … 9 SRI & Big Data  Définition - SRI Un système de recherche d'information (SRI) est un système qui permet de retrouver les « documents pertinents » à une requête utilisateur (textuelle) Exemples de SRI: Moteur de recherche Web (google, bing, …) Systèmes de RI documentaires (tels que pour la recherche d’articles scientifiques) Systèmes de RI dans les logiciels de GED Systèmes de RI spécifiques à une base de documents d’une entreprise 10 SRI & Big Data  Définition - SRI Remarque: Il ne faut pas confondre systèmes de bases de données et systèmes de RI Les SRI se focalisent sur la recherche d’informations textuelles dans des ressources telles que des documents La recherche (requêtage) dans des BD (relationnelles ou non relationnelles) ne relève pas du domaine de la RI, car : ces BD contiennent des données (et pas des informations) organisées suivant un certain schéma (modèle) de stockage (les données ont un modèle de conception métier) le résultat renvoie des données (table, liste de données) et pas des documents 11 SRI & Big Data  Historique La RI date des années 1940, dès la naissance des ordinateurs. Le nom de « recherche d’information » (information retrieval) fut donné par Calvin N. Mooers en 1948 [MOO 48] pour la première fois quand il travaillait sur son mémoire de maîtrise Au début, la RI se concentrait sur les applications dans des bibliothèques (on utilisait le nom "automatisation de bibliothèques") Dans les années 1950, on commençait de petites expérimentations en utilisant des petites collections de documents (références bibliographiques). Le modèle utilisé est le modèle booléen 12 SRI & Big Data  Historique La première conférence dédiée au thème de la RI – International Conference on Scientific Information - s’est tenue en 1958 à Washington Les premiers problèmes qui intéressaient les chercheurs portaient sur comment retrouver les documents (avec quels mots, quels termes) => la notion d’index est devenue au centre des recherche Dans les années 1960 et 1970, des expérimentations plus larges ont été menées, et des méthodologie pour évaluer les système de RI ont vue le jour. Des corpus de test (e.g. CACM) ont été conçus pour évaluer des systèmes différents de RI. Ces corpus de test ont beaucoup contribué à l'avancement de la RI 13 SRI & Big Data  Historique Parmi les projets d’expérimentation menés sur la RI : Projet Cranfield (dirigé par Cyril Cleverdon, 1957-1967) [CLE 67]: on visait à tester l’efficacité de différentes façons d’indexer et de rechercher des documents. C’est dans ce projet que les mesures précision et rappel (precision and recall) on été inventées. Ces mesures sont encore utilisées aujourd’hui pour évaluer la pertinence des résultats obtenus par rapport aux résultats souhaités Projet MEDLARS – MEDical Literature Analysis and Retrieval System (F. Wilfrid Lancaster, complete en 1968) [LAN 68]: il s’agit d’expérimentation de RI dans le domaine biomédical. Les documents sont indexés manuellement, avec un vocabulaire contrôlé (choisi). Les résultats sont évalués en terme de précision et de rappel. Les résultats de ce projet montrent que l’utilisation d’un vocabulaire contrôlé avec l’indexation manuelle est efficace mais restreint la pertinence des résultats. 14 SRI & Big Data  Historique SMART (Gerard Salton, 1ière version 1961-1965) [SAL 71] : celui qui a eu le plus d’impact sur la RI est le système SMART, développé entre les années 1960 et début des années 1970. Les travaux sur ce système ont été dirigés par G. Salton, professeur à Cornell university (NY). De nouvelles techniques ont été implémentées et expérimentées pour la première fois dans ce système telles que: l’utilisation du modèle vectoriel, la technique de « relevance feedback », le regroupement de documents / clustering, …). Le système SMART fut réécrit dans les années 1970 et 1980 par E. Fox et C. Buckley. Ce système a été, et est encore aujourd’hui, utilisé par de nombreux chercheurs pour des expérimentations en RI. 15 SRI & Big Data  Historique Les années 1980 ont été influencées par le développement de l'intelligence artificielle. Ainsi, on tentait d'intégrer des techniques de l'IA dans la RI (par exemple, système expert pour la RI, etc). Les années 1990 (surtout à partir de 1995) sont les années de l’avènement de l'Internet. Cela a eu pour effet de propulser la RI en avant et sur sur le web (apparition des moteurs de recherche web). La problématique de la RI a été élargie à d’autres types de documents/fichiers tels que le multimédia (et encore plus aujourd’hui avec les réseaux sociaux). Les techniques de base utilisées dans les moteurs de recherche web sont celles connues de la RI. Des améliorations et des spécificités liées au web ont été apportées par la suite. 16 SRI & Big Data  Problématique de la RI 17 SRI & Big Data  Problématique de la RI Besoin d’information How? Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 18 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 19 SRI & Big Data  Problématique de la RI Besoin d’information : Il s’agit d’une expression mentale de l’utilisateur Le même besoin peut être exprimé de différentes manières, selon l’utilisateur… Requête utilisateur: Est une représentation possible du besoin de l’utilisateur Peut prendre les formes suivantes : Texte libre, texte avec operateurs (AND, OR, NOT,…) Liste de mots clés (vocabulaire contrôlé) Images, sons Par navigation dans une collection Hashtag (cas des réseaux sociaux) … 20 SRI & Big Data  Problématique de la RI Problématique du besoin : Une requête idéale doit comporter toutes les informations que l’utilisateur recherche, la similarité serait alors optimale (et maximale) Or, l’utilisateur recherche une information qu’il ne connait pas a priori, il ne peut donc pas l’exprimer (décrire) de maniere précise (ideale) Le besoin est donc exprimé de manière approximative Le besoin est subjectif car dépend de l’utilisateur qui l’exprime 21 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 22 SRI & Big Data  Problématique de la RI Sources d’information : Ressources d’information (documents / fichiers) Formes des ressources : Texte images, sons, vidéo, graphiques, etc. Propriétés des ressources : Non structurée : texte brut (plain text) Structurée ou semi structurée (XML, HTML, …) Hétérogénéité Langage (contenu multilingue) Format connu (documents, images, vidéos,…) Format spécifique (issue d’applications métier…) 23 SRI & Big Data  Problématique de la RI Exemple semi-structuré: livre numérique (métadonnées + texte brut): 24 SRI & Big Data  Problématique de la RI Deux classes d’information: Méta-information, métadonnées (données/informations à propos du document) Attributs : titre, auteur, date de création, etc. Structure (organisation du contenu) : structure logique, liens,... Contenu : Contenu brut : texte du document Contenu sémantique : texte ayant du sens (information) extrait à partir du contenu brut 25 SRI & Big Data  Problématique de la RI Problématique des sources d’information : Beaucoup de formes et d’hétérogénéités dans les documents Quantité importante d’informations L’utilisateur ne connait pas les sources d’information à l’avance (pas nécessairement). L’information recherchée est noyée dans d’autres informations => Comment peut-on parcourir autant de sources d’information et en sélectionner les plus pertinentes par rapport à un besoin utilisateur ? 26 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 27 SRI & Big Data  Problématique de la RI Matching (mise en correspondance) : => Deux approches possibles: Approche simple de la RI : Correspondance mot à mot Trouver les documents ayant X Y Z les mêmes mots que la requête La requête et les documents sont des listes de mots clés (texte) On parcourt séquentiellement les textes des documents en recherchant les occurrences de chaque mot-clé de la requête On sélectionne les documents et classe les résultats : les documents qui contiennent le plus de mots de la requête sont présentés en premier 28 SRI & Big Data  Problématique de la RI Critique de l’approche simple: Efficace pour des bases de textes de petite taille : le temps de calcul est linéaire dans la taille de la base Pas de prétraitement de la requête ni des textes : caractères (majuscules, accents,...), mots de même famille => risque de passer à côté de certains documents Problème de Vitesse: L'opération de recherche est très lente. Pour chaque requête, on doit parcourir tous les documents dans la base. Dans la pratique, il y en a des centaines de milliers, voire des millions. Il n'est donc envisageable d'utiliser cette approche que sur des collections très petites (avec un contenu textuel pas très chargé) 29 SRI & Big Data  Problématique de la RI Exemples de SRI avec l’approche simple : Recherche de fichiers de code dans les Frameworks de développement informatique Recherche dans les e-mails (outlook, gmail, …) Fonctionnalité de recherche dans l’historique de navigation dans un navigateur web 30 SRI & Big Data  Problématique de la RI Approche par indexation : Correspondance Correspondance entre les X Y Z mots de la requête et les Index index (représentations des documents) Représentations Idée de base : On ne peut pas parcourir les documents à chaque requête On va donc prétraiter les documents pour savoir rapidement dans quel document apparaît un mot. Technique : => L’indexation Prétraiter les documents (sélectionner les termes clés qui les représentent) Constituer une liste de termes pour chaque document Construire une structure de données associant termes et documents => 31 Base d’index SRI & Big Data  Problématique de la RI Critique de l’approche par indexation: Elle est plus rapide car plus besoin du parcours séquentiel. Avec la structure d'index, on peut directement savoir quels sont les documents qui contiennent tel ou tel mot L’expression des requêtes peut être intelligente (avec des opérateurs de logique ente les mots), exprimant des besoins d'information complexes Le prix à payer pour ces avantages est le besoin d’espace de stockage supplémentaire pour la structure d'indexes. En général, cet espace peut aller de 40% jusqu’à 200% de la taille de la collection de documents, selon la complexité de l'indexation 32 SRI & Big Data  Problématique de la RI Exemples de SRI avec l’approche d’indexation: Tous les moteurs de recherche web, Certains moteurs intégré dans les logiciels du marché (logiciels professionnel de gestion, ERP, CRM,…), Outils de GED, Moteur de recherche des réseaux sociaux, … 33 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 34 SRI & Big Data  Problématique de la RI Pertinence des résultats : La pertinence est le degré de correspondance entre une requête et la liste des documents retournés en résultats Côté utilisateur humain, la pertinence est subjective: les résultats peuvent paraitre pertinents pour un utilisateur et pas assez pertinents pour un autre (pour une même requête) Côté système, la pertinence est algorithmique : termes de la requête dans un document (grâce aux index) = document pertinent Le but de rechercher l’information dans un SRI est de trouver seulement les documents pertinents à une requête, et pertinents pour la majorité des utilisateurs du système Aucun système de RI n’est parfait. L’objectif final est de trouver le bon rapport entre requête/résultat 35 SRI & Big Data  Synthèse de la problématique Caractéristiques d’un SRI : Le système doit être simple à utiliser (expression facile de la requête, possibilité d’exprimer des requêtes logiques,…) Le système doit conjuguer avec les différents formats et contenus des documents / sources d’information Le système doit fournir les meilleures réponses possibles, et ces réponses doivent être « pertinentes » pour l’utilisateur Le système doit fournir un nombre raisonnable de réponses Le système doit fournir des réponses rapides (délai raisonnable) => Comment essayer de satisfaire toutes ces caractéristiques à la fois? 36 SRI & Big Data  Solution : L’indexation Sources d’information Besoin d’information Input … Documents textuels, images, vidéos, … Matching Requête utilisateur Index Index Index Output 37 SRI & Big Data  L’indexation 38 SRI & Big Data  L’indexation C’est quoi l’indexation? Processus permettant de construire un ensemble de termes clés (« index ») permettant de représenter le contenu d’un document L’index peut représenter : Un mot simple: « pomme » Un groupe de mots : « pomme de terre » L’indexation peut être : Manuelle (experts des documents) Automatique (ordinateur) Semi-automatique (combinaison des deux) Basée sur : Un langage libre (éléments pris directement des documents) Un langage contrôlé (lexique, thesaurus, ontologie/réseau 39 sémantique,…) SRI & Big Data  Vocabulaire contrôlé Types de vocabulaires contrôlés: Lexique : Liste de mots clés Liste hiérarchique (taxonomie) : de concepts, de notations,… Thésaurus : Liste de mots clés + relation sémantiques entre les mots clés Ontologie / réseau sémantique : Liste de concepts + relations entre les concepts Dictionnaire de mots : Exemple : WordNet (pour l’anglais) 40 SRI & Big Data  Vocabulaire contrôlé WordNet est un dictionnaire (gratuit) de mots anglais créé par des chercheurs à l’université de Princeton Contenu de WordNet : Mots en anglais organisés en synsets : ensembles de mots synonymes Les synsets ont des définitions et des relations entre elles Un mot peut appartenir à plusieurs synsets Relations sémantiques entre synsets : Hyperonymie/hyponymie(généralisation/spécialisation) : is-a Antonymie (opposé à) 41 SRI & Big Data  Exemple : « City » dans WordNet 42 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 43 SRI & Big Data  L’indexation manuelle Idée de l’Indexation manuelle : On identifie pour chaque document les termes clés qui les représentent On enrichie manuellement la base d’indexes (Terme / Documents). Les termes peuvent être issus d’un langage contrôlé (recommandé) L’indexation manuelle se fait par le biais d’une interface d’indexation telle un formulaire (pas besoin d’être un informaticien) Précondition: Nécessité d’être un expert des documents concernés par l’indexation (bien connaître les documents et leur contenu) 44 SRI & Big Data  L’indexation manuelle Exemple : 45 SRI & Big Data  L’indexation manuelle Cas d’application : Souvent utilisées pour l’indexation des livres dans les bibliothèques et les centres de documentation Indexation de fichiers multimédias (images, vidéos, sons/ enregistrements vocaux, …) Indexation de fichiers spécifiques d’applications (cas où il est difficile d’en extraire du texte, ou le texte n’a pas de sens) 46 SRI & Big Data  L’indexation manuelle Avantages : Permet l’indexation de tous documents/fichiers sans se soucier de leurs formats et contenus Cas d’utilisation d’un vocabulaire contrôlé : Fournit une terminologie standard pour indexer et rechercher les documents Permet la classification (regroupement) de documents (par sujets, thème,…) Permet facilement une recherche par navigation dans les concepts et terminologies 47 SRI & Big Data  L’indexation manuelle Inconvénients : Indexation très coûteuse: pour construire le vocabulaire pour affecter les concepts (termes) aux documents Difficile à maintenir: La terminologie évolue, plusieurs termes sont rajoutés tous les jours Processus humain donc subjectif : Des termes différents peuvent être affectés à un même document par des indexeurs (humains) différents Les utilisateurs ne connaissent pas forcément le vocabulaire utilisé par les indexeurs 48 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 49 SRI & Big Data  L’indexation automatique Idée de l’indexation automatique : Le système (programme) informatique se charge de parcourir chaque document et d’en extraire les termes qui serviront à l’indexation Approche : L’approche courante est statistique avec les hypothèses suivantes: La redondance d’un mot marque son importance La cooccurrence des mots marque le sujet d’un document Autre critère pouvant être pris en compte: la position du terme dans le document (important dans le cas où la requête est une expression) 50 SRI & Big Data  L’indexation automatique : les étapes Démarche générale de l’indexation automatique : Etape 1 : Extraction des termes Etape 2 : Normalisation des mots / lemmatisation (regroupement des variantes d’un mot ) Etape 3 : Pondération (discrimination entre les termes clés/importants/significatifs et les autres) 51 SRI & Big Data  L’indexation automatique : les étapes Etape 1 : Extraction des termes Extraction de termes = tockenization Terme (tocken) : mot (simple/compose), mots clés, concepts Mot : suite de caractères séparés par des séparateurs (espace, signe de ponctuation, caractères spéciaux, retour à la ligne, tabulation,…), Nombres Les termes retenus seront les index utilisés pour la recherche Il faut prendre en compte les spécificités des langues : Langue française : Pomme de terre : 1, 2 ou 3 termes? Langue Allemande les mots composés ne sont pas segmentés: Lebensversicherungsgesellschaftsangestellter = "life insurance company employee" 52 SRI & Big Data  Etape 1 : Extraction de termes Pas d’espaces en chinois et en japonais Ne garantit pas l’extraction d’un terme de manière unique Le Japonais encore plus compliqué avec différents alphabets La langue arabe s’écrit de droite à gauche avec certains termes écrits de gauche à droite (ex : les chiffres) 53 SRI & Big Data  Etape 1 : Extraction de termes Suppression des mots « vides » (stoplist / Common Words removal) : Il s’agit de mots trop fréquents et pas utiles (à supprimer lors de la tockenisation) Il peut s’agir d’articles, de pronoms, de mots de liaison… (le choix des stopwords dépendent de la langue et du contexte) Exemples : Anglais : the, or, a, you, I, us, to, … Français : le , la, de, des, je, tu, à, aux, … Il faut faire attention à certaines exceptions: Certaines abréviations font référence à autre chose qu’aux stopwords Exemple: “US” pour dire ”USA” 54 SRI & Big Data  L’indexation automatique : les étapes Etape 2 : Normalisation Il s’agit de Lemmatisation (radicalisation, racinisation) / (stemming en anglais) : Processus consistant à regrouper les variantes d’un mot (mot de même famille) pour lui donner la forme neutre (canonique) qu'il a (forme proche du radical / racine). cette forme canonique est appelée lemme. Exemples : grand, grande, grands, grandes, grandement => grand La forme canonique de tous ces mots dont le sens premier exprime une taille importante est grand. Pour l’anglais : retrieve, retrieving, retrieval, retrieved, retrieves => retriev est le lemme de tous ces mots 55 SRI & Big Data  Etape 2 : Normalisation Techniques de normalisation: Approche algorithmique de transformation de mots en lemme : ces algorithmes appliquent des règles de désuffixation (suppression des suffixes). Soit le suffixe est supprimé, soit il est transformé selon des règles pour avoir la forme canonique du mot. Les algorithmes les plus connus : Algorithme de Porter pour l’anglais Algorithme de Carry pour le français Algorithme de Paice/Husk Approche par dictionnaire : Lemmatisation avec un lexique / dictionnaire : suppression de suffixes puis recherche de la racine correspondante dans le dictionnaire Technique de Troncatures: couper jusqu’à X caractères 56 SRI & Big Data  Approche algorithmique L’algorithme de Porter : Permet la désuffixation de mots anglais (enlever les suffixes) à commencer par la transformation du pluriel au singulier. Les règles de transformation sont classées en sept phases successives (traitement des pluriels et verbes conjugués, traitement des adverbes...) Il comprend cinq règles de contexte, qui indiquent les conditions dans lesquelles un suffixe devra être supprimé. La terminaison en -ing, par exemple, ne sera enlevée que si le radical comporte au moins une voyelle. Exemple : "troubling" deviendra "troubl", mais "sing" restera "sing". Les mots à analyser passent par toutes les étapes de désuffixation, et, dans le cas où plusieurs règles pourraient leur être appliquées, c'est toujours celle comprenant le suffixe le plus long qui est choisie. La racinisation (désuffixation) est accompagnée à chaque étape de règles de recodage 57 SRI & Big Data  L’algorithme de Porter Exemples : Règles Exemples en anglais SSES → SS caresses → caress SS → SS caress → caress S→ cats → cat ATIONAL → ATE relational → relate TIONAL → TION conditional → condition ATIVE → formative → form ALIZE → AL formalize → formal Exemples de transformation du mot : Generalizations étape1: Generalization étape 2: Generalize étape 3: General 58 étape 4: Gener SRI & Big Data  L’algorithme de Porter Aperçu des étapes: 59 SRI & Big Data  L’algorithme de Porter Implémentation de l’algorithme de porter (disponible an plusieurs langages de programmation) : https://tartarus.org/martin/PorterStemmer/index.html 60 SRI & Big Data  Approche algorithmique Pour la langue française : Les lemmes de la langue française peuvent avoir plusieurs formes en fonction : du genre (masculin ou féminin), de leur nombre (un ou plusieurs), de leur personne (moi, toi, eux…), de leur mode (indicatif, impératif,…) L’algorithme Carry fonctionne sur le même principe que l’algorithme de porter, et est téléchargeable gratuitement sur le site du projet GALILEI http://www.otlet-institute.org/GALILEI_Platform_fr.html 61 SRI & Big Data  Approche avec lexique Approche avec utilisation d’un lexique : L’outil TreeTagger https://www.cis.lmu.de/~schmid/tools/TreeTagger/ Version online: https://cental.uclouvain.be/treetagger/ Il s’agit d’un outil de lemmatisation et d’annotation de texte, créé par Helmut Schmid à l’université de Stuttgart Prend en compte plusieurs langues (français, anglais, allemand, italien, espagnol, portugais, russe, …) et peut être adapté à de nouvelles langues (si le lexique est fourni + un corpus entrainé ) De manière générale on y applique les règles suivantes: Pour un verbe conjugué: on prend sa forme à l'infinitif Pour un nom, adjectif, article,... : sa forme au masculin singulier L’outil peut être utilisé dans un cadre d’études / recherche / enseignement, mais est interdit d’usage commercial 62 SRI & Big Data  Exemple avec TreeTagger Phrase à lemmatiser : « Il s’agit d’un cours d’informatique sur la recherche d’information » Résultat : 63 SRI & Big Data  Etape 2 : Normalisation Utilisation de Troncature : Il s’agit de couper un mot au Xème caractère pour supprimer éventuellement des suffixes Valeur optimale de X pour le français : 7 caractères Exemple de troncature à 7 caractères économiquement : écomoni Quelques limites : Le nombre de caractère dépend de la langue. Certaines langues ne peuvent pas supporter cette technique Pas suffisant pour trouver une racine : certains mots, notamment les verbes, changement complètement de forme Exemple : verbe être : est, fut, soit Certains mots ont des sens différents mais deviennent le même lemme à la troncature. Exemple : Informatique et information => informa 64 SRI & Big Data  Etape 2 : Normalisation Autre technique : méthode des n-gram : Un n-gram est une succession de n lettres n = 1, 2, 3 Exemple : retrieval 1-gram : r, e, t, r, i, e, v, a, l 2-gram : re, et, tr, ri, ie, ev, va, al 3- gram : ret, etr, tri, rie, iev, eva, val Utile pour la racinisation pour certaines langues complexes, où il est difficile de trouver des règles de désuffixations 65 SRI & Big Data  Méthode des n-gram Hypothèse retenue: si les n-gram de deux mots ont une forte similitude alors ils ont de fortes chances d’être de la même famille Exemple : Comparaison de retrieve et retrieval avec 3-gram: A=retrieve : ret, etr, tri, rie, iev, eve B=retrieval ret, etr, tri, rie, iev, eva, val On calcule leur similitude avec la formule : Sim (A,B)=2*nb_comm/(nb_A +nb_B) Sim(A,B) = 0.76 Plus le rapport est proche de 1, plus la similitude est forte (il faut pour cela déterminer un seuil au delà duquel on accepte la similitude) 66 SRI & Big Data  Etape 2 : Normalisation Avantages de la normalisation : Permet d’avoir un terme commun qui fait référence à tous les termes d’une même famille Augmente les chances de répondre efficacement à une requête (quelque soit la technique de matching appliquée…) Permet de réduire la taille de la base d’index (c’est surtout pour cette raison qu’on utilise la normalisation) 67 SRI & Big Data  Etape 2 : Normalisation Limites de la normalisation : Peut conduire à une normalisation « agressive » Exemples : avec l’algorithme de Porter: policy/police, university/universe, organization/organ avec troncature: Internet/Interne Oubli de quelques normalisations intéressantes: Exemples : matrices/matrix, machine/machinery ne sont pas normalisés avec Porter Produit des mots difficiles à interpréter : Exemples : avec Porter: “iteration” produit “iter”, “general” produit “gener” 68 SRI & Big Data  L’indexation automatique : les étapes Etape 3 : Pondération Comment caractériser l’importance des termes dans un document ? Associer un (ou plusieurs) poids a un terme Idée sous jacente : Les termes importants doivent avoir un poids fort Approche la plus répandue : TF.IDF (du « Modèle vectoriel ») Enregistrer la position du terme dans le document (pour identifier les expressions et mots composés fréquents) Exemple: pomme de terre 69 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 70 SRI & Big Data  L’indexation semi-automatique L’indexation semi-automatique est la combinaison des deux techniques manuelles et automatiques Exemple : Dans le cas de documents contenant du texte : On automatise d’abord l’extraction des termes des documents (suppression de stopwords, lemmatisation, pondération éventuellement …) Les termes sélectionnés vont être proposés à l’utilisateur (expert de l’indexation manuelle) pour correction / validation et/ou pour l’ajout de nouveaux termes 71 SRI & Big Data  L’indexation : Synthèse Sources d’information Processus … d’indexation Documents textuels, images, vidéos, … (manuel, auto, semi-auto) Index Index Index A quoi ressemble une base d’index ? 72 SRI & Big Data  Structure de la base d’index Quelque soit la méthode et techniques d’indexation choisies, la rapidité et l’efficacité de la recherche dans la base d’index dépend de sa structure L’indexation permet d’obtenir (par défaut) une liste de termes décrivant chaque document : Le problème de cette forme de structure est que la recherche d’un terme est lente : on recherche le terme séquentiellement dans chaque document ⟹ La structure d’index la plus communément utilisée dans les moteurs de recherche est de forme : inverted index (fichier inversé) 73 SRI & Big Data  Structure de la base d’index Structure inverted index : Terme → {doc1, Doc2, …} Une structure inverted index contient chaque terme sélectionné dans les documents comme index, avec pour chaque index la référence à tous les documents qui le contiennent Cette structure peut être enrichie par: la fréquence du terme dans chaque document et la position 74 SRI & Big Data  Structure de la base d’index Exemple 1: Les documents D1, D2 et D3 contiennent les textes suivants: Pour chaque document des termes seront sélectionnés (après traitement), on parle de bag of words (sac de mot ) Pour D1 = c’ , est, ce, que Pour D2 = c’, est, ceci Pour D3 = ceci, est, une, banane Ces mots seront utilisés comme index 75 SRI & Big Data  Structure de la base d’index La structure inverted index résultante : N.B: chaque index dans une structure d’index est unique 76 SRI & Big Data  Structure de la base d’index Il existe deux types de structure d’index inversé : Record-Level Inverted Index : Le fichier d'index inversé contient une liste de références aux documents pour chaque terme utilisé comme index Word-Level Inverted Index : Le fichier d'index inversé contient non seulement la liste de références aux documents, mais également les positions de chaque mot dans un document. Cette dernière forme offre plus de fonctionnalités mais nécessite plus de puissance de traitement et d'espace pour être créée. Un autre critère est aussi pris en compte pour les deux types de structures: la fréquence du mot dans le document. La fréquence d’un mot permet de connaître son importance dans le document pour: décider de le sélectionner ou pas (cas de collections importantes) de savoir où le classer dans la liste des résultats 77 SRI & Big Data  Structure de la base d’index Exemple 2: fréquence DocId [positions] Inverted Index 78 SRI & Big Data  Structure de la base d’index Avantages: Recherche efficace : les index inversés permettent une recherche efficace de grands volumes de données textuelles. En indexant chaque terme de chaque document, l'index peut identifier rapidement tous les documents contenant un terme ou une expression de recherche donnée, réduisant ainsi considérablement le temps de recherche. Mises à jour rapides : les index inversés peuvent être mis à jour rapidement et efficacement à mesure que du nouveau contenu est ajouté au système. Cela permet une indexation et une recherche de nouveau contenu en temps quasi réel. Compression : les index inversés peuvent être compressés pour réduire les besoins de stockage. Diverses techniques telles que le delta encoding, gamma encoding, variable byte encoding, etc. peuvent être utilisées pour compresser efficacement. 79 SRI & Big Data  Structure de la base d’index Prise en charge de plusieurs langues : les index inversés peuvent prendre en charge plusieurs langues, permettant aux utilisateurs de rechercher du contenu dans différentes langues en utilisant le même système. 80 SRI & Big Data  Structure de la base d’index Comment rechercher dans une base d’index: Recherche séquentielle : temps linéaire dans la taille du vocabulaire indexé (Utile pour une petite base d’index uniquement). Recherche dichotomique : les index doivent être triés. on regarde le mot du milieu, on cherche sur le même principe dans la première ou seconde moitié (Temps logarithmique dans la taille du vocabulaire). Recherche avec un arbre de recherche : arbre dont les feuilles donnent accès à la ligne et les noeuds disent quelle branche suivre (Temps logarithmique dans la taille du vocabulaire). Recherche avec une fonction de hachage : fonction qui calcule le numéro de ligne à partir du mot. (Temps constant). 81 SRI & Big Data  Structure de la base d’index Remarque : Le stockage d’une structure d’index peut s’avérer très couteux en espace de stockage mais également en recherche. Dans le cas de très larges collections il faut penser à un système distribué pour les tâches d’indexation. L’un des modèles connus pour cela est le modèle du MapReduce de Google. 82 SRI & Big Data  Conclusion sur l’indexation L’indexation est une phase complexe qui nécessite des choix à faire à plusieurs niveaux (indexation manuelle ou automatique ou les deux, techniques d’extraction, de normalisation, structure de la base d’index,…). Ces choix dépendent aussi de : La taille de la collection La nature des ressources (documents/ fichiers) concernées par la RI Les techniques de RI utilisées pour le matching requête/documents Remarque : Pour déterminer si la représentation d'un document correspond à celle de la requête, on doit développer un processus de matching (avec évaluation des résultats pour vérifier son efficacité) Différents modèles ont été développés en relation avec la représentation de documents et de requêtes. C'est cet ensemble de représentations et la technique de mise en correspondance et de sélection des résultats qu'on appelle un modèle de RI. 83 SRI & Big Data  Les modèles de RI 84 SRI & Big Data  Les modèles de RI Notion de modèle dans le processus de RI : X Y Z Représentation des documents Représentation matching de la requête Index Un modèle de RI spécifie comment est la représentation d’une requête, comment est la représentation d’un document et comment faire la mise en correspondance (matching) entre les deux représentations 85 SRI & Big Data  Les modèles de RI Il existe deux formes de matching (mise en correspondance / appariement) dans la RI : exact matching / best matching Exact matching: On spécifie dans la requête les termes recherchés de manière précise L’ensemble des documents respectant exactement la requête sont sélectionnés (mais pas ordonnés) Best matching : On spécifie dans la requête les termes recherchés Les documents sont sélectionnés selon un degré de pertinence (similarité/ probabilité ) vis-à-vis de la requête et sont ordonnés (par pertinence) 86 SRI & Big Data  Les modèles de RI Plusieurs modèles de RI existent : Modèle booléen (1950) Modèle vectoriel (1970) Modèle probabiliste (1976) Modèle inférentiel (1992) Modèle LSI (Latent Semantic Indexing) (1994) Modèle de langage (1998) … 87 SRI & Big Data  Modèle Booléen Il s’agit du premier modèle de RI (modèle booléen strict) Caractéristiques : Représentation d’un document: un document est représenté par un ensemble de termes (qui indexent le document) : D = (𝑡1 , 𝑡2 , …, 𝑡𝑖 ) avec i ∈ [1, … , 𝑁] Représentation de la requête : une requête est une expression logique de termes avec des opérateurs booléens: AND (ᴧ) OR (ᴠ) NOT (¬) Exemple : Q = (𝑡1 ᴧ 𝑡2 ) ᴠ (𝑡3 ᴧ ¬ 𝑡4 ) Technique d’appariement « Exact match » : présence des termes de la requête dans la représentation d’un document → document sélectionné 88 SRI & Big Data  Modèle Booléen Exemple : D1 = (𝑡1 , 𝑡3 , 𝑡4 ) D2 = (𝑡2 , 𝑡4 ) D3 = (𝑡1 , 𝑡2 , 𝑡4 , 𝑡5 ) D4 = (𝑡1 , 𝑡4 ) Q1= (𝑡2 ᴧ 𝑡4 ) Q2 = 𝑡5 ᴠ (𝑡1 ᴧ ¬ 𝑡3 ) ⟹ D2 et D3 répondent à la requête Q1 ⟹ D3 et D4 répondent à la requête Q2 89 SRI & Big Data  Modèle Booléen Limites du modèles : Formulation de la requête avec les opérateurs de logique pas évidente (voire difficile) pour beaucoup d’utilisateur Sélection des documents sur décision binaire (soit le document répond à la requête, soit il n’y répond pas) Pas de classement des documents sélectionnés (pas de degré de pertinence entre les documents car ils n’ont pas de poids) Pour les collections volumineuses : risque de sélection de beaucoup trop de documents en résultat (surtout à cause de l’opérateur OR) 90 SRI & Big Data  Modèle Booléen pondéré Extension du modèles : Modèle booléen pondéré On intègre des pondérations dénotant la représentativité de tous les termes T d’une requête pour un document La fonction de pondération 𝑊𝐷 pour un document est: 𝑊𝐷 : T → [0,1]. Pour chaque terme de la requête, le poids de ce terme dans D vaut : 0 pour un terme non présent dans le document 1 pour un terme présent dans le document La fonction de correspondance entre les termes de la requête et des documents, notée Sim, est basée sur un calcul de similarité selon l’opérateur logique (AND, OR, NOT) 91 SRI & Big Data  Modèle Booléen pondéré Cas de l’opérateur NOT: 𝑺𝒊𝒎 𝑫, ¬𝒂 = 𝟏 − 𝑾𝑫 (a) Cas des opérateurs AND et OR : Formules 1 inspirées de la logique floue (ne tenant pas compte de tous les termes de la requête) 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝑴𝒂𝒙 [𝑾𝑫 (a), 𝑾𝑫 (b)] (a, b les termes d’une requête) 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝑴𝒊𝒏 [𝑾𝑫 (a), 𝑾𝑫 (b)] Formules 2 avec prise en compte de tous les termes de la requête 𝑾𝑫 𝒂 2 + 𝑾𝑫 𝒃 2 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝟐 𝟏−𝑾𝑫 𝒂 𝟐 + 𝟏−𝑾𝑫 𝒃 𝟐 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝟏 − 𝟐 92 SRI & Big Data  Modèle Booléen pondéré Exemple : on considère A et B les termes d’une requête Modèle pondéré Documents A B (A ᴠ B) (A ᴧ B) (A ᴠ B) (A ᴧ B) (formule 2) (formule 2) D1 1 1 1 1 1 1 D2 1 0 1 0 0,7 0,29 D3 0 1 1 0 0,7 0,29 La pondération permet ici de classer les documents Exemple: Pour la requête (A ᴠ B) avec le modèle pondéré, D1 sera classé en 1er, suivi de D2 et D3 dans le même ordre. 93 SRI & Big Data  Modèle Vectoriel Modèle créé au début des années 70 par Gerard Salton, appliqué pour la RI avec le système SMART (System for the Mechanical Analysis and Retrieval of Text) Caractéristiques : Modèle best-match le plus commun Requête en texte libre (un ou plusieurs termes) Documents ordonnés dans les résultats : on tient compte du poids des termes de la requête dans les documents pour pouvoir les classer (on parle de pondération) Les documents et la requête sont représentés comme des vecteurs dans un espace vectoriel : il s’agit de vecteur de poids Document : dj= (w1j, w2j, …, wNj) avec : Wij poids du terme ti dans le document dj 94 Requête : q= (w1q, w2q, …, wNq) Wiq : poids du terme ti dans la requête q SRI & Big Data  Modèle Vectoriel Illustration : représentations des documents et d’une requête dans un espace vectoriel de termes ti Plus les vecteurs représentant les documents sont proches, plus les documents sont similaires Plus l’angle entre la requête est le document est petit, plus le document répond à la requête On calcule la similarité vectorielle entre l’angle d’un document et d’une requête en utilisant le poids des termes (la mesure de 95 similarité la plus utilisée est la formule du cosinus) SRI & Big Data  Modèle Vectoriel Notion de pondération : Pondérer les termes permet de connaître leur importance dans la recherche pour sélectionner les documents les plus pertinents et les classer La pondération des termes pour une requête est simple : fréquence du terme dans la requête (term frequency) La pondération pour les documents est une notion plus complexe. Elle tient compte de : l'importance du terme dans le document (pondération locale) l'importance du terme dans la collection (pondération globale) La mesure la plus connue pour la pondération des termes pour un document est : tf.idf 96 SRI & Big Data  Modèle Vectoriel Les mesures: tf = Term Frequency est la fréquence du terme dans le document df = Document Frequency est la fréquence du terme dans la collection (corpus entier) on utilise la mesure df inversée, notée idf (Inverted Document Frequency) 97 SRI & Big Data  Modèle Vectoriel Formules : tf : (terme frequency) Formule simple du tf: est la fréquence du terme ti dans le document dj (nombre d’occurrences) tfi,j = freq(ti, dj) Variante du tf: fréquence normalisée logarithmiquement tfi,i = 1+ log(freq(ti, dj)) si freq(ti, dj) ≠ 0 idf : (inverted document frequency) Formule simple : idfj = 1 / dfj avec dfj nombre de documents où apparait le terme tj Formule normalisée logarithmiquement : idfj = log(N / dfj) avec N le nombre de documents du corpus Le poids de chaque terme ti dans un document dj est calculé: 98 Wi,j = tfi,j.idfj SRI & Big Data  Modèle Vectoriel Exemple de calcul de pondération : On considère la structure inverted index suivante : Terme DocId Freq Pomme d1 1 d2 3 d3 2 Poire d1 1 d3 2 d4 1 99 SRI & Big Data  Modèle Vectoriel → Pondération pour le terme t1 = pomme avec formule simple : Wt1,d1 = 1 x (1/3) = 0,33 Wt1,d2 = 3 x (1/3) = 1 Wt1,d3 = 2 x (1/3) = 0,67 → Pondération pour le terme t1 avec formule logarithmique : Wt1,d1 = (1 + log(1)) x (log(4/3)) = 0,12 Wt1,d2 = (1 + log(3)) x (log(4/3)) = 0,18 Wt1,d3 = (1 + log(2)) x (log(4/3)) = 0,16 N.B : d4 n’est pas indexé avec le terme pomme, il ne sera donc pas pris en compte dans le calcul des poids 100 SRI & Big Data  Modèle Vectoriel Fonction de matching: La similarité entre les représentations d’une requête Q et d’un document D est notée Sim(Q,D) et est calculée grâce à la formule du cosinus (cosine similarity): 𝑆𝑖𝑚 (𝑄, 𝐷) = cos(𝑄, 𝐷) = avec : Wi Q : poids des termes dans la requête (tf) Wi D : poids des termes dans le document (tf.idf) N.B: La similarité est comprise entre 0 et 1: résultat proche de 1 si les termes sont similaires, proche de 0 sinon. Dans le cas de larges collections, l’idéal est d’avoir un seuil de pertinence 101 ou de choisir les k-best score SRI & Big Data  Modèle Vectoriel Remarques : D’autres mesures de similarité existent en RI, telles que: Coefficient de Dice : Mesure de Jaccard : qi : poids du terme ti dans la requête di : poids du terme ti dans le document 102 SRI & Big Data  Modèle Vectoriel Avantages: Le langage de requête est simple (liste de mots) La pondération améliore les résultats de recherche La mesure de similarité permet d’ordonner les documents selon leur pertinence vis à vis de la requête Limites : Le modèle considère les termes indépendants, alors que ce n’est pas forcément le cas. Exemple: « pomme » et « pomme de terre » sont deux notions différentes. Si la structure d’index contient la position des termes, il est souhaitable d’en tenir compte (par exemple, inclure une condition qui vérifie d’abord la position des termes avant de calculer leur fréquence) Il n'y a pas de schéma de pondération optimal (dépend du corpus et de la requête) 103 SRI & Big Data  Amélioration des résultats Il existe des techniques pour améliorer les résultats retournés par un SRI (après l’affichage des résultats) La plus connues est la technique du Relevance feedback :il s’agit de reformuler la requête à partir des résultats et grâce au retour de l’utilisateur Principe du Relevance feedback: On estime que la première requête de l’utilisateur est souvent naïve et spontanée On permet à l’utilisateur de donner son avis (feedback) sur les résultats (sous une forme précise) La requête originale est reformulée (étendue avec de nouveaux termes) et re-pondérée 104 SRI & Big Data  Relevance feedback Illustration : Résultats : Ensemble de documents ordonné + Feedback utilisateur Nouvelle requête étendue Exemple de feedback : L’utilisateurs examine les k meilleurs documents et les étiquettes avec des valeurs [1,0] L’utilisateur classe les k meilleurs résultats par ordre de pertinence 105 selon son point de vue SRI & Big Data  Les modèles de RI Remarque 1: Les modèles de RI ont été inventés avant l’apparition de la technique de lemmatisation des mots dans l’indexation automatique. Les lemmes qui servent d’index peuvent être légèrement différents des termes de la requête et donc peuvent poser problème lors de la recherche. Exemple: on saisit le terme «économique» dans la requête mais c’est « économi » qui est enregistré dans la base. Il est possible de vérifier la similarité entre deux termes en utilisant des mesures de calcul de similarité (edit-distance). Parmi les plus connues: Levenshtein distance Damerau- Levenshtein distance Jaro-Winkler distance … 106 SRI & Big Data  Les modèles de RI Remarque 2 : Le stockage d’une structure d’index peut s’avérer très couteux en espace de stockage mais également en recherche. Dans le cas de très larges collections il faut penser à un système distribué pour les tâches d’indexation. L’un des modèles connus pour cela est le modèle du MapReduce de Google. 107 SRI & Big Data  Evaluation des SRI 108 SRI & Big Data  Evaluation des SRI Notion de pertinence des résultats : La pertinence est: la correspondance entre un document et une requête, un degré de relation (chevauchement, relativité, …) entre le document et la requête; un degré de la surprise qu'apporte un document, qui a un rapport avec le besoin de l'utilisateur; une mesure d'utilité du document pour l'utilisateur; … Les utilisateurs d'un système de RI ont des besoins très variés. Ils ont aussi des critères très différents pour juger si un document est pertinent ou pas. 109 SRI & Big Data  Evaluation des SRI Certains paramètres entrent en compte dans la pertinence des résultats d’un SRI (surtout pour les moteurs web): Profil de l’utilisateur Un besoin d’information exprimé par deux personnes de la même manière ne fournit pas forcément les mêmes réponses (prise en compte du profil de l’utilisateur quand il est connecté par exemple) Expérience de l’utilisateur à chaque même requête (relevance feedback) Contexte « externe » du besoin d’information Temporel : Un besoin d’information exprimé à différents moments n’a pas le même sens Géographique : Un besoin d’information exprimé à différents endroits n’a pas le même sens) (« restaurant » à Marrakech ne nécessite pas forcément de réponses de restaurants à Paris) 110 SRI & Big Data  Evaluation des SRI De manière générale, le but de la RI est de trouver seulement les documents pertinents à une requête, et donc utiles pour l'utilisateur Document pertinent = document où l'utilisateur doit pouvoir trouver les informations dont il a besoin. La qualité d'un système doit être mesurée en comparant les réponses du système avec les réponses idéales que l'utilisateur espère recevoir. Plus les réponses du système correspondent à celles que l'utilisateur espère, mieux est le système Pour arriver à une telle évaluation, on doit d'abord connaître les réponses idéales de l'utilisateur. L'évaluation d'un système se fait ensuite avec : un corpus de test 111 et des métriques connues en RI : Précision et Rappel. SRI & Big Data  Evaluation des SRI Dans un corpus de test, il y a: un ensemble de documents un ensemble de requêtes la liste de documents pertinents pour chaque requête (d’un point de vue utilisateur) Prérequis (pour des résultats assez objectifs): Les requêtes doivent traiter des sujets variés Il faut une collection assez variées contenant les documents pertinents (qui répondent aux requêtes) et d’autres moins pertinents Il faut des utilisateurs experts qui savent juger la pertinence d’un document (pour chaque requête, quelles sont les résultats attendus) 112 SRI & Big Data  Evaluation des SRI On compare les résultats obtenus par le système avec les résultats établis par les experts Les métriques utilisées en RI: Précision : proportion de document pertinents retrouvés parmi tous les documents retrouvés par le système Rappel : proportion de document pertinents retrouvés parmi tous les documents pertinents dans la collection 113 SRI & Big Data  Evaluation des SRI Illustration : Résultats obtenus Pas obtenus (sélectionnés) False True False True Negative Positive Positive Negative (FN) (TP) (FP) (TN) Pertinents Non pertinents 114 SRI & Big Data  Evaluation des SRI Ces mesures permettent d’améliorer : la qualité des index la formulation des requêtes la technique de matching entre les deux Il n’y a pas de bons taux de précision et de rappel. Ces deux mesures sont fortement liées: quand l’une augmente, l’autre diminue. L’objectif est de trouver le bon rapport entre la précision et le rappel: on parle de moyenne harmonique La moyenne harmonique entre précision et rappel est nommée: F-mesure (ou F-score) : 115 SRI & Big Data  Evaluation des SRI Exemple : (pour 1 requête) Nombre de docs dans la collection : 100 Nombre de docs pertinents dans la collection : 60 Nombre de docs sélectionnés : 30 dont 10 non pertinents Matrice de confusion Selected (confusion matrix) TP = 20 FP = 10 Predicted FN = 40 TN = 30 Precision = 20/(20+10) = 0,67 Rappel = 20/(20+40) = 0,33 F-score = 0,44 116 SRI & Big Data  Exemples d’implémentations Frameworks et moteurs de RI connus: Lucene : est une bibliothèque d’indexation et de recherche d’information textuelle, écrite en Java (existe aussi en: C++, C#, Perl, Python,…), disponible sous licence Apache. Le processus d’indexation et de recherche est traité de manière générale. Beaucoup de classes sont abstraites et doivent être spécialisée (par exemple, pour l’extraction automatique des termes pour les index, il y a une classe abstraite Analyzer, pour la recherche, une classe abstraite Query proposant différentes méthodes abstraites pour des requêtes booléennes, requêtes avec préfixe, …). Moteurs et applications de RI basées sur Lucene: Elastic seach, Solr, Nutch (web crawler) Xapian : moteur open source écrit en C++ offrant des fonctions d’indexation et de recherche (licence GPL). Il met en œuvre l’approche probabilistique de la RI et des opérateurs booléens pour la recherche 117 SRI & Big Data  Notion de métamoteur Un métamoteur (ou méta-chercheur) est un moteur de recherche qui puise ses informations d’autres moteurs de recherche connus : Le métamoteur interroge plusieurs moteurs de recherche (Google, Bing, Ask, Yahoo!,…) et retourne les résultats de chacun d'eux. Il n’y a pas de redondance dans les résultats puisque les résultats similaires sont éliminés (par exemple: si les moteurs Google et Yahoo! renvoient quelques mêmes liens, le métamoteur ne va les afficher qu'une seule fois dans la liste des résultats). Certains métamoteurs indiquent de quels moteurs de recherche provient chaque résultat Exemples : Moteurs généralistes: DogPile, Yippy, StartPage, Metacrawler Moteurs spécialisés: SiteSeerX, GoogleScholar, CCSearch, Indeed 118 SRI & Big Data  La RI sur le web 119 SRI & Big Data  La RI sur le web Caractéristiques du web : Taille : très grand nombre de documents (milliards et plus) Hétérogénéité : très grande variété de documents Répartition : documents répartis sur Internet Structure du Web : documents interconnectés par des hyperliens ⟹ Environnement complexe : Il faut parcourir le web tous les jours, toutes les heures … pour indexer la nouveauté La recherche doit être rapide et les résultats assez pertinents pour le plus d’utilisateurs possibles (sinon le moteur ne sera pas utilisé) Les moteurs de recherche web se basent sur les fondamentaux de la RI (indexation avec inverted index, recherche avec pondération, classement,…), mais ont leur propre techniques pour indexer et rechercher 120 SRI & Big Data  La RI sur le web Côté indexation : Les moteurs web utilise des web crawler (robots d’indexation ou collecteur) Un web crawler parcourt le web, visite le contenu des ressources trouvées (page web, documents,…) et extrait le maximum d’informations (pour ensuite en faire des index) Il procède en suivant récursivement les hyperliens trouvés à partir d'une page De manière générale un robot d'indexation se charge des questions suivantes : quelles pages télécharger quand vérifier s'il y a des changements dans les pages comment éviter les surcharges de pages Web (délais en général) comment coordonner les tâches de manière distribuée (parallélisme) 121 SRI & Big Data  La RI sur le web Les index sont extraits à partir de plusieurs éléments des ressources web : le contenu du document des pages et toutes ressources du site la structure du titre : titres de niveau 1, de niveau 2,… les métadonnées : title, keywords l’adresse de la ressource web Les mots clés utilisés pour le référencement chez l’hébergeur du site Un fichier d'exclusion (robots.txt) placé dans la racine d'un site Web permet de donner aux robots une liste de ressources à ignorer. En résultat de l’indexation, on obtient : Des Index de très grande dimension : taille du vocabulaire → des millions et de la base de ressources → des trillions Des Index répartis : des fermes de calcul réparties dans le monde entier (le stockage aussi) 122 SRI & Big Data  La RI sur le web Exemples de web crawler : GoogleBot de Google AppleBot d’Apple (se charge aussi de l’assistant SIRI) Baiduspider du moteur de recherche chinois Baidu BingBot pour Bing et Yahoo! 123 SRI & Big Data  La RI sur le web Côté recherche : La requête de la recherche est une liste de mots clés (on trouve aujourd’hui des filtres dans les moteurs : par langue, par date,…) Le calcul du score de similarité entre la requête et les ressources web s’inspirent du modèle vectoriel (c-à-d avec pondération et classement selon le score). Les formules de calcul de score de similarité dans les moteurs web sont secrètes (et elles évoluent constamment) D’autres spécificités sont en plus prises en compte dans la sélection et le classement (outre le référencement naturel des sites): La langue et le pays de l’utilisateur /géolocalisation de la requête Historique de navigation / profil utilisateur Popularité d’une page, d’un site … 124 SRI & Big Data  La RI sur le web Une spécificité de Google: le PageRank Google a inventé la notion de PageRank qui consiste à évaluer la popularité/notoriété d’une page web Principe du PageRank : une page est importante si beaucoup de pages importantes pointent sur elle Plus la valeur du PageRank est élevée, plus la page en question est populaire 125 SRI & Big Data  La RI sur le web L’algorithme du PageRank mesure quantitativement la notoriété d’une page : il attribue à chaque page un score sous la forme d’une valeur sur une échelle de 0 à 10. Ce score estime le nombre de fois que cliquerait sur la page web un utilisateur à partir d’autres pages Parmi les éléments utilisés pour le calcul du score d’une page: les liens entrants et sortants, les ancres (liens HyperText) le trafic associé à la page le choix de la page dans les résultats d’une requête le nom de domaine A noter que PageRank est une marque déposée de Google et le principe est breveté Le PageRank joue un rôle majeur dans le classement des résultats du moteur Google 126 SRI & Big Data  Synthèse Pour créer un bon SRI il faut : Identifier toutes les ressources (documents) concernées par la recherche dans le système Choisir une bonne technique d’indexation (adaptées à la nature des ressources recherchées) Mettre en place une structure d’index inversée et même enrichie (N.B : choisir une technologie qui supporte l’évolution de la taille de la base) Définir la manière de formuler les requêtes (simple et intuitive) Choisir un modèle de RI approprié ou définir une technique de matching (mesure de similarité) efficace et adaptée au système Cas de grandes collections : il faut penser au traitement distribué (pour l’indexation et la recherche) 127 SRI & Big Data  Références [MOO 48] Mooers, C.N., Application of Random Codes to the Gathering of Statistical Information, MIT Master's Thesis, 1948. [CLE 67] Cleverdon, C.W., The Cranfield tests on index language devices. Aslib Proceedings 19(6), 173-193, 1967. [LAN 68] Lancaster, F.W., Evaluation of the MEDLARS Demand Search Service, National Library of Medicine, Bethesda, Maryland, 1968. [SAL 71] Salton, G., The SMART Retrieval System. Prentice Hall, Englewood Cliffs, NJ, 1971. [SAL 83] Salton, G., Fox, E.A., Wu, H. Extended Boolean Information Retrieval. Communications of the ACM 26(11), 1022-1036, 1983. 128 SRI & Big Data  Références Le domaine de recherche d’information – Un survol d’une longue histoire, Jian-Yun Nie, Université de Montréal Recherche d’information (RI) – Fondements -, Philipe Mulhen, CLIP-IMAG Recherche d’information et traitement automatique du langage, Laure Soulier, Science Sorbonne Université, 2019 Modèles en recherche d’information, Cours Master Recherche Paris 13 - Rechercher et extraction d’information, A. Rozenknop Une introduction à la recherche d’information, Remi Guilleron, Université Lille & INRIA Lille & Cristal UMR CNRS 129 SRI & Big Data  Références http://www.piaf- archives.org/sites/default/files/bulk_media/m06s7/co/06_sec tion7_4.html https://fr.wikipedia.org/wiki/Racinisation#:~:text=Algorithme %20de%20Porter,- L'algorithme%20d%C3%A9velopp%C3%A9&text=Les%20mots %20%C3%A0%20analyser%20passent,%C3%A9tape%2C%20d e%20r%C3%A8gles%20de%20recodage. https://cental.uclouvain.be/treetagger/ https://fr.wikipedia.org/wiki/Index_invers%C3%A9 https://www.geeksforgeeks.org/inverted-index/ 130 SRI & Big Data  Références https://www.geeksforgeeks.org/cosine-similarity/ https://fr.wikipedia.org/wiki/Lucene#:~:text=Lucene%20est%2 0une%20biblioth%C3%A8que%20open,%2C%20PHP%2C%20C %23%2C%20Python. https://fr.wikipedia.org/wiki/PageRank https://www.calcul-pagerank.fr/ https://www.metadosi.fr/marketing-internet/seo/google- pagerank/ 131 SRI & Big Data