稀疏矩陣格式 coo_matrix

coo_matrix

是最簡(jiǎn)單的稀疏矩陣存儲(chǔ)方式，采用三元組(row, col, data)(或稱(chēng)為ijv format)的形式來(lái)存儲(chǔ)矩陣中非零元素的信息。

在實(shí)際使用中，一般coo_matrix用來(lái)創(chuàng)建矩陣，因?yàn)閏oo_matrix無(wú)法對(duì)矩陣的元素進(jìn)行增刪改操作；創(chuàng)建成功之后可以轉(zhuǎn)化成其他格式的稀疏矩陣（如csr_matrix、csc_matrix）進(jìn)行轉(zhuǎn)置、矩陣乘法等操作。

coo_matrix可以通過(guò)四種方式實(shí)例化，除了可以通過(guò)coo_matrix(D), D代表密集矩陣；coo_matrix(S), S代表其他類(lèi)型稀疏矩陣或者coo_matrix((M, N), [dtype])構(gòu)建一個(gè)shape為M*N的空矩陣，默認(rèn)數(shù)據(jù)類(lèi)型是d，還可以通過(guò)(row, col, data)三元組初始化：

>>> import numpy as np
>>> from scipy.sparse import coo_matrix
>>> _row  = np.array([0, 3, 1, 0])
>>> _col  = np.array([0, 3, 1, 2])
>>> _data = np.array([4, 5, 7, 9])
>>> coo = coo_matrix((_data, (_row, _col)), shape=(4, 4), dtype=np.int)
>>> coo.todense()  # 通過(guò)toarray方法轉(zhuǎn)化成密集矩陣(numpy.matrix)
>>> coo.toarray()  # 通過(guò)toarray方法轉(zhuǎn)化成密集矩陣(numpy.ndarray)
array([[4, 0, 9, 0],
       [0, 7, 0, 0],
       [0, 0, 0, 0],
       [0, 0, 0, 5]])

上面通過(guò)triplet format的形式構(gòu)建了一個(gè)coo_matrix對(duì)象，我們可以看到坐標(biāo)點(diǎn)(0,0)對(duì)應(yīng)值為4，坐標(biāo)點(diǎn)(1,1)對(duì)應(yīng)值為7等等，這就是coo_matrix。coo_matrix對(duì)象有很多方法，大多數(shù)是elementwise的操作函數(shù)；coo_matrix對(duì)象有以下屬性：

dtype dtype

矩陣中元素的數(shù)據(jù)類(lèi)型

shape 2-tuple

獲取矩陣的shape

ndim int

獲取矩陣的維度，當(dāng)然值是2咯

nnz

存儲(chǔ)值的個(gè)數(shù)，包括顯示聲明的零元素(注意)

data

稀疏矩陣存儲(chǔ)的值，是一個(gè)一維數(shù)組，即上面例子中的_data

row

與data同等長(zhǎng)度的一維數(shù)組，表征data中每個(gè)元素的行號(hào)

col

與data同等長(zhǎng)度的一維數(shù)組，表征data中每個(gè)元素的列號(hào)

在實(shí)際應(yīng)用中，coo_matrix矩陣文件通常存成以下形式，表示稀疏矩陣是coo_matrix(coordinate)，由13885行1列組成，共有949個(gè)元素值為非零，數(shù)據(jù)類(lèi)型為整形。

​ 下面給出coo_matrix矩陣文件讀寫(xiě)示例代碼，mmread()用于讀取稀疏矩陣，mmwrite()用于寫(xiě)入稀疏矩陣，mminfo()用于查看稀疏矩陣文件元信息。(這三個(gè)函數(shù)的操作不僅僅限于coo_matrix)

from scipy.io import mmread, mmwrite, mminfo
HERE = dirname(__file__)
coo_mtx_path = join(HERE, 'data/matrix.mtx')
coo_mtx = mmread(coo_mtx_path)
print(mminfo(coo_mtx_path))
# (13885, 1, 949, 'coordinate', 'integer', 'general')
# (rows, cols, entries, format, field, symmetry)
mmwrite(join(HERE, 'data/saved_mtx.mtx'), coo_mtx)

coo_matrix的優(yōu)點(diǎn)：

