稀疏矩阵

文章目录

• 稀疏矩阵的定义
• 稀疏矩阵在计算中的处理
• 稀疏矩阵常用的存储格式
• Coordinate（COO）
• 行压缩格式 Compressed Sparse Row（CSR）
• 列压缩格式 Compressed Sparse Column（CSC）
• ELLPACK（ELL）
• Hybrid（HYB）
• 对角线存储格式（DIA）
• Python中scipy.sparse库
• 不同存储模式在sparse库中的对应

稀疏矩阵的定义

矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素在矩阵内的分布没有规律。通常认为矩阵中非零元素的总是比上矩阵中所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵（Sparse matrix），改比值成为这个矩阵的稠密度。

稀疏矩阵几乎产生于所有的大型科学工程计算领域，包括计算流体力学、统计物理、电路模拟、图像处理、纳米材料计算等。

稀疏矩阵在计算中的处理

由稀疏矩阵的定义可知，在稀疏矩阵中非零元素较少。因此可以采用只存储非零元素的方法对矩阵进行压缩。

举例说明：一个二维数组$A_{m \times n}$Am×n​ ，假设其中每个元素有$L$L 个字节，那么存储整个矩阵需要$m \times n \times L$m×n×L 的空间，但是这些空间中大部分的存放的是“0”，从而会造成大量的空间浪费。根据稀疏矩阵定义，理想情况下最少只需要存储 $0.05 \times m \times n \times L$0.05×m×n×L 即可表示该矩阵。

稀疏矩阵常用的存储格式

Coordinate（COO）

如图所示，Coordinate存储方式是最简单的存储方式，每一个元素使用三元组的形式进行表示，分别是（行号，列号，数据内容）。对应于右边图中的一列。这种存储方式虽然简单，但是因为其记录的信息比较多，因此在空间上不是最优的。

行压缩格式 Compressed Sparse Row（CSR）

需要注意的是，CSR不是三元组的格式，而是一种整体的编码方式。其中，列号column indices和数值values是一一对应的，表示一个元素以及它所在的列号。而行偏移 row offsets是通过编码的形式表示的。其具体含义为：行偏移数组的最后一个元素表示在当前稀疏矩阵中，总共有多少个元素；行偏移数组中其他元素，表示某一行的第一个元素在所有数值中的位置。

如上图所示，假设 $i$i 表示第 $i$i 行，则当前行中的元素个数 $num_i$numi​ 为： $num_i = row\_offset[i+1] - row\_offset[i]$numi​=row_offset[i+1]−row_offset[i]

列压缩格式 Compressed Sparse Column（CSC）

列压缩格式与行压缩格式是相对应的，针对CSR中的矩阵，若采用CSC的格式，其存储方式如下：

Column Offsets： 0 2 5 7 9

Row Indices： 0 2 0 1 3 1 2 2 3

Values： 1 5 7 2 6 8 3 9 4

ELLPACK（ELL）

ELLPACK用两个与原矩阵行相同的矩阵分别存储列号（column indices）和数值（values）。如果没有元素了可以用 * 代替。特别地，如果某一样本（特定一行）所包含的属性信息过多，会导致列号矩阵和数值矩阵变得异常的“胖”，其他行结尾存在许多 * 标记，浪费存储空间。

Hybrid（HYB）

为了解决单独ELL存储时出现的：某一个样本（某一特定行）属性过多（非零元素过多）导致的存储空间浪费（补太多的符号 *），我们将ELL存储和COO存储结合。设定一个最大列数设定ELL存储时的数值矩阵和列号矩阵。将多余的元素再通过COO存储方式以三元组的方式进行存储。

对角线存储格式（DIA）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NBHM69cR-1597199778743)(H:\02 Machine Learning\学习资料\稀疏矩阵的介绍.assets\1785198-20191120202019052-206129904.png)]

顾名思义，对角线储存法以每一对角线的元素为对线，将其按列存入矩阵中。按照对角线方式存储时，存储矩阵的列代表对角线，行代表行。省略全零的对角线。这里的行对应行，所以5 、6是分别在第三行第四行的，前面补上无效元素*。按照这种方式存储矩阵，如果源实矩阵就是一个对角性很好的矩阵那么压缩效率会非常高。

Python中scipy.sparse库

python不能够自动创建稀疏矩阵，因此其必须要用scipy库中的特殊命令得到稀疏矩阵。

sparse模块的官方document地址：http://docs.scipy.org/doc/scipy/reference/sparse.html

不同存储模式在sparse库中的对应

bsr_matrix(arg1[, shape, dtype,copy, blocksize]) Block Sparse Row matrix

coo_matrix(arg1[, shape, dtype,copy]) A sparse matrix in COOrdinate format.

csc_matrix(arg1[, shape, dtype,copy]) Compressed Sparse Column matrix

csr_matrix(arg1[, shape, dtype,copy]) Compressed Sparse Row matrix

dia_matrix(arg1[, shape, dtype,copy]) Sparse matrix with DIAgonal storage

dok_matrix(arg1[, shape, dtype,copy]) Dictionary Of Keys based sparse matrix.

lil_matrix(arg1[, shape, dtype,copy]) Row-based linked list sparse matrix