稀疏数组 (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]
在这种情况下,我们可以看到在最终数组的 1,1
位置对应着两个 data
值。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
稀疏数组的后续步骤#
稀疏数组类型在处理大型、几乎为空的数组时最有用。具体来说,在这些情况下,稀疏线性代数 和 稀疏图方法 在效率方面改进最大。