使用稀疏矩阵与numpy数组

Question

我在Python中创建了一些带有单词计数的numpy数组：行是文档，列是单词X的计数。如果我有很多零计数，人们建议在进一步处理时使用稀疏矩阵，例如在分类器中。然而，当将numpy数组与稀疏矩阵馈送到Scikitlogistic regression classifier中时，似乎没有太大的区别。所以我想知道三件事：

• Wikipedia说

  a sparse matrix is a matrix in which most of the elements are zero

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

• 稀疏矩阵对像我这样的任务有多大帮助， 尤其是与numpy数组或标准列表相比？
• 到目前为止，我将数据收集到一个numpy数组中，然后转换为 Scipy中的csr_矩阵。这样做对吗？我不能 找出如何从头开始建立稀疏矩阵，然后 可能是不可能的。

非常感谢您的帮助！

Answer 1

a sparse matrix is a matrix in which most of the elements are zero Is that an appropriate way to determine when to use a sparse matrix format - as soon as > 50 % of the values are zero? Or does it make sense to use just in case?

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

X' W

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

How much does a sparse matrix help performance in a task like mine, especially compared to a numpy array or a standard list?

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

So far, I collect my data into a numpy array, then convert into the csr_matrix in Scipy. Is that the right way to do it? I could not figure out how to build a sparse matrix from the ground up, and that might be impossible.

不，这不是个好办法。你可以“从头开始”建立它，例如首先建立一个字典，然后转换它，等等。有很多方法可以先建立稀疏矩阵，而不需要密集矩阵。

Answer 2

@hpaulj您的时间不对，您将sparse.random映射到numpy数组（它的slowwish）的结果很慢，请记住：

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)

为了接近纽比我们需要

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

稀疏矩阵包和MATLAB中类似的包基于线性代数问题的思想，例如求解大型稀疏线性方程（例如，有限差分和有限元实现）。因此，矩阵积（numpy数组的dot积）和方程求解器等都得到了很好的开发。

我的粗略经验是，稀疏矩阵乘积必须具有1%的稀疏性，才能比等效的密集运算更快，换句话说，每99个零对应一个非零值。（但见下面的测试）

但是人们也尝试使用稀疏矩阵来节省内存。但请记住，这样的矩阵必须存储3个值数组（至少是coo格式）。所以稀疏度必须小于1/3才能开始节省内存。显然，如果首先构建密集数组，然后从中创建稀疏数组，就不会节省内存。

scipy包实现了许多稀疏格式。coo格式最容易理解和构建。根据文档构建一个并查看其.data、.row和.col属性（3个1d数组）。

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