WWWとブラウザの過去，現在，未来

Size: px

Start display at page:

Download "WWWとブラウザの過去，現在，未来"

あきみやまのかみしゃ
5 years ago
Views:

1 検索エンジンの仕組み

2 検索結果の表示順位 Google の人気の秘密 ( PageRank について PageRank はウェブの膨大なリンク構造を用いてその特性を生かしますページ A からページ B へのリンクをページ A によるページ B への支持投票とみなし Google はこの投票数によりそのページの重要性を判断しますしかし Google は単に票数つまりリンク数を見るだけではなく票を投じたページについても分析します重要度の高いページによって投じられた票はより高く評価されてそれを受け取ったページを重要なものにしていくのですこうした分析によって高評価を得た重要なページには高い PageRank ( ページ順位 ) が与えられ検索結果内の順位も高くなります PageRank は Google におけるページの重要度を示す総合的な指標であり各検索に影響されるものではありませんむしろ PageRank は複雑なアルゴリズムにしたがったリンク構造の分析にもとづく各ウェブページそのものの特性ですもちろん重要度が高いページでも検索語句に関連がなければ意味がありませんそのために Google は洗練されたテキストマッチ技術を使って検索に対し重要でなおかつ的確なページを探し出します

3 PageRank 多くの良質なページからリンクされているページはやはり良質なページである

4 A B 1. 被リンク数 ( 単純人気度 ) 1 つの Web ページからリンクされている A よりも 2 つの Web ページからリンクされている B の方が PageRank 値が高い SPAM ページ内輪推薦に対応できない C D A B 2. リンク元の被リンク数 1 つの Web ページからリンクされている C より 2 つの Web ページからリンクされている D の方が信用できるよって C からリンクされている A よりも D からリンクされている B の方が PageRank 値は高い A B 3. リンク元ページでのリンク数 A のリンク元はリンクが 2 つあるが B のリンク元はリンクが一つでありより厳選された推薦であるので A より B の方が PageRank 値は高い

5 PageRank 値の計算方法 1. リンク構造を隣接行列で表現する aij = 1 if ( ページ i からページ j へのリンクがある場合 ) 0 if ( ページ i からページ j へのリンクがない場合 ) 2. PageRank はどれだけリンクしているかではなくどれだけリンクされているかを重視しているので転置行列を作成し ( 行と列を入れ替えること ) さらにそれぞれの列 (column) ベクトルの総和が 1 ( 全確率 ) になるようにそれぞれのリンク数 ( すなわち非零要素数 ) で割る ( 推移確率行列 ) 3. 推移確率行列の最大固有値に属する固有ベクトルを求めこれが PageRank 値になる

6 PageRank の計算例題左図グラフのような Web があるとする. 問 1 どの Web サイトが評判が高いかを直感で示せ. 問 2 下記の手順で PageRank 値を求め, 問 1 と比較せよ 1. 隣接行列 2. 転置行列 3. 推移確率行列 4. 方程式を立てる 5. 固有値, 固有ベクトル, 正規化 (= ページランク )

7 PageRank の計算過程 (1) 1. 隣接行列 2. 転置行列 X = X t = A がどのノードと連結しているか? A がどのノードから連結されているか 3. 推移確率行列 M = /3 0 1/ /3 1/2 0 1/2 0 1/ /2 1/2 1/2 0 A ノードから他ノードへ推移する確率を求めるために, 列単位で正規化を行う

8 PageRank の計算過程 (2) 4. 推移確率行列の最大固有ベクトルを R とすると MP=λR /3 0 1/ /3 1/2 0 1/2 0 1/ /2 1/2 1/2 0 r A r B r C r D r E = λ r A r B r C r D r E グラフが強連結 ( グラフ上の任意の 2 点間に有向路が存在する ) の時は,λ=1 となるので, MP=R を解けばよい r A r B r C r D r E = 1 7/9 8/9 1/3 1 5.R を正規化する ( 要素の総和 (=4) で各要素を割る ) R= (1/4, 7/36, 2/9, 1/12, 1/4)

9 PageRank の計算例題 1 ( 各自やってみること )

10 検索エンジンのシステム構成

11 キーワード検索と全文検索キーワード検索 : Web ページに登録されたキーワードが検索対象検索が高速検索結果にゴミが少ないキーワード登録が手間検索漏れが多い ( デジカメデジタルカメラ ) 全文検索 : Web ページ内のすべての文字が検索対象ほとんどのサーチエンジンが採用逐次検索方式 :Web ページの先頭から順番に文字列照合インデックス方式 : 事前に Web ページを分析し索引情報 ( 語句 Web ページ ) を作成して利用する

12 インデックス検索方式に基づく全文検索 ( フルテキストサーチ ) Web ページ群データ収集部 ( ロボット, スパイダー, クローラ ) Web データを収集文書フィルタ部文字コードの統一, タグの除去インデックスファイルインデクサ部検索サーバー部検索語句結果表示フロントエンド部ユーザインデックス ( 索引 ) の作成検索語句とインデックスファイルとの照合

13 12000 台 (2004?) のサーチエンジンサーバー 80CPU 150 ラック空調 PC ラック前面に 20 台裏面に 20 台 2x44port Fast Ethernet Switch PC ラック前面に 20 台裏面に 20 台 19inch ラック (210cmH x 60cmW x 75cmD) に 1U の PC80 台を設置 (Rackable Systems の技術 : ラックの全面と背面の両方に奥行半分の PC を設置 ) 2 Fast Ethernet Switch / 筐体 4 筐体を GigaEther にて接続し 1 クラスタを構成

14 Aug-98 Feb-99 Aug-99 Feb-00 Aug-00 Feb-01 Aug-01 Feb-02 サーバー台数と収集された Web ページ数の推移 P C 台数台 Biglobe と提携 Yahoo! と提携平均 33 台 / 日で増加と提携台 20 億 18 億 16 億 14 億 12 億 10 億 8 億 6 億収集 W e b ページ数億 Netscape と提携 2 億 0

15 検索エンジンによる Web ページの評価方法の変化

16 On-page factors + Off-page factors Web ページの評価 ( 検索順位をあげる ) On-page factors( ページ内要因 ) + Off-page factors( ページ外要因 ) ページ内要因 :Web ページ内の情報 ( キーワード出現回数, キーワードの配置,<title> タグ, <h1>-<h6> タグ, サイト内リンクなど ) を評価ページ外要因 : リンク分析 ( 数, 質, 関連性, 時間, 信頼性 ) + アンカーテキストによりページを評価

17 On-page factors ( テキスト要素の最適化 1) テキストの論理構造, コンテンツを明確化クローラに好まれる Web サイトの制作本来の HTML の利用 1 スタイルシート (CSS) や JavaScript は外部ファイルにする ( 論理構造と視覚情報は分離する ) 2 キーワード抽出箇所 : タイトル, 見出し, 第 1 段落, 最終段落, 各段落の最初と最後 (<meta> タグは,90 年代, 評価対象であったが, スパムに多用されたため, 現在は無視される ) 3 <title> タグ : ページ遷移に沿ってキーワードを具体化 ( 海外旅行欧州旅行パリ 3 日間 ). 全ページに同じキーワードは駄目 ( 共通キーワードは可 ) 偏ったキーワード (ec サイトで, 商品名 or ショップ名だけをキーワードとする ) は駄目. キーワードの個数は 1-2 個 ( ネット利用者調査より ) 不必要に類似キーワードを繰り返さないスパム行為

18 テキスト要素の最適化 2 4 見出しタグ <hx>: 文章論理構造 (h1: 標題,h2: 部,h3: 章,h4: 節,h5: 項,h6: 小見出し ). クローラは <h1> 重視 <h1> を多用するとスパムと判断される 5 画像タグ <img>: クローラは画像理解できないので, alt 属性に画像を説明する適切なキーワードを記載 ( 例 ) グーグルバナーの表示 <a href=" <img src = border="0" alt="google" align="middle" width="128" height="53"> </a>

19 Off-page factors ( リンクの評価 1: 重要度 ) リンク分析 : 数, 質, 関連性, 信頼性, 時間の総合評価 ( ページランクアルゴリズムはリンク分析の一部にしかすぎない ) ページランクアルゴリズム : 被リンクの数と質の評価 +アンカーテキスト (10 年前. miserable failure) 重要度に課題 :Web 全体からみた重要度であって, 特定話題 ( 検索クエリー ) からみた重要度ではない. Bホテル信頼度に課題 : スパムに弱い. 関連性 :relevance(a,b)>relevance(a,c) (Teoma(Subject Specific Popularity), WiseNut(Context Sensitive Link Analysis) 等の Google キラーと呼ばれた新興検索エンジンが提唱 ( その後衰退 ).Google は関連性を後日導入. 新重要度 = 数質関連性 C コンビニ A 旅行

20 リンクの評価 2: 信頼性重要度だけでは, 大量の Web サイトを巧妙に開設し, そこからリンクを張りページランクをあげる事は依然可能. 信頼性 : 友達の友達は信用. その友達の友達は? その友達の友達は?? という考え方. 審査により予め信頼できる Web サイト群を決め, そこから信頼値を割り当てる. 重要度スパム? 優良? 新規? マニア? 信頼度 Yahoo 研究者の TrustRank: Google は 2005 年に TrustRank を商標化したが現在は使用中止?( 別のアルゴリズム採用?) 時間 : 開設期間が長い程, 信頼性は高い. 急激なリンク数の増加は不自然であり信頼性を低くする.

21 検索連動型広告

22 Web 上の広告バナー広告元来垂れ幕の意帯状の広告画像が宣伝用の垂れ幕を連想キーワード広告検索キーワードに関連する Web サイトを提示クリック回数で広告効果が計れる

23 キーワード広告 (1) 1999 年 Altavista によって試みられる広告枠をオークションで売りクリックされた分だけ広告料を課金ユーザのニーズに合った広告が期待できる現在は数十億ドル規模のビジネスに

24 キーワード広告 (2) オーバーチュアスポンサードサーチ Google アドワーズキーワードへの入札 ( クリック単価 ) W 杯 51~ 9 ワールドカップ 71~ 9 就職活動 425~ 35 キャッシング 2146~ 35 融資 1282~ 35 慶応 32~ 9

25 キーワード広告 (3) オーバーチュア : 入札金額で表示順位が決まる順位付け : クリック単価上限の高い順実際のクリック単価 : 一つ下位のクリック単価 +1 円 Google: 広告のクリック率も加味した表示順位順位付け : クリック単価上限クリック率の高い順実際のクリック単価 : 一つ下位のクリック単価上限クリック率自広告のクリック率 +1 円

26 GOOGLE アドワーズ広告 1 ビジネスモデル : 他のサイトが検索サイトから総合サイトにモデルチェンジする中 GOOGLE は検索一筋売上高の 99%= インターネット広告バナー広告検索連動型広告 = アドワーズ広告 ( 売上高 50%)+ アドセンス広告 ( 売上高 49%) アドワーズ (Adwords:Ad= 広告 +words= キーワード ) 広告検索キーワードに関連する広告を検索結果表示ページの上側と右側にテキスト表示 ( 上 1 枠 + 右 8 枠 = 最大 9 枠それ以降の広告は次ページ以降 ). ( ユーザへの配慮 ) テキスト表示 : 検索速度が遅くなってはいけない広告表示場所は上側と右側に定め検索結果閲覧を邪魔しないポップアップ広告はユーザが不快になる恐れがあるので禁止クリック単価 (CPC: cost per click) クリック率 (CTR: click through rate) で表示順位決定 CPC だけで決める広告主主導になりすぎるためさらに CTR が 0.5% を下回ると広告が抑制され, そのまま改善しない場合はステータスが無効になり取り下げられてしまいます ( 広告主への配慮 ) クリック課金型広告 (PPC (pay per click) 広告 ) クリックされた場合のみ広告料金が発生クリック単価 (7 円 ~1 万円 ) を設定しクリック数に応じて支払う 1 日当たりの上限金額設定可能

27 GOOGLE アドワーズ広告 2 CPC は常に変動クリック単価 (CPC)= 次ランクの (CPC 上限 CTR) 自分の CTR + 1 次ランクと同等になるための CPC+1 円次ランクに勝つための最低価格負けた時の CPC は最低価格 7 円 ( 例題 ) ワイン会社 A 社 CPC 上限 200 円 B 社 CPC 上限 100 円問 1:(A 社 CTR,B 社 CTR)=(3%,3%) の時の A 社と B 社の CPC は? 問 2:(3%,5%) の時の A 社と B 社の CPC は? 問 3:(3%,8%) の時の A 社と B 社の CPC は?

28 例題回答表示順位 : 評価値 = クリック単価クリック率問 1 (A 社 CTR,B 社 CTR)=(3%,3%) 各社最大評価値比較 A 社 200 X 3% > B 社 100 X 3% A 社が1 位,B 社が2 位 1 位 A 社 (100x3%[B 社のCTR]) 3%[A 社のCTR]+1=100+1=101 円 2 位 B 社 7 円 ( 最低クリック単価 ) 問 2(A 社 CTR,B 社 CTR)=(3%,5%) 各社最大評価値比較 A 社 200 X 3% > B 社 100 X 5% A 社が1 位,B 社が2 位 1 位 A 社 (100x5%[B 社のCTR]) 3%[A 社のCTR]+1=167+1=168 円 2 位 B 社 7 円 ( 最低クリック単価 ) 問 3(A 社 CTR,B 社 CTR)=(3%,8%) 各社最大評価値比較 A 社 200 X 3% < B 社 100 X 8% B 社が1 位,A 社が2 位 1 位 B 社 (200x3%[A 社のCTR]) 8%[B 社のCTR]+1=75+1=76 円 2 位 A 社 7 円 ( 最低クリック単価 )

29 アドワーズ広告練習問題 1 1. 掲載順位, 各社の CPC を求めよ. 2.A 社が一位になるには,CPC をいくらに設定すべきか? CPC( 円 ) CTR(%) A 社 B 社 C 社 D 社 E 社

WWWとブラウザの過去，現在，未来

WWWとブラウザの過去，現在，未来検索エンジンの仕組み検索結果の表示順位 Google の人気の秘密 (http://www.google.co.jp/intl/ja/why_use.html) PageRank について PageRank はウェブの膨大なリンク構造を用いてその特性を生かしますページ A からページ B へのリンクをページ A によるページ B への支持投票とみなし Google はこの投票数によりそのページの重要性を判断します

WWWとブラウザの 過去，現在，未来

WWWとブラウザの過去，現在，未来