Was sind einige Standardmethoden zum Berechnen des Abstands zwischen Dokumenten?

34

Wenn ich "Dokument" sage, denke ich an Webseiten wie Wikipedia-Artikel und Nachrichten. Ich bevorzuge Antworten, die entweder lexikalische Entfernungsmetriken aus Vanille oder semantische Entfernungsmetriken nach dem neuesten Stand der Technik enthalten, wobei letztere stärker bevorzugt werden.

machine-learning data-mining nlp text-mining similarity Matt
quelle

Antworten:

48

Es gibt verschiedene Möglichkeiten, dies zu tun, je nachdem, wie viele semantische Informationen Sie behalten möchten und wie einfach das Token Ihrer Dokumente ist (HTML-Dokumente sind wahrscheinlich nur schwer zu token, aber Sie könnten möglicherweise etwas mit Tags und Kontext tun .)

Einige von ihnen wurden von ffriend erwähnt, und die Absatzvektoren von user1133029 sind wirklich solide, aber ich dachte nur, ich würde etwas mehr über Plusses und Minuspunkte verschiedener Ansätze erzählen.

  • Kosinusdistanz - Eine echte Kosinusdistanz ist wahrscheinlich die häufigste Distanzmetrik, die generisch für mehrere Domänen verwendet wird. Trotzdem gibt es nur sehr wenige Informationen in der Kosinusdistanz, die tatsächlich auf irgendetwas Semantisches abgebildet werden können, was für diese Situation nicht ideal zu sein scheint.
  • Levenshtein Distance ( Levenshtein-Abstand) - Auch bekannt als edit distance, dies wird normalerweise nur auf der Ebene der einzelnen Token verwendet (Wörter, Bigramme usw.). Im Allgemeinen würde ich diese Metrik nicht empfehlen, da sie nicht nur semantische Informationen verwirft, sondern auch sehr unterschiedliche Wortänderungen sehr ähnlich behandelt. Sie ist jedoch eine äußerst häufige Metrik für diese Art von Dingen
  • LSA - Ist ein Teil eines großen Arsenals von Techniken, wenn es um die Bewertung der Ähnlichkeit von Dokumenten geht topic modeling. LSA ist in letzter Zeit aus der Mode gekommen, und meiner Erfahrung nach ist es nicht ganz der stärkste Ansatz zur Themenmodellierung, aber es ist relativ einfach zu implementieren und verfügt über einige Open-Source-Implementierungen
  • LDA - Ist auch eine Technik, die verwendet wird topic modeling, unterscheidet sich jedoch darin, LSAdass sie interne Darstellungen lernt, die in der Regel flüssiger und intuitiver sind. Im Allgemeinen sind die Ergebnisse, die Sie erhalten, LDAfür die Modellierung der Dokumentähnlichkeit besser als LSA, aber nicht ganz so gut, um zu lernen, wie man stark zwischen Themen unterscheidet.
  • Pachinko Allocation - Ist eine wirklich nette Erweiterung zu LDA. Im Allgemeinen ist dies nur eine deutlich verbesserte Version von LDA. Der einzige Nachteil ist, dass die Schulung etwas länger dauert und Open-Source-Implementierungen etwas schwieriger zu bekommen sind
  • word2vec - Google hat an einer Reihe von Techniken gearbeitet, mit denen Wörter und Dokumente auf intelligente Weise auf vernünftigere Vektoren reduziert werden können als mit Techniken wie Count Vectorizersund TF-IDF. Word2vec ist großartig, da es eine Reihe von Open-Source-Implementierungen enthält. Sobald Sie den Vektor haben, kann jede andere Ähnlichkeitsmetrik (z. B. der Kosinusabstand) mit deutlich höherer Effizienz verwendet werden.
  • doc2vec - Auch bekannt als paragraph vectors: Dies ist die neueste und beste in einer Reihe von Veröffentlichungen von Google, die sich mit dichten Vektordarstellungen von Dokumenten befassen . Die gensimImplementierung der Bibliothek in Python word2vecist so einfach, dass sie mit vertretbarem Aufwand erstellt werden kann. doc2vecDenken Sie jedoch an die Lizenz, wenn Sie diesen Weg beschreiten möchten

