使用稀疏矩阵与numpy数组

Question

我在Python中创建了一些带有字数的numpy数组:行是文档,列是字X的计数.如果我有很多零计数,人们建议在进一步处理这些时使用稀疏矩阵,例如在分类器中.当将一个numpy数组与一个稀疏矩阵输入到Scikit 逻辑回归分类器中时,它似乎并没有太大的区别.所以我想知道三件事:

• 维基百科说

  稀疏矩阵是大多数元素为零的矩阵

  这是确定何时使用稀疏矩阵格式的合适方法 - 只要> 50%的值为零？或者使用以防万一是有意义的吗？

• 稀疏矩阵在像我这样的任务中有多大帮助,特别是与numpy数组或标准列表相比？
• 到目前为止,我将数据收集到一个numpy数组中,然后转换为Scipy中的csr_matrix .这是正确的方法吗？我无法弄清楚如何从头开始构建稀疏矩阵,这可能是不可能的.

任何帮助深表感谢!

Answer 1

该scipy稀疏矩阵包,并且在MATLAB类似的,是基于来自线性代数问题,如求解大型稀疏线性方程组(如有限差分和有限元的实现)开发的想法.所以像矩阵产品(dotnumpy数组的产品)和方程求解器这样的东西都很发达.

我粗略的经验是,稀疏csr矩阵产品必须具有1%的稀疏度,而不是等效的密集dot操作 - 换句话说,每99个零的一个非零值.(但见下面的测试)

但人们也尝试使用稀疏矩阵来节省内存.但请记住,这样的矩阵必须存储3个值数组(至少在coo格式中).所以稀疏度必须小于1/3才能开始节省内存.显然,如果你首先构建密集数组,并且从那里创建稀疏数组,你就不会节省内存.

该scipy包实现了许多稀疏格式.该coo格式是最容易理解和建设.根据文档建立一个和看它的.data,.row和.col属性(3个维数组).

csr并且csc通常是根据coo格式构建的,并稍微压缩数据,使它们更难理解.但他们拥有大部分数学功能.

也可以索引csr格式,但通常这比等效的密集矩阵/数组情况慢.其他操作(如更改值(尤其是从0到非零),连接,增量增长)也较慢.

lil(列表清单)也很容易理解,最适合增量构建. dok实际上是一个字典子类.

一个关键点是稀疏矩阵限制为2d,并且在很多方面表现得像np.matrix类(尽管它不是子类).

使用scikit-learn和sparse可能是查找使用这些矩阵的优缺点的最佳方法来搜索其他问题.我已经回答了很多问题,但我知道'稀疏'方面比'学习'方面更好.我认为它们很有用,但我觉得合适并不总是最好的.任何定制都在learn旁边.到目前为止,该sparse包尚未针对此应用进行优化.

我刚刚尝试了一些矩阵产品测试,使用该sparse.random方法创建具有指定稀疏度的稀疏矩阵.稀疏矩阵乘法的表现比我预期的要好.

In [251]: M=sparse.random(1000,1000,.5)

In [252]: timeit M1=M*M
1 loops, best of 3: 2.78 s per loop

In [253]: timeit Ma=M.toarray(); M2=Ma.dot(Ma)
1 loops, best of 3: 4.28 s per loop

这是一个规模问题; 对于较小的矩阵,密集dot更快

In [255]: M=sparse.random(100,100,.5)

In [256]: timeit M1=M*M
100 loops, best of 3: 3.24 ms per loop

In [257]: timeit Ma=M.toarray(); M2=Ma.dot(Ma)
1000 loops, best of 3: 1.44 ms per loop

但比较索引

In [268]: timeit M.tocsr()[500,500]
10 loops, best of 3: 86.4 ms per loop

In [269]: timeit Ma[500,500]
1000000 loops, best of 3: 318 ns per loop

In [270]: timeit Ma=M.toarray();Ma[500,500]
10 loops, best of 3: 23.6 ms per loop

Answer 2

@hpaulj 你的时间错了，你得到的结果很慢，因为将 sparse.random 映射到 numpy 数组（它很慢），请记住这一点：

M=sparse.random(1000,1000,.5)
Ma=M.toarray()

%timeit -n 25 M1=M*M
352 ms ± 1.18 ms per loop (mean ± std. dev. of 7 runs, 25 loops each)

%timeit -n 25 M2=Ma.dot(Ma)
13.5 ms ± 2.17 ms per loop (mean ± std. dev. of 7 runs, 25 loops each)

为了接近 numpy 我们需要有

M=sparse.random(1000,1000,.03)

%timeit -n 25 M1=M*M
10.7 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 25 loops each)

%timeit -n 25 M2=Ma.dot(Ma)
11.4 ms ± 564 µs per loop (mean ± std. dev. of 7 runs, 25 loops each)

Answer 3

稀疏矩阵是其中大多数元素为零的矩阵，这是确定何时使用稀疏矩阵格式的合适方法 - 一旦 > 50% 的值为零？或者以防万一使用有意义吗？

没有一般规则。这完全取决于您以后的确切用法。您必须根据稀疏矩阵计算模型的复杂度，然后才能找到“最佳点”。这将取决于样本数量和维度。一般来说，它通常归结为以下形式的矩阵乘法

X' W

其中 X 是数据矩阵 N xd，W 是某个权重矩阵 dx K。因此，“密集”乘法需要NdK时间，而稀疏，假设您的平均每行稀疏度为 p 是NpdK。因此，如果您的稀疏度为 50%，您可以预期运行速度提高近 2 倍。较难的部分是估计稀疏访问的开销，而不是高度优化的密集访问。

稀疏矩阵对像我这样的任务的性能有多大帮助，尤其是与 numpy 数组或标准列表相比？

对于 LR 的特定情况，这甚至可能比密集格式快几倍，但为了观察差异，您需要大量高维 (>100) 的数据 (>1000)。

到目前为止，我将我的数据收集到一个 numpy 数组中，然后在 Scipy 中转换为 csr_matrix。这是正确的方法吗？我无法弄清楚如何从头开始构建稀疏矩阵，这可能是不可能的。

不，这不是一个好方法。您可以通过例如首先构建字典然后转换它等方式“从头开始”构建它。有很多方法可以构建稀疏矩阵而首先没有密集矩阵。