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

Presentation on theme: "データモデリング Webページの検索とランキング"— Presentation transcript:

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

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

3 キーワードらしさ 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 (総文書数/出現文書数)

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

5 空間ベクトル法 ページの文書ベクトル Dk と問合せのベクトルQの類似度で検索を実施 文書「空間ベクトル法」 問合せ（類似度 Web 検索）
Dk = (W1 のtf-idf, W2 のtf-idf, …, Wn のtf-idf) Q = (W1 のtf-idf, W2 のtf-idf, …, Wn の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へのリンクをページAによるページBへの支持投票と みなし、Googleはこの投票数によりそのページの重要性を判断します。 しかしGoogleは単に票数、つまり　リンク数を見るだけではなく、票を投じた ページについても分析します。「重要度」 の高いページによって投じられた票はより高く評価されて、それを受け取ったページ を「重要なもの」 にしていくのです。 PageRankは ページの重要度を示す総合的な指標であり、各検索に影響 されるものではありません

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

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

10 ベクトルと行列で表現 PageRankのスコアを値とする n 次元ベクトルを P, ページ間のリンクを表現する行列を A とすると、
　　先の式は 　　と表される （式2） Oi 1 (i j) ∈ E の場合 ページ i から j にリンクがあれば リンク元ページ i の外向きリンク数の逆数 Ai j ＝ （式3） A は，ページ i から j にリンクがあればリンク元ページ i の外向きリンク数の逆数を 要素 Aij　とする行列 前スライドの∑の式と今スライドのAの式の定義をよく見比べると，リンクの出るページと入るページで i と ｊ が入れ替わっている． ページ i （1≦ i ≦n）からページ j にリンクがある場合に，ページ j　のページランク P(ｊ） は P(j) = A11 P(1) A21 P(2) +．．．+An1P(n) = (1/o1) P(1) + (1/o2) P(2) +．．．+ (1/on) P(n) となる．これを行列とベクトルの積で表現するには P(i) = A11 P(1) A12 P(2) +．．．+A1nP(n) となっていて欲しい．どうすればよいか？ i と j をひっくり返せば良い． つまり　転置した行列を用いれば良い． 0 それ以外 （式4）

11 どうして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の２つある添字のうち，さきにある添字が増える式になっている．ページランクの計算を，通常の行列とベクトルの積で表現するには p (i) = A11 p (1) A12 p (2) +．．．+A1n p (n) となって， Aの２つある添字のうち，後にある添字が増える式になって欲しい．どうすればよいか？ i と j をひっくり返せば良い． つまり　転置した行列を用いれば良い．

12 図による例示 この図を表現する行列 A は A ＝
0 1/5 1/5 1/5 1/5 0 1/ /2 1/ /3 1/3 0 1/ /4 0 1/4 1/4 0 1/4 0 1/ / A ＝ この行列 A をページランク p1, p2, …, pn　からなるベクトルPにかけてはいけない． そんなことをしたら 　　　A11 P(1) A21 P(2) +．．．+An1P(n) になってしまう．これだと，第2項は 　「ページ1からページ２へのリンクがあるときに，ページ1の外向きリンクの逆数を，リンクの先のページランクP(2)にかける」 という意味になってしまう．そうではなく，第2項は 　　「ページ2からページ1へのリンクがあるときに，ページ2の外向きリンクの逆数を，リンクの先のページランクP(１)にかける」 となっていないといけない． 行列　Aを転置すると（A の行と列を入れ替えると），まさしくそうなる． A21だから, ページ2から1へリンクがあるかどうか．

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

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

15 Page と Brin のアイデア 要素がすべて1のベクトルが e のとき、遷移確率は 遷移確率行列を修正
外部リンクが無いページからは、各ページに同じ確率で遷移 このページに相当する A の行はすべて 1/n ユーザは確率 d でリンクを辿る（1-dで新ページを検索） 各ページから すべてのページ へのリンク追加（確率は 1- d ） 要素がすべて1のベクトルが e のとき、遷移確率は Page と Brin の論文では d = 0.85 ①について，外部にリンクを持たないページからはn個あるページのどれにでも同じ確率（1/n）で移動する ②について，あるページから出ているリンクをたどる確率は d で，リンクを辿らず無作為に新しいページに移る確率は(1-d)であるとPageとBrinは考えた． 式の中で，(1-d)e　の項はリンクを辿らず無作為に新しいページに移行した時を表し，dAp　の項は現在のページからのリンクを辿った時を表す．

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

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

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