データベースと情報検索 情報検索 ( 5 ) 検索エンジンの仕組み 教員 岩村 雅一. 日程(情報検索:担当 岩村)  12/9 検索エンジンを使ってみる  12/16 メディア検索を使ってみる  12/25 ウェブアプリケーションを 使ってみる  1/9 検索エンジンを用いた演習  1/20.

Slides:



Advertisements
Similar presentations
北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・2年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー.
Advertisements

データモデリング Web ページの検索とランキン グ Google, Yahoo はこんなことをして いる.
データベースと情報検索 情報検索(2) メディア検索エンジンを使っ てみる 岩村 雅一. 日程(情報検索:担当 岩村)  12/9 検索エンジンを使ってみる  12/16 メディア検索を使ってみる  12/25 ウェブアプリケーションを 使ってみる  1/9 検索エンジンを用いた演習  1/20.
11 月 17 日 インターネット検索の基礎 インターネット検索 最近の話題 宿題披露 興味を持っているものを検索してみ よう どんな時にインターネット検索するか 宿題 授業資料
データベースと情報検索 情報検索(1) 検索エンジンを使ってみる 工学部担当 教員 岩村 雅一. 日程(情報検索:担当 岩村)  12/9 検索エンジンを使ってみる  12/16 メディア検索を使ってみる  12/25 ウェブアプリケーションを 使ってみる  1/9 検索エンジンを用いた演習.
人間とコンピュータ インターネット検索 11 月 10 日, 11 月 17 日, 11 月 24 日.
Copyright © Kazuhito HAMANO 2007 all Rights Reserved. 1 情報基礎( Week4 ) ≪ WWW で展開される新しい技術≫ 非常勤講師 濱野和人 2007/5/8 火曜 1,2,3 限
情報基礎 A 第 4 週 データベースと表計算 情報基礎 A 第 4 週 データベースと表計算 1 徳山 豪 東北大学情報科学研究科 システム情報科学専攻 情報システム評価学分野.
データベースと情報検索 情報検索(3) ウェブアプリケーションを 使ってみる 教員 岩村 雅一. 日程(情報検索:担当 岩村)  12/9 検索エンジンを使ってみる  12/16 メディア検索を使ってみる  12/25 ウェブアプリケーションを 使ってみる  1/9 検索エンジンを用いた演習.
北海道大学理学部地球科学科地球物理学 惑星物理学研究室 B4 加藤 学
ウェブの時空間解析技術 東京大学生産技術研究所 戦略情報融合国際研究センター 成果概要 ウェブアーカイブ ウェブ空間解析 ウェブ時系列解析
コンピュータプラクティス I 再現性 水野嘉明
MS-Word ⇒ XML 2001/10 マウスをクリックしてください。(カーソルはどこにあっても結構です。)次ページが表示されます。
セキュアネットワーク符号化構成法に関する研究
シミュレーション論Ⅰ 第6回 待ち行列のシミュレーション.
Excelによる統計分析のための ワークシート開発
情報処理基礎 2006年 6月 1日.
秘密のリンク構造を持つグラフのリンク解析
座 席 表(CP教室) 出席番号.
分散コンピューティング環境上の Webリンク収集システムの実装
ISDASインターネット分散観測: ワームの平均寿命はいくらか?
数理科学コース・ 倉田 和浩 2007/11/3 大学祭オープンラボ
第1回 ガイダンス 工学部担当 教員 吉岡 理文 ・ 岩村 雅一
参照共起分析の Webディレクトリへの適用
前回までの配布資料(Webにないもの):教室の後方
夢見る図書館情報システム The Cards Challenge !
テキストマイニング, データマイニングと 社会活動のトレース
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
検索エンジンに関して The Anatomy of a Large-Scale Hypertextual Web Search Engine
早稲田大学 理工学術院 基幹理工学部 情報理工学科 後藤滋樹
リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究
卒業論文 最終発表 WWW情報検索 ナビゲーションシステムの設計と実装
PageRankの仕組 林晋.
9 Microsoft Word(1).
メディア学部 2011年9月29日(木) 担当教員:亀田弘之
情報検索演習 第8回 パソコンを起動しておくこと 前から4列目までに着席すること 2005年11月30日 後期 水曜5限
マイクロソフト Access での SQL 演習 第1回 SQL問い合わせ(クエリ)
基礎プログラミング演習 第1回.
Java ソフトウェア部品検索システム SPARS-J のための リポジトリ自動更新機能の実現
2003年度 データベース論 安藤 友晴.
Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列(推移行列、遷移行列) 固有値と固有ベクトル W大学
データモデリング Webページの検索とランキング
事務所における情報化の問題点 データが所内で共有されていない、各課ごとに個別に利用されている
環境リスクマネジメントに関する 検索システム
WWW上の効率的な ハブ探索法の提案と実装
プリムのアルゴリズム 重み付きグラフG=(V,E)の任意の点集合 U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝lを含むような最小木が存在する。
ネットショップデザイン入門Ⅰ・ⅡSEO 2013/12/18 Webデザイン入門 SEOの基本.
The Web as a graph 末次 寛之 清水 伸明.
情報検索(6) メディア検索の仕組み 教員 岩村 雅一
インターネット利用法実習 経営工学基礎演習a(第3週).
情報処理概論Ⅰ 2007 第5回 2019/4/7 情報処理概論Ⅰ 第5回.
類似度を用いた WWW のリンク構造の解析 谷 研究室    栗原 伸行.
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
エピソード記憶に訴えるBookmarkless Bookmarkの実現
2003年度 図書館活用論 Ⅰ 第9講 検索エンジンの仕組みと活用 (明治大学図書館庶務課システム担当 中林)
テキストマイニング, データマイニングと 社会活動のトレース
様々な情報源(4章).
実空間における関連本アウェアネス 支援システム
第10回:Microsoft Excel (2/2)
問題作成、解説担当:中島 副担当:坪坂、松本
基礎技術ー3 : Webページの標準規格について
構造的類似性を持つ半構造化文書における頻度分析
メディア学部 2010年9月30日(木) 担当教員:亀田弘之
数理統計学 西 山.
保守請負時を対象とした 労力見積のためのメトリクスの提案
自然言語処理2015 Natural Language Processing 2015
第2章 統計データの記述 データについての理解 度数分布表の作成.
情報検索(4) 検索エンジンを用いた演習 教員 岩村 雅一
自然言語処理2016 Natural Language Processing 2016
Presentation transcript:

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

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

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

Web のサイズ

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

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

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

検索キーワード数 1.2 語 : 30.09% 2. 1語 : 26.83% 3. 3語 : 16.60% 4. 4語 : 14.83% 5. 5語 : 6.76% 6. 6語 : 2.81% 7. 7語 : 1.13%  OneStat.com 調べ(2004年7月)

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

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

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

PC 台数の推移

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

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

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

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

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

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

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

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

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

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

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

小規模な例 A= FROMFROM TO

推移確率行列  推移確率行列M A = T M = 0 1/5 0 1/ /2 0 1/3 0 1/3 0 1/4 0 1/4 0 1/4 0 1/2 0 1/ 和が1 FROM TOTO

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

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

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

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

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

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

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

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

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

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

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

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

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

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