Semaine 6 / Les modèles vectoriels

Les modèles vectoriels

Petit rappel

Il est possible que vous sentiez le besoin de revoir le texte sur les vecteurs et matrices de la première semaine avant de lire le texte qui suit. Dans ce cas, n’hésitez pas à le revoir.

Les modèles vectoriels

Le modèle vectoriel le plus simpliste possible peut être décrit comme suit. Pour chaque document dans un ensemble, on compte le nombre d’occurrences de chaque mot (fréquence d’occurrence du terme, notée « $tf$ »). Ce décompte ou cette vérification des occurrences forme un vecteur pour chaque document et l’ensemble des vecteurs forme une matrice parfois appelée matrice d’occurrences. Au lieu de compter le nombre d’occurrences, on peut aussi simplement vérifier la présence du terme et attribuer la valeur 1 lorsque le terme est présent, et la valeur 0 quand le terme est absent. D’autres modèles sont possibles comme le modèle logarithmique : $1+\log(tf)$. On doit le modèle vectoriel à Gerard Salton [1].

Gerald Salton ( 1927-1995)

Prenons un exemple concret. Soit trois documents très courts ne contenant, respectivement, que :

 Jean est à l’usine. Pierre est aussi à l’usine. (document 1)
 Jean mange des pommes. (document 2)
 Pierre est à la ferme. (document 3)

En pratique, on voudra éviter de garder les mots qui sont présents dans tous les documents ou même dans plus de 10 % des documents. Si, dans notre exemple, on omet les termes les plus susceptibles de se trouver dans pratiquement tous les documents d’un ensemble (comme « à », « le », etc.), on peut représenter cet ensemble de documents avec la matrice suivante (présentée sous la forme d’un tableau) où l’on a répertorié la fréquence d’occurrence des termes [2] :

Terme Document 1 Document 2 Document 3
Jean 1 1 0
ferme 0 0 1
usine 2 0 0
pommes 0 1 0
Pierre 1 0 1

Dans un cas plus réaliste, nous aurions beaucoup de termes et, même après avoir utilisé la troncature des mots, la matrice sera très importante. Il y aura, en général davantage de termes que de documents.
Il en découle une redondance.
On peut vérifier, dans ce cas, qu’il suffit de
connaître le nombre d’occurrences de trois termes pour pouvoir différencier les trois documents : si on me donne un document X et que je sais combien il y a d’occurrences des mots Jean, ferme et usine, je peux alors déterminer de quel document il s’agit.

La requête par mots-clés d’un utilisateur, comme Jean ferme peut alors être traitée directement à partir de la matrice. Il suffit de constater qu’un ensemble de mots-clés peut être représenté comme un vecteur (le vecteur 1,1,0,0,0 dans ce cas [3]). Dans notre exemple, il semble que la meilleure réponse soit de présenter le document 1 à l’utilisateur, mais les documents 2 et 3 peuvent aussi être pertinents. Comment déterminer lequel des documents est le plus pertinent ?

Il y a plusieurs facteurs dont on doit tenir compte :
 Les documents plus volumineux contiendront plus de termes, mais ils ne seront pas nécessairement toujours plus pertinents. Il faut donc « pénaliser » les documents très volumineux et aider l’utilisateur à trouver des documents courts qui répondent bien à la requête.
 Toutes choses étant égales, plus un terme est fréquent dans un document, plus le document est pertinent par rapport à ce terme.
 On doit attribuer plus d’importance, dans la requête de l’utilisateur, aux termes plus rares. Si je fais une recherche avec lait Steinbeck, il est probable que je tienne davantage à trouver des documents qui contiennent beaucoup d’informations sur l’auteur Steinbeck et aussi sur le mot lait.

Prenons l’exemple précédent de requête avec Jean ferme. Le terme Jean est présent dans 2 documents sur 3 alors que le terme ferme est présent dans un seul document. Le facteur $idf$ qui sert à tenir compte de la rareté relative de certains termes est défini par la formule $idf=\log(\vert D \vert / df)$ où $\vert D \vert$ est le nombre de documents et $df$, le nombre de documents où un terme donné apparaît. Notez qu’en cas de doute, en informatique, le logarithme en base 2 est utilisé : rappelez-vous de la formule $\log_2(x)=\log_b(x)/\log_b(2)$. Dans notre exemple, le facteur $idf$ du mot ferme est $\log(3/1)\approx 1.6$, alors que le facteur $idf$ du mot Jean est $\log(3/2)\approx 0.6$. Partout, on multipliera donc la fréquence du terme ($tf$) par le facteur ($idf$).

Voici une liste des facteurs $idf$ de chacun de nos termes :

Terme idf
Jean 0.6
ferme 1.6
usine 1.6
pommes 1.6
Pierre 0.6

On voit que les termes plus rares ont un facteur idf plus important. Reprenons notre matrice d’occurrence en multipliant les fréquences (tf) par le facteur idf correspondant :

Terme Document 1 Document 2 Document 3
Jean 0.6 0.6 0
ferme 0 0 1.6
usine 3.2 0 0
pommes 0 1.6 0
Pierre 0.6 0 0.6

Maintenant, la requête par mots-clés de l’utilisateur doit aussi être multipliée par le facteur idf et le vecteur 1,1,0,0,0 devient donc 0.6,1.6,0,0,0. On peut ensuite calculer le cosinus [4] entre ce vecteur et les différentes colonnes de la matrice :

$\cos(\{0.6,1.6,0,0,0\}, \{0.6,0,3.2,0,0.6\})\approx 0.06$

$\cos(\{0.6,1.6,0,0,0\}, \{0.6,0,0,1.6,0\})\approx 0.12$

$\cos(\{0.6,1.6,0,0,0\}, \{0,1.6,0,0,0.6\})\approx 0.88$

Puisque le cosinus de deux vecteurs ne contenant que des valeurs positives est entre 0 et 1 et que plus la valeur s’approche de 1, plus les vecteurs sont similaires, on peut convertir les valeurs obtenues en pourcentages (respectivement 6 %, 12 % et 88 %). On constate donc que l’ordre de pertinence des documents est 3,2 et 1. Comme nous avons utilisé le cosinus comme mesure de similarité, nous pénalisons automatiquement les documents très longs à cause de la division par la norme du vecteur lors du calcul du cosinus.

Le script suivant calcule l’angle entre deux vecteurs :

V1:
V2:

[1Gerard Salton, A. Wong, and C.S. Yang, A Vector Space Model for Automatic Indexing, Commun. ACM, vol. 18 (11), 1975, p. 613-620.

[2Appelée aussi fréquence du terme ou tf pour term frequency.

[3Si la requête est « Jean usine Pierre », le vecteur correspondant à la requête est alors 1,0,1,0,1. Et ainsi de suite.

[4Rappelons que le cosinus entre deux vecteurs est donné par $\cos(v,w)=v\cdot w / \sqrt{v\cdot v \times w\cdot w}$.