「CSR形式」を理解するのに時間がかかったので自分なりにまとめてみた

機械学習の勉強を始めて、めちゃくちゃ初歩の初歩で詰まりました。
疎行列を表す「CSR形式」が理解できない…。

参考にさせていただきました。ありがとうございます。
https://qiita.com/iwasaki620/items/603220d9102e82d4438e

# 疎行列
非0値(Number of Non-Zero, NNZ)が少なく、要素の大半が0で埋められているような行列です。
例えばこんなの。
![CodeCogsEqn.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/2c834b45-5b6b-833a-6b4d-7052bd8840c0.gif)

この程度の行数×列数であれば大丈夫ですが、行も列も数十万・数百万・あるいはそれ以上のオーダーがある場合、メモリに載せられないといったことも起こりえます。無駄な計算も増えます。

#CSRは疎行列を表現する形式の一つ
ということで「効率良く疎行列を表記しましょう」という形式の一つがCSR形式です。
他にも色々ありますがCOOとCSR以外省きます。

#COOについて
効率良く疎行列を表現するためには0以外の値がどの座標にあるかを示してそれ以外を0とみなせば良いですよね。
例えば
![CodeCogsEqn (1).gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/910f9262-7fda-4774-de5d-73f5db559ce8.gif)
こんな行列があったとすると、値と行と列の対応は
![Untitled Diagram-Page-4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/775e90f6-8a37-77af-483e-503cef173083.png)
このようになります。(0インデックス)
座標で書くとこうなりますね。

    (0,0) 1
    (0,3) 2
    (1,1) 3
    (2,0) 1
    (3,2) 5

4行4列程度なのであまり違いはないですが、行・列が増えていくと顕著に差が出ます。

# CSRについて
次にCSRです。こいつを理解するのに時間がかかりました。

## CSRでは、「その行に属する値と列がどこから始まるか」をポインタで表す
ここが肝要で、理解できていなかった原因でした。
CSRでは、行のインデックスではなく「Index Pointer」と値・列で行列を表します。

先ほどの行列、
![CodeCogsEqn (1).gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/2b5e8002-5850-7251-cba9-683006d41621.gif)
の値・行・列を、行ごとに着色してみましょう。

![csr-Copy of Page-6 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/ae9b440c-b293-62cc-d759-2d7148a27e1a.png)
このようになります。
各行に属する値がどこから始まるかわかりやすくなりました。

この表は、こう書き直すこともできますよね。
![csr-Copy of Page-6 (3).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/a44add6c-2aa5-45b9-0049-2363b10efb74.png)

そう、このポインタの矢印が「Index Pointer」となります。

つまり、配列「Index Pointer」は **[0,2,3,4,5]** と表され、図にすると
![csr-Copy of Copy of Page-6 (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/a8f46e20-b78f-29eb-61b8-43840dc312d3.png)

となるわけです。
実際、

```python
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の行を含む行列があったとします。
![CodeCogsEqn (2).gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/d56495e6-3fc5-afe3-81bc-c59704e48e0d.gif)
この場合、Index Pointerはどうなるでしょうか？

まずCOO形式で確認してみましょう。
![csr-Page-10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/91205b33-f746-1f42-d90f-1d011ee31a7b.png)
こうなります。

これをCSR形式で表す場合、空の行である1行目と3行目の開始位置はどこになるでしょうか？
答えは
![csr-Copy of Page-10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/655411/e6cfef83-f5be-b213-c9e4-f33a68a49aaa.png)
こうです。
なぜなら、 **その行に1つもNNZが無いので、ポインタは動かない** からです。
したがって、Index Pointerの配列は **[0,3,3,4,4]** になります。

```python
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]

「行ごとにポインタで表す」をちゃんと理解してないと腑に落ちないですねー。