稀疏数组 (scipy.sparse)#

简介#

scipy.sparse 及其子模块提供了用于处理 稀疏数组 的工具。稀疏数组是数组中只有少数位置有数据，大多数位置被视为“空”的数组。稀疏数组非常有用，因为它们允许为线性代数（scipy.sparse.linalg）或基于图的计算（scipy.sparse.csgraph）提供更简单、更快或更节省内存的算法，但它们通常在切片、重塑或赋值等操作上灵活性较低。本指南将介绍 scipy.sparse 中稀疏数组的基础知识，解释稀疏数据结构的独特方面，并参考用户指南的其他部分，解释 稀疏线性代数 和 图方法。

开始使用稀疏数组#

稀疏数组是一种特殊类型的数组，其中只有少数位置有数据。这允许使用数据的 压缩 表示，其中仅记录存在数据的位置。有许多不同的稀疏数组格式，每种格式在压缩和功能之间做出不同的权衡。首先，让我们构建一个非常简单的稀疏数组，即坐标（COO）数组（coo_array），并将其与密集数组进行比较：

>>> import scipy as sp
>>> import numpy as np
>>> dense = np.array([[1, 0, 0, 2], [0, 4, 1, 0], [0, 0, 5, 0]])
>>> sparse = sp.sparse.coo_array(dense)
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> sparse
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

请注意，在我们的密集数组中，我们有五个非零值。例如，2 位于位置 0,3，而 4 位于位置 1,1。所有其他值均为零。稀疏数组显式记录这五个值（参见 5 stored elements and shape (3, 4)），然后将所有剩余的零值表示为隐式值。

大多数稀疏数组方法的工作方式与密集数组方法类似：

>>> sparse.max()
5
>>> dense.max()
5
>>> sparse.argmax()
10
>>> dense.argmax()
10
>>> sparse.mean()
1.0833333333333333
>>> dense.mean()
1.0833333333333333

一些“额外”的属性，例如返回存储值数量的 .nnz，也存在于稀疏数组中：

>>> sparse.nnz
5

大多数归约操作，例如 .mean()、.sum() 或 .max()，当应用于稀疏数组的轴时，将返回一个 numpy 数组：

>>> sparse.mean(axis=1)
array([0.75, 1.25, 1.25])

这是因为对稀疏数组的归约操作通常是密集的。

理解稀疏数组格式#

不同种类的稀疏数组具有不同的功能。例如，COO 数组不能被下标或切片：

>>> dense[2, 2]
5
>>> sparse[2, 2]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'coo_array' object is not subscriptable

但是，其他格式，例如压缩稀疏行（CSR） csr_array 支持切片和元素索引：

>>> sparse.tocsr()[2, 2]
5

有时，scipy.sparse 会返回与输入稀疏矩阵格式不同的稀疏矩阵格式。例如，两个 COO 格式稀疏数组的点积将是一个 CSR 格式数组：

>>> sparse @ sparse.T
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 3)>

这种变化发生的原因是 scipy.sparse 会改变输入稀疏数组的格式，以便使用最高效的计算方法。

scipy.sparse 模块包含以下格式，每种格式都有其独特的优缺点：

  • 块稀疏行（BSR）数组 scipy.sparse.bsr_array，当数组中包含数据的块是连续的时，这种格式最为合适。

  • 坐标（COO）数组 scipy.sparse.coo_array，提供了一种简单的方式来构建稀疏数组并在原地修改它们。COO 还可以快速转换为其他格式，如 CSR、CSC 或 BSR。

  • 压缩稀疏行（CSR）数组 scipy.sparse.csr_array，对于快速算术运算、向量乘积和按行切片最为有用。

  • 压缩稀疏列（CSC）数组 scipy.sparse.csc_array，对于快速算术运算、向量乘积和按列切片最为有用。

  • 对角线（DIA）数组 scipy.sparse.dia_array，只要数据主要出现在数组的对角线上，这种格式对于高效存储和快速算术运算非常有用。

  • 键字典（DOK）数组 scipy.sparse.dok_array，对于快速构建和单个元素访问非常有用。

  • 列表的列表（LIL）数组 scipy.sparse.lil_array，对于快速构建和修改稀疏数组非常有用。

关于每种稀疏数组格式的优缺点的更多信息可以在 它们的文档 中找到。 scipy.sparse 数组的所有格式都可以直接从 numpy.ndarray 构建。然而，某些稀疏格式也可以通过不同的方式构建。每种稀疏数组格式都有不同的优势，这些优势在每个类中都有文档说明。例如，构建稀疏数组的最常见方法之一是从各个 row、column 和 data 值构建稀疏数组。对于我们之前的数组：

