たつをの ChangeLog : 2011-11-10

HITS とはハイパーリンク構造（リンクや被リンクなど）を用いてウェブページのスコアを計算する方法。Google で用いられている PageRank の仲間。

HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。

アルゴリズム概要

各ページiの持つ auth を 、hub を とする。 をウェブグラフ全てのリンクの集合とし、 はページiからjへのリンクを表す(有無：1 or 0)とする。そして、以下の式（オリジナル論文での式）を繰り返し計算し最終的な auth と hub を得る。初期値は何らかの方法で与えられるとする。



実例で解説。下図のようなウェブグラフがあるとする。



初期値 は全て1として2回繰り返して計算してみる。

	0	1	2	3	4	5
	1	1	1	1	1	1
	1	0	2	1	3	0
	5	1	3	0	3	3
	1	0	8	3	11	0
	19	1	11	0	11	11

表の見方： は2番のノードのAuthorityスコアで、0番(=1)と4番(=1)からリンクが張られているので 1+1=2 となる。また、 は0番のノードのHubスコアでには2番(=2)と4番(=3)へリンクが張られているので 2+3=5 となる。

k=2 の時点では一番 Authority score が高いのが 4 番のページ(11)で、一番 Hub score が高いのが 0 番のページ(19)となる。

行列による計算

実装に際しては行列として扱うと楽。リンクは隣接行列で表すことができる。

前述のウェブグラフの隣接行列は下記のようになる。



で、最初にあげたオリジナルの式は下記の形に置き換えらえる（はの転置行列）。



そしていろいろあって下記の形に置き換えらえる（って、代入するだけ）。



つまり auth の計算は行列とベクトルの積を収束するまで繰り返し行えば良い。そして auth が出てきたら hub は一回の計算で出てくる。

先ほどの隣接行列での計算例。 はこうなる。



で、下記を繰り返し計算する。



結果はこうなる。



一番 Authority score が高いのが 4 番のページ(0.5)で、一番 Hub score が高いのが 0 番のページ(0.366)となる。グラフを再掲しておく。なんとなく納得できるかと。



なお、x も y も正規化している（要素の合計で割るだけ）。

サンプルプログラム

確認のために perl で作ったプログラムとその実行例をあげておく。あくまでサンプルプログラムなので高速化の余地はたくさんある（そもそも行列サイズが大きいとダメ）。あと、収束判定は面倒なので繰り返し数を固定にしている。

