Podobieństwo cosinusowe między 2 listami liczb

119

Muszę obliczyć podobieństwo cosinusowe między dwiema listami , powiedzmy na przykład lista 1, która jest dataSetIi lista 2, która jest dataSetII. Nie mogę używać niczego takiego jak numpy lub moduł statystyk. Muszę używać wspólnych modułów (matematyka itp.) (I możliwie najmniejszej liczby modułów, aby skrócić czas spędzony).

Powiedzmy, że dataSetIjest [3, 45, 7, 2]i dataSetIIjest [2, 54, 13, 15]. Długości list są zawsze równe.

Oczywiście podobieństwo cosinusowe mieści się w przedziale od 0 do 1 i ze względu na to zostanie zaokrąglone do trzeciego lub czwartego miejsca po przecinku za pomocą format(round(cosine, 3)).

Z góry dziękuję za pomoc.

Rob Alsod
źródło
29
Uwielbiam sposób, w jaki TAK zmiażdżył duszę z tego zadania domowego, aby uczynić go ładnym, ogólnym pytaniem. OP mówi „ Nie mogę używać numpy , muszę iść drogą matematyczną dla pieszych”, a górna odpowiedź brzmi „powinieneś spróbować scipy, używa numpy”. Mechanicy SO przyznają złotą odznakę popularnemu pytaniu.
Nikana Reklawyks
1
Nikana Reklawyks, to doskonała uwaga. Coraz częściej mam ten problem ze StackOverflow. Kilka pytań zostało oznaczonych jako „duplikaty” wcześniejszego pytania, ponieważ moderatorzy nie poświęcili czasu, aby zrozumieć, co sprawiło, że moje pytanie było wyjątkowe.
LRK9
@NikanaReklawyks, to jest świetne. Spójrz na jego profil, opowiada historię jednego z najlepszych .01% autorów SO, wiesz?
Nathan Chappell

Odpowiedzi:

174

Powinieneś spróbować SciPy . Zawiera wiele przydatnych naukowych procedur, na przykład „procedury numerycznego obliczania całek, rozwiązywania równań różniczkowych, optymalizacji i rzadkich macierzy”. Używa superszybkiego zoptymalizowanego NumPy do chrupania liczb. Zobacz tutaj, aby zainstalować.

Zauważ, że spatial.distance.cosine oblicza odległość , a nie podobieństwo. Musisz więc odjąć wartość od 1, aby uzyskać podobieństwo .

from scipy import spatial

dataSetI = [3, 45, 7, 2]
dataSetII = [2, 54, 13, 15]
result = 1 - spatial.distance.cosine(dataSetI, dataSetII)
charmoniumQ
źródło
122

inna wersja oparta numpytylko

from numpy import dot
from numpy.linalg import norm

cos_sim = dot(a, b)/(norm(a)*norm(b))
dontloo
źródło
3
Bardzo jasne jak definicja, ale może np.inner(a, b) / (norm(a) * norm(b))lepiej jest to zrozumieć. dotmoże uzyskać taki sam wynik jak innerdla wektorów.
Belter,
15
FYI to rozwiązanie jest znacznie szybsze w moim systemie niż używanie scipy.spatial.distance.cosine.
Ozzah
@ZhengfangXin podobieństwo cosinusowe z definicji waha się od -1 do 1
dontloo
2
Jeszcze krócej:cos_sim = (a @ b.T) / (norm(a)*norm(b))
Statystyki uczenia się na przykładzie
Jest to zdecydowanie najszybsze podejście w porównaniu do innych.
Jason Youn
73

Możesz użyć dokumentówcosine_similarity funkcji formularzysklearn.metrics.pairwise

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
źródło
21
Przypominamy tylko, że przekazywanie tablic jednych wymiarów jako danych wejściowych jest przestarzałe w sklearn w wersji 0.17 i spowoduje podniesienie wartości ValueError w 0.19.
Chong Tang
4
Jaki jest właściwy sposób zrobienia tego ze sklearn, biorąc pod uwagę to ostrzeżenie o wycofaniu?
Elliott,
2
@Elliott one_dimension_array.reshape (-1,1)
bobo32
2
@ bobo32 cosine_similarity (np.array ([1, 0, -1]). reshape (-1,0), np.array ([- 1, -1, 0]). reshape (-1,0)) I Chyba masz na myśli? Ale co to oznacza, że ​​wraca? To nowa tablica 2d, a nie podobieństwo cosinusowe.
Isbister
10
Dodajmy jeszcze jeden wspornikcosine_similarity([[1, 0, -1]], [[-1,-1, 0]])
Ayush
34

Nie sądzę, żeby wydajność miała tu duże znaczenie, ale nie mogę się oprzeć. Funkcja zip () całkowicie ponownie kopiuje oba wektory (właściwie to raczej transpozycja macierzy) tylko po to, aby uzyskać dane w „Pythonowej” kolejności. Byłoby ciekawie zaplanować wdrożenie nakrętek i śrub:

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

Przechodzi przez szum podobny do C podczas wyodrębniania elementów pojedynczo, ale nie powoduje masowego kopiowania tablicy i wykonuje wszystko, co ważne w pojedynczej pętli for, i wykorzystuje pojedynczy pierwiastek kwadratowy.

