Qual è il modo più veloce in Python per calcolare la similarità del coseno dato i dati sparsi della matrice?

Question

Dato un elenco di matrice sparse, qual è il modo migliore per calcolare la somiglianza del coseno tra ciascuna delle colonne (o righe) nella matrice? Preferirei non iterare n-scegliere-due volte.

Di 'la matrice di ingresso è:

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

La rappresentazione sparsa è:

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

In Python, è semplice per lavorare con il formato matrice ingresso:

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 

Gives:

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

Questo va bene per un input full-matrix, ma voglio davvero iniziare con la rappresentazione sparsa (a causa delle dimensioni e della scarsità della mia matrice). Qualche idea su come questo potrebbe essere realizzato al meglio? Grazie in anticipo.

Answer 1

È possibile calcolare coppie somiglianza coseno sulle righe di una matrice sparsa direttamente utilizzando sklearn. A partire dalla versione 0.17 supporta anche l'uscita sparse:

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)) 

Risultati:

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 

Se volete somiglianze coseno colonna-saggio semplicemente trasporre vostra matrice di ingresso in anticipo:

A_sparse.transpose() 

Answer 2

Si consiglia di verificare scipy.sparse (link). È possibile applicare le operazioni su quelle matrici sparse proprio come si usa una matrice normale.

Answer 3

Il seguente metodo è circa 30 volte più veloce di scipy.spatial.distance.pdist. Funziona abbastanza velocemente su matrici di grandi dimensioni (supponendo che tu abbia abbastanza RAM)

Vedi sotto per una discussione su come ottimizzare per la scarsità.

# 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 

Se il problema è tipico per i problemi di preferenza binario su larga scala, si hanno molte più voci in una dimensione rispetto agli altri. Inoltre, la dimensione corta è quella di cui si vogliono calcolare le somiglianze tra le voci. Chiamiamo questa dimensione la dimensione 'elemento'.

In questo caso, elencare gli "articoli" in righe e creare A utilizzando scipy.sparse. Quindi sostituire la prima linea come indicato.

Se il tuo problema è atipico avrai bisogno di ulteriori modifiche. Dovrebbero essere piuttosto semplici sostituzioni delle operazioni di base numpy con gli equivalenti scipy.sparse.

Answer 4

Hi si può fare in questo modo

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

ho preso tutte queste risposte e ha scritto uno script per 1. convalidare ciascuno dei risultati (vedere l'asserzione sotto) e 2. vedere quale è il più veloce. Codice e risultati sono al di sotto:

# 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) 

Risultati:

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 

Answer 6

ho provato alcuni metodi di cui sopra. Tuttavia, l'esperimento di @zbinsd ha i suoi limiti. La scarsità di matrice utilizzata nell'esperimento è estremamente bassa mentre la scarsità reale è di solito superiore al 90%. Nella mia condizione, lo sparse ha la forma di (7000, 25000) e la scarsità del 97%. Il metodo 4 è estremamente lento e non riesco a tollerare i risultati. Io uso il metodo 6 che è finito in 10 s. Sorprendentemente, provo il metodo qui sotto ed è finito in soli 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 

Questo metodo efficace è collegata da enter link description here