読者です 読者をやめる 読者になる 読者になる

のんびり読書日記

日々の記録をつらつらと

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::HITSPerlの行列演算用ライブラリのPDLを使って、固有値を求めてAuthority,Hubを特定しています。

k-meansとか他のアルゴリズムの実装もそうだけど、すべてをメモリ上に読み込んで実行するようなものではなくて、DBMなどを使用したり、適切にデータを分割しつつ大容量のデータに対しても問題なく実行できるデータマイニングツールを作ったら、受けたりしないだろうか。でもいまならHadoop使って分散処理しとけってことにもなるのかな?