第2回　レコメンドシステムの実装と課題

今回はレコメンドシステムの実装の問題と、その解決策として利用するHadoopについて説明します。

今回のポイントは以下の通りです。

スケールアップの限界
分散処理フレームワークの民主化
Hadoop Map Reduceの概要

増え続けるデータをどう扱うか

レコメンドシステムを協調フィルタリングのうち、ユーザベース方式により実装することを考えます。このシステムでは次のような映画の評価履歴を使い、「⁠この映画を評価した人はこの映画も評価しています」という映画の推薦を行います。

駄右衛門、ザスーラ、5、2009/12/21、・・・・
駄右衛門、ジュマンジ、5、2009/12/28、・・・・
菊之助、ブルースブラザーズ、5、2009/12/29、・・・・
利平、ザスーラ、4、2010/01/01、・・・・
十三、ハングオーバー、4、2010/01/01、・・・・
利平、ジュマンジ、4、2010/01/07、・・・・
力丸、バトルランナー、5、2010/01/15

この履歴は各行、左からユーザ名、映画のタイトル、その映画への評価、評価した時刻が含まれています。

最初に、この履歴を映画（アイテム）ごとにユーザを集約しリストを作成します。このリストをアイテムシーケンスデータと呼び、次のような形式になります。ここでは話を簡単にするために、評価や時刻など他の情報は落としてあります。

ザスーラ：駄右衛門、利平
ジュマンジ：駄右衛門、利平
ブルースブラザーズ：菊之助
ハングオーバー：十三
バトルランナー：力丸

前回の記事で、類似度の定義にはいろいろあると書きました。ここではその定義の1つとして、コサイン関数を使います。コサイン関数は2つのベクトルa（=(a₁,a₂,a₃,....,a_n)）, b（=(b₁,b₂,b₃,....,b_n)）を使うと、次のように定義できます。

コサイン関数は、2つのベクトルの要素が完全に一致すると1の値を取り、要素が全く一致しないと0になります。今回は、映画の類似度をコサイン関数で定義する場合、ユーザを要素とする映画のベクトルを考えることで計算できます。

「ザスーラ」と「ジュマンジ」のアイテムシーケンスをそれぞれベクトルa、およびベクトルbとすると、共にユーザ数が2であるので、|a|=|b|=√2 となります。

また、どちらの映画も駄右衛門および利平さんに評価されているので、a*b=2 となり、「⁠ザスーラ」と「ジュマンジ」の類似性は1となります。

他の映画の組み合わせについては、両方の映画を評価しているユーザが居ないので a*b=0 となり、映画の類似性は0です。

さて、ここまでの処理の実装方法について考えます。

通常、履歴から一気にそのままアイテム間の類似度の計算まで行うことは、履歴のデータサイズが小さくない限り、現実的にないと考えてよいでしょう。したがって、履歴、あるいはそこから抽出した情報をいったんデータベースに格納することになりますが、そのために、どんな環境を準備すればいいのでしょうか？

アイテムシーケンスを作成したら、それもデータベースに入れる必要が出てきます。単にデータのストレージだけでなく、あとから参照や演算等の処理を実行することを考えると、マシンのCPUやメモリのスペックも上げる必要があります。これはマシンのスケールアップによるアプローチです。

最後に、アイテム間の類似度の計算は、作成したアイテムシーケンスを“⁠全て⁠”読み込んでから実行します。アイテムIDが10万あり、類似度を浮動小数扱いにすると8バイトなので、類似度の結果は単純計算しても

100000×100000×8＝8×10¹⁰

で80ギガバイトもあります。履歴の収集開始時にはアイテム間で共通するユーザが無く（＝a*b=0⁠）⁠、類似度を計算できない場合もあるのでここまでメモリは必要になりませんが、履歴が蓄積されてくれば、使用するメモリ領域は増えてきます。

