機械学習の勉強を始めて、めちゃくちゃ初歩の初歩で詰まりました。
疎行列を表す「CSR形式」が理解できない…。
参考にさせていただきました。ありがとうございます。
https://qiita.com/iwasaki620/items/603220d9102e82d4438e
疎行列
非0値(Number of Non-Zero, NNZ)が少なく、要素の大半が0で埋められているような行列です。
例えばこんなの。
この程度の行数×列数であれば大丈夫ですが、行も列も数十万・数百万・あるいはそれ以上のオーダーがある場合、メモリに載せられないといったことも起こりえます。無駄な計算も増えます。
#CSRは疎行列を表現する形式の一つ
ということで「効率良く疎行列を表記しましょう」という形式の一つがCSR形式です。
他にも色々ありますがCOOとCSR以外省きます。
#COOについて
効率良く疎行列を表現するためには0以外の値がどの座標にあるかを示してそれ以外を0とみなせば良いですよね。
例えば
こんな行列があったとすると、値と行と列の対応は
このようになります。(0インデックス)
座標で書くとこうなりますね。
(0,0) 1
(0,3) 2
(1,1) 3
(2,0) 1
(3,2) 5
4行4列程度なのであまり違いはないですが、行・列が増えていくと顕著に差が出ます。
CSRについて
次にCSRです。こいつを理解するのに時間がかかりました。
CSRでは、「その行に属する値と列がどこから始まるか」をポインタで表す
ここが肝要で、理解できていなかった原因でした。
CSRでは、行のインデックスではなく「Index Pointer」と値・列で行列を表します。
先ほどの行列、
の値・行・列を、行ごとに着色してみましょう。
このようになります。
各行に属する値がどこから始まるかわかりやすくなりました。
この表は、こう書き直すこともできますよね。
そう、このポインタの矢印が「Index Pointer」となります。
つまり、配列「Index Pointer」は [0,2,3,4,5] と表され、図にすると
となるわけです。
実際、
import numpy as np
from scipy import sparse
data = np.array([[1,0,0,2],[0,3,0,0],[1,0,0,0],[0,0,5,0]])
sparse_data = sparse.csr_matrix(data)
print("sparse_data.data = {}".format(sparse_data.data))
print("sparse_data.indices = {}".format(sparse_data.indices))
print("sparse_data.indptr = {}".format(sparse_data.indptr))
sparse_data.data = [1 2 3 1 5]
sparse_data.indices = [0 3 1 0 2]
sparse_data.indptr = [0 2 3 4 5]
なるほどねー！
…じゃあ、値が全部0の行(空の行)があったらどうなるんですか？
はい、ここでめっっっっっちゃ詰まりました。
「ポインタで表す」が理解できていなかったからですね。
例えば、こういう全ての値が0の行を含む行列があったとします。
この場合、Index Pointerはどうなるでしょうか？
まずCOO形式で確認してみましょう。
こうなります。
これをCSR形式で表す場合、空の行である1行目と3行目の開始位置はどこになるでしょうか？
答えは
こうです。
なぜなら、 その行に1つもNNZが無いので、ポインタは動かない からです。
したがって、Index Pointerの配列は [0,3,3,4,4] になります。
import numpy as np
from scipy import sparse
test_empty = np.array([[1,0,5,2],[0,0,0,0],[1,0,0,0],[0,0,0,0]])
sparse_empty = sparse.csr_matrix(test_empty)
print("sparse_empty.data = {}".format(sparse_empty.data))
print("sparse_empty.indices = {}".format(sparse_empty.indices))
print("sparse_empty.indptr = {}".format(sparse_empty.indptr))
sparse_empty.data = [1 5 2 1]
sparse_empty.indices = [0 2 3 0]
sparse_empty.indptr = [0 3 3 4 4]
「行ごとにポインタで表す」をちゃんと理解してないと腑に落ちないですねー。