专栏首页ATYUN订阅号【学术】一篇关于机器学习中的稀疏矩阵的介绍

【学术】一篇关于机器学习中的稀疏矩阵的介绍

AiTechYun

编辑:Yining

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

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

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

教程概述

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

  • 稀疏矩阵
  • 稀疏的问题
  • 机器学习中的稀疏矩阵
  • 处理稀疏矩阵
  • 在Python中稀疏矩阵

稀疏矩阵

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

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

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

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

sparsity = count zero elements / total elements

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

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()函数将其转换为一个稀疏矩阵。

在下面的例子中,我们将一个3×6的稀疏矩阵定义为一个稠密数组,将它转换为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提供了你可以直接使用的实现。

本文分享自微信公众号 - ATYUN订阅号(atyun_com)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Diffbot启动了基于AI的知识图谱:包含1万亿个有关人类、地点和事物的事实

    如果你曾经在谷歌搜索名人,著名地标或之前的产品,那么你可能会遇到有时位于结果页右侧的信息框,充满了谷歌知识图谱的信息,这是一个实体数据库,用于增强网络和Goog...

    AiTechYun
  • 使用NumPy介绍期望值,方差和协方差

    AiTechYun 编辑:yuxiangyu 基础统计是应用机器学习中的有力工具,它可以更好地理解数据。而且,它也为更先进的线性代数运算和机器学习方法奠定了基础...

    AiTechYun
  • 【干货】用于机器学习的线性代数速查表

    NumPy,Python的数值计算库,它提供了许多线性代数函数。对机器学习从业人员用处很大。 在这篇文章中,你将看到对于机器学习从业者非常有用的处理矢量和矩阵的...

    AiTechYun
  • 数据分析与数据挖掘 - 06线性代数

    导数是高等数学中非常重要的知识点,也是人工智能的算法应用中比较常用的一个知识,这一章我们的重点就是讲解一下导数和其求导法则。首先我们来看一下导数的基本概念:函数...

    马一特
  • 齐次方程到矩阵(番外篇)

         最近做题,老是遇到了一些公式比如An=An-1+An-2,然后给你一个巨大n的数据,要你求An的值,然后以前做起来,还是比较的顺手的,但是时间抹去了记...

    Gxjun
  • 吹弹牛皮之Unity 引擎基础 - 矩阵(三)

    上图中展示了p,q两个基向量(单位向量)绕原点旋转后得到的新基向量p'和q'。根据勾股定理有:

    用户7698595
  • 吹弹牛皮之Unity 引擎基础 - 矩阵(一)

    沉迷于硬笔的练习偷懒了很长时间。过去的7月份仅仅更新了一篇文章,实在是深表遗憾。接着之前的向量篇小菜继续向下探索。谢谢大家长久来的鼓励和支持。

    用户7698595
  • 一起来学matlab-matlab学习笔记10 10_1一般运算符

    本文为matlab自学笔记的一部分,之所以学习matlab是因为其真的是人工智能无论是神经网络还是智能计算中日常使用的,非常重要的软件。也许最近其带来的一...

    DrawSky
  • 吴恩达机器学习笔记18-逆矩阵、矩阵转置

    “Linear Algebra review(optional)——Inverse and transpose”

    讲编程的高老师
  • 吴恩达机器学习笔记16-矩阵与矩阵的乘法

    “Linear Algebra review(optional)——Matrix-matrix multiplication”

    讲编程的高老师

扫码关注云+社区

领取腾讯云代金券