getrow() 的 Scipy 稀疏矩阵替代方案

Question

我正在处理大型稀疏二进制矩阵。我使用Scipy稀疏矩阵实现压缩了它们。Jaccard distancefrom的计算scipy.spatial.distance不支持对稀疏矩阵的直接运算，所以要么：

1. 将整个稀疏矩阵转换为密集矩阵，然后将每一行作为向量进行操作，这会占用大量内存

   或者

2. 遍历稀疏，抓取每一行使用getrow()并操作。

   或者

3. 编写我们自己的实现来处理稀疏矩阵。

为了正确看待事情，这里是示例代码：

import scipy.spatial.distance as d
import numpy as np
from scipy.sparse import csr_matrix

# benchmark performance 
X = np.random.random((3000, 3000))
# binarize
X[X > 0.3] = 0
X[X>0] = 1
mat =  csr_matrix(X)

a = np.zeros(3000)
a[4] = a[100] = a[22] =1
a = csr_matrix(a)

def jaccard_fast(v1,v2):
    common = v1.dot(v2.T)
    dis = (v1 != v2).getnnz()
    if common[0,0]:
        return 1.0-float(common[0,0])/float(common[0,0]+dis)
    else:
        return 0.0
    
def benchmark_jaccard_fast():
    for i in range(mat.shape[0]):
        jaccard_fast(mat.getrow(i),a)
        
def benchmark_jaccard_internal_todense():
    for v1,v2 in zip(mat.todense(),a.todense()):
         d.jaccard(v1,v2)
        
def benchmark_jaccard_internal_getrow():
    for i in range(mat.shape[0]):
        d.jaccard(mat.getrow(i),a)
        

print "Jaccard Fast:"
%time benchmark_jaccard_fast()
print "Jaccard Scipy (expanding to dense):"
%time benchmark_jaccard_internal_todense()
print "Jaccard Scipy (using getrow):"
%time benchmark_jaccard_internal_getrow()

jaccard_fast我自己的实现在哪里。在 scipy 稀疏矩阵上，getrow()我的实现似乎比内部实现快，但似乎减慢了我的实现速度。当我以 为基准jaccard_fast时scipy.spatial.distance.jaccard，结果是：

Jaccard Fast:
CPU times: user 1.28 s, sys: 0 ns, total: 1.28 s
Wall time: 1.28 s
Jaccard Scipy (expanding to dense):
CPU times: user 28 ms, sys: 8 ms, total: 36 ms
Wall time: 37.2 ms
Jaccard Scipy (using getrow):
CPU times: user 1.82 s, sys: 0 ns, total: 1.82 s
Wall time: 1.81 s

任何有关如何避免getrow瓶颈的帮助将不胜感激。todense()由于内存限制，我无法扩展我的稀疏矩阵。

Answer 1

众所周知，稀疏索引速度较慢，例如如何更快地读取/遍历/切片 Scipy 稀疏矩阵（LIL、CSR、COO、DOK）？

\n\n

In [33]: timeit for row in mat: x=row  # sparse iteration\n1 loops, best of 3: 510 ms per loop\n\nIn [35]: timeit for row in mat.todense(): x=row  # dense iteration\n10 loops, best of 3: 175 ms per loop\n

\n\n

但我发现d.jacard使用稀疏矩阵时你的速度也慢

\n\n

In [36]: ad=a.todense()\n\nIn [37]: timeit for row in mat.todense(): d.jaccard(row,ad) # all dense\n1 loops, best of 3: 734 ms per loop\n\nIn [38]: timeit for row in mat: d.jaccard(row.todense(),ad) # inner dense\n1 loops, best of 3: 1.69 s per loop\n\nIn [39]: timeit for row in mat: d.jaccard(row,a) # all sparse\n1 loops, best of 3: 4.61 s per loop\n

\n\n

消除getrow因素

\n\n

In [40]: mrow=mat.getrow(0)\n\nIn [41]: mrowd=mrow.todense()\n\nIn [42]: timeit d.jaccard(mrow, a)  # one sparse row\n1000 loops, best of 3: 1.32 ms per loop\n\nIn [43]: timeit d.jaccard(mrow.todense(), a.todense())  # with conversion\n1000 loops, best of 3: 539 \xc2\xb5s per loop\n\nIn [44]: timeit d.jaccard(mrowd, ad)  #  dense\n10000 loops, best of 3: 173 \xc2\xb5s per loop\n

