Kann jemand auf sehr einfache, grafische Weise ein Beispiel für Kosinusähnlichkeit geben?

201

Cosinus-Ähnlichkeitsartikel auf Wikipedia

Können Sie die Vektoren hier (in einer Liste oder so) anzeigen und dann rechnen und uns zeigen lassen, wie es funktioniert?

Ich bin ein Anfänger.

TIMEX
quelle
1
Versuchen Sie, eine Kopie von Geometry and Meaning by Widdows ( press.uchicago.edu/presssite/… ) in die Hand zu nehmen . Ich habe sie vor einiger Zeit gelesen und wünschte, ich hätte sie vor einigen Jahren, einen großartigen Einführungstext.
Nathan Howell

Antworten:

463

Hier sind zwei sehr kurze Texte zum Vergleich:

  1. Julie loves me more than Linda loves me

  2. Jane likes me more than Julie loves me

Wir wollen wissen, wie ähnlich diese Texte sind, rein in Bezug auf die Anzahl der Wörter (und das Ignorieren der Wortreihenfolge). Wir beginnen mit einer Liste der Wörter aus beiden Texten:

me Julie loves Linda than more likes Jane

Jetzt zählen wir, wie oft jedes dieser Wörter in jedem Text vorkommt:

   me   2   2
 Jane   0   1
Julie   1   1
Linda   1   0
likes   0   1
loves   2   1
 more   1   1
 than   1   1

Die Wörter selbst interessieren uns allerdings nicht. Wir interessieren uns nur für diese beiden vertikalen Zählvektoren. Zum Beispiel gibt es in jedem Text zwei Instanzen von 'Ich'. Wir werden entscheiden, wie nahe diese beiden Texte beieinander liegen, indem wir eine Funktion dieser beiden Vektoren berechnen, nämlich den Kosinus des Winkels zwischen ihnen.

Die zwei Vektoren sind wieder:

a: [2, 0, 1, 1, 0, 2, 1, 1]

b: [2, 1, 1, 0, 1, 1, 1, 1]

Der Kosinus des Winkels zwischen ihnen beträgt ungefähr 0,822.

Diese Vektoren sind 8-dimensional. Eine Tugend der Verwendung von Kosinusähnlichkeit besteht eindeutig darin, dass eine Frage, die über die menschliche Fähigkeit zur Visualisierung hinausgeht, in eine Frage umgewandelt wird, die möglich ist. In diesem Fall können Sie sich dies als einen Winkel von ungefähr 35 Grad vorstellen, der ein gewisser Abstand von Null oder eine perfekte Übereinstimmung ist.

Bill Bell
quelle
12
Genau das habe ich gesucht. Genau. Wird dies als die einfachste Form des "Vektorraummodells" angesehen?
TIMEX
2
Ich bin wirklich froh, dass dir das nützlich war, Alex. Entschuldigen Sie die Verzögerung der Antwort. Ich habe StackOverflow schon eine Weile nicht mehr besucht. Eigentlich ist dies ein Beispiel für einen "inneren Produktraum". Es gibt eine grundlegende Diskussion auf Wikipedia.
Bill Bell
1
Gibt es eine Möglichkeit, die Dokumentlänge zu normalisieren?
sinθ
1
Sie müssen die Längennormalisierung verwenden und vorher versuchen, die logarithmische Frequenzgewichtung für alle Termvektoren zu verwenden. Wenn Sie bereits mit normalisierten Vektoren zu tun haben, dann ist es das Punktprodukt von AB
Ali Gajani
4
Detaillierteres Beispiel mit Verwendung von Längennormalisierung
Mike B.
121

Ich vermute, Sie sind mehr daran interessiert, einen Einblick in das " Warum" zu bekommen " der Kosinusähnlichkeit zu erhalten (warum sie einen guten Hinweis auf Ähnlichkeit liefert) als in das " Wie " der Berechnung (die für die Berechnung verwendeten spezifischen Operationen). Wenn Sie sich für Letzteres interessieren, lesen Sie die von Daniel in diesem Beitrag angegebene Referenz sowie eine zugehörige SO-Frage .

