今回は、Hadoopでコサイン関数を計算する方法の最終回です。
おさらい
前回は、履歴から作成した、ユーザごとにアクセスしたアイテムのリストであるユーザシーケンスから、同一シーケンスの中に出現したアイテムのペアとそれらをアクセスしたユーザ数(シーケンスの数)を抽出しました。この段階でコサイン関数の計算に必要な要素が揃いました。
アクセスユーザ数からコサイン関数へ
第三段階の処理フローは次の通りです。ここでもアイテムIDを具体的なアイテム名で示しています。
- ①では、第二段階の出力結果を入力し、そのまま出力しています
- ②では、keyであるアイテムペアでソートしてReducerに渡しています。
- ③では、keyであるアイテムペアをアクセスしたユーザ数、および各アイテムをアクセスしたユーザ数を使いコサイン関数を計算します。
これをMapperおよびReducerで実装します。
Mapperは図2の①に相当します。このMapperは第二段階の出力結果をReducerにそのまま渡しているだけです。アイテムペアをkeyにしているので、Reducerにはこのアイテムペアでソートされた結果が渡されます。このペアはアイテムの組み合わせでなく順列になっていることに注意してください。同一keyであれば、同じ順列であり、同じReducerに渡されています。
Reducerは図2の③に相当します。主な処理はMapperの出力をマージして、アイテムペアごとの相関係数の計算です。
第二段階のReducerは任意の一組のアイテムのペアを順序を入れ替えものも含めて二通り(組み合わせでなく順列であることに注意)出力していたことを思い出してください。第三段階のReducerの処理直前では、同一keyであっても、valueにはペアを構成する両アイテムをアクセスしたユーザ数が含まれていますが、アイテムごとのアクセスユーザ数はどちらか一方しか含まれていませんでした。
図2の例では、「ザスーラ:ジュマンジ 3>2>0」と「ザスーラ:ジュマンジ 0>2>2」は同じkeyですが、valueを構成する値が違っていることに注意してください。ソートの結果、第三段階のReducerで、アイテムの順列が一致する=同一keyのデータを同じReducerで受けることから、初めて、keyを構成するアイテムのアクセス数を両方取得できます。
Hadoop Streamingを使って計算する
コサイン関数の計算に必要なMapperおよびReducerは全て揃いました。各段階でのMapper、Reducerおよび各段階の処理結果を保存するディレクトリを表1のとおりにすると、リスト3のようにHadoop Streamingの実行スクリプトを記述できます。
表1 各段階の処理結果保存ディレクトリ
処理の段階 | Mapper/ Reducer | 処理結果を出力 するディレクトリ |
第一段 | Mapper:mapper_for_gihyo_1.pl | gihyo |
Reducer:reducer_for_gihyo_1.pl |
第二段 | Mapper:mapper_for_gihyo_2.pl | gihyo2 |
Reducer:reducer_for_gihyo_2.pl |
第三段 | Mapper:mapper_for_gihyo_3.pl | gihyo3 |
Reducer:reducer_for_gihyo_3.pl |
第一段階の入力データ、Amazonのレビューデータは、この例ではディレクトリamazonにあります。
間単にスクリプトの内容を説明します。
- hadoop jar /opt/hadoop/contrib/streaming/hadoop-*-streaming.jar は、利用しているHadoopのバージョンに合わせて変えてください。
- -inputでMapperが読み込むデータのあるHDFSのディレクトリを指定します。
- -outputでReducerがデータを出力するHDFSのディレクトリを指定します。
- -mapperでMapperとなるスクリプトを指定します。
- -reducerでReducerとなるスクリプトを指定します。
- -fileでMapperおよびReducerとなるスクリプトファイルを指定します。
- -jobconf mapred.reduce.tasks=12でReducerの数を指定します。この例では12としています。
この計算結果をMySQLなどのデータベース、あるいはHBaseに保存することで、レコメンドシステムを実現できます。
処理を短くできないか?
今回の目的は、アイテム相関に基づくレコメンドを実施することでした。このレコメンドでは、基準となるアイテムごとに、他アイテムをアイテム相関の値で高い順にユーザに表示します。今回はそのアイテム相関をコサイン関数を用いて計算していますので、コサイン関数の値が高い順位にアイテムを表示することになります。
ここで、基準となるアイテム(ザスーラ)に対する他のアイテム(ジュマンジ、バトルランナー、はやぶさ)を表示する場合、ザスーラに対する他の映画のコサイン関数による値は図3の通りです。
表2 「ザスーラ」を基準とした各アイテムとアクセスユーザ数
アイテムおよびアイテムペア | アクセスユーザ数 |
ザスーラ | 3 |
ジュマンジ | 2 |
バトルランナー | 100 |
はやぶさ | 1000 |
ザスーラ:ジュマンジ | 2 |
ザスーラ:バトルランナー | 2 |
ザスーラ:はやぶさ | 2 |
これらの値に、基準となるアイテム(ザスーラ)の出現頻度3が共通して含まれていることがわかるでしょうか? これらの値をアクセスユーザ数3の平方根で割る場合、値は変わりますが、値の大小関係は変わりません。したがって、ザスーラと相関の強いアイテムとして、ジュマンジ、バトルランナー、はやぶさの順にユーザに対し推薦することになります。
このため、単にアイテムごとに他のアイテムのランキングを表示するのであれば、コサイン係数でなくこの値を計算するだけなので、二段目のReducerの出力結果だけで十分です。
コサイン関数以外は計算できるか?
もちろん、コサイン関数以外にも他の関数や指標を使って相関および類似度を計算できます。相関や類似度を求めるのに使われる関数や指標には次のようなものがあります。
表3 相関を使う場合に使用される指標の一覧
名称 | 定義 |
Jaccard係数 |
|
Dice係数 |
|
Simpson係数 |
|
Mutual Information (相互情報量) |
|
アイテムa, bのアイテムシーケンスをベクトルna,nbと表すと、表3の記号の意味はそれぞれ次の通り。ここではユーザのアイテムアクセスログを想定した表現にとなっています。
- na*nb
na,nbの内積。アイテムa, bを両方アクセスしたユーザの数。
- |na|,|nb|
na,nbの大きさ。それぞれアイテムa, bをアクセスしたユーザの数の平方根。
- |na ∩ nb|
アイテムa, bを両方アクセスしたユーザの数。
- |na ∪ nb|
アイテムa, bのどちらかをアクセスしたユーザの数。
- min(|na|, |nb|)
na,nbの比較。アイテムa, bをアクセスしたユーザの数のうち小さい方の数を返す。
- p(na ∩ nb), p(na), p(nb)
na ∩ nb, na, nbそれぞれの出現確率。
見ておわかりのとおり、これらの関数および指標は共通してna、nbのみで構成されています。したがって、コサイン関数を求めるのに使った関数、第三段目のReducerを変更するだけで、これらの関数や指標を計算できます。またReducerの中で同時に複数の関数および指標を計算することもできます。
次回はアイテムベースのレコメンドをコンテンツベースでの実装方法を紹介します。