¿Cuál es la forma más rápida en Python para calcular la similitud del coseno dados los escasos datos de la matriz?

numpy pandas

Question

Dada una lista de matriz dispersa, ¿cuál es la mejor manera de calcular la similitud del coseno entre cada una de las columnas (o filas) en la matriz? Preferiría no iterar n-elija-dos veces.

Digamos que la matriz de entrada es:

A=
[0 1 0 0 1
0 0 1 1 1
1 1 0 1 0]

La representación dispersa es:

A =
0, 1
0, 4
1, 2
1, 3
1, 4
2, 0
2, 1
2, 3

En Python, es sencillo trabajar con el formato de entrada de matriz:

import numpy as np
from sklearn.metrics import pairwise_distances
from scipy.spatial.distance import cosine
A = np.array(
[[0, 1, 0, 0, 1],
[0, 0, 1, 1, 1],
[1, 1, 0, 1, 0]])
dist_out = 1-pairwise_distances(A, metric="cosine")
dist_out

Da:

array([[ 1. , 0.40824829, 0.40824829],
[ 0.40824829, 1. , 0.33333333],
[ 0.40824829, 0.33333333, 1. ]])

Eso está bien para una entrada de matriz completa, pero realmente quiero comenzar con la representación dispersa (debido al tamaño y la dispersión de mi matriz). ¿Alguna idea sobre cómo esto podría lograrse mejor? Gracias por adelantado.

Answer 1

Deberías scipy.sparse un vistazo a scipy.sparse ( scipy.sparse ). Puede aplicar operaciones en esas matrices dispersas tal como lo hace con una matriz normal.

Answer 2

El siguiente método es aproximadamente 30 veces más rápido que scipy.spatial.distance.pdist . Funciona bastante rápido en matrices grandes (suponiendo que tienes suficiente RAM)

Vea a continuación una discusión sobre cómo optimizar la dispersión.

# base similarity matrix (all dot products)
# replace this with A.dot(A.T).toarray() for sparse representation
similarity = numpy.dot(A, A.T)
# squared magnitude of preference vectors (number of occurrences)
square_mag = numpy.diag(similarity)
# inverse squared magnitude
inv_square_mag = 1 / square_mag
# if it doesn''t occur, set it''s inverse magnitude to zero (instead of inf)
inv_square_mag[numpy.isinf(inv_square_mag)] = 0
# inverse of the magnitude
inv_mag = numpy.sqrt(inv_square_mag)
# cosine similarity (elementwise multiply by inverse magnitudes)
cosine = similarity * inv_mag
cosine = cosine.T * inv_mag

Si su problema es típico para problemas de preferencias binarias a gran escala, tiene muchas más entradas en una dimensión que en la otra. Además, la dimensión corta es aquella cuyas entradas desea calcular similitudes. Llamemos a esta dimensión la dimensión ''artículo''.

Si este es el caso, liste sus ''artículos'' en filas y cree A usando scipy.sparse . Luego reemplace la primera línea como se indica.

Si su problema es atípico, necesitará más modificaciones. Esos deberían ser reemplazos bastante simples de las operaciones numpy básicas con sus equivalentes scipy.sparse .

Answer 3

He intentado algunos métodos arriba. Sin embargo, el experimento de @zbinsd tiene su limitación. La dispersión de la matriz utilizada en el experimento es extremadamente baja, mientras que la verdadera dispersión suele ser superior al 90%. En mi condición, el escaso es con la forma de (7000, 25000) y la dispersión del 97%. El método 4 es extremadamente lento y no puedo tolerar los resultados. Uso el método 6 que está terminado en 10 s. Sorprendentemente, pruebo el método a continuación y está terminado en solo 0.247 s.

import sklearn.preprocessing as pp
def cosine_similarities(mat):
col_normed_mat = pp.normalize(mat.tocsc(), axis=0)
return col_normed_mat.T * col_normed_mat

Este eficiente método está vinculado mediante la introducción de la descripción del enlace aquí

Answer 4

Hola, puedes hacerlo de esta manera

 temp = sp.coo_matrix((data, (row, col)), shape=(3, 59))
temp1 = temp.tocsr()
#Cosine similarity
row_sums = ((temp1.multiply(temp1)).sum(axis=1))
rows_sums_sqrt = np.array(np.sqrt(row_sums))[:,0]
row_indices, col_indices = temp1.nonzero()
temp1.data /= rows_sums_sqrt[row_indices]
temp2 = temp1.transpose()
temp3 = temp1*temp2

Answer 5

Puede calcular la similitud de coseno por pares en las filas de una matriz dispersa directamente utilizando sklearn. A partir de la versión 0.17 también es compatible con salida escasa:

