Scipy稀疏...数组？

Question

我正在使用numpy数组进行Kmeans分类，这些数组非常稀疏——里面有很多零。我想用scipy的“稀疏”包来减少存储空间，但我对如何创建数组而不是矩阵有点困惑。

我看过一个关于如何创建稀疏矩阵的教程：http://www.scipy.org/SciPy_Tutorial#head-c60163f2fd2bab79edd94be43682414f18b90df7

为了模拟一个数组，我创建了一个1xN的矩阵，但你可能猜到，Asp.dot(Bsp)并不能正常工作，因为你不能直接相乘两个1xN的矩阵。我得把每个数组转置成Nx1，这样做很麻烦，因为我每次计算点积都得这么做。

接下来，我尝试创建一个NxN的矩阵，让第一列等于第一行（这样就可以相乘两个矩阵，并只取左上角作为点积），但这样做效率真的很低。

我希望能用scipy的稀疏包来替代numpy的array()，但目前我还不太确定该怎么做。

有什么建议吗？

Answer 1

我不太确定这样做是否真的更好或更快，但你可以这样做来避免使用转置：

Asp.multiply(Bsp).sum()

这个方法就是逐个元素相乘，然后把所有的乘积加起来。你可以创建一个你正在使用的矩阵格式的子类，把上面的计算作为点积。

不过，可能直接转置它们会更简单：

Asp*Bsp.T

这看起来没什么大不了的，但你也可以创建一个子类，并修改mul()方法。

Answer 2

你可以创建一个现有的二维稀疏数组的子类。

from scipy.sparse import dok_matrix

class sparse1d(dok_matrix):
    def __init__(self, v):
        dok_matrix.__init__(self, (v,))
    def dot(self, other):
        return dok_matrix.dot(self, other.transpose())[0,0]

a=sparse1d((1,2,3))
b=sparse1d((4,5,6))
print a.dot(b)

Answer 3

使用一种基于行或列的 scipy.sparse 格式，比如 csc_matrix 和 csr_matrix。

这些格式在底层使用了高效的C语言实现（包括乘法），而且转置操作几乎没有开销（特别是如果你调用 transpose(copy=False)），就像使用numpy数组一样。

编辑：通过 ipython 进行的一些时间测试：

import numpy, scipy.sparse
n = 100000
x = (numpy.random.rand(n) * 2).astype(int).astype(float) # 50% sparse vector
x_csr = scipy.sparse.csr_matrix(x)
x_dok = scipy.sparse.dok_matrix(x.reshape(x_csr.shape))

现在 x_csr 和 x_dok 的稀疏度是50%：

print repr(x_csr)
<1x100000 sparse matrix of type '<type 'numpy.float64'>'
        with 49757 stored elements in Compressed Sparse Row format>

以及时间测试结果：

timeit numpy.dot(x, x)
10000 loops, best of 3: 123 us per loop

timeit x_dok * x_dok.T
1 loops, best of 3: 1.73 s per loop

timeit x_csr.multiply(x_csr).sum()
1000 loops, best of 3: 1.64 ms per loop

timeit x_csr * x_csr.T
100 loops, best of 3: 3.62 ms per loop

所以看起来我说错了。转置操作确实非常便宜，但在最新的scipy 0.9.0中，没有高效的C实现来处理 csr * csc 的乘法。每次调用都会构造一个新的csr对象 :-(

作为一种变通方法（虽然现在的scipy相对稳定），你可以直接在稀疏数据上进行点乘：

timeit numpy.dot(x_csr.data, x_csr.data)
10000 loops, best of 3: 62.9 us per loop

注意，这种最后的方法又进行了numpy的密集乘法。稀疏度是50%，所以实际上比 dot(x, x) 快了2倍。