データモデリング Webページの検索とランキング

データモデリング
Webページの検索とランキング
Google, Yahooはこんなことをしている
検索の精度を示す指標
適合率(Precision)
P=
検索結果内の正解文書数
検索された文書の数
全文書内の
適合文書の数
(本当の解集合)
検索された
文書の数
再現率(Recall)
R=
検索結果内の正解文書数
全文書内の適合文書の数
F値
F= 1
R
R
全文書
2
+
P
1
P
検索結果内の
正解文書数
条件が厳しくなるとPが上がり Rが下がる
条件が緩くなるとPが下がり Rが上がる
キーワードらしさ tf-idf
• 文章中の特徴的な単語(キーワード)を抽出するため
のアルゴリズム
• 文書の集合 { D1, D2, …., Dn}内の文書 Di を単語の
集合 { W1, W2, …, Wm} とみる
• 個々の単語の評価
– tf(Term Frequency)は単語の頻度
• 繰り返される 単語は評価が高い
• 文書Dk でのWi の出現数 / Dk の単語数
– Idf(Inverse Document Frequency)
• Wi は,特定の文書 Di にしか出現しない なら、評価が高い。逆に
Wi は,すべての文書に出現するなら、その 評価は低い
• 文書の集合 { D1, D2, …., Dn}のなかでWi が現れる比の逆数
• そのままでは大きすぎるので log をとる
• 単語の評価 = 頻度・ log (総文書数/出現文書数)
クローリング(Crawling)
• リンクの自動航行
– クローラと呼ばれるプログラムが、インターネット上のWeb
ペー ジのリンクをたどりながら情報を収集
– クローラは スパイダ(蜘蛛) とも呼ばれる
• クローラが収集するもの
– 各ページに含まれる各単語の tf-idf値 を計算
– ページごとに文書ベクトル化
文書ベクトルDk
Dk = (W1 のtf-idf値, W2 のtf-idf値, …, Wn のtf-idf値)
– 各ページのリンク先を記録(PageRankで利用)
• 一度、訪問したサイトはそこからのリンクを辿らない
• クローリングは 定期的 に実施される
空間ベクトル法
ページの文書ベクトル Dk と問合せのベクトルQの
類似度で検索を実施
Dk = (W1 のtf-idf, W2 のtf-idf, …, Wn のtf-idf)
Q = (W1 のtf-idf, W2 のtf-idf, …, Wn のtf-idf)
2つのベクトルのコサイン類似度
類似度
似ているときに1、逆方向の時に-1
• 文書「空間ベクトル法」
問合せ
– 類似度は0.7, Webは0.2, 検索は1.4
• 問合せ(類似度 Web 検索)
文書
– 類似度1, Web 1, 検索 1
• 類似度が高いものを選択
Web
検索
PageRank Algorithm
• 多くの検索結果を順位づけて並べたい
• Google 創始者の Larry Page と Sergey Brin が米
スタンフォード大学大学院在籍中に開発
• 論文の評価にヒントを得て考え出された
• PageRankとは
– 「多くの良質なページからリンクされているページは、
やはり良質なページである」 という再帰的な関係をも
とに、すべてのWebページの重要度を判定したもの
– PageRank 自体はユーザが検索式に与えた語句とは
まったく無関係な、 すでに定まった量
Googleの紹介ページより
• ページAからページBへのリンクをページAによるペー
ジBへの支持投票と みなし、Googleはこの投票数によ
りそのページの重要性を判断します。
• しかしGoogleは単に票数、つまり リンク数を見るだけ
ではなく、票を投じた ページについても分析します。
「重要度」 の高いページによって投じられた票はより
高く評価されて、それを受け取ったページ を「重要なも
の」 にしていくのです。
• PageRankは ページの重要度を示す総合的な指標で
あり、各検索に影響 されるものではありません
PageRankの意味の図示
• あるページの PageRank を、そのページに存
在する発リンク数で 割った数が、リンク先の
ページの PageRank に加算される
数式を使って表現
• すべてのWebページの集合を V とし,それらの間
のリンクの集合を E とするとWeb空間は
G=(V, E)
で表現できる
• ページの総数を n とし,ページ i のPageRankスコア
を P(i), ページ j からの外向けリンクの数を Oj
とすると
P(i) = Σ
(j i) ∈ E
P(j)
Oj
(式1)
ただし、(j i) はページ j からページ i へのリンク
ベクトルと行列で表現
• PageRankのスコアを値とする n 次元ベクトルを P,
ページ間のリンクを表現する行列を A とすると、
P=
Ai j =
P(1)
P(2)
:
P(n)
1
Oi
(i j) ∈ E の場合
ページ i から j にリンクがあれば
リンク元ページ i の外向きリンク数の逆数
(式3)
それ以外
0
先の式は
P=
と表される
(式2)
AT
P
(式4)
どうしてAの転置行列 AT なの?
さきの(式1)とAの定義(式3)をよく見比べると,リンクの出るページと入るペー
ジで i と j が入れ替わっている.
• ページ i (1≦ i ≦n)からページ j にリンクがある場合に,ページ j のペー
ジランク P(j) は
P(j) = A11 P(1) + A21 P(2) +...+An1P(n)
= (1/o1) P(1) + (1/o2) P(2) +...+ (1/on) P(n)
となる.Aの2つある添字のうち,さきにある添字が増える式になっている.
ページランクの計算を,通常の行列とベクトルの積で表現するには
P(i) = A11 P(1)
+ A12 P(2)
+...+A1nP(n)
となって, Aの2つある添字のうち,後にある添字が増える式になって欲しい.
どうすればよいか?
i と j をひっくり返せば良い.
つまり 転置した行列を用いれば良い.
図による例示
この図を表現する
行列 A は
A=
A21だから, ページ2から1へリンクがあるかどうか.
0 1/5 1/5 1/5 1/5 0 1/5
1 0 0 0 0 0 0
1/2 1/2 0 0 0 0 0
0 1/3 1/3 0 1/3 0 0
1/4 0 1/4 1/4 0 1/4 0
1/2 0 0 0 1/2 0 0
0 0 0 0 1 0 0
各ページのPageRankは不変な値
• 不変なベクトル P は A をかけても P のまま
P = AT P
• これは、行列とベクトルの固有値問題
λP=MP
(M – λ E) P = 0
P ≠ 0 が存在するためには
| M– λ E | = 0
これは λ の n 次方程式で、λ の実数解は高々 n 個
• この場合 P は固有値 λ = 1 に対応する固有ベクトル
• 固有値 λ = 1 の存在には特定条件の成立が必要
• 成立すれば 、n 元連立方程式 P = AT P より、べき乗法
で P も計算可能
Page と Brin はマルコフモデルに着目
• ユーザがリンクを無作為にたどるとすると、ペー
ジ遷移はマルコフ遷移モデル
• 次の条件が満たされると、固有値 λ = 1 が存在
– A がマルコフ推移の遷移確率行列である
• 各行の値を総和すると 1
• 外部にリンクを持たないページがない
– グラフが強連結である
• どのページからも、どのページへも辿り着ける
– グラフが非周期的である
• あるページからそこに戻るパスの長さが k (>1) の整数倍で
あれば周期的、そうでなければ非周期的(すなわち k = 1)
• このような A が見つかるということは、ユーザが
リンクをクリックし続けると、ある特定のページに
行き着く確率を計算できることを意味する
Page と Brin のアイデア
遷移確率行列を修正
① 外部リンクが無いページからは、各ページに同じ確率
で遷移
– このページに相当する A の行はすべて 1/n
② ユーザは確率 d でリンクを辿る(1-dで新ページを検索)
– 各ページからすべてのページへのリンク追加(確率は 1- d )
要素がすべて1のベクトルが e のとき、遷移確率は
1
(1 – d) e + d ATp = (1– d) 1 + d
:
1
Page と Brin の論文では d = 0.85
A11 A21 ・・
:
1/n 1/n ・・
:
p
[補助] PageとBrinは考えた!
• ①について,外部にリンクを持たないページからはn個あ
るページのどれにでも同じ確率(1/n)で移動する.(これで
A がマルコフ推移の遷移確率行列になった)
• ②について,あるページから出ているリンクをたどる確率
は d で,リンクを辿らず無作為に新しいページに移る確率
は(1-d)である.(これで,どのページへも辿り着けるように
なった.また周期kが1となったので、周期グラフでもなく
なった)
• 式の中で,(1-d)e の項はリンクを辿らず無作為に新しい
ページに移行した時を表し,dATp の項は現在のページ
からのリンクを辿った時を表す.
すべてのページの PageRank を計算
• 不変になるまで遷移確率行列を繰り返し適用
P0 = e / n
k=1
do {
Pk = (1 – d ) e + d AT Pk-1
k=k+1
} while( | Pk – Pk-1 | < ε )
return Pk
3.22億個のリンクがある場合、52回の繰り返しで収束
検索エンジンの概要
• クローリングしてインデックスと 行列 A を作っ
ておく。
インデックスは、ページごとの文書ベクトル Dk
• Dk = (W1 のtf-idf値, W2 のtf-idf値, …, Wn のtf-idf値)
• PageRank を計算しておく
• ユーザが指定した検索式とインデックスから、
類似度を使って検索結果の集合を作成
• 検索結果の集合の要素を PageRank で整列