如何实现余弦相似度计算的并行化

Question

我通过读取一个目录中大量文件生成了一个很大的数据帧。我已经设法并行化了在解析中读取文件的部分。我获取该数据并为下一步生成数据帧。这是计算相似度矩阵。

现在，我正在尝试计算数据框的行之间的余弦相似度。由于它是一个大数据帧，它需要很长时间(几个小时)才能运行。我如何并行化这个进程。

这是我当前计算余弦相似度的代码，它在单个线程上运行：

df = df.fillna(0)

data = df.values
m, k = data.shape

mat = np.zeros((m, m))

"""
scipy cosine similarity is between 0-2 instead of -1 to 1 
in that case 1 is 0 and 2 is -1
"""
for i in xrange(m):
    for j in xrange(m):
        if i != j:
            mat[i][j] = 1 - cosine(data[i,:], data[j,:])
        else:
            mat[i][j] = 1. # 0 if we don't do 1-cosine()

Answer 1

首先，我假设你的cosine是scipy.spatial.distance.cosine，它的关键计算是：

dist = 1.0 - np.dot(u, v) / (norm(u) * norm(v))

所以看起来我可以用下面的代码替换你的双循环：

data1 = data/np.linalg.norm(data,axis=1)[:,None]
mat1 = np.einsum('ik,jk->ij', data1, data1)

也就是说，在开始时标准化一次data，而不是在每个节点上。然后用einsum计算出整套dot乘积。

对于一个小的测试用例(m，k=4,3)，这比你的双循环快25倍。

注意:我只针对一个小的data数组对您的答案进行了测试。

scipy.spactial.distance.norm和cosine有一些我还没有实现的检查。

虽然einsum在中等大小的数组上速度很快，但它可能会陷入较大的数组的泥潭，并且会在您的元素逐个元素dot之前遇到内存错误。底层的dot库可能会被更好地调优以处理多核机器。

但是，即使data太大而无法通过一次einsum调用来处理，您也可以将计算分成几个块，例如

mat[n1:n2,m1:m2] = np.einsum('ik,jk->ij', data1[n1:n2,:], data1[m1:m2,:])

Answer 2

我想给你指一下https://docs.python.org/2/library/multiprocessing.html的方向

注意pool.map(函数，可迭代)

然后构建一组三角形位置元组，编写适当的函数并发出。