ページの関連度とアンテナ

昨日(id:atzy:20080403)、以下のようなことを書きました。

はてなアンテナでは「おとなりページ」なるものがあります。「あるページAと別のページBが、同じアンテナからリンクされている」という数が多いとおとなりとなるようです。「おとなり指数」なるものもありますが、せいぜい、余弦をとったとかそんな感じでしょうか？毎回動的に計算しているようですから、たいしたことはやっていないのは明白といえます。

ここで「余弦をとった」と一言で終わらせています。具体的にはどうやって、二つのページが関連していると判断しているのでしょうか？

「私が考案しました」という話ではなく、(たぶん)教科書に書かれている方法です。

リンク関係のベクトル

ウェブページに限らず、ある二つのものの関連の大きさはどのようにして求めるのでしょうか？さまざまな手法があると思いますが、「特性ベクトル」と呼ばれるものを利用することがあります。

仮に、人間を分類するとして、次の特徴を数値化できたとしましょう。

国語が好きな度合い
数学が好きな度合い
社会科が好きな度合い
理科が好きな度合い
外国語が好きな度合い

例えば学校の10段階評価でも構いません。その場合は1から10の値をとることになります*1。そして、それぞれ、人物について実際に値が決まります。左から順に国語、数学、社会科、理科、外国語の数値としましょう。

山田(3, 9, 1, 8, 5)
田中(7, 2, 3, 6, 9)
佐藤(3, 9, 8, 9, 2)

これを特性ベクトルと呼びます。もちろん、「適切な」特性ベクトルをとる必要がありますが、適切な特性ベクトルが何であるのか自体が大きな問題ですので、ここではその話はいたしません。

ベクトルの関連度(内積)

この特性ベクトルが似ていればそれは「近い」のだというのが、一つの考え方です。ベクトルというのは矢印のようなもので、「近さ」というものを考えることができます。

では、近さをどのように表すのかといえば、例えば「内積」です。ベクトルの内積は高校数学あたりであったかと思います。

しかし、そのような数学の話はおいておいて、やることは簡単です。山田さんと田中さんの特性ベクトルの内積ならば、3*7 + 9*2 + 1*3 + 8*6 + 5*9 = 21 + 18 + 3 + 48 + 45 = 135 となります。同じ特徴どうしを掛け合わせて和をとることになります。

簡単でしょう？こんな単純な計算で終わりです。内積とかベクトルとかいうから難しく聞こえますが、中学生でも分かる話です。

ベクトルの関連度(余弦)

内積は実際に利用されるものですが、「全体的に高得点であるかどうか」が大きく効いてくるという性質を持ちます。そうでなく、「(高得点かどうかにかかわらず)理系科目が突出している人」という特徴を捉えたいときにはそれは不適切となります。

その場合は、ベクトル自体を正規化しておく必要があります。あるいは、特性ベクトルはそのままで、余弦をとるという言い方をすることもできます。正規化とは、この場合は、特性ベクトルの長さを1にするというものです。起点をそろえた矢印の一方から他方に垂線を下ろし、起点から垂線の足までの長さということもできます。

ベクトルX, Yの余弦 = ベクトルX, Yの内積/(Xの長さ*Yの長さ)

という関係にあります。

おとなりページ

では、おとなりページはどのように算出されているのでしょうか？調べたら書いてあるのかもしれませんが、調べておりませんので、推測で書きます。仮にはてながそのように実装していなかったとしても、「そういう考え方もあるんだ」と考えてください。

おそらくは、特性ベクトルとして「アンテナからのリンク」をとっています。簡単のために、アンテナが三つ(A, B, C)であり、アンテナからリンクされているページが四つ(X, Y, Z, W)であったとします。

X = (1, 0, 1)
Y = (1, 1, 0)
Z = (1, 1, 1)
W = (0, 0, 1)

上記のような特性ベクトルをとります。左から順にA, B, C のアンテナからのリンクの有無を表し、リンクありを1、なしを0ととります。

ここで、ページXとページYの内積は1、ページXとページZの内積は2となります。余弦をとってもよいでしょう。

なお、軸を反転させて、アンテナ間の関連度を考えることもできます。

A = (1, 1, 1, 0)
B = (0, 1, 1, 0)
C = (1, 0, 1, 1)

アンテナAとBの内積は2、アンテナBとCならば1となります。

はてながこれを使っているとして、この内積・余弦の計算をページアクセス時にリアルタイムにやっているのか、あるいは、アンテナ更新時にやっているのか、あるいは実は一日に一度だけバッチ処理で計算して、その間は更新が反映されないのか、そのあたりは調べていないので分かりません。アンテナ更新の際にアップデート計算しているのではないかと想像します。たぶん、アンテナ総数に対して、アンテナに登録されているページや一度の更新で変化するページは少ないのでうまい計算があるのではないでしょうか。

おとなり指数は%で表示されておりますので、ベクトル完全一致を100%として、余弦で処理しているというのが、とりあえずの見方かと思います。これは、頑張れば人力で確かめることが可能ですが、私自身は「はてながどうしているか」でなく、「どうやったら本当に関連しているものが見つかるか」に興味がありますので、放置します。

PageRank

ちなみに、PageRankはどうやっているのかというと、ここの「アンテナ」と「ページ」の区別を行いません。つまり、「全部がページかつアンテナ」と考えます。ページA, B, C, DからページA, B, C, Dへのリンク関係の有無を特性ベクトルとしています。
このようなものは、全体を行列として扱い、隣接行列といいます。

Googleでは、さすがに「ページ間のリンクの余弦をとっています」程度の処理で終了にはしていないのではないかと思いますが、基本的な「関連」の考え方はこれだと思います。少なくともページの中に含まれる単語を解析していると思います。出現単語の特性ベクトルの類似で類似度をはかるのも一般的な手法です。

*1:学校の成績の場合は平均を0にするように変換するのが適切でしょうね。例えば10→9、9→7、…、1→-9のように。