第4回　レコメンドシステム－協調フィルタリングのHadoopへの実装［中編］

皆様、遅くなりましたが明けましておめでとうございます。本年も宜しくお願い申し上げます。

今回は前回に引き続き、ユーザシーケンスからコサイン関数の計算に必要な値（図1のa1:b1、a1、およびb1）を取り出す方法を紹介します。

おさらい

Hadoopはデータをクラスタ内のローカルディスクに分散し、そのデータがあるノード上で処理を実行するというデータローカリティを実現しているため、コサイン関数をMapReduceのフレームワークに変換して処理することを紹介しました。

その設計方法として、処理結果の形式から逆に考える方法を紹介しました。

ユーザシーケンスからアクセスユーザ数のカウントまで

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

①では、各ユーザシーケンスからシーケンス内に含まれるアイテムをkey、同一ユーザシーケンス内に含まれていた他アイテムをvalueとするペアのリストを作成します。
②では、keyであるアイテムでソートしてReducerに渡しています。
③では、keyであるアイテムをアクセスしたユーザ数、およびそのアイテムと同一ユーザシーケンス内に出現したアイテムの両方をアクセスしたユーザ数を算出しています。

HDFSには、同一ユーザにアクセスされたアイテムの組み合わせをkey、各アイテムをアクセスしたユーザ数、および両アイテムをアクセスしたユーザ数をvalueとするペアが入ります。

この例ではザスーラ、ジュマンジ、両方をアクセスしたユーザ数はそれぞれ3人、2人、2人なので、keyをザスーラとジュマンジ（順序に注意してください⁠）⁠、valueをザスーラをアクセスしたユーザ数、ザスーラとジュマンジをアクセスしたユーザ数、ジュマンジをアクセスしたユーザ数の並びで構成しています（色の違いを参考にしてください⁠）⁠。さらにこれらの順序を入れ替えたkeyとvalueのペアも出力します。

バトルランナーにアクセスしたユーザは他の映画をアクセスしていないので、コサイン関数を計算できないため、以降の処理で使わないため出力しません。

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

リスト1　ユーザシーケンスからアイテムのリストを作成

#!/usr/bin/perl

use strict;

my $i = 0;
my $item_id0 = 0;
my $length = 0;
my %count = ();
my @list = ();
my @string = ();

while (<STDIN>) {
    chomp $_;
    chop $_;
    #ユーザシーケンスをユーザIDとアイテムIDのリストに分割する。
    my @string = split ( /\t/, $_);
    #アイテムIDのリストから、アイテムのリストを取り出す。
    my @list = split (/:/,$string[1]);
    #アイテムのリストから重複しているアイテムを取り除く。
    my %count = ();
    @list = grep {!$count{$_}++} @list;
    #アイテムの個数を取り出す。
    my $length = @list;
    if ( $length > 1 ) {                              
        for ( $i = 0; $i < $length; $i++ ) {          
            $item_id0 = shift @list;                  
            print ( $item_id0 . "\t");                
            foreach ( @list ) {                       
                    print ( $_ . ":" );               
            }                                         
            print ("\n" );                            
            push @list,$item_id0;                     
        }                                             
    }                                                  ――アイテムリストに複数のアイテムがある場合の処理
    else {                                            
        print ( $list[0] . "\t" . $list[0] . "\n" );  
    }                                                  ――アイテムリスト内のアイテムが1個の場合の処理
}

Mapperは図2内の①に相当します。主な処理はユーザシーケンスからのアイテムリストの作成です。アイテムリストをユーザシーケンスごとに作成し、アイテムリスト内のアイテムの個数により、処理を分岐します。

複数のアイテムが存在する場合は、各リスト内のアイテムの組み合わせを出力します。この場合は、アイテムリスト内の任意のアイテムをkey、それ以外のアイテムをリスト化したをvalueとしたペアを出力します。リストはアイテムを``:''でネストして生成します。

