Travaux pratiques - Détection de quasi-copies avec MinHash LSH¶

Références externes utiles :

Documentation datasketch

datasketch sur GitHub

Jeu de données 20 Newsgroups (scikit-learn)

Objectif

L'objectif de cette séance de TP est de mettre en œuvre le hachage sensible à la similarité dans le cas de la détection de quasi-copies de documents textuels, en utilisant la bibliothèque datasketch. Nous illustrerons les notions de similarité de Jaccard, de signature MinHash et d'amplification vues en cours, et mesurerons le gain de complexité apporté par LSH par rapport à une comparaison exhaustive.

Les quatre parties de la séance sont :

Calcul de la similarité de Jaccard et construction de hash (ou signatures) MinHash.
Construction d'un index LSH et recherche de documents similaires à une requête.
Mesure de l'impact des paramètres \(n\) et \(t\) sur la précision et le rappel.
Comparaison du coût d'une auto-jointure exhaustive \(O(N^2)\) et d'une auto-jointure via LSH.

Mise en place

Installez la bibliothèque datasketch si elle n'est pas déjà disponible :

import sys
import subprocess
subprocess.check_call([sys.executable, "-m", "pip", "install", "datasketch", "--quiet"])

Vérifiez l'installation en important les classes dont nous aurons besoin :

from datasketch import MinHash, MinHashLSH
import numpy as np
import time

Nous travaillerons sur le jeu de données 20 Newsgroups, une collection de ~18 000 messages issus de 20 groupes de discussion Usenet. Ce jeu est disponible directement dans scikit-learn et ne nécessite aucun téléchargement manuel.

from sklearn.datasets import fetch_20newsgroups

# Chargement des données (toutes catégories, sans les en-têtes)
newsgroups = fetch_20newsgroups(subset='all',
                                remove=('headers', 'footers', 'quotes'))
textes = newsgroups.data
categories = newsgroups.target
noms_categories = newsgroups.target_names

print(f"{len(textes)} documents, {len(noms_categories)} catégories")
print("Exemple (300 premiers caractères) :")
print(textes[0][:300])

Pour garder des temps de calcul raisonnables nous travaillerons sur un sous-ensemble de 2 000 documents, tirés aléatoirement :

rng = np.random.default_rng(seed=42)
indices = rng.choice(len(textes), size=2000, replace=False)
corpus = [textes[i] for i in indices]
labels = [categories[i]  for i in indices]
N = len(corpus)
print(f"Corpus de travail : {N} documents")

Partie 1 : Similarité de Jaccard et signatures MinHash¶

Représentation par ensembles de k-grammes¶

Pour comparer des documents par la similarité de Jaccard, chaque document est représenté comme un ensemble de k-grammes (séquences de k caractères consécutifs). Deux documents partageant de nombreux k-grammes auront un indice de Jaccard élevé.

def kgrammes(texte, k=3):
    """Retourne l'ensemble des k-grammes d'un texte (en minuscules)."""
    texte = texte.lower()
    return set(texte[i:i+k] for i in range(len(texte) - k + 1))

# Calcul des ensembles de k-grammes pour tout le corpus
k = 3
ensembles = [kgrammes(doc, k) for doc in corpus]
print(f"Exemple : document 0 → {len(ensembles[0])} k-grammes distincts")

Question :

Affichez les 20 premiers k-grammes de ensembles[0]. Sont-ils des « mots » ? Que se passe-t-il si vous augmentez k à 5 ou 8 ? Quel impact cela a-t-il sur la taille des ensembles et sur la sensibilité de la similarité de Jaccard aux reformulations ?

Correction :

print(list(ensembles[0])[:20])

Les k-grammes de caractères ne correspondent pas à des mots : ils découpent le texte en sous-chaînes de longueur fixe, incluant les espaces et la ponctuation. Un k plus grand rend la mesure plus sélective (deux textes doivent partager de longues sous-chaînes pour être similaires) et réduit la taille des ensembles en augmentant leur spécificité. En pratique, k=3 à 5 est un bon compromis pour la détection de quasi-copies.

Calcul exact de la similarité de Jaccard¶

