python - Scipy CSR "vectors"之间更快的 Python 余弦差异

Question

这是一个经典的问题，但我相信很多人仍在寻找答案。这个问题与 this one 不同，因为我的问题是两个稀疏向量(不是矩阵)之间的运算。

我写了一个blog post关于当数据维度变高时，余弦 Scipy 空间距离 (SSD) 如何变得更慢(因为它适用于密集向量)。这篇文章是印度尼西亚语的，但是无论语言如何，代码、我的实验设置和结果都应该很容易理解(在文章的底部)。

目前，该解决方案对于高维数据的处理速度快了 70 倍以上(与 SSD 相比)并且内存效率更高:

    import numpy as np

    def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity
        uData = u.data; vData = v.data
        denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2))
        if denominator>0:
            uCol = u.indices; vCol = v.indices # np array
            intersection = set(np.intersect1d(uCol,vCol))
            uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection])
            vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])             
            return 1-np.dot(uI,vI)/denominator
        else:
            return float("inf")

是否有可能进一步改进该功能(Pythonic 或通过 JIT/Cython？？？)。

Answer 1

这里有一个替代方案，alt_fCosine，它(在我的机器上)对于大小为 10**5 和 10** 的 CSR 向量大约快 3 倍4非零元素:

import scipy.sparse as sparse
import numpy as np
import math

def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity
    uData = u.data; vData = v.data
    denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2))
    if denominator>0:
        uCol = u.indices; vCol = v.indices # np array
        intersection = set(np.intersect1d(uCol,vCol))
        uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection])
        vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])             
        return 1-np.dot(uI,vI)/denominator
    else:
        return float("inf")

def alt_fCosine(u,v): 
    uData, vData = u.data, v.data
    denominator = math.sqrt(np.sum(uData**2) * np.sum(vData**2))
    if denominator>0:
        uCol, vCol = u.indices, v.indices 
        uI = uData[np.in1d(uCol, vCol)]
        vI = vData[np.in1d(vCol, uCol)]
        return 1-np.dot(uI,vI)/denominator
    else:
        return float("inf")

# Check that they return the same result
N = 10**5
u = np.round(10*sparse.random(1, N, density=0.1, format='csr'))
v = np.round(10*sparse.random(1, N, density=0.1, format='csr'))
assert np.allclose(fCosine(u, v), alt_fCosine(u, v))

alt_fCosine 替换两个列表推导式，调用 np.intersection1d并通过两次调用 np.in1d 和 advance 来形成 Python 集索引。

<小时/>

对于N = 10**5:

In [322]: %timeit fCosine(u, v)
100 loops, best of 3: 5.73 ms per loop

In [323]: %timeit alt_fCosine(u, v)
1000 loops, best of 3: 1.62 ms per loop

In [324]: 5.73/1.62
Out[324]: 3.537037037037037