在推薦系統中，我們通常使用非常稀疏的矩陣，因為項目總體非常大，而單個用戶通常與項目總體的一個非常小的子集進行交互。以YouTube為例——用戶通常會觀看數百個(可能是數千個)視頻，而YouTube的語料庫中有數百萬個視頻，這導致了>99%的稀疏性。
這意味著當我們在一個矩陣中表示用戶(行)和行為(列)時，結果是一個由許多零值組成的極其稀疏的矩陣。
在真實的場景中，我們如何最好地表示這樣一個稀疏的用戶-項目交互矩陣?
為什麼我們不能只使用Numpy數組或panda數據流呢?
要理解這一點，我們必須理解計算的兩個主要約束——時間和內存。前者就是我們所知道的「程序運行所需的時間」，而後者是「程序使用了多少內存」。前者非常簡單，但對於後者，確保程序不消耗所有內存非常重要，尤其是在處理大型數據集時，否則會遇到著名的「內存不足」錯誤。
我們PC上的每個程序和應用程式都使用一些內存(見下圖)。當我們運行矩陣計算並希望將這些稀疏矩陣存儲為Numpy數組或panda DataFrame時，它們也會消耗很多內存。
為了形式化這兩個約束，它們通常被稱為時間和空間(內存、硬碟等存儲)複雜性。
空間複雜度
當處理稀疏矩陣時，將它們存儲為一個完整的矩陣(從這裡開始稱為密集矩陣)是非常低效的。這是因為一個完整的數組為每個條目佔用一塊內存，所以一個n x m數組需要n x m塊內存。從簡單的邏輯角度來看，存儲這麼多零是沒有意義的!
從數學的角度來看，如果我們有一個100,000 x 100,000矩陣，這將要求我們有100,000 x 100,000 x 8 = 80gb的內存來存儲這個矩陣(因為每個double使用8位元組)!
時間複雜度
除了空間複雜性之外，密集的矩陣也會加劇運行時。我們將用下面的一個例子來說明。
那麼我們如何表示這些矩陣呢?
SciPy的稀疏模塊介紹
在Python中，稀疏數據結構在scipy中得到了有效的實現。稀疏模塊，其中大部分是基於Numpy數組。實現背後的思想很簡單:我們不將所有值存儲在密集的矩陣中，而是以某種格式存儲非零值(例如，使用它們的行和列索引)。
在我們深入研究CSR之前，讓我們比較一下在使用DataFrames和使用稀疏矩陣時在時間和空間複雜度上的效率差異。
import numpy as np from scipy import sparse from sys import getsizeof# Matrix 1: Create a dense matrix (stored as a full matrix). A_full = np.random.rand(600, 600)# Matrix 2: Store A_full as a sparse matrix (though it is dense). A_sparse = sparse.csc_matrix(A_full)# Matrix 3: Create a sparse matrix (stored as a full matrix). B_full = np.diag(np.random.rand(600))# Matrix 4: Store B_full as a sparse matrix. B_sparse = sparse.csc_matrix(B_full)# Create a square function to return the square of the matrix def square(A): return np.power(A, 2)
然後我們統計這些不同的矩陣以不同的形式存儲以及它們使用了多少內存。
%timeit square(A_full) print(getsizeof(A_full))>>> 6.91 ms ± 84.5 s per loop (mean ± std. dev. of 7 runs, 100 loops each) >>> 2880112%timeit square(A_sparse) print(getsizeof(A_sparse))>>> 409 ms ± 11.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) >>> 56%timeit square(B_full) print(getsizeof(B_full))>>> 2.18 ms ± 56.5 s per loop (mean ± std. dev. of 7 runs, 100 loops each) >>> 2880112%timeit square(B_sparse) print(getsizeof(B_sparse))>>> 187 s ± 5.24 s per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> 56
顯然，當我們用稀疏模塊存儲一個稀疏矩陣時，可以獲得時間和空間的最佳性能。
壓縮稀疏行(CSR)
儘管在SciPy中有很多類型的稀疏矩陣，比如鍵的字典(DOK)和列表的列表(LIL)，但我只討論壓縮稀疏行(CSR)，因為它是最常用和最廣為人知的格式。
CSR(以及CSC，又名壓縮稀疏列)用於寫一次讀多任務。為了有效地表示稀疏矩陣，CSR使用三個numpy數組來存儲一些相關信息，包括:
data(數據):非零值的值,這些是存儲在稀疏矩陣中的非零值
indices(索引):列索引的數組,從第一行(從左到右)開始，我們標識非零位置並在該行中返回它們的索引。在下面的圖中，第一個非零值出現在第0行第5列，因此5作為索引數組中的第一個值出現，然後是1(第1行，第1列)。
indptr(指針):表示索引指針，返回一個行開始的數組。這個定義容易把人搞糊塗，我選擇這樣解釋:它告訴我們每行包含多少個值。在下面的例子中，我們看到第一行包含一個值a，因此我們用0:1對它進行索引。第二行包含兩個值b, c，然後我們從1:3開始索引，以此類推。len(indptr) = len(data) + 1 = len(indexes) + 1，因為對於每一行，我們用開始和結束索引表示它(類似於索引列表)。
有哪些方法可以構造csr_matrix?
創建一個完整的矩陣並將其轉換為一個稀疏矩陣
some_dense_matrix = np.random.random(600, 600) some_sparse_matrix = sparse.csr_matrix(some_dense_matrix)
正如前面所看到的，這種方法是有很大問題的，因為我們必須首先獲得這個非常消耗內存的密集矩陣，然後才能將它轉換成一個稀疏矩陣。
創建一個空的稀疏矩陣
# format: csr_matrix((row_len, col_len)) empty_sparse_matrix = sparse.csr_matrix((600, 600))
注意，我們不應該創建一個空的稀疏矩陣，然後填充它們，因為csrmatrix被設計為一次寫、一次讀多。向csrmatrix寫入將是低效的，並且應該考慮其他類型的稀疏矩陣，比如在操作稀疏結構方面更有效的List of lists。
用數據創建一個稀疏矩陣
# method 1 # format: csr_matrix((data, (row_ind, col_ind)), [shape=(M, N)]) # where a[row_ind[k], col_ind[k]] = data[k]data = [3, 9, 5] rows = [0, 1, 1] cols = [2, 1, 2]sparse_matrix = sparse.csr_matrix((data, (rows, cols)), shape=(len(rows), len(cols)) sparse_matrix.toarray()>>> array([[0, 0, 3], [0, 9, 5], [0, 0, 0]], dtype=int64)# method 2 # format: csr_matrix((data, indices, indptr), [shape=(M, N)]) # column indices for row i: indices[indptr[i]:indptr[i+1]] # data values: data[indptr[i]:indptr[i+1]]data = [3, 9, 5] indices = [2, 1, 2] indptr = [0, 1, 3, 3]sparse_matrix = sparse.csr_matrix((data, indices, indptr)) sparse_matrix.toarray()>>> array([[0, 0, 3], [0, 9, 5], [0, 0, 0]], dtype=int64)
推薦使用這種方法
最後推薦兩篇文章，有興趣的可以深入閱讀
Sparse data structures in Python
Complexity and Sparse Matrices