SciPyの疎行列を利用して、膨大な量のデータ前処理を加速させる


# これなに？


広告分野での機械学習システムをpythonとScalaで開発している長谷川といいます。  
Web広告では一日に膨大な量のリクエストを受けるとともに、その特徴量の種類も非常に豊富なため、どうしても使用メモリ量や実行時間がボトルネックになることが多々あります。  
そのため、塵も積もればの精神で、日々細かい改善を繰り返しながら、パフォーマンスを改善しているのですが、その際に`scipy.sparse`の性質を利用することで、実行時間とメモリ使用量を改善できたことがあったので、その経験を元にしていくつか例を紹介します。

## scipy.sparseとは?
ざっくりいうと、疎である行列のメモリの持ち方を効率化するためのモジュールです。持ち方は、行いたい処理の性質に応じて、行指向の`csr形式`や列指向`csc形式`など、多々あるのですが、今回は**`coo形式(座標形式)`**の性質を利用して、処理を効率化します。

## COOの性質
1:  `coo`は行列の要素を(行,列)のタプルで指定し、指定しなかったものは0になるという性質があります。


```python
from scipy.sparse import coo_matrix
import numpy as np

value=np.ones(3)
row = np.array([0,1,2])
col = np.array([0,1,2])

mat=coo_matrix((value,(row,col)))
print(f'coo:{mat.toarray()}')
```

    coo:[[1. 0. 0.]
     [0. 1. 0.]
     [0. 0. 1.]]


上のように、座標形式で指定した要素のみが1となりました。

2: さらに、`coo_matrix`は同じ座標を指定すると要素が加算される性質があります。


```python
value=np.ones(4)
row = np.array([0,1,1,2])
col = np.array([0,1,1,2])

mat=coo_matrix((value,(row,col)))
print(f'coo:{mat.toarray()}')
```

    coo:[[1. 0. 0.]
     [0. 2. 0.]
     [0. 0. 1.]]


同じ座標で指定されている`(1,1)`の要素のみが加算されて2になりました  
この２つの性質を利用して、処理を効率化できる例を見ていきます。

# バージョン
- Python 3.7.1
- numpy==1.15.4
- pandas==0.23.4
- scikit-learn==0.20.1
- scipy==1.1.0

# 応用例



## 1. 大量のデータをOne-Hot Encoding
１つ目の例としては、大量のカテゴリデータをOne-Hot Encodingする場合です。  
仮のデータには`titanic`データの`embark_town`特徴量を使用します。


```python
import pandas as pd
import numpy as np
import scipy as sp
from scipy.sparse import coo_matrix 
from seaborn.utils import load_dataset

# ダミー化したいデータ
x=load_dataset('titanic')['embark_town']
x=x.fillna('NaN')

# 見やすくするためDataFrameに変換
pd.DataFrame(x.head())
```




<div>
<style scoped>

</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>embark_town</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>Southampton</td>
    </tr>
    <tr>
      <th>1</th>
      <td>Cherbourg</td>
    </tr>
    <tr>
      <th>2</th>
      <td>Southampton</td>
    </tr>
    <tr>
      <th>3</th>
      <td>Southampton</td>
    </tr>
    <tr>
      <th>4</th>
      <td>Southampton</td>
    </tr>
  </tbody>
</table>
</div>



`pandas.factorize`でindexに変換します


```python
# 追加でdummy化するデータと整合性を保つためsortしておく
x_index,category=pd.factorize(x,sort=True) 
x_index[:10]
```




    array([3, 0, 3, 3, 3, 2, 3, 3, 3, 0])



欠損値も含めてカテゴリは以下のようになりました。


```python
category
```




    Index(['Cherbourg', 'NaN', 'Queenstown', 'Southampton'], dtype='object')



ここから、`coo_matrix`の性質を利用します。  
`coo_matrix`をインスタンス化する際に必要な引数のタプルの第一要素に、座標に対応した(0ではない)要素の値を行列で
指定するわけですが、ここは、全て1かつ、ただの`view`で構わないので、`numpy.broadcast_to`を使って、無駄なメモリを使用しないように効率化します


```python
x_size=len(x_index)
row=np.arange(x_size)
x_coo=coo_matrix((np.broadcast_to(1,x_size),(row,x_index)))
```

`numpy.array`型に変化して中身をチェックしてみます。


```python
x_coo.toarray()[:10]
```




    array([[0, 0, 0, 1],
           [1, 0, 0, 0],
           [0, 0, 0, 1],
           [0, 0, 0, 1],
           [0, 0, 0, 1],
           [0, 0, 1, 0],
           [0, 0, 0, 1],
           [0, 0, 0, 1],
           [0, 0, 0, 1],
           [1, 0, 0, 0]])



できました。
本当正しくにダミー化できているのか確認するため、`pd.get_dummies`を使用した場合と結果が同じか確認します


```python
x_dummied=pd.get_dummies(x)                      
(x_coo.toarray()==x_dummied.values).all()
```




    True



全く同じ結果になってますね

### パフォーマンス
重要なのは、実行時間と使用するメモリがが本当に改善されているかです。それを確認するため、以下のように1000種類のカテゴリを持つ500万レコードのデータセットを想定して実験してみます。(簡単のため、すでにカテゴリごとのindexは割り振られているとします。)

```python
# 巨大なデータセットを作成(1000種類のカテゴリを持つ500万レコードのデータセット)
index=np.arange(0,1000)
test_data=np.random.choice(index,5000000)
```