>>> dense
array([[1, 0, 0, 2],
       [0, 4, 1, 0],
       [0, 0, 5, 0]])

row、column 和 data 数组描述了稀疏数组中存在条目的行、列和值：

>>> row = [0,0,1,1,2]
>>> col = [0,3,1,2,2]
>>> data = [1,2,4,1,5]

使用这些，我们现在可以定义一个稀疏数组，而不需要先构建一个密集数组：

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

不同的类有不同的构造函数，但 scipy.sparse.csr_array、scipy.sparse.csc_array 和 scipy.sparse.coo_array 允许这种构建方式。

稀疏数组、隐式零和重复项#

稀疏数组之所以有用，是因为它们代表了许多值*隐式地*，而不存储实际的占位符值。在 scipy.sparse 中，用于表示“无数据”的值是一个*隐式零*。当需要*显式零*时，这可能会引起混淆。例如，在 scipy.sparse.csgraph 的 图方法 中，我们通常需要能够区分（A）连接节点 i 和 j 且权重为零的链接和（B）节点 i 和 j 之间没有链接。稀疏矩阵可以做到这一点，只要我们记住*显式*和*隐式*零的区别。 例如，在我们之前的 csr 数组中，我们可以通过在 data 列表中包含它来包含一个显式零。让我们将数组中最后一行的最后一个条目视为一个 显式零：

>>> row = [0,0,1,1,2,2]
>>> col = [0,3,1,2,2,3]
>>> data = [1,2,4,1,5,0]

然后，我们的稀疏数组将有 六个 存储的元素，而不是五个：

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

“额外”的元素是我们的 显式零。当转换回密集数组时，两者仍然是相同的，因为密集数组显式表示 所有内容：

>>> csr.todense()
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])

但是，对于稀疏算术、线性代数和图方法，2,3 处的值将被视为 显式零。要移除此显式零，我们可以使用 csr.eliminate_zeros() 方法。这将对稀疏数组 就地 操作，并移除任何零值存储的元素：

>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>
>>> csr.eliminate_zeros()
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

在 csr.eliminate_zeros() 之前，有六个存储的元素。之后，只有五个存储的元素。

另一个复杂点来自于在构建稀疏数组时如何处理 重复项。当我们在构建稀疏数组时，row,col 处有两个或多个条目时，就会发生 重复项。这通常在使用 data、row 和 col 向量构建稀疏数组时发生。例如，我们可能在前一个数组中表示 1,1 处的重复值：

>>> row = [0,0,1,1,1,2]
>>> col = [0,3,1,1,2,2]

>>> data = [1,2,1,3,1,5]

在这种情况下，我们可以看到在最终数组中，有两个 data 值对应于 1,1 位置。scipy.sparse 将分别存储这些值：

>>> dupes = sp.sparse.coo_array((data, (row, col)))
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

请注意，尽管只有五个唯一的数据位置，但这个稀疏数组中存储了六个元素。当这些数组转换回稠密数组时，重复的值会被求和。因此，在位置 1,1 处，稠密数组将包含重复存储条目的总和，即 1 + 3：

>>> dupes.todense()
array([[1, 0, 0, 2],
      [0, 4, 1, 0],
      [0, 0, 5, 0]])

要在稀疏数组本身中去除重复值，从而减少存储的元素数量，我们可以使用 .sum_duplicates() 方法：

>>> dupes.sum_duplicates()
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

现在我们的稀疏数组中只有五个存储的元素，并且它与我们在此指南中一直使用的数组完全相同：

>>> dupes.todense()
array([[1, 0, 0, 2],
       [0, 4, 1, 0],
       [0, 0, 5, 0]])

规范格式#

几种稀疏数组格式具有“规范格式”，以允许更高效的操作。 通常这些格式包括以下限制：

  • 任何值都没有重复条目

  • 排序的索引

具有规范形式的类包括：coo_array、csr_array、csc_array 和 bsr_array。 有关每个规范表示的详细信息，请参阅这些类的文档字符串。

要检查这些类的实例是否处于规范形式，请使用 .has_canonical_format 属性：

>>> coo = sp.sparse.coo_array(([1, 1, 1], ([0, 2, 1], [0, 1, 2])))
>>> coo.has_canonical_format
False

要将实例转换为规范形式，请使用 .sum_duplicates() 方法：

>>> coo.sum_duplicates()
>>> coo.has_canonical_format
True

稀疏数组的下一步操作#

稀疏数组类型在处理大型、几乎为空的数组时最为有用。具体来说，稀疏线性代数 和 稀疏图方法 在这些情况下效率提升最大。

On this page