Kosinusähnlichkeit

In der Datenanalyse ist die Kosinusähnlichkeit ein Maß für die Ähnlichkeit zweier Vektoren ungleich null, die in einem Skalarproduktraum definiert sind . Die Kosinusähnlichkeit entspricht dem Kosinus des Winkels zwischen den Vektoren; das heißt, sie ist das Skalarprodukt der Vektoren, dividiert durch das Produkt ihrer Längen. Daraus folgt, dass die Kosinusähnlichkeit nicht von den Längen der Vektoren abhängt, sondern nur von ihrem Winkel. Die Kosinusähnlichkeit liegt stets im Intervall [0, 1]. Beispielsweise haben zwei proportionale Vektoren eine Kosinusähnlichkeit von +1, zwei orthogonale Vektoren eine Ähnlichkeit von 0 und zwei entgegengesetzte Vektoren eine Ähnlichkeit von −1. In manchen Kontexten dürfen die Komponentenwerte der Vektoren nicht negativ sein; in diesem Fall ist die Kosinusähnlichkeit beschränkt . ${\displaystyle [-1,+1].}$${\displaystyle [0,1]}$

Beispielsweise wird in der Informationswiedergewinnung und im Text-Mining jedem Wort eine eindeutige Koordinate zugewiesen, und ein Dokument wird durch den Vektor der Häufigkeit jedes Wortes im Dokument repräsentiert. Die Kosinusähnlichkeit liefert dann ein nützliches Maß dafür, wie ähnlich zwei Dokumente hinsichtlich ihres Inhalts und unabhängig von ihrer Länge wahrscheinlich sind. ^{[ 1 ]}

Die Technik wird auch zur Messung des Zusammenhalts innerhalb von Clustern im Bereich Data Mining eingesetzt . ^{[ 2 ]}

Ein Vorteil der Kosinusähnlichkeit ist ihre geringe Komplexität , insbesondere bei dünnbesetzten Vektoren : Es müssen nur die von Null verschiedenen Koordinaten berücksichtigt werden.

Andere Bezeichnungen für die Kosinusähnlichkeit sind Orchini-Ähnlichkeit und Tucker-Kongruenzkoeffizient ; die Otsuka-Ochiai-Ähnlichkeit (siehe unten) ist die auf Binärdaten angewandte Kosinusähnlichkeit . ^{[ 3 ]}

Der Kosinus zweier von Null verschiedener Vektoren kann mithilfe der euklidischen Skalarproduktformel hergeleitet werden :

${\displaystyle \mathbf {A} \cdot \mathbf {B} =\left\|\mathbf {A} \right\|\left\|\mathbf {B} \right\|\cos \theta }$

Gegeben seien zwei n- dimensionale Attributvektoren A und B. Die Kosinusähnlichkeit, cos(θ) , wird mithilfe eines Skalarprodukts und des Betrags wie folgt dargestellt :

${\displaystyle {\text{cosine similarity}}=S_{C}(A,B):=\cos(\theta )={\mathbf {A} \cdot \mathbf {B} \over \|\mathbf {A} \|\|\mathbf {B} \|}={\frac {\sum \limits _{i=1}^{n}{A_{i}B_{i}}}{{\sqrt {\sum \limits _{i=1}^{n}{A_{i}^{2}}}}\cdot {\sqrt {\sum \limits _{i=1}^{n}{B_{i}^{2}}}}}},}$

wobei und die -ten Komponenten der Vektoren und sind . ${\displaystyle A_{i}}$${\displaystyle B_{i}}$${\displaystyle i}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {B} }$

Die resultierende Ähnlichkeit reicht von −1 (genau gegensätzlich) bis +1 (genau gleich), wobei 0 Orthogonalität (keine Korrelation ) anzeigt, während Zwischenwerte eine mittlere Ähnlichkeit oder Unähnlichkeit anzeigen.

