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

Question

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

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

目前，此解决方案对于高维数据（与 SSD 相比）的速度提高了 70 多倍，而且内存效率更高：

    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**4 非零元素的 CSR 向量大约快 3 倍：

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 和 advanced 形成 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

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

Faster Python Cosine dissimilarity between Scipy CSR "vectors"

python

cython

sparse-matrix

jit

numba