Erkennung ähnlicher Duplikate mit Jaccard-Ähnlichkeit und MinHash

Ähnliche Dokumente finden: Jaccard-Ähnlichkeit und MinHash

• Problemdefinition
  • Es wird diskutiert, wie sich ähnliche Dokumente in einer großen Dokumentensammlung identifizieren lassen.
  • Wenn man etwa beim Web-Crawling dieselbe Seite mehrfach abruft, kann es mehrere Versionen mit kleinen Unterschieden in den Metadaten oder nach geringfügigen Bearbeitungen geben.
  • In diesem Beitrag wird ein Verfahren zur approximativen Deduplizierung mit Jaccard-Ähnlichkeit und MinHash untersucht.

Ähnlichkeit

• Definition von Ähnlichkeit
  • Es wird definiert, wie sich die Ähnlichkeit zwischen zwei Dokumenten messen lässt und wie Paare gefunden werden, deren Ähnlichkeitswert einen bestimmten Schwellenwert überschreitet.
  • Es wird eine Ähnlichkeitsfunktion S:U×U→[0,1] definiert; wenn S(A,B)≥S_crit gilt, werden die beiden Dokumente als approximative Duplikate betrachtet.

Jaccard-Ähnlichkeit

• Jaccard-Ähnlichkeit
  • Eine Funktion, die die Ähnlichkeit zweier endlicher Mengen als Verhältnis von Schnittmenge zu Vereinigungsmenge ausdrückt.
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Je ähnlicher zwei Mengen sind, desto mehr Elemente haben sie gemeinsam.

Erweiterung der Jaccard-Ähnlichkeit

• Erweiterungsmethode
  • Dokumente werden in Merkmalsmengen umgewandelt, und dann werden Mengen mit hoher Jaccard-Ähnlichkeit gesucht.
  • Für kleine Korpora ist das direkt anwendbar, bei großen Korpora jedoch ineffizient.

Approximation der Jaccard-Ähnlichkeit

• MinHash-Signaturen
  • Um die Jaccard-Ähnlichkeit zu approximieren, wird Sampling verwendet.
  • Für jedes Dokument wird vorab eine Signatur fester Größe berechnet, um die Ähnlichkeit effizient zu schätzen.

Mehr Hashfunktionen verwenden

• Mehrere Hashfunktionen
  • Mithilfe mehrerer Hashfunktionen wird jedes Dokument zu einem k-elementigen Vektor zusammengefasst.
  • Die Jaccard-Ähnlichkeit wird approximiert, indem die Anzahl übereinstimmender Hashwerte zwischen zwei Signaturen gezählt wird.

Vergleich aller Dokumente

• Dokumente gruppieren
  • Dokumente werden gruppiert, sodass nur ähnliche Dokumente miteinander verglichen werden.
  • MinHash-Werte werden als Gruppierungsschlüssel verwendet, um approximative Duplikate effizient zu finden.

Flexiblere Duplikaterkennung

• Verwendung mehrerer Schlüssel
  • Mit mehreren Schlüsseln werden Dokumente in mehrere Buckets eingeordnet und innerhalb jedes Buckets verglichen.
  • So lassen sich Duplikate auch bei niedrigeren Ähnlichkeitswerten erkennen.

Fazit

• Fazit
  • Mit Algorithmen wie MinHash lassen sich ähnliche Dokumente effizient finden.
  • Der Beitrag soll mehr Ingenieurinnen und Ingenieuren diese Algorithmen näherbringen und ihr Verständnis dafür fördern.

Anhang: Dokumente als Mengen darstellen

• n-Gramme

  • Dokumente werden zur Vergleichbarkeit als n-Gramme dargestellt.
  • Je nach Wert von n verändert sich die Genauigkeit des Vergleichs.

• Wortsegmentierung

  • Dokumente werden in Wörter oder Tokens zerlegt und als Merkmale verwendet.
  • Es können auch ausgefeiltere Tokenizer eingesetzt werden.

Meinung von GN⁺

• Bedeutung der Erkennung ähnlicher Dokumente

  • Das Entfernen von Duplikaten in großen Datensätzen ist wichtig, um die Datenqualität zu verbessern und Speicherplatz zu sparen.
  • Besonders beim Web-Crawling oder bei der Datenerfassung ist dies unverzichtbar.

