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 ?

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 ?

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 ?

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 ?

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 ?

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 ?

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.

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 ?

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é ?

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.

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