スパース行列データを与えたときのコサイン類似度を計算するPythonの中で最も速い方法は何ですか？

Question

疎な行列のリストがある場合、行列の各列（または行）間のコサインの類似度を計算する最良の方法は何ですか？むしろ、n-chooseを2回反復しないでください。

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

スパース表現である：Pythonで

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

、それがマトリックス入力フォーマットで動作するように簡単です：

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

これはフル・マトリックス入力の場合には問題ありませんが、実際には（マトリクスのサイズと希薄さのため）疎な表現から始めたいと考えています。これがどのようにして最高の成果を収めることができるかについてのアイディア前もって感謝します。

Answer 1

それを行うことができます。

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

Answer 2

scipy.sparse（link）をチェックしてください。通常の行列の使い方と同じように、これらの疎行列に操作を適用できます。

Answer 3

以下の方法は、scipy.spatial.distance.pdistより約30倍高速です。それは、あなたが十分なRAMを持っていると仮定して、大規模な行列でかなり素早く動く

スパース性を最適化する方法については以下を参照してください。

# 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 

あなたの問題は、大規模なバイナリ好みの問題に典型的である場合は、他の次元でより多くのエントリを持っています。また、短い次元は、エントリ間の類似度を計算したい次元です。このディメンションを 'アイテム'ディメンションとしましょう。

この場合、 'items'を行に並べてAをscipy.sparseで作成します。指示に従って最初の行を交換します。

問題が一般的でない場合は、さらに修正する必要があります。それらはscipy.sparse同等物で基本的なnumpyオペレーションのかなり簡単な置き換えであるべきです。

Answer 4

こんにちはあなたはあなたが直接sklearnを使用して、スパース行列の行のペアごとのコサイン類似度を計算することができ、このよう

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

私が撮ったバージョン0.17の時点で、それはまた、まばらな出力をサポートしていますすべてのこれらの答えは、スクリプトを書いた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'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) 

結果：私は上記のいくつかの方法を試してみました

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

。しかし、@zbinsdによる実験には限界があります。実験で使用されたマトリックスの希​​薄さは非常に低く、実際の希薄さは通常90％以上です。 私の状態では、スパースは（7000,25000）の形と97％のまばゆいです。方法4は非常に遅く、結果を得ることはできません。私は10秒で終了する方法6を使用します。驚いたことに、私は以下の方法を試してみて、わずか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 

この効率的な方法は、スパースAの最初の行が '0、1'であってはならないenter link description here