Vektorraummodell cosine tf-idf zum Auffinden ähnlicher Dokumente

Haben Sie Korpus von über Millionen Dokumenten

Für ein bestimmtes Dokument möchten Sie ähnliche Dokumente mit Cosinus wie im Vektorraummodell finden

$d_1 \cdot d_2 / ( ||d_1|| ||d_2|| )$

Alle tf wurden mit erhöhter Frequenz normalisiert, um eine Tendenz zu längeren Dokumenten wie in diesem tf-idf zu vermeiden :

$tf(t,d)=0.5+0.5\frac{f(t,d)}{\mathrm{max}\{f(t,d): t\in d\}}$

Habe alle vorberechnet Lassen Sie die Werte für den Nenner vorberechnen. Für ein gegebenes muss also mehr als 1 Million erzielt werden. Haben Sie einen Schwellenwert von 0,6 Kosinus für Ähnlichkeit $||d||$

$d1$ $d2$

Ich kann das für eine gegebene es gibt einen ziemlich engen Bereich von für Cosinus 0,6 Zum Beispiel in einer Suche nach ähnlichem für einen Cosinus von 0,6 und a von 7,7631 dann Bereich von 7,0867 bis 8,8339 Wo außerhalb der Kosinusschwelle 0,6 Bereich von bis 0,7223 bis 89,3395 $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$
Dies war mit Standard-tf-Dokumentnormalisierung.
Es wird eine Menge von das hat keine Chance, ein Cosinus 0.6 Match zu sein $||d_2||$

Zum Schluss die Frage:
Für ein Geben und Kosinus von> = 0,6, wie kann der Bereich von das hat eine Chance? Welche kann ich sicher beseitigen? $||d_1||$ $||d_2||$
$||d_2||$

Ich kenne auch die Anzahl der Terme in und wenn es einen Termzählbereich gibt. $d_1$ $d_2$

Durch Experimentieren
und scheint sicher zu sein, aber hoffentlich gibt es eine Reichweite, die sich als sicher erwiesen hat $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Erstellt einige Testfälle mit sehr eindeutigen Begriffen, einige nicht so eindeutig und einige häufig. Sicher genug, Sie können den einzigartigsten Begriff verwenden und diese Häufigkeit im Vergleich erhöhen. Der Zähler steigt (Punktprodukt) und || vergleicht || und wird einen Kosinus sehr nahe an 1 bekommen.

Art verwandt und NICHT die Frage.
Ich benutze auch die tf-idf, um Dokumente in Gruppen zu gruppieren. Der Kundenstamm, an den ich verkaufe, ist es gewohnt, in der Nähe von Dup-Gruppen zu sein. Dort verfolge ich einen ähnlichen Ansatz, indem ich die kleinste Anzahl von Begriffen betrachte und sie gegen die Anzahl der Begriffe bis zu 3x bewerte. Eine Laufzeit von 10 sieht also zwischen 10 und 30 aus (4-9 hatten bereits einen Schuss auf 10). Hier kann ich es mir leisten, einen zu verpassen, der in einem anderen aufgenommen wurde. Ich bin zu 10% fertig und die größte Quote ist 1,8.