Um sowohl das Wie als auch das Warum zu erklären, ist es zunächst sinnvoll, das Problem zu vereinfachen und nur in zwei Dimensionen zu arbeiten. Sobald Sie dies in 2D erhalten haben, ist es einfacher, es in drei Dimensionen zu betrachten, und es ist natürlich schwieriger, es sich in viel mehr Dimensionen vorzustellen, aber bis dahin können wir die lineare Algebra verwenden, um die numerischen Berechnungen durchzuführen und uns auch dabei zu helfen, in Begriffen zu denken von Linien / Vektoren / "Ebenen" / "Kugeln" in n Dimensionen, obwohl wir diese nicht zeichnen können.

So, in zwei Dimensionen : in Bezug auf Text Ähnlichkeit bedeutet dies , dass wir würden konzentrieren sich auf zwei verschiedene Begriffe, sagen die Worte „London“ und „Paris“, und wir würden uns zählen , wie oft jedes dieser Wörter in jeder gefunden die beiden Dokumente, die wir vergleichen möchten. Dies gibt uns für jedes Dokument einen Punkt in der xy-Ebene. Wenn Doc1 beispielsweise einmal Paris und viermal London hätte, würde ein Punkt bei (1,4) dieses Dokument präsentieren (im Hinblick auf diese winzige Bewertung von Dokumenten). Oder in Bezug auf Vektoren wäre dieses Doc1-Dokument ein Pfeil, der vom Ursprung zum Punkt (1,4) führt. Lassen Sie uns vor diesem Hintergrund darüber nachdenken, was es bedeutet, dass zwei Dokumente ähnlich sind und wie sich dies auf die Vektoren bezieht.

SEHR ähnliche Dokumente (wiederum in Bezug auf diesen begrenzten Satz von Dimensionen) hätten die gleiche Anzahl von Verweisen auf Paris UND die gleiche Anzahl von Verweisen auf London, oder vielleicht könnten sie das gleiche Verhältnis dieser Verweise haben. Ein Dokument, Doc2, mit 2 Verweisen auf Paris und 8 Verweisen auf London, wäre ebenfalls sehr ähnlich, nur mit vielleicht einem längeren Text oder einer Art Wiederholung der Städtenamen, aber im gleichen Verhältnis. Vielleicht sind beide Dokumente Leitfäden über London und beziehen sich nur vorübergehend auf Paris (und wie unkühl diese Stadt ist ;-) Nur ein Scherz !!!.

Jetzt können weniger ähnliche Dokumente auch Verweise auf beide Städte enthalten, jedoch in unterschiedlichen Anteilen. Vielleicht würde Doc2 Paris nur einmal und London siebenmal zitieren.

Zurück in unserer xy-Ebene, wenn wir diese hypothetischen Dokumente zeichnen, sehen wir, dass sich ihre Vektoren überlappen (obwohl einige Vektoren länger sein können), wenn sie SEHR ähnlich sind, und da sie weniger gemeinsam haben, beginnen diese Vektoren zu divergieren. einen größeren Winkel zwischen ihnen haben.

Indem wir den Winkel zwischen den Vektoren messen , können wir eine gute Vorstellung von ihrer Ähnlichkeit bekommen , und um die Sache noch einfacher zu machen, indem wir den Kosinus dieses Winkels nehmen, haben wir einen schönen Wert von 0 zu 1 oder -1 zu 1, der anzeigt Diese Ähnlichkeit hängt davon ab, was und wie wir erklären. Je kleiner der Winkel ist, desto größer (näher an 1) ist der Kosinuswert und desto höher ist auch die Ähnlichkeit.

Im Extremfall haben die Dokumente absolut nichts gemeinsam, wenn Doc1 nur Paris und Doc2 nur London zitiert. Doc1 hätte seinen Vektor auf der x-Achse, Doc2 auf der y-Achse, den Winkel 90 Grad, Cosinus 0. In diesem Fall würden wir sagen, dass diese Dokumente orthogonal zueinander sind.

