データモデリング Web ページの検索とランキン グ Google, Yahoo はこんなことをして いる.

Presentation on theme: "データモデリング Web ページの検索とランキン グ Google, Yahoo はこんなことをして いる."— Presentation transcript:

1 データモデリング Web ページの検索とランキン グ Google, Yahoo はこんなことをして いる

2 検索の精度を示す指標 適合率 (Precision) 検索結果内の正解文書数 検索された文書の数 再現率 (Recall) 検索結果内の正解文書数 全文書内の適合文書の数 F 値 F = 1R1R 1P1P + 2 検索結果内の 正解文書数 検索された 文書の数 全文書内の 適合文書の数 （本当の解集合） 全文書 条件が厳しくなると P が上がり R が下がる 条件が緩くなると P が下がり R が上がる RP P =P = R =R =

3 キーワードらしさ tf-idf 文章中の特徴的な単語（キーワード）を抽出する ためのアルゴリズム 文書の集合 { D 1, D 2, …., D n } 内の文書 D i を単語の 集合 { W 1, W 2, …, W m } とみる 個々の単語の評価 – tf （ Term Frequency ）は単語の頻度 繰り返される 単語は評価が高い 文書 D k での W i の出現数 / D k の単語数 – Idf(Inverse Document Frequency) W i は，特定の文書 D i にしか出現しない なら、評価が高い。 逆に W i は，すべての文書に出現するなら、その 評価は低い 文書の集合 { D 1, D 2, …., D n } のなかで W i が現れる比の逆数 そのままでは大きすぎるので log をとる 単語の評価 = 頻度・ log ( 総文書数 / 出現文書数 )

4 クローリング (Crawling) リンクの自動航行 – クローラと呼ばれるプログラムが、インターネット 上の Web ペー ジのリンクをたどりながら情報を収集 – クローラは スパイダ（蜘蛛） とも呼ばれる クローラが収集するもの – 各ページに含まれる各単語の tf-idf 値 を計算 – ページごとに文書ベクトル化 文書ベクトル D k D k = ( W 1 の tf-idf 値, W 2 の tf-idf 値, …, W n の tf-idf 値 ) – 各ページのリンク先を記録（ PageRank で利用） 一度、訪問したサイトはそこからのリンクを辿ら ない クローリングは 定期的 に実施される

5 空間ベクトル法 ページの文書ベクトル D k と問合せのベクトル Q の類似度で検索を実施 D k = ( W 1 の tf-idf, W 2 の tf-idf, …, W n の tf-idf) Q = ( W 1 の tf-idf, W 2 の tf-idf, …, W n の tf-idf) 2 つのベクトルのコサイン類似度 似ているときに１、逆方向の時に -1 文書「空間ベクトル法」 – 類似度は 0.7, Web は 0.2, 検索は 1.4 問合せ（類似度 Web 検索） – 類似度 1, Web 1, 検索 1 類似度が高いものを選択 類似度 Web 検索 文書 問合せ

6 PageRank Algorithm 多くの検索結果を順位づけて並べたい Google 創始者の Larry Page と Sergey Brin が米 スタンフォード大学大学院在籍中に開発 論文の評価にヒントを得て考え出された PageRank とは – 「多くの良質なページからリンクされているペー ジは、 やはり良質なページである」 という再帰 的な関係をもとに、すべての Web ページの重要度 を判定したもの – PageRank 自体はユーザが検索式に与えた語句とは まったく無関係な、 すでに定まった量

7 Google の紹介ページより ページＡからページＢへのリンクをページ A によ るページ B への支持投票と みなし、 Google はこの 投票数によりそのページの重要性を判断します。 しかし Google は単に票数、つまり リンク数を見 るだけではなく、票を投じた ページについても分 析します。「重要度」 の高いページによって投じ られた票はより高く評価されて、それを受け取っ たページ を「重要なもの」 にしていくのです。 PageRank は ページの重要度を示す総合的な指標で あり、各検索に影響 されるものではありません

8 PageRank の意味の図示 あるページの PageRank を、そのページに 存在する発リンク数で 割った数が、リン ク先のページの PageRank に加算される

9 数式を使って表現 すべての Web ページの集合を V とし，それらの 間のリンクの集合を E とすると Web 空間は G = ( V, E ) で表現できる ページの総数を n とし，ページ i の PageRank ス コアを P(i) ， ページ j からの外向けリンクの 数を O j とすると ただし、 (j i) はページ j からページ i へのリンク P(i) = Σ P(j) OjOj (j i) ∈ E （式１）