from sklearn.metrics.pairwise import cosine_similarity
from scipy import sparse
A = np.array([[0, 1, 0, 0, 1], [0, 0, 1, 1, 1],[1, 1, 0, 1, 0]])
A_sparse = sparse.csr_matrix(A)
similarities = cosine_similarity(A_sparse)
print(''pairwise dense output:/n {}/n''.format(similarities))
#also can output sparse matrices
similarities_sparse = cosine_similarity(A_sparse,dense_output=False)
print(''pairwise sparse output:/n {}/n''.format(similarities_sparse))

Resultados:

pairwise dense output:
[[ 1. 0.40824829 0.40824829]
[ 0.40824829 1. 0.33333333]
[ 0.40824829 0.33333333 1. ]]
pairwise sparse output:
(0, 1) 0.408248290464
(0, 2) 0.408248290464
(0, 0) 1.0
(1, 0) 0.408248290464
(1, 2) 0.333333333333
(1, 1) 1.0
(2, 1) 0.333333333333
(2, 0) 0.408248290464
(2, 2) 1.0

Si desea similitudes de coseno en columnas, simplemente transponga su matriz de entrada de antemano:

A_sparse.transpose()

Answer 6

Tomé todas estas respuestas y escribí un script para 1. validar cada uno de los resultados (ver la afirmación a continuación) y 2. ver cuál es el más rápido. El código y los resultados están a continuación:

# Imports
import numpy as np
import scipy.sparse as sp
from scipy.spatial.distance import squareform, pdist
from sklearn.metrics.pairwise import linear_kernel
from sklearn.preprocessing import normalize
from sklearn.metrics.pairwise import cosine_similarity
# Create an adjacency matrix
np.random.seed(42)
A = np.random.randint(0, 2, (10000, 100)).astype(float).T
# Make it sparse
rows, cols = np.where(A)
data = np.ones(len(rows))
Asp = sp.csr_matrix((data, (rows, cols)), shape = (rows.max()+1, cols.max()+1))
print "Input data shape:", Asp.shape
# Define a function to calculate the cosine similarities a few different ways
def calc_sim(A, method=1):
if method == 1:
return 1 - squareform(pdist(A, metric=''cosine''))
if method == 2:
Anorm = A / np.linalg.norm(A, axis=-1)[:, np.newaxis]
return np.dot(Anorm, Anorm.T)
if method == 3:
Anorm = A / np.linalg.norm(A, axis=-1)[:, np.newaxis]
return linear_kernel(Anorm)
if method == 4:
similarity = np.dot(A, A.T)
# squared magnitude of preference vectors (number of occurrences)
square_mag = np.diag(similarity)
# inverse squared magnitude
inv_square_mag = 1 / square_mag
# if it doesn''t occur, set it''s inverse magnitude to zero (instead of inf)
inv_square_mag[np.isinf(inv_square_mag)] = 0
# inverse of the magnitude
inv_mag = np.sqrt(inv_square_mag)
# cosine similarity (elementwise multiply by inverse magnitudes)
cosine = similarity * inv_mag
return cosine.T * inv_mag
if method == 5:
''''''
Just a version of method 4 that takes in sparse arrays
''''''
similarity = A*A.T
square_mag = np.array(A.sum(axis=1))
# inverse squared magnitude
inv_square_mag = 1 / square_mag
# if it doesn''t occur, set it''s inverse magnitude to zero (instead of inf)
inv_square_mag[np.isinf(inv_square_mag)] = 0
# inverse of the magnitude
inv_mag = np.sqrt(inv_square_mag).T
# cosine similarity (elementwise multiply by inverse magnitudes)
cosine = np.array(similarity.multiply(inv_mag))
return cosine * inv_mag.T
if method == 6:
return cosine_similarity(A)
# Assert that all results are consistent with the first model ("truth")
for m in range(1, 7):
if m in [5]: # The sparse case
np.testing.assert_allclose(calc_sim(A, method=1), calc_sim(Asp, method=m))
else:
np.testing.assert_allclose(calc_sim(A, method=1), calc_sim(A, method=m))
# Time them:
print "Method 1"
%timeit calc_sim(A, method=1)
print "Method 2"
%timeit calc_sim(A, method=2)
print "Method 3"
%timeit calc_sim(A, method=3)
print "Method 4"
%timeit calc_sim(A, method=4)
print "Method 5"
%timeit calc_sim(Asp, method=5)
print "Method 6"
%timeit calc_sim(A, method=6)

Resultados:

Input data shape: (100, 10000)
Method 1
10 loops, best of 3: 71.3 ms per loop
Method 2
100 loops, best of 3: 8.2 ms per loop
Method 3
100 loops, best of 3: 8.6 ms per loop
Method 4
100 loops, best of 3: 2.54 ms per loop
Method 5
10 loops, best of 3: 73.7 ms per loop
Method 6
10 loops, best of 3: 77.3 ms per loop