疎行列をどう扱うか?疎行列のPython実装チュートリアル

この記事では主にPythonで疎行列を実装するためのサンプルコードを紹介します。エディターをフォローして見てみましょう

エンジニアリングの実践では、ほとんどの場合、大きな行列は一般に疎行列であるため、疎行列をどのように扱うかは実務上非常に重要です。この記事では、Python での実装を例として取り上げます。まず、スパース行列がどのように格納され、表現されるかを見てみましょう。

1. スパースモジュールの事前学習

Pythonのscipyモジュールには、スパース行列を解くために特別に設計されたスパースモジュールと呼ばれるモジュールがあります。この記事の内容のほとんどは、実際にはスパース モジュールに基づいています。

最初のステップは、スパースモジュール

>>> from scipy import sparse

をインポートすることです。そして、ヘルプ、最初に見てみましょう

>>> help(sparse)

そして、最も関心のある部分を直接見つけます:

  Usage information
  =================

  There are seven available sparse matrix types:

    1. csc_matrix: Compressed Sparse Column format
    2. csr_matrix: Compressed Sparse Row format
    3. bsr_matrix: Block Sparse Row format
    4. lil_matrix: List of Lists format
    5. dok_matrix: Dictionary of Keys format
    6. coo_matrix: COOrdinate format (aka IJV, triplet format)
    7. dia_matrix: DIAgonal format

  To construct a matrix efficiently, use either dok_matrix or lil_matrix.
  The lil_matrix class supports basic slicing and fancy
  indexing with a similar syntax to NumPy arrays. As illustrated below,
  the COO format may also be used to efficiently construct matrices.

  To perform manipulations such as multiplication or inversion, first
  convert the matrix to either CSC or CSR format. The lil_matrix format is
  row-based, so conversion to CSR is efficient, whereas conversion to CSC
  is less so.

  All conversions among the CSR, CSC, and COO formats are efficient,
  linear-time operations.

この説明を通じて、スパースモジュールの一般的な理解。スパースモジュールにスパース行列を格納するには 7 つの方法があります。次に、これら7つの方法を1つずつ紹介していきます。

2.coo_matrix

coo_matrixは最も単純な保存方法です。 3 つの配列 row、col、data は、ゼロ以外の要素の情報を格納するために使用されます。 3 つの配列は同じ長さを持ち、row は要素の行を保持し、col は要素の列を保持し、data は要素の値を保持します。一般に、coo_matrix は行列の作成に主に使用されます。これは、coo_matrix は行列の要素を追加、削除、変更することができないためです。行列が正常に作成されると、他の形式の行列に変換されます。

>>> row = [2,2,3,2]
>>> col = [3,4,2,3]
>>> c = sparse.coo_matrix((data,(row,col)),shape=(5,6))
>>> print c.toarray()
[[0 0 0 0 0 0]
 [0 0 0 0 0 0]
 [0 0 0 5 2 0]
 [0 0 3 0 0 0]
 [0 0 0 0 0 0]]

注意すべき点は、coo_matrix を使用して行列を作成する場合、同じ行と列の座標が複数回出現する可能性があるということです。マトリックスが実際に作成された後、対応する座標値が合計されて最終結果が得られます。

3.dok_matrix と lil_matrix

dok_matrix と lil_matrix は、行列の要素が徐々に追加されるシナリオに適用できます。 doc_matrix の戦略は、辞書を使用して行列内の 0 ではない要素を記録することです。当然のことながら、辞書のキーには記録された要素の位置情報の祖先が格納され、値は記録された要素の特定の値になります。

>>> import numpy as np
>>> from scipy.sparse import dok_matrix
>>> S = dok_matrix((5, 5), dtype=np.float32)
>>> for i in range(5):
...   for j in range(5):
...       S[i, j] = i + j
...
>>> print S.toarray()
[[ 0. 1. 2. 3. 4.]
 [ 1. 2. 3. 4. 5.]
 [ 2. 3. 4. 5. 6.]
 [ 3. 4. 5. 6. 7.]
 [ 4. 5. 6. 7. 8.]]

lil_matrix は 2 つのリストを使用して非ゼロ要素を格納します。 data には各行の非ゼロ要素が格納され、rows には非ゼロ要素が配置されている列が格納されます。この形式は、要素を一度に 1 つずつ追加し、行関連のデータを迅速に取得するのにも最適です。

>>> from scipy.sparse import lil_matrix
>>> l = lil_matrix((6,5))
>>> l[2,3] = 1
>>> l[3,4] = 2
>>> l[3,2] = 3
>>> print l.toarray()
[[ 0. 0. 0. 0. 0.]
 [ 0. 0. 0. 0. 0.]
 [ 0. 0. 0. 1. 0.]
 [ 0. 0. 3. 0. 2.]
 [ 0. 0. 0. 0. 0.]
 [ 0. 0. 0. 0. 0.]]
>>> print l.data
[[] [] [1.0] [3.0, 2.0] [] []]
>>> print l.rows
[[] [] [3] [2, 4] [] []]

上記の分析から、スパース行列を構築する上記 2 つの方法は、一般に、非ゼロ要素を徐々に追加することによって行列を構築し、その後、それらを迅速に計算できる他の行列格納方法に変換するために使用されることが容易にわかります。

4.dia_matrix

斜め収納方法です。ここで、列は対角線を表し、行は行を表します。対角線上の要素がすべて 0 の場合は省略されます。

元の行列が対角行列の場合、圧縮率は非常に高くなります。

インターネットで写真を見つけましたが、原理は誰でも簡単に理解できます。

5.csr_matrix および csc_matrix

csr_matrix、正式名は Compressed Sparse Row で、行列を行ごとに圧縮します。 CSR には、数値、列番号、行オフセットの 3 種類のデータが必要です。 CSRとは、数値や列番号の意味をcooのものと一致させたコーディング方法です。行オフセットは、行の最初の要素の開始オフセット位置を値で示します。

この原理をよりよく反映している写真もインターネットで見つけました。

Pythonでの使い方を見てください:

>>> from scipy.sparse import csr_matrix
>>> indptr = np.array([0, 2, 3, 6])
>>> indices = np.array([0, 2, 2, 0, 1, 2])
>>> data = np.array([1, 2, 3, 4, 5, 6])
>>> csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()
array([[1, 0, 2],
    [0, 0, 3],
    [4, 5, 6]])

はどうですか、理解するのは難しくありませんか？

ドキュメントの内容を見てみましょう

 Notes
 | -----
 |
 | Sparse matrices can be used in arithmetic operations: they support
 | addition, subtraction, multiplication, pision, and matrix power.
 |
 | Advantages of the CSR format
 |  - efficient arithmetic operations CSR + CSR, CSR * CSR, etc.
 |  - efficient row slicing
 |  - fast matrix vector products
 |
 | Disadvantages of the CSR format
 |  - slow column slicing operations (consider CSC)
 |  - changes to the sparsity structure are expensive (consider LIL or DOK)

csr_matrix が実行列演算により適していることを理解するのは難しくありません。

csc_matrix については、csr_matrix に似ていますが、列に基づいて圧縮されているため、個別には紹介しません。

6.bsr_matrix

Block Sparse Row 形式は、名前が示すように、ブロック化の考え方に基づいて行列を圧縮します。

以上が疎行列をどう扱うか?疎行列のPython実装チュートリアルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。