データベースと情報検索

Size: px

Start display at page:

Download "データベースと情報検索"

かずしねぎたや
4 years ago
Views:

1 データベースと情報検索情報検索 (5) 検索エンジンの仕組み教員岩村雅一

2 日程 ( 情報検索 : 担当岩村 ) 12/9 検索エンジンを使ってみる 12/16 メディア検索を使ってみる 12/25 ウェブアプリケーションを使ってみる 1/9 検索エンジンを用いた演習 1/2 検索エンジンの仕組み 1/27 メディア検索の仕組み 2/3 消費者生成メディアの最近

3 Web の構造グラフ構造ページここにリンクがあるこっちにもリンクアンカーリンク

4 Web のサイズ

5 Web の地図どんな形? ランダム?

6 Web の地図 : 蝶ネクタイ理論 Web の直径は? 1 クリックくらい 1 くらい 1 くらい 1 万以上 19 クリック (1999 年 ) コアに到達可コアから到達不可コアから到達可コアに到達不可強連結な部分 IBM の HP より

7 Web の利用 ( アンケート ) Web での調べ物ディレクトリサービス主体? 検索エンジン主体? 検索エンジンに入れるキーワードの数は? 1 個 2 個 3 個 4 個 5 個それ以上

8 検索キーワード数 OneStat.com 調べ (24 年 7 月 ) 1. 2 語 : 3.9% 2. 1 語 : 26.83% 3. 3 語 : 16.6% 4. 4 語 : 14.83% 5. 5 語 : 6.76% 6. 6 語 : 2.81% 7. 7 語 : 1.13%

9 簡単な検索キーワードの有無 1 億ものページを数語で区別可能? 限界あり別の何か賢い方法が必要? どのような可能性が考えられるか?

10 参考文献 Google の秘密 - PageRank 徹底解説馬場肇 /pagerank.html サーチエンジン Google 山名早人近藤秀和情報処理, Vol.42, No.8, 21 WWW サーチエンジンの作り方原田昌紀情報処理, Vol.41, No.1, 2

11 Google Page & Brin により設立された (1998) Stanfordの大学院生データマイニングを研究世界最大級の情報を持つ検索エンジン 8 億ページ (25.4 現在 ) クラスタコンピューティング PC4.5 万台から8 万台 (CPUは倍; 予測値 ) 2 千 ~6 千テラバイト (1テラ=1,,,,=1 兆 )

12 PC 台数の推移

13 ソフトウェア構成収集アンカーの情報相対 URL を絶対 URL に変更アンカー部分のテキスト情報 web ページの相互リンク情報圧縮 anchor, word, word 位置などの抽出 word から word- ID へのハッシュ doc-id から word-id への索引とその逆逆向きの索引を作成

14 Mining= 採鉱 ( 鉱石を採掘すること ) Data Mining データ = 鉱山埋もれた有益な情報 = 鉱石 Text Mining データがテキストとして与えられたもの IBM の事例が有名 Web Mining Mining の対象が web PageRank は Web Mining の一種

15 Web Mining Web Contents Mining Web からの情報抽出やテキストマイニング Web Usage Mining ログやクリック履歴を解析してアクセスパターンを分析 Web Structure Mining リンク構造に基づくマイニング PageRank はこの一種

16 PageRank 基本的な考え方多くの重要なページからリンクされているページはやはり重要なページであるリンク = 投票ただし 1 ページが 1 票持っているのではないページの重要度に応じた票数

17 重要度 Google の秘密 - PageRank 徹底解説馬場肇より引用

18 重要度の意味被リンク数リンクされていればそれだけ重要度は大リンク元の重要度重要度が高いページからのリンクは高く評価リンク元のリンク数選び抜かれたリンクならば重要視小大小大

19 PageRank の計算重要度の初期値を定める推移確率に従って重要度を伝播収束した結果をPageRankとする

20 小規模な例に対する PageRank PageRank の値が最大のページは? Google の秘密 - PageRank 徹底解説馬場肇より引用

