Kosinusähnlichkeit
Im Datenanalyse, Kosinusähnlichkeit ist ein Maß für die Ähnlichkeit zwischen zwei Zahlensequenzen. Zum Definieren werden die Sequenzen als Vektoren in einem angesehen innerer Produktraumund die Kosinusähnlichkeit ist definiert als die Kosinus des Winkels zwischen ihnen, das heißt das, das Skalarprodukt der Vektoren geteilt durch das Produkt ihrer Länge. Daraus folgt, dass die Ähnlichkeit der Cosinus nicht von den Größen der Vektoren abhängt, sondern nur von ihrem Winkel. Die Kosinusähnlichkeit gehört immer zum Intervall Zum Beispiel zwei Proportionalvektoren eine Kosinusähnlichkeit von 1, zwei haben orthogonale Vektoren eine Ähnlichkeit von 0 und zwei haben Gegenteil Vektoren haben eine Ähnlichkeit von -1. Die Kosinusähnlichkeit wird insbesondere im positiven Raum verwendet, wo das Ergebnis ordentlich eingegrenzt ist .
Zum Beispiel in Informationsrückgewinnung und TextabbauJedem Wort wird eine andere Koordinate zugewiesen und ein Dokument wird durch den Vektor der Anzahl der Vorkommen jedes Wortes im Dokument dargestellt. Die Ähnlichkeit der Kosinus ergibt dann ein nützliches Maß dafür, wie ähnliche zwei Dokumente in Bezug auf ihren Gegenstand und unabhängig von der Länge der Dokumente wahrscheinlich sind.[1]
Die Technik wird auch verwendet, um den Kohäsion in Clustern im Bereich von zu messen Data Mining.[2]
Ein Vorteil der Ähnlichkeit der Cosinus ist seine geringe Komplexität, speziell für spärliche Vektoren: Es müssen nur die Koordinaten ungleich Null berücksichtigt werden.
Andere Namen für die Ähnlichkeit mit Cosinus sind einzuziehen Orchini -Ähnlichkeit und Tucker -Kongruenzkoeffizient; das OTSUKA -OCHII -Ähnlichkeit (Siehe unten) ist die Ähnlichkeit der Cosinus, die auf Binärdaten angewendet wird.
Definition
Der Cosinus von zwei Vektoren ungleich Null kann durch die Verwendung der Verwendung abgeleitet werden Euklidisches Punktprodukt Formel:
Zwei gegeben Vektoren von Attributen, A und B, die Kosinusähnlichkeit, cos (θ), wird mit a dargestellt Skalarprodukt und Größe wie
wo und sind Komponenten Vektor und beziehungsweise.
Die resultierende Ähnlichkeit reicht von –1, was genau entgegengesetzt ist, bis 1 genau gleich, wobei 0 angegeben ist Orthogonalität oder Dekorrelation, während die Zwischenwerte eine intermediäre Ähnlichkeit oder Unähnlichkeit anzeigen.
Zum Textübereinstimmung, die Attributvektoren A und B sind normalerweise die Begriffsfrequenz Vektoren der Dokumente. Kosinusähnlichkeit kann als Methode von gesehen werden Normalisierung Dokumentlänge während des Vergleichs.
Im Falle des InformationsrückgewinnungDie Kosinusähnlichkeit von zwei Dokumenten reicht von 0 bis 1, da die Begriffsfrequenzen nicht negativ sein können. Dies gilt bei der Verwendung tf -idf Gewichte. Der Winkel zwischen zwei Termfrequenzvektoren kann nicht mehr als 90 ° betragen.
Wenn die Attributvektoren durch Subtrahieren des Vektormittels normalisiert werden (z. B.,,, ) Die Maßnahme wird als zentrierte Cosinus -Ähnlichkeit bezeichnet und entspricht dem Pearson -Korrelationskoeffizient. Für ein Beispiel der Zentrierung,
Der Begriff Kosinusentfernung wird üblicherweise für die Ergänzung der Ähnlichkeit Cosinus im positiven Raum verwendet
Es ist jedoch wichtig zu beachten, dass der Kosinusabstand nicht richtig ist Entfernungsmetrik da es das nicht hat Dreiecksungleichung Eigentum - oder formeller, die Schwarz -Ungleichheit- und es verstößt gegen das Zufalls -Axiom. Eine Möglichkeit, dies zu sehen, ist zu Hinweis dass die Cosinus -Entfernung die Hälfte der ist quadratische euklidische Entfernung des Die Normalisierung der Vektoren und die quadratische euklidische Entfernung erfüllen auch die Dreiecksungleichheit nicht. Um die Eigenschaft der Dreieck -Ungleichheit zu reparieren und gleichzeitig dieselbe Ordnung beizubehalten Euklidische Entfernung. Alternativ kann die dreieckige Ungleichheit, die für Winkelabstände wirkt, direkt in Bezug auf den Cosinus ausgedrückt werden. sehen unter.
Winkelabstand und Ähnlichkeit
Der normalisierte Winkel, bezeichnet als Winkelabstand, zwischen zwei beliebigen Vektoren und ist eine formelle Entfernungsmetrik und kann aus der Kosinusähnlichkeit berechnet werden.[3] Die Ergänzung der Winkelabstandsmetrik kann dann verwendet werden, um zu definieren Winkel Ähnlichkeit Funktion zwischen 0 und 1, einschließlich.
Wenn die Vektorelemente positiv oder negativ sein können:
Oder wenn die Vektorelemente immer positiv sind:
Leider ist die Berechnung der Arcus cosinus -Funktion eher langsam, wodurch die Verwendung des Winkelabstands rechnerisch teurer wird als die Verwendung der häufigeren (aber nicht metrischen) Kosinusabstand.
L2-Normalisierte euklidische Entfernung
Ein weiterer wirksamer Stellvertreter für die Entfernung des Kosinus kann erhalten werden durch Normalisierung der Vektoren, gefolgt von der Anwendung von Normal Euklidische Entfernung. Unter Verwendung dieser Technik wird jeder Begriff in jedem Vektor zuerst durch die Größe des Vektors geteilt, wodurch ein Vektor der Einheitslänge erzielt wird. Dann ist klar, dass der euklidische Abstand über den Endpunkten zweier Vektoren eine ordnungsgemäße Metrik ist, die dieselbe Ordnung wie der Cosinus-Abstand (a monotonische Transformation der euklidischen Entfernung; sehen unter) Für einen Vergleich von Vektoren vermeidet und vermeidet außerdem die potenziell teuren trigonometrischen Operationen, die erforderlich sind, um eine ordnungsgemäße Metrik zu erzielen. Sobald die Normalisierung aufgetreten ist, kann der Vektorraum mit dem gesamten Bereich der Techniken verwendet werden, die jedem euklidischen Raum zur Verfügung stehen, insbesondere Standard Dimensionsreduzierung Techniken. Diese normalisierte Formentfernung wird häufig in vielen verwendet tiefes Lernen Algorithmen.
Otsuka -Ochiai -Koeffizient
In der Biologie gibt es ein ähnliches Konzept, das als OTSUKA -Ochiai -Koeffizient bekannt ist Yanosuke Otsuka (auch als ōtsuka, ootsuka oder otuka geschrieben,[4] japanisch: 大塚 弥之助)[5] und Akira Ochiai (japanisch: 落合 明),[6] Auch als Ochiai -Barkman bekannt[7] oder Ochiai -Koeffizient,[8] was dargestellt werden kann als:
Hier, und sind Sets, und ist die Anzahl der Elemente in . Wenn Sets als Bitvektoren dargestellt werden, ist der Otsuka -Ochiai -Koeffizient als der gleiche wie die Kosinusähnlichkeit.
In einem kürzlich erschienenen Buch,[9] Der Koeffizient wird bei einem anderen japanischen Forscher mit dem Familiennamen Otsuka falsch eingerichtet. Die Verwirrung tritt auf, weil Akira Ochiai 1957 den Koeffizienten nur Otsuka zuschreibt (kein Vorname erwähnt)[6] Indem Sie einen Artikel von Ikuso Hamai (zitierenjapanisch: 浜井 生三),[10] der wiederum den ursprünglichen Artikel von 1936 von Yanosuke Otsuka zitiert.[5]
Eigenschaften
Die bemerkenswerteste Eigenschaft der Kosinusähnlichkeit ist, dass sie eher einen relativen als einen absoluten Vergleich der einzelnen Vektordimensionen widerspiegelt. Für jede Konstante und Vektor , die Vektoren und sind maximal ähnlich. Die Maßnahme ist daher für Daten am besten geeignet, bei denen die Häufigkeit wichtiger ist als absolute Werte. Insbesondere die Begriffsfrequenz in Dokumenten. Jedoch neuere Metriken mit einer Grundlage in der Informationstheorie, wie z. Jensen -ShannonEs wurde gezeigt, dass SED und dreieckige Divergenz in einigen Kontexten eine verbesserte Semantik verbessert haben.[11]
Die Ähnlichkeit der Kosinus hängt mit dem Zusammenhang mit Euklidische Entfernung folgendermaßen. Bezeichnen die euklidische Distanz mit dem üblichen und beobachten Sie das
durch Erweiterung. Wann A und B sind auf Einheitenlänge normalisiert, Dieser Ausdruck ist also gleich zu
Kurz gesagt, der Cosinus -Abstand kann in Bezug auf die euklidische Entfernung als ausgedrückt werden
- .
Die euklidische Entfernung wird als die genannt Akkordentfernung (Weil es die Länge des Akkordkreises am Einheitskreis ist) und es ist der euklidische Abstand zwischen den Vektoren, die auf die Einheitsumme der quadratischen Werte in ihnen normalisiert wurden.
Nullverteilung: Für Daten, die sowohl negativ als auch positiv sein können, die Nullverteilung Für die Ähnlichkeit der Kosinus ist die Verteilung der Skalarprodukt von zwei unabhängigen zufälligen Einheitsvektoren. Diese Verteilung hat a bedeuten von null und a Varianz von (wo ist die Anzahl der Dimensionen), und obwohl die Verteilung zwischen -1 und +1 begrenzt ist, als wächst groß, die Verteilung wird von der zunehmend gut angesehen Normalverteilung.[12][13] Andere Datenarten wie z. Bitstreams, die nur die Werte 0 oder 1 annehmen, die Nullverteilung hat eine andere Form und kann einen Mittelwert ungleich Null haben.[14]
Dreiecksungleichheit für die Ähnlichkeit der Cosinus
Die Gewöhnlichen Dreiecksungleichung Für Winkel (d. H. Lichtbogenlängen auf einer Einheitshyperspkhere) gibt uns das
Weil die Kosinusfunktion als Winkel in abnimmt [0,, π] Radians nimmt zu, das Gefühl dieser Ungleichheiten wird umgekehrt, wenn wir den Cosinus jedes Wertes einnehmen:
Unter Verwendung der Kosinus -Additions- und Subtraktionsformeln können diese beiden Ungleichheiten in Bezug auf den ursprünglichen Cosinus geschrieben werden.
Diese Form der Dreieck -Ungleichheit kann verwendet werden, um die minimale und maximale Ähnlichkeit von zwei Objekten A und B zu begrenzen, wenn die Ähnlichkeiten zu einem Referenzobjekt C bereits bekannt sind. Dies wird beispielsweise in der metrischen Datenindexierung verwendet, wurde jedoch auch zur Beschleunigung der sphärischen Beschleunigung verwendet K-Means Clustering[15] Genauso wie die euklidische Dreiecksungleichheit wurde verwendet, um normale K-Mittel zu beschleunigen.
Weiches Cosinus -Maß
Ein weicher Cosinus oder eine ("weiche" Ähnlichkeit) zwischen zwei Vektoren berücksichtigt Ähnlichkeiten zwischen Merkmalspaaren.[16] Die traditionelle Cosinus -Ähnlichkeit berücksichtigt die Vektorraummodell (VSM) Merkmale als unabhängig oder völlig unterschiedlich, während das Soft Cosinus -Maß unter Berücksichtigung der Ähnlichkeit von Merkmalen in VSM vorschlägt, die das Konzept des Cosinus (und des weichen Cosinus) sowie der Idee der (weichen) Ähnlichkeit verallgemeinern.
Zum Beispiel im Bereich von Verarbeitung natürlicher Sprache (NLP) Die Ähnlichkeit zwischen den Funktionen ist ziemlich intuitiv. Merkmale wie Wörter, n-Gramsoder syntaktisch n-Grams[17] Kann ziemlich ähnlich sein, obwohl sie formell als unterschiedliche Merkmale im VSM angesehen werden. Zum Beispiel sind Wörter "Spielen" und "Spiel" unterschiedliche Wörter und somit unterschiedliche Punkte in VSM zugeordnet. Dennoch sind sie semantisch verwandt. Im Falle von n-Grams oder syntaktisch n-Grams, Levenshtein -Entfernung Kann angewendet werden (in der Tat kann auch Levenshtein -Entfernung auf Wörter angewendet werden).
Zur Berechnung des weichen Cosinus die Matrix s wird verwendet, um die Ähnlichkeit zwischen den Merkmalen anzuzeigen. Es kann durch Levenshtein -Entfernung berechnet werden, Wordnet Ähnlichkeit oder andere Ähnlichkeitsmaßnahmen. Dann multiplizieren wir uns einfach mit dieser Matrix.
Zwei gegeben N-Dimension Vektoren und Die Ähnlichkeit mit weicher Cosinus wird wie folgt berechnet:
wo sij = Ähnlichkeit (Funktioni, Besonderheitj).
Wenn es keine Ähnlichkeit zwischen den Funktionen gibt (sII = 1, sij = 0 zum i ≠ j) Die gegebene Gleichung entspricht der konventionellen Kosinus -Ähnlichkeitsformel.
Das Zeitkomplexität von dieser Maßnahme ist quadratisch, was es auf reale Aufgaben anwendbar macht. Beachten Sie, dass die Komplexität auf subquadratisch reduziert werden kann.[18] Eine effiziente Implementierung einer solchen Soft Cosinus -Ähnlichkeit ist in der enthalten Gensim Open Source -Bibliothek.
Siehe auch
- Sørensen -Dice -Koeffizient
- Hamming -Entfernung
- Korrelation
- Jaccard Index
- Simrank
- Informationsrückgewinnung
Verweise
- ^ Singhal, Amit (2001). "Modernes Informationsabruf: Ein kurzer Überblick". Bulletin des technischen Komitees der IEEE Computer Society für Data Engineering 24 (4): 35–43.
- ^ P.-N. Tan, M. Steinbach & V. Kumar, Einführung in den Data Mining, Addison-Wesley (2005), ISBN0-321-32136-7, Kapitel 8; Seite 500.
- ^ "Cosinusabstand, Kosinusähnlichkeit, Winkel -Kosinusabstand, Winkel -Kosinus -Ähnlichkeit". www.itl.nist.gov. Abgerufen 2020-07-11.
- ^ Omori, Masae (2004). "Geologische Idee von Yanosuke Otuka, der das Fundament der Neotektonik (Geowissenschaftler) baute". Erdkunde. 58 (4): 256–259. doi:10.15080/agcjchikyukagaku.58.4_256.
- ^ a b Otsuka, Yanosuke (1936). "Der faunale Charakter der japanischen pleistozänen Marine Mollusca als Beweis für das Klima, der während des Pleistozäns in Japan kälter wurde". Bulletin der biogeografischen Gesellschaft Japans. 6 (16): 165–170.
- ^ a b Ochiai, Akira (1957). "Zoogeografische Studien über die in Japan und seinen Nachbarnregionen-IIs gefundenen alleinigen Fische.". Bulletin der japanischen Gesellschaft der wissenschaftlichen Fischerei. 22 (9): 526–530. doi:10.2331/suisan.22.526.
- ^ Barkman, Jan J. (1958). Phytosokiologie und Ökologie von Kryptogamischen Epiphyten: einschließlich einer taxonomischen Untersuchung und Beschreibung ihrer Vegetationseinheiten in Europa. Asssen: Van Gorcum.
- ^ H. Charles Romesburg (1984). Clusteranalyse für Forscher. Belmont, Kalifornien: Lebensdauer Lernpublikationen. p. 149.
- ^ Howarth, Richard J. (2017). Wörterbuch der mathematischen Geowissenschaften: mit historischen Notizen. Cham, Schweiz: Springer. p. 421. doi:10.1007/978-3-319-57315-1. ISBN 978-3-319-57314-4.
- ^ Hamai, Ikuso (1955). "Schichtung der Gemeinschaft durch" Gemeinschaftskoeffizient "(Fortsetzung)". Japanisches Journal of Ecology. 5 (1): 41–45. doi:10.18960/Seitai.5.1_41.
- ^ Connor, Richard (2016). Eine Geschichte von vier Metriken. Ähnlichkeitssuche und Anwendungen. Tokio: Springer.
- ^ Spruill, Marcus C. (2007). "Asymptotische Verteilung von Koordinaten auf hochdimensionalen Kugeln". Elektronische Kommunikation in der Wahrscheinlichkeit. 12: 234–247. doi:10.1214/ecp.v12-1294.
- ^ "Verteilung von Punktprodukten zwischen zwei zufälligen Einheitenvektoren in der RD". Crossvalidated.
- ^ Graham L. Giller (2012). "Die statistischen Eigenschaften von zufälligen Bitstreams und die Stichprobenverteilung der Kosinusähnlichkeit". Giller Investments Research Notes Notes (20121024/1). doi:10.2139/ssrn.2167044.
- ^ Schubert, Erich; Lang, Andreas; Feher, Gloria (2021). Reyes, Nora; Connor, Richard; Kriege, Nils; Kazempour, Daniyal; Bartolini, Ilaria; Schubert, Erich; Chen, Jian-Jia (Hrsg.). "Beschleunigung der kugelförmigen K-Mittel". Ähnlichkeitssuche und Anwendungen. Vorlesungsnotizen in Informatik. Cham: Springer International Publishing: 217–231. Arxiv:2107.04074. doi:10.1007/978-3-030-89657-7_17. ISBN 978-3-030-89657-7.
- ^ Sidorov, Grigori; Gelbukh, Alexander; Gómez-Adorno, Helena; Pinto, David (29. September 2014). "Weiche Ähnlichkeit und Messung von Soft Cosinus: Ähnlichkeit der Merkmale im Vektorraummodell". Computación y Sistemas. 18 (3): 491–504. doi:10.13053/cys-18-3-2043. Abgerufen 7. Oktober 2014.
- ^ Sidorov, Grigori; Velasquez, Francisco; Stamatatos, Efstathios; Gelbukh, Alexander; Chanona-Hernández, Liliana (2013). Fortschritte in der Computational Intelligence. Vorlesungsnotizen in Informatik. Vol. 7630. LNAI 7630. S. 1–11. doi:10.1007/978-3-642-37798-3_1. ISBN 978-3-642-37798-3.
- ^ Novotný, Vít (2018). Implementierungsnotizen für das Soft Cosinus -Maß. Die 27. ACM Internationale Konferenz über Informations- und Wissensmanagement. Torun, Italien: Assoziation für Computermaschinen. S. 1639–1642. Arxiv:1808.09407. doi:10.1145/3269206.3269317. ISBN 978-1-4503-6014-2.