稀疏矩阵定义

百度百科:在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。简单来说,稀疏矩阵就是绝大部分都是0的矩阵,只包含很少的非零值.

比如,

image.png

上述稀疏矩阵非零元素有9个,26个零值.稀疏性是74%.

稀疏矩阵因为绝大部分都是0元素,如果我们仍然按照普通方式存储,无疑会浪费很多空间;同时如果进行运算时,0元素对最终结果也没有帮助,增加了许多无效计算. 因此,我们需要设计出新的存储方式,或者说数据结构来存储稀疏矩阵.比较常见的有:

DOK:Dictionary of keys.将非零元素的坐标(row,column)作为key,非零元素值作为value;同时只存储非零元素值,零值被扔掉.可以以任意顺序逐渐构建稀疏矩阵;但是按某种顺序访问非零元素时比较困难.通常用来构建矩阵,然后再把矩阵转换成别的方式.
COO:Coordinate list,坐标格式.三个数组row,col,value,分别存储非零元素坐标的行,列以及非零值.理论上稀疏矩阵中的元素在存储时顺序是任意的,但是为了方便元素访问,存储时先按照先左后右,先上后下顺序进行存储(left to right, top to buttom).
CSR:压缩稀疏行
CSC:压缩稀疏列,和CSR类似.

稀疏矩阵存储

对于稀疏矩阵的存储,为了达到压缩的目的(节省存储空间),只存储非0元素值,但是也要保留非零元素的位置,方便恢复.所以,我们存储时不仅存储非零元素值,同时存储其坐标位置(row,column). 针对这两者的存储,会出现不同的设计方案.这里主要介绍COO,CSR和CSC存储格式.

COO

我们使用三个数组row,column和data分别用来存储非零元素坐标的row_index,col_index,以及数值.比如:

image

NNO:The number of nonzero.矩阵非零元素个数. 三个数组的长度都是NNO.data[i]在原稀疏矩阵中的坐标为(row[i],col[i]]).

>>> from scipy.sparse import *
>>> 
>>> row = [0,0,1,1,2,2,2,3,3]
>>> col = [0,1,1,2,0,2,3,1,3]
>>> data = [1,7,2,8,5,3,9,6,4]
>>> import numpy as np
>>> coo = coo_matrix((data,(row,col)),shape=(4,4),dtype=np.int)
>>> coo
<4x4 sparse matrix of type '<class 'numpy.int64'>'
    with 9 stored elements in COOrdinate format>
>>> coo.todense()
matrix([[1, 7, 0, 0],
        [0, 2, 8, 0],
        [5, 0, 3, 9],
        [0, 6, 0, 4]])

可以发现,这种存储方式中,row数组和column数组中有一定的重复元素.我们是否可以针对这个冗余特性进一步进行压缩?之后出现CSR,CSC,分别是对row数组和column数组进行了压缩.

CSR

NNO:稀疏矩阵非零元素个数;

M:稀疏矩阵行数;

N:稀疏矩阵列数.

对COO稀疏矩阵存储格式的三个数组中的row数组进行压缩.其他两个数组保持不变;三个数组分别是row_ptr,columns和data.其中columns和data数组长度均为NNO(矩阵的非零元素个数).如何对COO的row进行压缩?

row_ptr存储的是每行的第一个非零元素距离稀疏矩阵第一个元素的偏移位置;

row_ptr:长度为M+1.
row_ptr[0] = 0
row_ptr[i] = row_ptr[i-1] + nno(rows[i-1])[第i-1行非零元素个数]
row_ptr[M] = NNO.

由row_ptr我们可以知道每行非零元素在data中的index范围.第i行的非零元素为data[row_ptr[i]:row_ptr[i+1]],对data数组的切片,不包含data[row_ptr[i+1]];同时第i行非零元素的col坐标分别为columns[row_ptr[i]:row_ptr[i+1]];对data和columns的访问相似,index是相同的.

image

如上图中,第0行非零元素在data中是data[0:2],就是1,7;列坐标为columns[0:2],就是0,1,第1行非零元素为data[2:4],有两个元素2和8,列坐标分别为columns[2:4],1和2.

>>> row_ptr = [0,2,4,7,9]
>>> col = [0,1,1,2,0,2,3,1,3]
>>> data = [1,7,2,8,5,3,9,6,4]
>>> csr = csr_matrix((data,col,row_ptr),shape=(4,4),dtype=np.int)# 被压缩的数组放在最后一个
>>> csr.todense()
matrix([[1, 7, 0, 0],
        [0, 2, 8, 0],
        [5, 0, 3, 9],
        [0, 6, 0, 4]])

方便进行行操作.