また、ユーザの新規加入やアイテムの追加があるため、このままでは単一マシンのメモリでは計算することが難しいのは明らかで、マシンのスケールアップでは解決が難しそうです。

巨人の肩に乗る

これまでにも、大量データの処理で直面する課題の解決方法はいろいろ考えられていますが、その中で最も有名かつ広く使われているのはGoogleが採用したアプローチです。正確には、そのアプローチのアイデア自体は昔からあったのですが、Googleの凄いところはページランク同様に実装したところです。

Googleの扱う大量データと言えば、全世界のWebコンテンツです。この大量データから検索結果の基となる情報ができるまでの流れを見てみましょう。

一連の処理では

大量のWebコンテンツをどこに格納するのか？
これらのコンテンツのインデクシングをどう実現するのか？
コンテンツ間のリンク解析をどうやって実現するのか？

といった課題に直面します。これらの課題を、マシンのスケールアップでなくスケールアウトで解決することをGoogleは選択し、誕生したのがGoogle File SystemとGoogle Map Reduceです。スケールアップがマシンのスペックを上げて集中処理するのに対し、スケールアウトは安価なマシンを組み合わせて分散処理するアプローチです。

GoogleはこれらGoogle File SystemとGoogle Map Reduceのコードは公開しないものの、その実装方法については論文として公開しました。この論文をもとにオープンソースとして実装されたのがHadoop HDFSとHadoop Map Reduceです。

HDFSは分散ファイルシステムであり、Hadoop Map Reduceは分散処理のフレームワークです。実装上の微妙な違いはあるものの、Googleが使っている大規模データの分散処理技術を、我々も自由に使えるようになりました。

Hadoopによる分散処理

Hadoop Map Reduceはフレームワークなので、MapおよびReduce関数は利用者側で設計することになります。MapとReduce間でやり取りするデータの構造は、<key value>のペアという形式の制約があるものの、この制約のおかげで利用者側は処理のロジックの設計に集中できます。

したがって、従来の分散処理と違ってメモリ、ジョブの管理、スケジューリングやデバッグといったシステムレベルでの管理方法を考えずにアルゴリズムの実装に集中できます。このアルゴリズムはデータが増えようが、クラスタを構成するマシンの数が増えようがそのまま適用できます。

Hadoopを使うと、Webコンテンツのインデクシングは、

HDFSにWebコンテンツを格納する
Hadoop Map ReduceでHDFS内のコンテンツに対してMap Reduceを実行する
HDFSに作成したインデックスを格納する

という3ステップで実現できます。

Hadoop Map ReduceはMapおよびReduceという2つの処理から構成され、Mapは抽出、Reduceは集約を受け持ちます。Mapを「コンテンツから、単語をkey、コンテンツのIDをvalue⁠」⁠、Reduceを「単語ごとにリストを作成する」と設計すれば、以下のようにWebコンテンツのインデックスを生成できます。

ここで各コンテンツに対してMapは並列に同じ処理を実行し、Reduceはその結果を集約しています。もし、可変長のN-gramのインデックスを作りたいというのであれば、valueに単語の出現位置なども入れることになりますが、基本はこの<key value>の形式でデータをやり取りします。

この例で示すように、Map Reduceは、処理を個々のマシンでなくクラスタ全体で実行します。データを分割して計算する場合、データをクラスタ内のローカルディスクに分散し、そのデータがあるノード上で処理を実行、つまりストレージと演算処理を単一ノード上で実行するアプローチをとります。したがって、従来のアルゴリズムをこのフレームワークで実行できるように再設計する必要があります。先ほどの映画の履歴では、何をkey、何をvalueにすれば良いのでしょうか？

次回の記事ではこの説明をしたいと思います。

それまでにHadoopの環境設定とAmazon Review data setの準備をお願いします。実装はHadoop StreammingとPerlを利用します。

なお、Hadoopの詳細な設定については本家ApacheのHadoopサイトをはじめ、各種の文献、書籍等をご覧ください。