第8回　コンテンツベースのレコメンドシステムのHadoop実装［後編］

自分で確認してみたい場合

前回紹介したMapReduceの第一段階のReducerの出力結果のデータ構造で

<key value>

は

<単語id　単語idを含むアイテムidのリスト>

でした。

コンテンツベースのレコメンドは、アイテム間の類似性をそれぞれの内容（アイテムのメタデータや概要など）の類似性に基づいて計算するために単語を使います。

一般に、ミススペルされた単語の出現頻度は他の単語に比べ非常に低く、それらを含むレビューおよび該当するアイテムは少ないと予想できます。また、冠詞などの単語はほとんど全てのレビューに出現するため、出現頻度は他の単語に比べて非常に高く、それらを含むレビューおよび該当するアイテムの数は非常に大きくなります。

したがって、単語ごとのレビューやアイテムのリストの長さを見て、以降の処理で利用する単語を選択することができます。

TF/IDF

TFはTerm Frequecny（単語の出現頻度⁠）⁠、IDFはInverse Document Frequency（逆文書頻度）で、これらは文書内の単語の重み付けの方法として、情報検索の分野等でよく使われます。これらの重み付けの定義は次の通りです。

TF/IDFを使うと、同一単語に対して、「⁠文書内での出現頻度」と「逆文書頻度」の二通りから重みを付けられます。

TFは局所的な重み付けで、文書内で出現頻度が高い単語に大きな値を与えます。一方、IDFは大局的な重み付けで、出現する文書が少ない単語に大きな値を与えます。同じ単語でも、TFの場合は文書ごとに値が異なるのに対し、IDFは文書集合全体で一定であることに注意してください。

各単語の重みはこれらTFとIDFの積で計算します。

以上の定義より、多くの文書に出現し、かつ各文書での出現頻度の低い単語の値は小さくなり、逆に少数の文書のみに出現し、かつその文書内での出現頻度の高い単語の値は大きくなります。

ここで簡単な例で重みの付け方を説明します。

① 文書a、bから文書内に含まれた単語を要素とする文書ベクトルを作成する。
② 文書ベクトルを表形式で表現する。
セル内の数値は各文書で列に該当する単語が出現した回数になる。
③ 文書ベクトルのTF値を表形式のデータから計算する。
TF値なので表形式のデータをそのまま使う。
④ 文書ベクトルのIDF値を表形式のデータから計算する。
ここでは全文書の数を10としている。
IDFの値は各文書での出現頻度に関係なく、同じ単語であれば全文書で共通であることに注意してください。
⑤ 文書ベクトルのTF/IDF値をTF及びIDFのデータから計算する。
各文書かつ各単語ごとに③と④で計算した値を使って積を求めます。

MapReduceを使ってTF/IDFを計算しよう

図2に示した流れに従い、アイテムごとのTF/IDFを計算します。ここでは文書（レビュー）をアイテムごとに集約しているので、次のような変換をします。

単語→そのまま
文書→アイテムごとの文書群

同一アイテムへの文書が複数ある場合、それをまとめて1つの文書にしています。

ここで知りたいのは「文書の近さ」で無く、「⁠アイテムの近さ」なので、ここでは各文書で出現する単語の頻度を全て1とし、TF/IDFを次のように計算します。

もちろん、各文書で出現する単語の頻度をそのまま使う方法も可能です。先ほどの図2の結果を使いTF/IDFを計算すると、次のようになります。

これらの重みを計算するために、第7回で紹介したMapReduceを使い、MapReduceの変更箇所を考えます。

第一段階

この段階で単語ごとのTFおよびIDFを計算します。

各アイテムで単語が出現する頻度を「各アイテムで単語が出現するレビューの頻度」としているので、Mapperでは前回同様に、レビューごとに <単語アイテムID> を出力します。

このペアは同一文書から複数回出現しないようにしています。そこで、Reducerを次のように変更します。

リスト1　第一段階でのReducer

#!/usr/bin/perl
use strict;

my ($key,$value);
my $key_current = "";
my $cnt = 0;
my $idf = 0;
my %tf = ();
my $v = 0;

