Edited at
Fringe81Day 18

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


これなに?

広告分野での機械学習システムをpythonとScalaで開発している長谷川といいます。


Web広告では一日に膨大な量のリクエストを受けるとともに、その特徴量の種類も非常に豊富なため、どうしても使用メモリ量や実行時間がボトルネックになることが多々あります。


そのため、塵も積もればの精神で、日々細かい改善を繰り返しながら、パフォーマンスを改善しているのですが、その際にscipy.sparseの性質を利用することで、実行時間とメモリ使用量を改善できたことがあったので、その経験を元にしていくつか例を紹介します。


scipy.sparseとは?

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


COOの性質

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

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は同じ座標を指定すると要素が加算される性質があります。

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になりました


この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

1つ目の例としては、大量のカテゴリデータをOne-Hot Encodingする場合です。


仮のデータにはtitanicデータのembark_town特徴量を使用します。

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())




embark_town




0
Southampton


1
Cherbourg


2
Southampton


3
Southampton


4
Southampton

pandas.factorizeでindexに変換します

# 追加でdummy化するデータと整合性を保つためsortしておく

x_index,category=pd.factorize(x,sort=True)
x_index[:10]

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

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

category

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

ここから、coo_matrixの性質を利用します。


coo_matrixをインスタンス化する際に必要な引数のタプルの第一要素に、座標に対応した(0ではない)要素の値を行列で

指定するわけですが、ここは、全て1かつ、ただのviewで構わないので、numpy.broadcast_toを使って、無駄なメモリを使用しないように効率化します

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型に変化して中身をチェックしてみます。

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を使用した場合と結果が同じか確認します

x_dummied=pd.get_dummies(x)                      

(x_coo.toarray()==x_dummied.values).all()

True

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


パフォーマンス

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

# 巨大なデータセットを作成(1000種類のカテゴリを持つ500万レコードのデータセット)

index=np.arange(0,1000)
test_data=np.random.choice(index,5000000)

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

!pip install memory_profiler

%load_ext memory_profiler

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


pandas.get_dummiesを使用した場合

実行時間

%%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)

メモリ使用量

%memit pd.get_dummies(test_data)

peak memory: 4770.79 MiB, increment: 4558.70 MiB

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


sklearn.preprocessingのOneHotEncoderを利用した場合

返り値がsparseになるようにオプションを設定します

実行時間

%%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)

メモリ使用量

%%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を応用する場合

これが本命

実行時間

%%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)

使用メモリ

%%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)を生成する応用例も上げます

# 利用するデータ

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を使わない標準的なやり方でやってみます

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')


coo_matrixを使った場合

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

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')

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


パフォーマンス

実行時間にどれ位の差がでるかも確認してみます

# 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)

# 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の他の性質についてはこちらの本に非常に丁寧にまとまっているので、とてもおすすめです。


データ前処理でもろもろ工夫している例はまだまだ他にもいくつかあるので、ぼそぼそ上げてければと思います。