稀疏矩陣定義
百度百科:在矩陣中赖钞，若數(shù)值為0的元素數(shù)目遠遠多于非0元素的數(shù)目需纳，并且非0元素分布沒有規(guī)律時，則稱該矩陣為稀疏矩陣蛤织；與之相反赴叹，若非0元素數(shù)目占大多數(shù)時，則稱該矩陣為稠密矩陣指蚜。定義非零元素的總數(shù)比上矩陣所有元素的總數(shù)為矩陣的稠密度乞巧。簡單來說,稀疏矩陣就是絕大部分都是0的矩陣,只包含很少的非零值.
比如,
上述稀疏矩陣非零元素有9個,26個零值.稀疏性是74%.
稀疏矩陣因為絕大部分都是0元素,如果我們?nèi)匀话凑掌胀ǚ绞酱鎯?無疑會浪費很多空間;同時如果進行運算時,0元素對最終結(jié)果也沒有幫助,增加了許多無效計算. 因此,我們需要設(shè)計出新的存儲方式,或者說數(shù)據(jù)結(jié)構(gòu)來存儲稀疏矩陣.比較常見的有:
- DOK:Dictionary of keys.將非零元素的坐標(row,column)作為key,非零元素值作為value;同時只存儲非零元素值,零值被扔掉.可以以任意順序逐漸構(gòu)建稀疏矩陣;但是按某種順序訪問非零元素時比較困難.通常用來構(gòu)建矩陣,然后再把矩陣轉(zhuǎn)換成別的方式.
- COO:Coordinate list,坐標格式.三個數(shù)組row,col,value,分別存儲非零元素坐標的行,列以及非零值.理論上稀疏矩陣中的元素在存儲時順序是任意的,但是為了方便元素訪問,存儲時先按照先左后右,先上后下順序進行存儲(left to right, top to buttom).
- CSR:壓縮稀疏行
- CSC:壓縮稀疏列,和CSR類似.
稀疏矩陣存儲
對于稀疏矩陣的存儲,為了達到壓縮的目的(節(jié)省存儲空間),只存儲非0元素值,但是也要保留非零元素的位置,方便恢復(fù).所以,我們存儲時不僅存儲非零元素值,同時存儲其坐標位置(row,column). 針對這兩者的存儲,會出現(xiàn)不同的設(shè)計方案.這里主要介紹COO,CSR和CSC存儲格式.
COO
我們使用三個數(shù)組row,column和data分別用來存儲非零元素坐標的row_index,col_index,以及數(shù)值.比如:
NNO:The number of nonzero.矩陣非零元素個數(shù). 三個數(shù)組的長度都是NNO.data[i]在原稀疏矩陣中的坐標為(row[i],col[i]]).
>>> from scipy.sparse import *
>>>
>>> row = [0,0,1,1,2,2,2,3,3]
>>> col = [0,1,1,2,0,2,3,1,3]
>>> data = [1,7,2,8,5,3,9,6,4]
>>> import numpy as np
>>> coo = coo_matrix((data,(row,col)),shape=(4,4),dtype=np.int)
>>> coo
<4x4 sparse matrix of type '<class 'numpy.int64'>'
with 9 stored elements in COOrdinate format>
>>> coo.todense()
matrix([[1, 7, 0, 0],
[0, 2, 8, 0],
[5, 0, 3, 9],
[0, 6, 0, 4]])
可以發(fā)現(xiàn),這種存儲方式中,row數(shù)組和column數(shù)組中有一定的重復(fù)元素.我們是否可以針對這個冗余特性進一步進行壓縮?之后出現(xiàn)CSR,CSC,分別是對row數(shù)組和column數(shù)組進行了壓縮.
CSR
- NNO:稀疏矩陣非零元素個數(shù);
- M:稀疏矩陣行數(shù);
- N:稀疏矩陣列數(shù).
對COO稀疏矩陣存儲格式的三個數(shù)組中的row數(shù)組進行壓縮.其他兩個數(shù)組保持不變;三個數(shù)組分別是row_ptr,columns和data.其中columns和data數(shù)組長度均為NNO(矩陣的非零元素個數(shù)).如何對COO的row進行壓縮?
row_ptr存儲的是每行的第一個非零元素距離稀疏矩陣第一個元素的偏移位置;
- row_ptr:長度為M+1.
- row_ptr[0] = 0
- row_ptr[i] = row_ptr[i-1] + nno(rows[i-1])[第i-1行非零元素個數(shù)]
- row_ptr[M] = NNO.
由row_ptr我們可以知道每行非零元素在data中的index范圍.第i行的非零元素為data[row_ptr[i]:row_ptr[i+1]],對data數(shù)組的切片,不包含data[row_ptr[i+1]];同時第i行非零元素的col坐標分別為columns[row_ptr[i]:row_ptr[i+1]];對data和columns的訪問相似,index是相同的.
如上圖中,第0行非零元素在data中是data[0:2],就是1,7;列坐標為columns[0:2],就是0,1,第1行非零元素為data[2:4],有兩個元素2和8,列坐標分別為columns[2:4],1和2.
>>> row_ptr = [0,2,4,7,9]
>>> col = [0,1,1,2,0,2,3,1,3]
>>> data = [1,7,2,8,5,3,9,6,4]
>>> csr = csr_matrix((data,col,row_ptr),shape=(4,4),dtype=np.int)# 被壓縮的數(shù)組放在最后一個
>>> csr.todense()
matrix([[1, 7, 0, 0],
[0, 2, 8, 0],
[5, 0, 3, 9],
[0, 6, 0, 4]])
方便進行行操作.
CSC
和CSR類似.只不過對列進行壓縮,row和data保持不變.
方便進行列操作.
