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 | |||
public:omi-5a-o-rech:1._recherche_et_indexation [2017/12/15 15:09] – [1. Données texte] edauce | public:omi-5a-o-rech:1._recherche_et_indexation [2019/01/11 10:39] (Version actuelle) – [6. Représentation vectorielle] edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ===== Indexation des documents texte===== | ||
+ | ==== 1. Données texte ==== | ||
+ | |||
+ | * Fouille de textes : "Text mining" | ||
+ | * Bases de documents : données de type texte (" | ||
+ | * Algorithmes de recherche sur des documents textes. | ||
+ | |||
+ | === 1.1 Bases documentaires === | ||
+ | |||
+ | * $B$ : base documentaire: | ||
+ | * Librairie, bibliothèque, | ||
+ | * Dossier contenant des documents (fichiers textes, documents formatés, pages web, forums...) | ||
+ | * Serveur de fichiers (serveur web, fournisseur de contenus, ...) | ||
+ | * Moteur de recherche | ||
+ | * $n$ : nombre de documents : $n = |B|$. | ||
+ | * $d \in B$ : un document appartenant à la base $B$. | ||
+ | * $t \in d$ : un terme présent dans le document $d$. | ||
+ | |||
+ | Recherche documentaire : | ||
+ | {{: | ||
+ | |||
+ | |||
+ | === 1.2 Ordres de grandeur === | ||
+ | |||
+ | * Centre de documentation : $n \in [10^2 - 10^4]$ | ||
+ | * Fournisseur de contenus (Amazon) : $ n \in [10^4 - 10^8] $ | ||
+ | * Moteur de recherche (Google) : $ n \in [10^8 - 10^{16}] $ | ||
+ | |||
+ | --> "Big data" | ||
+ | |||
+ | === 1.3 Enjeux === | ||
+ | * Temps de réponse (< 1s ?) | ||
+ | * Stockage des données | ||
+ | * Protection des données | ||
+ | * Vie privée | ||
+ | |||
+ | === 1.4 Méthodes === | ||
+ | * Théorie de l' | ||
+ | * Apprentissage automatique (" | ||
+ | * Reconnaissance de formes | ||
+ | * Statistiques | ||
+ | |||
+ | === 1.5 Exemples de moteurs de recherche === | ||
+ | |||
+ | * {{https:// | ||
+ | * {{https:// | ||
+ | ==== 2. Algorithmes sur les textes ==== | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | ==== 3. Principes généraux : double indexation ==== | ||
+ | |||
+ | === Fichier inverse - BitMap === | ||
+ | |||
+ | On appelle fichier inverse la structure de données qui, à tout terme t, associe l’ensemble D(t) des documents contenant le terme t. | ||
+ | | ||
+ | La structure de données implémentant | ||
+ | * A chaque document $d$ est attribué un entier $i \in 1..n$ | ||
+ | * A chaque terme $t$ est attribué un entier $j \in 1..m$ | ||
+ | * $T[i,j] = 1 \Leftrightarrow j \in i$ | ||
+ | * $T[i,j] = 0 \Leftrightarrow j \notin i$ | ||
+ | * Chaque colonne T[:,j] désigne l' | ||
+ | * Chaque ligne T[i,:] désigne l' | ||
+ | |||
+ | Soit $q$ une requête constituée de plusieurs termes $j_1, j_2, ... j_k$. | ||
+ | |||
+ | Cette requête s' | ||
+ | |||
+ | L' | ||
+ | $$ T[:,j_1] \text{ and } T[:,j_2] \text{ and }...\text{ and } T[:,j_k] $$ | ||
+ | |||
+ | On note $\{i_1, i_2, ...\}$ la liste des documents sélectionnés par la requête $q$. | ||
+ | |||
+ | === Similarité === | ||
+ | |||
+ | Pour chaque document $i$ sélectionné par fichier inverse, on calcule un score de **similarité** : | ||
+ | |||
+ | Les documents sont ensuite classés par ordre // | ||
+ | $$ (i_1', i_2', ...)$$ | ||
+ | avec $\text{sim}(i_1', | ||
+ | |||
+ | ==== 4. similarité : approche binaire ==== | ||
+ | |||
+ | * Un document $d$ est une liste ordonnée de termes : $d = (d[1], d[2], ..., )$ | ||
+ | * On cherche une représentation " | ||
+ | * L' | ||
+ | |||
+ | ==== Représentation ensembliste des documents ==== | ||
+ | |||
+ | un document $d$ est représenté par l' | ||
+ | |||
+ | == Similarité de Jaccard == | ||
+ | Soient deux ensembles A et B. | ||
+ | |||
+ | L' | ||
+ | $$ J(A,B) = \frac{|A \cap B|}{|A \cup B|} $$ | ||
+ | ==== Représentation vectorielle | ||
+ | |||
+ | * Un document $d$ est représenté par sous la forme d'un vecteur **binaire** $\boldsymbol{x}$ de dimension $m$ | ||
+ | * $m$ est la taille du vocabulaire | ||
+ | * Chaque terme $t \in V$ est indexé par un entier $i \in 1..m$ | ||
+ | * $x_i = 1 \Leftrightarrow i \in d$ | ||
+ | * $x_i = 0 \Leftrightarrow i \notin d$ | ||
+ | |||
+ | == Similarité vectorielle == | ||
+ | |||
+ | * Similarité basée sur la distance : | ||
+ | * Distance vectorielle : | ||
+ | * distance de Hamming : | ||
+ | $$ \text{dist}(\boldsymbol{x}, | ||
+ | * Similarité : | ||
+ | $$ \text{sim}(\boldsymbol{x}, | ||
+ | * Similarité du cosinus : | ||
+ | $$ \text{sim}(\boldsymbol{x}, | ||
+ | ==== 5. Statistiques sur les textes ==== | ||
+ | |||
+ | On dispose d’une base $B$ de $n$ documents textes. | ||
+ | |||
+ | On note $B = \{d_1, | ||
+ | |||
+ | Les documents sont écrits dans un langage $L$ obéissant à un vocabulaire $V$. | ||
+ | |||
+ | On note $V = \{t_1, t_2, ... \}$ où chaque $t_i$ est un terme du vocabulaire $V$. | ||
+ | |||
+ | On note $A$ l' | ||
+ | |||
+ | On note $\alpha \in A$ un caractère de l' | ||
+ | |||
+ | Soit $d$ un document de $B$. Il peut être décrit comme : | ||
+ | * une suite de symboles : $d = (\alpha_1, \alpha_2, ...)$ avec $\alpha_i \in A$. | ||
+ | * ou une suite de mots : $d = (t_1, t_2, ...)$ avec $t_i \in V$. | ||
+ | |||
+ | [[public: | ||
+ | |||
+ | |||
+ | |||
+ | [[public: | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 6. Représentation | ||
+ | |||
+ | * Un document $d$ est représenté par sous la forme d'un vecteur **réel** $\boldsymbol{x}$ de dimension $m$ | ||
+ | * $m$ est la taille du vocabulaire | ||
+ | * Chaque terme $t \in V$ est indexé par un entier $j \in 1..m$ | ||
+ | * $x_j = h(j,d) \Leftrightarrow j \in d$ | ||
+ | * h(j,d) correspond : | ||
+ | * à la fréquence de $j$ dans $d$ : | ||
+ | $$f_d(j)$$ | ||
+ | * au score TF-IFD de $j$ dans $d$ : | ||
+ | $$ - f_d(j) \log g_B(j)$$ | ||
+ | * $x_j = 0 \Leftrightarrow j \notin d$$ | ||
+ | == Comparaison vectorielle == | ||
+ | |||
+ | * Similarité euclidienne | ||
+ | * distance euclidienne : | ||
+ | $$ \text{dist}(\boldsymbol{x}, | ||
+ | * similarité euclidienne : | ||
+ | $$ \text{sim}(\boldsymbol{x}, | ||
+ | * Similarité du cosinus : | ||
+ | $$ \text{sim}(\boldsymbol{x}, | ||
+ | |||
+ | |||
+ | ==== 7. Recherche Web==== | ||
+ | |||
+ | ===PageRank=== | ||
+ | |||
+ | < | ||
+ | Le World Wide Web (www) est un réseau | ||
+ | * formé de documents (les pages html) hébergées sur des serveurs, | ||
+ | * les serveurs sont localisés à l'aide de leur adresse (url : universal ressource locator) | ||
+ | * les documents sont liés entre eux par des liens hypertextes. | ||
+ | </ | ||
+ | |||
+ | Les algorithmes d' | ||
+ | |||
+ | <note important> | ||
+ | $$\text{score}(i, | ||
+ | où $\text{PR}(i)$ est la popularité de la page $i$. | ||
+ | </ | ||
+ | |||
+ | <note tip> | ||
+ | Le score de popularité le plus célèbre est le **" | ||
+ | </ | ||
+ | |||
+ | Le calcul du Page Rank repose sur un modèle de parcours aléatoire de graphes. On considère un internaute se déplaçant sur le Web de manière aléatoire. A chaque page visitée, il suit un lien au hasard et répète cette opération un nombre indéfini de fois. Le résultat est un chemin aléatoire sur le graphe. Au cours de ce parcours, certains sites seront visités plus souvent que d' | ||
+ | |||
+ | < | ||
+ | {{public: | ||
+ | </ | ||
+ | |||
+ | Concrètement, | ||
+ | * A chaque page visitée | ||
+ | * dans q% des cas, suivre un lien au hasard | ||
+ | * dans (1-q)% des cas, choisir une page quelconque du réseau sans suivre de lien particulier. | ||
+ | |||
+ | q est appelé le terme d'// | ||
+ | |||
+ | Le graphe est constitué de $n$ nœuds où chaque nœud est une page web. On considère que chaque page est indexée par un indice $i \in 1..n$. | ||
+ | |||
+ | < | ||
+ | Dans ce cas, le graphe peut être représenté par une matrice $G$ de taille | ||
+ | $G$ a une structure de //matrice creuse// (beaucoup de 0, peu de 1) | ||
+ | |||
+ | $$G = \left( | ||
+ | \begin{array}{ccccccccccc} | ||
+ | 1& & & & & & & & & & \\ | ||
+ | & | ||
+ | & | ||
+ | 1& | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & & & &1& & & & &1& \\ | ||
+ | & & & &1& & & & & &1\\ | ||
+ | \end{array} | ||
+ | \right) | ||
+ | $$ | ||
+ | (La valeur 0 n'est pas représentée) | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | On peut de même définir une matrice de transition $P$ contenant les probabilités de transition d'une page à l' | ||
+ | $$P = \left( | ||
+ | \begin{array}{ccccccccccc} | ||
+ | 1& & & & & & & & & & \\ | ||
+ | & | ||
+ | & | ||
+ | \frac{1}{3}& | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & | ||
+ | & & & & | ||
+ | & & & & | ||
+ | \end{array} | ||
+ | \right) | ||
+ | $$ | ||
+ | </ | ||
+ | |||
+ | Le calcul du page Rank est fondé sur une estimation de la proportion de temps passée sur chaque site en suivant ce principe. | ||
+ | |||
+ | Il correspond à la mesure stationnaire de la chaîne de Markov associée, définie comme le vecteur $\boldsymbol{x}$ positif et de somme 1 vérifiant~: | ||
+ | $$\boldsymbol{x} = \boldsymbol{x}Q^T$$ | ||
+ | avec~ | ||
+ | $$Q = qP + \frac{(1-q)}{n} \boldsymbol{1}$$ | ||
+ | avec $\mathbf{1}$ matrice de taille $n \times n$ ne contenant que des 1. | ||
+ | |||
+ | En pratique : | ||
+ | * Le graphe étant de grande taille, il n'est pas possible de résoudre directement l' | ||
+ | * Le graphe est régulièrement mis à jour pour prendre en compte les évolution du Web et de la popularité des différentes pages. | ||
+ | |||
+ | La mise à jour du graphe //et du PageRank// se fait de manière itérative à l'aide d'un " | ||
+ | |||
+ | < | ||
+ | **Algo** : | ||
+ | * Initialiser le vecteur $\boldsymbol{x}$ à la valeur $(1/n,1/n, ..., 1/n)$ | ||
+ | * Pour chaque page visitée $i$ : | ||
+ | - Mettre à jour les valeurs des liens sortants : $$ \forall j : i \rightarrow j, P_{ij} \leftarrow \frac{1}{\sum_{j : i \rightarrow j}1} $$ | ||
+ | - choisir une page $j$ au hasard parmi les liens sortants | ||
+ | - Mettre à jour le score $x_j$ de la page $j$ en fonction des liens entrants, i.e. $$ x_j \leftarrow q \sum_{i: | ||
+ | </ | ||
+ | | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ==== 8. Classification ==== | ||
+ | |||
+ | **TODO** |