Beim Textvergleich sind die Attributvektoren A und B üblicherweise die Termfrequenzvektoren der Dokumente. Die Kosinusähnlichkeit kann als Methode zur Normalisierung der Dokumentlänge beim Vergleich betrachtet werden. Im Bereich des Information Retrieval liegt die Kosinusähnlichkeit zweier Dokumente zwischen 0 und 1 , da Termfrequenzen nicht negativ sein können. Dies gilt auch bei Verwendung von TF-IDF -Gewichten. Der Winkel zwischen zwei Termfrequenzvektoren kann nicht größer als 90° sein. ${\displaystyle 0\to 1}$

Werden die Attributvektoren durch Subtraktion ihrer Mittelwerte normalisiert (z. B. durch ), spricht man von zentrierter Kosinusähnlichkeit; sie entspricht dem Pearson-Korrelationskoeffizienten . Ein Beispiel für die Zentrierung: ${\displaystyle A-{\bar {A}}}$

${\displaystyle {\text{if}}\,A=[A_{1},A_{2}]^{T},{\text{ then }}{\bar {A}}=\left[{\frac {(A_{1}+A_{2})}{2}},{\frac {(A_{1}+A_{2})}{2}}\right]^{T},}$

${\displaystyle {\text{ so }}A-{\bar {A}}=\left[{\frac {(A_{1}-A_{2})}{2}},{\frac {(-A_{1}+A_{2})}{2}}\right]^{T}.}$

Wenn der Abstand zwischen zwei Einheitsvektoren als die Länge ihrer Vektordifferenz definiert ist, dann $${\displaystyle \operatorname {dist} (\mathbf {A} ,\mathbf {B} )={\sqrt {(\mathbf {A} -\mathbf {B} )\cdot (\mathbf {A} -\mathbf {B} )}}={\sqrt {\mathbf {A} \cdot \mathbf {A} -2(\mathbf {A} \cdot \mathbf {B} )+\mathbf {B} \cdot \mathbf {B} }}={\sqrt {2(1-S_{C}(\mathbf {A} ,\mathbf {B} ))}}\,.}$$

Dennoch wird der Kosinusabstand ^{[ 4 ]} oft ohne die Quadratwurzel oder den Faktor 2 definiert:

${\displaystyle {\text{cosine distance}}=D_{C}(A,B):=1-S_{C}(A,B)\,.}$

Da die Kosinusdistanz proportional zum Quadrat der euklidischen Distanz ist, stellt sie keine echte Distanzmetrik dar; sie erfüllt weder die Dreiecksungleichung – noch, formaler, die Schwarzsche Ungleichung – und verletzt das Koinzidenzaxiom. Um die Dreiecksungleichung wiederherzustellen und gleichzeitig die Reihenfolge beizubehalten, kann man zur euklidischen Distanz oder Winkeldistanz θ = arccos( SC ( _A , B )) übergehen. Alternativ lässt sich die Dreiecksungleichung, die für Winkeldistanzen gilt , direkt mithilfe der Kosinuswerte ausdrücken; siehe unten . ${\textstyle {\sqrt {2(1-S_{C}(A,B))}}}$

Der normalisierte Winkel, auch Winkelabstand genannt , zwischen zwei beliebigen Vektoren ist ein formales Distanzmaß und kann aus der Kosinusähnlichkeit berechnet werden. ^{[ 5 ]} Das Komplement des Winkelabstandsmaßes kann dann verwendet werden, um eine Winkelähnlichkeitsfunktion zu definieren , die auf den Bereich zwischen 0 und 1 (einschließlich) beschränkt ist. ${\displaystyle A}$${\displaystyle B}$

Wenn die Vektorelemente positiv oder negativ sein können:

${\displaystyle {\text{angular distance}}=D_{\theta }:={\frac {\arccos({\text{cosine similarity}})}{\pi }}={\frac {\theta }{\pi }}}$

${\displaystyle {\text{angular similarity}}=S_{\theta }:=1-{\text{angular distance}}=1-{\frac {\theta }{\pi }}}$

