Mahoutで分散レコメンド(1)

さて、ちょっと間があきましたが。

前回まで、いったんレコメンドを抜けてクラスタリングの世界をご紹介してみた訳ですが。あまりウケがよさそうじゃないのでレコメンドに戻ってみます。

そんな中でMahoutが一押しであるのは、スケーラビリティの確保に重点が置かれていることです。

機械学習というのは、当然、計算に基づいて結果を出すわけですが、その基礎となるデータが多ければ多いほど、確からしい結果を出してくれます。が、しかし、データが多ければ多いほど、指数的に計算量が増加する傾向があります。

Apache Mahoutで機械学習してみるべ - 都元ダイスケ IT-PRESS

という導入から紹介に入ったレコメンドですが、実はあのアルゴリズムは分散処理できません。できませんったらできません。だってMapReduceパラダイムで書いてないんだもん。

ということで、先日紹介した処理をそのままMapReduce処理に変換できれば嬉しかったんですが。残念ながら、紹介したアルゴリズムをそのまま、分散処理の恩恵が受けられるようにMapReduceパラダイムに変換することは、できないようです*1。まぁ、出来ないのか異様に難しいのか、わからないけどとにかくMahoutには実装がないです。

つまり、「分散処理の恩恵が受けられるMapReduceパラダイムとして記述できるレコメンデーションアルゴリズム」ってのが必要なんですね。というわけで、先日紹介したアルゴリズムは、まずサッパリ忘れてください。新しいの行きます。

Hadoop税

新しいアルゴリズムを紹介する前に。HadoopってのはMapReduceパラダイムを使って上手い事スケーラビリティを得られるプラットフォームな訳ですが、スケーラビリティは必要ではない場合、つまり扱うデータが小さく従来の非分散レコメンドアルゴリズムでも現実的な時間内で計算が終了する場合、逆に時間を食います。

非分散レコメンドは、データが小さい状態であれば「リアルタイム処理*2」ができます。しかし、これから紹介する分散レコメンドのアルゴリズムでは、どんなにデータが小さくても少なくとも5分程度の処理時間必要、つまり「バッチ処理*3」しかできません。

バッチ処理では、「最新の評価情報にリアルタイムで追従する」ことができなくなる、というトレードオフは認識しておきましょう。

類似度行列(similarity matrix)

数学の授業で習った「行列」って覚えてますか？*4

こんなの*5。まぁ、ビビらないで。ここで使うのはベクトルのかけ算（内積）だけです。

で、ちょっと思い出してほしいんですが。非分散レコメンドで「Similarity（類似度）」っていう概念が出てきました。ユーザ同士がどれだけ似ているかを表す値。この類似度は、ユーザだけでなく、アイテムにも適用できます*6。で、以前挙げた例では「ピアソン相関係数」っていう-1〜1の範囲の値をSimilarityとして利用しました。

アイテム（101〜107）同士のピアソン相関係数を、全組み合わせで算出して、表にしてみました。データ数が少なくて計算できない(NaN）ところが多いですが。

	101	102	103	104	105	106	107
101	1.00	0.94	-0.80	0.77	-1.00	NaN	NaN
102	0.94	1.00	-0.98	0.99	NaN	NaN	NaN
103	-0.80	-0.98	1.00	-0.86	NaN	NaN	NaN
104	0.77	0.99	-0.86	1.00	NaN	NaN	NaN
105	-1.00	NaN	NaN	NaN	1.00	NaN	NaN
106	NaN	NaN	NaN	NaN	NaN	1.00	NaN
107	NaN	NaN	NaN	NaN	NaN	NaN	1.00

まず、101vs101や107vs107など、同じアイテム同士の類似性は、完全一致ってことで1.00になってます。当然ですが。しかしこんな値は当たり前すぎて計算に含めても全く意味がないので、全部NaNにしてしまいます*7。

この表の中身を行列として考えるんです*8。こういうのを類似度行列(similarity matrix)と呼ぶっぽいです。

ちなみに今回はピアソン相関係数を使った類似度行列を作りましたが、データの性質によって、共起(co-occurence)やユーグリッド距離(Euclidean distance)など、様々な「類似度」を使うことがあります。

でだ。次にユーザの評価表を考えます。ここではユーザ1の人に対してレコメンドをしてみようと思います。ユーザ1の評価データはこんなかんじ。

	ユーザ1
101	5.0
102	3.0
103	2.5
104	-
105	-
106	-
107	-

未評価の部分は0として、これも行列にするとこんなかんじ。これがユーザベクトル。

で、類似度行列とユーザベクトルの内積をもとめまーす。

はい、もう嫌になってきましたね。俺もです。

まぁ、こんな感じで求めた行列は、a〜fが101〜107の各アイテムに対する「オススメ度*9」になっています。この値が大きいアイテムがお勧めちゅーことですね。

今回のまとめ

レコメンドを分散アルゴリズムに対応させるためには、こんな感じで数学の世界にはまり込みます。俺も何故だかは分かりませんが、上記のアルゴリズムはMapReduceパラダイムで表現できるみたいです。

そろそろ理屈はお腹いっぱいですね。さて次回は実際にMahoutを使って分散レコメンドしてみます。

そういえば

Apache Mahout v0.5 リリースされましたね。おめでとうございます。

*1:ただし、「分散処理の恩恵があまり受けられない形で、先日のアルゴリズムをHadoop上に無理矢理乗せることは可能です。でも意味ないですね。

*2:つまり、Webアプリにおいて、ユーザからのリクエストをトリガとして計算を走らせ、その計算結果をレスポンスで返すような感じ。

*3:リクエストとは独立したバッチで事前に計算しておいて、リクエスト時に計算結果だけを参照する。

*4:まさか、はてなのTeX記法のお世話になる日が来ようとは…。

*5:俺あんま好きじゃなかったなぁ。なんか縦横無尽に掛けたり足したりするだけなんだけど、数式作ってるうちにどこを見てるんだか分かんなくなって…。

*6:アイテム同士がどれだけ似ているかを計算できる。

*7:NaNにしないと有害なのか、1.00のままでもいいのか、なんてのはよくわかりません。とりあえずMahoutん中ではNaNにしてるのですw

*8:うわ、ほんとにNaNだらけだな。最後まで計算できるか不安になってきたw

*9:ただし、この段階では非分散の時のような「予想評点」ではない。