WikipediaのキーワードリンクでHITSアルゴリズムを試す
昨日の記事で作成した、Wikipediaのキーワードリンクのデータを使って、HITSアルゴリズムを試してみます。
HITSはグラフ理論では有名なアルゴリズムで、リンク関係を使用してネットワーク中の重要なノードを特定する手法です。HITSで求められるノードには、AuthorityとHubの2種類があります。Authorityはその名の通りネットワーク中で権威のあるノードで、情報量が豊富であるなどといった特徴を持ちます。Hubは権威のあるノードに多くつながっているノードで、Webではリンク集ページなどに相当します。
考え方はPageRankと似ており、Yahooの検索でもHITSが使用されているらしいです。HITS具体的なアルゴリズムについては、解説しているページが多く存在するので、そちらを参照してください。
では実際にWikipediaのデータを使って、AuthorityとHubを求めてみます。作成したコードは以下の通りです。
#!/usr/bin/perl # # HITS Algorithm # # Usage: # hits.pl -i linkdb -d outdir # => outdir/auth.hdb, outdir/hub.hdb # use strict; use warnings; use Getopt::Long; use TokyoCabinet; use constant { DBM_AUTHORITY => 'auth.hdb', DBM_HUB => 'hub.hdb', }; sub usage_exit { print <<'USAGE'; Usage: hits.pl -l linkdb -d outdir -l, --link linkdb link structure DBM -d, --directory outdir output directory USAGE exit 1; } sub _update_authority { my ($linkdb, $authdb, $hubdb) = @_; _fill_zero($authdb); $linkdb->iterinit(); while (my $id = $linkdb->iternext()) { my $hubval = $hubdb->get($id); next if !$hubval; my $val = $linkdb->get($id); next if !$val; my %link = unpack('(Nn)*', $val); foreach my $linkid (keys %link) { my $authval = $authdb->get($linkid) || 0; # 本当はadddoubleを使いたい $authdb->put($linkid, $authval + $hubval); } } } sub _update_hub { my ($linkdb, $authdb, $hubdb) = @_; $linkdb->iterinit(); while (my $id = $linkdb->iternext()) { my $val = $linkdb->get($id); next if !$val; my %link = unpack('(Nn)*', $val); my $sum = 0; foreach my $linkid (keys %link) { my $authval = $authdb->get($linkid); next if !$authval; $sum += $authval; } $hubdb->put($id, $sum); } } sub _initialize { my ($linkdb, $pointdb) = @_; my $rnum = $linkdb->rnum(); my $initval = 1 / sqrt($rnum); $linkdb->iterinit(); while (my $id = $linkdb->iternext()) { $pointdb->put($id, $initval); } } sub _fill_zero { my $pointdb = shift; $pointdb->iterinit(); while (my $id = $pointdb->iternext()) { $pointdb->put($id, 0); } } sub _normalize { my $pointdb = shift; my $sum = 0; $pointdb->iterinit(); while (my $id = $pointdb->iternext()) { my $val = $pointdb->get($id); $sum += $val * $val; } $sum = sqrt($sum); $pointdb->iterinit(); while (my $id = $pointdb->iternext()) { my $val = $pointdb->get($id); $pointdb->put($id, $val / $sum); } } sub hits { my ($linkdb, $authdb, $hubdb, $num_loop) = @_; return if !$linkdb || !$authdb || !$hubdb || !$num_loop; print "Start HITS Algorithm\n"; print "Initialize authority and hub values\n"; _initialize($linkdb, $authdb); _initialize($linkdb, $hubdb); for (my $i = 0; $i < $num_loop; $i++) { print "HITS Loop No.$i\n"; print " Update authority values\n"; _update_authority($linkdb, $authdb, $hubdb); print " Normalize authority values\n"; _normalize($authdb); print " Update hub values\n"; _update_hub($linkdb, $authdb, $hubdb); print " Normalize hub values\n"; _normalize($hubdb); } print "Finish HITS Algorithm\n"; } sub main { my ($opt_link, $opt_dir); GetOptions( 'link=s' => \$opt_link, 'directory=s' => \$opt_dir, ); if (!$opt_link || !$opt_dir) { usage_exit(); } my $linkdb = TokyoCabinet::HDB->new(); if (!$linkdb->open($opt_link, $linkdb->OREADER)) { die "cannot open $opt_link"; } # Authority my $dbpath = "$opt_dir/".DBM_AUTHORITY; my $authdb = TokyoCabinet::HDB->new(); if (!$authdb->open($dbpath, $authdb->OWRITER | $authdb->OCREAT | $authdb->OTRUNC)) { die 'cannot open authority dbm'; } # Hub $dbpath = "$opt_dir/".DBM_HUB; my $hubdb = TokyoCabinet::HDB->new(); if (!$hubdb->open($dbpath, $hubdb->OWRITER | $hubdb->OCREAT | $hubdb->OTRUNC)) { die 'cannot open hub dbm'; } hits($linkdb, $authdb, $hubdb, 2); if (!$linkdb->close()) { die 'DBM error: '.$linkdb->errmsg($linkdb->ecode); } if (!$authdb->close()) { die 'DBM error: '.$authdb->errmsg($authdb->ecode); } if (!$hubdb->close()) { die 'DBM error: '.$hubdb->errmsg($hubdb->ecode); } } main(); __END__
実行すると、出力先のディレクトリに各ノードのAuthorityらしさ、Hubらしさの値が格納されたDBMが保存されます。DBMはTokyoCabinetのHashDBを使用しています。Perlだとさすがにちょっと重いです。
% hits.pl -l input/keywordlink.hdb -d output/ Start HITS Algorithm Initialize authority and hub values HITS Loop No.0 Update authority values Normalize authority values Update hub values Normalize hub values HITS Loop No.1 Update authority values Normalize authority values Update hub values Normalize hub values Finish HITS Algorithm % ls output/ auth.hdb hub.hdb
結果を確認してみます。ここではauthority値の高い上位20個を出してみます。
% tchmgr list -pv output/auth.hdb | sort -k 2 -g -r | head -20 795475 0.609741015783626 774362 0.336106167081492 1026301 0.126274804347428 1154752 0.123104890818884 1115992 0.118730319034636 382164 0.114997761746758 367227 0.113159899472264 695574 0.106973706038722 139686 0.104140457125625 1187903 0.0957168846339769 2314 0.0884719214904044 934064 0.0872059038347122 771753 0.0820636547333957 426 0.0804728979044152 774353 0.0795730106371791 254551 0.0794516311517766 975171 0.0772167231742544 1140703 0.0731744680425005 2008 0.0701603398667454 1205720 0.0695813798570621
keyがキーワードのIDで、valueはauthority/hub値になっています。IDのままだと分からないので、キーワードに戻してみると、以下の結果になります。地名が多く含まれていますね。
| 順位 | authority値の高いキーワード |
|---|---|
| 1 | 日本 |
| 2 | 東京都 |
| 3 | アメリカ合衆国 |
| 4 | 北海道 |
| 5 | イギリス |
| 6 | 大阪府 |
| 7 | 昭和 |
| 8 | フランス |
| 9 | 神奈川県 |
| 10 | テレビ朝日 |
| 11 | ドイツ |
| 12 | 愛知県 |
| 13 | 埼玉県 |
| 14 | 兵庫県 |
| 15 | 千葉県 |
| 16 | 福岡県 |
| 17 | 明治 |
| 18 | 静岡県 |
| 19 | 俳優 |
| 20 | 第二次世界大戦 |
またHub値の高いワードは以下になります。「○○年の〜」というキーワードが多く含まれています。その年の出来事へのリンクが多く含まれているからでしょうか。
| 順位 | hub値の高いキーワード |
|---|---|
| 1 | 2007年の日本 |
| 2 | 日本 |
| 3 | 2006年の日本 |
| 4 | 2008年の日本 |
| 5 | 「最近の出来事」2005年2月 |
| 6 | 日本の地理 |
| 7 | 世界の一体化 |
| 8 | 訃報 2007年 |
| 9 | 日本における市外局番の変更 |
| 10 | 広域地名 |
| 11 | 「最近の出来事」2005年3月 |
| 12 | 住宅扶助 |
| 13 | ファミリーマート |
| 14 | 「最近の出来事」2004年3月 |
| 15 | テスト・ザ・ネイション |
| 16 | 2006年のスポーツ |
| 17 | 日本の市の人口順位 |
| 18 | 2007年のスポーツ |
| 19 | 東横イン |
| 20 | ローカルヒーロー |
これだけだとあまり面白い結果でもないので、今度はカテゴリを絞って調べてみます。女性タレントに絞ったときのAuthority値の高いキーワードは以下になります。有名な人がちゃんと上位にきていますね。
| 順位 | authority値の高いキーワード |
|---|---|
| 1 | 和田アキ子 |
| 2 | 松田聖子 |
| 3 | 松浦亜弥 |
| 4 | 中森明菜 |
| 5 | 中山美穂 |
| 6 | 上戸彩 |
| 7 | 工藤静香 |
| 8 | 藤原紀香 |
| 9 | BoA |
| 10 | 篠原涼子 |
| 11 | 広末涼子 |
| 12 | 斉藤由貴 |
| 13 | 中川翔子 |
| 14 | 宮沢りえ |
| 15 | 久本雅美 |
なかなか面白いですね。まあこれぐらいならネットワークを解析しなくても、文章の多いページとかで簡単に解析できてしまいそうな気もしますが…。
ちなみに、HITSはネットワークを行列として考えたときに、その行列の固有値を求める問題として考えられるそうなので、ちまたにたくさんある行列計算用ライブラリを使えば簡単に解けそうだけど、wikipediaのように多数のノード・リンクを持つネットワークでも問題なく計算できるものなんだろうか？まずそっちを試してから自分で作るべきなんだろうけど、あまりうまくいく気がしなかったので今回は自前でやってしまいました。ちなみに、CPANモジュールのAlgorithm::HITSはPerlの行列演算用ライブラリのPDLを使って、固有値を求めてAuthority,Hubを特定しています。
k-meansとか他のアルゴリズムの実装もそうだけど、すべてをメモリ上に読み込んで実行するようなものではなくて、DBMなどを使用したり、適切にデータを分割しつつ大容量のデータに対しても問題なく実行できるデータマイニング用ツールを作ったら、受けたりしないだろうか。でもいまならHadoop使って分散処理しとけってことにもなるのかな？