Bitte identifizieren Sie die Fehler in dieser Analyse.
Wie in AN6U5 ausgeführt, gibt es einen Fehler in dieser Analyse.
Es ist kein Kosinus mehr, wenn das Dokument auf gewichtet normalisiert ist.
Und wie von Mathew herausgestellt, kann
ich auch nicht auf d1⋅d2≤d1⋅d1 schließen Ich hoffe immer noch auf etwas, das mir eine harte Bindung gibt, aber Leute, die dieses Zeug zu kennen scheinen, sagen mir nein,
ich möchte die Frage nicht ändern, also ignoriere dies einfach.
Ich werde eine Analyse durchführen und vielleicht eine separate Frage zur Dokumentnormalisierung
für stellen Der Zweck dieser Frage ist die Annahme, dass das Dokument auf raw tf normalisiert ist.
Entschuldigung, aber ich bin einfach nicht gut mit dem Markup, das zur Erstellung der Gleichungen verwendet wird.
Also in meiner Notation
|| d1 || = sqrt (Summe (w1 x w1))
d1 Punkt d2 = Summe (w1 X w2)
Angenommen, d1 ist das kürzere Dokument.
Der beste d1 Punkt d2, der erreicht werden kann, ist d1 Punkt d1.
Wenn d1 100 paul 20
heiratet und d2 100 paul 20 peter 1 heiratet.
Normalisiert
d1 ist heiraten 1 paul 1/5
d2 ist heiraten 1 paul 1/5 peter 1/100
Heiraten und paul haben eindeutig die gleiche ID in beiden Dokumenten.
Die bestmögliche d1 Punkt d2 ist d1 Punkt d1
Die maximal mögliche Übereinstimmung mit d1 ist d1
cos = d1 Punkt d1 / || d1 || || d2 ||
Quadrat beide Seiten
cos X cos = (d1 Punkt d1) X (d1 Punkt d1) / ((d1 Punkt d1) X (d2 Punkt d2)) cos X cos = (d1 Punkt d1) / (d2 Punkt d2)
nimm das Quadrat Wurzel beider Seiten
cos = || d1 || / || d2 ||
ist || d2 || nicht durch die cos begrenzt?
Wenn ich nur || d2 || benutze > = cos || d1 || und || d2 || <= || d1 || / cos Ich bekomme die Rechengeschwindigkeit, die ich brauche

text-mining similarity Paparazzo
quelle

Ihr Argument, das mit einer durch

bestimmten Grenze endet

funktioniert nicht, weil "Der beste d1 Punkt d2, der erreicht werden kann, ist d1 Punkt d1" falsch ist. Während

c o s = \frac{| | d_{1} | |}{| | d_{2} | |}

$\mathrm{cos}=\frac{||d_1||}{||d_2||}$

\frac{d_{1} \cdot d_{2}}{| | d_{1} | | | | d_{2} | |} \leq \frac{d_{1} \cdot d_{1}}{| | d_{1} | | | | d_{1} | |}

$\frac{d_1\cdot d_2}{||d_1||\ ||d_2||}\le\frac{d_1\cdot d_1}{||d_1||\ ||d_1||}$

d_{1} \cdot d_{2} \leq d_{1} \cdot d_{1}

$d_1\cdot d_2\le d_1\cdot d_1$

@ MatthewGraves Ich glaube, ich stimme dir zu. Nicht mein Fachwissen, aber ich hacke immer noch daran herum.

Paparazzo

Antworten:

Leider vereinfacht sich die Mathematik, um zu zeigen, dass Sie die Einschränkung des Kosinus-Ähnlichkeitsvergleichs der Vektoren anhand ihrer Länge nicht rigoros rechtfertigen können.

Der entscheidende Punkt ist, dass sich die Kosinus-Ähnlichkeitsmetrik basierend auf der Länge normalisiert, so dass nur die Einheitsvektoren berücksichtigt werden. Ich weiß, dass dies nicht unbedingt die Antwort ist, die Sie wollten, aber die Mathematik zeigt deutlich, dass die Kosinus-Ähnlichkeitsmetriken unabhängig von der Vektorlänge sind.

Schauen wir uns die Mathematik genauer an:

Sie wenden eine Kosinus-Ähnlichkeitsmetrik an und müssen diese Metrik größer als 0,6 sein:

s i m i l a r i t y = \cos (θ) = \frac{A \cdot B}{| | A | | | | B | |} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||}\geq0.6$

Die skalaren Längen auf der Unterseite können jedoch auf die obigen Kreuzprodukte verteilt werden (Verteilungseigenschaft):

\frac{A \cdot B}{| | A | | | | B | |} = \frac{A}{| | A | |} \cdot \frac{B}{| | B | |} = \hat{A} \cdot \hat{B}

$\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||} = \frac{\mathbf{A}}{||A||}\cdot\frac{\mathbf{B}}{||B||}=\hat{\mathbf{A}}\cdot\hat{\mathbf{B}}$

$\hat{\mathbf{A}}$ $\hat{\mathbf{B}}$ $\mathbf{A}$ $\mathbf{B}$

Dafür:

s i m i l a r i t y = \cos (θ) = \frac{d 1 \cdot d 2}{| | d 1 | | | | d 2 | |} = \hat{d 1} \cdot \hat{d 2} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{d1}\cdot\mathbf{d2}}{||d1|| ||d2||}=\hat{\mathbf{d1}}\cdot\hat{\mathbf{d2}}\geq0.6$

hängt nur von der Ausrichtung der Vektoren ab und nicht von ihrer Größe (dh Länge).

Versöhnen Sie dies mit dem, was Sie tun:

$\geq0.6$ $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Sie können vielleicht das, was Sie getan haben, mit Entfernungsmetriken in Einklang bringen, indem Sie auch die euklidische Entfernung berücksichtigen. Während die Kosinusähnlichkeit nur einen Wert zwischen -1 und 1 basierend auf dem Winkel zwischen den beiden Vektoren zurückgibt, geben die euklidischen Abstände Werte zurück, die von den Längen der beiden Vektoren abhängen. In gewissem Sinne kombinieren Sie Aspekte der euklidischen Distanz mit Kosinusähnlichkeit.

Es ist ziemlich sinnvoll zu verlangen, dass die relativen Längen innerhalb von 25% voneinander liegen, in dem Sinne, dass dies einen Aspekt der euklidischen Distanz kombiniert, um gruppierte Überdachungen zu erzeugen, die die Rechenzeit verkürzen, und dann kann die längenunabhängige Kosinusähnlichkeit als verwendet werden die endgültige Determinante.

Beachten Sie, dass 1 / .8 = 1,25 ist, also ist d2> =. 8d1 eine strengere Einschränkung als d2 <= d1 / .8. Ich schlage vor, d2> =. 75d1 und d2 <= 1.25d1 zu verwenden, da dies symmetrisch ist.

Hoffe das hilft!

AN6U5
quelle

Ich denke, dies nutzt nicht die Tatsache, dass Vektorlängen aufgrund des von ihm verwendeten tf-Normalisierungsschemas hauptsächlich von den gemeinsamen IDF-Gewichten stammen. Wenn ein Dokument eine sehr niedrige Norm hat, bedeutet dies, dass es keine seltenen Wörter enthält (oder diese mit einer sehr geringen Bruchhäufigkeit enthält), was bedeutet, dass es als ähnlich wie ein Dokument ausgeschlossen werden kann, das nur seltene Wörter enthält. Aber wie eng diese Einschränkung im Allgemeinen ist, scheint mir unklar. Es ist wahrscheinlich der Fall, dass theoretische Grenzen im Vergleich zu beobachteten empirischen Grenzen sehr weit sind.

Matthew Graves

@ Matthew Graves, alles was ich sage ist, dass die Kosinusähnlichkeit unabhängig von der Vektorlänge ist. Er fragt, wie sich Unterschiede in der Vektorlänge auf die resultierende Kosinusähnlichkeit auswirken können, und die Antwort lautet: Sie können nicht.

AN6U5

Die empirische Korrelation kann nicht ignoriert werden. Es gibt eine Möglichkeit, die Zufälligkeit des Korpus zu korrelieren, wenn auch nur statistisch. Ich habe nicht genug Repräsentanten auf dieser Seite, um mich zu registrieren.

Paparazzo

Hier stimme ich nicht zu. Es wird nicht basierend auf der Länge normalisiert. Es normalisiert sich auf den häufigsten Begriff. Ein längeres Dokument kann nur verdünnt werden. Ich bin bereit anzupassen, wie die Normalisierung durchgeführt wird, um eine Grenze zu erhalten, die ich unterstützen kann.

Paparazzo

Vielen Dank, dass Sie Ihre Frage geändert haben. Es verdeutlicht besser, was Sie erreichen möchten. Beachten Sie, dass Ihre modifizierte Normalisierung dies eigentlich nicht zu einer Kosinusähnlichkeit macht, da dies streng definiert ist. Ich würde ein paar zusätzliche Änderungen vorschlagen, um dies zu formulieren. Pass auf dich auf und viel Glück.

AN6U5

$||d_i||$ $||d_i||$ $||d_i||$