Hinzufügen von Dimensionen :
Mit diesem intuitiven Gefühl für Ähnlichkeit, ausgedrückt als kleiner Winkel (oder großer Kosinus), können wir uns jetzt Dinge in drei Dimensionen vorstellen, indem wir beispielsweise das Wort "Amsterdam" in die Mischung einbringen und ganz gut visualisieren, wie ein Dokument mit zwei Verweise auf jeden haben einen Vektor, der in eine bestimmte Richtung geht, und wir können sehen, wie diese Richtung mit einem Dokument verglichen wird, in dem Paris und London jeweils dreimal zitiert werden, aber nicht Amsterdam usw. Wie gesagt, wir können versuchen, uns diese Phantasie vorzustellen Platz für 10 oder 100 Städte. Es ist schwer zu zeichnen, aber leicht zu konzipieren.

Ich werde zum Schluss nur ein paar Worte über die Formel selbst sagen . Wie ich bereits sagte, liefern andere Referenzen gute Informationen zu den Berechnungen.

Zuerst in zwei Dimensionen. Die Formel für den Kosinus des Winkels zwischen zwei Vektoren wird aus der trigonometrischen Differenz (zwischen Winkel a und Winkel b) abgeleitet:

cos(a - b) = (cos(a) * cos(b)) + (sin (a) * sin(b))

Diese Formel sieht der Punktproduktformel sehr ähnlich:

Vect1 . Vect2 =  (x1 * x2) + (y1 * y2)

Dabei cos(a)entspricht der xWert und sin(a)der yWert für den ersten Vektor usw. Das einzige Problem besteht darin x, dass yusw. nicht genau die Werte cosund sinsind, da diese Werte auf dem Einheitskreis gelesen werden müssen. Das ist , wo der Nenner der Formel Tritten in: durch das Produkt aus der Länge dieser Vektoren unterteilt, die xund yKoordinaten normalisiert sind.

mjv
quelle
25

Hier ist meine Implementierung in C #.

using System;

namespace CosineSimilarity
{
    class Program
    {
        static void Main()
        {
            int[] vecA = {1, 2, 3, 4, 5};
            int[] vecB = {6, 7, 7, 9, 10};

            var cosSimilarity = CalculateCosineSimilarity(vecA, vecB);

            Console.WriteLine(cosSimilarity);
            Console.Read();
        }

        private static double CalculateCosineSimilarity(int[] vecA, int[] vecB)
        {
            var dotProduct = DotProduct(vecA, vecB);
            var magnitudeOfA = Magnitude(vecA);
            var magnitudeOfB = Magnitude(vecB);

            return dotProduct/(magnitudeOfA*magnitudeOfB);
        }

        private static double DotProduct(int[] vecA, int[] vecB)
        {
            // I'm not validating inputs here for simplicity.            
            double dotProduct = 0;
            for (var i = 0; i < vecA.Length; i++)
            {
                dotProduct += (vecA[i] * vecB[i]);
            }

            return dotProduct;
        }

        // Magnitude of the vector is the square root of the dot product of the vector with itself.
        private static double Magnitude(int[] vector)
        {
            return Math.Sqrt(DotProduct(vector, vector));
        }
    }
}
tranmq
quelle
Das ist großartig, danke. Ich habe es geliebt, wie du Magnitude erklärt hast. =)
liminal18
Das ist großartig, aber was ist, wenn wir mit Dateien oder Zeichenfolgen arbeiten?
Talha
21

Der Einfachheit halber reduziere ich die Vektoren a und b:

Let :
    a : [1, 1, 0]
    b : [1, 0, 1]

Dann Kosinusähnlichkeit (Theta):

 (Theta) = (1*1 + 1*0 + 0*1)/sqrt((1^2 + 1^2))* sqrt((1^2 + 1^2)) = 1/2 = 0.5

