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

Учитывая разреженный список матриц, каков наилучший способ вычисления сходства косинусов между каждым из столбцов (или строк) в матрице? Я бы предпочел не перебирать n-choose-два раза.

Скажем, входная матрица:

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

Редкое представление:

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

В Python прямолинейно работать с матричным входным форматом:

 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 

дает:

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

Это нормально для полноразмерного ввода, но я действительно хочу начать с разреженного представления (из-за размера и разреженности моей матрицы). Любые идеи о том, как это можно сделать лучше всего? Заранее спасибо.

  • Точность плавающей точки в массиве Python
  • Python. Как сделать эту программу многопроцессорной?
  • MySQL и заблокировать таблицу, прочитать, а затем усечь
  • Доступ к указателям void в Python (с использованием SWIG или чего-то еще)
  • Сортировка словаря Python на основе значений вложенных словарей
  • matplotlib: использование цветной таблицы для цветной таблицы
  • разделять элементы списка в python
  • Как перезаписать некоторые байты в середине файла с помощью Python?
  • 5 Solutions collect form web for “Какой самый быстрый способ в Python вычислить подобие косинуса при использовании разреженных матричных данных?”

    Вы можете вычислять попарно-косинус-подобие по строкам разреженной матрицы непосредственно с помощью 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() 

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

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

     # base similarity matrix (all dot products) # replace this with A.dot(AT).toarray() for sparse representation similarity = numpy.dot(A, AT) # 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 

    Если ваша проблема типична для проблем с большими двоичными предпочтениями, у вас есть намного больше записей в одном измерении, чем в другом. Кроме того, короткий размер – это тот, чьи записи вы хотите рассчитать сходства между ними. Назовем это измерение размером «item».

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

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

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

    Я взял все эти ответы и написал сценарий для 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, AT) # 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*AT 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) 

    Результаты:

     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 

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

      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 
    Python - лучший язык программирования в мире.