• Vorteile von MinHash

  • MinHash ermöglicht die Erkennung ähnlicher Dokumente auf effiziente und skalierbare Weise.
  • Es ist flexibler als herkömmliche hashbasierte Verfahren zur Deduplizierung.

• Andere ähnliche Techniken

  • Auch andere Sketch-Algorithmen wie HyperLogLog können zur Lösung ähnlicher Probleme eingesetzt werden.
  • Durch die Kombination beider Algorithmen lässt sich eine noch leistungsfähigere Lösung schaffen.

• Aspekte für den praktischen Einsatz

  • Die Bedeutung der Wahl der Hashfunktion: Die Auswahl der Hashfunktion hat großen Einfluss auf die Genauigkeit der Ergebnisse.
  • Das Gleichgewicht zwischen Performance und Genauigkeit: Je mehr Hashfunktionen verwendet werden, desto höher ist die Genauigkeit, aber desto größer werden auch die Performance-Kosten.

• Empfohlene Technik

  • Mit Tools wie der MinHashLSH-Implementierung von Spark lässt sich dies leicht anwenden.
  • Für eine effiziente Deduplizierung in großen Datensätzen wird empfohlen, solche Techniken aktiv zu nutzen.

[GN⁺]

Hacker-News-Kommentare

• Jaccard-Ähnlichkeit und der F1-Score lassen sich auch bei unscharfen Mengen identisch verwenden

  • Bei unscharfen Mengen muss ein geeignetes T-Norm/T-Conorm-Paar gewählt werden
  • Diese Methode ist nützlich für die Validierung medizinischer Bildsegmentierung
  • Die meisten setzen den Schwellenwert auf 0,5 und verwenden binäre Mengen
  • Das verringert die Präzision des Validierungsoperators erheblich

• Es gibt Erfahrung mit der Implementierung von Deduplizierung für eine Datenbank der französischen Regierung in Python

  • Derzeit wird datasketch empfohlen
  • Es gibt auch ein neues Tool namens rensa
  • rensa ist eine schnellere, in Rust geschriebene Version

• Die Technik wurde in den frühen Tagen von Google zur Deduplizierung entwickelt

  • In Jeffrey Ullmans "Mining Massive Datasets" wird sie ausführlich erklärt
  • Ursprünglich wurde sie bei AltaVista entwickelt

• Es gibt Erfahrung mit der Implementierung eines Minhash-Systems

  • Dabei wurde das Problem gelöst, die (ungefähre) Inverse von Teilmatrizen großer Matrizen zu finden
  • Minhashing wurde verwendet, um ähnliche Matrizen zu finden
  • Mit Multi-Resolution-Hashing wurde die Selektivität der Suche angepasst

• Weil Minhash und seine Varianten schwer zu verstehen sind, wird an einem Visualisierungstool gearbeitet

  • Es soll auch die Berechnung der Jaccard-Ähnlichkeit enthalten

• Über Codebeispiele lässt sich die Technik leichter verstehen

  • Gelernt wurde sie von Douglas Eck bei Google
  • Sie wurde für Song-Clustering verwendet

• Das NVIDIA-Team hat einen GPU-beschleunigten Fuzzy-Deduplizierungsalgorithmus veröffentlicht

  • Ein GitHub-Repository und Dokumentation sind verfügbar
  • Python-Beispiele sind ebenfalls enthalten

• Deduplizierungsstrategien, die Hashing oder kleine neuronale Netze mit einer Vektorsuchmaschine kombinieren, sind verbreitet

  • Es gibt Googles RETSim-Modell und das USearch-Engine-Projekt

• Auf einen Tippfehler des Autors wurde hingewiesen

  • Statt S(A,B) sollte es S(A,C) heißen

• Es wird an der Lösung eines Problems gearbeitet, ähnliche Nachrichteneinträge in Postgres zu einem Eintrag zusammenzufassen

  • Es gibt 600.000 Feed-Einträge
  • Inhalt und Zusammenfassung sind sehr ähnlich