77

给定一个稀疏矩阵列表,计算矩阵中每一列(或行)之间的余弦相似度的最佳方法是什么?我宁愿不迭代 n-choose-two 次。

假设输入矩阵是:

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

这对于全矩阵输入来说很好,但我真的想从稀疏表示开始(由于我的矩阵的大小和稀疏性)。关于如何最好地实现这一点的任何想法?提前致谢。

4

9 回答 9

82

您可以直接使用 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()
于 2016-08-23T14:45:15.900 回答
47

以下方法比 . 快大约 30 倍scipy.spatial.distance.pdist。它在大型矩阵上运行得非常快(假设你有足够的 RAM)

有关如何优化稀疏性的讨论,请参见下文。

import numpy as np

# base similarity matrix (all dot products)
# replace this with A.dot(A.T).toarray() for sparse representation
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
cosine = cosine.T * inv_mag

如果您的问题是大规模二元偏好问题的典型问题,那么您在一个维度中的条目比另一个维度要多得多。此外,短维度是您要计算其条目之间相似性的维度。让我们将此维度称为“项目”维度。

如果是这种情况,请在行中列出您的“项目”并A使用scipy.sparse. 然后按照指示替换第一行。

如果您的问题是非典型问题,则需要进行更多修改。这些应该是用它们的等价物替换基本numpy操作的非常简单的方法。scipy.sparse

于 2013-12-19T17:26:53.960 回答
15

我已经尝试了上面的一些方法。但是,@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

这种高效的方法通过在此处输入链接描述进行链接

于 2017-09-30T09:31:18.857 回答
13

我接受了所有这些答案并编写了一个脚本来 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
于 2017-05-12T17:31:11.747 回答
3

嗨,你可以这样做

    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
于 2016-06-13T00:30:44.707 回答
2

基于 Vaali 的解决方案:

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。它应该使用稀疏计算以极少的内存开销来完成更密集的部分。不过我还没有对它进行广泛的测试,所以请注意(更新:我已经对这个解决方案进行了测试和基准测试,我对此解决方案充满信心)

此外,这是 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 看起来第一个算法在大多数情况下表现最好.

于 2018-08-30T19:45:05.520 回答
1

您应该查看scipy.sparse。您可以像使用普通矩阵一样对这些稀疏矩阵应用操作。

于 2013-07-13T05:41:14.417 回答
0
def norm(vector):
    return sqrt(sum(x * x for x in vector))    

def cosine_similarity(vec_a, vec_b):
        norm_a = norm(vec_a)
        norm_b = norm(vec_b)
        dot = sum(a * b for a, b in zip(vec_a, vec_b))
        return dot / (norm_a * norm_b)

如果一次传入一对向量,这种方法似乎比使用 sklearn 的实现要快一些。

于 2019-03-04T21:59:24.613 回答
0

我建议分两步运行:

1)生成映射A的映射A:列索引->非零对象

2) 对于每个对象 i (行) 与非零出现 (列) {k1,..kn} 计算余弦相似度仅针对联合集 A[k1] UA[k2] U.. A[kn] 中的元素

假设一个具有高稀疏性的大稀疏矩阵,这将比蛮力获得显着提升

于 2019-03-11T13:40:49.797 回答