検索エンジンの仕組み

(1)

検索エンジンの仕組み

(2)

検索結果の表示順位

「

Google

の人気の秘密

(http://www.google.co.jp/intl/ja/why_use.html)

」

• PageRank

について

PageRank

は、ウェブの膨大なリンク構造を用いて、その特性を生かしま

す。ページＡからページＢへのリンクをページ

A

によるページ

B

への支持投票とみなし、

Google

はこの投票数によりそのページの重要性を判断します。しかし

Google

は単に票数、つまりリンク数を見るだけではなく、票を投じたページについても分析します。「重要度」の高いページによって投じられた票はより高く評価されて、それを受け取ったページを「重要なもの」にしていくのです。

こうした分析によって高評価を得た重要なページには高い

PageRank

（ページ順位）が与えられ、検索結果内の順位も高くなります。

PageRank

は

Google

におけるページの重要度を示す総合的な指標であ

り、各検索に影響されるものではありません。むしろ、

PageRank

は複雑

なアルゴリズムにしたがったリンク構造の分析にもとづく、各ウェブページ

そのものの特性です。もちろん、重要度が高いページでも検索語句に関

連がなければ意味がありません。そのために

Google

は洗練されたテキ

ストマッチ技術を使って、検索に対し重要でなおかつ、的確なページを探

し出します。

(3)

PageRank

多くの良質なページからリンクされている

ページは、やはり良質なページである

(4)

B

A

１．被リンク数

(

単純人気度）

１つの

Web

ページからリンクされている

A

よりも、２つの

Web

ページからリンクされているBの方がPageRank値が高い

SPAM

ページ、内輪推薦に対応できない

D C

B A

２．リンク元の被リンク数

１つの

Web

ページからリンクされている

C

より２つの

Web

ページからリンクされているDの方が信用できる。よって、Cからリンクされている

A

よりも、

D

からリンクされている

B

の方が

PageRank

値は高い

B

A

３．リンク元ページでのリンク数

A

のリンク元はリンクが２つあるが、

B

のリンク元はリンクが一つであり、より厳選された推薦であるので、

AよりBの方がPageRank値は高い

(5)

PageRank

値の計算方法

１．リンク構造を隣接行列で表現する。

aij =

1 if (

ページ

i

からページ

j

へのリンクが「ある」場合

) 0 if (

ページ

i

からページ

j

へのリンクが「ない」場合

)

２．

PageRank

は「どれだけリンクしているか」ではなく「どれだ

けリンクされているか」を重視しているので、転置行列を作成し

(

行と列を入れ替えること

)

、さらにそれぞれの列

(column)

ベクトルの総和が

1 (

全確率

)

になるようにそれぞれのリンク数

(

すなわち、非零要素数

)

で割る（推移確率行列）。

３．推移確率行列の最大固有値に属する固有ベクトルを求め、

これが

PageRank

値になる。

(6)

PageRank

の計算例題

左図グラフのような

Web

があるとする．

問１どの

Web

サイトが評判が高いかを直感で示せ．

問２下記の手順で

PageRank

値を求め，問１と比較せよ

１．隣接行列２．転置行列３．推移確率行列４．方程式を立てる５．固有値，

固有ベクトル，

正規化（＝ページランク）

(7)

１．隣接行列

X =

0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0

２．転置行列

X ^t=

0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0

A

がどのノードと連結しているか？

Aがどのノードから連結されているか

３．推移確率行列

M =

0 0 0 0 1 1/3 0 1/2 0 0 1/3 1/2 0 1/2 0 1/3 0 0 0 0 0 1/2 1/2 1/2 0

A

ノードから他ノードへ推移する確率を求めるために，列単位で正規化を行う

PageRank

の計算過程（１）

(8)

４．推移確率行列の最大固有ベクトルを

R

とすると

MP=λR

PageRank

の計算過程（

2

）

0 0 0 0 1 1/3 0 1/2 0 0 1/3 1/2 0 1/2 0 1/3 0 0 0 0 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

点間に有向路が存在する）

の時は，

λ

＝１となるので，

MP=R

を解けばよい

r_A r_B r_C r_D r_E

1 7/9 8/9 1/3 1

=

５．

R

を正規化する

(要素の総和（＝４）で各要素を割る）

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)

• 19inch

ラック（

210cmH x 60cmW x 75cmD

）に

1U

の

PC80

台を設置。

(Rackable Systems

の技術：ラックの全面と背面の両方に奥行半分の

PC

を設置

)

• 2 Fast Ethernet Switch /

筐体

• 4

筐体を

GigaEther

にて接続し１クラスタを構成。

空調

2x44port Fast Ethernet Switch

PC

ラック前面に２０台裏面に２０台

PC

ラック前面に２０台裏面に２０台

空調

2x44port Fast Ethernet Switch

PC

ラック前面に２０台裏面に２０台

PC

ラック前面に２０台裏面に２０台

１２０００台

(2004?)

のサーチエンジンサーバー

８０

CPU

×１５０ラック

(14)

サーバー台数と収集された

Web

ページ数の推移

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Aug-98 Feb-99 Aug-99 Feb-00 Aug-00 Feb-01 Aug-01 Feb-02

2001.3 8000台 2000.12 Biglobe

　　　　　と提携

1998.8 ３０台

1999.6 Netscapeと提携 2000.6 Yahoo!と提携

平均３３台/日で増加

２億４億６億８億１０億１２億

１４億

収

集 W

e b ページ数 P

C 台数

１６億

１８億

２０億

2001.4 @Niftyと提携

(15)

検索エンジンによる

Web

ページの評価方法の変化

(16)

On-page factors

＋

Off-page factors

• Web

ページの評価（検索順位をあげる）

→

On-page factors

（ページ内要因）

＋

Off-page factors

（ページ外要因）

•

ページ内要因：

Web

ページ内の情報（キーワード出現回数，

キーワードの配置，

<title>

タグ，

タグ，

サイト内リンクなど）を評価

•

ページ外要因：リンク分析（数，質，関連性，時間，信頼性）

＋アンカーテキストによりページを評価

(17)

On-page factors

（テキスト要素の最適化

1

）

テキストの論理構造，コンテンツを明確化

→

クローラに好まれる

Web

サイトの制作

→

本来の

HTML

の利用

①スタイルシート

(CSS)

や

JavaScript

は外部ファイルにする

（論理構造と視覚情報は分離する）

②キーワード抽出箇所：タイトル，見出し，第

1

段落，最終段落，

各段落の最初と最後

(<meta>

タグは，

90

年代，評価対象であったが，スパムに多用されたため，現在は無視される）

③

<title>

タグ：ページ遷移に沿ってキーワードを具体化

（海外旅行

→

欧州旅行

→

パリ

3

日間）．

全ページに同じキーワードは駄目（共通キーワードは可）

偏ったキーワード（

ec

サイトで，商品名

or

ショップ名だけをキーワードとする）は駄目．

キーワードの個数は１－２個（ネット利用者調査より）

不必要に類似キーワードを繰り返さない

→

スパム行為

(18)

テキスト要素の最適化

2

④見出しタグ

<hx>

：文章論理構造

（

h1:

標題，

h2:

部，

h3:

章，

h4:

節，

h5:

項，

h6:

小見出し）．

クローラは

<h1>

重視

→<h1>

を多用するとスパムと判断される

⑤画像タグ

<img>

：クローラは画像理解できないので，

alt

属性に画像を説明する適切なキーワードを記載

（例）グーグルバナーの表示

<img src = http://www.google.com/logos/Logo_40wht.gif

border="0" alt="Google" align="middle" width="128" height="53">

</a>

(19)

Off-page factors

（リンクの評価１：重要度）

•

リンク分析：数，質，関連性，信頼性，時間の総合評価

（ページランクアルゴリズムはリンク分析の一部にしかすぎない）

•

ページランクアルゴリズム：被リンクの数と質の評価

＋アンカーテキスト（

10

年前

. miserable failure

）

重要度に課題：

Web

全体からみた重要度であって，

特定話題（検索クエリー）からみた重要度ではない．

信頼度に課題：スパムに弱い．

•

＞

relevance(A,C)

（

Teoma(Subject Specific Popularity), WiseNut(Context Sensitive

Link Analysis)

等の

Google

キラーと呼ばれた新興検索エンジンが提唱

（その後衰退）．

Google

は関連性を後日導入．

http://internet.watch.impress.co.jp/www/article/2002/0403/teoma.htm

※新重要度＝数×質×関連性

Cコンビニ

Bホテル A旅行

(20)

リンクの評価２：信頼性

•

重要度だけでは，大量の

Web

サイトを巧妙に開設し，そこからリンクを張りページランクをあげる事は依然可能．

•

信頼性：友達の友達は信用．その友達の友達は？その友達の友達は？？という考え方．審査により予め信頼できる

Web

サイト群を決め，そこから信頼値を割り当てる．

重要度

信頼度

•

時間：開設期間が長い程，信頼性は高い．

急激なリンク数の増加は不自然であり信頼性を低くする

．

優良？

スパム？

新規？マニア？

Yahoo研究者のTrustRank:

http://www.vldb.org/conf/2004/RS15P3.PDF Googleは2005年にTrustRankを商標化したが、

現在は使用中止？（別のアルゴリズム採用？）

(21)

検索連動型広告

(22)

Web

上の広告

•

バナー広告

元来「垂れ幕」の意

帯状の広告画像が宣伝用の垂れ幕を連想

•

キーワード広告

検索キーワードに関連する

Web

サイトを提示

クリック回数で広告効果が計れる

(23)

キーワード広告

(1)

• 1999

年

Altavista

によって試みられる

•

広告枠をオークションで売り、クリックされた分だけ広告料を課金

•

ユーザのニーズに合った広告が期待できる

•

現在は数十億ドル規模のビジネスに

(24)

キーワード広告

(2)

•

オーバーチュアスポンサードサーチ

http://www.jp.overture.com/

• Google

アドワーズ

https://adwords.google.co.jp/select/

•

キーワードへの入札

(

クリック単価

)

–

「

W

杯」

¥51

～

¥9

「ワールドカップ」

¥71

～

¥9 –

「就職活動」

¥425

～

¥35

–

「キャッシング」

¥2146

～

¥35

「融資」

¥1282

～

¥35 –

「慶応」

¥32

～

¥9

(25)

キーワード広告

(3)

•

オーバーチュア：入札金額で表示順位が決まる

–

順位付け：クリック単価上限の高い順

–

実際のクリック単価：一つ下位のクリック単価＋１円

• Google

：広告のクリック率も加味した表示順位

–

順位付け：クリック単価上限×クリック率の高い順

–

実際のクリック単価：一つ下位のクリック単価上限×クリッ

ク率÷自広告のクリック率＋１円

(26)

GOOGLE

アドワーズ広告１

•

ビジネスモデル：他のサイトが検索サイトから総合サイトにモデルチェンジする中、

GOOGLE

は検索一筋。

売上高の９９％＝インターネット広告

•

バナー広告→検索連動型広告＝アドワーズ広告（売上高５０％）＋アドセンス広告（売上高４９％）

アドワーズ(Adwords:Ad＝広告＋words＝キーワード)広告

検索キーワードに関連する広告を検索結果表示ページの上側と右側に

テキスト表示（上１枠＋右８枠＝最大９枠。それ以降の広告は次ページ以降）．

（ユーザへの配慮）

・テキスト表示：検索速度が遅くなってはいけない

・広告表示場所は上側と右側に定め、検索結果閲覧を邪魔しない

・ポップアップ広告はユーザが不快になる恐れがあるので禁止。

・クリック単価(CPC: cost per click)×クリック率(CTR: click through rate) で表示順位決定。CPCだけで決める広告主主導になりすぎるため。

・さらにCTRが0.5%を下回ると広告が抑制され，そのまま改善しない場合はステータスが

「無効」になり取り下げられてしまいます。

（広告主への配慮）

クリック課金型広告（

PPC (pay per click)

広告）

→

クリックされた場合のみ広告料金が発生

クリック単価（７円～１万円）を設定しクリック数に応じて支払う

１日当たりの上限金額設定可能。

(27)

CPC

は常に変動

クリック単価（

CPC)

＝

次ランクの（

CPC

上限×

CTR)

÷自分の

CTR

＋１

→

次ランクと同等になるための

CPC

＋１円

→

次ランクに勝つための最低価格負けた時の

CPC

は最低価格７円

（例題）

ワイン会社

A

社

CPC

上限２００円

B

社

CPC

上限１００円

問１：（

A

社

CTR

，

B

社

CTR)

