Какой самый быстрый способ в Python вычислить подобие косинуса при использовании разреженных матричных данных?

Ответ 1

Вы можете вычислять попарное косинус-подобие по строкам разреженной матрицы, непосредственно используя sklearn. Начиная с версии 0.17 он также поддерживает разреженный вывод:

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

Результаты:

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

Если вы хотите сходство по косинусу по столбцам, просто переставьте исходную матрицу заранее:

A_sparse.transpose()

Ответ 2

Следующий метод примерно в 30 раз быстрее, чем scipy.spatial.distance.pdist. Он работает довольно быстро на больших матрицах (если у вас достаточно ОЗУ)

Ниже приведено описание того, как оптимизировать для разреженности.

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

Если ваша проблема типична для проблем с большими двоичными предпочтениями, у вас есть намного больше записей в одном измерении, чем в другом. Кроме того, короткий размер - это тот, чьи записи вы хотите рассчитать сходства между ними. Позвольте этому измерению определить размер элемента.

Если это так, перечислите свои "элементы" в строках и создайте A с помощью scipy.sparse. Затем замените первую строку, как указано.

Если ваша проблема нетипична, вам понадобятся дополнительные изменения. Это должны быть довольно простые замены основных операций numpy с их эквивалентами scipy.sparse.

Ответ 3

Я пробовал некоторые методы выше. Однако эксперимент @zbinsd имеет свое ограничение. Рассеяемость матрицы, используемая в эксперименте, чрезвычайно низка, а реальная редкость обычно превышает 90%. В моем состоянии разреженная форма (7000, 25000) и разреженность 97%. Метод 4 чрезвычайно медленный, и я не могу терпимо получить результаты. Я использую метод 6, который завершен за 10 с. Удивительно, но я пробую метод ниже, и он закончил всего лишь 0,247 с.

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

Этот эффективный метод связан, введя описание ссылки здесь

Ответ 4

Я взял все эти ответы и написал script для 1. подтвердите каждый из результатов (см. утверждение ниже) и 2. посмотрите, какая из них самая быстрая. Код и результаты приведены ниже:

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

Результаты:

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

Ответ 5

Вы должны проверить scipy.sparse (ссылка). Вы можете применять операции на этих разреженных матрицах так же, как, как вы используете обычную матрицу.

Ответ 6

Привет, вы можете сделать это так.

    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

Ответ 7

Строительство решения Ваали:

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)

Это занимает разреженную матрицу (желательно csr_matrix) и возвращает csr_matrix. Он должен делать более интенсивные части, используя разреженные вычисления с минимальными издержками памяти. Я не тестировал его широко, поэтому, caveat emptor (Обновление: я уверен, что теперь я уверен в этом решении, которое я тестировал и сравнивал с ним)

Кроме того, вот редкая версия решения Waylon, если она помогает кому-либо, а не уверенному, какое решение на самом деле лучше.

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)

Оба решения, похоже, имеют четность с sklearn.metrics.pairwise.cosine_similarity

: -D

Обновить:

Теперь я протестировал оба решения против моей существующей реализации Cython: https://github.com/davidmashburn/sparse_dot/blob/master/test/benchmarks_v3_output_table.txt, и похоже, что первый алгоритм выполняет лучшие из трех наиболее важных,