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

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

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

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

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

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

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

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

sparsity = count zero elements / total elements

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

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

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

稀疏矩陣會(huì)導(dǎo)致空間和時(shí)間復(fù)雜度方面的問(wèn)題。

空間復(fù)雜度

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

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

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

時(shí)間復(fù)雜度

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

在這樣的問(wèn)題上使用線性代數(shù)的方法是浪費(fèi)的，因?yàn)榇蠖鄶?shù)O(N^3)的算術(shù)運(yùn)算致力于求解方程組或矩陣求逆涉及的零操作數(shù)。

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

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

數(shù)據(jù)

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

這里有三個(gè)例子：

用戶是否在電影目錄中觀看過(guò)電影；

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

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

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

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

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

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

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

研究領(lǐng)域

機(jī)器學(xué)習(xí)中一些研究領(lǐng)域必須開(kāi)發(fā)專門(mén)的方法來(lái)直接解決稀疏性問(wèn)題，這是因?yàn)檩斎霐?shù)據(jù)幾乎總是稀疏的。以下是三個(gè)例子：

1.處理文本文檔的自然語(yǔ)言處理；

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

3.處理包含大量黑色像素圖像時(shí)的計(jì)算機(jī)視覺(jué)問(wèn)題；

若語(yǔ)言模型中有100000個(gè)單詞，那么特征向量的長(zhǎng)度為100000，但對(duì)于簡(jiǎn)短的電子郵件消息而言，幾乎所有的特征計(jì)數(shù)為零。

使用稀疏矩陣

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

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

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

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

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

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

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

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

通過(guò)調(diào)用scr_matrix()函數(shù)，可以使用CSR表示將存儲(chǔ)在Numpy數(shù)組中的稠密矩陣轉(zhuǎn)換為稀疏矩陣。在下面的例子中，定義一個(gè)3x6稀疏矩陣作為一個(gè)密集數(shù)組，并將其轉(zhuǎn)換為CSR稀疏表示，然后通過(guò)調(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)

運(yùn)行該示例后，首先打印出定義的密集數(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ù)來(lái)計(jì)算矩陣的稀疏性。不過(guò)，可以通過(guò)首先找到矩陣的密度并從中減去相關(guān)值來(lái)輕松地計(jì)算出來(lái)。Numpy數(shù)組中的非零元素的數(shù)量可以由count_nonzero()函數(shù)給出，數(shù)組中的元素總個(gè)數(shù)可以由數(shù)組的size屬性給出。因此，可以將數(shù)組稀疏度計(jì)算為：

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

下面的示例演示如何計(jì)算數(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)

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

[[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)容請(qǐng)查看原文