摘要：本文主要介紹了稀疏矩陣的基本知識、它存在的一些問題以及如何在Python中應用它，對於初學者和工程應用者來說是一份不錯的入門材料。

對於一個矩陣而言，若數值為零的元素遠遠多於非零元素的個數，且非零元素分佈沒有規律時，這樣的矩陣被稱作稀疏矩陣；與之相反，若非零元素數目佔據絕大多數時，這樣的矩陣被稱作稠密矩陣。

稀疏矩陣在工程應用中經常被使用，尤其是在通信編碼和機器學習中。若編碼矩陣或特徵表達矩陣是稀疏矩陣時，其計算速度會大大提升。對於機器學習而言，稀疏矩陣應用非常廣，比如在數據特徵表示、自然語言處理等領域。

用稀疏表示和工作在計算上代價很高，需要專門處理稀疏矩陣的表示和操作等，但是這些操作可以大幅提升性能。

在本教程中，讀者可以學習稀疏矩陣的基本概念、存在的問題以及如何在Python中使用它。

稀疏矩陣

稀疏矩陣是由大部分為零的矩陣組成的矩陣，這是和稠密矩陣有所區別的主要特點。

如果它的許多元素為零，則矩陣是稀疏的。對稀疏性感興趣的原因是利用好這一特性能夠大幅降低計算量，並且在實踐中發現很多大型矩陣問題也是稀疏的。

矩陣的稀疏性可以用一個分數來量化，即矩陣中零元素的個數除以矩陣中元素的總數。

sparsity = count zero elements / total elements

下面是一個小的3x6的稀疏矩陣例子

 1, 0, 0, 1, 0, 0
A = (0, 0, 2, 0, 0, 1)
 0, 0, 0, 2, 0, 0

上面這個矩陣中總共有18個元素，其中有13個元素為0，則該矩陣的稀疏分數為0.722或72%左右。

稀疏存在的問題

稀疏矩陣會導致空間和時間複雜度方面的問題。

空間複雜度

大型矩陣需要大量的內存來存儲，我們希望使用的一些大型矩陣是稀疏的。

實際上，大多數大型矩陣都是稀疏的，幾乎所有的條目都是零

一個例子是大型矩陣太大以至於不能存儲在內存中，這個矩陣就是鏈接矩陣，它表示的從一個網站到另一個網站的鏈接。一個較小的稀疏矩陣例子可能是一本書中針對所有已知單詞或術語出現矩陣。這兩種情況所包含的矩陣都是稀疏的，其零值比非零數據值多，將這些矩陣表示為稠密矩陣的問題是需要內存，並且在矩陣中必須分配32位或64位零值。這顯然是對內存資源的一種浪費，因為這些零值不包含任何信息。

時間複雜度

假設一個非常大型的稀疏矩陣可以存儲在內存中，之後將在這個矩陣上執行一些操作。簡單來說，若矩陣主要包含的是零值，即沒有多少數據，那麼對這個矩陣執行操作可能需要花費很長的時間，其中執行的大部分計算將涉及零值相加或相乘。

在這樣的問題上使用線性代數的方法是浪費的，因為大多數O(N^3)的算術運算致力於求解方程組或矩陣求逆涉及的零操作數。

矩陣運算的時間複雜度隨著矩陣大小增加而增加。對於機器學習而言，即使是最簡單的方法也可能需要對每一行、每一列甚至整個矩陣進行許多操作運算，這會導致執行時間會變得很長，上述問題會變得更加複雜。

機器學習中的稀疏矩陣

稀疏矩陣在機器學習應用中經常出現。本節將討論一些常見的示例，以便讀者對其有個直觀的瞭解，並深入的理解稀疏性問題。

數據

稀疏矩陣一般出現在一些特定類型的數據中，比如常見的記錄活動發生的次數等。

這裡有三個例子：

1.用戶是否在電影目錄中觀看過電影；

2.用戶是否購買產品目錄中的產品；

3.歌曲目錄中收聽歌曲的次數；

數據準備

稀疏矩陣出現在用於編寫數據的編碼方案中。三個常見的例子如下：

