まとめ：Hadoop Mapreduceで大きな相関行列（行列の積）を計算する。(Summery : Calculating Large Correlation Matrix with Hadoop MapReduce）

今回のログで、密な行列同士の乗算を一旦終わりにしたいと思う。
この話題については、物理の方に論文がありそうなので、そちらをチェックする予定。Fast Multipole Methodなどの論文を、「チラ見」すると、確かに天体物理や磁場を研究する人たちに、大きな（密な）行列を計算する必要があるのは、もっともな話である。これらについては、なんらかまとまったら、ログにしようと思う。

さて、先のログで、5000行×5000列、10000行×10000列の行列積については、Amazon Elastic MapReduceによって、リーズナブルに計算できることが分かった。
相関行列の演算時間を処理単位でみれば、その殆どが行列積の演算（共分散行列の計算）で占められているので、相関行列の実行速度をあげるためには、行列積をいかに速く計算するアルゴリズムを採用するかにかかっている。
（上で述べたように、論文を調べて、なんらかの進展があれば、アルゴリズムを変えてみたい）

さて、多変量解析において、10,000変量というのは大きな数字と言ってよいと思うが、協調フィルタリングやクラスタリングといった機械学習の分野では、そうも言っていられない。ユーザーベースの協調フィルタリングでは、お客様をアイテム数次元の空間にプロットすることで類似度を計り（アイテム数が変量となり、お客様数がサンプル数となる）、アイテムベースでは、アイテムをお客様数次元のプロットとして類似度をはかる（お客様数が変量となり、アイテム数がサンプルとなる）。クラスタリングでも、協調フィルタリングと同様の「類似性概念」が用いられる。
以前のログにも書いたが、機械学習分野の観測値データは「疎な行列」であって、この場合、次元縮約により、分析する次元を落として計算するのが定石であって、プログラム的な扱いも全く異なる。

ここで、気になるのは、密な行列の積を行う、先のプログラムの有効性である。
先に提示したケース２のプログラムは、相関係数を求めるにあたって、変量方向には分割を許しているが、サンプル方向には分割を許していない。
そのため１行のバイト数が膨れ上がり、Hadoop MapReduce（のreduce処理）においてメモリーリークを誘発すると考えられる。

以下に20000行20000列の行列積を、10000の時と同じクラスタで実行した結果を示すが、行列積の部分だけ抜き出すと7.4倍の実行時間がかかる。演算回数が行（列）の3乗のオーダーであるから、2^3=8とほぼ一致しており、メモリーのリークが発生しない限り、理屈通りの実行速度を得ることができることがわかる。

	実行時間
10000行10000列	1,373sec(22mins,53sec)
20000行20000列	10,197sec(2hrs,49mins,57sec)

ケース２として示したアルゴリズムは、変量方向へは、分割情報をもとにパーティションを制御できるので、変量が10000が数万〜数十万と大きくなった場合、スケールアウトすればよい。

とすれば、課題はサンプル方向のデータ量の肥大であり、これはメモリーを多くつけるようにする、つまり「スケールアップ」で解決するしかなく、これではHadoop MapReduceの思想に反する。

しかし、幸運なことに、この問題については簡単に解決できる。以下にその実装方法を記す。
結論から言えば、共分散行列を算出する際に、データをサンプル方向に分割して行列積を計算し、結果を要素ごとに足し算すればよい。以下に、簡単な図と式で説明する。

共分散行の計算は以下であった。

ここで、下のように上第３式にある行列を転置したものをPとおく。

ここでPを以下のように変量方向に分割する。分割処理はMapperで実装すればよいだろう。

このとき、

が成り立つ。

したがって、部分行列Piに関して乗算をおこない、最後に足し合わせれば、大きいサンプルサイズになっても、メモリーのリークを防ぐ事ができる。
要素のインデックスも揃うので、実装は簡単だと思うので、時間があるときに実装してみたい。