dann ist die Umkehrung von cos 0,5 60 Grad.

userPS
quelle
18

Dieser Python-Code ist mein schneller und schmutziger Versuch, den Algorithmus zu implementieren:

import math
from collections import Counter

def build_vector(iterable1, iterable2):
    counter1 = Counter(iterable1)
    counter2 = Counter(iterable2)
    all_items = set(counter1.keys()).union(set(counter2.keys()))
    vector1 = [counter1[k] for k in all_items]
    vector2 = [counter2[k] for k in all_items]
    return vector1, vector2

def cosim(v1, v2):
    dot_product = sum(n1 * n2 for n1, n2 in zip(v1, v2) )
    magnitude1 = math.sqrt(sum(n ** 2 for n in v1))
    magnitude2 = math.sqrt(sum(n ** 2 for n in v2))
    return dot_product / (magnitude1 * magnitude2)


l1 = "Julie loves me more than Linda loves me".split()
l2 = "Jane likes me more than Julie loves me or".split()


v1, v2 = build_vector(l1, l2)
print(cosim(v1, v2))
Victor Yan
quelle
Können Sie erklären, warum Sie set in der Zeile "all_items = set (counter1.keys ()). Union (set (counter2.keys ()))" verwendet haben?
Ghos3t
@ Ghos3t, das heißt, Liste der verschiedenen Wörter aus beiden Dokumenten zu erhalten
Jobs
7

Am Beispiel von @Bill Bell gibt es zwei Möglichkeiten, dies in [R] zu tun.

a = c(2,1,0,2,0,1,1,1)

b = c(2,1,1,1,1,0,1,1)

d = (a %*% b) / (sqrt(sum(a^2)) * sqrt(sum(b^2)))

oder die Leistung der crossprod () -Methode nutzen ...

e = crossprod(a, b) / (sqrt(crossprod(a, a)) * sqrt(crossprod(b, b)))
Andrew U.
quelle
5

Dies ist ein einfacher PythonCode, der die Kosinusähnlichkeit implementiert.

from scipy import linalg, mat, dot
import numpy as np

In [12]: matrix = mat( [[2, 1, 0, 2, 0, 1, 1, 1],[2, 1, 1, 1, 1, 0, 1, 1]] )

In [13]: matrix
Out[13]: 
matrix([[2, 1, 0, 2, 0, 1, 1, 1],
        [2, 1, 1, 1, 1, 0, 1, 1]])
