稀疏矩阵的类型

scipy.sparse中提供了多种格式的稀疏矩阵, 每种都有自己的特点, 根据实际情况与需要选择使用. 因此要充分了解各种稀疏矩阵的特点.

from scipy.sparse import csr_matrix, csc_matrix, coo_matrix, dia_matrix, dok_matrix, lil_matrix

CSR Matrix

Compressed Sparse Row matrix.

初始化方法

• csr_matrix(D)

  • D表示dense matrix

• csr_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocsr()

• csr_matrix((M, N), [dtype])

  • 创建一个shape为(M, N)的空的稀疏矩阵

• csr_matrix((data, (row_ind, col_ind)), [shape=(M, N)])

  • data, row_ind, col_ind对应着a[row_ind[k], col_ind[k]] = data[k]

  • 如果不指定shape, 则从传入的参数中自动推断

• csr_matrix((data, indices, indptr), [shape=(M, N)])

  • 这种形式就是CSR的标准形式

  • 第i行的有值的列索引存储在indices[indptr[i]:indptr[i+1]]

  • 对应的值存储在data[indptr[i]:indptr[i+1]]

  • indptr相当于存储着每一行起始终止位置. 因此CSR这种形式是把所有的行数据存储在一个扁平列表中, 因此需要记录分隔位置.

indptr = np.array([0, 2, 3, 6])
indices = np.array([0, 2, 2, 0, 1, 2])
data = np.array([1, 2, 3, 4, 5, 6])
csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()
array([[1, 0, 2],
       [0, 0, 3],
       [4, 5, 6]])

优点

• 数学计算效率高, 加乘等

• 行切片效率高

• 向量, 矩阵乘法效率高

缺点

• 列切片慢

• 转换成其他格式的稀疏矩阵慢(如LIL, DOK)

CSC Matrix

Compressed Sparse Column matrix.

初始化方法

• csc_matrix(D)

  • D表示dense matrix

• csc_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocsc()

• csc_matrix((M, N), [dtype])

  • 创建一个shape为(M, N)的空的稀疏矩阵

• csc_matrix((data, (row_ind, col_ind)), [shape=(M, N)])

  • data, row_ind, col_ind对应着a[row_ind[k], col_ind[k]] = data[k]

  • 如果不指定shape, 则从传入的参数中自动推断

• csc_matrix((data, indices, indptr), [shape=(M, N)])

  • 这种形式就是CSR的标准形式

  • 第i列的有值的行索引存储在indices[indptr[i]:indptr[i+1]]

  • 对应的值存储在data[indptr[i]:indptr[i+1]]

  • indptr相当于存储着每一列起始终止位置. 因此CSR这种形式是把所有的列数据存储在一个扁平列表中, 因此需要记录分隔位置.

indptr = np.array([0, 2, 3, 6])
indices = np.array([0, 2, 2, 0, 1, 2])
data = np.array([1, 2, 3, 4, 5, 6])
csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()
array([[1, 0, 4],
       [0, 0, 5],
       [2, 3, 6]])

优点

• 数学计算效率高, 加乘等

• 列切片效率高

• 向量, 矩阵乘法效率高

缺点

• 行切片慢

• 转换成其他格式的稀疏矩阵慢(如LIL, DOK)

COO Matrix

A sparse matrix in COOrdinate format.

初始化方法

• coo_matrix(D)

  • D表示dense matrix

• coo_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocoo()

• coo_matrix((data, (row_ind, col_ind)), [shape=(M, N)])

  • data, row_ind, col_ind对应着a[row_ind[k], col_ind[k]] = data[k]

>>> # Constructing a matrix using ijv format
>>> row  = np.array([0, 3, 1, 0])
>>> col  = np.array([0, 3, 1, 2])
>>> data = np.array([4, 5, 7, 9])
>>> coo_matrix((data, (row, col)), shape=(4, 4)).toarray()
array([[4, 0, 9, 0],
       [0, 7, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 5]])

>>> # Constructing a matrix with duplicate indices
>>> row  = np.array([0, 0, 1, 3, 1, 0, 0])
>>> col  = np.array([0, 2, 1, 3, 1, 0, 0])
>>> data = np.array([1, 1, 1, 1, 1, 1, 1])
>>> coo = coo_matrix((data, (row, col)), shape=(4, 4))
>>> # Duplicate indices are maintained until implicitly or explicitly summed
>>> np.max(coo.data)
1
>>> coo.toarray()
array([[3, 0, 1, 0],
       [0, 2, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 1]])

优点

• 与各种形式的稀疏矩阵之间的转换高效, 特别是与csr/csc之间相互的转换

• 输入时允许有重复位置的输入

缺点

• 不支持切片

• 不支持数学运算

应用场景

• COO是一种快速创建稀疏矩阵的格式, 新建稀疏矩阵很高效

• 一般是使用COO创建稀疏矩阵, 然后转为CSR或CSC格式进行矩阵的计算

• 转换成CSR或CSC格式时, 重复位置的元素会被加和

LIL Matrix

Row-based linked list sparse matrix

数据格式

每行为一个array, 这个array的内容为排序好的非0位置的索引, 对应的data的array要与索引保持相同的格式且对齐.

应用场景

这是用来增量添加来创建稀疏矩阵的格式. 注意在向已有的矩阵添加元素时, 要先排序, 然后再顺序添加.

这里的添加指的是使用切片指定添加.

初始化方法

• lil_matrix(D)

  • D表示dense matrix

• lil_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocoo()

• lil_matrix((M, N), [dtype])

  • 创建一个shape为(M, N)的空的稀疏矩阵

优点

• 支持灵活的切片

• 转换成其他稀疏矩阵很高效

缺点

• 两个LIL类型的稀疏矩阵之间的加法很慢, 要先转换成CSR/CSC格式

• 列切片很慢

• 矩阵乘积很慢

DOK Matrix

Dictionary Of Keys based sparse matrix.

应用场景

这也是一种创建后增量增补数据的高效格式, 与LIL的区别在于保存数据的形式, LIL的是列表形式, DOK是字典的形式.

初始化方法

• dok_matrix(D)

  • D表示dense matrix

• dok_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocoo()

• dok_matrix((M, N), [dtype])

  • 创建一个shape为(M, N)的空的稀疏矩阵

优点

• 由于是使用字典格式保存每个位置的值, 因此对单个值的查询和赋值都是在O(1)内完成的, 非常高效.

DIA Matrix

Sparse matrix with DIAgonal storage.

初始化方法

• dia_matrix(D)

  • D表示dense matrix

• dia_matrix(S)

  • S表示其他的稀疏矩阵, 相当于S.tocoo()

• dia_matrix((M, N), [dtype])

  • 创建一个shape为(M, N)的空的稀疏矩阵

• dia_matrix((data, offsets), shape=(M, N))

  • 见例子Diagonal Format (DIA)