{ "cells": [ { "cell_type": "markdown", "id": "4924e439", "metadata": {}, "source": [ "\n", "" ] }, { "cell_type": "markdown", "id": "e102a908", "metadata": {}, "source": [ "# Travaux pratiques - Détection de quasi-copies avec MinHash LSH\n", "\n", "Références externes utiles :\n", "\n", "> - [Documentation datasketch](https://ekzhu.com/datasketch/documentation.html) \n", "- [datasketch sur GitHub](https://github.com/ekzhu/datasketch) \n", "- [Jeu de données 20 Newsgroups (scikit-learn)](https://scikit-learn.org/stable/datasets/real_world.html#the-20-newsgroups-text-dataset) " ] }, { "cell_type": "markdown", "id": "19d5da04", "metadata": {}, "source": [ "# Objectif\n", "\n", "**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](https://github.com/ekzhu/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.\n", "\n", "Les quatre parties de la séance sont :\n", "\n", "1. Calcul de la similarité de Jaccard et construction de *hash* (ou signatures) MinHash. \n", "1. Construction d'un index LSH et recherche de documents similaires à une requête. \n", "1. Mesure de l'impact des paramètres $ n $ et $ t $ sur la précision et le rappel. \n", "1. Comparaison du coût d'une auto-jointure exhaustive $ O(N^2) $ et d'une auto-jointure via LSH. " ] }, { "cell_type": "markdown", "id": "fa16208e", "metadata": {}, "source": [ "# Mise en place\n", "\n", "Installez la bibliothèque `datasketch` si elle n'est pas déjà disponible :" ] }, { "cell_type": "code", "execution_count": null, "id": "23d8248b", "metadata": { "hide-output": false }, "outputs": [], "source": [ "import sys\n", "import subprocess\n", "subprocess.check_call([sys.executable, \"-m\", \"pip\", \"install\", \"datasketch\", \"--quiet\"])" ] }, { "cell_type": "markdown", "id": "80413729", "metadata": {}, "source": [ "Vérifiez l'installation en important les classes dont nous aurons besoin :" ] }, { "cell_type": "code", "execution_count": null, "id": "0bb3705c", "metadata": { "hide-output": false }, "outputs": [], "source": [ "from datasketch import MinHash, MinHashLSH\n", "import numpy as np\n", "import time" ] }, { "cell_type": "markdown", "id": "f7dea022", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": null, "id": "dfee859b", "metadata": { "hide-output": false }, "outputs": [], "source": [ "from sklearn.datasets import fetch_20newsgroups\n", "\n", "# Chargement des données (toutes catégories, sans les en-têtes)\n", "newsgroups = fetch_20newsgroups(subset='all',\n", " remove=('headers', 'footers', 'quotes'))\n", "textes = newsgroups.data\n", "categories = newsgroups.target\n", "noms_categories = newsgroups.target_names\n", "\n", "print(f\"{len(textes)} documents, {len(noms_categories)} catégories\")\n", "print(\"Exemple (300 premiers caractères) :\")\n", "print(textes[0][:300])" ] }, { "cell_type": "markdown", "id": "7db96cc9", "metadata": {}, "source": [ "Pour garder des temps de calcul raisonnables nous travaillerons sur un sous-ensemble de 2 000 documents, tirés aléatoirement :" ] }, { "cell_type": "code", "execution_count": null, "id": "efadecf6", "metadata": { "hide-output": false }, "outputs": [], "source": [ "rng = np.random.default_rng(seed=42)\n", "indices = rng.choice(len(textes), size=2000, replace=False)\n", "corpus = [textes[i] for i in indices]\n", "labels = [categories[i] for i in indices]\n", "N = len(corpus)\n", "print(f\"Corpus de travail : {N} documents\")" ] }, { "cell_type": "markdown", "id": "64a8f4e8", "metadata": {}, "source": [ "## Partie 1 : Similarité de Jaccard et signatures MinHash" ] }, { "cell_type": "markdown", "id": "b987b74b", "metadata": {}, "source": [ "### Représentation par ensembles de k-grammes\n", "\n", "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é." ] }, { "cell_type": "code", "execution_count": null, "id": "428bb6c4", "metadata": { "hide-output": false }, "outputs": [], "source": [ "def kgrammes(texte, k=3):\n", " \"\"\"Retourne l'ensemble des k-grammes d'un texte (en minuscules).\"\"\"\n", " texte = texte.lower()\n", " return set(texte[i:i+k] for i in range(len(texte) - k + 1))\n", "\n", "# Calcul des ensembles de k-grammes pour tout le corpus\n", "k = 3\n", "ensembles = [kgrammes(doc, k) for doc in corpus]\n", "print(f\"Exemple : document 0 → {len(ensembles[0])} k-grammes distincts\")" ] }, { "cell_type": "markdown", "id": "e815e58e", "metadata": {}, "source": [ "### Question :\n", "\n", "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 ?" ] }, { "cell_type": "markdown", "id": "207af7fd", "metadata": {}, "source": [ "### Correction :" ] }, { "cell_type": "code", "execution_count": null, "id": "7697c94c", "metadata": { "hide-output": false }, "outputs": [], "source": [ "print(list(ensembles[0])[:20])" ] }, { "cell_type": "markdown", "id": "bef85988", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "id": "f7ff24d9", "metadata": {}, "source": [ "### Calcul exact de la similarité de Jaccard\n", "\n", "Écrivons une fonction de calcul exact de la similarité de Jaccard entre deux ensembles :" ] }, { "cell_type": "code", "execution_count": null, "id": "94c86c3b", "metadata": { "hide-output": false }, "outputs": [], "source": [ "def jaccard(A, B):\n", " \"\"\"Similarité de Jaccard entre deux ensembles.\"\"\"\n", " inter = len(A & B)\n", " union = len(A | B)\n", " return inter / union if union > 0 else 0.0\n", "\n", "# Test sur les deux premiers documents\n", "print(f\"Jaccard(doc0, doc1) = {jaccard(ensembles[0], ensembles[1]):.4f}\")" ] }, { "cell_type": "markdown", "id": "d699bb7a", "metadata": {}, "source": [ "### Question :\n", "\n", "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 ?" ] }, { "cell_type": "markdown", "id": "b544f8b1", "metadata": {}, "source": [ "### Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "afa8af58", "metadata": {}, "source": [ "### Signatures MinHash\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "b39537a7", "metadata": { "hide-output": false }, "outputs": [], "source": [ "num_perm = 128 # nombre de fonctions de hachage élémentaires\n", "\n", "def minhash(ensemble, num_perm=128):\n", " \"\"\"Calcule la signature MinHash d'un ensemble.\"\"\"\n", " m = MinHash(num_perm=num_perm)\n", " for element in ensemble:\n", " m.update(element.encode('utf-8'))\n", " return m\n", "\n", "# Calcul des signatures pour tout le corpus\n", "t0 = time.time()\n", "signatures = [minhash(e, num_perm) for e in ensembles]\n", "print(f\"Signatures calculées en {time.time()-t0:.1f} s\")" ] }, { "cell_type": "markdown", "id": "70e861c1", "metadata": {}, "source": [ "La similarité de Jaccard peut être **estimée** à partir des signatures (sans accéder aux ensembles) :" ] }, { "cell_type": "code", "execution_count": null, "id": "d7d03e86", "metadata": { "hide-output": false }, "outputs": [], "source": [ "jaccard_exact = jaccard(ensembles[0], ensembles[1])\n", "jaccard_estime = signatures[0].jaccard(signatures[1])\n", "print(f\"Jaccard exact : {jaccard_exact:.4f}\")\n", "print(f\"Jaccard estimé : {jaccard_estime:.4f}\")\n", "print(f\"Erreur absolue : {abs(jaccard_exact - jaccard_estime):.4f}\")" ] }, { "cell_type": "markdown", "id": "e60d4718", "metadata": {}, "source": [ "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 $." ] }, { "cell_type": "markdown", "id": "46a01bdb", "metadata": {}, "source": [ "## Partie 2 : Index LSH et recherche de documents similaires" ] }, { "cell_type": "markdown", "id": "1472b800", "metadata": {}, "source": [ "### Construction de l'index\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "id": "9d4b9866", "metadata": { "hide-output": false }, "outputs": [], "source": [ "seuil = 0.3 # seuil de similarité de Jaccard\n", "\n", "lsh = MinHashLSH(threshold=seuil, num_perm=num_perm)\n", "\n", "# Insertion de tous les documents dans l'index\n", "t0 = time.time()\n", "for i, sig in enumerate(signatures):\n", " lsh.insert(f\"doc_{i}\", sig)\n", "print(f\"Index construit en {time.time()-t0:.2f} s\")" ] }, { "cell_type": "markdown", "id": "40d1ee28", "metadata": {}, "source": [ "### Question :\n", "\n", "Inspectez l'objet `lsh` : accédez à `lsh.b` et `lsh.r`. Que représentent ces deux valeurs ?\n", "Quel est leur produit, et quel lien a-t-il avec `num_perm` ?" ] }, { "cell_type": "markdown", "id": "dc10ecbb", "metadata": {}, "source": [ "### Correction :\n", "\n", "> " ] }, { "cell_type": "code", "execution_count": null, "id": "d60e0f7f", "metadata": { "hide-output": false }, "outputs": [], "source": [ "lsh.__dict__" ] }, { "cell_type": "markdown", "id": "c0afcb85", "metadata": {}, "source": [ "\n", "`lsh.b` est le nombre de tables de hachage ($ t $) et `lsh.r` est le nombre de\n", "fonctions élémentaires par table ($ n $). Leur produit `b × r` doit être inférieur ou\n", "égal à `num_perm`. En cas d'inégalité, `b × r` permutations sont employées par LSH et\n", "les `num_perm - b × r` permutations restantes servent simplement à calculer un peu mieux\n", "la similarité de Jaccard entre la requête et les candidats retournés par LSH.\n", "\n", "`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`." ] }, { "cell_type": "markdown", "id": "78346046", "metadata": {}, "source": [ "### Recherche par similarité" ] }, { "cell_type": "code", "execution_count": null, "id": "9f4b9863", "metadata": { "hide-output": false }, "outputs": [], "source": [ "# Recherche des documents similaires au document 0\n", "requete = signatures[0]\n", "resultats = lsh.query(requete)\n", "print(f\"Documents similaires à doc_0 (seuil={seuil}) : {resultats}\")\n", "\n", "# Vérification : similarité exacte avec chaque résultat\n", "for cle in resultats:\n", " idx = int(cle.split('_')[1])\n", " j = jaccard(ensembles[0], ensembles[idx])\n", " print(f\" {cle} : Jaccard exact = {j:.4f}\")" ] }, { "cell_type": "markdown", "id": "4e42d792", "metadata": {}, "source": [ "### Question :\n", "\n", "Parmi les résultats retournés, y a-t-il des **faux positifs** (documents retournés\n", "dont la similarité exacte est inférieure au seuil) ? Est-ce difficile de trouver manuellement\n", "dans le corpus un document dont la similarité avec `doc_0` est supérieure au seuil mais qui\n", "n'apparaît pas dans les résultats (**faux négatif**) ? Pourquoi ?" ] }, { "cell_type": "markdown", "id": "fb678931", "metadata": {}, "source": [ "### Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "689b2c5b", "metadata": {}, "source": [ "### Interprétation des catégories\n", "\n", "Quelle catégorie représentent les documents trouvés ?" ] }, { "cell_type": "code", "execution_count": null, "id": "d78f9a14", "metadata": { "hide-output": false }, "outputs": [], "source": [ "idx_resultats = [int(c.split('_')[1]) for c in resultats]\n", "for idx in idx_resultats:\n", " print(f\" doc_{idx} → catégorie : {noms_categories[labels[idx]]}\")" ] }, { "cell_type": "markdown", "id": "6b8eb3f0", "metadata": {}, "source": [ "### Question :\n", "\n", "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 ?" ] }, { "cell_type": "markdown", "id": "e0e4960e", "metadata": {}, "source": [ "### Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "7898e42b", "metadata": {}, "source": [ "## Partie 3 : Impact des paramètres $ n $ et $ t $\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "5444d6f2", "metadata": {}, "source": [ "### Constitution d'un ensemble de référence\n", "\n", "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 :" ] }, { "cell_type": "code", "execution_count": null, "id": "421fa4fd", "metadata": { "hide-output": false }, "outputs": [], "source": [ "N_ref = 200\n", "corpus_ref = corpus[:N_ref]\n", "ensembles_ref = ensembles[:N_ref]\n", "\n", "# Calcul exhaustif : toutes les paires (i, j) avec i < j\n", "t0 = time.time()\n", "paires_vraies = set()\n", "for i in range(N_ref):\n", " for j in range(i+1, N_ref):\n", " if jaccard(ensembles_ref[i], ensembles_ref[j]) >= seuil:\n", " paires_vraies.add((i, j))\n", "t_exhaustif = time.time() - t0\n", "print(f\"Référence exhaustive : {len(paires_vraies)} paires similaires\")\n", "print(f\"Temps (exhaustif, N={N_ref}) : {t_exhaustif:.2f} s\")" ] }, { "cell_type": "markdown", "id": "baa1cda8", "metadata": {}, "source": [ "### Mesure de précision et rappel pour différentes configurations" ] }, { "cell_type": "code", "execution_count": null, "id": "2169ee7e", "metadata": { "hide-output": false }, "outputs": [], "source": [ "def evaluer_lsh(ensembles, paires_vraies, num_perm, threshold):\n", " \"\"\"Construit un index LSH, fait l'auto-jointure et calcule précision/rappel.\"\"\"\n", " sigs = [minhash(e, num_perm) for e in ensembles]\n", " lsh = MinHashLSH(threshold=threshold, num_perm=num_perm)\n", " for i, s in enumerate(sigs):\n", " lsh.insert(f\"d{i}\", s)\n", "\n", " paires_lsh = set()\n", " t0 = time.time()\n", " for i, s in enumerate(sigs):\n", " for cle in lsh.query(s):\n", " j = int(cle[1:])\n", " if j > i:\n", " paires_lsh.add((i, j))\n", " t_lsh = time.time() - t0\n", "\n", " vp = len(paires_vraies & paires_lsh)\n", " precision = vp / len(paires_lsh) if paires_lsh else 0.0\n", " rappel = vp / len(paires_vraies) if paires_vraies else 0.0\n", " return precision, rappel, t_lsh, lsh.b, lsh.r\n", "\n", "# Exploration de différentes valeurs de num_perm avec threshold fixé\n", "print(f\"{'num_perm':>8} {'b (tables)':>10} {'r (fonct.)':>10} \"\n", " f\"{'Précision':>10} {'Rappel':>8} {'Temps (s)':>10}\")\n", "print(\"-\" * 65)\n", "for np_ in [32, 64, 128, 256]:\n", " p, r, t, b, rv = evaluer_lsh(ensembles_ref, paires_vraies, np_, seuil)\n", " print(f\"{np_:>8} {b:>10} {rv:>10} {p:>10.3f} {r:>8.3f} {t:>10.3f}\")" ] }, { "cell_type": "markdown", "id": "745ebeac", "metadata": {}, "source": [ "### Question :\n", "\n", "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 ?" ] }, { "cell_type": "markdown", "id": "590b3a87", "metadata": {}, "source": [ "### Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "83a0ea7a", "metadata": {}, "source": [ "### Question :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "554e38ae", "metadata": {}, "source": [ "### Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "848faff1", "metadata": {}, "source": [ "## Partie 4 : Gain de complexité : auto-jointure exhaustive vs LSH\n", "\n", "Mesurons maintenant le gain de temps apporté par LSH pour l'auto-jointure sur des corpus de taille croissante." ] }, { "cell_type": "code", "execution_count": null, "id": "1d478de4", "metadata": { "hide-output": false }, "outputs": [], "source": [ "def autojointure_exhaustive(ensembles, seuil):\n", " \"\"\"Auto-jointure exhaustive : O(N^2) comparaisons de Jaccard.\"\"\"\n", " N = len(ensembles)\n", " paires = set()\n", " for i in range(N):\n", " for j in range(i+1, N):\n", " if jaccard(ensembles[i], ensembles[j]) >= seuil:\n", " paires.add((i, j))\n", " return paires\n", "\n", "def autojointure_lsh(ensembles, seuil, num_perm=128):\n", " \"\"\"Auto-jointure via LSH.\"\"\"\n", " sigs = [minhash(e, num_perm) for e in ensembles]\n", " lsh = MinHashLSH(threshold=seuil, num_perm=num_perm)\n", " for i, s in enumerate(sigs):\n", " lsh.insert(f\"d{i}\", s)\n", " paires = set()\n", " for i, s in enumerate(sigs):\n", " for cle in lsh.query(s):\n", " j = int(cle[1:])\n", " if j > i:\n", " paires.add((i, j))\n", " return paires\n", "\n", "# Comparaison pour des tailles croissantes\n", "tailles = [50, 100, 200, 400]\n", "t_exhaustifs = []\n", "t_lshs = []\n", "print(f\"{'N':>6} {'Exhaustif (s)':>14} {'LSH (s)':>10} \"\n", " f\"{'Accélération':>13} {'Rappel LSH':>12}\")\n", "print(\"-\" * 62)\n", "\n", "for N_test in tailles:\n", " sous_corpus = ensembles[:N_test]\n", "\n", " t0 = time.time()\n", " paires_ex = autojointure_exhaustive(sous_corpus, seuil)\n", " t_ex = time.time() - t0\n", " t_exhaustifs.append(t_ex)\n", "\n", " t0 = time.time()\n", " paires_lsh = autojointure_lsh(sous_corpus, seuil)\n", " t_lsh = time.time() - t0\n", " t_lshs.append(t_lsh)\n", "\n", " vp = len(paires_ex & paires_lsh)\n", " rappel = vp / len(paires_ex) if paires_ex else 1.0\n", " accel = t_ex / t_lsh if t_lsh > 0 else float('inf')\n", "\n", " print(f\"{N_test:>6} {t_ex:>14.3f} {t_lsh:>10.3f} \"\n", " f\"{accel:>13.1f}× {rappel:>12.3f}\")" ] }, { "cell_type": "markdown", "id": "dbec5886", "metadata": {}, "source": [ "## Question :\n", "\n", "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 ?" ] }, { "cell_type": "markdown", "id": "9cd351b5", "metadata": {}, "source": [ "## Correction :\n", "\n", "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." ] }, { "cell_type": "markdown", "id": "ff08d357", "metadata": {}, "source": [ "## Question :\n", "\n", "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é ?" ] }, { "cell_type": "markdown", "id": "76c77137", "metadata": {}, "source": [ "## Correction :\n", "\n", "> 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." ] }, { "cell_type": "code", "execution_count": null, "id": "6ead311a", "metadata": { "hide-output": false }, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "\n", "fig, ax = plt.subplots()\n", "ax.loglog(tailles, t_exhaustifs, 'o-', label='Exhaustif O(N²)')\n", "ax.loglog(tailles, t_lshs, 's-', label='LSH O(N)')\n", "ax.set_xlabel('N (taille du corpus)')\n", "ax.set_ylabel('Temps (s)')\n", "ax.legend()\n", "ax.set_title('Auto-jointure : exhaustif vs LSH (log-log)')\n", "plt.tight_layout()\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "5e125eaf", "metadata": {}, "source": [ "## Question (bilan) :\n", "\n", "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`." ] }, { "cell_type": "markdown", "id": "6037d774", "metadata": {}, "source": [ "## Correction :\n", "\n", "- **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. \n", "- **Précision** : augmente avec un `threshold` plus élevé (seuil plus strict) et avec un `r` plus grand (chaque table est plus sélective). \n", "- **Temps de calcul** : augmente linéairement avec `num_perm` (calcul des signatures) et avec `b` (nombre de tables interrogées par la requête). \n", "- **Mémoire** : proportionnelle à $ N \\times \\text{num\\_perm} $ pour le stockage des signatures et à $ N \\times b $ pour l'index. \n", "\n", "\n", "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." ] } ], "metadata": { "date": 1792566218.6432536, "filename": "tpMinHashLSH.rst", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python" }, "title": "Travaux pratiques - Détection de quasi-copies avec MinHash LSH" }, "nbformat": 4, "nbformat_minor": 5 }