Bayesian Setsを試してみた
この前YAPC Asia 2009に参加してきたのですが、そこで「はてなブックマークのシステムについて」の発表の中で、「はてブの関連エントリはBayesian Setsを使って計算されている」という話を聞いてBayesian Setsに俄然興味が湧いてきました。Bayesian Setsは以前論文だけ少し読んで、あまりよく分からないまま放置していたのですが、せっかくなのでPerlで作って試してみました。
Bayesian Setsについて詳しくは、以下のリンク先の資料をご参照下さい。
実際に作成したコードは以下の通りです。上記のMatlabのコードを参考にさせていただいています。
#!/usr/bin/perl # # Bayesian Sets # # Usage: # % bayesian_sets.pl input.tsv query1 query2 .. # # Reference # - Paper: http://www.gatsby.ucl.ac.uk/~heller/bsets.pdf # - Matlab code: http://chasen.org/~daiti-m/dist/bsets/ # use strict; use warnings; use constant { MAX_OUTPUT => 20, }; sub read_vectors { my $fh = shift; my %vectors; while (my $line = <$fh>) { chomp $line; my @arr = split /\t/, $line; my $doc_id = shift @arr; my %vector = @arr; map { $vector{$_} = 1 } keys %vector; $vectors{$doc_id} = \%vector; } return \%vectors; } sub get_parameters { my ($vectors, $c) = @_; my $average_vector = _average_vector($vectors); my (%alpha, %beta); while (my ($key, $val) = each %{ $average_vector }) { $alpha{$key} = $c * $val; $beta{$key} = $c * (1 - $val); } return (\%alpha, \%beta); } sub calc_similarities { my ($vectors, $queries, $alpha, $beta) = @_; my %query_vector; my $num_query; foreach my $query (@{ $queries }) { if (!exists $vectors->{$query}) { warn "[WARN] '$query' doesn't exist in input documents. Skip it\n"; next; } while (my ($key, $val) = each %{ $vectors->{$query} }) { $query_vector{$key} += $val; } $num_query++; } return if !%query_vector; my $length_qvec = scalar(keys %query_vector); my %weight_vector; foreach my $key (keys %{ $alpha }) { my $val = $query_vector{$key} || 0; $weight_vector{$key} = log(1 + $val / $alpha->{$key}) - log(1 + ($num_query - $val) / $beta->{$key}); } my %score; while (my ($doc_id, $vector) = each %{ $vectors }) { $score{$doc_id} = _inner_product(\%weight_vector, $vector); } return \%score; } sub _average_vector { my $vectors = shift; my %average_vector; my $num_vector = 0; while (my ($doc_id, $vector) = each %{ $vectors }) { while (my ($key, $val) = each %{ $vector }) { $average_vector{$key} += $val; } $num_vector++; } map { $average_vector{$_} /= $num_vector } keys %average_vector; return \%average_vector; } sub _inner_product { my ($v1, $v2) = @_; return 0 if !$v1 || !$v2; my @keys = scalar(keys %{ $v1 }) < scalar(keys %{ $v2 }) ? keys %{ $v1 } : keys %{ $v2 }; my $prod = 0; foreach my $key (@keys) { $prod += $v1->{$key} * $v2->{$key} if $v1->{$key} && $v2->{$key}; } return $prod; } sub main { my $path = shift @ARGV; my @queries = @ARGV; if (!$path || !@queries) { warn "Usage $0 file query1 query2 ..\n"; exit 1; } open my $fh, $path or die "cannot open file: $path"; my $vectors = read_vectors($fh); return if !$vectors; my ($alpha, $beta) = get_parameters($vectors, 2); # c=2 my $score = calc_similarities($vectors, \@queries, $alpha, $beta); my $count = 0; foreach my $doc_id (sort { $score->{$b} <=> $score->{$a} } keys %{ $score }) { last if ++$count > MAX_OUTPUT; printf "%s\t%.3f\n", $doc_id, $score->{$doc_id}; } } main();
入力データには以下のようなタブ区切りのテキストファイルを用意します。データ例は以前の記事で作成した、Wikipediaの各キーワードをTFIDFで重み付けしたデータです。実際にはvalue部分はいらないのですが、以前の名残りでそのままのフォーマットにしています。
# document_id \t key1 \t val1 \t key2 \t val2 \t ... 龍淵郡 郡 2365 長淵 1857 半島 1555 淵 1460 龍 1313 朝鮮 1137 （/ 1126 九 987 串 971 長山 788 リョンヨン 777 モングンポ 777 クミポ 777 朝鮮民主主義人民共和国 777 美浦 733 派 720 教会 714 救面 708 ざんかん 708 チャンサンゴッ 708 金浦 605 史上 595 松川 555 プロテスタント 529 分割 527 地 526 岬 513 里 506 建設 505 苔 500 年 496 南岸 490 当時 487 珪砂 483 黄海 481 再編 468 夢 460 ら 460 北朝鮮 444 宣教 404 1884 397 相 397 ソレ 382 甕 379 白島 360 徐 359 灘 344 教会堂 341 景勝 336 崙 334 神さまこんにちは ピョンテ 2332 チュンジャ 2332 慶州 1381 映画 1270 人 929 旅 827 チョン・ムソン 777 キム・ボヨン 777 ハン・ミヌ 777 国際 756 ペ・チャンホ 708 脳性 689 ソンギ 639 ミヌ 639 彼 624 祭 615 詩人 614 3 574 妊婦 548 麻痺 539 回 481 念願 468 英 458 39 430 Hello 425 ロード 419 アン 414 家 413 モスクワ 409 電車 399 God 395 16 377 乗車 366 遠足 350 神さま 342 無賃 339 !） 332 さ 331 大人 329 小学生 309 ムービー 298 ベルリン 296 とき 295 実家 289 一 288 原題 286 途方 272 神様 264 韓国 263 公開 259 藤原雅長 年 5208 雅 1285 藤原 1271 近臣 1263 位 1138 従 1118 任 1110 長 957 元年 903 3 861 7 813 院 798 近衛 782 五位上民部権大輔 777 嘉 770 視 764 4 760 下 747 日 747 左 713 隆信 708 月 689 わら 638 叙 629 保 600 8 599 能 595 参議 572 守 556 蔵人 521 久安 515 五 507 少将 506 26 503 顕能 500 在任 460 2 451 ふじ 448 中将 448 19 445 処分 431 久 425 死去 424 任命 422 兼 416 教 406 後期 403 長男 401 この間 377 辞任 377
実際に動かしてみます。入力ドキュメント集合のファイルと、(複数の)クエリを指定します。クエリは入力ドキュメント集合中に含まれている document_id しか使用できません。
% ./bayesian_sets.pl input.tsv トヨタ自動車 トヨタ自動車 140.748 豊田英二 47.205 トヨタ・トヨエース 45.501 5チャンネル 42.303 ポルシェ 40.428 トヨタ・マークX 37.372 日産・マーチ 36.659 フォード・モーター 36.333 三菱自動車工業 33.872 マツダ 33.625 ホンダ・インサイト 32.407 トヨタ・タンドラ 32.004 トヨタ・クルーガー 29.959 ジオ (自動車) 29.293 シボレー・キャバリエ 29.142 トヨタF1 28.830 三菱・ディオン 27.994 いすゞ・エルフ 27.712 ヒュンダイ・ソナタ 27.452 富士重工業 27.111 % ./bayesian_sets.pl input.tsv 原宿警察署 原宿警察署 203.638 滝野川警察署 80.618 牛込警察署 59.605 万世橋警察署 52.241 三田警察署 (東京都) 47.331 城東警察署 (東京都) 43.736 王子警察署 42.404 丸の内警察署 37.594 中野警察署 (東京都) 36.628 広島東警察署 32.846 田無警察署 31.444 豊田幹部交番 31.430 小金井警察署 31.352 尾鷲警察署 30.760 日下部警察署 30.656 山梨県警察 30.290 戸塚町 30.032 阿東幹部交番 29.785 神宮前 (渋谷区) 28.061 倶知安警察署 27.630
ちゃんと関連しているものが取得できていますね。本当は「apple banana」と「apple iPod」のように複数の意味を持つ言葉で、複数のクエリを入れた場合にそのクラスタ内の単語が出てくるのを確かめられるとよかったのですが。
今回使用した入力データのサイズは10万個のドキュメント(wikipediaのキーワード)ですが、実行には25秒ほどかかっています。今回のコードは入力データからのインデックスの作成と、クエリからの類似アイテムの検索の両方を同時に処理させているため動作が遅いですが、インデックスは初めに作成して保存しておけるようにしておけば、そこそこのスピードで検索できるようになると思います。
まだBayesian Setsの肝をあまり理解できていないのですが、
- 与えられたクエリが含まれていると思われるクラスタをオンデマンドで求め、そのクラスタに含まれている他のアイテムを返す
- クエリから求めた重みベクトルと入力ドキュメント集合から構成した行列の積(重みベクトルと全文書の内積)を求めるだけで計算できる
あたりがうれしいところなんでしょうか？一般的な転置インデックスを使用した類似コンテンツを求める方法でも同様のことはできそうな気がするのですが、「オンデマンドにクラスタを求める」というところでゴミが消されるんですかね。ちなみに単純に全文書とのcosine距離で類似したものを取ってきた場合だと、以下のような結果になります。大抵は良好な結果が得られますが、たまにクエリによってはゴミだらけになっちゃってますね。
% ./cos.pl input.tsv トヨタ自動車 トヨタ自動車 1.000 豊田英二 0.625 松井石根 0.610 島崎藤村 0.609 鉄道の歴史 (日本) 0.598 土佐電気鉄道 0.592 日産・マーチ 0.591 新関八洲太郎 0.588 近衛道嗣 0.588 岡村貢 0.587 高田保馬 0.587 8月7日 0.586 仙台東照宮 0.584 3月25日 0.584 飛鳥時代 0.583 三菱自動車工業 0.582 蒲郡競艇場 0.580 富士重工業 0.580 大林組 0.579 ホンダ・インサイト 0.576 % ./cos.pl input.tsv 原宿警察署 原宿警察署 1.000 阿東幹部交番 0.776 周南警察署 0.775 竹原警察署 0.773 高梁警察署 0.771 日下部警察署 0.769 大牟田警察署 0.764 三原警察署 0.758 音戸警察署 0.756 横須賀警察署 0.754 城東警察署 (東京都) 0.753 山口南警察署 0.752 松浦警察署 0.752 王子警察署 0.751 滝野川警察署 0.750 東近江警察署 0.750 つがる警察署 0.748 万世橋警察署 0.743 あわら警察署 0.743 丸亀警察署 0.743
あと、この前のpLSIの記事では結局そのまま放置になってるのですが、せっかくなので今度こそパッケージングしてAlgorithm::BayesianSetsを作ろうと思います。あまり使い道はなさそうですが、ざっくりどんなものか知るのには多少役に立ちそうですし、何より僕自身がCPAN Authorになってみたいので…^^;
追記：weight_vectorを求めるところが一部間違っていたため、コードと実行結果、実行時間を修正しました。ただ実行結果はポイント以外はほとんど違いはないと思います。
