Quel est le moyen le plus rapide en Python pour calculer la similarité des cosinus avec des données matricielles éparses?

La méthode suivante est environ 30 fois plus rapide que scipy.spatial.distance.pdist. Il fonctionne assez rapidement sur de grandes matrices (en supposant que vous avez assez de RAM)

Voir ci-dessous pour une discussion de la façon d'optimiser la densité.

# 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 votre problème est typique pour les problèmes de préférence binaire à grande échelle, vous avez beaucoup plus d'entrées dans une dimension que l'autre. En outre, la dimension courte est celle dont les entrées vous voulez calculer les similitudes entre. Appelons cela dimension la dimension "item".

si c'est le cas, listez vos 'items' en lignes et créez A en utilisant scipy.sparse. Puis remplacer la première ligne comme indiqué.

Si votre problème est atypique, vous aurez besoin de plus de modifications. Cela devrait être des remplacements assez simples de base numpy opérations avec leur scipy.sparse équivalents.

j'ai essayé quelques méthodes ci-dessus. Cependant, l'expérience de @zbinsd a ses limites. La densité de la matrice utilisée dans l'expérience est extrêmement faible alors que la densité réelle est généralement supérieure à 90%. Dans mon état, le clairsemé est avec la forme de (7000, 25000) et la sparsity de 97%. La méthode 4 est extrêmement lente et je ne supporte pas d'obtenir les résultats. J'utilise la méthode 6 qui se termine en 10 Secondes. Étonnamment, j'ai essayé la méthode ci-dessous et il est terminé en seulement 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

Cette méthode efficace est lié par entrez la description du lien ici

j'ai pris toutes ces réponses et j'ai écrit un script à 1. valider chacun des résultats (voir l'affirmation ci-dessous) et 2. voir qui est le plus rapide. Le Code et les résultats sont ci-dessous:

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

Résultats:

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

Vous devriez vérifier scipy.sparse (lien). Vous pouvez appliquer des opérations sur ces matrices éparses tout comme vous utilisez une matrice normale.

Hi-vous pouvez le faire de cette façon

    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

Construction de Vaali la solution:

def sparse_cosine_similarity(sparse_matrix):
    out = (sparse_matrix.copy() if type(sparse_matrix) is csr_matrix else
           sparse_matrix.tocsr())
    squared = out.multiply(out)
    sqrt_sum_squared_rows = np.array(np.sqrt(squared.sum(axis=1)))[:, 0]
    row_indices, col_indices = out.nonzero()
    out.data /= sqrt_sum_squared_rows[row_indices]
    return out.dot(out.T)

ceci prend une matrice clairsemée (de préférence une csr_matrix) et retourne une csr_matrix. Il devrait faire les pièces plus intensives en utilisant des calculs épars avec un minimum de mémoire aérienne. je n'ai pas testé beaucoup, donc caveat emptor (mise à Jour: j'ai confiance dans cette solution, maintenant que je l'ai testé et comparé)

aussi, voici la version clairsemée de la solution de Waylon au cas où il aide qui que ce soit, je ne sais pas quelle solution est la meilleure.

def sparse_cosine_similarity_b(sparse_matrix):
    input_csr_matrix = sparse_matrix.tocsr()
    similarity = input_csr_matrix * input_csr_matrix.T
    square_mag = similarity.diagonal()
    inv_square_mag = 1 / square_mag
    inv_square_mag[np.isinf(inv_square_mag)] = 0
    inv_mag = np.sqrt(inv_square_mag)
    return similarity.multiply(inv_mag).T.multiply(inv_mag)

les Deux solutions semblent avoir la parité avec sklearn.métrique.par paires.cosine_similarity