perl de 集合知プログラミング（６）

deliciousのリンクを推薦するシステムを作る

今回はdeliciousのデータを使って、似ているユーザを見つけ出し、まだブックマークしていないリンクを推薦する、ということをやってみます。類似ユーザを見つけたり、リンクを推薦する部分はこれまでに作ったものが使えるので、deliciousからfeedを取得して2.2節のサンプルと同じフォーマットのデータセットを作成するところを新規に作りました。

データセットの作成

2.2節と同じようにユーザ名と、アイテム（今回の場合はリンク）に対するそのユーザの評価スコアを持つデータセットを作成します。ユーザ名は特定のタグのPopular Bookmarksをブックマークしたユーザ一とし、ユーザすべてがブックマークしたURLについて、各ユーザがブックマークしていればスコアを1、ブックマークしていなければ0とします。

delicious/help/feedsを見ると、Popular Bookmarksは

Popular bookmarks by tag:
http://feeds.delicious.com/v2/{format}/popular/{tag}

で取れるので、得られたfeedからURLを取り出して、さらに

Recent bookmarks for a URL:
http://feeds.delicious.com/v2/{format}/url/{url md5}

でユーザ名を取得します。この二つの処理を実行して、ユーザ名をキーにしたハッシュを作るコードは以下のようになりました。

# Popular bookmarkを取得する関数
sub get_popular {
    my ($tag, $count) = @_;

    # Popular bookmarksをJSON形式で取得 from Delicious
    my $tagd = uri_escape(encode('utf-8', $tag)); # URLエンコード
    my $base = "http://feeds.delicious.com/v2/json/popular";
    my $url = sprintf("%s/%s?count=%d", $base, $tagd, $count);

    my $ua = LWP::UserAgent->new;
    my $req = HTTP::Request->new('GET', $url);
    my $res = $ua->request($req); # ハッシュを要素に持つ配列が得られる

    unless( $res->is_success ) {
	die "Request failed : $url";
    }
    else {
	my $r = decode_json(decode_utf8($res->content)); 
	return $r; # 配列のリファレンス
    }
}

# Recent bookmark for a URLを取得する関数
sub get_urlposts {
    my $urls = shift;

    # Recent Bookmars for a URL
    my $base = "http://feeds.delicious.com/v2/json/url";
    my $count = @{$urls};
    my $url;

    my $ua = LWP::UserAgent->new;
    my $req;
    my $res;

    my %rb = ();
    for( my $i=0; $i<$count; $i++) {
	# Request
	$url = sprintf("%s/%s", $base, md5_hex($urls->[$i]->{'u'}));
	$req = HTTP::Request->new('GET', $url);
	$res = $ua->request($req); # ハッシュを要素に持つ配列が得られる

	unless( $res->is_success ) {
	    die "Request failed : $url";
	}
	else {
	    my $r = decode_json(decode_utf8($res->content));
	    $rb{$urls->[$i]->{'u'}} = $r;
	}    
    }

    return \%rb;
}

# Popular bookmarkをブックマークしたユーザリスト（user dict）を作成する関数
sub initializeUserDict {
    my ($tag, $count) = @_;

    # Popular Bookmarksを取得
    my $pb = get_popular($tag, $count);

    # Recent bookmark for a URLを取得
    my $rb = get_urlposts(\%{$pb});

    # ユーザをキーにしたハッシュ(user dict)を作成
    my %ud = ();
    foreach my $key (keys %{$rb}) {
	my $loop = @{$rb->{$key}};
	for(my $i=0; $i<$loop; $i++) {
	    $ud{$rb->{$key}->[$i]->{'a'}} = ();
	}
    }

    return \%ud;
}

ユーザ毎のブックマークは、

Bookmarks for a specific user:
http://feeds.delicious.com/v2/{format}/{username}

で取ってきて、自分がブックマークしたリンクとその他のユーザがブックマークしたリンクのそれぞれに対してスコア付けして最終的なデータセットを作ります（下記のfillItems）。

