疎行列（Sparse Matrix）を使ってメモリを節約する

データエンジニアだったりデータアナリストだったりします。 @kazasiki です。

データ分析でわりと使うのにいまいち知名度が低そうなデータ構造に、疎行列(Sparse Matrix)もしくは疎配列(Sparse Array)というのがあります。名前だけは知っているという人も多いのではないでしょうか？

この記事では、疎行列の概念と構造を簡単に紹介しつつ、Pythonのデータ分析系のライブラリでどんな感じで使われてるかを書いていきます。実際にどのくらい性能が上がるのかとか、サンプルコードとかは割愛するので、そのあたりは別の記事を参照していただければ幸いです。

疎行列とは

wikipediaの説明を引用するとこんな感じです。

数値解析と計算科学の分野において、疎行列（そぎょうれつ、英語: sparse matrix）または疎配列（英語: sparse array）とは、成分のほとんどが零である行列のことをいう[1]。スパース行列とも言う。(中略)。行列のゼロ要素の数を要素数の合計で割った値を、行列のスパース性（sparsity）と呼ぶことがある。

$\begin{bmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{bmatrix}$

（例えば）上の疎行列には非ゼロ要素が9個しかなく、ゼロ要素は26個ある。スパース性は74%であり、密度は26%である。

格納形式

疎行列を効率的に格納する格納方式としてはいろいろな方式がありますが、わかりやすい方式としてCOO方式があります。Coordinate(座標)の略らしいです。名前はちょっと分かりづらいです。

例えば以下のような行列があるとします。

$\begin{bmatrix} 0 & 5 & 6 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 7 \end{bmatrix}$

それを以下のような構造で保持します。

data = [5, 6, 7]
row = [0, 0, 3]
col = [1, 2, 3]

意味はそのまんまで、行列に含まれる0以外の値を 行・列・値 の3つの値で保持していくだけです。この例ではそこまで恩恵を感じないかもしれませんが、スパース性の高い大きな疎行列を素直に格納するよりもCOO方式が少ないメモリで等価な情報を保存できるイメージが付いたんじゃないでしょうか？

この他にもCSR方式(Compressed Row Storage)などさらに効率が良い方式もありますが、ここでは割愛します。恐らく実用的にはそちらのほうが用いられてる事が多いです。

また、概念としては色んな集合に応用できるもので、単純なところでは疎配列(Sparse Array)も広く用いられてます。同じような仕組みを持つ配列のことです。

実装例

疎行列が使えるライブラリとして一番の有名どころはやはりscipyだと思います。

docs.scipy.org

基本的な使い方や性能検証などは別の方の記事に纏まってるので割愛させていただきます。

note.nkmk.me

活用例：TF-IDF

実際どんな処理をするときに疎行列を使うのかといえば、いろいろありますが、個人的に身近なのは自然言語処理におけるTF-IDFです。

wikipediaの説明を引用するとこんな感じです。

tf–idfは、term frequency–inverse document frequencyの略であり、コーパスや収集された文書群において、ある単語がいかに重要なのかを反映させることを意図した統計量（数値）である。

Term frequencyは単語の頻度、Inverse document frequencyは逆文書頻度という意味です。TF-IDF自体の解説をすると長くなるのでここではバッサリ省略します。

ざっくりとした特徴として、例えば あめんぼ赤いなあいうえお と あめんぼは赤くないのでわ？ という文書があるとします。この文書群に対して以下のようにTF-IDFを計算すると、列に全ての文書中にある単語、各文書が1つの行。文書に含まれない単語は0、文書に含まれる単語は 0<x<=1 の値となるテーブルが作られます。（ここでは１文書が１文となってますが、実際は文書中の文の数や長さは問いません）

文書	あいうえお	あめんぼ	ない	ので	赤い	赤く
あめんぼ赤いなあいうえお	0.632	0.449	0.000	0.000	0.632	0.000
あめんぼは赤くないのでわ？	0.000	0.380	0.534	0.534	0.000	0.534

値が各文書における単語の重要度なのですが、それは置いておいて、計算対象となる文書とそれに含まれる単語が増えていったときに疎行列になりそうだな〜ということは分かってもらえたでしょうか。

実際のところ、例えばsciki-learnのTF-IDF関連の機能の計算結果は疎行列の値で返されています。

scikit-learn.org

見慣れないTypeの値かもしれませんが、安易に普通のnumpy.matrixとかに変換してしまうとメモリを大量に消費してしまう可能性があるので注意しましょう。

pandasでの事情

Pythonでデータ解析する人は大抵pandasを使ってると思うのでpandasの話をすると、pandasはdtypeとして疎配列(Sparse Array)に対応してます。DataFrameの特定の列だけ指定する形です。さすがにDataFrame全体もしくは部分を疎行列として保持することは難しいようです。

pandas.pydata.org

pandasの疎配列は少し高機能で、 ほとんどの値が0 でなくても、 ほとんどの値が同じ なら効率的にデータを扱うことが出来ます。例えば ほとんどの値がnan などでも同様に扱えます。疎行列の0にあたる部分の値を任意で指定できます。

メモリの節約になるのも勿論ですが、dtypeで指定してあればそのカラムのデータがスパース性の高いデータであることを示せます。扱うデータにそういったデータが有れば積極的に使ってみましょう。

ちなみにpandasであれば、 category というdtypeもあります。

pandas.pydata.org

こちらはカーディナリティが低いデータに対応するデータ構造で、性別や血液型などごく少ない種類の値のデータを扱う際に有効です。

内部的には整数として保持されるだけなので疎行列のような効果は期待できないですが、上記のような性質を持つ文字列型のカラムをcategory型にすることである程度の効果が得られる可能性はあります。データの性質をコードで示すという意味でも有効なのでこちらも積極的に使ってみましょう。

まとめ

ということで疎行列(Sparse Matrix)の紹介記事でした。概念やライブラリの紹介はちょこちょこあるんですが、scikit-learnやpandasと絡めた記事があんまりなさそうだったので書いてみました。どれくらいメモリの節約になるのかみたいな計測も他の記事でされてるので割愛しました。この記事では理屈や用途を理解していただければ幸いです。