Modèles de recherche
Booléen et vectoriel
1
Modèles de recherche
• Un modèle de recherche précise les
détails de:
– représentation de document
– représentation de la requête
– fonction de recherche
• Détermine la notion de pertinence.
– La notion de pertinence peut être binaire
ou continu (c.a.d recherche classé).
2
Classes de modèles de recherche
• Le modèles booléens (théorétique)
• Les modèles vectoriel (statistique /
algébriques)
– Latent Semantic Indexing LSA
• Les modèles probabilistes
3
Autres Dimensions gérées par les modèles
• Vue logique des documents
– Index de Termes (mots-clés)
– Texte intégral
– Texte intégral + structure (par exemple
hypertexte)
• Tâche utilisateur
– Recherche
– Navigation
4
Étapes communes Prétraitement
• Supprimer les caractères et le balisage indésirables
(Par exemple des balises HTML, la ponctuation,
chiffres, etc.).
• Séparer les tokens (mots clés) sur la base des espaces.
• Radicaliser les tokens pour avoir des « Stem »
– Ex: computational comput
• Supprimer les mots vides communs (par exemple, la,
elle, etc.).
• Détecter des phrases courantes (éventuellement à
l'aide d'un dictionnaire spécifique de domaine).
• Construire l'index inversé (mot-clé liste des
documents le contenant).
5
Modèle booléen
• Un document est représenté comme un
ensemble des mots-clés.
• Les requêtes sont des expressions booléennes de
mots-clés, reliés par AND, OR et NOT, y compris
l'utilisation de crochets pour indiquer la portée.
– [[Rio AND Brésil] OR [Hilo AND Hawaii]] AND hôtel
AND NOT Hilton]
• Sortie:
• Le document est pertinent ou non.
• Aucun résultat partiel ou classement.
6
Modèle de recherche Booléen
• C’est un modèle de recherche populaire
parce que:
– Facile à comprendre pour des requêtes
simples.
– formalisme simple.
• Les modèles booléens peuvent être étendus pour
inclure le classement.
• Il existe des implémentations efficaces pour les
requêtes normales.
7
Modèles booléennes Problèmes
• Très rigide: ET signifie tous; OU signifie quelconque.
• Difficile à exprimer le besoin complexe des utilisateurs.
• Difficile de contrôler le nombre de documents récupérés.
– Tout documents correspondants (match) seront retournés.
• Difficile à classer.
– Tout documents correspondants (match) satisfont logiquement la
requête.
• Difficile à réaliser un retour de pertinence (relevance
feedback).
– Si un document est identifié par l'utilisateur comme pertinent ou
non pertinent, comment modifier la requête?
8
Les Modèles Statistiques
• Un document est généralement représenté par un sac
à mots (mots non ordonnées avec des fréquences).
• Sac = ensemble qui permet plusieurs occurrences
d'un même élément.
• Pour la requête, l'utilisateur spécifie un ensemble de
termes souhaités avec des poids en option:
– Termes Pondérés :
Q = <0,5 base de données; texte 0,8; informations 0,2>
– Termes non pondérés :
Q = <Base de données; texte; information>
– Pas de conditions booléennes spécifiées dans la requête.
9
Recherche Statistique
• La recherché est sur la base de la similarité entre la
requête et les documents.
• Les documents de sortie sont classés en fonction de la
similarité avec la requête.
• La similarité est basée sur la fréquence des mots-clés
dans la requête et le document.
• Le retour de pertinence (relevance feedback) peut
être pris en charge:
– Mots-clés des documents pertinents « ajoutés » à la requête.
– Mots-clés des documents non pertinents « soustraites » de la requête.
10
Problèmes du modèleVectoriel
• Comment déterminer les mots importants dans un
document?
– sens des mots?
– Mot n-grams (et expressions, idiomes, ...) termes
• Comment déterminer le degré d'importance d'un
terme dans un document et dans la collection?
• Comment déterminer le degré de similarité entre
un document et la requête?
• Dans le cas du Web, quelle est la collection et
quels sont les effets des liens, des informations de
formatage, etc.?
11
Le modèle Vectoriel
• Supposons t termes distincts issues après
prétraitement; appeler mots clés d'indexation ou
le vocabulaire.
• Ces termes « orthogonales » forment un espace
vectoriel.
dimensionnalité = t = | Vocabulaire |
• Un poids d'une valeur réel wij est associer à
chaque terme i dans un document ou requête j..
• Les deux documents et requêtes sont exprimées en
vecteurs: t-dimensionnelle
dj = (w1j, w2j, ..., wtj) 12
Representation Graphique
Exemple:
D1 = 2T1 + 3T2 + 5T3 T3
D2 = 3T1 + 7T2 + T3
5
Q = 0T1 + 0T2 + 2T3
D1 = 2T1+ 3T2 + 5T3
Q = 0T1 + 0T2 + 2T3
2 3
T1
D2 = 3T1 + 7T2 + T3
• D1 ou D2 plus similaire to Q?
• Comment mesurer la similarité:
7
T2 par Distance? Angle?
Projection?
13
Collection de documents
• Une collection de n documents peuvent être représentés dans le
modèle d'espace vectoriel par une matrice terme-document.
• Une entrée de la matrice correspond à la « Poids » d'un terme dans
le document; zéro signifie que le terme n'a pas de signification dans
le document ou il n'existe tout simplement pas dans le document.
T1 T2 …. Tt
D1 w11 w21 … wt1
D2 w12 w22 … wt2
: : : :
: : : :
Dn w1n w2n … wtn
14
Pondération: Fréquence de Terme
• La règle est que les termes les plus fréquents dans
un document sont plus importants.
Fij = Fréquence de terme i dans le document j
• Il est préférable de normaliser la fréquence des
termes (tf) en divisant par la fréquence du terme
le plus courant dans le document:
tfij = Fij / maxi{Fij}
15
Pondération: Fréquence inverse de document idf
• Les termes qui apparaissent dans différent
documents sont moins indicatif du thème général.
df i = document frequency of term i
= Nombre de documents contenant le terme i
idfi = inverse document frequency of term i,
= log2 (N / df i)
(N: Nombre total de documents)
• C’est une indication de la force de discrimination
de ce terme.
• Le Log est utilisé pour amortir l'effet par rapport
16
à tf qui est normaliser.
Pondération TF-IDF
• Une combinaison typique des indicateurs
d’importance des termes est la pondération TF-IDF:
wij = tfij * idfi = tfij * Log2 (N / dfi)
• Un terme se produisant fréquemment dans le
document, mais rarement dans le reste de la
collection est associer à un poids élevé.
• Il existe de nombreuses autres pondération pour le
modèle vectoriel.
• Expérimentalement, tf-idf donne toujours de bon
résultats.
17
Calcul TF-IDF - Exemple
• Compte tenu d'un document contenant des termes avec des
fréquences données:
• A (3), B (2), C (1)
• Supposons que la collection contient 10.000 documents et
les df de ces termes dans ces documents sont les suivants:
A (50), B (1300), C (250)
• Alors:
A: tf = 3/3; idf = log2(10000/50) = 7,6; tf-idf = 7,6
B: tf = 2/3; idf = log2 (10000/1300) = 2,9; tf-idf = 2,0
C: tf = 1/3; idf = log2 (10000/250) = 5,3; tf-idf = 1,8
18
Vecteur de requête
• Le vecteur de requête est généralement
considéré comme un document et aussi
pondéré tf-idf.
• Optionnellement, l'utilisateur peut fournir
des poids pour les termes de la requête qu’il
donne.
19
calcule de similarité
• Une mesure de similarité est une fonction qui
calcule le degré de similitude entre deux vecteurs.
• En utilisant une mesure de similarité entre la
requête et chaque document:
– Il est possible de classer les documents récupérés dans
l'ordre de pertinence.
– Il est possible d'appliquer un certain seuil afin que l'on
peut contrôler la taille de l'ensemble récupéré.
20
Mesure de similarité: Produit interne
• Similarité entre les vecteurs pour le document di et requête q
peut être calculé en tant que produit interne (produit scalaire):
t
sim(dj,q) = dj•q = w w
i 1
ij iq
où wij est le poids du terme i dans le document j et wiq est le poids du
terme i dans la requête
• Pour les vecteurs binaires, le produit interne est le nombre de
termes de requête correspondant dans le document (taille
d'intersection).
• Pour les vecteurs pondérés terme, il est la somme des produits
des poids des termes correspondants.
21
Propriétés du produit interne
• Le produit interne est sans limite.
• Favorise les longs documents avec un grand
nombre de termes uniques.
• Mesure le nombre Termes qui apparaissent dans
le document et la reqête mais pas le nombre des
mots qui n’apparaissent pas.
22
produit interne - Exemples
h
rc de s ure r t io
n
e t u n a
ech ase née itec nate te stio rm
Binary: r
e
b on rch di ex ge fo
d a o r t la in
D = 1, 1, 1, 0, 1, 1, 0
Taille du vecteur = taille du vocabulaire = 7
Q = 1, 0 , 1, 0, 0, 1, 1 0 exprime qu’un terme ne figurent pas dans
le document ou une requête
sim(D, Q) = 3
Weighted:
D1 = 2T1 + 3T2 + 5T3 D2 = 3T1 + 7T2 + 1T3
Q = 0T1 + 0T2 + 2T3
sim(D1 , Q) = 2*0 + 3*0 + 5*2 = 10
sim(D2 , Q) = 3*0 + 7*0 + 1*2 = 2
23
Mesure similarité: Cosinus
• similarité cosinus mesure le cosinus de t3
l'angle entre deux vecteurs.
• produit scalaire normalisé par les
longueurs vectorielles.
t
ré1
dj q ( wij wiq ) Q
CosSim (dj, q) =
i 1
t t
t1
dj q wij wiq
2 2
i 1 i 1
t2 ré2
D1 = 2T1 + 3T2 + 5T3 CosSim(D1 , Q) = 10 / (4+9+25)(0+0+4) = 0.81
D2 = 3T1 + 7T2 + 1T3 CosSim(D2 , Q) = 2 / (9+49+1)(0+0+4) = 0.13
Q = 0T1 + 0T2 + 2T3
d1 est 6 fois mieux que d2 en utilisant la similarité cosinus mais seulement 5 fois en
utilisant le produit interne.
24
Implémentation naïf
1. Convertir tous les documents dj de collection D à en
vecteurs pondérés tf-idf, de taille V(vocabulaire mot-clé)
2. Convertir la requête en un vecteur tf-idf de taille V.
3. Pour chaque dj dans D faire
calculer sj = CosSim (dj, q)
4. Trier les documents par poids décroissants.
5. Retournez les K document les mieux classésà
l'utilisateur.
complexité temps: O (| V |·| D |) mauvaise pour un grand V
& D!
| V | = 10 000; | D | = 100 000; | V |·| D | = 1000000000
25
Propriétés du modèle vctoriel
• Simple, approche mathématique.
• Pondération locale (tf) Et globals (idf)
d'occurrence des mots.
• Permet une correspondance partielle et les
résultats classés.
• Tend à travailler très bien dans la pratique en
dépit des faiblesses évidentes.
• Permet la mise en œuvre efficace sur de grandes
collections de documents.
26
Problèmes avec modèle vectoriel
• Sémantique (pas de considération de sens des mots).
• syntaxique (par de considération de la structure de
phrase, l'ordre des mots, l'information de proximité).
• Suppos l'indépendance des terme (par exemple ignores de
synonymie).
• Manque le contrôle d'un modèle booléen (par exemple,
exigeant un terme à apparaître dans un document).
– Étant donné une requête de deux termes "A B", le modèle
vectoriel peut préférer un document contenant "A"
fréquemment, mais pas "B", sur un document qui contient à la
fois A et B, mais les deux moins fréquemment.
27