Oder, falls die Vektorelemente immer positiv sind:

${\displaystyle {\text{angular distance}}=D_{\theta }:={\frac {2\cdot \arccos({\text{cosine similarity}})}{\pi }}={\frac {2\theta }{\pi }}}$

${\displaystyle {\text{angular similarity}}=S_{\theta }:=1-{\text{angular distance}}=1-{\frac {2\theta }{\pi }}}$

Leider ist die Berechnung der inversen Kosinusfunktion ( arccos ) langsam, weshalb die Verwendung des Winkelabstands rechenaufwändiger ist als die Verwendung des gebräuchlicheren (aber nicht metrischen) Kosinusabstands oben.

Ein weiterer effektiver Näherungswert für die Kosinusdistanz lässt sich durch Normalisierung der Vektoren und anschließende Anwendung der euklidischen Distanz gewinnen . Dabei wird jedes Element jedes Vektors zunächst durch seine Länge dividiert, wodurch ein Vektor der Länge 1 entsteht. Die euklidische Distanz zwischen den Endpunkten zweier Vektoren ist dann eine geeignete Metrik, die dieselbe Ordnung wie die Kosinusdistanz (eine monotone Transformation der euklidischen Distanz; siehe unten ) für jeden Vektorvergleich liefert und zudem die potenziell aufwendigen trigonometrischen Operationen vermeidet, die zur Berechnung einer geeigneten Metrik erforderlich wären. Nach der Normalisierung kann der Vektorraum mit allen für euklidische Räume verfügbaren Techniken genutzt werden, insbesondere mit Standardverfahren zur Dimensionsreduktion . Diese normalisierte Distanzform wird häufig in Deep-Learning -Algorithmen verwendet. ${\displaystyle L_{2}}$

In der Biologie gibt es ein ähnliches Konzept, das als Otsuka-Ochiai-Koeffizient bekannt ist und nach Yanosuke Otsuka (auch als Ōtsuka, Ootsuka oder Otuka geschrieben, ^{[ 6 ]} Japanisch :大塚 弥之助) ^{[ 7 ]} und Akira Ochiai ( Japanisch :落合 明), ^{[ 8 ]} , auch bekannt als Ochiai-Barkman ^{[ 9 ]} oder Ochiai-Koeffizient ^{[ 10 ]} , der dargestellt werden kann als:

${\displaystyle K={\frac {|A\cap B|}{\sqrt {|A|\times |B|}}}}$

Hierbei sind und Mengen , und ist die Anzahl der Elemente in . Werden Mengen als Bitvektoren dargestellt, so entspricht der Otsuka-Ochiai-Koeffizient der Kosinusähnlichkeit. Er ist identisch mit dem von Godfrey Thomson eingeführten Score . ^{[ 11 ]}${\displaystyle A}$${\displaystyle B}$${\displaystyle |A|}$${\displaystyle A}$

In einem kürzlich erschienenen Buch ^{[ 12 ]} wird der Koeffizient fälschlicherweise einem anderen japanischen Forscher mit dem Familiennamen Otsuka zugeschrieben. Die Verwirrung entsteht dadurch, dass Akira Ochiai 1957 den Koeffizienten ausschließlich Otsuka (ohne Angabe des Vornamens) ^{[ 8 ]} zuschreibt und dabei einen Artikel von Ikuso Hamai ( japanisch :浜井 生三) ^{[ 13 ]} zitiert , der wiederum den Originalartikel von Yanosuke Otsuka aus dem Jahr 1936 ^{[ 7 ]} anführt.