＝（３％，３％）の時の

A

社と

B

社の

CPC

は？

問２：（３％，５％）の時の

A

社と

B

社の

CPC

は？

問３：（３％，８％）の時のA社とB社のCPCは？

GOOGLE

アドワーズ広告２

(28)

例題回答

表示順位：評価値＝クリック単価×クリック率問１（

A

社

CTR

，

B

社

CTR)

＝（３％，３％）

各社最大評価値比較

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

円（最低クリック単価）

問２（

A

社

CTR

，

B

社

CTR)

＝（３％，

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円（最低クリック単価）

問３（

A

社

CTR

，

B

社

CTR)

＝（３％，

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)

アドワーズ広告練習問題１

CPC

（円）

CTR(

％）

A

社

300 2.0

B

社

210 5.0

C

社

200 2.0

D

社

200 4.0

E

社

190 4.0

１．掲載順位，各社の

CPC

を求めよ．

２．

A

社が一位になるには，

CPC

検索エンジンの仕組み

検索エンジンの仕組み

検索結果の表示順位

「

の人気の秘密

」

について

は、ウェブの膨大なリンク構造を用いて、その特性を生かしま

す。ページＡからページＢへのリンクをページ

によるページ

への支持 投票とみなし、

はこの投票数によりそのページの重要性を判断し ます。しかし

こうした分析によって高評価を得た重要なページには高い

（ページ順位）が与えられ、検索結果内の順位も高くなります。

は

におけるページの重要度を示す総合的な指標であ

り、各検索に影響されるものではありません。むしろ、

は複雑

なアルゴリズムにしたがったリンク構造の分析にもとづく、各ウェブページ

そのものの特性です。 もちろん、重要度が高いページでも検索語句に関

連がなければ意味がありません。 そのために

は洗練されたテキ

ストマッチ技術を使って、検索に対し重要でなおかつ、的確なページを探

し出します。

多くの良質なページからリンクされている

ページは、やはり良質なページである

１．被リンク数

単純人気度）

１つの

ページからリンクされている

よりも、２つの

ページからリンクされて いるBの方がPageRank値が高い

ページ、内輪推薦に対応できない

２．リンク元の被リンク数

１つの

ページからリンクされている

より２つの

ページからリンクされて いるDの方が信用できる。よって、Cから リンクされている

よりも、

からリンクされ ている

の方が

値は高い

３．リンク元ページでのリンク数

のリンク元はリンクが２つあるが、

のリンク元は リンクが一つであり、より厳選された推薦であるので、

値の計算方法

１．リンク構造を隣接行列で表現する。

ページ

からページ

へのリンクが「ある」場合

ページ

からページ

へのリンクが「ない」場合

２．

は「どれだけリンクしているか」ではなく「どれだ

けリンクされているか」を重視しているので、 転置行列を作 成し

行と列を入れ替えること

、さらにそれぞれの列

ベクトルの総和が

全確率

になるようにそれぞれ のリンク数

すなわち、非零要素数

で割る（推移確率行列）。

３．推移確率行列の最大固有値に属する固有ベクトルを求め、

これが

値になる。

の計算例題

左図グラフのような

があるとする．

問１ どの

サイトが評判が高いか を直感で示せ．

問２ 下記の手順で

値を 求め，問１と比較せよ

１．隣接行列 ２．転置行列 ３．推移確率行列 ４．方程式を立てる ５．固有値，

固有ベクトル，

正規化（＝ページランク）

１．隣接行列

２．転置行列

がどのノードと連結しているか？

３．推移確率行列

への支持投票とみなし、

はこの投票数によりそのページの重要性を判断します。しかし

そのものの特性です。もちろん、重要度が高いページでも検索語句に関

連がなければ意味がありません。そのために

ページからリンクされているBの方がPageRank値が高い

ページからリンクされているDの方が信用できる。よって、Cからリンクされている

からリンクされている

のリンク元はリンクが一つであり、より厳選された推薦であるので、

けリンクされているか」を重視しているので、転置行列を作成し

になるようにそれぞれのリンク数

問１どの

サイトが評判が高いかを直感で示せ．

問２下記の手順で

値を求め，問１と比較せよ

１．隣接行列２．転置行列３．推移確率行列４．方程式を立てる５．固有値，

ノードから他ノードへ推移する確率を求めるために，列単位で正規化を行う

グラフが強連結（グラフ上の任意の

ページの先頭から順番に文字列照合インデックス方式：事前に

インデックス検索方式に基づく全文検索

検索語句結果表示

索引）の作成イン

デックスファイル

検索語句とインデックスファイルとの照合

の技術：ラックの全面と背面の両方に奥行半分の

にて接続し１クラスタを構成。

ラック前面に２０台裏面に２０台

ラック前面に２０台裏面に２０台

ラック前面に２０台裏面に２０台

ラック前面に２０台裏面に２０台