もちろん、アイテムリスト内の全てのアイテムのペアを取り出して、そのアイテムペアをkey、ユーザidをvalueとして出力する方法もありますが、アイテムをリスト化した場合に比較してkeyとvalueのペアを大量に生成することになり、ソート処理に時間がかかり、処理全体の効率が悪くなります。

リスト2　アイテムリストからユーザ数の算出

#!/usr/bin/perl

use strict;

my ($key,$value) = ();
my $key_current = "";
my $id = 0;
my $count = 0;
my %co_count = ();
my %flag = ();
my @list = ();

while (<STDIN>) {
    chomp $_;
    ＃入力したデータをkeyとvalueのペアに分割する。分割するデリミタはMap関数の出力形式に合わせる。
    ＃ここでは前出のＭａpperのkey及びvalueがタブ区切りで出力したので、デリミタをタブにする。  
    ($key,$value) = split(/\t/,$_);

    #key値が変わった＝以前のkeyに関するデータの読み込みが終了のサインなので、
    #以前のkeyである$key_currentに対する処理を開始する。
    if ( $key ne $key_current )  {
      # $key_currentがペアを作るアイテムについて出力する。             
        if ( defined $flag{$key_current} ) {
            foreach $id ( sort keys (%co_count) ) {
                print ($key_current . ":" . $id . "\t" . $count . ">" . $co_count{$id} . ">" . 0 . "\n");
                print ($id . ":" . $key_current . "\t" . 0 . ">" . $co_count{$id} . ">" . $count . "\n");
            }
        }
         #比較対象となるkeyを変更する。
        $key_current = $key;
        $count = 0;
        %co_count = %flag = @list = ();
    }
    if ( $value =~ /:/ ) {          
        chop $value;                
        @list = split(/:/,$value);  
        foreach $id ( @list ) {     
            $co_count{$id} += 1;    
        }                           
        $count += 1;                
        $flag{$key} = 1;            
    }                                ――Value内に複数のアイテムがある場合の処理
    else { $count += 1; }            ――Value内のアイテムが1個の場合の処理
}
#標準入力を読み終えた段階で、まだ出力していないkeyに対し、集約を行い、その結果を出力する。
if ( defined $flag{$key_current} ) {
    foreach $id ( sort keys (%co_count) ) {
        print ($key_current . ":" . $id . "\t" . $count . ">" . $co_count{$id} . ">" . 0 . "\n");
        print ($id . “:” . $key_current . “\t” . 0 . “>” . $co_count{$id} . “>” .  $count . "\n");
    }
}

Reduceは図2内の③に相当します。主な処理はMapperの出力をマージして、各アイテムをアクセスしたユーザ数、および両アイテムをアクセスしたユーザ数の算出です。「⁠同じkeyに関連付けられた全データ（keyが同じkeyとvalueのペア）は同じReducerに送られる」という特徴を生かし、Reducer側ではkeyのカウントをするだけで、keyとなっているアイテムをアクセスしたユーザ数を取得します。これはReducerの$countの変数に入ります。

出力は$key_currentとペアを作るアイテムidについて、$key_currentをアクセスしたユーザ数と、$key_currentおよびアイテムidの両方をアクセスしたユーザ数を出力します。この段階ではペアとなるアイテムidをアクセスしたユーザ数が分からないので、コサイン関数は計算できません（Reducerの数を1に設定し、全てのkeyとvalueのペアを読み込むまで出力しないように設計すれば可能ですが、データサイズが大きければメモリの限界を超えるでしょう⁠）⁠。次の処理で計算できるように、出力は$key_currentとペアを作るアイテムidを入れ替えた結果をも出力します。

次回は最後の第三段階の処理を紹介し、協調フィルタリング編のまとめとします。実はこの第二段階の処理で、協調フィルタリングに必要なアイテム間相関の値が得られていることも、そこで紹介します。