Die bemerkenswerteste Eigenschaft der Kosinusähnlichkeit ist, dass sie einen relativen, nicht absoluten Vergleich der einzelnen Vektordimensionen widerspiegelt. Für jede positive Konstante und jeden Vektor sind die Vektoren und maximal ähnlich. Das Maß eignet sich daher am besten für Daten, bei denen die Häufigkeit wichtiger ist als absolute Werte, insbesondere die Termfrequenz in Dokumenten. Neuere Metriken mit informationstheoretischer Grundlage, wie Jensen-Shannon , SED und die Dreiecksdivergenz, haben jedoch in einigen Kontexten eine verbesserte Semantik gezeigt. ^{[ 14 ]}${\displaystyle a}$${\displaystyle V}$${\displaystyle V}$${\displaystyle aV}$

Die Kosinusähnlichkeit steht in folgendem Zusammenhang mit der euklidischen Distanz . Man bezeichnet die euklidische Distanz mit dem üblichen und stellt fest, dass ${\displaystyle \|A-B\|}$

${\displaystyle \|A-B\|^{2}=(A-B)\cdot (A-B)=\|A\|^{2}+\|B\|^{2}-2(A\cdot B)\ }$( Polarisationsidentität )

durch Expansion . Wenn A und B auf Einheitslänge normiert sind, ist dieser Ausdruck gleich ${\displaystyle \|A\|^{2}=\|B\|^{2}=1}$

${\displaystyle 2(1-\cos(A,B)).}$

Kurz gesagt, lässt sich die Kosinusdistanz durch die euklidische Distanz ausdrücken als

${\displaystyle D_{C}(A,B)={\frac {\|A-B\|^{2}}{2}}\quad \mathrm {when} \quad \|A\|^{2}=\|B\|^{2}=1}$Die

Die euklidische Distanz wird auch Sehnendistanz genannt (weil sie die Länge der Sehne auf dem Einheitskreis ist) und sie ist die euklidische Distanz zwischen den Vektoren, die auf die Summe der quadrierten Werte in ihnen normiert wurden.

Nullverteilung: Für Daten, die sowohl negative als auch positive Werte annehmen können, entspricht die Nullverteilung der Kosinusähnlichkeit der Verteilung des Skalarprodukts zweier unabhängiger, zufälliger Einheitsvektoren . Diese Verteilung hat einen Mittelwert von null und eine Varianz von (wobei die Anzahl der Dimensionen ist). Obwohl die Verteilung auf den Bereich zwischen −1 und +1 beschränkt ist, wird sie mit zunehmendem immer besser durch die Normalverteilung approximiert . ^{[ 15 ] [ 16 ]} Bei anderen Datentypen wie Bitströmen , die nur die Werte 0 oder 1 annehmen, hat die Nullverteilung eine andere Form und kann einen von null verschiedenen Mittelwert aufweisen. ^{[ 17 ]}${\displaystyle 1/n}$${\displaystyle n}$${\displaystyle n}$

Die gewöhnliche Dreiecksungleichung für Winkel (d. h. Bogenlängen auf einer Einheitshypersphäre) liefert uns Folgendes:

${\displaystyle |~\angle {AC}-\angle {CB}~|\leq ~\angle {AB}~\leq ~\angle {AC}~+~\angle {CB}~.}$

Da die Kosinusfunktion mit zunehmendem Winkel im Intervall [0, π ] Radiant abnimmt, kehrt sich die Bedeutung dieser Ungleichungen um, wenn wir den Kosinus jedes Wertes bilden:

${\displaystyle \cos(\angle {AC}-\angle {CB})\geq \cos(\angle {AB})\geq \cos(\angle {AC}+\angle {CB}).}$

Mithilfe der Additions- und Subtraktionsformeln für Kosinusfunktionen lassen sich diese beiden Ungleichungen in Abhängigkeit von den ursprünglichen Kosinusfunktionen ausdrücken.

${\displaystyle \cos(A,C)\cdot \cos(C,B)+{\sqrt {\left(1-\cos(A,C)^{2}\right)\cdot \left(1-\cos(C,B)^{2}\right)}}\geq \cos(A,B),}$

${\displaystyle \cos(A,B)\geq \cos(A,C)\cdot \cos(C,B)-{\sqrt {\left(1-\cos(A,C)^{2}\right)\cdot \left(1-\cos(C,B)^{2}\right)}}.}$