10 ベクトルと行列で表現 PageRank のスコアを値とする n 次元ベクトルを P, ページ間のリンクを表現する行列を A とすると、 先の式は と表される P = P(1) P(2) ： P(n) A i j ＝ OiOi 1 (i j) ∈ E の場合 ページ i から j にリンクがあれば リンク元ページ i の外向きリンク数の逆数 0 それ以外 P = A T P （式 2 ） （式 3 ） （式 4 ）

11 どうして A の転置行列 A T な の？ さきの ( 式 1) と A の定義 ( 式 3) をよく見比べると，リンクの出るページと 入るページで i と j が入れ替わっている． ページ i （ 1 ≦ i ≦ n ）からページ j にリンクがある場合に，ページ j の ページランク P( ｊ） は P(j) = A 11 P(1) + A 21 P(2) + ．．． +A n1 P(n) = (1/o 1 ) P(1) + (1/o 2 ) P(2) + ．．． + (1/o n ) P(n) となる． A の２つある添字のうち，さきにある添字が増える式になって いる．ページランクの計算を，通常の行列とベクトルの積で表現する には P(i) = A 11 P(1) + A 12 P(2) + ．．． +A 1n P(n) となって， A の２つある添字のうち，後にある添字が増える式になって 欲しい．どうすればよいか？ i と j をひっくり返せば良い． つまり 転置した行列を用いれば良い．

12 図による例示 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 A ＝A ＝ この図を表現す る行列 A は A 21 だから, ページ 2 から 1 へリンクがあるかどうか．

13 各ページの PageRank は不変な値 不変なベクトル P は A をかけても P のまま これは、行列とベクトルの固有値問題 P ≠ 0 が存在するためには これは λ の n 次方程式で、 λ の実数解は高々 n 個 この場合 P は固有値 λ = 1 に対応する固有ベクトル 固有値 λ = 1 の存在には特定条件の成立が必要 成立すれば 、 n 元連立方程式 P = A T P より、べき乗 法で P も計算可能 P = A T P λ P = M P （ M – λ E) P = 0 | M– λ E | = 0

14 Page と Brin はマルコフモデルに着 目 ユーザがリンクを無作為にたどるとすると、 ページ遷移はマルコフ遷移モデル 次の条件が満たされると、固有値 λ = 1 が存 在 – A がマルコフ推移の遷移確率行列である 各行の値を総和すると 1 外部にリンクを持たないページがない – グラフが強連結である どのページからも、どのページへも辿り着ける – グラフが非周期的である あるページからそこに戻るパスの長さが k (>1) の整数 倍であれば周期的、そうでなければ非周期的 ( すなわち k = 1) このような A が見つかるということは、ユー ザがリンクをクリックし続けると、ある特定 のページに行き着く確率を計算できることを 意味する

15 Page と Brin のアイデア 遷移確率行列を修正 ① 外部リンクが無いページからは、各ページに同じ確 率で遷移 – このページに相当する A の行はすべて 1/n ② ユーザは確率 d でリンクを辿る（ 1-d で新ページを検 索） – 各ページからすべてのページへのリンク追加（確率は 1- d ） 要素がすべて 1 のベクトルが e のとき、遷移確 率は Page と Brin の論文では d = 0.85 (1 – d) e + d A T p = (1– d) + d p 11：111：1 A 11 A 21 ・・ ： 1/n 1/n ・・ ：

16 [ 補助 ] Page と Brin は考えた！ ①について，外部にリンクを持たないページからは n 個あるページのどれにでも同じ確率（ 1/n ）で移動す る．（これで A がマルコフ推移の遷移確率行列になっ た） ②について，あるページから出ているリンクをたどる 確率は d で，リンクを辿らず無作為に新しいページに 移る確率は (1-d) である．（これで，どのページへも辿 り着けるようになった．また周期ｋが１となったので、 周期グラフでもなくなった） 式の中で， (1-d) e の項はリンクを辿らず無作為に新 しいページに移行した時を表し， d A T p の項は現在の ページからのリンクを辿った時を表す．

17 すべてのページの PageRank を計算 不変になるまで遷移確率行列を繰り返し適用 ３. ２２億個のリンクがある場合、 52 回の繰り返し で収束 P 0 = e / n k = 1 do { P k = (1 – d ) e + d A T P k-1 k = k + 1 } while( | P k – P k-1 | < ε ) return P k

18 検索エンジンの概要 クローリングしてインデックスと 行列 A を作っておく。 インデックスは、ページごとの文書ベクトル D k D k = ( W 1 の tf-idf 値, W 2 の tf-idf 値, …, W n の tf-idf 値 ) PageRank を計算しておく ユーザが指定した検索式とインデックス から、類似度を使って検索結果の集合を 作成 検索結果の集合の要素を PageRank で整列