Écrivons une fonction de calcul exact de la similarité de Jaccard entre deux ensembles :

def jaccard(A, B):
    """Similarité de Jaccard entre deux ensembles."""
    inter = len(A & B)
    union = len(A | B)
    return inter / union if union > 0 else 0.0

# Test sur les deux premiers documents
print(f"Jaccard(doc0, doc1) = {jaccard(ensembles[0], ensembles[1]):.4f}")

Question :

Calculez la similarité de Jaccard entre doc0 et quelques autres documents du corpus. Trouvez deux documents dont la similarité est supérieure à 0,3. Combien de paires faudrait-il calculer pour trouver toutes les paires similaires dans le corpus de 2 000 documents ?

Correction :

Pour trouver toutes les paires similaires dans un corpus de \(N\) documents il faut calculer \(N(N-1)/2\) similarités, soit ici \(2000 \times 1999 / 2 = 1\,999\,000\) calculs. C'est l'auto-jointure exhaustive de complexité \(O(N^2)\) que LSH permettra d'éviter.

Signatures MinHash¶

Calculons maintenant la signature MinHash de chaque document. Chaque signature est un vecteur de num_perm valeurs de hachage ; nous verrons en partie 3 comment ce paramètre influe sur la qualité de l'approximation.

num_perm = 128    # nombre de fonctions de hachage élémentaires

def minhash(ensemble, num_perm=128):
    """Calcule la signature MinHash d'un ensemble."""
    m = MinHash(num_perm=num_perm)
    for element in ensemble:
        m.update(element.encode('utf-8'))
    return m

# Calcul des signatures pour tout le corpus
t0 = time.time()
signatures = [minhash(e, num_perm) for e in ensembles]
print(f"Signatures calculées en {time.time()-t0:.1f} s")

La similarité de Jaccard peut être estimée à partir des signatures (sans accéder aux ensembles) :

jaccard_exact  = jaccard(ensembles[0], ensembles[1])
jaccard_estime = signatures[0].jaccard(signatures[1])
print(f"Jaccard exact   : {jaccard_exact:.4f}")
print(f"Jaccard estimé  : {jaccard_estime:.4f}")
print(f"Erreur absolue  : {abs(jaccard_exact - jaccard_estime):.4f}")

L'estimation MinHash est un estimateur sans biais de la similarité de Jaccard. L'erreur standard de l'estimation est \(1/\sqrt{n}\) où \(n\) est le nombre de fonctions de hachage (num_perm). Avec num_perm=128, l'erreur standard est environ \(1/\sqrt{128} \approx 0{,}088\).

Partie 2 : Index LSH et recherche de documents similaires¶

Construction de l'index¶

