Ctrl+K

稀疏陣列 (scipy.sparse)#

簡介#

scipy.sparse 及其子模組提供了用於處理稀疏陣列的工具。稀疏陣列是指陣列中只有少數位置有資料，而大多數位置被視為「空的」陣列。稀疏陣列非常有用，因為它們允許使用更簡單、更快速和/或更少記憶體密集型的演算法來進行線性代數 (scipy.sparse.linalg) 或基於圖的計算 (scipy.sparse.csgraph)，但對於切片、重塑或賦值等操作，它們通常較不靈活。本指南將介紹 scipy.sparse 中稀疏陣列的基礎知識，解釋稀疏資料結構的獨特之處，並引導您閱讀使用者指南的其他章節，以了解稀疏線性代數和圖方法。

稀疏陣列入門#

稀疏陣列是一種特殊的陣列，其中只有少數位置有資料。這允許使用資料的壓縮表示法，其中僅記錄資料存在的位置。有許多不同的稀疏陣列格式，每種格式都在壓縮和功能之間做出不同的權衡。首先，讓我們建立一個非常簡單的稀疏陣列，即座標 (COO) 陣列 (coo_array)，並將其與密集陣列進行比較

>>> import scipy as sp
>>> import numpy as np
>>> dense = np.array([[1, 0, 0, 2], [0, 4, 1, 0], [0, 0, 5, 0]])
>>> sparse = sp.sparse.coo_array(dense)
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> sparse
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

請注意，在我們的密集陣列中，我們有五個非零值。例如，2 位於位置 0,3，而 4 位於位置 1,1。所有其他值均為零。稀疏陣列明確地記錄這五個值（請參閱 5 stored elements and shape (3, 4)），然後將所有剩餘的零值表示為隱含值。

大多數稀疏陣列方法的工作方式與密集陣列方法類似

>>> sparse.max()
5
>>> dense.max()
5
>>> sparse.argmax()
10
>>> dense.argmax()
10
>>> sparse.mean()
1.0833333333333333
>>> dense.mean()
1.0833333333333333

稀疏陣列上也存在一些「額外」屬性，例如 .nnz，它會傳回儲存值的數量

>>> sparse.nnz
5

當對稀疏陣列的軸應用時，大多數歸約運算（例如 .mean()、.sum() 或 .max()）將傳回 numpy 陣列

>>> sparse.mean(axis=1)
array([0.75, 1.25, 1.25])

這是因為稀疏陣列上的歸約通常是密集的。

了解稀疏陣列格式#

不同種類的稀疏陣列具有不同的功能。例如，COO 陣列無法進行下標或切片

>>> dense[2, 2]
5
>>> sparse[2, 2]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'coo_array' object is not subscriptable

但是，其他格式（例如壓縮稀疏列 (CSR)）csr_array 支援切片和元素索引

>>> sparse.tocsr()[2, 2]
5

有時，scipy.sparse 會傳回與輸入稀疏矩陣格式不同的稀疏矩陣格式。例如，兩個 COO 格式的稀疏陣列的點積將是 CSR 格式的陣列

>>> sparse @ sparse.T
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 3)>

發生此變更的原因是 scipy.sparse 將變更輸入稀疏陣列的格式，以便使用最有效率的計算方法。

scipy.sparse 模組包含以下格式，每種格式都有其獨特的優點和缺點

  • 區塊稀疏列 (BSR) 陣列 scipy.sparse.bsr_array，當陣列中包含資料的部分以連續區塊形式出現時，此格式最為適用。

  • 座標 (COO) 陣列 scipy.sparse.coo_array，此格式提供了一種簡單的方式來建構稀疏陣列並就地修改它們。COO 也可以快速轉換為其他格式，例如 CSR、CSC 或 BSR。

  • 壓縮稀疏列 (CSR) 陣列 scipy.sparse.csr_array，此格式最適用於快速算術、向量乘積和按列切片。

  • 壓縮稀疏行 (CSC) 陣列 scipy.sparse.csc_array，此格式最適用於快速算術、向量乘積和按行切片。

  • 對角 (DIA) 陣列 scipy.sparse.dia_array，只要資料主要沿著陣列的對角線出現，此格式就適用於有效率的儲存和快速算術。

  • 鍵字典 (DOK) 陣列 scipy.sparse.dok_array，此格式適用於快速建構和單元素存取。

  • 列表列表 (LIL) 陣列 scipy.sparse.lil_array，此格式適用於快速建構和修改稀疏陣列。

有關每種稀疏陣列格式的優缺點的更多資訊，請參閱它們的文件。

scipy.sparse 陣列的所有格式都可以直接從 numpy.ndarray 建構而來。但是，某些稀疏格式也可以透過不同的方式建構。每種稀疏陣列格式都有不同的優點，這些優點記錄在每個類別中。例如，建構稀疏陣列最常見的方法之一是從個別的 row、column 和 data 值建構稀疏陣列。對於我們之前的陣列

>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])