# user dictに評価値を埋める関数
sub fillItems {
    my $ud = shift;
    
    # bookmark for specific user
    my $base = "http://feeds.delicious.com/v2/json";
    my $url;

    my $ua = LWP::UserAgent->new;
    my $req;
    my $res;

    my $r;
    my $count;
    my %all_items = ();
    foreach my $user (keys %{ $ud }) {
	$url = sprintf("%s/%s", $base, $user);
	$req = HTTP::Request->new('GET', $url);
	$res = $ua->request($req);

	unless( $res->is_success ) {
	    warn "Request Failed : " . $url . "\n";
	}
	else {
	    $r = decode_json(decode_utf8($res->content));
	}

	# userがブックマークしているurlは1を埋める
	$count = @{$r};
	for(my $i=0; $i<$count; $i++) {
	    $ud->{$user}->{$r->[$i]->{'u'}} = 1.0;
	    $all_items{$r->[$i]->{'u'}} = 1;
	}
    }

    # userがブックマークしていないurlは0を埋める
    foreach my $user (keys %{$ud}) {
	foreach my $key (keys %all_items) {
	    # keyが存在しなければ新たに追加
	    if( not exists $ud->{$user}->{$key} ) {
		$ud->{$user}->{$key} = 0.0;
	    }
	}
    }
}

で、実際に出来たデータセットを表示するとこんな感じになります。

データセット（一部）

username : 
	http://brettterpstra.com/single-keystroke-instapaper-in-google-reader/:0
	https://wincent.com/wiki/MacVim_fullscreen_mode:0
	http://kirik.tea-nifty.com/diary/2010/08/post-74bf.html:0
	http://www.twfan.com/:1
	http://thinkit.co.jp/article/117/3/:1
・・・

似ているユーザの探索とまだブックマークしていないリンクの推薦

上で作ったデータセットに対して、topMatchesとgetRecommendationsを適用するだけです。MyRecommendationsという名前でpackageにして、useして使います。Popular Bookmarksをブックマークしたユーザの中からランダムにひとり選んで、そのユーザと似ているユーザ、リンクの推薦を実行します。

my @users = keys(%{$udict});
my $unum = @users;
my $num = int(rand($unum));
my $n = 5;

# Similar User
print "Similar user for $users[$num] :\n";
my @match_users = topMatches($udict, $users[$num], $n, \&sim_pearson);
for (my $i=0; $i<$n; $i++) {
    foreach my $key (keys %{ $match_users[$i] }) {
	print "\t" . "$key\t : $match_users[$i]{$key}\n";
    }
}
# リンクを推薦
print "Recommendations for $users[$num] :\n";
my @recommendations = getRecommendations($udict, $users[$num], \&sim_pearson);
for(my $i=0; $i<$n; $i++) {
    foreach my $key (keys %{ $recommendations[$i] }) {
 	print "\t" . uri_unescape($key) . "\t : $recommendations[$i]{$key}\n";
    }
}

実行結果（ユーザ名は一応伏せておきます）

Similar user for username :
	user1	 : 0.248722131593262
	user2	 : 0.248722131593261
	user3	 : 0.112126155519305
	user4	 : 0.112126155519304
	user5	 : 0.112126155519304
Recommendations for username :
	http://www.slideshare.net/takashi_ohmoto/the-future-ofsocialmedia	 : 0.201744213016654
	http://labs.unoh.net/2010/08/cassandra.html	 : 0.180869323189683
	http://d.hatena.ne.jp/vwxyz/20100812/1281593928	 : 0.162174699633529
	http://togetter.com/li/41702	 : 0.153917520990862
	http://d.hatena.ne.jp/ZIGOROu/20100809/1281346447	 : 0.133042631163891

その他

いつものようにgist: 489178 - GitHubにコードを置いております。deliciousのヘルプは情報が少ないので、すごく苦労しました（せめて得られるデータのサンプルを載せておいてくれればよかったのに）。。。

stMind

about Tech, Computer vision and Machine learning

perl de 集合知プログラミング（６）

deliciousのリンクを推薦するシステムを作る

データセットの作成

似ているユーザの探索とまだブックマークしていないリンクの推薦

その他