稀疏矩阵的压缩方法

说明： 稀疏矩阵是机器学习中经常遇到的一种矩阵形式，特别是当矩阵行列比较多的时候，本着“节约”原则，必须要对其进行压缩。本节即演示一种常用的压缩方法，并说明其他压缩方式。

2.6.2 稀疏矩阵压缩

我们已经可以用Numpy中的二维数组表示矩阵或者Numpy中的np.mat()函数创建矩阵对象，这样就能够很方便地完成有关矩阵的各种运算。但是，对于稀疏矩阵而言，因为存在大量的零元素，每个零元素都要存储和参与运算，这样会造成大量的冗余和浪费。其实，只需要记录非零数字和位置，比如2.6.1中统计网站互相链接的矩阵中，只需要存储标记为1 的有关网站信息即可，标记为 0 的——这些是冗余——可以不保存。以矩阵乘法为例，0 乘以任何数都是 0 ，0 加上任何数都等于该数，所以这些计算可以不进行。

由此，就要修改矩阵的表示形式，只记录非零元素及其位置，没有记录的位置，都是零元素，这就是矩阵压缩。

★矩阵压缩的基本原则：

• 不重复存储相同元素
• 不存储零元素

下面详细介绍一种压缩稀疏行（Compressed Sparse Row，CSR）的矩阵压缩方法。

假设有三条文本，内容如下（为了方便，以英文为例）：

• 文档1：Short sentence
• 文档2：This is not a short sentence.
• 文档3：It is not raining. Is it?

去掉所有的标点符号，并且忽略大小写，然后将所有单词编排序号，如下图2-6-2所示。

图 2-6-2

然后将图2-6-2中的所有单词取出（去除重复单词），并统计每个文档中单词的出现次数（为了直观，此处以统计词的频数，而不是频率），如下表所示：

如果写成矩阵，则为：\pmb{T} = \begin{bmatrix}1&1&0&0&0&0&0&0\\1&1&1&1&1&1&0&0\\0&0&0&2&1&0&2&1\end{bmatrix} 按照上表和矩阵，可以得到三个文档中的每个单词出现的列索引，即矩阵中非零元素对应的列索引，组成一个列表：

ind = [0, 1, 0, 1, 2, 3, 4, 5, 3, 4, 6, 7]

一般称ind为列索引。

然后，将矩阵 \pmb{T} 中的所有非零数字（单词出现次数）也组成一个列表（与ind中的列索引对应）：

val = [1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1]

一般称val为值。

最后，观察稀疏矩阵 \pmb{T} ，第一行第一个非零元素之前共有 0 个非零元素；第二行的第一个非零元素之前共有 2 个非零元素，第三行的第一个非零元素之前共有 8

个非零元素；再记录矩阵中所有的非零数字个数 12 。通过 0、2、8、12 这几个数字，就能确定每行非零数字的数量。将这几个数字仍然组成一个列表：

ptr = [0, 2, 8, 12]

这样，我们通过ind、val、ptr 三个列表中的值，就能准确地记录了矩阵 \pmb{T} 中所有非零数字的位置和值，同时剔除了零元素。从而实现了对原有稀疏矩阵的压缩。从图2-6-3中，能够更直观地了解上述压缩过程和效果。

图 2-6-3

CSR 的“按行压缩”就体现在ptr所记录的结果中，其中的数值可以称为行偏移量，从中可以确定每行的非零数字个数。

与 CSR 对应的，还有按列压缩（Compressed Sparse column，CSC）。此外，还有其他压缩方式，如：COO、DIA、ELL、HYB等。本书在此对这些压缩方式不予以介绍，有兴趣的读者可以查阅有关资料。

在SciPy库中，提供了多种针对稀疏矩阵类（https://docs.scipy.org/doc/scipy/reference/sparse.html），分别实现不同的压缩方式：

下面以csr_matrix为例进行演示。

import numpy as np
from scipy.sparse import csr_matrix

m = csr_matrix((3, 8), dtype=np.int8)
m

# 输出
<3x8 sparse matrix of type '<class 'numpy.int8'>'
 with 0 stored elements in Compressed Sparse Row format>

以上创建了一个用变量 m引用的被压缩过的矩阵，从输出信息可知，其中保存了 0 个元素，也就意味着对应的稀疏矩阵中都是零元素。

m.toarray()   # 转换为数组

# 输出
array([[0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0]], dtype=int8)

显然，在上面所创建的是所有元素都是零的矩阵——常说的“空矩阵”。

row = np.array([0, 0, 2])
col = np.array([0, 2, 2])
data = np.array([1, 2, 3])
m2 = csr_matrix((data, (row, col)), shape=(3, 8))
m2

# 输出
<3x8 sparse matrix of type '<class 'numpy.int64'>'
 with 3 stored elements in Compressed Sparse Row format>

这里创建了一个 3×8 的稀疏矩阵，然后用CSR方式压缩，从返回信息中可知，在m2这个压缩矩阵中，保存了 3 个元素，与data中的值的数量一致。如果将这个压缩矩阵还原，则为：

m2.toarray()

# 输出
array([[1, 0, 2, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 3, 0, 0, 0, 0, 0]], dtype=int64)

为了便于对照理解前述对稀疏矩阵 \pmb{T} 的压缩分析，下面的程序中就创建了该矩阵，并用 CSR 压缩。

T = np.array([[1,1,0,0,0,0,0,0], [1,1,1,1,1,1,0,0], [0,0,0,2,1,0,2,1]])
csr_T = csr_matrix(T)
csr_T

# 输出
<3x8 sparse matrix of type '<class 'numpy.int64'>'
 with 12 stored elements in Compressed Sparse Row format>

变量csr_T引用的对象是对矩阵 \pmb{T} 施行 CSR 后的结果，从输出结果中可知，此对象是将原 3×8 的稀疏矩阵以CSR模式压缩为含有 12 个元素的对象。

可以通过csr_T的属性，分别得到行偏移量、列索引和值，请与前述分析对照，理解 CSR 的特点。

# 列索引
csr_T.indices

# 输出
array([0, 1, 0, 1, 2, 3, 4, 5, 3, 4, 6, 7], dtype=int32)

# 行偏移量
csr_T.indptr

# 输出
array([ 0,  2,  8, 12], dtype=int32)

# 值
csr_T.data

# 输出
array([1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1], dtype=int64)

其他压缩模式，读者可以结合 SciPy 中的类进行理解和使用。