有利于稀疏格式之間的快速轉(zhuǎn)換（tobsr()、tocsr()、to_csc()、to_dia()、to_dok()、to_lil()）

允許又重復(fù)項(xiàng)（格式轉(zhuǎn)換的時(shí)候自動(dòng)相加）

能與CSR / CSC格式的快速轉(zhuǎn)換

coo_matrix的缺點(diǎn)：

不能直接進(jìn)行算術(shù)運(yùn)算

csr_matrix ​

csr_matrix，全稱(chēng)Compressed Sparse Row matrix，即按行壓縮的稀疏矩陣存儲(chǔ)方式，由三個(gè)一維數(shù)組indptr, indices, data組成。

這種格式要求矩陣元按行順序存儲(chǔ)，每一行中的元素可以亂序存儲(chǔ)。

那么對(duì)于每一行就只需要用一個(gè)指針表示該行元素的起始位置即可。

indptr存儲(chǔ)每一行數(shù)據(jù)元素的起始位置，indices這是存儲(chǔ)每行中數(shù)據(jù)的列號(hào)，與data中的元素一一對(duì)應(yīng)。

​

csr_matrix可用于各種算術(shù)運(yùn)算：它支持加法，減法，乘法，除法和矩陣冪等操作。

其有五種實(shí)例化方法，其中前四種初始化方法類(lèi)似coo_matrix，即通過(guò)密集矩陣構(gòu)建、通過(guò)其他類(lèi)型稀疏矩陣轉(zhuǎn)化、構(gòu)建一定shape的空矩陣、通過(guò)(row, col, data)構(gòu)建矩陣。

其第五種初始化方式這是直接體現(xiàn)csr_matrix的存儲(chǔ)特征：csr_matrix((data, indices, indptr), [shape=(M, N)])，意思是，矩陣中第i行非零元素的列號(hào)為indices[indptr[i]:indptr[i+1]]，相應(yīng)的值為data[indptr[i]:indptr[i+1]]

舉個(gè)例子：

>>> import numpy as np
>>> from scipy.sparse import csr_matrix
>>> 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 = csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()
array([[1, 0, 2],
       [0, 0, 3],
       [4, 5, 6]])

csr_matrix同樣有很多方法，其中tobytes()，tolist(), tofile()，tostring()值得注意，其他具體參考官方文檔，csr_matrix對(duì)象屬性前五個(gè)同coo_matrix，另外還有屬性如下：

indices

與屬性data一一對(duì)應(yīng)，元素值代表在某一行的列號(hào)

indptr

csr_matrix各行的起始值，length(csr_object.indptr) == csr_object.shape[0] + 1

has_sorted_indices

判斷每一行的indices是否是有序的，返回bool值

csr_matrix的優(yōu)點(diǎn)：

高效的算術(shù)運(yùn)算CSR + CSR，CSR * CSR等高效的行切片快速矩陣運(yùn)算

csr_matrix的缺點(diǎn)：

列切片操作比較慢（考慮csc_matrix）稀疏結(jié)構(gòu)的轉(zhuǎn)換比較慢（考慮lil_matrix或doc_matrix）

csc_matrix

​ csc_matrix和csr_matrix正好相反，即按列壓縮的稀疏矩陣存儲(chǔ)方式，同樣由三個(gè)一維數(shù)組indptr, indices, data組成，如下圖所示：

其實(shí)例化方式、屬性、方法、優(yōu)缺點(diǎn)和csr_matrix基本一致，這里不再贅述，它們之間唯一的區(qū)別就是按行或按列壓縮進(jìn)行存儲(chǔ)。

而這一區(qū)別決定了csr_matrix擅長(zhǎng)行操作；csc_matrix擅長(zhǎng)列操作，進(jìn)行運(yùn)算時(shí)需要進(jìn)行合理存儲(chǔ)結(jié)構(gòu)的選擇。

lil_matrix

​ lil_matrix，即List of Lists format，又稱(chēng)為Row-based linked list sparse matrix。它使用兩個(gè)嵌套列表存儲(chǔ)稀疏矩陣：data保存每行中的非零元素的值，rows保存每行非零元素所在的列號(hào)(列號(hào)是順序排序的)。

