リンク構造を用いてスコアを計算する HITS アルゴリズム
2011-11-10-1
[Algorithm][Programming]
HITS とはハイパーリンク構造(リンクや被リンクなど)を用いてウェブページのスコアを計算する方法。Google で用いられている PageRank の仲間。
HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。
各ページiの持つ auth を
、hub を
とする。
をウェブグラフ全てのリンクの集合とし、
はページiからjへのリンクを表す(有無:1 or 0)とする。そして、以下の式(オリジナル論文での式)を繰り返し計算し最終的な auth と hub を得る。初期値は何らかの方法で与えられるとする。
![](https://chart.apis.google.com/chart?cht=tx&chl=%5Cdisplaystyle%20x_%7Bi%7D%5E%7B(k)%7D%3D%5Csum_%7Bj%3Ae_%7Bji%7D%5Cin%20E%7Dy_%7Bj%7D%5E%7B(k-1)%7D%5C%5Cy_%7Bi%7D%5E%7B(k)%7D%3D%5Csum_%7Bj%3Ae_%7Bij%7D%5Cin%20E%7Dx_%7Bj%7D%5E%7B(k)%7D)
実例で解説。下図のようなウェブグラフがあるとする。
![](https://chart.apis.google.com/chart?cht=gv:neato&chl=digraph{0-%3E2;0-%3E4;1-%3E0;2-%3E4;4-%3E2;4-%3E3;5-%3E4}&chs=200x200)
初期値
は全て1として2回繰り返して計算してみる。
表の見方:
は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)となる。
実装に際しては行列として扱うと楽。リンクは隣接行列で表すことができる。
前述のウェブグラフの隣接行列
は下記のようになる。
![](https://chart.apis.google.com/chart?cht=tx&chl=L%3D%5Cleft(%5Cbegin%7Barray%7D%7Bcccccc%7D0%260%261%260%261%260%5Ccr%201%260%260%260%260%260%5Ccr%200%260%260%260%261%260%5Ccr%200%260%260%260%260%260%5Ccr%200%260%261%261%260%260%5Ccr%200%260%260%260%261%260%5Ccr%5Cend%7Barray%7D%5Cright))
で、最初にあげたオリジナルの式は下記の形に置き換えらえる(
は
の転置行列)。
![](https://chart.apis.google.com/chart?cht=tx&chl=x%5E%7B(k)%7D%3DL%5E%7BT%7Dy%5E%7B(k-1)%7D%5C%5Cy%5E%7B(k)%7D%3DLx%5E%7B(k)%7D)
そしていろいろあって下記の形に置き換えらえる(って、代入するだけ)。
![](https://chart.apis.google.com/chart?cht=tx&chl=x%5E%7B(k)%7D%3DL%5E%7BT%7DLx%5E%7B(k-1)%7D%5C%5Cy%5E%7B(k)%7D%3DLx%5E%7B(k)%7D)
つまり auth の計算は行列とベクトルの積を収束するまで繰り返し行えば良い。そして auth が出てきたら hub は一回の計算で出てくる。
先ほどの隣接行列
での計算例。
はこうなる。
![](https://chart.apis.google.com/chart?cht=tx&chl=L%5E%7BT%7DL%3D%5Cleft(%5Cbegin%7Barray%7D%7Bcccccc%7D1%260%260%260%260%260%5Ccr%200%260%260%260%260%260%5Ccr%200%260%262%261%261%260%5Ccr%200%260%261%261%260%260%5Ccr%200%260%261%260%263%260%5Ccr%200%260%260%260%260%260%5Ccr%5Cend%7Barray%7D%5Cright))
で、下記を繰り返し計算する。
![](https://chart.apis.google.com/chart?cht=tx&chl=x%5E%7B(k)%7D%3DL%5E%7BT%7DLx%5E%7B(k-1)%7D%3D%5Cleft(%5Cbegin%7Barray%7D%7Bcccccc%7D1%260%260%260%260%260%5Ccr%200%260%260%260%260%260%5Ccr%200%260%262%261%261%260%5Ccr%200%260%261%261%260%260%5Ccr%200%260%261%260%263%260%5Ccr%200%260%260%260%260%260%5Ccr%5Cend%7Barray%7D%5Cright)x%5E%7B(k-1)%7D)
結果はこうなる。
![](https://chart.apis.google.com/chart?cht=tx&chl=x%5E%7BT%7D%3D%5Cleft(%5Cbegin%7Barray%7D%7Bcccccc%7D0%260%260.3660%260.1340%260.5%260%5Cend%7Barray%7D%5Cright)%5C%5Cy%5E%7BT%7D%3D%5Cleft(%5Cbegin%7Barray%7D%7Bcccccc%7D0.3660%260%260.2113%260%260.2113%260.2113%5Cend%7Barray%7D%5Cright))
一番 Authority score が高いのが 4 番のページ(0.5)で、一番 Hub score が高いのが 0 番のページ(0.366)となる。グラフを再掲しておく。なんとなく納得できるかと。
![](https://chart.apis.google.com/chart?cht=gv:neato&chl=digraph{0-%3E2;0-%3E4;1-%3E0;2-%3E4;4-%3E2;4-%3E3;5-%3E4}&chs=200x200)
なお、x も y も正規化している(要素の合計で割るだけ)。
確認のために perl で作ったプログラムとその実行例をあげておく。あくまでサンプルプログラムなので高速化の余地はたくさんある(そもそも行列サイズが大きいとダメ)。あと、収束判定は面倒なので繰り返し数を固定にしている。
■コード(naive-hits-mini.pl):
■実行例:上から、
, auth, hub。
データは前述のもの(
)を使っている。結果も前述のと同じとなった。
この本の記法、式展開、サンプルを使用させて頂きました。PageRankの本なのですが、HITSの解説が分かりやすいです。
- Google PageRankの数理 --最強検索エンジンのランキング手法を求めて--
![](https://asin.ta2o.net/img/4320122399-m.jpg)
本記事の数式および図は 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でもやりました。)
HITS は Authority score(以下、auth) と Hub score(以下、hub) の2種類のスコアを算出する。
アルゴリズム概要
各ページiの持つ auth を
実例で解説。下図のようなウェブグラフがあるとする。
初期値
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 |
表の見方:
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
■実行例:上から、
% ./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の数理 --最強検索エンジンのランキング手法を求めて--
![](https://asin.ta2o.net/img/4320122399-m.jpg)
本記事の数式および図は 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でもやりました。)