while (<STDIN>) {
        chomp $_;
      #単語を$key 、アイテムを$valueとする
        ($key,$value) = split(/\t/,$_);
        if ( $key ne $key_current )  {
            #単語ごとのユニークアイテム数を取得
                $idf = keys %tf;
                #ここではユニークアイテム数の値が5以上の単語について処理を行っています
                if ( $idf > 5 ) {
                        print ($key_current . "\t");
                        foreach ( keys %tf ) {
                  #単語ごとのTFとIDFの積を計算
                                $v = $tf{$_}*log(100000/$idf)/log(2);
                                print ($_ . "-" . $v . ":");
                        }
                        print ("\n");
                }
                $key_current = $key;
                $idf = 0;
                %tf = ();
        }
      #アイテムごとの出現レビュー数をカウント
        $tf{$value} += 1;
}
@list = keys %tf;
$idf = keys %tf;
if ( $#list > -1 ) {
        print ($key . "\t");
        foreach ( keys %tf ) {
                $v = $tf{$_}*log(100000/$idf);
                print ($_ . "-" . $v . ":");
        }
        print ("\n");
}

各単語で出現したアイテムIDの数は文書の数と等しくなり、これがTFに相当します。また、各単語に集約されたアイテムIDの異なる数が、各単語を含む文書の数になります。ここではあらかじめ全アイテムの数が100000とわかっているものとして、IDFを計算します。

第二段階

ここでは第一段階の出力を使って、アイテムのペア及びTFとIDFの積の値を集約していきます。

Mapperの主な処理は、ターゲットアイテム（計算の基準となるアイテム、全てのアイテムがターゲットアイテムになります）とそれとペアとなるアイテムのペアを単語ごとに、TFとIDFの積と合わせて出力しています。

リスト2　第二段階でのMapper

#!/usr/bin/perl
use strict;

my $i = 0;
my $h_term = 0;
my $h_v = 0;
my $item_id0 = 0;
my $item_id1 = 0;
my $length = 0;
my @list = ();
my @string = ();

while (<STDIN>) {
        chomp $_;
        my @string = split ( /\t/, $_);
      #アイテムリストを取得
        my @list = split (/:/,$string[1]);
        my $length = @list;
        if ( $length > 1 ) {
             #アイテムリストの先頭からアイテムの組み合わせとそのTFとIDFの積をペアとして出力
                for ( $i = 0; $i < $length; $i++ ) {
                        $h_term = shift @list;
                        $h_term =~/(.+)\-(.+)/;
                        $item_id0 = $1;
                        $h_v = $2;
                    #ターゲットアイテムについてアイテムIDとそのTFとIDFの積を出力
                        print ( $item_id0 . "\t" . $h_v . ">");
                    #ターゲットアイテムとペアを組むアイテムIDとそのTFとIDFの積を出力
                        foreach ( @list ) {
                                print ( $_ . ":" );
                        }
                        print ("\n" );
                        push @list,$h_term;
                }
        }
       #ペアが存在しないアイテムIDを出力
        else {
                $list[0] =~/(.+)\-(.+)/;
                $item_id0 = $1;
                $h_v = $2;
                print ( $item_id0 . "\t" . $h_v . ">" . $item_id0 . "\n" );
        }
}

リスト3　第二段階でのReducer

#!/usr/bin/perl
use strict;

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

while (<STDIN>) {
        chomp $_;
        ($key,$value) = split(/\t/,$_);

        if ( $key ne $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_current = $key;
                $count = 0;
                %co_count = %flag = @list = ();
        }
        if ( $value =~ /:/ ) {
                @plist = split(/>/,$value);
                @list = split (/:/,$plist[1]);
                foreach ( @list ) {
                        $_ =~/(.+)\-(.+)/;
                        $id = $1;
                        $co_count{$id} += $2;
                }
                $count += $plist[0];
                $flag{$key} = 1;
        }
        else {
                $value =~ /(.+)>.+/;
                $count += $1;
         }
}
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");
        }
}

第三段階

ここでの処理は第5回で利用したReducerのうち

$corr = $co/($key_count{$key_current}*$key_count{$id});

の箇所を

$corr = $co/sqrt($key_count{$key_current}*$key_count{$id});

とします。

また、今回はvalueが小数になるので次のような変更も必要です。

if ( $value =~ /(\d+)>(\d+)>(\d+)/ ) {

↓

if ( $value =~ /(.+)>(.+)>(.+)/ ) {

Mapperはそのまま使えます。

TF/IDFの正確な値でなく、TF/IDFに基づく相対的な大小関係を求めたいのであれば、第5回で紹介したように第二段階で終了することができます。単語の重み付けにはTF/IDF以外にも多くの方法がありますし、単語の品詞情報や共起情報あるいはN-gramの利用もあります。

次回は最終回で、レコメンド全般について振り返ります。