Détection de quasi-doublons avec la similarité de Jaccard et MinHash

Trouver des documents similaires : similarité de Jaccard et MinHash

• Définition du problème
  • Discussion sur la manière d’identifier des documents similaires dans une collection de documents à grande échelle
  • Par exemple, lorsqu’une même page est récupérée plusieurs fois via du web crawling, on peut se retrouver avec plusieurs versions dues à de légères différences de métadonnées ou à de petites modifications éditoriales
  • Cet article explore une méthode de déduplication approximative utilisant la similarité de Jaccard et MinHash

Similarité

• Définition de la similarité
  • Définir la similarité entre deux documents et trouver les paires dont la valeur de similarité dépasse un certain seuil
  • Définir une fonction de similarité S:U×U→[0,1], et considérer que deux documents sont des quasi-doublons lorsque S(A,B)≥S_crit

Similarité de Jaccard

• Similarité de Jaccard
  • Fonction qui exprime la similarité entre deux ensembles finis comme le rapport entre leur intersection et leur union
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Plus deux ensembles sont similaires, plus ils partagent les mêmes éléments

Extension de la similarité de Jaccard

• Méthode d’extension
  • Transformer les documents en ensembles de caractéristiques, puis rechercher les ensembles ayant une forte similarité de Jaccard
  • Cette approche est directement applicable sur un petit corpus, mais devient inefficace sur un corpus volumineux

Approximation de la similarité de Jaccard

• Signature MinHash
  • Utiliser l’échantillonnage pour approximer la similarité de Jaccard
  • Pré-calculer pour chaque document une signature de taille fixe afin d’estimer efficacement la similarité

Utiliser davantage de fonctions de hachage

• Fonctions de hachage multiples
  • Utiliser plusieurs fonctions de hachage pour résumer chaque document sous forme d’un vecteur de k éléments
  • Approximer la similarité de Jaccard en comptant le nombre de hachages identiques entre deux signatures

Comparer tous les documents

• Regroupement des documents
  • Regrouper les documents afin de ne comparer que les documents similaires
  • Utiliser les valeurs MinHash comme clés de regroupement pour trouver efficacement des quasi-doublons

Détection de doublons plus flexible

• Utilisation de plusieurs clés
  • Utiliser plusieurs clés pour placer les documents dans plusieurs buckets, puis effectuer les comparaisons à l’intérieur de chaque bucket
  • Cela permet de détecter des doublons même pour des valeurs de similarité plus faibles

Conclusion

• Conclusion
  • Des algorithmes comme MinHash permettent de trouver efficacement des documents similaires
  • Souhait que cet article aide davantage d’ingénieurs à découvrir et à comprendre ce type d’algorithmes

Annexe : représenter un document comme un ensemble

• n-grammes

  • Représenter les documents avec des n-grammes pour les comparer
  • La précision de la comparaison varie selon la valeur de n

• Découpage en mots

  • Découper les documents en mots ou en tokens pour les utiliser comme caractéristiques
  • Il est aussi possible d’utiliser des tokenizers plus sophistiqués

Avis de GN⁺

• Importance de la détection de documents similaires

  • Éliminer les doublons dans de grands jeux de données est important pour améliorer la qualité des données et économiser de l’espace de stockage
  • C’est particulièrement indispensable dans le web crawling ou les processus de collecte de données

• Avantages de MinHash

  • MinHash permet de détecter des documents similaires de manière efficace et scalable
  • L’approche est plus flexible que les méthodes classiques de déduplication basées sur le hachage

• Autres techniques similaires

  • D’autres algorithmes de sketch, comme HyperLogLog, peuvent aussi être utilisés pour résoudre des problèmes similaires
  • Combiner les deux algorithmes peut permettre de construire une solution plus robuste

• Points à considérer en pratique

  • Importance du choix des fonctions de hachage : ce choix a un impact majeur sur la précision des résultats
  • Équilibre entre performance et précision : plus on utilise de fonctions de hachage, plus la précision augmente, mais avec un coût de performance plus élevé

• Technologies recommandées

  • Peut être mis en œuvre facilement avec des outils comme l’implémentation MinHashLSH de Spark
  • Il est recommandé d’exploiter activement ce type de techniques pour une déduplication efficace sur de grands jeux de données

[GN⁺]

Avis Hacker News

• La similarité de Jaccard et le score F1 peuvent aussi être utilisés tels quels avec des ensembles flous

  • Avec des ensembles flous, il faut choisir une paire T-Norm/T-Conorm appropriée
  • Cette méthode est utile pour la validation de la segmentation d’images médicales
  • La plupart des gens fixent un seuil à 0,5 et utilisent des ensembles binaires
  • Cela réduit fortement la précision de l’opérateur de validation

• J’ai déjà mis en œuvre la déduplication de la base de données du gouvernement français en Python

  • Aujourd’hui, je recommande datasketch
  • Il existe aussi un nouvel outil appelé rensa
  • rensa est une version plus rapide écrite en Rust

• C’est une technique développée au début chez Google pour la déduplication

  • Elle est expliquée en détail dans "Mining Massive Datasets" de Jeffrey Ullman
  • Cette technique a d’abord été développée chez AltaVista

• J’ai déjà implémenté un système Minhash

  • Cela résolvait un problème consistant à trouver l’inverse (approché) de sous-matrices dans de grandes matrices
  • J’ai utilisé le minhashing pour trouver des matrices similaires
  • J’ai utilisé du hachage multi-résolution pour ajuster la sélectivité de la recherche

• Comme Minhash et ses variantes sont difficiles à comprendre, je suis en train de créer un outil de visualisation

  • Il inclura aussi le calcul de similarité de Jaccard

• Il est plus facile de comprendre la technique avec des exemples de code

  • J’ai appris cette technique de Douglas Eck chez Google
  • Elle est utilisée pour le clustering de chansons

• Une équipe de NVIDIA a publié un algorithme de déduplication floue accéléré par GPU

  • Un dépôt GitHub et une documentation sont fournis
  • Des exemples Python sont également inclus

• Une stratégie de déduplication combinant du hachage ou un petit réseau de neurones avec un moteur de recherche vectorielle est courante

  • Il existe le modèle RETSim de Google et le projet de moteur USearch

• J’ai signalé une coquille à l’auteur

  • Il faut écrire S(A,C) au lieu de S(A,B)

• Je travaille à résoudre le problème de réduction d’articles de presse similaires en un seul dans Postgres

  • Il y a 600 000 éléments de flux
  • Le contenu et les résumés sont très similaires