1.獨熱編碼，用於將分類數據表示為稀疏二元向量；

2.計數編碼，用於表示文檔詞彙表中單詞的頻率；

3.TF-IDF編碼，用於表示詞彙表中詞頻逆文檔頻數；

研究領域

機器學習中一些研究領域必須開發專門的方法來直接解決稀疏性問題，這是因為輸入數據幾乎總是稀疏的。以下是三個例子：

1.處理文本文檔的自然語言處理；

2.用於處理目錄中的產品使用的推薦系統；

3.處理包含大量黑色像素圖像時的計算機視覺問題；

若語言模型中有100000個單詞，那麼特徵向量的長度為100000，但對於簡短的電子郵件消息而言，幾乎所有的特徵計數為零。

使用稀疏矩陣

表示和使用稀疏矩陣的解決方案是使用替代的數據結構來表示稀疏矩陣。零元素值可以被忽略，只有稀疏矩陣中的非零元素值需要被存儲或使用。有多種數據結構能有效地構造稀疏矩陣，下面列出三個常見示例：

1.字典：一個字典使用行和列索引映射出一個值；

2.列表的列表：矩陣的每一行都以列表形式存儲，每個子列表包含列的索引和其值；

3.座標列表：元組列表存儲在包含行索引、列索引和其值的每個元組中；

還有一些更適合執行有效操作的數據結構，比如以下兩個常見示例：

1.CSR（Compressed Sparse Row）：稀疏矩陣用非零值的三個一維數組、行的範圍和列索引表示；

2.CSC（Compressed Sparse Column)：與CSR方法相同，只是列索引在行索引之前被壓縮並首先被讀取；

Python中的稀疏矩陣

SciPy使用多個數據結構為創建稀疏矩陣提供了工具，以及將稠密矩陣轉化為稀疏矩陣的工具。許多在Numpy數組上運行的線性代數Numpy和SciPy函數可以在SciPy稀疏數組上操作。此外，使用Numpy數據結構的機器學習庫也可以在Scipy稀疏數組上操作，例如，用於機器學習的scikit-learning和用於深度學習的Keras。

通過調用scr_matrix()函數，可以使用CSR表示將存儲在Numpy數組中的稠密矩陣轉換為稀疏矩陣。在下面的例子中，定義一個3x6稀疏矩陣作為一個密集數組，並將其轉換為CSR稀疏表示，然後通過調用todense()函數將其轉換回密集數組。

運行該示例後，首先打印出定義的密集數組，然後打印出CSR表示，最後打印出重建的密集矩陣。

[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]
 (0, 0)\t1
 (0, 3)\t1
 (1, 2)\t2
 (1, 5)\t1
 (2, 3)\t2
[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]

Numpy不提供函數來計算矩陣的稀疏性。不過，可以通過首先找到矩陣的密度並從中減去相關值來輕鬆地計算出來。Numpy數組中的非零元素的數量可以由count_nonzero()函數給出，數組中的元素總個數可以由數組的size屬性給出。因此，可以將數組稀疏度計算為：

sparsity = 1.0 - count_nonzero(A) / A.size

下面的示例演示如何計算數組的稀疏度：

運行示例後，首先打印定義的稀疏矩陣，然後是矩陣的稀疏度。

[[1 0 0 1 0 0]
[0 0 2 0 0 1]
[0 0 0 2 0 0]]
0.7222222222222222

相關資源

如果您希望深入的瞭解稀疏矩陣，本節提供了有關該主題的一些資源：

書籍

線性代數簡介，第五版，2016.

科學計算的藝術，第三版，2007.

人工智能：現代方法，第三版，2009.

直接稀疏矩陣的方法，第二版，2017.

API

Sparse matrices(scipy.sparse)API

Scipy.sparse.csr_matrix()API

Numpy.count_nonzero()API

Numpy.ndarray.size API

文章

稀疏矩陣（維基百科）

作者信息

Jason Brownlee，機器學習專家，專注於機器學習的推廣教育。

本文由阿里云云棲社區組織翻譯，文章原標題《A Gentle Introduction to Sparse Matrices for Machine Learning》，作者：Jason Brownlee，譯者：海棠。