■コード(naive-hits-mini.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my $L_ref = [map {chomp; [split(/\s+/, $_)]} <DATA>];
my $Lt_ref = transpose($L_ref);
my $LtL_ref = multiply($Lt_ref, $L_ref);
print_matrix($LtL_ref);

my $x_ref;
foreach (@$L_ref) {
    push @$x_ref, [1];
}

for (my $i = 0; $i < 20; $i++) {
    $x_ref = normalize(multiply($LtL_ref, $x_ref));
}
print_vector($x_ref);

my $y_ref = normalize(multiply($L_ref, $x_ref));
print_vector($y_ref);

sub transpose {
    my ($m_ref) = @_;
    my @rv;
    for (my $i = 0; $i < @$m_ref; $i++) {
	for (my $j = $i; $j < @{$m_ref->[0]}; $j++) {
	    $rv[$j][$i] = $m_ref->[$i][$j];
	    $rv[$i][$j] = $m_ref->[$j][$i];
	}
    }
    return \@rv;
}

sub multiply {
    my ($m1_ref, $m2_ref) = @_;
    my @rv;
    for (my $i = 0; $i < @$m1_ref; $i++) {
	for (my $j = 0; $j < @{$m2_ref->[0]}; $j++) {
	    for (my $z = 0; $z < @$m2_ref; $z++) {
		$rv[$i][$j] += $m1_ref->[$i][$z] * $m2_ref->[$z][$j];
	    }
	}
    }
    return \@rv;
}

sub normalize {
    my ($v_ref) = @_;
    my @rv;
    my $sum = 0;
    foreach my $i (@$v_ref) {
	$sum += $i->[0];
    }
    foreach my $i (@$v_ref) {
	push @rv, [$i->[0] / $sum];
    }
    return \@rv;
}

sub print_vector {
    my ($m_ref) = @_;
    print join("\n", map {sprintf "%.4f", $_->[0]} @$m_ref), "\n\n";
}

sub print_matrix {
    my ($m_ref) = @_;
    print join("\n", map {"@$_"} @$m_ref), "\n\n";
}

__DATA__
0 0 1 0 1 0
1 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0

■実行例：上から、, auth, hub。

% ./naive-hits-mini.pl
1 0 0 0 0 0
0 0 0 0 0 0
0 0 2 1 1 0
0 0 1 1 0 0
0 0 1 0 3 0
0 0 0 0 0 0

0.0000
0.0000
0.3660
0.1340
0.5000
0.0000

0.3660
0.0000
0.2113
0.0000
0.2113
0.2113

データは前述のもの()を使っている。結果も前述のと同じとなった。

参考文献

この本の記法、式展開、サンプルを使用させて頂きました。PageRankの本なのですが、HITSの解説が分かりやすいです。
- Google PageRankの数理 --最強検索エンジンのランキング手法を求めて--


本記事の数式および図は Google Chart API を使用しています。
- #google - chart API で数式表示 (404 Blog Not Found)
http://blog.livedoor.jp/dankogai/archives/51299017.html
- Google Chart API で Graphviz が使える！すごい！[2011-02-15-3]

その他の参考文献：
- Wikipedia:HITS algorithm
- HITS, 主成分分析, SVD (naoyaのはてなダイアリー)
http://d.hatena.ne.jp/naoya/20090301/hits
（IIRでもやりました。）

うちの子の出生届を出しに行ったときに手続きした「子ども手当」ですが、政治的ないろいろでまた申請しなおしました。面倒ですねよねえ。



ref.
- [を] とらちゃんの出生届[2010-09-17-2]

「子ども手当」。
これは中学校修了まで月額1万3千円（現在）支給されるというもの。
ありがたや。

ほぼ毎朝欠かさず作っているサラダの写真と材料メモを週に一度木曜日にまとめてブログ記事にしています。

妻子帰省のためしばらくお休みしていましたが今週から復活です。朝に一日1,2種類ずつ離乳食ストックを作っている関係で、火水木はその残りが追加されている状況です。

■11/7（月）

キュウリ
レタス
プチトマト

■11/8（火）

ブロッコリー（加熱）
キャベツ（加熱）
ソーセージ（加熱）
キュウリ
レタス
フライドオニオン

■11/9（水）

ニンジン（加熱）
ソーセージ（加熱）
キュウリ
レタス
プチトマト

■11/10（木）

サツマイモ（加熱）
ソーセージ（加熱）
キュウリ
レタス
プチトマト

これまでの記録

(0) 朝食サラダメモ、始めます[2011-02-15-4]
(1) 朝食サラダメモ(2011/2/12-17)[2011-02-17-2]
(2) 朝食サラダメモ(2011/2/18-24)[2011-02-24-1]
(3) 朝食サラダメモ(2011/2/25-3/3)[2011-03-03-1]
(4) 朝食サラダメモ(2011/3/4-10)[2011-03-10-1]
(5) 朝食サラダメモ(2011/3/11-17)[2011-03-17-2]
(6) 朝食サラダメモ(2011/3/18-24)[2011-03-24-1]
(7) 朝食サラダメモ(2011/3/25-31)[2011-03-31-1]
(8) 朝食サラダメモ(2011/4/1-7)[2011-04-07-1]
(9) 朝食サラダメモ(2011/4/8-14)[2011-04-14-3]
(10) 朝食サラダメモ(2011/4/15-21)[2011-04-21-1]
(11) 朝食サラダメモ(2011/4/22-28)[2011-04-28-4]
(12) 朝食サラダメモ(2011/4/29-5/5)[2011-05-05-1]
(13) 朝食サラダメモ(2011/5/6-12)[2011-05-12-2]
(14) 朝食サラダメモ(2011/5/13-19)[2011-05-19-3]
(15) 朝食サラダメモ(2011/5/20-26)[2011-05-26-2]
(16) 朝食サラダメモ(2011/5/27-6/2)[2011-06-02-1]
(17) 朝食サラダメモ(2011/6/3-9)[2011-06-09-1]
(18) 朝食サラダメモ(2011/6/10-16)[2011-06-16-1]
(19) 朝食サラダメモ(2011/6/17-23)[2011-06-23-1]
(20) 朝食サラダメモ(2011/6/24-30)[2011-06-30-1]
(21) 朝食サラダメモ(2011/7/1-7)[2011-07-07-5]
(22) 朝食サラダメモ(2011/7/8-14)[2011-07-14-1]
(23) 朝食サラダメモ(2011/7/15-21)[2011-07-21-1]
(24) 朝食サラダメモ(2011/7/22-28)[2011-07-28-1]
(25) 朝食サラダメモ(2011/7/28-8/4)[2011-08-04-2]
(26) 朝食サラダメモ(2011/8/5-11)[2011-08-11-1]
(27) 朝食サラダメモ(2011/8/12-18)[2011-08-18-1]
(28) 朝食サラダメモ(2011/8/19-25)[2011-08-25-1]
(29) 朝食サラダメモ(2011/8/26-9/1)[2011-09-01-4]
(30) 朝食サラダメモ(2011/9/2-8)[2011-09-08-1]
(31) 朝食サラダメモ(2011/9/9-15)[2011-09-15-1]
(32) 朝食サラダメモ(2011/9/16-22)[2011-09-22-1]
(33) 朝食サラダメモ(2011/9/23-29)[2011-09-29-1]
(34) 朝食サラダメモ(2011/9/30-10/6)[2011-10-06-1]
(35) 朝食サラダメモ(2011/10/7-13)[2011-10-13-1]
(36) 朝食サラダメモ(2011/10/14-20)[2011-10-20-1]
(37) 朝食サラダメモ(2011/10/21-27)[2011-10-27-1]

妻との連絡用に便利に使っていた iPhone アプリ「Beluga」が11月11日から使えなくなります。Facebook に買収されたのが原因。Facebook Messenger を使え、ということらしいです。でも妻は Facebook のアカウント持ってないからなあ。

- [を] 妻との連絡用ツールの一つとして iPhone に Beluga を入れてみた[2011-03-22-3]

ということで、代替アプリに移行しました。「RingReef」です。



使い勝手はだいたい Beluga と同じです。我が家では何の苦もなく移行完了です。よかった、よかった。

さっそく妻とともに活用中です。例えばこれは育児メモ。食事、お風呂、昼寝、オムツなどを記録して育児に役立てています。



もちろん不満点はいくつかあります。入力フォームで複数行入力するとカーソルが下の方に行き過ぎて見えなくなっちゃうとか。でも、これから良くなっていくでしょう、と期待。



追記111127: 入力フォームの問題は11/21のアップデートで解決してました。素晴らしい！

六本木というか西麻布かな。居酒屋がやっているランチです。品数多くし、おいしいしで、満足度が高いです。ここは当たり。



宿呂久 やどろく
http://r.tabelog.com/tokyo/A1307/A130701/13013722/
場所：東京都港区西麻布3-21-24 第五中岡ビル 2F

私は記事トップの写真の西京焼の定食を頂いたのですが、刺身までついてくる！嬉しすぎる！

これは一緒に行ったK氏ののっけ丼。刺身のお魚が増量でどんぶりになってる感じかな。


値段はなんでも1000円。ランチは最近始めたそうです。11:30から14:00までだって。