Perl で MapReduce - Mahout Frequent Pattern Mining Data -

最近、Perl も書き始めてみたので、Hadoop 上で分散実行できる Perl での MapReduce 実装を紹介する。大規模データマイニング・機械学習のライブラリ Apache Mahout の Parallel Frequent Pattern Mining の入力データを生成する Perl MapReduce 実装の紹介。

Frequent Pattern Mining 入門

Frequent Pattern Mining (Association Analysis )は、隠されたルールパターンを抽出するアルゴリズム。有名な例としては、1992年のウォルマートのクリスマス商戦で「おむつを買った人は半ダースのビールを買う可能性が最も高い」という頻出ルールを抽出し、商品陳列に活かした売上向上した事例。

入門資料：

データ

MovieLens Data Sets 100k Ratings のデータを例に紹介する。
このデータは 943 userが 1682 movieに対して行った 100,000 の評価データ。
以下、HDFSの movielens/ 下に配置し実行。

データ形式

 userid | itemid | rating | timestamp(unixtime)

データ例： ua.test

1	20	4	887431883
1	33	4	878542699
1	61	4	878542420
1	117	3	874965739
1	155	2	878542201
1	160	4	875072547
1	171	5	889751711
1	189	3	888732928
1	202	5	875072442
1	265	4	878542441
2	13	4	888551922
2	50	5	888552084
2	251	5	888552084
...

Perl MapReduce

Perl での MapperとReducerの実装。各userごとに 5段階評価の中で4以上の好評価のmovieのid を ","(カンマ)区切りでつなげ出力する。
Mapperで (key, value) を (userid, 4以上の評価movieid)で出力し、Reducerで useridごとに、movieidsをカンマ区切りでつなげる。

#!/usr/bin/perl
use strict;

my $SEP = "\t";
my $NSEP = ",";

main();

sub main{
        if($ARGV[0] eq 'map'){
                mapper();
        }elsif($ARGV[0] eq 'reduce'){
                reducer();
        }
}

sub mapper{
        while(my $line = <STDIN>){
                chomp($line);
                my @values = split(/$SEP/, $line);
		if(@values != 0){ 
         	        my ($userid, $itemid, $rating, $timestamp) = @values;		
			if($rating >= 4){
       				print join($SEP, @values), "\n";
			}
		}
        }
}

sub reducer{
	my %eval;
        while(my $line = <STDIN>){
                chomp($line);
                my ($userid, $itemid) = split(/$SEP/, $line);
		if(!defined($eval{$userid})){
			$eval{$userid} .= $itemid;
		}else{
			$eval{$userid} .= $NSEP.$itemid;
		}
        }
	while(my ($key, $itemids) = each(%eval)){
                print join($NSEP, $itemids), "\n";
	}
}

実行

Hadoop Streaming を用いた Perl MapReduce 実行

$HADOOP_HOME/bin/hadoop jar $HADOOP_HOME/contrib/streaming/hadoop-x.xx.x-streaming.jar  \
-files mapreduce.pl \
-mapper "mapreduce.pl map" \
-reducer "mapreduce.pl reduce" \ 
-numReduceTasks 50 \ 
-input movielens/ua.test \
-output movielens/out

出力

出力：movielens/out/part-00000, part-00001,...

以下のMahout の Paralel Frequent Patten Mining の入力データ形式で出力が行われる。
各userごとに 5段階評価の中で4以上の好評価のmovieのid が ","(カンマ)区切りでつなげられたデータ。

movielens/out/part-00000

227,229,243,288,294,300,380,449,450,748
246,249,250,257,276,1012
2,4,8,11,14,22,56,58,64,68,69,70,76,78,81,91,101,117,121,124,125,127,135,139,141,147,154,156,157,164,168,169,171,176,180,181,186,188,196,198,203,204,206,207,209,210,214,223,226,227,228,230,234,238,246,249,250,262,265,268,270,272,273,276,282,288,290,294,301,302,307,315,317,318,324,333,340,347,357,403,404,408,417,418,419,420,423,427,429,432,436,448,463,471,474,496,547,550,559,566,568,569,578,581,588,628,640,649,652,684,693,732,737,742,746,747,751,770,806,843,845,853,854,922,969,1129,1135,1172,1218,1220,1240
6,9,11,12,14,17,22,25,30,31,33,42,79,83,86,96,98,100,131,132,143,155,166,177,178,179,180,185,187,190,191,197,199,203,213,237,241,269,272,287,301,307,311,312,313,318,347,357,367,382,421,423,425,435,471,478,483,486,489,494,499,501,506,507,512,521,526,529,602,603,604,611,613,614,618,631,648,652,657,659,662,690,692,705,707,713,739,813,855,900,903,923,945,958,964,966,971,995,1020,1048,1086,1101,1125,1193,1194,1197,1198,1200
258,288,302,313,315,333,895,896,1127
...