這種格式很適合逐個(gè)添加元素，并且能快速獲取行相關(guān)的數(shù)據(jù)。

其初始化方式同coo_matrix初始化的前三種方式：通過(guò)密集矩陣構(gòu)建、通過(guò)其他矩陣轉(zhuǎn)化以及構(gòu)建一個(gè)一定shape的空矩陣。

lil_matrix可用于算術(shù)運(yùn)算：支持加法，減法，乘法，除法和矩陣冪。其屬性前五個(gè)同coo_matrix，另外還有rows屬性，是一個(gè)嵌套List，表示矩陣每行中非零元素的列號(hào)。

LIL matrix本身的設(shè)計(jì)是用來(lái)方便快捷構(gòu)建稀疏矩陣實(shí)例，而算術(shù)運(yùn)算、矩陣運(yùn)算則轉(zhuǎn)化成CSC、CSR格式再進(jìn)行，構(gòu)建大型的稀疏矩陣還是推薦使用COO格式。

LIL format優(yōu)點(diǎn)

支持靈活的切片操作行切片操作效率高，列切片效率低

稀疏矩陣格式之間的轉(zhuǎn)化很高效（tobsr()、tocsr()、to_csc()、to_dia()、to_dok()、to_lil()）

LIL format缺點(diǎn)

加法操作效率低 (consider CSR or CSC)

列切片效率低(consider CSC)

矩陣乘法效率低 (consider CSR or CSC)

dok_matrix ​

dok_matrix，即Dictionary Of Keys based sparse matrix，是一種類(lèi)似于coo matrix但又基于字典的稀疏矩陣存儲(chǔ)方式，key由非零元素的的坐標(biāo)值tuple(row, column)組成，value則代表數(shù)據(jù)值。

dok matrix非常適合于增量構(gòu)建稀疏矩陣，并一旦構(gòu)建，就可以快速地轉(zhuǎn)換為coo_matrix。

其屬性和coo_matrix前四項(xiàng)同；其初始化方式同coo_matrix初始化的前三種：通過(guò)密集矩陣構(gòu)建、通過(guò)其他矩陣轉(zhuǎn)化以及構(gòu)建一個(gè)一定shape的空矩陣。

對(duì)于dok matrix，可用于算術(shù)運(yùn)算：它支持加法，減法，乘法，除法和矩陣冪；允許對(duì)單個(gè)元素進(jìn)行快速訪問(wèn)（ O(1) ）; 不允許重復(fù)。

>>> import numpy as np
>>> from scipy.sparse import dok_matrix
>>> np.random.seed(10)
>>> matrix = random(3, 3, format='dok', density=0.4)
>>> matrix[1, 1] = 33
>>> matrix[2, 1] = 10
>>> matrix.toarray()
array([[ 0.        ,  0.        ,  0.        ],
       [ 0.        , 33.        ,  0.        ],
       [ 0.19806286, 10.        ,  0.22479665]])
>>> dict(matrix)
{(2, 0): 0.19806286475962398, (2, 1): 10.0, (2, 2): 0.22479664553084766, (1, 1): 33.0}
>>> isinstance(matrix, dict)
True

在上面代碼最后可以看到，實(shí)際上dok_matrix實(shí)例也是dict實(shí)例，在實(shí)現(xiàn)上繼承了dict類(lèi)。

dia_matrix

​ dia_matrix，全稱(chēng)Sparse matrix with DIAgonal storage，是一種對(duì)角線的存儲(chǔ)方式。

如下圖中，將稀疏矩陣使用offsets和data兩個(gè)矩陣來(lái)表示。offsets表示data中每一行數(shù)據(jù)在原始稀疏矩陣中的對(duì)角線位置k（k>0, 對(duì)角線往右上角移動(dòng)；k0, 對(duì)角線往左下方移動(dòng)；k=0，主對(duì)角線）。

該格式的稀疏矩陣可用于算術(shù)運(yùn)算：它們支持加法，減法，乘法，除法和矩陣冪。