Nous construisons maintenant un index MinHashLSH. Le paramètre threshold fixe le seuil de similarité de Jaccard à partir duquel deux documents sont considérés comme similaires (et donc susceptibles d'être retournés ensemble). num_perm doit correspondre à celui utilisé pour le calcul des signatures.

seuil = 0.3    # seuil de similarité de Jaccard

lsh = MinHashLSH(threshold=seuil, num_perm=num_perm)

# Insertion de tous les documents dans l'index
t0 = time.time()
for i, sig in enumerate(signatures):
    lsh.insert(f"doc_{i}", sig)
print(f"Index construit en {time.time()-t0:.2f} s")

Question :

Inspectez l'objet lsh : accédez à lsh.b et lsh.r. Que représentent ces deux valeurs ? Quel est leur produit, et quel lien a-t-il avec num_perm ?

Correction :

lsh.__dict__

lsh.b est le nombre de tables de hachage (\(t\)) et lsh.r est le nombre de fonctions élémentaires par table (\(n\)). Leur produit b × r doit être inférieur ou égal à num_perm. En cas d'inégalité, b × r permutations sont employées par LSH et les num_perm - b × r permutations restantes servent simplement à calculer un peu mieux la similarité de Jaccard entre la requête et les candidats retournés par LSH.

datasketch choisit automatiquement b et r pour que la courbe de probabilité de collision soit la plus proche possible d'une fonction à seuil autour de threshold.

Recherche par similarité¶

# Recherche des documents similaires au document 0
requete = signatures[0]
resultats = lsh.query(requete)
print(f"Documents similaires à doc_0 (seuil={seuil}) : {resultats}")

# Vérification : similarité exacte avec chaque résultat
for cle in resultats:
    idx = int(cle.split('_')[1])
    j = jaccard(ensembles[0], ensembles[idx])
    print(f"  {cle} : Jaccard exact = {j:.4f}")

Question :

Parmi les résultats retournés, y a-t-il des faux positifs (documents retournés dont la similarité exacte est inférieure au seuil) ? Est-ce difficile de trouver manuellement dans le corpus un document dont la similarité avec doc_0 est supérieure au seuil mais qui n'apparaît pas dans les résultats (faux négatif) ? Pourquoi ?

Correction :

Des faux positifs sont possibles : un document peut être dans le même bucket que la requête sans dépasser le seuil de similarité. Des faux négatifs existent également : un document similaire peut se trouver dans un bucket différent si la requête est proche d'une frontière entre pages. Trouver un faux négatif manuellement est difficile car il faudrait calculer la similarité exacte avec tous les documents du corpus, or c'est ce qu'on cherche à éviter.

Interprétation des catégories¶

Quelle catégorie représentent les documents trouvés ?

idx_resultats = [int(c.split('_')[1]) for c in resultats]
for idx in idx_resultats:
    print(f"  doc_{idx} → catégorie : {noms_categories[labels[idx]]}")

Question :

Les documents retournés appartiennent-ils majoritairement à la même catégorie que doc_0 ? Qu'est-ce que cela révèle sur la nature de la similarité mesurée par les k-grammes de caractères ?

Correction :

Les documents retournés appartiennent souvent à la même catégorie (ou à des catégories proches) que la requête, ce qui confirme que les k-grammes de caractères capturent une certaine proximité sémantique en plus de la proximité lexicale. Cependant, la similarité de Jaccard sur les k-grammes est surtout sensible à la répétition de sous-chaînes identiques, ce qui la rend efficace pour détecter des quasi-copies (absentes ici) ou des textes traitant du même sujet avec un vocabulaire similaire, mais moins adaptée à la recherche sémantique à proprement parler.

Partie 3 : Impact des paramètres \(n\) et \(t\)¶

Nous pouvons maintenant mesurer comment les paramètres b (nombre de tables, \(t\)) et r (fonctions par table, \(n\)) influent sur la qualité de la recherche. Rappelons que datasketch gère ces paramètres implicitement à travers threshold et num_perm ; nous les explorons en faisant varier ces deux derniers.

Constitution d'un ensemble de référence¶

Pour mesurer précision et rappel nous avons besoin d'un ensemble de paires vraiment similaires. Nous pouvons construire cet ensemble de référence sur un petit sous-corpus de 200 documents en calculant toutes les similarités exactes :

N_ref = 200
corpus_ref   = corpus[:N_ref]
ensembles_ref = ensembles[:N_ref]

# Calcul exhaustif : toutes les paires (i, j) avec i < j
t0 = time.time()
paires_vraies = set()
for i in range(N_ref):
    for j in range(i+1, N_ref):
        if jaccard(ensembles_ref[i], ensembles_ref[j]) >= seuil:
            paires_vraies.add((i, j))
t_exhaustif = time.time() - t0
print(f"Référence exhaustive : {len(paires_vraies)} paires similaires")
print(f"Temps (exhaustif, N={N_ref}) : {t_exhaustif:.2f} s")

Mesure de précision et rappel pour différentes configurations¶

def evaluer_lsh(ensembles, paires_vraies, num_perm, threshold):
    """Construit un index LSH, fait l'auto-jointure et calcule précision/rappel."""
    sigs = [minhash(e, num_perm) for e in ensembles]
    lsh  = MinHashLSH(threshold=threshold, num_perm=num_perm)
    for i, s in enumerate(sigs):
        lsh.insert(f"d{i}", s)

    paires_lsh = set()
    t0 = time.time()
    for i, s in enumerate(sigs):
        for cle in lsh.query(s):
            j = int(cle[1:])
            if j > i:
                paires_lsh.add((i, j))
    t_lsh = time.time() - t0

    vp = len(paires_vraies & paires_lsh)
    precision = vp / len(paires_lsh)  if paires_lsh  else 0.0
    rappel    = vp / len(paires_vraies) if paires_vraies else 0.0
    return precision, rappel, t_lsh, lsh.b, lsh.r

# Exploration de différentes valeurs de num_perm avec threshold fixé
print(f"{'num_perm':>8}  {'b (tables)':>10}  {'r (fonct.)':>10}  "
      f"{'Précision':>10}  {'Rappel':>8}  {'Temps (s)':>10}")
print("-" * 65)
for np_ in [32, 64, 128, 256]:
    p, r, t, b, rv = evaluer_lsh(ensembles_ref, paires_vraies, np_, seuil)
    print(f"{np_:>8}  {b:>10}  {rv:>10}  {p:>10.3f}  {r:>8.3f}  {t:>10.3f}")

Question :

Décrivez l'évolution de la précision et du rappel lorsque num_perm augmente. Est-ce conforme à ce que prédit la théorie sur l'amplification des fonctions LSH ? Y a-t-il un compromis à faire ?

Correction :

Augmenter num_perm améliore en général la précision et le rappel car l'estimation MinHash devient plus fidèle à la similarité de Jaccard exacte. Cependant, cela augmente aussi le temps de calcul (plus de fonctions de hachage à évaluer) et la mémoire occupée par l'index. En pratique, num_perm=128 offre ici un bon compromis.

Question :

Faites varier threshold entre 0,1 et 0,5 (avec num_perm=128 fixé). Que se passe-t-il sur b et r ? Comment évolue le nombre de paires retournées ? Expliquez le lien avec la notion d'effet de seuil vue en cours.

Correction :

Quand threshold augmente, datasketch choisit un r plus élevé (plus de fonctions par table) pour rendre les buckets plus sélectifs et réduire les faux positifs, au prix d'un rappel plus faible pour les paires proches du seuil. Le nombre de paires retournées diminue fortement. C'est l'illustration directe de l'effet de seuil : la courbe de probabilité de collision s'aplatit à gauche et à droite du seuil.

Partie 4 : Gain de complexité : auto-jointure exhaustive vs LSH¶

Mesurons maintenant le gain de temps apporté par LSH pour l'auto-jointure sur des corpus de taille croissante.

def autojointure_exhaustive(ensembles, seuil):
    """Auto-jointure exhaustive : O(N^2) comparaisons de Jaccard."""
    N = len(ensembles)
    paires = set()
    for i in range(N):
        for j in range(i+1, N):
            if jaccard(ensembles[i], ensembles[j]) >= seuil:
                paires.add((i, j))
    return paires

def autojointure_lsh(ensembles, seuil, num_perm=128):
    """Auto-jointure via LSH."""
    sigs = [minhash(e, num_perm) for e in ensembles]
    lsh  = MinHashLSH(threshold=seuil, num_perm=num_perm)
    for i, s in enumerate(sigs):
        lsh.insert(f"d{i}", s)
    paires = set()
    for i, s in enumerate(sigs):
        for cle in lsh.query(s):
            j = int(cle[1:])
            if j > i:
                paires.add((i, j))
    return paires

# Comparaison pour des tailles croissantes
tailles = [50, 100, 200, 400]
t_exhaustifs = []
t_lshs = []
print(f"{'N':>6}  {'Exhaustif (s)':>14}  {'LSH (s)':>10}  "
      f"{'Accélération':>13}  {'Rappel LSH':>12}")
print("-" * 62)

for N_test in tailles:
    sous_corpus = ensembles[:N_test]

    t0 = time.time()
    paires_ex = autojointure_exhaustive(sous_corpus, seuil)
    t_ex = time.time() - t0
    t_exhaustifs.append(t_ex)

    t0 = time.time()
    paires_lsh = autojointure_lsh(sous_corpus, seuil)
    t_lsh = time.time() - t0
    t_lshs.append(t_lsh)

    vp = len(paires_ex & paires_lsh)
    rappel = vp / len(paires_ex) if paires_ex else 1.0
    accel  = t_ex / t_lsh if t_lsh > 0 else float('inf')

    print(f"{N_test:>6}  {t_ex:>14.3f}  {t_lsh:>10.3f}  "
          f"{accel:>13.1f}×  {rappel:>12.3f}")

Question :

Comment évolue le rapport de temps entre l'approche exhaustive et LSH quand \(N\) augmente ? Ce comportement est-il cohérent avec les complexités théoriques \(O(N^2)\) (exhaustif) et approximativement \(O(N)\) (LSH) ? Le rappel est-il satisfaisant ?

Correction :

Quand \(N\) double, le temps exhaustif est multiplié par environ 4 (croissance quadratique), tandis que le temps LSH est multiplié par environ 2 (croissance quasi-linéaire). L'accélération apportée par LSH augmente donc avec \(N\), ce qui confirme l'intérêt de l'approche pour les grandes collections. Le rappel reste relativement élevé, ce qui signifie que LSH retrouve une majorité des paires vraiment similaires.

Question :

Tracez le temps d'exécution en fonction de \(N\) pour les deux approches (sur une même figure en échelle log-log). Que peut-on lire directement sur une telle courbe concernant les ordres de complexité ?

Correction :

En échelle log-log, une complexité \(O(N^k)\) se traduit par une droite de pente \(k\). La droite de l'approche exhaustive doit avoir une pente proche de 2, celle de LSH une pente proche de 1. Plus \(N\) est grand, plus l'écart vertical entre les deux droites est important, ce qui illustre l'accélération croissante apportée par LSH.

import matplotlib.pyplot as plt

fig, ax = plt.subplots()
ax.loglog(tailles, t_exhaustifs, 'o-', label='Exhaustif O(N²)')
ax.loglog(tailles, t_lshs,       's-', label='LSH O(N)')
ax.set_xlabel('N (taille du corpus)')
ax.set_ylabel('Temps (s)')
ax.legend()
ax.set_title('Auto-jointure : exhaustif vs LSH (log-log)')
plt.tight_layout()
plt.show()

Question (bilan) :

Résumez les compromis à effectuer lors de l'utilisation de MinHash LSH : quels paramètres agissent sur le rappel ? sur la précision ? sur le temps de calcul ? sur la mémoire occupée ? Donnez une règle pratique pour choisir num_perm et threshold.

Correction :

Rappel : augmente avec num_perm (meilleure estimation MinHash) et avec un threshold plus bas (plus de paires retournées). L'augmentation de b (nombre de tables) augmente aussi le rappel.
Précision : augmente avec un threshold plus élevé (seuil plus strict) et avec un r plus grand (chaque table est plus sélective).
Temps de calcul : augmente linéairement avec num_perm (calcul des signatures) et avec b (nombre de tables interrogées par la requête).
Mémoire : proportionnelle à \(N \times \text{num\_perm}\) pour le stockage des signatures et à \(N \times b\) pour l'index.

En pratique : choisir threshold en fonction du seuil de similarité métier (à partir de quelle similarité deux documents sont-ils considérés comme similaires ?), puis choisir num_perm entre 64 et 256 selon la tolérance à l'erreur d'estimation. datasketch détermine alors automatiquement b et r de façon optimale.

Travaux pratiques - Détection de quasi-copies avec MinHash LSH¶

Partie 1 : Similarité de Jaccard et signatures MinHash¶

Représentation par ensembles de k-grammes¶

Calcul exact de la similarité de Jaccard¶

Signatures MinHash¶

Partie 2 : Index LSH et recherche de documents similaires¶

Construction de l'index¶

Recherche par similarité¶

Interprétation des catégories¶

Partie 3 : Impact des paramètres \(n\) et \(t\)¶

Constitution d'un ensemble de référence¶

Mesure de précision et rappel pour différentes configurations¶

Partie 4 : Gain de complexité : auto-jointure exhaustive vs LSH¶

Table des matières

Recherche