Modèle vectoriel et cosinus de Salton

placeholder

Modèle vectoriel et cosinus de Salton

Cher lecteur, tu t'intéresses aux moteurs de recherche, donc tu sais que la plupart des moteurs (en tout cas au moins celui qui est ton préféré) effectuent deux tâches distinctes : l'analyse de la pertinence et le classement des pages entre elles. Pour la deuxième tâche l'algorithme le plus connu est probablement le PageRank de Google, dont je parlerais un autre jour.

Bref, revenons à l'analyse de la pertinence d'une page (=un document) par rapport à un requête. En 1968, Gerard Salton (1927-1995, professeur à l'Université de Cornell, pionnier de l'Information Retrieval) présente pour la première fois le modèle vectoriel. Son hypothèse est que les fréquences d'occurrences des termes d'un texte donnent une bonne représentation du contenu du texte.

Dans ce billet je vais vous faire une présentation « avec les mains » du concept de modèle vectoriel (donc ce ne sera pas 100% correct, ni même up-to-date, mais vous aurez au moins une vague intuition de la chose). Notamment : on utilise rarement la fréquence mais plutôt une métrique comme les sempiternels tf et idf, qui permettent de prendre en compte les éléments plus rares dans un corpus.

Modèle vectoriel

On va prendre un texte et le transformer en un vecteur dans un espace bien choisi. L'espace en question sera un espace dont chaque dimension correspondra à un mot « significatif » du dictionnaire de tous les mots utilisables, notons d la taille de ce dictionnaire.
Par ailleurs, on va s'intéresser à la fréquence de chaque mot significatif dans notre texte, chaque mot se verra donc associer une valeur comprise entre 0 et 1. Au final notre espace est donc [0..1]d.
Il faut donc maintenant définir ce que l'on appelle un mot (ou terme) significatif. Lorsque l'on s'intéresse à un texte, on va le lemmatiser, c'est à dire repérer les lexies : les unités lexicographiques du texte. Il ne s'agit pas stricto sensu des mots car plusieurs mots peuvent constituer une seule lexie. On va ensuite enlever toutes les lexies inutiles : mots de liaisons, conjonctions, pronoms, déterminants. On va parfois également « aplanir » le texte : passer les verbes à l'infinitif (si on a choisi de garder les verbes), choisir la version pluriel ou singulier de chaque mot etc. Au final on va avoir un ensemble de mots, éventuellement en plusieurs exemplaires pour certains mots, qui seront les fameux mots significatifs. La deuxième tâche va être alors de calculer la fréquence de chaque mot, ce qui donnera la représentation vectorielle du texte.

Exemple

Prenons les textes suivants :

Texte 1 : la loutre est dans la rivière
Texte 2 : la loutre est avec les loutres dans la rivière

On va lemmatiser tout ça (sans prendre en compte les verbes) :

Texte 1 : loutre, rivière
Texte 2 : loutre, loutre, rivière

On va ensuite représenter chacun de ces textes par un vecteur dans l'espace des fréquences des mots rivière, loutre (dans cet ordre).

Texte 1 : (1/2, 1/2 )
Texte 2 : (1/3, 2/3)

Ce qui donne graphiquement :

image1salton

Analyse de la pertinence

On remarquera qu'une requête est aussi un texte, même si la plupart du temps il est plus court qu'un texte classique. Pour voir quelle est la page (= le texte) le plus pertinent pour une requête, on va regarder (graphiquement en quelque sorte) quel est le vecteur (d'un texte) qui est le plus proche du vecteur de la requête. Cette proximité se mesure à l'aide d'une mesure de similarité. Il y en a de nombreuses mais la plus connu, au moins dans le folklore SEO, est le cosinus de Salton (tiens tiens, comme on se retrouve).

On va donc choisir le texte qui correspond au vecteur qui a le plus petit cosinus avec le vecteur de la requête. Autrement dit, plus l'angle est fermé, plus je suis proche.
Si l'on revient sur l'exemple, en prenant la requête « je suis dans la rivière avec les loutres de la rivière » j'obtiens le vecteur (2/3, 1/3). Sur la graphique j'obtiens :

image2salton

Et donc le texte le plus proche est le texte 1.
Et voilà, vous connaissez au moins l'idée derrière le modèle vectoriel et le fameux cosinus de Salton.

No Comments

Comments are closed.