什么是稀疏矩阵？

在矩阵中，如果数值为0的元素数目远远多于非0元素的数目，并且非0元素分布无规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。

大的稀疏矩阵在一般情况下是通用的，特别是在应用机器学习中，例如包含计数的数据、映射类别的数据编码，甚至在机器学习的整个子领域，如自然语言处理（NLP）。

本教程将向你介绍稀疏矩阵所呈现的问题，以及如何在Python中直接使用它们。

教程概述

本教程分为5部分;分别为:

• 稀疏矩阵


• 稀疏的问题


• 机器学习中的稀疏矩阵


• 处理稀疏矩阵


• 在Python中稀疏矩阵

稀疏矩阵

稀疏矩阵是一个几乎由零值组成的矩阵。稀疏矩阵与大多数非零值的矩阵不同，非零值的矩阵被称为稠密矩阵。

如果矩阵中的许多系数都为零，那么该矩阵就是稀疏的。对稀疏现象有兴趣是因为它的开发可以带来巨大的计算节省，并且在许多大的实践中都会出现矩阵稀疏的问题。

—第1页，《稀疏矩阵的直接教学方法》（Direct Methods for Sparse Matrices），第二版，2017年。

矩阵的稀疏性可以用一个得分来量化，也就是矩阵中零值的个数除以矩阵中元素的总个数。

sparsity = count zero elements / total elements

下面是一个小的3x6稀疏矩阵的例子。

1, 0, 0, 1, 0, 0

A = (0, 0, 2, 0, 0, 1)

 0, 0, 0, 2, 0, 0

这个例子在矩阵中的18个元素中有13个零值，这个矩阵的得分是0.722或约72%。

稀疏的问题

稀疏矩阵会导致空间复杂度和时间复杂度的问题。

空间复杂度
非常大的矩阵需要大量的内存，而我们想要处理的一些非常大的矩阵是稀疏的。

在实践中，大多数大型矩阵都是稀疏的——几乎所有的项都为零。

—第465页，《线性代数介绍》（Introduction to Linear Algebra），第五版，2016年。

一个非常大的矩阵的例子是，因为它太大而不能存储在内存中，这是一个显示从一个网站到另一个网站的链接的链接矩阵。一个更小的稀疏矩阵的例子可能是一个单词或术语的出现矩阵，在一本书中与所有已知的英语单词对应。

在这两种情况下，所包含的矩阵都是稀疏的，其零值比数据值要多。将这些稀疏矩阵表示为稠密矩阵的问题是对内存的要求，并且必须为矩阵中的每个32位或64位零值做出分配。

这显然是对内存资源的浪费，因为这些零值不包含任何信息。

时间复杂度
假设一个非常大的稀疏矩阵可以适应内存，我们将需要对这个矩阵执行操作。

简单地说，如果矩阵包含了大部分零值，也就是没有数据，那么在这个矩阵中执行操作可能需要很长时间，其中的大部分计算都需要或将零值相加或相乘。

在这样的问题上使用线性代数的一般方法是很浪费的，因为大多数O(N^3)算术运算都用于求解方程组或反转（invert）包含零操作数的矩阵。

—第75页，《数值分析：科学计算的艺术》（Numerical Recipes: The Art of Scientific Computing），第三版，2007年。

这是矩阵运算的时间复杂度增加的问题，随着矩阵的大小而增加。

当我们考虑到即使是琐碎的机器学习方法可能需要对每一行、列甚至整个矩阵进行许多操作时，这个问题也会变得更加复杂，从而导致执行时间大大延长。

机器学习中的稀疏矩阵

稀疏矩阵在应用机器学习中经常出现。

在这一节中，我们将讨论一些常见的例子，以激发你对稀疏问题的认识。

数据
稀疏矩阵在某些特定类型的数据中出现，最值得注意的是记录活动的发生或计数的观察。

三个例子包括:

• 用户是否在一个电影目录中有曾经看过的电影。


• 用户是否在一个产品目录中有已经购买过的产品。


• 在一个歌曲目录中数出收听过的歌曲的数量。

数据准备
在准备数据时，稀疏矩阵会出现在编码方案中。

三种常见的例子包括:

• 独热编码，用来表示分类数据为稀疏的二进制向量。


• 计数编码，用于表示文档中词汇的频率。


• TF-IDF编码，用于表示词汇中标准化的单词频率得分。

