Kosinusähnlichkeit zwischen 2 Zahlenlisten

119

Ich muss die Kosinusähnlichkeit zwischen zwei Listen berechnen , sagen wir zum Beispiel Liste 1 dataSetIund Liste 2 dataSetII. Ich kann nichts wie Numpy oder ein Statistikmodul verwenden. Ich muss gemeinsame Module (Mathematik usw.) verwenden (und dabei möglichst wenige Module, um den Zeitaufwand zu reduzieren).

Sagen wir dataSetIist [3, 45, 7, 2]und dataSetIIist [2, 54, 13, 15]. Die Länge der Listen ist immer gleich.

Natürlich liegt die Kosinusähnlichkeit zwischen 0 und 1 , und aus diesem Grund wird sie mit auf die dritte oder vierte Dezimalstelle gerundet format(round(cosine, 3)).

Vielen Dank im Voraus für Ihre Hilfe.

Rob Alsod
quelle
28
Ich mag die Art und Weise, wie SO die Seele aus dieser Hausaufgabenfrage herausgedrückt hat, um sie zu einer schönen allgemeinen Referenz zu machen. OP sagt " Ich kann Numpy nicht verwenden , ich muss den Fußgänger-Mathe-Weg gehen" und die beste Antwort lautet "Sie sollten es mit Scipy versuchen, es verwendet Numpy". SO-Mechaniker verleihen der beliebten Frage ein goldenes Abzeichen.
Nikana Reklawyks
1
Nikana Reklawyks, das ist ein ausgezeichneter Punkt. Ich hatte dieses Problem immer öfter mit StackOverflow. Und ich hatte mehrere Fragen, die als "Duplikate" einer früheren Frage markiert waren, weil sich die Moderatoren nicht die Zeit genommen hatten, zu verstehen, was meine Frage einzigartig machte.
LRK9

Antworten:

174

Sie sollten SciPy ausprobieren . Es gibt eine Reihe nützlicher wissenschaftlicher Routinen, zum Beispiel "Routinen zum numerischen Berechnen von Integralen, Lösen von Differentialgleichungen, Optimieren und spärlichen Matrizen". Es verwendet das superschnell optimierte NumPy für die Zahlenverarbeitung. Siehe hier für die Installation.

Beachten Sie, dass Spatial.Distance.cosine die Entfernung und nicht die Ähnlichkeit berechnet . Sie müssen also den Wert von 1 subtrahieren, um die Ähnlichkeit zu erhalten .

from scipy import spatial

dataSetI = [3, 45, 7, 2]
dataSetII = [2, 54, 13, 15]
result = 1 - spatial.distance.cosine(dataSetI, dataSetII)
charmoniumQ
quelle
122

eine andere Version, die numpynur auf basiert

from numpy import dot
from numpy.linalg import norm

cos_sim = dot(a, b)/(norm(a)*norm(b))
dontloo
quelle
3
Sehr klar wie die Definition, aber vielleicht np.inner(a, b) / (norm(a) * norm(b))besser zu verstehen. dotkann das gleiche Ergebnis wie innerfür Vektoren erhalten.
Belter
14
Zu Ihrer Information, diese Lösung ist auf meinem System erheblich schneller als die Verwendung scipy.spatial.distance.cosine.
Ozzah
@ ZhengfangXin Cosinus Ähnlichkeit reicht von -1 bis 1 per Definition
Dontloo
2
Noch kürzer:cos_sim = (a @ b.T) / (norm(a)*norm(b))
Lernstatistiken am Beispiel
Dies ist bei weitem der schnellste Ansatz im Vergleich zu anderen.
Jason Youn
72

Sie können mit cosine_similarityFunktionsform sklearn.metrics.pairwise docs

In [23]: from sklearn.metrics.pairwise import cosine_similarity

In [24]: cosine_similarity([[1, 0, -1]], [[-1,-1, 0]])
Out[24]: array([[-0.5]])
Akavall
quelle
20
Nur eine Erinnerung daran, dass das Übergeben von eindimensionalen Arrays als Eingabedaten in sklearn Version 0.17 veraltet ist und ValueError in 0.19 auslöst.
Chong Tang
4
Was ist der richtige Weg, um dies mit sklearn angesichts dieser Abwertungswarnung zu tun?
Elliott
2
@Elliott one_dimension_array.reshape (-1,1)
bobo32
2
@ bobo32 cosine_similarity (np.array ([1, 0, -1]). Umformung (-1,0), np.array ([- 1, -1, 0]). Umformung (-1,0)) I. Vermutlich meinst du? Aber was bedeutet dieses Ergebnis, dass es zurückkehrt? Es ist ein neues 2d-Array, keine Cosinus-Ähnlichkeit.
Isbister
10
Schließen Sie es mit einer weiteren Klammer eincosine_similarity([[1, 0, -1]], [[-1,-1, 0]])
Ayush
33

