Hadoopでレコメンドシステムを作ろう

第5回レコメンドシステム-協調フィルタリングのHadoopへの実装[後編]

今回は、Hadoopでコサイン関数を計算する方法の最終回です。

おさらい

前回は、履歴から作成した、ユーザごとにアクセスしたアイテムのリストであるユーザシーケンスから、同一シーケンスの中に出現したアイテムのペアとそれらをアクセスしたユーザ数(シーケンスの数)を抽出しました。この段階でコサイン関数の計算に必要な要素が揃いました。

図1 前回までに説明した処理の範囲
図1 前回までに説明した処理の範囲

アクセスユーザ数からコサイン関数へ

第三段階の処理フローは次の通りです。ここでもアイテムIDを具体的なアイテム名で示しています。

図2 第三段階の処理フロー
図2 第三段階の処理フロー
  • ①では、第二段階の出力結果を入力し、そのまま出力しています
  • ②では、keyであるアイテムペアでソートしてReducerに渡しています。
  • ③では、keyであるアイテムペアをアクセスしたユーザ数、および各アイテムをアクセスしたユーザ数を使いコサイン関数を計算します。

これをMapperおよびReducerで実装します。

リスト1 Mapperの処理
#!/usr/bin/perl

use strict;

while (<STDIN>) {
        chomp $_;
        print ( $_ . "\n" );
}

Mapperは図2の①に相当します。このMapperは第二段階の出力結果をReducerにそのまま渡しているだけです。アイテムペアをkeyにしているので、Reducerにはこのアイテムペアでソートされた結果が渡されます。このペアはアイテムの組み合わせでなく順列になっていることに注意してください。同一keyであれば、同じ順列であり、同じReducerに渡されています。

リスト2 Reducerの処理
#!/usr/bin/perl

use strict;

my ($key0,$value) = ();
my ($key,$id) = ();
my $co = 0;
my $corr = 0;
my %co_count = ();
my %key_count = ();
my $key_current = "";
my @list = ();

while (<STDIN>) {
        chomp $_;
      #入力したデータをkey0とvalueのペアに分割する。分割するデリミタはMap関数の出力形式に合わせる。
      #ここでは前出のMapperのkey及びvalueがタブ区切りで出力したので、デリミタをタブにする。  
        ($key0,$value) = split(/\t/,$_);
      #key0はアイテムペアなので、$key及び$idのアイテムに分割する。分割するデリミタは第二段階のReducerの出力形式に合わせる。	
        ($key,$id) = split(/:/,$key0);

      #key値が変わった=以前のkeyに関するデータの読み込みが終了のサインなので、以前のkeyである$key_currentに対する処理を開始する。
        if ( $key ne $key_current )  {
                if ($key_current ne "" && ( keys (%co_count) > 0 ) ) {
                        foreach $id ( sort keys %co_count ) {
                 #アイテムペアをアクセスしたユーザ数をダブルカウントしているので、二で割る。    
                                $co = $co_count{$id}/2;
                                $corr = $co/($key_count{$key_current}*$key_count{$id});
                #基準とするアイテムのID、ペアとなったアイテムID2、基準とするアイテムをアクセスしたユーザ数、両アイテムをアクセスしたユーザ数、ペアとなったアイテムをアクセスしたユーザ数、両アイテムの相関係数の順に出力 	  
                                print ($key_current . "\t". $id . "\t" . $key_count{$key_current} . "\t" . $co . "\t" . $key_count{$id} . "\t" . $corr . "\n");
                        }
                }
            #比較対象となるkeyを変更する
               $key_current = $key;
               $corr = %key_count = %co_count = @list = ();
        }
        if ( $value =~ /(\d+)>(\d+)>(\d+)/ ) {
                if ( $1 > 0 ) { $key_count{$key} = $1; }
                $co_count{$id} += $2;
                if ( $3 > 0 ) { $key_count{$id} = $3; }
        }
}
#標準入力を読み終えた段階で、まだ出力していないkeyに対し、集約を行い、その結果を出力する。
if ($key_current ne "" && ( keys (%co_count) > 0 ) ) {
        foreach $id ( sort keys %co_count ) {
                $co = $co_count{$id}/2;
                $corr = $co/($key_count{$key_current}*$key_count{$id});
                print ($key_current . "\t". $id . "\t" . $key_count{$key_current} . "\t" .
 $co . "\t" . $key_count{$id} . "\t" . $corr . "\n");
        }
}

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.plgihyo
Reducer:reducer_for_gihyo_1.pl
第二段Mapper:mapper_for_gihyo_2.plgihyo2
Reducer:reducer_for_gihyo_2.pl
第三段Mapper:mapper_for_gihyo_3.plgihyo3
Reducer:reducer_for_gihyo_3.pl

第一段階の入力データ、Amazonのレビューデータは、この例ではディレクトリamazonにあります。

リスト3 Hadoop Streamingによる計算スクリプト
hadoop dfs -rmr gihyo/;
hadoop jar /opt/hadoop/contrib/streaming/hadoop-*-streaming.jar - D mapred.task.timeo
ut=300000 -input amazon -output gihyo/ -mapper './mapper_for_gihyo_1.pl' -reducer
 './reducer_for_gihyo_1.pl'  -file './mapper_for_gihyo_1.pl' -file './reducer_for_gihy
o_1.pl' -jobconf mapred.reduce.tasks=12;
hadoop dfs -rmr gihyo2/;
hadoop jar /opt/hadoop/contrib/streaming/hadoop-*-streaming.jar - D mapred.task.timeo
ut=300000 -input gihyo/ -output gihyo2/ -mapper './mapper_for_gihyo_2.pl'
 -reducer './reducer_for_gihyo_2.pl' -file './mapper_for_gihyo_2.pl' -file './reducer_for_gihyo_2.pl' ?
jobconf mapred.reduce.tasks=12;
hadoop dfs -rmr gihyo3/;
hadoop jar /opt/hadoop/contrib/streaming/hadoop-*-streaming.jar - D mapred.task.timeo
ut=300000 -input gihyo2/ -output gihyo3/ -mapper './mapper_for_gihyo_3.pl'
 -reducer './reducer_for_gihyo_3.pl' -file './mapper_for_gihyo_3.pl' -file './reducer_for_gihyo_3.pl' ?
jobconf mapred.reduce.tasks=12;

間単にスクリプトの内容を説明します。

  • 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 「ザスーラ」に対するアイテム相関をコサイン関数で表すと

これらの値に、基準となるアイテム(ザスーラ)の出現頻度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それぞれの出現確率。

見ておわかりのとおり、これらの関数および指標は共通してnanbのみで構成されています。したがって、コサイン関数を求めるのに使った関数、第三段目のReducerを変更するだけで、これらの関数や指標を計算できます。またReducerの中で同時に複数の関数および指標を計算することもできます。

次回はアイテムベースのレコメンドをコンテンツベースでの実装方法を紹介します。

おすすめ記事

記事・ニュース一覧