[を]CHALOW Search: date:2011-11-10

宿呂久のお魚ランチは満足度高い！（六本木）

さよなら Beluga！こんにちは RingReef！

【日記】朝食サラダメモ(2011/11/4-10)

「子ども手当」の申請をまた行う

リンク構造を用いてスコアを計算する HITS アルゴリズム

これまでの記録

アルゴリズム概要

行列による計算

サンプルプログラム

参考文献

5 件見つかりました。

2011-11-10-5 [飲食店]

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

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

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

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

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

この記事に言及しているこのブログ内の記事

【日記】平日ランチメモ(2011/11/7-11) (2011-11-11)

2011-11-10-4 [iPhone]

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

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

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

- RingReef

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

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

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

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

この記事に言及しているこのブログ内の記事

2011 年 11 月に入れてみた iPhone/iPad アプリ (2011-11-30)

2011-11-10-3 [料理][日記][MorningSalad]

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

妻子帰省のためしばらくお休みしていましたが今週から復活です。朝に一日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]

この記事に言及しているこのブログ内の記事

2011-11-10-2 [Family]

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

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

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

この記事に言及しているこのブログ内の記事

2011-11-10-1 [Algorithm][Programming]

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

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

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

$\displaystyle x_{i}^{(k)}=\sum_{j:e_{ji}\in E}y_{j}^{(k-1)}\\y_{i}^{(k)}=\sum_{j:e_{ij}\in E}x_{j}^{(k)}$

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

初期値 $y_{i}^{(0)}$ は全て1として2回繰り返して計算してみる。

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

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

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

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

$L=\left(\begin{array}{cccccc}0&0&1&0&1&0\cr 1&0&0&0&0&0\cr 0&0&0&0&1&0\cr 0&0&0&0&0&0\cr 0&0&1&1&0&0\cr 0&0&0&0&1&0\cr\end{array}\right)$

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

$x^{(k)}=L^{T}y^{(k-1)}\\y^{(k)}=Lx^{(k)}$

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

$x^{(k)}=L^{T}Lx^{(k-1)}\\y^{(k)}=Lx^{(k)}$

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

先ほどの隣接行列 $L$ での計算例。 $L^{T}L$ はこうなる。

$L^{T}L=\left(\begin{array}{cccccc}1&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&2&1&1&0\cr 0&0&1&1&0&0\cr 0&0&1&0&3&0\cr 0&0&0&0&0&0\cr\end{array}\right)$

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

$x^{(k)}=L^{T}Lx^{(k-1)}=\left(\begin{array}{cccccc}1&0&0&0&0&0\cr 0&0&0&0&0&0\cr 0&0&2&1&1&0\cr 0&0&1&1&0&0\cr 0&0&1&0&3&0\cr 0&0&0&0&0&0\cr\end{array}\right)x^{(k-1)}$

結果はこうなる。

$x^{T}=\left(\begin{array}{cccccc}0&0&0.3660&0.1340&0.5&0\end{array}\right)\\y^{T}=\left(\begin{array}{cccccc}0.3660&0&0.2113&0&0.2113&0.2113\end{array}\right)$

一番 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

■実行例：上から、 $L^{T}L$ , 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

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

$y_{i}^{(0)}$

$x_{i}^{(1)}$

$y_{i}^{(1)}$

$x_{i}^{(2)}$

$y_{i}^{(2)}$

この本の記法、式展開、サンプルを使用させて頂きました。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でもやりました。）

この記事に言及しているこのブログ内の記事

たつをの ChangeLog