Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
restricted:cm1 [2020/04/26 22:23] – [2. Similarité entre documents] edauce | restricted:cm1 [2021/01/12 22:50] (Version actuelle) – [TEXT MINING] edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ===== RECHERCHE D' | ||
+ | |||
+ | ==== 1. Généralités ==== | ||
+ | |||
+ | === 1.1 Base de textes === | ||
+ | Une bases de textes est un ensemble constitué de plusieurs textes. | ||
+ | |||
+ | Exemples : | ||
+ | * Bases de documents, dossiers contenant des documents, ... | ||
+ | * Collections de livres (électroniques) | ||
+ | * Contenus en ligne (descriptifs de films, articles de journaux, descriptifs de produits.) | ||
+ | * Messageries, | ||
+ | * Ensemble du web (les pages web étant vues comme du texte mis en forme au format html). | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | On note : | ||
+ | * d∈B : un document appartenant à la base B. | ||
+ | * t∈d : un terme présent dans le document d. | ||
+ | |||
+ | On dispose d’une base B de n documents textes. Une base documentaire B est un // | ||
+ | |||
+ | On note B={d1,d2,...}, | ||
+ | |||
+ | n est le nombre de documents de la base : n=|B|. | ||
+ | |||
+ | <note tip> | ||
+ | **Ordres de grandeur** | ||
+ | * Centre de documentation : n∈[102−104] | ||
+ | * Fournisseur de contenus (Amazon) : n∈[104−108] | ||
+ | * Moteur de recherche (Google) : n∈[108−1016] | ||
+ | </ | ||
+ | |||
+ | Les documents sont écrits dans un langage L obéissant à un vocabulaire V. | ||
+ | |||
+ | On note V={t1,t2,...} où chaque tk est un terme du vocabulaire V. | ||
+ | |||
+ | K est la taille du vocabulaire : K=|V|. | ||
+ | |||
+ | On note A l' | ||
+ | |||
+ | On note α∈A un caractère de l' | ||
+ | |||
+ | Un document texte pourra être décrit soit comme : | ||
+ | * une séquence de caractères (lettres) | ||
+ | * une séquence de termes (mots) | ||
+ | Soit d un document de B. Il peut être décrit comme : | ||
+ | * une suite de symboles : d=(α1,α2,...) avec αi∈A. | ||
+ | * ou une suite de mots : d=(t1,t2,...) avec ti∈V. | ||
+ | |||
+ | |||
+ | === 1.2 Recherche d' | ||
+ | Les algorithmes que l’on va étudier portent sur la recherche d' | ||
+ | |||
+ | La recherche dans les bases de textes nécessite la mise en oeuvre d' | ||
+ | |||
+ | Exemples : | ||
+ | * Recherche de textes contenant le terme : “artichaud” | ||
+ | * Recherche d’un motif (expression régulière) : une adresse email, une URL, un expéditeur, | ||
+ | |||
+ | Recherche documentaire : | ||
+ | {{: | ||
+ | |||
+ | → La réponse de l’algorithme est une liste ordonnée de références, | ||
+ | |||
+ | === 1.3 Problématiques de la recherche de texte === | ||
+ | - **performance** du programme, il faut considérer deux notes et non pas une seule. La performance d’un programme se mesure sur un axe (précision, | ||
+ | - **temps de réponse des algorithmes** : l’utilisateur classique veut attendre moins de 2 à 3 secondes. Sur des bases extrêmement grandes (type recherche web), il faut donc être très performant pour atteindre ces temps de réponses. | ||
+ | - **Stockage des données** : intégralité des textes ou simple descriptif/ | ||
+ | * Les moteurs de recherche par exemple ne stockent aucune page web, ils ne stockent que des index et des références. | ||
+ | * On parle de “Big Data" | ||
+ | - **Protection des données et vie privée** : la recherche par le contenu a accès au contenu des documents (textes, messages, notes), qui peuvent contenir des informations à caractère privé. L’indexation de ces textes et messages doit être fait avec le consentement de l' | ||
+ | |||
+ | |||
+ | === 1.4 Méthodes === | ||
+ | * Théorie de l' | ||
+ | * Apprentissage automatique (" | ||
+ | * Reconnaissance de formes | ||
+ | * Statistiques | ||
+ | |||
+ | === 1.5 Exemples de moteurs de recherche === | ||
+ | |||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | |||
+ | ==== 2. Similarité entre documents ==== | ||
+ | Pour mettre en oeuvre la recherche dans les bases de textes, on a besoin d'une **métrique** permettant de mesurer la similarités entre plusieurs documents. | ||
+ | |||
+ | <note tip> | ||
+ | La **similarité** est un score (un scalaire) permettant de mesurer la " | ||
+ | |||
+ | Plus le score de similarité entre deux documents est élevé, plus les documents sont proches (du point de vue de leur " | ||
+ | |||
+ | Les scores de similarité sont en général normalisés (entre 0 et 1 ou entre -1 et 1) | ||
+ | </ | ||
+ | |||
+ | Les distances classiques entre chaines de caractères étant inopérantes pour des textes de grande taille, on utilise en général une approche ensembliste/ | ||
+ | |||
+ | * Un document d est une liste ordonnée de termes : d=(d[1],d[2],...,) | ||
+ | * On cherche une représentation " | ||
+ | * L' | ||
+ | |||
+ | === 2.1 Approche ensembliste === | ||
+ | |||
+ | un document d est représenté par l' | ||
+ | |||
+ | Soient deux ensembles A et B. | ||
+ | |||
+ | L' | ||
+ | J(A,B)=|A∩B||A∪B| | ||
+ | |||
+ | Dans le cas où A et B sont des ensembles de termes, deux documents qui utiliseraient exactement les mêmes termes (mais pas dans le même ordre) auraient une similarité de 1 tandis que deux documents utilisant un vocabulaire strictement différent auraient une similarité de 0. | ||
+ | |||
+ | On notera que par construction, | ||
+ | |||
+ | < | ||
+ | **Exercice 1** : Donner la similarité de Jaccard entre les deux textes suivants: | ||
+ | |||
+ | texte 1 = "// | ||
+ | |||
+ | texte 2 = "// | ||
+ | |||
+ | (indication : " | ||
+ | </ | ||
+ | |||
+ | === 2.2 Approche basée sur les fréquences=== | ||
+ | |||
+ | L' | ||
+ | |||
+ | L' | ||
+ | |||
+ | < | ||
+ | * Soit '' | ||
+ | * Soit '' | ||
+ | * Soit '' | ||
+ | <code python> | ||
+ | cpt = {} | ||
+ | for mot in doc : | ||
+ | if mot not in cpt: | ||
+ | cpt[mot] = 1 | ||
+ | else: | ||
+ | cpt[mot] += 1 | ||
+ | | ||
+ | freq = {} | ||
+ | for mot in cpt : | ||
+ | freq[mot] = cpt[mot]/T | ||
+ | </ | ||
+ | </ | ||
+ | |||
+ | Remarque : la somme des fréquences vaut 1. | ||
+ | |||
+ | === Comparaison d' | ||
+ | Soit un message d constitué de T mots (d1, …, di, …, dT). | ||
+ | Chaque mot appartient à un vocabulaire V={t1,...,tK} de taille K. | ||
+ | |||
+ | Pour effectuer une comparaison basée sur les fréquences d' | ||
+ | |||
+ | Pour tout t∈V, on note f(t,d) la fréquence du terme t dans le document d. | ||
+ | |||
+ | * Un document d est représenté sous la forme d'un vecteur **réel** x∈RK | ||
+ | * (avec K la taille du vocabulaire) | ||
+ | * A tout terme t∈V on associe son index k∈1..K : | ||
+ | * xk=f(t,d)⇔t∈d | ||
+ | * xk=0⇔t∉d | ||
+ | |||
+ | |||
+ | **Remarque** : | ||
+ | x est un vecteur “creux”. Il contient beaucoup de 0 (le vocabulaire utilisé dans un texte est de taille ≪ K). | ||
+ | |||
+ | <note tip> | ||
+ | La transformation vectorielle traduit un texte d en un vecteur appartenant | ||
+ | * => passage d’une information qualitative à une information quantitative. | ||
+ | * => Des textes peuvent être : | ||
+ | * voisins | ||
+ | * colinéaires | ||
+ | * orthogonaux | ||
+ | * etc… | ||
+ | * tout comme des vecteurs de RK | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | En particulier, | ||
+ | <note important> | ||
+ | dist(x,y)=√∑i∈1..m(xi−yi)2 | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | En inversant la distance, on obtient la similarité euclidienne | ||
+ | sim(x,y)=11+dist(x,y) | ||
+ | </ | ||
+ | |||
+ | Plus intéressante, | ||
+ | <note tip> | ||
+ | sim(x,y)=x.y||x||×||y|| | ||
+ | </ | ||
+ | * Deux textes " | ||
+ | * Par exemple, deux textes utilisant un vocabulaire proche mais de taille (norme) tres différente peuvent avoir un score de similarité (colinéarité/ | ||
+ | * Deux textes " | ||
+ | |||
+ | === 2.3 Fréquence documentaire === | ||
+ | |||
+ | <note important> | ||
+ | Dans une langue donnée, si on considère l’ensemble des énoncés possibles, certains mots apparaissent plus fréquemment que d’autres. | ||
+ | |||
+ | * les plus fréquents : ''" | ||
+ | * très fréquent : ''" | ||
+ | * assez fréquent : ''" | ||
+ | * … | ||
+ | * très rare : ''" | ||
+ | </ | ||
+ | |||
+ | ** Loi de Zipf ** | ||
+ | * soit V l’ensemble du vocabulaire. On note pour tout t appartenant à V : f(t) est la fréquence du terme t. | ||
+ | * r(t) : rang du terme t (les termes sont ordonnés selon les fréquences décroissantes). | ||
+ | |||
+ | Loi de Zipf : la fréquence d’un terme est inversement proportionnelle à son rang. | ||
+ | <note important> | ||
+ | |||
+ | f(t)≃C/r(t) | ||
+ | avec C une constante | ||
+ | </ | ||
+ | |||
+ | Il s'agit d'une distribution de type “loi de Puissance”. | ||
+ | |||
+ | remarque : pour une base de textes donnée, on peut estimer la constante C en traçant les fréquence mesurées empiriquement selon une échelle logarithmique (log(r), log(f)) | ||
+ | |||
+ | <note important> | ||
+ | log(f(t))≃log(C)−log(r(t)) | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | {{https:// | ||
+ | Fréquence des mots en fonction du rang dans la version originale d' | ||
+ | </ | ||
+ | |||
+ | Interprétation : | ||
+ | * très peu de mot apparaissent très souvent | ||
+ | * beaucoup de mots apparaissent très peu souvent | ||
+ | |||
+ | Du point de vue de la théorie de l’information : | ||
+ | * Les termes courants apportent peu d’informations | ||
+ | * Les termes peu courants apportent beaucoup d’informations. | ||
+ | |||
+ | < | ||
+ | **Exercice 2** : On considère une base B contenant n=100.000 documents et un vocabulaire V contenant K=10000 termes. Soient t1 le terme le plus fréquent et tK le terme le moins fréquent. Donnez une estimation, pour C=0.1, du nombre de documents contenant le terme t1 et le terme tK. | ||
+ | </ | ||
+ | |||
+ | === TF-IDF == | ||
+ | |||
+ | Il est possible à partir de l’étude de fréquence de définir un seuil pour sélectionner les termes les plus “informatifs”. | ||
+ | |||
+ | <note important> | ||
+ | **Rappels** (théorie de l' | ||
+ | On mesure l’information apportée par le terme t comme : | ||
+ | I(t)=−log2(p(t)) | ||
+ | où p(t) est la probabilité d’apparition du mot t dans la séquence. | ||
+ | Si le symbole t est “rare” (p(t) est faible), l’information qu’il apporte est élevée. Si le symbole t est fréquent, l’information qu’il apporte est faible. | ||
+ | |||
+ | Voir également : [[public: | ||
+ | </ | ||
+ | |||
+ | Dans le cadre des bases de documents, on appelle **fréquence documentaire** g(t) d’un terme t la fréquence d’apparition du terme **dans les différents documents de la base** B. | ||
+ | |||
+ | <note important> | ||
+ | g(t)=p(t∈d)=|d:t∈d|/|B| | ||
+ | </ | ||
+ | |||
+ | Où |{d:t dans d}| est le nombre de documents contenant t et |B| est la taille de la base. | ||
+ | |||
+ | Exemples : | ||
+ | * g(t)=1 : le terme est présent dans tous les documents | ||
+ | * g(t)=0,5 : le terme est présent dans 1 document sur 2 | ||
+ | * g(t)=1/n : le terme est présent dans 1 seul document | ||
+ | |||
+ | On peut sur le même principe mesurer l’**information documentaire** apportée par le terme t comme : | ||
+ | <note important> | ||
+ | I(t)=−log2(p(t∈d))=−log2(g(t)) | ||
+ | </ | ||
+ | ici, I(t) représente la capacité du terme t à “séparer” les documents de la base. | ||
+ | |||
+ | Ainsi, les termes apportant I bits d’information permettent de réaliser I partitions de la base (pour extraire des sous-ensembles de taille |B|/2I ) | ||
+ | |||
+ | On remarque que | ||
+ | * si le terme est présent dans tous les documents, son information documentaire est nulle. | ||
+ | * si le terme est présent dans un seul document, son information documentaire est maximale. | ||
+ | |||
+ | En pratique, l' | ||
+ | |||
+ | En recherche d’information, | ||
+ | |||
+ | Soit d un document appartenant à B. | ||
+ | Pour tout t appartenant à d : | ||
+ | TF-IDF(t,d)=−f(t,d)log(g(t)) | ||
+ | * où f(t,d) est la fréquence du terme t dans d | ||
+ | * et g(t) est la fréquence documentaire de t dans B. | ||
+ | |||
+ | La transformation TD-IDF traduit alors un texte d en un vecteur x appartenant à ∈RK selon le principe vu précédemment: | ||
+ | * A tout terme t∈V on associe son index k∈1..K : | ||
+ | * xk=TF-IDF(t,d)⇔t∈d | ||
+ | * xk=0⇔t∉d | ||
+ | |||
+ | Le codage TF-IDF est utilisé principalement : | ||
+ | * Dans les moteurs de recherche | ||
+ | * Dans la classification automatique de documents | ||
+ | |||
+ | < | ||
+ | **Exercice 3** : soit B une base de documents contenant n textes, chaque texte est encodé comme une liste de mots (sans majuscules ni ponctuation). Ecrire le code Python permettant de calculer la fréquence documentaire des différents termes de la base. | ||
+ | </ | ||
+ | |||