Warum macht die Textreuse-Packung in R LSH-Eimer viel größer als die ursprünglichen Minhashes?
Soweit ich weiß, ist eine der Hauptfunktionen der LSH-Methode die Datenreduktion auch über die zugrunde liegenden Hashes hinaus (häufig Minhashes). Ich habe das textreusePaket in R verwendet und bin von der Größe der generierten Daten überrascht. textreuseist ein von Experten geprüftes ROpenSci- Paket, daher gehe ich davon aus, dass es seine Aufgabe korrekt erfüllt, aber meine Frage bleibt bestehen.
Angenommen, ich verwende 256 Permutationen und 64 Bänder für meine Minhash- bzw. LSH-Funktionen - realistische Werte, die häufig verwendet werden, um Ähnlichkeiten mit einer relativen Sicherheit (~ 98%) von nur 50% zu erkennen.
Wenn ich eine zufällige Textdatei mit TextReuseTextDocument(256 Dauerwellen) hashe und sie zuweise trtd, habe ich:
object.size(trtd$minhashes)
> 1072 bytes
Lassen Sie uns nun die LSH-Buckets für dieses Objekt (64 Bänder) erstellen und es zuweisen l, ich werde haben:
object.size(l$buckets)
> 6704 bytes
Die beibehaltenen Hashes in den LSH-Eimern sind also sechsmal größer als die ursprünglichen Minhashes. Ich verstehe, dass dies passiert, weil textreuse ein MD5-Digest verwendet wird , um die Bucket-Hashes zu erstellen.
Aber ist das nicht zu verschwenderisch / übertrieben, und kann ich es nicht verbessern? Ist es normal, dass unsere Datenreduktionstechnik in diesem Ausmaß aufgebläht wird? Und ist es nicht effektiver, die Dokumente basierend auf den ursprünglichen Hashes (ähnlich wie Dauerwellen = 256 und Bänder = 256) abzugleichen und dann einen Schwellenwert zu verwenden, um die falsch positiven Ergebnisse auszusortieren?
Beachten Sie, dass ich die typischen Texte wie Mining of Massive Datasets überprüft habe , diese Frage jedoch zu dieser speziellen Implementierung weiterhin besteht. Beachten Sie auch, dass die Frage nicht nur aus Neugier, sondern auch aus Not besteht. Wenn Sie Millionen oder Milliarden von Hashes haben, werden diese Unterschiede erheblich.
Antworten
Paketautor hier. Ja, es wäre verschwenderisch, mehr Hashes / Bänder zu verwenden, als Sie benötigen. (Beachten Sie jedoch, dass es sich hier um Kilobyte handelt, die viel kleiner sein können als die Originaldokumente.)
Die Frage ist, was brauchst du? Wenn Sie nur Übereinstimmungen finden müssen, die nahezu identisch sind (dh mit einem Jaccard-Wert nahe 1,0), benötigen Sie keine besonders sensible Suche. Wenn Sie jedoch potenzielle Übereinstimmungen, die nur eine teilweise Überlappung aufweisen, zuverlässig erkennen müssen (dh mit einem Jaccard-Score, der näher an 0 liegt), benötigen Sie mehr Hashes / Bänder.
Da Sie MMD gelesen haben, können Sie dort die Gleichung nachschlagen. Das hier dokumentierte Paket enthält jedoch zwei Funktionen , mit denen Sie berechnen können, wie viele Hashes / Bänder Sie benötigen. lsh_threshold()berechnet den Jaccard-Schwellenwert, der erkannt wird; Dabei lsh_probability()erfahren Sie, wie wahrscheinlich es ist, dass ein Dokumentpaar mit einer bestimmten Jaccard-Punktzahl erkannt wird. Spielen Sie mit diesen beiden Funktionen herum, bis Sie die Anzahl der Hashes / Bänder erhalten, die für Ihr Suchproblem optimal sind.