摘要：對于機器學(xué)習(xí)而言，稀疏矩陣應(yīng)用非常廣，比如在數(shù)據(jù)特征表示自然語言處理等領(lǐng)域。稀疏存在的問題稀疏矩陣會導(dǎo)致空間和時間復(fù)雜度方面的問題。通過調(diào)用函數(shù)，可以使用表示將存儲在數(shù)組中的稠密矩陣轉(zhuǎn)換為稀疏矩陣。

對于一個矩陣而言，若數(shù)值為零的元素遠(yuǎn)遠(yuǎn)多于非零元素的個數(shù)，且非零元素分布沒有規(guī)律時，這樣的矩陣被稱作稀疏矩陣；與之相反，若非零元素數(shù)目占據(jù)絕大多數(shù)時，這樣的矩陣被稱作稠密矩陣。

稀疏矩陣在工程應(yīng)用中經(jīng)常被使用，尤其是在通信編碼和機器學(xué)習(xí)中。若編碼矩陣或特征表達(dá)矩陣是稀疏矩陣時，其計算速度會大大提升。對于機器學(xué)習(xí)而言，稀疏矩陣應(yīng)用非常廣，比如在數(shù)據(jù)特征表示、自然語言處理等領(lǐng)域。

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

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

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

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

矩陣的稀疏性可以用一個分?jǐn)?shù)來量化，即矩陣中零元素的個數(shù)除以矩陣中元素的總數(shù)。

sparsity = count zero elements / total elements

下面是一個小的3x6的稀疏矩陣?yán)?/p>

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

上面這個矩陣中總共有18個元素，其中有13個元素為0，則該矩陣的稀疏分?jǐn)?shù)為0.722或72%左右。

稀疏矩陣會導(dǎo)致空間和時間復(fù)雜度方面的問題。

空間復(fù)雜度

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

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

一個例子是大型矩陣太大以至于不能存儲在內(nèi)存中，這個矩陣就是鏈接矩陣，它表示的從一個網(wǎng)站到另一個網(wǎng)站的鏈接。一個較小的稀疏矩陣?yán)涌赡苁且槐緯嗅槍λ幸阎獑卧~或術(shù)語出現(xiàn)矩陣。這兩種情況所包含的矩陣都是稀疏的，其零值比非零數(shù)據(jù)值多，將這些矩陣表示為稠密矩陣的問題是需要內(nèi)存，并且在矩陣中必須分配32位或64位零值。這顯然是對內(nèi)存資源的一種浪費，因為這些零值不包含任何信息。

時間復(fù)雜度

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

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

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

稀疏矩陣在機器學(xué)習(xí)應(yīng)用中經(jīng)常出現(xiàn)。本節(jié)將討論一些常見的示例，以便讀者對其有個直觀的了解，并深入的理解稀疏性問題。

數(shù)據(jù)

稀疏矩陣一般出現(xiàn)在一些特定類型的數(shù)據(jù)中，比如常見的記錄活動發(fā)生的次數(shù)等。

這里有三個例子：

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

用戶是否購買產(chǎn)品目錄中的產(chǎn)品；

歌曲目錄中收聽歌曲的次數(shù)；

數(shù)據(jù)準(zhǔn)備

稀疏矩陣出現(xiàn)在用于編寫數(shù)據(jù)的編碼方案中。三個常見的例子如下：

獨熱編碼，用于將分類數(shù)據(jù)表示為稀疏二元向量；

計數(shù)編碼，用于表示文檔詞匯表中單詞的頻率；

TF-IDF編碼，用于表示詞匯表中詞頻逆文檔頻數(shù)；

研究領(lǐng)域

機器學(xué)習(xí)中一些研究領(lǐng)域必須開發(fā)專門的方法來直接解決稀疏性問題，這是因為輸入數(shù)據(jù)幾乎總是稀疏的。以下是三個例子：

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

2.用于處理目錄中的產(chǎn)品使用的推薦系統(tǒng)；

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

若語言模型中有100000個單詞，那么特征向量的長度為100000，但對于簡短的電子郵件消息而言，幾乎所有的特征計數(shù)為零。

使用稀疏矩陣

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

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

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

3.坐標(biāo)列表：元組列表存儲在包含行索引、列索引和其值的每個元組中；

還有一些更適合執(zhí)行有效操作的數(shù)據(jù)結(jié)構(gòu)，比如以下兩個常見示例：

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

CSC（Compressed Sparse Column)：與CSR方法相同，只是列索引在行索引之前被壓縮并首先被讀?。?/p> Python中的稀疏矩陣

SciPy使用多個數(shù)據(jù)結(jié)構(gòu)為創(chuàng)建稀疏矩陣提供了工具，以及將稠密矩陣轉(zhuǎn)化為稀疏矩陣的工具。許多在Numpy數(shù)組上運行的線性代數(shù)Numpy和SciPy函數(shù)可以在SciPy稀疏數(shù)組上操作。此外，使用Numpy數(shù)據(jù)結(jié)構(gòu)的機器學(xué)習(xí)庫也可以在Scipy稀疏數(shù)組上操作，例如，用于機器學(xué)習(xí)的scikit-learning和用于深度學(xué)習(xí)的Keras。

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

# dense to sparse
from numpy import array
from scipy.sparse import csr_matrix
# create dense matrix
A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])
print(A)
# convert to sparse matrix (CSR method)
S = csr_matrix(A)
print(S)
# reconstruct dense matrix
B = S.todense()
print(B)

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

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

  (0, 0)    1
  (0, 3)    1
  (1, 2)    2
  (1, 5)    1
  (2, 3)    2

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

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

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

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

# calculate sparsity
from numpy import array
from numpy import count_nonzero
# create dense matrix
A = array([[1, 0, 0, 1, 0, 0], [0, 0, 2, 0, 0, 1], [0, 0, 0, 2, 0, 0]])
print(A)
# calculate sparsity
sparsity = 1.0 - count_nonzero(A) / A.size
print(sparsity)

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

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

0.7222222222222222

文章標(biāo)題《A Gentle Introduction to Sparse Matrices for Machine Learning》，作者：Jason Brownlee，譯者：海棠。

文章詳細(xì)的內(nèi)容請查看原文