Hoffe das hilft, lass es mich wissen, wenn du irgendwelche Fragen hast.

indico
quelle
6

Es gibt eine Reihe von semantischen Distanzmaßen, jedes mit seinen Vor- und Nachteilen. Hier sind nur einige davon:

  • Kosinusabstand , inneres Produkt zwischen Dokumentenmerkmalsvektoren;
  • LSA , ein anderes vektorbasiertes Modell, das jedoch SVD zum Entrauschen der ursprünglichen Term-Document-Matrix verwendet;
  • WordNet- basiert, vom Menschen verifiziert, jedoch kaum erweiterbar.

Beginnen Sie mit einem einfachsten Ansatz und gehen Sie dann je nach Problemstellung für Ihren speziellen Fall weiter.

freund
quelle
1
Beachten Sie, dass Sie bei der Ausführung von LSA in der Regel den Kosinusabstand für die LSA-Projektionen des Originaldatensatzes verwenden. Nur um klarzustellen.
Simon
6

Empirisch habe ich festgestellt, dass LSA LDA jedes Mal und bei jedem Datensatz, an dem ich es ausprobiert habe, weit überlegen ist. Ich habe mit anderen Menschen gesprochen, die dasselbe gesagt haben. Es wurde auch verwendet, um eine Reihe von SemEval-Wettbewerben für das Messen der semantischen Ähnlichkeit zwischen Dokumenten zu gewinnen, häufig in Kombination mit einem auf Wordnet basierenden Maß für Themenmodellierung und nicht semantische Ähnlichkeit in meiner Erfahrung, im Gegensatz zu dem, was einige Responder angegeben haben.

Wenn Sie gensim (eine Python-Bibliothek) verwenden, hat es LSA, LDA und word2vec, so dass Sie das 3. doc2vec leicht vergleichen können. Doc2vec ist eine coole Idee, lässt sich aber nicht sehr gut skalieren, und Sie müssen es wahrscheinlich selbst implementieren, wie ich es bin keine Kenntnis von Open-Source-Implementierungen. Es ist nicht gut skalierbar, da für jedes Dokument ein neues und separates Modell mit SGD, einem langsamen Algorithmus für maschinelles Lernen, erstellt werden muss. Aber es gibt Ihnen wahrscheinlich die genauesten Ergebnisse. LSA und LDA skalieren ebenfalls nicht gut (word2vec jedoch), LDA skaliert im Allgemeinen schlechter. Die Implementierungen von Gensim sind jedoch sehr schnell, da iterative SVD verwendet wird.

Ein weiterer Hinweis: Wenn Sie word2vec verwenden, müssen Sie immer noch festlegen, wie Vektoren aus Dokumenten zusammengesetzt werden sollen, da Sie einen anderen Vektor pro Wort erhalten. Der einfachste Weg, dies zu tun, besteht darin, jeden Vektor zu normalisieren und den Mittelwert über alle Wortvektoren im Dokument zu nehmen, oder einen gewichteten Mittelwert durch idf-Gewichtung jedes Wortes zu nehmen. Es ist also nicht so einfach wie 'use word2vec', Sie müssen etwas weiter machen, um die Ähnlichkeit von Dokumenten zu berechnen.

Ich persönlich würde mit LSA gehen, da ich gesehen habe, dass es empirisch gut funktioniert und Gensims Bibliothek sehr gut skaliert. Es gibt jedoch kein kostenloses Mittagessen. Probieren Sie daher am besten jede Methode aus, um herauszufinden, welche für Ihre Daten besser geeignet ist.