ETA: Zaktualizowano wywołanie drukowania, aby było funkcją. (Oryginał to Python 2.7, a nie 3.3. Bieżący działa pod Pythonem 2.7 z rozszerzeniemfrom __future__ import print_function instrukcją.) Dane wyjściowe są takie same, tak czy inaczej.

CPYthon 2.7.3 na 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

Tak więc w tym przypadku sposób niepytoniczny jest około 3,6 razy szybszy.

Mike Housky
źródło
2
Co jest cosine_measurew tym przypadku?
MERose
1
@MERose: cosine_measurei cosine_similaritysą po prostu różnymi implementacjami tego samego obliczenia. Równoważne ze skalowaniem obu tablic wejściowych do „wektorów jednostkowych” i obliczeniem iloczynu skalarnego.
Mike Housky
3
Domyśliłbym się tego samego. Ale to nie jest pomocne. Przedstawiasz porównania czasowe dwóch algorytmów, ale przedstawiasz tylko jeden z nich.
MERose,
@MERose Och, przepraszam. cosine_measureto kod wysłany wcześniej przez pkacprzaka. Ten kod był alternatywą dla „innego” całkowicie standardowego rozwiązania Pythona.
Mike Housky
dziękuję, to jest świetne, ponieważ nie używa żadnej biblioteki i jasne jest zrozumienie matematyki, która się za tym kryje
grepit
18

bez użycia importu

math.sqrt (x)

można zastąpić

x ** .5

bez używania numpy.dot () musisz stworzyć własną funkcję kropkową używając funkcji list:

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

a wtedy jest to tylko prosta kwestia zastosowania wzoru na podobieństwo cosinusowe:

def cosine_similarity(a,b):
    return dot(a,b) / ( (dot(a,a) **.5) * (dot(b,b) ** .5) )
Mohammed
źródło
15

Zrobiłem test porównawczy na podstawie kilku odpowiedzi w pytaniu i uważa się, że następujący fragment jest najlepszym wyborem:

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)

Wynik zaskakuje mnie, że wdrożenie oparte o scipynie należy do najszybszych. Sprofilowałem i stwierdziłem, że cosinus w scipy zajmuje dużo czasu, aby rzutować wektor z listy Pythona na tablicę numpy.

wprowadź opis obrazu tutaj

McKelvin
źródło
skąd jesteś taki pewien, że to jest najszybsze?
Jeru Luke
@JeruLuke Wkleiłem link do mojego wyniku testu porównawczego na samym początku odpowiedzi: gist.github.com/mckelvin/…
McKelvin
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)

Możesz go zaokrąglić po obliczeniu:

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

Jeśli chcesz, żeby była naprawdę krótka, możesz użyć tej jednej linijki:

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
źródło
Wypróbowałem ten kod i wygląda na to, że nie działa. Wypróbowałem to z byciem v1 [2,3,2,5]i byciem v2 [3,2,2,0]. Wraca z 1.0, jakby były dokładnie takie same. Masz jakiś pomysł, co jest nie tak?
Rob Alsod
Poprawka zadziałała tutaj. Dobra robota! Zobacz poniżej brzydsze, ale szybsze podejście.
Mike Housky,
Jak można dostosować ten kod, jeśli podobieństwo trzeba obliczyć w macierzy, a nie dla dwóch wektorów? Myślałem, że biorę macierz i transponowaną macierz zamiast drugiego wektora, trochę to nie działa.
student
możesz użyć np.dot (x, yT), aby to uprościć
user702846
3

Możesz to zrobić w Pythonie za pomocą prostej funkcji:

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
źródło
3
To jest tekstowa implementacja cosinusa. Daje błędne dane wyjściowe dla danych numerycznych.
alvas
Czy możesz wyjaśnić, dlaczego użyłeś set w linii "intersection = set (vec1.keys ()) & set (vec2.keys ())".
Ghos3t
Wydaje się, że twoja funkcja oczekuje map, ale wysyłasz jej listy liczb całkowitych.
Ghos3t
3

Używając numpy porównaj jedną listę liczb z wieloma listami (macierz):

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
źródło
1

Możesz użyć tej prostej funkcji, aby obliczyć podobieństwo cosinusowe:

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
źródło
1
po co wymyślać koło na nowo?
Jeru Luke
@JeruLuke może udzielić „samodzielnej” odpowiedzi, takiej, która nie wymaga dodatkowego importu (ów) (i może konwersji z listy do numpy.array lub czegoś podobnego)
Marco Ottina
1

Jeśli używasz już PyTorch , powinieneś skorzystać z ich implementacji CosineSimilarity .

Przypuśćmy, że masz ndwuwymiarowe numpy.ndarrays, v1a v2więc ich kształty są oba (n,). Oto jak uzyskać ich podobieństwo cosinusowe:

import torch
import torch.nn as nn

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

Albo załóżmy, że masz dwa numpy.ndarrays w1i w2, które mają oba kształty (m, n). Poniżej znajduje się lista podobieństw cosinusowych, z których każde jest podobieństwem cosinusowym między wierszem w w1a odpowiadającym mu wierszem w w2:

cos(torch.tensor(w1), torch.tensor(w2)).tolist()
Yuxuan Chen
źródło
-1

Wszystkie odpowiedzi są świetne w sytuacjach, w których nie możesz używać NumPy. Jeśli możesz, oto inne podejście:

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)

Pamiętaj też o EPSILON = 1e-07zabezpieczeniu podziału.

user702846
źródło