具有numpy的大型稀疏矩阵的余弦相似度

Question

以下代码使我的系统在完成之前耗尽了内存。

您能否建议一种在大型矩阵（例如下面的矩阵）上计算余弦相似度的更有效方法？

我想针对原始矩阵（mat）相对于所有其他矩阵计算65000行中的每一行的余弦相似度，以使结果为65000 x 65000矩阵，其中每个元素为原始矩阵中两行之间的余弦相似度矩阵。

import numpy as np
from scipy import sparse
from sklearn.metrics.pairwise import cosine_similarity

mat = np.random.rand(65000, 10)

sparse_mat = sparse.csr_matrix(mat)

similarities = cosine_similarity(sparse_mat)

在运行了最后一行之后，我总是会用完内存，并且该程序会因MemoryError冻结或崩溃。无论我在8 GB本地RAM上还是在64 GB EC2实例上运行，都会发生这种情况。

Answer 1

同样的问题在这里。我有一个很大的非稀疏矩阵。它很适合内存，但cosine_similarity由于任何未知原因而崩溃，可能是因为它们在某处复制矩阵一次太多。所以我让它比较“左边”的小批量行而不是整个矩阵：

import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

def cosine_similarity_n_space(m1, m2, batch_size=100):
    assert m1.shape[1] == m2.shape[1]
    ret = np.ndarray((m1.shape[0], m2.shape[0]))
    for row_i in range(0, int(m1.shape[0] / batch_size) + 1):
        start = row_i * batch_size
        end = min([(row_i + 1) * batch_size, m1.shape[0]])
        if end <= start:
            break # cause I'm too lazy to elegantly handle edge cases
        rows = m1[start: end]
        sim = cosine_similarity(rows, m2) # rows is O(1) size
        ret[start: end] = sim
    return ret

对我来说没有崩溃；天啊。尝试不同的批量大小以使其更快。我曾经一次只比较 1 行，而在我的机器上花费了大约 30 倍的时间。

愚蠢而有效的健全性检查：

import random
while True:
    m = np.random.rand(random.randint(1, 100), random.randint(1, 100))
    n = np.random.rand(random.randint(1, 100), m.shape[1])
    assert np.allclose(cosine_similarity(m, n), cosine_similarity_n_space(m, n))

Answer 2

由于您试图存储 65000x65000 矩阵，因此内存不足。请注意，您正在构建的矩阵根本不稀疏。np.random.rand生成 0 到 1 之间的随机数。因此没有足够的零来csr_matrix实际压缩数据。事实上，几乎可以肯定根本不存在零。

如果仔细查看回溯MemoryError，您会发现cosine_similarity如果可能的话，会尝试使用稀疏点积：

MemoryError                  Traceback (most recent call last)
    887         Y_normalized = normalize(Y, copy=True)
    888 
--> 889     K = safe_sparse_dot(X_normalized, Y_normalized.T, dense_output=dense_output)
    890 
    891     return K

所以问题不在于cosine_similarity，而在于你的矩阵。尝试初始化一个实际的稀疏矩阵（例如，稀疏度为 1%），如下所示：

>>> a = np.zeros((65000, 10))
>>> i = np.random.rand(a.size)
>>> a.flat[i < 0.01] = 1        # Select 1% of indices and set to 1
>>> a = sparse.csr_matrix(a)

然后，在具有 32GB RAM 的计算机上（8GB RAM 对我来说不够），运行以下命令不会出现内存错误：

>>> b = cosine_similarity(a)
>>> b
array([[ 0.,  0.,  0., ...,  0.,  0.,  0.],
       [ 0.,  0.,  0., ...,  0.,  0.,  0.],
       [ 0.,  0.,  0., ...,  0.,  0.,  0.],
       ..., 
       [ 0.,  0.,  0., ...,  1.,  0.,  0.],
       [ 0.,  0.,  0., ...,  0.,  0.,  0.],
       [ 0.,  0.,  0., ...,  0.,  0.,  0.]])