メモリの使用量は`memory_profiler`を使用して計測します


```python
!pip install memory_profiler
```



```python
%load_ext memory_profiler
```





Jupyterのマジックコマンドを使って実行時間と使用したメモリを比べてみます

#### pandas.get_dummiesを使用した場合

実行時間


```python
%%timeit
import pandas as pd
pd.get_dummies(test_data)
```

    3.71 s ± 70.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


メモリ使用量


```python
%memit pd.get_dummies(test_data)
```

    peak memory: 4770.79 MiB, increment: 4558.70 MiB


`sparse`でないので、非常にメモリを食ってます

#### sklearn.preprocessingのOneHotEncoderを利用した場合
返り値が`sparse`になるようにオプションを設定します

実行時間


```python
%%timeit
from sklearn.preprocessing import OneHotEncoder
encoder=OneHotEncoder(categories='auto',sparse=True)
encoder.fit_transform(test_data.reshape(-1,1))
```

    1.1 s ± 83 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


メモリ使用量


```python
%%memit 
from sklearn.preprocessing import OneHotEncoder
encoder=OneHotEncoder(categories='auto',sparse=True)
encoder.fit_transform(test_data.reshape(-1,1)) 
```

    peak memory: 388.10 MiB, increment: 0.00 MiB


返り値が`sparse`なので、メモリは少なくすんでますが、処理に時間がかかってます

#### sparse.coo_matrixを応用する場合
これが本命

実行時間


```python
%%timeit
from scipy.sparse import  coo_matrix
test_size=len(test_data)
row=np.arange(test_size)
coo_matrix((np.broadcast_to(1,test_size),(row,test_data)))
```

    53.3 ms ± 1.92 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)


使用メモリ


```python
%%memit 
from scipy.sparse import  coo_matrix
test_size=len(test_data)
row=np.arange(test_size)
coo_matrix((np.broadcast_to(1,test_size),(row,test_data)))
```

    peak memory: 388.16 MiB, increment: 0.01 MiB



`coo`形式で変換したほうが速く、メモリも少量ですみます。    
ただし、pandasやscikit-learnのメソッドを使用したほうが`pandas.factorize`でやるようなindexづけなどのencodingに必要な前処理を裏側でやってくれるので、極端に大きなDataSetでない限りはそちらで良いかなと思います。  
ちなみに、`pandas.get_dummies`のオプションの`sparse`というのがありますが、`True`にすると返り値の型が`SparseDataFrame`になるので、諸々要注意です(少なくとも実行時間がさらに遅くなります)

## 2. 大量のデータから混同行列を作成する

別例として、加算される性質を利用して、混同行列(confusion matrix)を生成する応用例も上げます


```python
# 利用するデータ
N=100000
rng = np.random.RandomState(1)

data1=rng.randint(0,10,size=N)
data2=rng.randint(0,10,size=N)
```

### scikit-learnのcofusion_matrixを使った場合

まず、`sparse`を使わない標準的なやり方でやってみます


```python
from sklearn.metrics import confusion_matrix
import seaborn as sns
mat_sk=confusion_matrix(data1,data2)

sns.heatmap(mat_sk.T, square=True, annot=True, fmt='d', cbar=False, cmap='RdPu')
```




![output_54_1.png](https://qiita-image-store.s3.amazonaws.com/0/119585/99b82ad2-c956-e29b-8f0f-8a11d6e2eb26.png)




### coo_matrixを使った場合

coo_matrixを使って同じ混同行列を作成してみます


```python
mat_coo=coo_matrix((np.broadcast_to(1,N),(data1,data2)))

sns.heatmap(mat_coo.toarray().T, square=True, annot=True, fmt='d', cbar=False, cmap='RdPu')
```





![output_57_1.png](https://qiita-image-store.s3.amazonaws.com/0/119585/9324c281-fc4e-a10e-2f22-0f318aa90d1c.png)


全く同じ混同行列が作成できました

### パフォーマンス
実行時間にどれ位の差がでるかも確認してみます


```python
# scikit-learnのconfusion_matrixを使用
%timeit mat_sk=confusion_matrix(data1,data2)
```

    80.6 ms ± 1.22 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)



```python
# coo_matrixを使用
%timeit mat_coo=coo_matrix((np.broadcast_to(1,N),(data1,data2))).toarray()
```

    944 µs ± 23.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


前の例と同じように、`coo_matrix`を使用したほうが圧倒的に速いですね。

# 感想とか

`sparse_matrix`の性質をうまく利用すると、データ量が多くなれば多くなるほど、`scipy.sparse`をうまく利用すると、実行時間、メモリともに効率化できることが多々あります。  
ただし、`scipy.sparse` の性質を知った上で利用しないと、むしろ処理の速度を悪化させる場合があるのもあるので、注意が必要です。  
また、コード自体の可読性も下がるので、極端に巨大なデータでなかったり、そもそも処理を効率化させる必要がない場合は、一般的なモジュールのメソッドを使うほうがおそらく良いです。  
`scipy.sparse`の他の性質については[こちらの本](https://www.oreilly.co.jp/books/9784873118604/)に非常に丁寧にまとまっているので、とてもおすすめです。  
データ前処理でもろもろ工夫している例はまだまだ他にもいくつかあるので、ぼそぼそ上げてければと思います。