分析ノート

今回も疎行列のお話です。
前回の記事で登場した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属性の中に行単位でデータが固まって存在してて、
行単位の取り出しや演算が得意なことにも納得できると思います。

前回の記事に続いて疎行列の話です。
参考:scipyにおける疎行列

今回は疎行列を実装する型(クラス)のうち、csc_matrixとcsr_matrixの紹介です。
前回紹介した、lil_matrixには効率的に疎行列を構成できるメリットがありますが、
計算が遅いというデメリットがあります。
ドキュメントに次のように書いてある通り、演算するときはcsrかcsc形式に変換した方が良いです。
arithmetic operations LIL + LIL are slow (consider CSR or CSC)

とりあえず本当に遅いのか時間を測っておきましょう。
今回は 10000*10000の大きめの疎行列を作り、実験します。
(arrayの場合の時間も測定したいので、最初にarrayで作成して変換していますが、本来は最初からlil型で生成してメモリを節約の恩恵を受けた方が良いです。)
また、csrと、cscはそれぞれ行方向、列方向の取り出しに有利という特徴があるので、実験用データによって有利不利無いように対称行列を作りました。

from scipy import sparse
import numpy as np
# 疎行列作成
M_array = np.random.choice(
    [0, 1, 2, 3, 4, 5],
    p=[0.99, 0.002, 0.002, 0.002, 0.002, 0.002],
    size=[10000, 10000]
)
# 自身の転置行列と足し合わせて対称行列にする
M_array = M_array + M_array.T

# それぞれの型に変換する
M_lil = sparse.lil_matrix(M_array)
M_csc = sparse.csc_matrix(M_lil)
M_csr = sparse.csr_matrix(M_lil)

# 和をとるのにかかる時間を計測
%timeit M_array + M_array
# 406 ms ± 2.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit M_lil + M_lil
# 618 ms ± 7.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit M_csc + M_csc
# 7.92 ms ± 17.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csr + M_csr
# 7.94 ms ± 51.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

ご覧の通り、 lil 同士の演算は通常のarray形式よりも遅く、一方でcscやcsr同士の演算は圧倒的に速くなりました。

あとは、cscとcsrの違いですが、それぞれ、列方向のスライスと行方向のスライスが効率的に行えます。
(あまり指摘されないようですが、スライスをとるだけであればarrayが一番早い。)

これもそれぞれみておきましょう。

# 列方向のスライス
%timeit M_array[:, 400]
# 225 ns ± 3.06 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit M_lil[:, 400]
# 11.4 ms ± 201 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csc[:, 400]
# 151 µs ± 2.73 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit M_csr[:, 400]
# 2.86 ms ± 127 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

列方向のスライスについては、array が最速ではありますが、 csc が csr に比べてかなり早いことが確認できます。

次は行方向。

# 行方向のスライス
%timeit M_array[400, :]
# 235 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit M_lil[400, :]
# 36.6 µs ± 1.37 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit M_csc[400, :]
# 2.9 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit M_csr[400, :]
# 66 µs ± 3.39 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

今度は、csr が csc より速くなりました。
とはいえ、lil が csrよりも速く処理できています。(array最速は変わらず。)

これは、前回の記事で説明した通り、lilがrows属性に、行ごとの値を保有しているからのようです。

csrの方が演算が速く、わざわざ疎行列を作ったうえでなんの演算もせずにスライスで値を取り出すだけという場面もあまり無いので、
csrかcscを選んで使うことが多いと思いますが、行方向のスライスだけならlilが速いことは一応覚えておこうと思います。

自然言語処理やレコメンドシステムの開発などをやっていると、サイズは非常に大きいが成分のほとんどは0という行列が頻繁に登場します。
そのような行列を疎行列と言います。
疎行列 – Wikipedia
これをそのまま扱うと、メモリは無駄に消費するし無駄な計算は増えるしで非常に効率の悪いことになります。
そのため、scipyでは疎行列を専門に扱う scipy.sparse というモジュールが用意されています。

ドキュメント: Sparse matrices (scipy.sparse)

リンク先を見たらわかる通り、疎行列を表す型は結構色々な種類があります。(Sparse matrix classes 参照)
それぞれ、他の型との変換が高速とか、行方向/列方向の取り出しが早いとか個別にメリットを持っていますが、
共通しているのはデータ量を大幅に節約できる点です。

今後の記事でいくつか紹介する予定ですが、とりあえずデータ量を削減できるって特徴だけでも確認しておきましょう。

疎行列のメリットを感じるにはかなり小さいのですが、乱数で10*10の疎行列(array型)を作って、
それを lil_matrix に変換して、中のデータを見てみましょう。

まずデータ作成。
(今回はサンプルとして、array型でデータを作って変換していますが、
省メモリの恩恵をきちんと受けるには最初から疎行列でデータを生成するべきである点には注意してください。)

from scipy import sparse
import numpy as np
M_array = np.random.choice(
    [0, 1, 2, 3, 4, 5],
    p=[0.9, 0.02, 0.02, 0.02, 0.02, 0.02],
    size=[10, 10]
)
M_array

# 出力例
array([[0, 3, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 4, 0, 0, 0, 0],
       [0, 0, 0, 0, 5, 0, 3, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 2, 0, 0],
       [0, 5, 0, 0, 0, 3, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

これを型変換します。方法は、strとintの変換と似たような感じで、lil_matrix(D)のようにするとできます。

M_lil = sparse.lil_matrix(M_array)
M_lil
# 出力
<10x10 sparse matrix of type ''
	with 9 stored elements in LInked List format>

これで変換できました。

printすると、0ではない成分の座標と値を保有していることが確認できます。
(ただし、実際のデータ構造は結構違います。print用に整形しているようです。)

print(M_lil)
# 以下出力
  (0, 1)	3
  (1, 3)	1
  (1, 5)	4
  (2, 4)	5
  (2, 6)	3
  (3, 7)	2
  (4, 1)	5
  (4, 5)	3
  (8, 9)	2

0行1列目が3, 1行3列目が1,という風に読んでいくと、確かに0以外の成分が記録されているのがわかります。

なお、実際のデータ構造は型ごとに違うのですが、lil_matrixの場合は次ように、
dataとrowsとうい二つの属性を使ってデータを保有しています。

print(M_lil.data)
'''
[list([3]) list([1, 4]) list([5, 3]) list([2]) list([5, 3]) list([])
 list([]) list([]) list([2]) list([])]
'''

print(M_lil.rows)
'''
[list([1]) list([3, 5]) list([4, 6]) list([7]) list([1, 5]) list([])
 list([]) list([]) list([9]) list([])]
'''

data方は、各行の0ではない要素の値、rowsにそれぞれの要素が何番目に入っているのかの情報を保有しています。
合計18個の数字で、10*10=100個の要素を持つ行列を表現できています。

あと、lil_matrixの重要なメリットして、スライスで値を取り出せるし、代入もできるという点があります。

print(M_lil[0, 1])
# 3

(できて当然に思えますが、他の疎行列のデータ型によってはこれができないものがある。)
そのため、 lil_matrix で疎行列を作って、それを(その他のメリットを持つ)他の型に変換して使うというやり方をよくやります。
(Intended Usageにそう書いてあるので従っています。)

最後に、arrayに戻す方法は toarray()です。

M_lil.toarray()
# 出力
array([[0, 3, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 4, 0, 0, 0, 0],
       [0, 0, 0, 0, 5, 0, 3, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 2, 0, 0],
       [0, 5, 0, 0, 0, 3, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int64)