SciPyでの疎行列（sparse matrix）の膨大な量のデータ前処理

1. 疎行列（sparse matrix）の概要

疎行列とは、ほとんど行列の要素がゼロであるような行列です。行列内のほとんどが0という特徴から、0を無視する工夫をすれば、メモリや計算速度を節約が可能になります。疎行列ではない、よくある行列を「密行列」（dense matrix）と呼ぶこともあります。数値計算や機械学習や自然言語処理など幅広い分野で扱われています。

以下の図は10×10の密行列と10×10の疎行列になります。8割近くが0の疎行列で非ゼロ部分だけ用いて計算すれば、計算時間が約2/10になり計算が早く終わらせることが可能になります。

PythonのSciPyライブラリには、疎行列を作成、保存、操作するための多くのオプションがあります。PythonのScipyを用いて、疎行列計算について解説していきます。

密行列（dense matrix）
85、90、99ゼロ率の10,000 x 10,000密行列のデータを作成します。

# Create Sparse Data
import numpy as np
from scipy import sparse
from scipy.stats import uniform
from sys import getsizeof

np.random.seed(seed=42)
array = uniform.rvs(size=100000000, loc = 0, scale=2)
array = np.reshape(array, (10000, 10000))
sparse_85 = np.where(array<1.70, 0, 1)
sparse_90 = np.where(array<1.80, 0, 1)
sparse_99 = np.where(array<1.98, 0, 1)

sparse_85

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

行列の平均計算時間を比較しました。ゼロ件が多くになると、ちょっと計算時間が増やします。

%%time
print(sparse_85.mean())

0.14997601
Wall time: 90.5 ms

%%time
print(sparse_90.mean())

0.09997476
Wall time: 91.8 ms

%%time
print(sparse_99.mean())

0.01001172
Wall time: 97.7 ms

密行列は結構メモリーをかがります。

# Get Memory size
print(getsizeof(sparse_85))
print(getsizeof(sparse_90))
print(getsizeof(sparse_99))

400000112
400000112
400000112

3.1 COO方式(座標形式)

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

COO方式のメリット
・スパースフォーマット間の高速変換を容易にします
・重複エントリを許可します（例を参照）
・CSR / CSCフォーマットとの間の非常に高速な変換

COO方式のデメリット
・直接サポートしていません：
・算術演算
・スライス

各密行列がcoo形式の疎行列にを変更します。

mat_coo_85 = sparse.coo_matrix(sparse_85)
mat_coo_90 = sparse.coo_matrix(sparse_90)
mat_coo_99 = sparse.coo_matrix(sparse_99)
print(mat_coo_85)

(0, 1) 1
(0, 7) 1
(0, 11) 1
(0, 33) 1
: :
(9999, 9988) 1
(9999, 9989) 1
(9999, 9990) 1

平均計算の時間をみると、ゼロ率が多くになれば、実行時間が減らします。

%%time
print(mat_coo_85.mean())

0.14997600999999874
Wall time: 366 ms

%%time
print(mat_coo_90.mean())

0.09997475999999916
Wall time: 254 ms

%%time
print(mat_coo_99.mean())

0.010011720000000003
Wall time: 29 ms

coo形式の疎行列はメモリーがかなり減少できます。

# Get Memory size
print(getsizeof(mat_coo_85))
print(getsizeof(mat_coo_90))
print(getsizeof(mat_coo_99))

56
56
56

3.2 CSR方式

圧縮行格納方式(Compressed Sparse Row)
CRS圧縮とは、行方向に探索し、非ゼロの行列の要素を格納していきます。
CSR方式のメリット
・効率的な算術演算CSR + CSR、CSR * CSRなど。
・効率的な行スライス
・高速行列ベクトル積

CSR方式のデメリット
・遅いカラムスライス操作（CSCを検討）
・スパース構造の変更には費用がかかります（LILまたはDOKを検討してください）

scipy.sparse.csr_matrix

CSR方式を圧縮します。

mat_csr_85 = sparse.csr_matrix(sparse_85)
mat_csr_90 = sparse.csr_matrix(sparse_90)
mat_csr_99 = sparse.csr_matrix(sparse_99)
print(mat_csr_85)

(0, 1) 1
(0, 7) 1
(0, 11) 1
: :
(9999, 9988) 1
(9999, 9989) 1
(9999, 9990) 1

ゼロ率が増やせば、実行時間が減らします。

%%time
print(mat_csr_85.mean())

0.14997600999999874
Wall time: 202 ms

%%time
print(mat_csr_90.mean())

0.09997475999999916
Wall time: 128 ms

%%time
print(mat_csr_99.mean())

0.010011720000000003
Wall time: 18 ms

CSR圧縮は結構メモリーが減少できます。

# Get Memory size
print(getsizeof(mat_csr_85))
print(getsizeof(mat_csr_90))
print(getsizeof(mat_csr_99))

56
56
56

3.3 CSC方式

圧縮列格納方式(Compressed Sparse Column: CSC)
CSC方式とは、非ゼロの行列の要素を格納していく。CSR方式の列バージョンです。

CSC方式のメリット
・効率的な算術演算CSC + CSC、CSC * CSCなど。
・効率的なカラムスライス
・高速行列ベクトル積（CSR、BSRの方が速い場合があります）

CSC方式のデメリット
・遅い行のスライス操作（CSRを考慮）
・スパース構造の変更には費用がかかります（LILまたはDOKを検討してください）

scipy.sparse.csc_matrix

mat_csc_85 = sparse.csc_matrix(sparse_85)
mat_csc_90 = sparse.csc_matrix(sparse_90)
mat_csc_99 = sparse.csc_matrix(sparse_99)
print(mat_csc_85)

(9, 0) 1
(16, 0) 1
(17, 0) 1
: :
(9978, 9999) 1
(9983, 9999) 1
(9989, 9999) 1

CSCの圧縮もゼロ率が増やせば、計算時間が減らします。

%%time
print(mat_csc_85.mean())

0.14997600999999874
Wall time: 215 ms

%%time
print(mat_csc_90.mean())

0.09997475999999916
Wall time: 124 ms

%%time
print(mat_csc_99.mean())

0.010011720000000003
Wall time: 15.1 ms

csc圧縮はメモリーがかなり減少できます。

# Get Memory size
print(getsizeof(mat_csc_85))
print(getsizeof(mat_csc_90))
print(getsizeof(mat_csc_99))

56
56
56

4. まとめ

85%、90%、99%ゼロ率の密行列を作成しました。一方、密行列の計算はかなりメモリーを利用します。圧縮方式に変更すると、メモリーは凄く減少ができました。一方、計算時間はゼロ率により変わります。ゼロ率が多ければ多いほど、計算時間が早くになることが確認できた。

担当者：HM
香川県高松市出身　データ分析にて、博士（理学）を取得後、自動車メーカー会社にてデータ分析に関わる。その後コンサルティングファームでデータ分析プロジェクトを歴任後独立　気が付けばデータ分析プロジェクトだけで５０以上担当
理化学研究所にて研究員を拝命中　応用数理学会所属

目次

1. 疎行列（sparse matrix）の概要

3.1 COO方式(座標形式)

3.2 CSR方式

3.3 CSC方式

4. まとめ