\n\n

=====================

\n\n

我需要重新运行这些测试，因为d.jaccard不适用于稀疏（并且jaccard_fast不适用于密集）。因此，将稀疏行迭代问题从jaccard计算中分离出来将需要更多的工作。

\n\n

我稍微修改了一下jaccard_fast：

\n\n

def my_jaccard(mat, a):\n    common = mat*a.T # sparse does the large matrix product well \n    dis=np.array([(row!=a).getnnz() for row in mat]) # iterative\n    cA = common.A.ravel()\n    return 1 - cA/(cA + dis)\n

\n\n

它返回d.jaccard与密集行上运行的值相匹配的值。 d.jaccard返回1为 0 的行。common我似乎不需要测试（除非和cA可能在同一槽位均为 0）。cAdis

\n\n

In [141]: r=np.array([d.jaccard(row,ad) for row in mat.todense()])\n\nIn [142]: r1=my_jaccard(mat,a)\n\nIn [143]: np.allclose(r,r1)\nOut[143]: True\n

\n\n

而且速度只有一半。如果我可以重新设计，dis计算应该具有相似的速度。

\n\n

In [144]: timeit r=np.array([d.jaccard(row,ad) for row in mat.todense()])\n1 loops, best of 3: 783 ms per loop\n\nIn [145]: timeit r1=my_jaccard(mat,a)\n1 loops, best of 3: 1.29 s per loop\n

\n\n

对计算的进一步调整。我屏蔽了common0 的值。这有 2 个目的 - 它确保我们不会出现除以 0 的问题，并且减少了dis迭代次数，从而略微提高了速度。

\n\n

def my_jaccard(mat, a):\n    common=mat*a.T\n    cA = common.A.ravel()\n    mask = cA!=0\n    cA = cA[mask]\n    dis = np.array([(row!=a).getnnz() for row, b in zip(mat,mask) if b])\n    ret = np.ones(mat.shape[0])\n    ret[mask] = 1 - cA/(cA+dis)\n    return ret\n

\n\n

这样时间就减少了一点。

\n\n

In [188]: timeit my_jaccard(mat,a)\n1 loops, best of 3: 1.04 s per loop\n

\n\n

=================

\n\n

Python - Efficient Function with scipy稀疏矩阵的问题有重叠

\n\n

在那个问题中，我比较了稀疏矩阵和 1 行矩阵，发现使用sparse.kron复制行是复制numpy广播的最快方法。

\n\n

使用这个想法来jaccard计算dis数组

\n\n

def my_jaccard1(mat, a):\n    common = mat*a.T\n    cA = common.A.ravel()\n    aM = sparse.kron(a,np.ones((mat.shape[0],1),int))\n    dis = (mat!=aM).sum(1)\n    ret = 1-cA/(cA+dis.A1)\n    return ret    \n

\n\n

这样，时间显着改善（10 倍）：

\n\n

In [318]: timeit my_jaccard1(mat,a)\n1 loops, best of 3: 97.1 ms per loop\n

\n\n

我可以像以前一样应用屏蔽来防止被零除；但它实际上减慢了计算速度（至 140 毫秒）。

\n\n

def my_jaccard3(mat, a):\n    common = mat*a.T\n    cA = common.A.ravel()\n    mask = cA!=0\n    cA = cA[mask]\n    aM = sparse.kron(a,np.ones((len(cA),1),int))\n    dis = (mat[mask,:]!=aM).sum(1)\n    ret = np.ones(mat.shape[0])\n    ret[mask] = 1 - cA/(cA+dis.A1) \n    return ret  \n

\n\n

=======================

\n\n

编辑-疑似病例的测试

\n\n

In [75]: x,y= np.array([1,1,0,0,1,0]), np.array([0,0,1,0,1,0])\n\nIn [76]: d.jaccard(x,y)\nOut[76]: 0.75\n\nIn [78]: jaccard_fast(sparse.csr_matrix(x),sparse.csr_matrix(y))\nOut[78]: 0.75\n

\n\n

我的版本：

\n\n

In [79]: my_jaccard(sparse.csr_matrix(x),sparse.csr_matrix(y))\nOut[79]: array([ 0.75])\n...\nIn [82]: my_jaccard3(sparse.csr_matrix(x),sparse.csr_matrix(y))\nOut[82]: array([ 0.75])\n

\n\n

（编辑-明确使用sparse.kron）

\n