Chapitre 6 : Éléments similaires (shingling, min-hashing, LSH)
Trouver les paires d’éléments similaires (documents quasi-dupliqués, articles, …) dans une énorme collection. Comparer toutes les paires est en \(O(n^2)\) — impossible à grande échelle. La chaîne shingling → min-hashing → LSH résout ce problème.
Objectifs
À la fin de ce chapitre, vous devez pouvoir :
Représenter un document par ses k-shingles et la similarité de Jaccard
Compresser les ensembles par des signatures min-hash
Trouver les paires candidates par LSH sans comparer toutes les paires
1. Shingling
Un k-shingle est une sous-chaîne (ou suite de k mots) consécutive du document. Un document devient l’ensemble de ses k-shingles. Deux documents proches partagent beaucoup de shingles.
On mesure la similarité de deux ensembles par la similarité de Jaccard :
(Choix de k : assez grand pour que la probabilité qu’un shingle apparaisse par hasard soit faible — typiquement k = 5 à 10 pour des caractères.) On hache souvent les shingles en entiers pour gagner de la place.
2. Min-hashing
Les ensembles de shingles sont énormes. On les résume par de courtes signatures qui préservent la similarité de Jaccard.
Principe. On représente la collection par une matrice caractéristique (lignes = shingles, colonnes = documents, 1 si présent). Une fonction de min-hash \(h\) correspond à une permutation des lignes ; la valeur min-hash d’une colonne = le numéro de la première ligne (dans cette permutation) où la colonne vaut 1.
Propriété fondamentale : pour deux colonnes,
En utilisant n fonctions de min-hash, la signature d’un document est le vecteur de ses n valeurs min-hash ; la fraction de positions égales entre deux signatures estime leur Jaccard. En pratique, on simule les permutations par n fonctions de hachage.
3. Locality-Sensitive Hashing (LSH)
But : ne produire qu’un petit nombre de paires candidates (celles probablement similaires), sans examiner les \(O(n^2)\) paires.
Technique des bandes (banding). On découpe la signature (longueur n) en b bandes de r lignes (\(n = b\cdot r\)). Pour chaque bande, on hache la tranche de signature de chaque document dans des buckets. Deux documents deviennent candidats s’ils tombent dans le même bucket pour au moins une bande.
Analyse. Si deux documents ont une similarité s, la probabilité qu’ils soient candidats est :
Cette courbe a une forme en S : un seuil approximatif \(t \approx (1/b)^{1/r}\). On choisit b et r pour que le seuil sépare bien les paires similaires (rendues candidates) des dissemblables (écartées).
Étape finale : ne vérifier (calcul exact de la similarité) que les paires candidates — bien moins nombreuses.
4. Mesures de distance & autres (brève description)
Notion |
Idée |
|---|---|
Distances |
Jaccard, Euclidienne, Cosinus, Hamming, édition — chacune adaptée à un type de données. |
LSH pour le cosinus |
Hyperplans aléatoires (random projections / sketches) : \(\Pr[\text{même signe}] = 1 - \theta/\pi\). |
LSH pour l’euclidien |
Projection sur des droites aléatoires découpées en segments. |
Applications |
Détection de plagiat, articles d’actualité similaires, résolution d’entités (entity resolution), empreintes. |
Exercices
Exercice 1 — Jaccard
A = {1,2,3,4}, B = {2,3,5}. Calculez la similarité de Jaccard.
▶ Voir la correction
\(A\cap B = \{2,3\}\) (taille 2) ; \(A\cup B = \{1,2,3,4,5\}\) (taille 5). Donc \(\text{sim} = 2/5 = 0{,}4\).
Exercice 2 — Banding LSH
Signatures de longueur n = 20, découpées en b = 5 bandes de r = 4.
Pour une paire de similarité s = 0,8, probabilité d’être candidate ?
▶ Voir la correction
\(1-(1-s^{r})^{b} = 1-(1-0{,}8^{4})^{5} = 1-(1-0{,}4096)^{5} = 1-0{,}5904^{5} \approx 1-0{,}0717 \approx \mathbf{0{,}93}\). Une paire très similaire (0,8) a donc ~93 % de chances d’être candidate ; une paire dissemblable (petit s) a une probabilité très faible — c’est l’effet de seuil en S.