Simon
quelle
Wie genau haben Sie LSA angewendet? Es ist erwähnenswert, dass LDA tatsächlich eine ziemlich dünne Hülle um LSA ist (es ist pLSA mit einem Dirichlet-Prior), von der empirisch gezeigt wurde, dass sie die Verallgemeinerung erheblich steigert. Mit LSA würden Sie mit ziemlicher Sicherheit bessere Genauigkeiten sehen, aber das ist im Allgemeinen eine Folge der Überanpassung, was bei LSA ein sehr bemerkenswertes Problem darstellt. Was genau meinen Sie mit Skalierung hier? doc2vec benötigt nicht für jedes Dokument ein neues Modell, und für die Berechnung gibt es keinen nennenswerten Unterschied zwischen LSA und LDA, da beide sehr skalierbar sind.
Slater Victoroff
Ich habe nicht beobachtet, ob ich mit LSA in Einklang gekommen bin, und wie gesagt, ich habe mehrere andere Leute getroffen, die eine bessere Leistung als LDA gesehen haben. Außerdem habe ich gesehen, dass LSA in vielen Siegerwettbewerben eingesetzt wurde. Ich habe noch nie gesehen, dass LDA in einem Siegerwettbewerb eingesetzt wurde. Dies ist die akademische Konferenz zum Vergleich der semantischen Ähnlichkeit zwischen Dokumenten. Ich gehe also davon aus, dass sie wissen, was sie tun. Wenn Sie sich auf Mikolovs Absatzvektorimplementierung beziehen, führt Doc2vec SGD für jedes Dokument separat aus. Es ist also sehr langsam.
Simon
@SlaterVictoroff Ich denke, das ist zu viel, um zu sagen, dass es zu passend ist. Es ist bekannt, dass LDA für Such- / Informationsabruf- und Empfehlungsfälle schlecht ist. Empirisch hat sich gezeigt, dass LSA viel besser funktioniert. Dies entspricht auch meinen eigenen Erfahrungen, da ich diese Ergebnisse gerne anhand unserer eigenen Daten validieren möchte. Doc2Vec-Versionen führen einen Gradientenabstieg pro Dokument durch. Dies hängt vom in Doc2Vec verwendeten Algorithmus ab, da sich dieser im Allgemeinen auf viele verschiedene Algorithmen bezieht.
Simon
3

Stand der Technik scheinen "Absatzvektoren" zu sein, die in einem kürzlich erschienenen Artikel eingeführt wurden: http://cs.stanford.edu/~quocle/paragraph_vector.pdf . Der cosinus / euklidische Abstand zwischen Absatzvektoren würde wahrscheinlich besser funktionieren als jeder andere Ansatz. Dies ist wahrscheinlich noch nicht möglich, da es an Open Source-Implementierungen mangelt.

Das nächstbeste ist der Kosinusabstand zwischen LSA-Vektoren oder der Kosinusabstand zwischen rohen BOW-Vektoren. Manchmal ist es besser, andere Gewichtungsschemata zu wählen, wie z. B. TF-IDF.

user1133029
quelle
Beachten Sie meine Kommentare zur Skalierbarkeit von Absatzvektoren. Diese Technik sieht sehr vielversprechend aus, ist jedoch schwer zu implementieren und lässt sich überhaupt nicht gut skalieren, da Sie für jedes Dokument eine separate SGD erstellen, was sehr kostspielig ist, wenn ich mich an das Papier erinnere
Simon,
1

Es ist nützlich, die Familie der lokalitätssensitiven Hashing-Algorithmen in Ihrer Werkzeugtasche zu haben . Diese Familie ist überhaupt nicht semantisch. Eigentlich ist der Text als eine Folge von Bits zu betrachten. Ich finde es in schmutzigen Datensätzen nützlich, wenn derselbe Text mit geringfügigen Unterschieden oft vorkommt.

Sie können ssdeep (das auf Nilsimsa-Hash basiert ) verwenden, um solche Dokumente zu identifizieren. Ssdeep war ursprünglich für die Domain Spam geplant. Spammer nehmen häufig kleine Änderungen an der Nachricht vor (fügen Sie ein Leerzeichen hinzu), um die Erkennung durch exakte Signatur (z . B. md5 ) zu verhindern.

Da viele Versionen fast desselben Dokuments in demselben Datensatz statistische Methoden zerstören, die darauf angewendet werden, kann eine solche Bereinigung sehr vorteilhaft sein.

DaL
quelle