21 PageRank の評価順位 PageRank 文書 ID 発リンクID 被リンクID ,3,4,5,7 2,3,5, ,3,4,6 1,4,6, ,3, ,2 1,4, ,3,5 1, ,5 5

22 PageRank の意味と計算ランダムにリンクを辿るユーザが一定時間に各ページを訪問する確率ちょっと高度な内容推移確率を行列で表したとき最大固有値に対する固有ベクトルが PageRank となる詳しいことは Google で PageRank を検索して出てくる Google の秘密 - PageRank 徹底解説を見て!

23 リンク構造の表現隣接行列で表す A= 1 i ページ i から j にリンクがあれば aij=1 j

24 小規模な例 TO A= F R O M

25 推移確率行列推移確率行列 M FROM T A T = O M = 1 1 1/5 1/5 1/5 1/5 1/5 1 1/2 1/2 1/3 1/3 1/3 1/4 1/4 1/4 1/4 1/2 1/2 1 和が 1

26 PageRank の計算重要度の初期値を定める推移確率行列に従って重要度を伝播収束した結果をPageRankとする

27 PageRank の計算収束したときのPageRankをR( ベクトル ) とすると R cmr これは良く見ると MR R において λ=1/c としたもの

28 PageRank の計算要するに M の固有値と固有ベクトルを求めればよい R は絶対値最大の固有値に対する固有ベクトル ( 優固有ベクトル )

29 小規模な例に対する PageRank R=

30 現実の問題への適用 1. 数学用語 2. 現実世界との相違 3. 数値計算の方法

31 数学用語 (1) PageRank はマルコフ過程と関連している PageRank が表す量ランダムにリンクを辿って動くユーザが一定の時間のうちにそれぞれのページを訪問する定常分布ただし推移確率行列が既約であることが条件

32 数学用語 (2) 再帰状態 i から出発していつかは i に戻る確率が 1 のとき状態 i は再帰的という強連結任意の頂点から出発して他の任意の頂点へ到達できること

33 数学用語 (3) 再帰類リンクをたどっていける範囲再帰類既約ただ一つの再帰類しかできないこと強連結なら既約非再帰類

34 現実世界との相違 (1): 問題点理論では既約 ( 強連結 ) を仮定実際にはこの仮定は成り立たないリンクが出ていないページリンクされていないページ推移確率行列が既約でないとどうなるか優固有ベクトルが複数存在 PageRankが一意に定まらない

35 現実世界との相違 (2): 解決策推移確率行列を既約にする M ' M (1 ) 1 N.85 意味すべての要素が 1/N である N 次正方行列ユーザは時々 ( 確率 1-μ で ) 全く無関係なページにジャンプする

36 数値計算の方法大規模疎行列の計算メモリの問題は出てこない優固有ベクトルの計算固有値をすべて求めるのは計算量が多いべき乗法で求める

37 PageRank の使い方 PageRank の値検索質問 ( 入力されるキーワード ) に依存しない検索質問に対する回答 PageRank でランキングされたページの中から類似ページを探し出す処理が必要

38 試してみようページランクが分かるページページランクの計算 calculator.php nk.asp など

39 レポート課題 PageRank を調べてみよ pagerank を調べることができるサイトがあるそれを使っていくつかサイトのランクを調べる妥当性を論じる適当に設定した小規模なグラフに対して PageRank を求めてみよグラフの構造と値を見比べて考察妥当な値かどうか

Microsoft PowerPoint _3a-SEO.pptx

Microsoft PowerPoint _3a-SEO.pptx 3.Web の使いやすさ検索エンジン最適化 Web アクセシビリティ 1 検索エンジンのシェア 2018 年 5 月現在の世界シェア (%) モバイルにはタブレット端末も含むデスクトップモバイル Google 70.0 81.3 Baidu ( 百度 ) 17.2 12.7 Bing ( マイクロソフト ) 7.6 0.8 Yahoo! 3.6 0.8 その他 1.6 4.4 出典: http://netmarketshare.com/