row、column 和 data 陣列描述了我們的稀疏陣列具有條目的行、列和值

>>> row = [0,0,1,1,2]
>>> col = [0,3,1,2,2]
>>> data = [1,2,4,1,5]

使用這些，我們現在可以定義一個稀疏陣列，而無需先建構密集陣列

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

不同的類別有不同的建構函式，但 scipy.sparse.csr_array、scipy.sparse.csc_array 和 scipy.sparse.coo_array 允許這種建構方式。

稀疏陣列、隱含零值和重複項#

稀疏陣列之所以有用，是因為它們隱含地表示它們的大部分值，而無需儲存實際的預留位置值。在 scipy.sparse 中，用於表示「無資料」的值是隱含零值。當需要明確零值時，這可能會造成混淆。例如，在 圖方法 中，從 scipy.sparse.csgraph 來看，我們通常需要能夠區分 (A) 連接節點 i 和 j 且權重為零的連結，以及 (B) 節點 i 和 j 之間沒有連結。稀疏矩陣可以做到這一點，只要我們牢記明確和隱含零值即可。

例如，在我們之前的 csr 陣列中，我們可以透過將明確零值包含在 data 列表中來加入明確零值。讓我們將陣列中最後一行和最後一列的最後一個條目視為明確零值

>>> row = [0,0,1,1,2,2]
>>> col = [0,3,1,2,2,3]
>>> data = [1,2,4,1,5,0]

然後，我們的稀疏陣列將有六個儲存元素，而不是五個

>>> csr = sp.sparse.csr_array((data, (row, col)))
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

「額外」元素是我們的明確零值。當轉換回密集陣列時，兩者仍然相同，因為密集陣列明確地表示所有內容

>>> csr.todense()
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])
>>> dense
array([[1, 0, 0, 2],
    [0, 4, 1, 0],
    [0, 0, 5, 0]])

但是，對於稀疏算術、線性代數和圖方法，2,3 位置的值將被視為明確零值。若要移除此明確零值，我們可以使用 csr.eliminate_zeros() 方法。這會在稀疏陣列上就地運作，並移除任何零值儲存元素

>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>
>>> csr.eliminate_zeros()
>>> csr
<Compressed Sparse Row sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

在 csr.eliminate_zeros() 之前，有六個儲存元素。之後，只有五個儲存元素。

另一個複雜點是建構稀疏陣列時如何處理重複項。當我們在建構稀疏陣列時，在 row,col 處有兩個或多個條目時，可能會發生重複項。當使用 data、row 和 col 向量建構稀疏陣列時，通常會發生這種情況。例如，我們可以使用 1,1 處的重複值來表示我們之前的陣列

>>> row = [0,0,1,1,1,2]
>>> col = [0,3,1,1,2,2]
>>> data = [1,2,1,3,1,5]

在這種情況下，我們可以發現有兩個 data 值對應於最終陣列中的 1,1 位置。scipy.sparse 將單獨儲存這些值

>>> dupes = sp.sparse.coo_array((data, (row, col)))
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 6 stored elements and shape (3, 4)>

請注意，此稀疏陣列中有六個儲存元素，儘管只有五個唯一位置有資料。當這些陣列轉換回密集陣列時，重複值會被加總。因此，在位置 1,1 處，密集陣列將包含重複儲存條目的總和 1 + 3

>>> dupes.todense()
array([[1, 0, 0, 2],
      [0, 4, 1, 0],
      [0, 0, 5, 0]])

若要移除稀疏陣列本身內的重複值，從而減少儲存元素的數量，我們可以使用 .sum_duplicates() 方法

>>> dupes.sum_duplicates()
>>> dupes
<COOrdinate sparse array of dtype 'int64'
     with 5 stored elements and shape (3, 4)>

現在我們的稀疏陣列中只有五個儲存元素，它與我們在本指南中一直使用的陣列相同

>>> dupes.todense()
array([[1, 0, 0, 2],
       [0, 4, 1, 0],
       [0, 0, 5, 0]])

標準格式#

多種稀疏陣列格式具有「標準格式」，以便實現更有效率的運算。通常，這些格式包含額外的限制，例如

  • 任何值都沒有重複條目

  • 已排序的索引

具有標準形式的類別包括：coo_array、csr_array、csc_array 和 bsr_array。有關每個標準表示法的詳細資訊，請參閱這些類別的文件字串。

若要檢查這些類別的執行個體是否為標準格式，請使用 .has_canonical_format 屬性

>>> coo = sp.sparse.coo_array(([1, 1, 1], ([0, 2, 1], [0, 1, 2])))
>>> coo.has_canonical_format
False

若要將執行個體轉換為標準格式，請使用 .sum_duplicates() 方法

>>> coo.sum_duplicates()
>>> coo.has_canonical_format
True

稀疏陣列的後續步驟#

當處理大型、幾乎為空的陣列時，稀疏陣列類型最為有用。具體而言，稀疏線性代數和稀疏圖方法在這些情況下效率提升最為顯著。

在本頁中