Ich denke, Leistung ist hier nicht sehr wichtig, aber ich kann nicht widerstehen. Die Funktion zip () kopiert beide Vektoren vollständig neu (eigentlich eher eine Matrixtransponierung), um die Daten in der Reihenfolge "Pythonic" zu erhalten. Es wäre interessant, die Implementierung der Schrauben und Muttern zeitlich zu planen:

import math
def cosine_similarity(v1,v2):
    "compute cosine similarity of v1 to v2: (v1 dot v2)/{||v1||*||v2||)"
    sumxx, sumxy, sumyy = 0, 0, 0
    for i in range(len(v1)):
        x = v1[i]; y = v2[i]
        sumxx += x*x
        sumyy += y*y
        sumxy += x*y
    return sumxy/math.sqrt(sumxx*sumyy)

v1,v2 = [3, 45, 7, 2], [2, 54, 13, 15]
print(v1, v2, cosine_similarity(v1,v2))

Output: [3, 45, 7, 2] [2, 54, 13, 15] 0.972284251712

Dies geht durch das C-ähnliche Rauschen des einzelnen Extrahierens von Elementen, führt jedoch kein Kopieren von Bulk-Arrays durch und erledigt alles Wichtige in einer einzigen for-Schleife und verwendet eine einzelne Quadratwurzel.

ETA: Der Druckaufruf wurde aktualisiert, um eine Funktion zu sein. (Das Original war Python 2.7, nicht 3.3. Das aktuelle läuft unter Python 2.7 mit afrom __future__ import print_function Anweisung ausgeführt.) Die Ausgabe ist in beiden Fällen dieselbe.

CPYthon 2.7.3 auf 3.0 GHz Core 2 Duo:

>>> timeit.timeit("cosine_similarity(v1,v2)",setup="from __main__ import cosine_similarity, v1, v2")
2.4261788514654654
>>> timeit.timeit("cosine_measure(v1,v2)",setup="from __main__ import cosine_measure, v1, v2")
8.794677709375264

Der unpythonische Weg ist in diesem Fall also etwa 3,6-mal schneller.

Mike Housky
quelle
2
Was ist cosine_measurein diesem Fall?
MERose
1
@MERose: cosine_measureund cosine_similaritysind einfach verschiedene Implementierungen derselben Berechnung. Entspricht der Skalierung beider Eingabearrays auf "Einheitsvektoren" und der Aufnahme des Punktprodukts.
Mike Housky
3
Ich hätte das auch erraten. Aber es ist nicht hilfreich. Sie präsentieren Zeitvergleiche zweier Algorithmen, aber nur einen davon.
MERose
@MERose Oh, sorry. cosine_measureist der Code, der früher von pkacprzak gepostet wurde. Dieser Code war eine Alternative zur "anderen" All-Standard-Python-Lösung.
Mike Housky
Vielen Dank, das ist großartig, da es keine Bibliothek verwendet und es klar ist, die Mathematik dahinter zu verstehen
Grepit
15

Ich habe einen Benchmark basierend auf mehreren Antworten in der Frage durchgeführt und das folgende Snippet wird als die beste Wahl angesehen:

def dot_product2(v1, v2):
    return sum(map(operator.mul, v1, v2))


def vector_cos5(v1, v2):
    prod = dot_product2(v1, v2)
    len1 = math.sqrt(dot_product2(v1, v1))
    len2 = math.sqrt(dot_product2(v2, v2))
    return prod / (len1 * len2)

Das Ergebnis überrascht mich, dass die Implementierung scipynicht die schnellste ist. Ich habe ein Profil erstellt und festgestellt, dass Cosinus in Scipy viel Zeit benötigt, um einen Vektor von der Python-Liste in ein Numpy-Array umzuwandeln.

Geben Sie hier die Bildbeschreibung ein

McKelvin
quelle
Wie bist du dir so sicher, dass dies der schnellste ist?
Jeru Luke
@ JeruLuke Ich habe den Link meines Benchmark-Ergebnisses ganz am Anfang der Antwort eingefügt
McKelvin
15

ohne Importe zu verwenden

math.sqrt (x)

kann durch ersetzt werden

x ** .5

Ohne Verwendung von numpy.dot () müssen Sie mithilfe des Listenverständnisses eine eigene Punktfunktion erstellen:

def dot(A,B): 
    return (sum(a*b for a,b in zip(A,B)))

und dann ist es nur eine einfache Sache, die Kosinus-Ähnlichkeitsformel anzuwenden:

def cosine_similarity(a,b):
    return dot(a,b) / ( (dot(a,a) **.5) * (dot(b,b) ** .5) )
Mohammed
quelle
10
import math
from itertools import izip

def dot_product(v1, v2):
    return sum(map(lambda x: x[0] * x[1], izip(v1, v2)))

def cosine_measure(v1, v2):
    prod = dot_product(v1, v2)
    len1 = math.sqrt(dot_product(v1, v1))
    len2 = math.sqrt(dot_product(v2, v2))
    return prod / (len1 * len2)

Sie können es nach dem Rechnen abrunden:

cosine = format(round(cosine_measure(v1, v2), 3))

Wenn Sie es wirklich kurz haben möchten, können Sie diesen Einzeiler verwenden:

from math import sqrt
from itertools import izip

def cosine_measure(v1, v2):
    return (lambda (x, y, z): x / sqrt(y * z))(reduce(lambda x, y: (x[0] + y[0] * y[1], x[1] + y[0]**2, x[2] + y[1]**2), izip(v1, v2), (0, 0, 0)))
pkacprzak
quelle
Ich habe diesen Code ausprobiert und er scheint nicht zu funktionieren. Ich habe es mit v1 [2,3,2,5]und v2 versucht [3,2,2,0]. Es kehrt mit zurück 1.0, als ob sie genau gleich wären. Irgendeine Idee was falsch ist?
Rob Alsod
Das Update hat hier funktioniert. Gut gemacht! Weiter unten finden Sie einen hässlicheren, aber schnelleren Ansatz.
Mike Housky
Wie ist es möglich, diesen Code anzupassen, wenn die Ähnlichkeit innerhalb einer Matrix und nicht für zwei Vektoren berechnet werden muss? Ich dachte, ich nehme eine Matrix und die transponierte Matrix anstelle des zweiten Vektors, aber es scheint nicht zu funktionieren.
Student
Sie können np.dot (x, yT) verwenden, um es einfacher zu machen
user702846
3

Sie können dies in Python mit einer einfachen Funktion tun:

def get_cosine(text1, text2):
  vec1 = text1
  vec2 = text2
  intersection = set(vec1.keys()) & set(vec2.keys())
  numerator = sum([vec1[x] * vec2[x] for x in intersection])
  sum1 = sum([vec1[x]**2 for x in vec1.keys()])
  sum2 = sum([vec2[x]**2 for x in vec2.keys()])
  denominator = math.sqrt(sum1) * math.sqrt(sum2)
  if not denominator:
     return 0.0
  else:
     return round(float(numerator) / denominator, 3)
dataSet1 = [3, 45, 7, 2]
dataSet2 = [2, 54, 13, 15]
get_cosine(dataSet1, dataSet2)
rajeshwerkushwaha
quelle
3
Dies ist eine Textimplementierung von Cosinus. Es wird die falsche Ausgabe für die numerische Eingabe ausgegeben.
Alvas
Können Sie erklären, warum Sie set in der Zeile "intersection = set (vec1.keys ()) & set (vec2.keys ())" verwendet haben?
Ghos3t
Auch Ihre Funktion scheint Karten zu erwarten, aber Sie senden ihm Listen mit ganzen Zahlen.
Ghos3t
3

Vergleichen Sie mit numpy eine Liste von Zahlen mit mehreren Listen (Matrix):

def cosine_similarity(vector,matrix):
   return ( np.sum(vector*matrix,axis=1) / ( np.sqrt(np.sum(matrix**2,axis=1)) * np.sqrt(np.sum(vector**2)) ) )[::-1]
sten
quelle
1

Mit dieser einfachen Funktion können Sie die Kosinusähnlichkeit berechnen:

def cosine_similarity(a, b):
return sum([i*j for i,j in zip(a, b)])/(math.sqrt(sum([i*i for i in a]))* math.sqrt(sum([i*i for i in b])))
Isira
quelle
1
Warum das Rad neu erfinden?
Jeru Luke
@ JeruLuke vielleicht, um eine "eigenständige" Antwort zu geben, diejenigen, die keine zusätzlichen Importe erfordern (und vielleicht Konvertierungen von Liste zu numpy.array oder so ähnlich)
Marco Ottina
1

Wenn Sie PyTorch bereits verwenden, sollten Sie die CosineSimilarity-Implementierung verwenden .

Angenommen, Sie haben nzweidimensionale numpy.ndarrays, v1und v2ihre Formen sind beide (n,). So erhalten Sie ihre Kosinusähnlichkeit:

import torch
import torch.nn as nn

cos = nn.CosineSimilarity()
cos(torch.tensor([v1]), torch.tensor([v2])).item()

Oder nehmen wir an, Sie haben zwei numpy.ndarrays w1und w2, deren Formen beide sind (m, n). Im Folgenden erhalten Sie eine Liste von Cosinus-Ähnlichkeiten, wobei jede die Cosinus-Ähnlichkeit zwischen einer Zeile in w1und der entsprechenden Zeile in ist w2:

cos(torch.tensor(w1), torch.tensor(w2)).tolist()
Yuxuan Chen
quelle
-1

Alle Antworten eignen sich hervorragend für Situationen, in denen Sie NumPy nicht verwenden können. Wenn Sie können, ist hier ein anderer Ansatz:

def cosine(x, y):
    dot_products = np.dot(x, y.T)
    norm_products = np.linalg.norm(x) * np.linalg.norm(y)
    return dot_products / (norm_products + EPSILON)

Denken Sie auch EPSILON = 1e-07daran, die Teilung zu sichern.

user702846
quelle