Quantifizieren Sie die Ähnlichkeit von Wortsäcken

Ich habe zwei Datensätze, die die häufigsten Wörter und ihre Häufigkeit von zwei verschiedenen Artikeln enthalten.

z.B:

A = [apple: 23, healthy: 15, tasty: 4]
B = [apple: 19, healthy: 21, bad: 7]

Beide Datensätze enthalten ähnliche Wörter. Ich möchte eine Maßnahme finden, die mir eine Vorstellung davon gibt, ob die beiden Artikel über dasselbe sprechen oder nicht. In diesem Fall diskutieren sie möglicherweise über Äpfel und ihre gesundheitlichen Vorteile.

Ich kann ein einfaches Maß wie bekommen, similarity = words in A and B / total number of wordsaber gibt es ein formelleres Maß, vielleicht eines, das die Frequenzen als Gewichte verwendet?

Lassen Sie mich dies ansprechen, indem ich die vier möglicherweise häufigsten Ähnlichkeitsmetriken für Wortbeutel und Dokumentvektoren (Zählvektoren) im Allgemeinen beschreibe, dh Sammlungen diskreter Variablen.

Die Kosinusähnlichkeit wird im Allgemeinen am häufigsten verwendet. Sie sollten jedoch immer zuerst messen und sicherstellen, dass keine andere Ähnlichkeit zu besseren Ergebnissen für Ihr Problem führt. Bewerten Sie, ob Sie einige der komplexeren Messgrößen verwenden können. Mit Ausnahme der Ähnlichkeit von Jaccard können Sie (möglicherweise möchten) eine Form der TF-IDF-Neugewichtung (ff) auf Ihre Dokumentanzahl / -vektoren anwenden , bevor Sie diese Maßnahmen verwenden. Das TF Gewichtungsterm könnte sogar sein Okapi-BM25 und der IDF Begriff ersetzt mit corpus Entropie , aber am Ende hat wenig mit der ursprünglichen Frage zur Hand zu tun (BOW Ähnlichkeitsmaß).

Beachten Sie, dass die erste Kennzahl, die Jaccard-Ähnlichkeit, einen erheblichen Nachteil aufweist: Sie ist am stärksten von Längenunterschieden zwischen Dokumenten betroffen und berücksichtigt auch nicht die Worthäufigkeit. Für die Kosinusähnlichkeit und den Abstand können (oder sollten) Sie die Vektoren anpassen, indem Sie Ihre Vektoren auf die Einheitslänge normalisieren (dh zusätzlich zur TF-IDF-Neugewichtung). Aber selbst dann haben kürzere Dokumente aus offensichtlichen Gründen eine geringere Anzahl (dh mehr Nullen in ihren Vektoren) als längere Dokumente. (Ein Weg, um diesen Unterschied in der Sparsity zu umgehen, könnte darin bestehen, nur Wörter oberhalb eines Mindestgrenzwerts einzuschließen und einen dynamischen Grenzwert zu verwenden, der mit der Dokumentlänge zunimmt.)$\chi^2$

Bevor wir auf die Maßnahmen eingehen, sollte erwähnt werden, dass sich diese Diskussion nur auf symmetrische Maßnahmen konzentriert, während auch asymmetrische Maßnahmen existieren (insbesondere die KL-Divergenz ).

1. Jaccard-Ähnlichkeit$J$

Dies ist die einfachste Metrik: Sammeln Sie die Menge aller Wörter in beiden Dokumenten (Tweets, Sätze, ...), und und messen Sie den Bruchteil der Wörter, die die beiden Sätze gemeinsam haben:${A}$${B}$

$$J_{A,B} = \frac{|{A} \cap {B}|}{|{A} \cup {B}|}$$

Diese Kennzahl funktioniert auch für Wörter (und Dokumente), indem Zeichensätze (oder Wort) Gramm gesammelt werden, wobei normalerweise 1, 2 und möglicherweise 3 ist. Beachten Sie jedoch, dass die Jaccard-Ähnlichkeit ihre Grenzen hat. Wenn die Sequenz von gewesen war und die der waren nur , deren Jaccard Ähnlichkeit dennoch perfekt ( das heißt, ), es sei denn, Sie verwenden den gerade beschriebenen n-Gramm-Trick.$n$$n$$A$$(x, y, z, x, y, z, x, y, z)$$B$$(x, y, z)$$1.0$