In [14]: dot(matrix[0],matrix[1].T)/np.linalg.norm(matrix[0])/np.linalg.norm(matrix[1])
Out[14]: matrix([[ 0.82158384]])
Nilani Algiriyage
quelle
3
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 
* @author Xiao Ma
* mail : [email protected]
*
*/
  public class SimilarityUtil {

public static double consineTextSimilarity(String[] left, String[] right) {
    Map<String, Integer> leftWordCountMap = new HashMap<String, Integer>();
    Map<String, Integer> rightWordCountMap = new HashMap<String, Integer>();
    Set<String> uniqueSet = new HashSet<String>();
    Integer temp = null;
    for (String leftWord : left) {
        temp = leftWordCountMap.get(leftWord);
        if (temp == null) {
            leftWordCountMap.put(leftWord, 1);
            uniqueSet.add(leftWord);
        } else {
            leftWordCountMap.put(leftWord, temp + 1);
        }
    }
    for (String rightWord : right) {
        temp = rightWordCountMap.get(rightWord);
        if (temp == null) {
            rightWordCountMap.put(rightWord, 1);
            uniqueSet.add(rightWord);
        } else {
            rightWordCountMap.put(rightWord, temp + 1);
        }
    }
    int[] leftVector = new int[uniqueSet.size()];
    int[] rightVector = new int[uniqueSet.size()];
    int index = 0;
    Integer tempCount = 0;
    for (String uniqueWord : uniqueSet) {
        tempCount = leftWordCountMap.get(uniqueWord);
        leftVector[index] = tempCount == null ? 0 : tempCount;
        tempCount = rightWordCountMap.get(uniqueWord);
        rightVector[index] = tempCount == null ? 0 : tempCount;
        index++;
    }
    return consineVectorSimilarity(leftVector, rightVector);
}

/**
 * The resulting similarity ranges from −1 meaning exactly opposite, to 1
 * meaning exactly the same, with 0 usually indicating independence, and
 * in-between values indicating intermediate similarity or dissimilarity.
 * 
 * For text matching, the attribute vectors A and B are usually the term
 * frequency vectors of the documents. The cosine similarity can be seen as
 * a method of normalizing document length during comparison.
 * 
 * In the case of information retrieval, the cosine similarity of two
 * documents will range from 0 to 1, since the term frequencies (tf-idf
 * weights) cannot be negative. The angle between two term frequency vectors
 * cannot be greater than 90°.
 * 
 * @param leftVector
 * @param rightVector
 * @return
 */
private static double consineVectorSimilarity(int[] leftVector,
        int[] rightVector) {
    if (leftVector.length != rightVector.length)
        return 1;
    double dotProduct = 0;
    double leftNorm = 0;
    double rightNorm = 0;
    for (int i = 0; i < leftVector.length; i++) {
        dotProduct += leftVector[i] * rightVector[i];
        leftNorm += leftVector[i] * leftVector[i];
        rightNorm += rightVector[i] * rightVector[i];
    }

    double result = dotProduct
            / (Math.sqrt(leftNorm) * Math.sqrt(rightNorm));
    return result;
}

public static void main(String[] args) {
    String left[] = { "Julie", "loves", "me", "more", "than", "Linda",
            "loves", "me" };
    String right[] = { "Jane", "likes", "me", "more", "than", "Julie",
            "loves", "me" };
    System.out.println(consineTextSimilarity(left,right));
}
}
user1472571
quelle
3

Einfacher JAVA-Code zur Berechnung der Kosinusähnlichkeit

/**
   * Method to calculate cosine similarity of vectors
   * 1 - exactly similar (angle between them is 0)
   * 0 - orthogonal vectors (angle between them is 90)
   * @param vector1 - vector in the form [a1, a2, a3, ..... an]
   * @param vector2 - vector in the form [b1, b2, b3, ..... bn]
   * @return - the cosine similarity of vectors (ranges from 0 to 1)
   */
  private double cosineSimilarity(List<Double> vector1, List<Double> vector2) {

    double dotProduct = 0.0;
    double normA = 0.0;
    double normB = 0.0;
    for (int i = 0; i < vector1.size(); i++) {
      dotProduct += vector1.get(i) * vector2.get(i);
      normA += Math.pow(vector1.get(i), 2);
      normB += Math.pow(vector2.get(i), 2);
    }
    return dotProduct / (Math.sqrt(normA) * Math.sqrt(normB));
  }
nikoo28
quelle
1
Es ist kein "einfacher, grafischer Weg", sondern nur Code. Obwohl andere den gleichen Fehler auch gemacht haben: /
Skrylar
-1

Zwei Vektoren A und B existieren in einem 2D-Raum oder 3D-Raum, der Winkel zwischen diesen Vektoren ist cos Ähnlichkeit.

Wenn der Winkel größer ist (maximal 180 Grad erreichen kann), ist dies Cos 180 = -1 und der minimale Winkel ist 0 Grad. cos 0 = 1 impliziert, dass die Vektoren zueinander ausgerichtet sind und daher die Vektoren ähnlich sind.

cos 90 = 0 (was ausreicht, um zu schließen, dass die Vektoren A und B überhaupt nicht ähnlich sind, und da der Abstand nicht negativ sein kann, liegen die Cosinuswerte zwischen 0 und 1. Ein größerer Winkel impliziert daher eine Verringerung der Ähnlichkeit (Visualisierung auch) macht Sinn)

Sabbern
quelle