领域研究
机器学习中的一些领域必须开发专门的方法来解决稀疏问题，因为输入的数据几乎总是稀疏的。

三个例子包括:

• 用于处理文本文档的自然语言处理。


• 推荐系统在一个目录中进行产品使用。


• 当处理图像时计算机视觉包含许多黑色像素（black pixel）。

如果在语言模型中有100,000个单词，那么特征向量长度为100,000，但是对于一个简短的电子邮件来说，几乎所有的特征都是0。

—第22页，《人工智能：一种现代方法》（Artificial Intelligence: A Modern Approach），第三版，2009年。

处理稀疏矩阵

表示和处理稀疏矩阵的解决方案是使用另一个数据结构来表示稀疏数据。

零值可以被忽略，只有在稀疏矩阵中的数据或非零值需要被存储或执行。

多个数据结构可以用来有效地构造一个稀疏矩阵;下面列出了三个常见的例子。

• Dictionary of Keys。在将行和列索引映射到值时使用字典。


• List of Lists。矩阵的每一行存储为一个列表，每个子列表包含列索引和值。


• Coordinate List。一个元组的列表存储在每个元组中，其中包含行索引、列索引和值。

还有一些更适合执行高效操作的数据结构;下面列出了两个常用的示例。

• 压缩的稀疏行。稀疏矩阵用三个一维数组表示非零值、行的范围和列索引。


• 压缩的稀疏列。与压缩的稀疏行方法相同，除了列索引外，在行索引之前被压缩和读取。

被压缩的稀疏行，也称为CSR，通常被用来表示机器学习中的稀疏矩阵，因为它支持的是有效的访问和矩阵乘法。

在Python中稀疏矩阵

SciPy提供了使用多种数据结构创建稀疏矩阵的工具，以及将稠密矩阵转换为稀疏矩阵的工具。

许多在NumPy阵列上运行的线性代数NumPy和SciPy函数可以透明地操作SciPy稀疏数组。此外，使用NumPy数据结构的机器学习库也可以在SciPy稀疏数组上透明地进行操作，例如用于一般机器学习的scikit-learn和用于深度学习的Keras。

存储在NumPy数组中的稠密矩阵可以通过调用csr_matrix()函数将其转换为一个稀疏矩阵。

在下面的例子中，我们将一个3x6的稀疏矩阵定义为一个稠密数组，将它转换为CSR稀疏表示，然后通过调用todense()函数将它转换回一个稠密数组。

# dense to sparse

from numpy import array

from scipy.sparse import csr_matrix

# create dense matrix

A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])

print(A)

# convert to sparse matrix (CSR method)

S = csr_matrix(A)

print(S)

# reconstruct dense matrix

B = S.todense()

print(B)

运行该示例首先打印已定义的稠密数组，接着是CSR表示，然后是重新构建的稠密矩阵。

[[1 0 0 1 0 0]

 [0 0 2 0 0 1]

 [0 0 0 2 0 0]]

 

 (0, 0) 1

 (0, 3) 1

 (1, 2) 2

 (1, 5) 1

 (2, 3) 2

 

[[1 0 0 1 0 0]

 [0 0 2 0 0 1]

 [0 0 0 2 0 0]]

NumPy并没有提供一个函数来计算矩阵的稀疏性。

不过，我们可以很容易地计算出矩阵的密度，然后从一个矩阵中减去它。NumPy数组中的非零元素可以由count_nonzero()函数给出，数组中元素的总数可以由数组的大小属性给出。因此，数组的稀疏性可以被计算为：

sparsity = 1.0 - count_nonzero(A) / A.size

下面的例子演示了如何计算数组的稀疏性。

# calculate sparsity

from numpy import array

from numpy import count_nonzero

# create dense matrix

A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])

print(A)

# calculate sparsity

sparsity = 1.0 - count_nonzero(A) / A.size

print(sparsity)

运行这个例子首先打印出定义的稀疏矩阵，接着是矩阵的稀疏性。

[[1 0 0 1 0 0]

 [0 0 2 0 0 1]

 [0 0 0 2 0 0]]

 

0.7222222222222222

总结

在学习了这篇教程之后，你知道了：

• 稀疏矩阵几乎包含全部零值，并且与稠密矩阵不同。


• 你可能会在数据、数据准备和机器学习的子领域中遇到稀疏矩阵。


• 有许多有效的方法可以存储和使用稀疏矩阵，而SciPy提供了你可以直接使用的实现。