Hadoop MapReduceで相関行列を計算する。Roadmap for Calculating Large Correlation Coefficient Matrix based on Dense Matrix Multiplication with Hadoop MapReduce

今回から、数回に分けて変量間の相関行列（Peason相関係数が並んだ行列）

を求めていく。

注記；以前のログにも書いたが、Apache Mahoutの協調フィルタリングの実装には、Pearson相関係数によるSimilarity（類似度）計算が含まれている。このブログで示す結果と同じ結果をえるために、Mahoutを紐解くのもよいかもしれない。
これまでの議論は、協調フィルタリングの「ユーザーを変量、アイテムをサンプル、プリファレンス値を観測値」とした場合と同義である（これは、「ユーザーベースのリコメンダー」と呼ばれ、「アイテムベースのリコメンダー」の場合には、変量とサンプルの関係は逆になる）。ただし、協調フィルタリングでは、変量とサンプルのすべての組み合わせについてのデータは存在しない（それが当たり前であるし、そうでなければ、協調フィルタリングを使ってリコメンドする意味がない）。
因に、Mahoutで類似度を操作するクラスはUserSimilarity.javaというインターフェイスで実装されている。JavaDocから見る限り、Pearsonの相関係数の他に、アイテム数を次元とした空間でのユークリッド距離や、ユーザーをベクトルとした場合の挟角のCosine値、Spearmanの順位相関、谷本の類似度（ジャカードインデックス）、対数尤度が実装されているようだ。特殊な類似度が含まれているが、機械学習系にそのような論文があるのかもしれない。
類似度はノルムの条件を満たせばよいし、Preferenceが似ているものは基本的には「近く」分布する。

追記；「Mahout イン アクション」を読んだ限り、Mahoutの協調フィルタリングでMapReduceを用いるケースでは、類似度として上記の（PeasonやSpearmanの相関係数といいた）オプションは用いられず、供起行列（あるアイテムが他のアイテムと一緒に、同一ユーザーによって評価されているかの頻度を行列にしたもの）を類似度として用いているようだ。また、疎な行列（Sparse Matrix）を前提としてアルゴリズムを実装しているようなので、Mahoutのプログラムを密な行列（Dense Matrix）に適用できるか、はよく考える必要がある。
ただし、本が少し古いので、新しい実装があるかもしれない。

話がそれたが、復習として、相関行列Rの計算方法を以下にまとめておく。

変量間の相関行列の計算方法

相関行列Rは以下の式で計算される。

ただし、

であり、観測値は以下の表で表される。列が変量、行がサンプルを表す。

また、この行列は以下のように各変量を一行として、テキスト形式でデータ化する。

行インデックス 列インデックス 観測値

相関行列の算出ステップ

見通しをよくするために、以下に相関行列を求めるまでの、MapReduceジョブのステップを示す。
全体で８ステップとなるが、積和行列の算出は行列の積算となるので、内部に２つのMapReduceを含むこととなる。

実行時間の目標：以下のクラスターを用い、5000変量で、各変量につき5000サンプルあるとして1時間以内での計算を行うことを目標とする。

インフラ	Amazon Elastic MapReduce
リージョン	US Standard
インスタンスタイプ	m1.small
マスタ・インスタンスグループ	1インスタンス
コア・インスタンスグループ	8インスタンス
タスク・インスタンスグループ	10インスタンス

この場合のコストであるが、定価ベースでUS Standardのm1.smallが$0.06/hであるから、$1.14。EMRが$0.015/hであるから$0.285。合計で$1.425となる。（ただし、Amazon S3を使う場合には、別途、その費用が必要となる）