今回も疎行列のお話です。
前回の記事で登場したcrsとcscについて、具体的にどのようなデータ構造なのかを紹介します。
ちなみにcrsとcscはそれぞれ、
圧縮行格納方式 (Compressed Sparse Row) と、
圧縮列格納方式 (Compressed Sparse Column) の略です。
ほぼ同じ処理を行方向に行うか列方向の違いしかなく、転置を取るとそれぞれ入れ替わるので、 CSRの方を紹介します。
ちなみに、 wikipediaの説明で理解したので、それをみながら記事を書いています。
例として取り上げる行列はこれ。(wikipediaの例と同じ。)
$$
\left(
\begin{matrix}
1 & 2 & 3 & 0 \\
0 & 0 & 0 & 1 \\
2 & 0 & 0 & 2 \\
0 & 0 & 0 & 1 \\
\end{matrix}
\right)
$$
まず、csr形式のデータで作りましょう。
今回はarrayで作って変換するのではなく、お作法にしたがい、lil形式で生成してから変換します。
from scipy import sparse
# 成分が全て0の 4 * 4 の lil形式の疎行列を作成。
M_lil = sparse.lil_matrix((4, 4))
# 各成分を代入。
M_lil[0, 0] = 1
M_lil[0, 1] = 2
M_lil[0, 2] = 3
M_lil[1, 3] = 1
M_lil[2, 0] = 2
M_lil[2, 3] = 2
M_lil[3, 3] = 1
# M_csr形式に変換
M_csr = sparse.csr_matrix(M_lil)
# 確認
print(M_csr)
# 出力
'''
(0, 0) 1.0
(0, 1) 2.0
(0, 2) 3.0
(1, 3) 1.0
(2, 0) 2.0
(2, 3) 2.0
(3, 3) 1.0
'''
これで、csr形式の変数、M_csrに例の行列が格納されました。
printすると整形されて表示されるのですが、実際のデータ構造はこうはなっていません。
wikipediaの説明と、ドキュメントをみながら確認します。
まず、 実際のデータは、次の3つの属性に格納されています。
data ・・・ CSR format data array of the matrix
indices ・・・ CSR format index array of the matrix
indptr ・・・ CSR format index pointer array of the matrix
具体例を見てから説明します。
print(M_csr.data)
# [1. 2. 3. 1. 2. 2. 1.]
print(M_csr.indices)
# [0 1 2 3 0 3 3]
print(M_csr.indptr)
# [0 3 4 6 7]
まず、data が 疎行列の0では無い要素の値を、左上から行方向(右側へ)に順番に並べたものです。
(csrのrが対応。 cscの場合はここで列方向(下向き)に並べたものになります。)
そして、indices が、それぞれの要素が、何列目の要素なのかを示す配列です。
明らかにわかるように、data と indices の要素の数はその疎行列の0では無い成分の個数です。
あとは、dataの各要素が何行目なのかがわかれば、行列を復元できますが、
それを担っているのが、indptr です。
これだけ、wikipediaの説明と異なっていて非常にわかりにくいですが、次のように解釈できます。
# 行列の最初の行のデータは、indptrの最初の2個のデータで作ったスライスの値
print(M_csr.data[0: 3])
# [1. 2. 3.]
# 次の行のデータは、indptrの一つずらした2個のデータで作ったスライスの値
print(M_csr.data[3: 4])
# [1.]
# 以下繰り返し
print(M_csr.data[4: 6])
# [2. 2.]
print(M_csr.data[6: 7])
# [1.]
明らかにわかる通り、 indptr の要素の個数は行の数より1つ大きくなります。
これで、csr_matrixの中のデータの構造がわかりました。
また、data属性の中に行単位でデータが固まって存在してて、
行単位の取り出しや演算が得意なことにも納得できると思います。