python - sparse matrix (python - 稀疏矩陣)

◎前置概念

• 當我們在做資料檢索時，如tf-idf、term count中，會發現這些matrix中只含有少量的非0數值，若document、word數量及大時，將其矩陣完整的存下來會導致Memory占用過多，甚至不夠。 
• 此時便可以使用稀疏矩陣，不將0數值也存下來。
• 使用numpy的lil_matrix配合tocsr，進行一系列運作

◎LIL（list of lists）

A = lil_matrix((4, 4))
A[0, 0] = 1
A[1, 2] = 1
A[1, 3] = 2
A[2, 3] = 1
print(A.data)
print(A.rows)

• lil_matrix.data : 每個row中非0之值(column 0 至 column n)
• lil_matrix.rows : 為每個row中非0之值，其位置的column值(column 0 至 column n) 
• 型態皆為list

[list([1.0]) list([1.0, 2.0]) list([1.0]) list([])]
[list([0]) list([2, 3]) list([3]) list([])]

◎CSR（compressed sparse row）

B = A.tocsr()
print(B.data)
print(B.indices)
print(B.indptr)

• tocsr().data : row-major，非0之值
• tocsr().indices : row-major，其值非0之column位置
• tocsr().indptr : 從0開始，row-major，包含其row及其之前row，累計的非0數值總數 
• 型態皆為numpy.ndarray

[ 1.  1.  2.  1.]
[0 2 3 3]
[0 1 3 4 4]

◎LIL  + CSR

• 創建(使用LIL) : CSR加入元素，會需要知道indptr，而indptr需要累加，因此會比LIL慢
• 運算(使用CSR) : 由於CSR型態將list轉為ndarray，ndarray的運算會比list快(原因)