Um einige Algebra durchzuarbeiten, möchte ich einige weitere Begriffe einführen (und einige in kürzere umbenennen):

$d_1$ $[t_1, t_2, ...]$ $[w_1, w_2, ...]$ $[d_1, d_2, ...]$ $0.5\le t_i\le 1$ $0\le w_i\le 6$ $D_1=||d_1||$

$d_1$ $x$ $d_1+x$ $X$

$X=\sqrt{\sum_i w_i^2 (t_i+x_i)^2}$

$0.6D_1X\le \sum_i w_i^2t_i(t_i+x_i)$

$0.5\le t_i+x_i \le 1$

$x$ $x_i=0\ \forall i$ $d_i+x_i=1$

$x$ $X^2$ $X$ $X>0$ $X$ $-X$ $P$ $P$

$0\ge 0.36D_1^2\sum_i w_i^2 (t_i+x_i)^2-\sum_{i,j}w_i^4t_it_j(t_i+x_i)(t_j+x_j)$

$0\ge x^TPx+q^Tx+r$ $P_{i,j}=0.36D_1^2-w_i^2t_it_j$ $i=j$ $-w_i^2t_it_j$

$P$ $d_1$ $X$

$X$ $w$ $x$ $X$

Matthew Graves
quelle

Ich stimme || d || nicht zu mit scheint als Seltenheitsmaßnahme zu dienen. Es ist normalisiert. "Mary hatte ein kleines Lamm" wird ein kleineres || haben als "Marry hatte ein weißes kleines Lamm". Und "oddxxA oddxxB oddxxC" hat ein kleineres || als "oddxxA oddxxB oddxxC oddxxD" in ungefähr dem gleichen Verhältnis. Und diese beiden Vergleiche werden ähnliche cos haben.

Paparazzo

@Frisbee, bist du dir bei diesem Vergleich sicher? Angenommen, die idfs sind 0 für 'a', 0,5 für 'had' und 'Mary', 1 für 'little' und 'white' und 2 für 'lamm', dann berechne ich 2,4 für "Mary had a little lamm" und 2,55 für "Mary hatte ein weißes kleines Lamm", aber 1,83 für "Eine Mary hatte ein kleines Lamm". Das heißt, die einzige Möglichkeit, die Norm zu verringern, besteht darin, die Häufigkeit des häufigsten Begriffs zu erhöhen und keine neuen Wörter hinzuzufügen. Oder verwenden wir nicht die gleiche Formel?

Matthew Graves

Ich dachte, Sie haben das Dokument auf der gewichteten (mit IDF) und nicht auf der Rohfrequenz normalisiert. Das würde die Dinge ändern. Es ist für mich sinnvoller, sich auf gewichtet zu normalisieren. Ein Dokument erheblich ändern || indem man 'a' zum häufigsten Begriff macht.

Paparazzo

d_{t} = w_{t} (0.5 + 0.5 \frac{w_{t} f (t, d)}{m a x {w_{t} f (t, d) : t \in d}})

$d_t=w_t(0.5+0.5\frac{w_tf(t,d)}{\mathrm{max}\{w_tf(t,d): t\in d\}})$

w_{t} = l o g \frac{N}{| {d \in D : t \in d} |}

$w_t=\mathrm{log}\frac{N}{|\{d\in D: t\in d\}|}$

d

$d$

d_{i}

$d_i$

d

$d$

Ich poste eine Antwort, aber natürlich werde ich den Bonus an jemand anderen vergeben

Ich denke, es gibt einen maximalen Zähler, wenn das Dokument tf normalisiert ist

d1⋅d2 / (|| d1 |||| d2 ||)

Angenommen, d1 hat gleiche oder weniger Terme (oder nimm einfach das d mit weniger Termen).
Die maximal mögliche normalisierte tf ist 1.
Die maximal mögliche Zählersumme (tf1, i * idf, i * 1 * idf, i)

|| d2 || = Summe (tf1, i * idf, i * 1 * idf, i) / || d1 || / .6

Zumindest arbeite ich daran, aber es gibt eindeutig ein Minimum.
Wenn Sie übereinstimmen, haben Sie || d ||

Paparazzo
quelle