Schließlich sollte angemerkt werden, dass der Würfelkoeffizient$D$ eine etwas komplexere Version der Jaccard-Ähnlichkeit ist, aber auch die Wortanzahl nicht berücksichtigt und leicht aus berechnet werden kann als: .$J$$D = \frac{2J}{1+J}$

2. Kosinusähnlichkeit$\alpha$

Die Kosinusähnlichkeit ist wahrscheinlich die mit Abstand beliebteste Metrik. Collect geordneten Sätze aller Wortzählungen aus beiden Dokumenten (tweets, Sätze, ...), und , die effektiv ist, zwei " Dokumentenvektoren " und , und messen den Kosinus Winkel zwischen den beiden Vektoren:$A$$B$ $\vec{a}$$\vec{b}$

$$\alpha_{A,B} = \frac{\vec{a} \cdot \vec{b}}{|\vec{a}||\vec{b}|} = \frac{\sum{a_i b_i}}{\sqrt{\sum{a_i^2}}\sqrt{\sum{b_i^2}}}$$

Da Sie Ihre Vektoren vor dieser Berechnung auf Einheitsvektoren (dh die Teile) normalisieren können , müssen Sie nur das Punktprodukt zwischen den beiden Vektoren berechnen, um die Ähnlichkeit zu berechnen - was nichts ist mehr als die Summe der Produkte aller Paare. Das Punktprodukt kann auf modernen CPUs besonders effizient berechnet werden.$|\vec{z}|$

3. Rangkorrelationskoeffizient nach Spearman$\rho$

Anstatt die Anzahl der einzelnen Wörter zu verwenden, ordnen Sie die Wörter jedes Dokuments nach ihrer Anzahl und weisen damit jedem Wort für jedes Dokument, und , einen Rang zu . Dies erspart Ihnen die Längennormalisierung der Dokumentvektoren. Verwenden wir die Wikipedia-Nomenklatur und rufen die Ranggenerierungsfunktion auf (die den Rang für ein bestimmtes Wort aus einer (Wort-, Zähl-) Tupelliste oder einem Dokumentvektor ) . Zweitens definieren wir den Abstand zwischen demselben Wort zwischen den beiden Dokumenten als . Das ist,$A$$B$$i$$X$$\vec{x}$$rg$$d$$i$$d_i = rg(A, i) - rg(B, i)$$d$ die Differenz zwischen den beiden Rängen, Null, wenn gleich, und ungleich Null, sonst. Damit kann der Koeffizient aus ganzen Zahlen berechnet werden als:

$$\rho_{A,B} = 1 - \frac{6-\sum d_i^2}{n(n^2-1)}$$

Beachten Sie, dass für diese Formulierung starke Anforderungen gelten: Alle Ränge müssen unterschiedlich sein . Selbst für Bindungen (wenn zwei Wörter im selben Dokument dieselbe Anzahl haben) müssen Sie ihnen unterschiedliche Ränge zuweisen. Ich schlage vor, Sie verwenden in diesen Fällen die alphanumerische Reihenfolge. Und für Wörter, die nur in einem Dokument vorkommen, platzieren Sie sie an den letzten Positionen im anderen Dokument (wiederum in derselben alphanumerischen Reihenfolge). Es sollte beachtet werden, dass Sie durch erneutes Gewichten Ihrer Zählungen mit TF-IDF vor der Berechnung dieser Ähnlichkeit weitaus weniger Bindungen zwischen Wörtern mit Zählungen ungleich Null haben können.

Wenn Sie Bindungen beibehalten möchten (dh nicht alle Ränge "künstlich" unterscheiden möchten) oder wenn Sie Cutoffs verwenden, um einige der (Wort-, Zähl-) Tupel zu entfernen, oder nur die obersten häufigsten Wörter auswählen , Sie sollten mit der Standardformel für seine (und definieren als eine Funktion, die den kompletten rank erzeugt Vektor für alle Dokumente (Word, count) Tupel sind alphanumerisch geordnet in dem Dokument Vektor ):$n$$\rho$$rg$$X$$\vec{x}$

$$\rho_{A,B} = \frac{cov(rg(\vec{a}), rg(\vec{b}))}{\sigma_{rg_A} \sigma_{rg_B}}$$

Wobei die Kovarianz zwischen den Rängen der beiden Dokumente ist und die Standardabweichung der (möglicherweise abgeschnittenen) Ränge (mit Bindungen) von Dokument .$cov$$\sigma_{rg_X}$$rg$$X$