Diese Form der Dreiecksungleichung kann verwendet werden, um die minimale und maximale Ähnlichkeit zweier Objekte A und B zu beschränken, wenn die Ähnlichkeiten zu einem Referenzobjekt C bereits bekannt sind. Sie wird beispielsweise bei der metrischen Datenindizierung eingesetzt, wurde aber auch zur Beschleunigung des sphärischen k-Means-Clusterings verwendet ^{[ 18 ]} , analog zur Verwendung der euklidischen Dreiecksungleichung zur Beschleunigung des regulären k-Means-Clusterings.

Eine weiche Kosinusähnlichkeit (oder „weiche“ Ähnlichkeit) zwischen zwei Vektoren berücksichtigt die Ähnlichkeiten zwischen Merkmalspaaren. ^{[ 19 ]} Die traditionelle Kosinusähnlichkeit betrachtet die Merkmale des Vektorraummodells (VSM) als unabhängig oder völlig unterschiedlich, während das weiche Kosinusmaß die Ähnlichkeit von Merkmalen im VSM berücksichtigt. Dies trägt dazu bei, das Konzept des Kosinus (und des weichen Kosinus) sowie die Idee der (weichen) Ähnlichkeit zu verallgemeinern.

Im Bereich der natürlichen Sprachverarbeitung (NLP) ist die Ähnlichkeit von Merkmalen beispielsweise recht intuitiv. Merkmale wie Wörter, n -Gramme oder syntaktische n- Gramme ^{[ 20 ]} können sich sehr ähnlich sein, obwohl sie formal im VSM als unterschiedliche Merkmale betrachtet werden. So sind beispielsweise die Wörter „spielen“ und „Spiel“ unterschiedliche Wörter und werden daher im VSM auf unterschiedliche Punkte abgebildet; dennoch sind sie semantisch verwandt. Im Fall von n- Grammen oder syntaktischen n- Grammen kann die Levenshtein-Distanz angewendet werden (tatsächlich lässt sich die Levenshtein-Distanz auch auf Wörter anwenden).

Zur Berechnung des Soft-Cosine-Effekts wird die Matrix s verwendet, um die Ähnlichkeit zwischen Merkmalen anzugeben. Diese kann mithilfe der Levenshtein-Distanz, der WordNet- Ähnlichkeit oder anderer Ähnlichkeitsmaße berechnet werden . Anschließend wird einfach mit dieser Matrix multipliziert.

Gegeben seien zwei N- dimensionale Vektoren und . Die weiche Kosinusähnlichkeit wird wie folgt berechnet: ${\displaystyle a}$${\displaystyle b}$

${\displaystyle {\begin{aligned}\operatorname {soft\_cosine} _{1}(a,b)={\frac {\sum \nolimits _{i,j}^{N}s_{ij}a_{i}b_{j}}{{\sqrt {\sum \nolimits _{i,j}^{N}s_{ij}a_{i}a_{j}}}{\sqrt {\sum \nolimits _{i,j}^{N}s_{ij}b_{i}b_{j}}}}},\end{aligned}}}$

wobei s _ij = similarity(feature _i , feature _j ) .

Wenn keine Ähnlichkeit zwischen den Merkmalen besteht ( s _ii = 1 , s _ij = 0 für i ≠ j ), ist die gegebene Gleichung äquivalent zur herkömmlichen Kosinusähnlichkeitsformel.

Die Zeitkomplexität dieses Verfahrens ist quadratisch, wodurch es sich für reale Aufgaben eignet. Die Komplexität lässt sich auf subquadratisch reduzieren. ^{[ 21 ]} Eine effiziente Implementierung dieser weichen Kosinusähnlichkeit ist in der Open-Source-Bibliothek Gensim enthalten .

• Dice-Sørensen-Koeffizient
• Hamming-Distanz
• Korrelation
• Jaccard-Index
• SimRank
• Informationsabruf