自然言語処理やレコメンドシステムの開発などをやっていると、サイズは非常に大きいが成分のほとんどは0という行列が頻繁に登場します。
そのような行列を疎行列と言います。
疎行列 – Wikipedia
これをそのまま扱うと、メモリは無駄に消費するし無駄な計算は増えるしで非常に効率の悪いことになります。
そのため、scipyでは疎行列を専門に扱う scipy.sparse というモジュールが用意されています。
ドキュメント: Sparse matrices (scipy.sparse)
リンク先を見たらわかる通り、疎行列を表す型は結構色々な種類があります。(Sparse matrix classes 参照)
それぞれ、他の型との変換が高速とか、行方向/列方向の取り出しが早いとか個別にメリットを持っていますが、
共通しているのはデータ量を大幅に節約できる点です。
今後の記事でいくつか紹介する予定ですが、とりあえずデータ量を削減できるって特徴だけでも確認しておきましょう。
疎行列のメリットを感じるにはかなり小さいのですが、乱数で10*10の疎行列(array型)を作って、
それを lil_matrix に変換して、中のデータを見てみましょう。
まずデータ作成。
(今回はサンプルとして、array型でデータを作って変換していますが、
省メモリの恩恵をきちんと受けるには最初から疎行列でデータを生成するべきである点には注意してください。)
from scipy import sparse
import numpy as np
M_array = np.random.choice(
[0, 1, 2, 3, 4, 5],
p=[0.9, 0.02, 0.02, 0.02, 0.02, 0.02],
size=[10, 10]
)
M_array
# 出力例
array([[0, 3, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 4, 0, 0, 0, 0],
[0, 0, 0, 0, 5, 0, 3, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 3, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
これを型変換します。方法は、strとintの変換と似たような感じで、lil_matrix(D)のようにするとできます。
M_lil = sparse.lil_matrix(M_array)
M_lil
# 出力
<10x10 sparse matrix of type ''
with 9 stored elements in LInked List format>
これで変換できました。
printすると、0ではない成分の座標と値を保有していることが確認できます。
(ただし、実際のデータ構造は結構違います。print用に整形しているようです。)
print(M_lil)
# 以下出力
(0, 1) 3
(1, 3) 1
(1, 5) 4
(2, 4) 5
(2, 6) 3
(3, 7) 2
(4, 1) 5
(4, 5) 3
(8, 9) 2
0行1列目が3, 1行3列目が1,という風に読んでいくと、確かに0以外の成分が記録されているのがわかります。
なお、実際のデータ構造は型ごとに違うのですが、lil_matrixの場合は次ように、
dataとrowsとうい二つの属性を使ってデータを保有しています。
print(M_lil.data)
'''
[list([3]) list([1, 4]) list([5, 3]) list([2]) list([5, 3]) list([])
list([]) list([]) list([2]) list([])]
'''
print(M_lil.rows)
'''
[list([1]) list([3, 5]) list([4, 6]) list([7]) list([1, 5]) list([])
list([]) list([]) list([9]) list([])]
'''
data方は、各行の0ではない要素の値、rowsにそれぞれの要素が何番目に入っているのかの情報を保有しています。
合計18個の数字で、10*10=100個の要素を持つ行列を表現できています。
あと、lil_matrixの重要なメリットして、スライスで値を取り出せるし、代入もできるという点があります。
print(M_lil[0, 1])
# 3
(できて当然に思えますが、他の疎行列のデータ型によってはこれができないものがある。)
そのため、 lil_matrix で疎行列を作って、それを(その他のメリットを持つ)他の型に変換して使うというやり方をよくやります。
(Intended Usageにそう書いてあるので従っています。)
最後に、arrayに戻す方法は toarray()です。
M_lil.toarray()
# 出力
array([[0, 3, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 4, 0, 0, 0, 0],
[0, 0, 0, 0, 5, 0, 3, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 3, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], dtype=int64)