​dia_matrix五個(gè)屬性同coo matrix, 另外還有屬性offsets；dia_matrix有四種初始化方式，其中前三種初始化方式同coo_matrix前三種初始化方式，即：通過(guò)密集矩陣構(gòu)建、通過(guò)其他矩陣轉(zhuǎn)化以及構(gòu)建一個(gè)一定shape的空矩陣。

第四種初始化方式如下：

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

​ 其中，data[k,:]存儲(chǔ)著稀疏矩陣offsets[k]對(duì)角線上的值

>>> data = np.arange(15).reshape(3, -1) + 1
>>> offsets = np.array([0, -3, 2])
>>> dia = sparse.dia_matrix((data, offsets), shape=(7, 5))
>>> dia.toarray()
array([[ 1,  0, 13,  0,  0],
       [ 0,  2,  0, 14,  0],
       [ 0,  0,  3,  0, 15],
       [ 6,  0,  0,  4,  0],
       [ 0,  7,  0,  0,  5],
       [ 0,  0,  8,  0,  0],
       [ 0,  0,  0,  9,  0]])

不是很常用,了解即可

bsr_matrix

​ bsr_matrix，全稱(chēng)Block Sparse Row matrix，這種壓縮方式極其類(lèi)似CSR格式，但使用分塊的思想對(duì)稀疏矩陣進(jìn)行按行壓縮。所以，BSR適用于具有dense子矩陣的稀疏矩陣。該種矩陣有五種初始化方式，分別如下：

bsr_matrix(D, [blocksize=(R,C)])

D是一個(gè)M*N的二維dense矩陣；blocksize需要滿足條件：M % R = 0和N % C = 0，若不給定該參數(shù)，內(nèi)部將會(huì)應(yīng)用啟發(fā)式的算法自動(dòng)決定一個(gè)合適的blocksize.

bsr_matrix(S, [blocksize=(R,C)])

S是指其他類(lèi)型的稀疏矩陣

bsr_matrix((M, N), [blocksize=(R,C), dtype])

構(gòu)建一個(gè)shape為M*N的空矩陣

bsr_matrix((data, ij), [blocksize=(R,C), shape=(M, N)])

data 和ij 滿足條件： a[ij[0, k], ij[1, k]] = data[k]

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

data.shape一般是k*R*C，其中R、C分別代表block的行和列長(zhǎng)，k代表有幾個(gè)小block矩陣；第i行的塊列索引存儲(chǔ)在indices[indptr[i]:indptr[i+1]]，其值是data[ indptr[i]: indptr[i+1] ]。

bsr_matrix可用于算術(shù)運(yùn)算：支持加法，減法，乘法，除法和矩陣冪。如下面的例子，對(duì)于許多稀疏算術(shù)運(yùn)算，BSR比CSR和CSC更有效：

>>> from scipy.sparse import bsr_matrix
>>> import numpy
>>> 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]).repeat(4).reshape(6, 2, 2)
>>> bsr_matrix((data,indices,indptr), shape=(6, 6)).toarray()
array([[1, 1, 0, 0, 2, 2],
       [1, 1, 0, 0, 2, 2],
       [0, 0, 0, 0, 3, 3],
       [0, 0, 0, 0, 3, 3],
       [4, 4, 5, 5, 6, 6],
       [4, 4, 5, 5, 6, 6]])

可以通過(guò)熱圖觀察矩陣有沒(méi)有明顯分塊模式再?zèng)Q定使不使用該方式

bsr matrix對(duì)象擁有9個(gè)屬性，前四個(gè)屬性與coo matrix相同，另外還有以下屬性(注意csr matrix和bsr matrix之間的區(qū)別與聯(lián)系)：

data

即稀疏矩陣的數(shù)組，data.shape一般是k*R*C

indices

與屬性data中的k個(gè)二維矩陣一一對(duì)應(yīng)，元素值代表在某一行的列號(hào)

indptr

bsr各行起始起始值

blocksize

即tuple(R,C)

has_sorted_indices

判斷每一行的indices是否是有序的，返回bool值

實(shí)用函數(shù)

構(gòu)造特殊稀疏矩陣

scipy.sparse模塊還包含一些便捷函數(shù)，用于快速構(gòu)建單位矩陣、對(duì)角矩陣等，下面做一個(gè)簡(jiǎn)單的匯總：