Kurz gesagt, Sie könnten diesen Ansatz als die Hälfte zwischen der Jaccard-Ähnlichkeit und der Cosine-Ähnlichkeit sehen. Insbesondere ist es (etwas mehr - siehe nächste Maßnahme) robust gegen Verteilungsunterschiede zwischen den Wortzahlen zwischen Dokumenten, wobei die allgemeine Worthäufigkeit weiterhin berücksichtigt wird. In den meisten Arbeiten scheint die Cosinus-Ähnlichkeit die Rangkorrektur von Spearman zu übertreffen - Sie sollten dies jedoch testen und mit TF-IDF und Spearman möglicherweise gute Ergebnisse erzielen, während Sie bei diesem Ansatz, wie gesagt, keine Längennormalisierung durchführen müssen Ihrer Dokumentvektoren.

4. (Pearson's testbasiert) Abstand$\chi^2$$\chi^2$

Bisher gehen alle unsere Ähnlichkeitsmaße von der Homogenität der Worthäufigkeiten aus, dh davon, dass die Varianzen unserer Wortzahlen bei allen Dokumenten einer Sammlung (einem "Korpus") gleich sind, was (hoffentlich intuitiv) nicht der Fall ist der Fall . Das heißt, Kilgarriff (1997) hatte zuvor gezeigt, dass das besser zum Vergleichen der Wortanzahl geeignet ist als unsere obigen Maße. Beachten Sie, dass Sie, wenn Sie der aktuellen Forschung folgen, für Korpusvergleiche heute (z. B. zur Funktionsauswahl ) wahrscheinlich den Bootstrap- Test anstelle von .$\chi^2$$\chi^2$

Der Vergleich von Kilgarriff kann genauso gut auf Dokumente angewendet werden (indem angenommen wird, dass es nur zwei "Klassen" gibt, Ihre beiden Dokumente und daher ), und aufgrund seiner Robustheit ist er möglicherweise der Ähnlichkeit vorzuziehen bisher gezeigte Maßnahmen. Beachten Sie, dass Sie bei diesem Ansatz einen Abstand erhalten. Um diesen Wert in eine Ähnlichkeit umzuwandeln , müssen Sie die Umkehrung vornehmen (dh je größer dieser Abstand ist, desto kleiner ist die Ähnlichkeit des Dokuments). Definieren wir die Anzahl aller Wörter in einem Dokument als und die Summe beider Dokumente und als . Dann a$\chi^2$$d.f. = 1$$X$$n_X = \sum x_i$$A$$B$$n = n_A + n_B$$\chi^2$Der statistische Abstand für zwei Dokumente (Dokumentvektoren) kann aus der Pearson- als:$\sum \frac{(O_i-E_i)^2}{E_i}$

$$\chi^2_{A,B} = n \left[ \sum{ \frac{a_i^2}{n_A(a_i+b_i)} } + \sum{ \frac{b_i^2}{n_B(a_i+b_i)} } \right] - n$$

Diese Berechnung ist jedoch rechenintensiver in der Ausführung, was wahrscheinlich erklärt, warum die meisten Ansätze an der Cosinus-Ähnlichkeit festhalten, und dies umso mehr, wenn Sie überprüfen können, ob Ihre Klassifizierungs- / Abruf- / Clustering-Ergebnisse nicht von diesem letzteren Entfernungsmaß profitieren. Wie das verlinkte Papier zeigt, scheint dieses Abstandsmaß die Cosinus-Ähnlichkeit mit der TF-IDF-Nachwägung nicht zu übertreffen. Beachten Sie jedoch, dass das verknüpfte Papier die Häufigkeitszählungen des "rohen" Terms verwendet, um dieses Abstandsmaß zu berechnen, und dieses mit der TF-IDF-neu gewichteten Cosinus-Ähnlichkeit vergleicht. Wie bereits erwähnt, ist es normalerweise eine gute Idee, zuerst die Dokumentvektoren auf ihre (dh Längen) zu normalisieren, um gute Ergebnisse zu , dh$X / n_X$ Zuerst (und Sie könnten sogar versuchen, vorher die TF-IDF-Neugewichtung von Dokumentvektoren anzuwenden). In diesem Fall vereinfacht sich die obige Formel (ein wenig) zu:

$$\chi^2_{A,B} = 2 \left[ \sum{ \frac{a_i^2}{a_i+b_i} } + \sum{ \frac{b_i^2}{a_i+b_i} } \right] - 2$$