今天在使用lightfm的时候,输入的数据类型可以是稀疏矩阵,一开始尝试先构造列表然后类型转换为系数矩阵,发现运行到中途进程被kill掉了,才发现这个dok_matrix神奇的类
1.sparse模块初探
python中scipy模块中,有一个模块叫sparse模块,就是专门为了解决稀疏矩阵而生。本文的大部分内容,其实就是基于sparse模块而来的。 第一步自然就是导入sparse模块
<span class="hljs-prompt">>>> </span><span class="hljs-keyword">from</span> scipy <span class="hljs-keyword">import</span> sparse
然后help一把,先来看个大概
>>> <span class="hljs-built_in">help</span>(sparse)
直接找到我们最关心的部分:
Usage information ================= There are <span class="hljs-constant">seven</span> available sparse matrix types: <span class="hljs-number">1.</span> csc_matrix: Compressed Sparse Column <span class="hljs-built_in">format</span> <span class="hljs-number">2.</span> csr_matrix: Compressed Sparse Row <span class="hljs-built_in">format</span> <span class="hljs-number">3.</span> bsr_matrix: Block Sparse Row <span class="hljs-built_in">format</span> <span class="hljs-number">4.</span> lil_matrix: List <span class="hljs-operator">of</span> Lists <span class="hljs-built_in">format</span> <span class="hljs-number">5.</span> dok_matrix: Dictionary <span class="hljs-operator">of</span> Keys <span class="hljs-built_in">format</span> <span class="hljs-number">6.</span> coo_matrix: COOrdinate <span class="hljs-built_in">format</span> (aka IJV, triplet <span class="hljs-built_in">format</span>) <span class="hljs-number">7.</span> dia_matrix: DIAgonal <span class="hljs-built_in">format</span> To construct <span class="hljs-operator">a</span> matrix efficiently, use either dok_matrix <span class="hljs-operator">or</span> lil_matrix. The lil_matrix class supports basic slicing <span class="hljs-operator">and</span> fancy indexing <span class="hljs-operator">with</span> <span class="hljs-operator">a</span> similar syntax <span class="hljs-built_in">to</span> NumPy arrays. As illustrated below, <span class="hljs-operator">the</span> COO <span class="hljs-built_in">format</span> may also be used <span class="hljs-built_in">to</span> efficiently construct matrices. To perform manipulations such <span class="hljs-keyword">as</span> multiplication <span class="hljs-operator">or</span> inversion, <span class="hljs-keyword">first</span> <span class="hljs-built_in">convert</span> <span class="hljs-operator">the</span> matrix <span class="hljs-built_in">to</span> either CSC <span class="hljs-operator">or</span> CSR <span class="hljs-built_in">format</span>. The lil_matrix <span class="hljs-built_in">format</span> is row-based, so conversion <span class="hljs-built_in">to</span> CSR is efficient, whereas conversion <span class="hljs-built_in">to</span> CSC is less so. All conversions <span class="hljs-operator">among</span> <span class="hljs-operator">the</span> CSR, CSC, <span class="hljs-operator">and</span> COO formats are efficient, linear-<span class="hljs-built_in">time</span> operations.
通过这段描述,我们对sparse模块就有了个大致的了解。sparse模块里面有7种存储稀疏矩阵的方式。接下来,我们对这7种方式来做个一一介绍。
2.coo_matrix
coo_matrix是最简单的存储方式。采用三个数组row、col和data保存非零元素的信息。这三个数组的长度相同,row保存元素的行,col保存元素的列,data保存元素的值。一般来说,coo_matrix主要用来创建矩阵,因为coo_matrix无法对矩阵的元素进行增删改等操作,一旦矩阵创建成功以后,会转化为其他形式的矩阵。
>>> row = [<span class="hljs-number">2</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>,<span class="hljs-number">2</span>] >>> col = [<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">2</span>,<span class="hljs-number">3</span>] >>> c = sparse.coo_matrix((data,(row,col)),shape=(<span class="hljs-number">5</span>,<span class="hljs-number">6</span>)) >>> <span class="hljs-built_in">print</span> c.toarray() <span class="hljs-string">[[0 0 0 0 0 0] [0 0 0 0 0 0] [0 0 0 5 2 0] [0 0 3 0 0 0] [0 0 0 0 0 0]]</span>
稍微需要注意的一点是,用coo_matrix创建矩阵的时候,相同的行列坐标可以出现多次。矩阵被真正创建完成以后,相应的坐标值会加起来得到最终的结果。
3.dok_matrix与lil_matrix
dok_matrix和lil_matrix适用的场景是逐渐添加矩阵的元素。doc_matrix的策略是采用字典来记录矩阵中不为0的元素。自然,字典的key存的是记录元素的位置信息的元祖,value是记录元素的具体值。
>>> import numpy as np >>> from scipy.sparse import dok_matrix >>> S = dok_matrix((<span class="hljs-number">5</span>, <span class="hljs-number">5</span>), dtype=np.float32) >>> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">5</span>): <span class="hljs-keyword">...</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">5</span>): <span class="hljs-keyword">...</span> S[i, j] = i + j <span class="hljs-keyword">...</span> >>> print S.toarray() [[ <span class="hljs-number">0.</span> <span class="hljs-number">1.</span> <span class="hljs-number">2.</span> <span class="hljs-number">3.</span> <span class="hljs-number">4.</span>] [ <span class="hljs-number">1.</span> <span class="hljs-number">2.</span> <span class="hljs-number">3.</span> <span class="hljs-number">4.</span> <span class="hljs-number">5.</span>] [ <span class="hljs-number">2.</span> <span class="hljs-number">3.</span> <span class="hljs-number">4.</span> <span class="hljs-number">5.</span> <span class="hljs-number">6.</span>] [ <span class="hljs-number">3.</span> <span class="hljs-number">4.</span> <span class="hljs-number">5.</span> <span class="hljs-number">6.</span> <span class="hljs-number">7.</span>] [ <span class="hljs-number">4.</span> <span class="hljs-number">5.</span> <span class="hljs-number">6.</span> <span class="hljs-number">7.</span> <span class="hljs-number">8.</span>]]
lil_matrix则是使用两个列表存储非0元素。data保存每行中的非零元素,rows保存非零元素所在的列。这种格式也很适合逐个添加元素,并且能快速获取行相关的数据。
>>> from scipy.sparse import lil_matrix >>> l = lil_matrix((<span class="hljs-number">6</span>,<span class="hljs-number">5</span>)) >>> l[<span class="hljs-number">2</span>,<span class="hljs-number">3</span>] = <span class="hljs-number">1</span> >>> l[<span class="hljs-number">3</span>,<span class="hljs-number">4</span>] = <span class="hljs-number">2</span> >>> l[<span class="hljs-number">3</span>,<span class="hljs-number">2</span>] = <span class="hljs-number">3</span> >>> <span class="hljs-built_in">print</span> l.toarray() <span class="hljs-string">[[ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 1. 0.] [ 0. 0. 3. 0. 2.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.]]</span> >>> <span class="hljs-built_in">print</span> l.data <span class="hljs-string">[[] [] [1.0] [3.0, 2.0] [] []]</span> >>> <span class="hljs-built_in">print</span> l.rows <span class="hljs-string">[[] [] [3] [2, 4] [] []]</span>
由上面的分析很容易可以看出,上面两种构建稀疏矩阵的方式,一般也是用来通过逐渐添加非零元素的方式来构建矩阵,然后转换成其他可以快速计算的矩阵存储方式。
4.dia_matrix
这是一种对角线的存储方式。其中,列代表对角线,行代表行。如果对角线上的元素全为0,则省略。
如果原始矩阵是个对角性很好的矩阵那压缩率会非常高。
找了网络上的一张图,大家就很容易能看明白其中的原理。
5.csr_matrix与csc_matrix
csr_matrix,全名为Compressed Sparse Row,是按行对矩阵进行压缩的。CSR需要三类数据:数值,列号,以及行偏移量。CSR是一种编码的方式,其中,数值与列号的含义,与coo里是一致的。行偏移表示某一行的第一个元素在values里面的起始偏移位置。
同样在网络上找了一张图,能比较好反映其中的原理。
看看在python里怎么使用:
>>> from scipy.sparse import csr_matrix >>> indptr = np.array([<span class="hljs-number">0</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">6</span>]) >>> indices = np.array([<span class="hljs-number">0</span>, <span class="hljs-number">2</span>, <span class="hljs-number">2</span>, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">2</span>]) >>> data = np.array([<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>, <span class="hljs-number">6</span>]) >>> csr_matrix((data, indices, indptr), shape=(<span class="hljs-number">3</span>, <span class="hljs-number">3</span>)).toarray() array(<span class="hljs-string">[[1, 0, 2], [0, 0, 3], [4, 5, 6]]</span>)
怎么样,是不是也不是很难理解。 我们再看看文档中是怎么说的
Notes <span class="hljs-string">| -----</span> <span class="hljs-string">|</span> <span class="hljs-string">| Sparse matrices can be used in arithmetic operations: they support</span> <span class="hljs-string">| addition, subtraction, multiplication, division, and matrix power.</span> <span class="hljs-string">|</span> <span class="hljs-string">| Advantages of the CSR format</span> <span class="hljs-string">| - efficient arithmetic operations CSR + CSR, CSR * CSR, etc.</span> <span class="hljs-string">| - efficient row slicing</span> <span class="hljs-string">| - fast matrix vector products</span> <span class="hljs-string">|</span> <span class="hljs-string">| Disadvantages of the CSR format</span> <span class="hljs-string">| - slow column slicing operations (consider CSC)</span> <span class="hljs-string">| - changes to the sparsity structure are expensive (consider LIL or DOK)</span>
不难看出,csr_matrix比较适合用来做真正的矩阵运算。 至于csc_matrix,跟csr_matrix类似,只不过是基于列的方式压缩的,不再单独介绍。
6.bsr_matrix
原矩阵A:
block_size为2时,分块表示的压缩矩阵E:
BSR的zero-based索引表示:
values = (1 02 1 6 7 8 2 1 4 5 1 4 3 0 0 7 2 0 0)
columns = (0 1 1 1 2)
pointerB= (0 2 3)
pointerE= (2 3 5)
分块压缩稀疏行格式(BSR) 通过四个数组确定:values,columns,pointerB, pointerE.
其中数组values:是一个实(复)数,包含原始矩阵A中的非0元,以行优先的形式保存;
数组columns:第i个整型元素代表块压缩矩阵E中第i列;
数组pointerB :第j个整型元素给出columns第j个非0块的起始位置;
数组pointerE:第j个整型元素给出columns数组中第j个非0块的终止位置。