Cách nhanh nhất trong Python để tính toán độ tương tự cosin cho dữ liệu ma trận thưa thớt là gì?

Question

Đưa ra danh sách ma trận thưa thớt, cách tốt nhất để tính độ tương tự cosin giữa mỗi cột (hoặc hàng) trong ma trận là gì? Tôi không muốn lặp lại n-chọn-hai lần.

Say ma trận đầu vào là:

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

Các đại diện thưa thớt là:

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

Trong Python, nó đơn giản để làm việc với các định dạng ma trận đầu vào:

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 

Cung cấp:

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

Đó là tốt cho đầu vào đầy đủ ma trận, nhưng tôi thực sự muốn bắt đầu với biểu diễn thưa thớt (do kích thước và độ lệch của ma trận của tôi). Bất kỳ ý tưởng về cách này tốt nhất có thể được thực hiện? Cảm ơn trước.

Answer 1

Bạn có thể tính tương đồng cosin cặp trên hàng của một ma trận thưa thớt trực tiếp sử dụng sklearn. Tính đến phiên bản 0.17 nó cũng hỗ trợ đầu ra thưa thớt:

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

Kết quả:

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 

Nếu bạn muốn tương đồng cosin cột khôn ngoan chỉ đơn giản là transpose ma trận đầu vào của bạn trước:

A_sparse.transpose() 

Answer 2

Bạn nên kiểm tra scipy.sparse (link). Bạn có thể áp dụng các phép toán trên các ma trận thưa thớt đó giống như cách bạn sử dụng ma trận thông thường.

Answer 3

Phương pháp sau đây nhanh hơn khoảng 30 lần so với scipy.spatial.distance.pdist. Nó hoạt động khá nhanh trên các ma trận lớn (giả sử bạn có đủ RAM)

Xem bên dưới để thảo luận về cách tối ưu hóa cho sự thưa thớt.

# 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 

Nếu vấn đề của bạn là điển hình cho vấn đề tùy chọn nhị phân quy mô lớn, bạn có nhiều mục nhập trong một thứ nguyên hơn kích thước khác. Ngoài ra, kích thước ngắn là thứ có mục bạn muốn tính toán điểm tương đồng giữa. Hãy gọi kích thước này là thứ nguyên 'item'.

Nếu trường hợp này xảy ra, hãy liệt kê 'các mục' của bạn theo hàng và tạo A bằng cách sử dụng scipy.sparse. Sau đó thay thế dòng đầu tiên như được chỉ ra.

Nếu vấn đề của bạn không điển hình, bạn sẽ cần nhiều sửa đổi hơn. Đó là những thay thế khá đơn giản của các hoạt động cơ bản numpy với các số tương đương scipy.sparse tương đương của chúng.

Answer 4

Hi bạn có thể làm theo cách này

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

tôi mất tất cả những câu trả lời này và đã viết một kịch bản để 1. xác nhận mỗi kết quả (xem khẳng định bên dưới) và 2. xem đó là nhanh nhất. Mã và kết quả là dưới đây:

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

Kết quả:

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

Tôi đã thử một số phương pháp trên. Tuy nhiên, thí nghiệm của @zbinsd có giới hạn của nó. Độ thưa thớt của ma trận được sử dụng trong thử nghiệm là cực kỳ thấp trong khi sự thưa thớt thực thường là trên 90%. Trong tình trạng của tôi, thưa thớt là với hình dạng của (7000, 25000) và thưa thớt 97%. Phương pháp 4 là cực kỳ chậm và tôi không thể chịu đựng được kết quả. Tôi sử dụng phương pháp 6 được hoàn thành trong 10 giây. Thật ngạc nhiên, tôi thử phương pháp dưới đây và nó kết thúc chỉ trong 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 

phương pháp hiệu quả này được liên kết bởi enter link description here