ポータルサイトと
検索エンジン
ポータルサイト
・ポータルサイト(Portal Site)
→最初にアクセスするWebページ。
・広告やEC取引仲介サービスにより収入を得る。
・検索エンジン、情報サービス、e-マーケットプレイス、
業界系などに分類されるが、近年、SNSの台頭がめざ
ましい。
・全世界ではGoogleがトップシェアをとるが、
国に依存して、ポータルサイトの状況はかなり異なる。
代表的な検索エンジンと
シェアの推移
2つの検索エンジン
• ディレクトリ型検索エンジン(Yahoo!) (人手で作成されたディレクトリ(カテゴリ)に沿って検索。ユー ザがWebサイトをYahoo!に登録,審査,承認されればディレ クトリ登録(2-3週間)。情報が厳選されているので検索結果 の質は高い。でも即時性に劣る。 • ロボット型全文検索エンジン(Google)Web自動巡回ソフト(robot, crawler, spider)がWebデータを 収集し(2004.12で80億ページ)、インデクス(索引付き)DB を作成し検索に利用する。即時性があるが検索結果が膨大。
テキスト一致度やPageRank(良いページからリンクされてい
るページはやはり良いページ)などによりWebページをランキ ング。
1996年 Yahoo!JAPAN
・インターネットユーザーが まだまだ珍しかった時代 ・1996年4月 Yahoo! JAPAN スタート ・検索機能のみ ・38万PV/Day(1996年5月)1998年 Yahoo!JAPAN
・(情報)サービス登場 ・サービスは検索ボックスの下 にまとめて表示 ・1500万PV(1998.9)2001年 Yahoo!JAPAN
検索+サービス お薦めのサービスを トピックスの下に表示 サービスに重点が移り始める サービス数>50 1億ページを突破!(2000.7) 2億ページを突破!(2001.8)2003年 Yahoo!JAPAN
サービスの占めるスペースが拡大 メールやカレンダーなど個人ツール の入り口が、トピックス上にまとまり Yahoo! BBの枠も大きく設けるYahoo! JAPAN 10年間の
ページビュー(PV)の推移
2010年以降:Yahoo!は検索エンジンからほぼ撤退し、 情報サービスとしてのポータルサイトとなる。 http://www.yahoo.co.jp/ 2014.12 月間総ページビュー(PV)数は約606億PV、 スマートフォンで約273億PV。30億PV/日。 http://ir.yahoo.co.jp/jp/individual/marketandusage.htmlGOOGLE 誕生
1.サーゲイ・ブリン(スタンフォード大学,CS)が博士課程で データマイニングの研究を進める。 2.Webデータに興味を持つラリー・ペイジ(ロシア人)が参画 3.2人で1.5万ドル(160万円)のお金を出して,TB(テラバイト) オーダーのHDDを購入して実験を進める。 4.ビジネスプランを申請。 5.サンマイクロシステム社が$10万(1050万円)出資 6.ベンチャーキャピタルが2500万ドル(26億円)出資 7.1998年9月:GOOGLE(グーグル:10の100乗 を示す英単 語「googol」に由来 )GOOGLE アドワーズ広告(後で詳細)
• ビジネスモデル:他のサイトが検索サイトから総合サイトにモデルチェンジする中、GOOGLEは検索一筋。 売上高の99%=インターネット広告→現在は95%程度 • バナー広告→検索連動型広告=アドワーズ広告(売上高50%)+アドセンス広告(売上高49%) アドワーズ(Adwords:Ad=広告+words=キーワード)広告 検索キーワードに関連する広告を検索結果表示ページの上側と右側に テキスト表示(上1枠+右8枠=最大9枠。それ以降の広告は次ページ以降). →最近は、画面の上側と下側 (ユーザへの配慮) ・テキスト表示:検索速度が遅くなってはいけない ・広告表示場所は上側と右(下)側に定め、検索結果閲覧を邪魔しない ・ポップアップ広告はユーザが不快になる恐れがあるので禁止。・クリック単価(CPC: Cost Per Click)×クリック率(CTR: Cick Through Rate)
で表示順位決定。CPCだけで決める広告主主導になりすぎるため。
・さらにCTRが0.5%を下回ると広告が抑制され,そのまま改善しない場合はステータスが 「無効」になり取り下げられる。
(広告主への配慮)
クリック課金型広告(PPC (Pay Per Click)広告)
→クリックされた場合のみ広告料金が発生
クリック単価(7円~1万円)を設定しクリック数に応じて支払う 1日当たりの上限金額設定可能。
GOOGLE アドセンス広告
• Webサイトを持つ人がアドセンスに無料登録
• 登録されたWebサイトを解析し掲載すべき広告を
決定し掲載
• その広告がクリックされれば、Webサイト登録者と
GOOGLEに広告料が二分されて入る
• 利益率は低いが、世界中が広告媒体となる。
現在の主要検索エンジン
2018/12/14はここから
ディレクトリ型 ロボット型
Yahoo! (USA)
Yahoo! Directory(2014.12.31中止) YST→ Bing(2010)
Yahoo! Japan
Yahoo! Category(2018.3.29中止) YST→Google(2010)
ニールセン・オンライン、検索サービス利用動向レポート「MegaView Search」 http://www.netratings.co.jp/news_release/2010/05/Newsrelease20100527.html
現在、世界40カ国の検索エンジのシェア(1)
http://www.globalmarketingchannel.com/press/pdf/20121120.pdf
現在、世界40カ国の検索エンジのシェア(2)
韓国発「NAVER まとめ」の(日本における)月間訪問者数が1,300万人を突破 (2009年7月より日本語サービス開始)
ニールセン: 日本のネットサービス利用者数ランキング1
検索結果の表示順位
「Googleの人気の秘密 (http://www.google.co.jp/intl/ja/why_use.html)」• PageRankについて PageRankは、ウェブの膨大なリンク構造を用いて、その特性を生かしま す。ページAからページBへのリンクをページAによるページBへの支持 投票とみなし、Googleはこの投票数によりそのページの重要性を判断し ます。しかしGoogleは単に票数、つまりリンク数を見るだけではなく、票 を投じたページについても分析します。「重要度」 の高いページによって 投じられた票はより高く評価されて、それを受け取ったページ を「重要な もの」にしていくのです。 こうした分析によって高評価を得た重要なページには高いPageRank (ページ順位)が与えられ、検索結果内の順位も高くなります。 PageRankは Googleにおけるページの重要度を示す総合的な指標であ り、各検索に影響されるものではありません。むしろ、PageRankは複雑 なアルゴリズムにしたがったリンク構造の分析にもとづく、各ウェブページ そのものの特性です。 もちろん、重要度が高いページでも検索語句に関 連がなければ意味がありません。 そのためにGoogleは洗練されたテキ ストマッチ技術を使って、検索に対し重要でなおかつ、的確なページを探 し出します。
PageRank
多くの良質なページからリンクされている
ページは、やはり良質なページである
B A 1.被リンク数(単純人気度) 1つのWebページからリンクされているA よりも、2つのWebページからリンクされて いるBの方がPageRank値が高い SPAMページ、内輪推薦に対応できない D C B A 2.リンク元の被リンク数 1つのWebページからリンクされている Cより2つのWebページからリンクされて いるDの方が信用できる。よって、Cから リンクされているAよりも、Dからリンクされ ているBの方がPageRank値は高い B A 3.リンク元ページでのリンク数 Aのリンク元はリンクが2つあるが、Bのリンク元は リンクが一つであり、より厳選された推薦であるので、 AよりBの方がPageRank値は高い
PageRank値の計算方法
1.リンク構造を隣接行列で表現する。 aij = 1 if (ページ i からページ j へのリンクが「ある」場合) 0 if (ページ i からページ j へのリンクが「ない」場合) 2. PageRank は「どれだけリンクしているか」ではなく「どれだ けリンクされているか」を重視しているので、 転置行列を作 成し(行と列を入れ替えること)、さらにそれぞれの列 (column)ベクトルの総和が 1 (全確率)になるようにそれぞれ のリンク数(すなわち、非零要素数)で割る(推移確率行列)。 3.推移確率行列の最大固有値に属する固有ベクトルを求め、 これがPageRank値になる。PageRankの計算例題
左図グラフのようなWebがあるとする. 問1 どのWebサイトが評判が高いか を直感で示せ. 問2 下記の手順でPageRank値を 求め,問1と比較せよ 1.隣接行列 2.転置行列 3.推移確率行列 4.方程式を立てる 5.固有値, 固有ベクトル, 正規化(=ページランク)R= (1/4, 7/36, 2/9, 1/12, 1/4)
1.隣接行列 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 2.転置行列 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がどのノードから連結されているか 3.推移確率行列 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の計算過程(1)
4.推移確率行列の最大固有ベクトルを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 rA rB rC rD rE = λ rA rB rC rD rE グラフが強連結(グラフ上の任意 の2点間に有向路が存在する) の時は,λ=1となるので, MP=Rを解けばよい rA rB rC rD rE 1 7/9 8/9 1/3 1 = 5.Rを正規化する (要素の総和(=4)で各要素を割る) R= (1/4, 7/36, 2/9, 1/12, 1/4)PageRankの計算例題1
(各自やってみること)
キーワード検索と全文検索
• キーワード検索: Webページに登録されたキーワードが検索対象。 ○検索が高速。 ○検索結果にゴミが少ない。 ×キーワード登録が手間。 ×検索漏れが多い(デジカメ≠デジタルカメラ) • 全文検索: Webページ内のすべての文字が検索対象。 ほとんどのサーチエンジンが採用 逐次検索方式:Webページの先頭から順番に文字列照合 インデックス方式:事前にWebページを分析し索引情報(語 句、Webページ)を作成して利用するインデックス検索方式に基づく
全文検索(フルテキストサーチ)
データ収集部 (ロボット,スパイダー,クローラ) 文書フィルタ部 インデクサ部 検索サーバー部 フロントエンド部、ユーザ 検索語句 結果表示 Webページ群 文字コードの統一,タグの除去 インデックス(索引)の作成 イン デックス ファイル 検索語句とインデックス ファイルとの照合 Webデータを収集• 19inchラック(210cmH
x 60cmW x 75cmD)に
1UのPC80台を設置。
(Rackable Systemsの
技術:ラックの全面と背
面の両方に奥行半分の
PCを設置)
• 2 Fast Ethernet Switch
/ 筐体
• 4筐体をGigaEtherにて
接続し1クラスタを構成。
空調 2x44port Fast Ethernet Switch PC ラック前面に20台 裏面に20台 PC ラック前面に20台 裏面に20台 空調 2x44port Fast Ethernet Switch PC ラック前面に20台 裏面に20台 PC ラック前面に20台 裏面に20台12000台(2004?)のサーチエンジンサーバー
80CPU×150ラック
Google のデータセンタ
外観は巨大な工場のよう 内部には 大量のコンピュータ 全部で 2250 万台という噂 (サーバの日本国内 市場規模は 50 万台) 電力使用量 2 億 6 千万ワットサーバー台数と収集されたWebページ数の推移
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 A ug -98 F eb -99 A ug -99 F eb -00 A ug -00 F eb -01 A ug -01 F eb -02 2001.3 8000台 2000.12 Biglobe と提携 1998.8 30台 1999.6 Netscapeと提携 2000.6 Yahoo!と提携 平均33台/日で増加 2億 4億 6億 8億 10億 12億 14億 収集 W e b ペ ー ジ 数 P C 台 数 16億 18億 20億 2001.4 @Niftyと提携(Web巡回)ロボット
(クローラー,スパイダー)の仕組み
①手作業により収集すべきWebページ(URL)を登録
(URL: Uniform Resource Locator→インターネット上に存在 する情報資源(文書や画像など)の場所を指し示す記述方式)
②登録されているURLにアクセスしWebページを収集
③そのWebページに記載されているリンクを辿って
Webページを収集
④リンクを辿る深さを制限してデータ収集
1サーバーに100以上のロボット
100x12000=120万以上のロボットが巡回
全文検索からのインデックス生成の困難さ
英語:区切り記号として空白がある
→インデックス生成容易
日本語:区切り記号としての空白がない
漢字仮名交じり文
→インデックス生成困難
さとうとしお
→漢字変換すると
さとう としお(佐藤敏夫)
さとう と しお(砂糖と塩)
日本語形態素解析
形態素(意味を持つ最小の文字列) 大きな地震が来ないことを祈ります。 基本的アルゴリズム ①入力文の先頭文字列と最長一致する辞書項目=先頭候補 ②先頭候補に続きく部分と最長一致辞書項目=2番目候補 ③先頭候補と2番目候補との接続可否を検査。接続可なら3番目候補へ (×あります・です,○ありません・でしょうか) ④接続不可の時、2番目候補をより短い別の候補に置換して再度接続検査 ⑤2番目候補がなくなれば、先頭候補に後戻りしてより短い候補に置換して同様の処理を続ける ○索引ファイルサイズが小さく検索時間は速い ○辞書で照合しており,検索ノイズが少ない ×事前に辞書の構築が必要. 大きな 地震 が 来 な い こと を 祈 り ます 。 連体詞 名詞 格助詞 動詞語幹 助動詞 活用語尾 形式名詞 格助詞 動詞語幹 活用語尾 助動詞 句読点代表的な日本語形態素解析ツール
茶筌システム
• 奈良先端科学技術大学院大学情報科学研究科
自然言語処理学講座(松本研究室)
で開発
•
http://chasen.naist.jp/hiki/ChaSen/
から
自由にダウンロードして使用可能
• 実行してみましょう!
「
大きな地震が来ないことを祈ります。」を
Chasen に入力すると?
Nグラム方式
• Gram(グラム):ギリシャ語で[書かれたもの] Nグラム:N文字 先頭からN文字の文字列を1単位とし,1文字ずつずらしてN文字列を索 引とし,その出現位置情報ともに登録する方式 • N=2として「文字列の検索処理」にNグラム方式を適用すると 「(1)文字」「(2)字列」「(3)列の」「(4)の検」 「(5)検索」「(6)索処」「(7)処理」「(8)理」と分解し, インデックスファイルに登録する(数字は出現位置). 「検索」を入力すると→(5)で見つかる 「検索処理」を入力すると→「検索」と「処理」の両方が含まれ、 かつその出現位置が2ずれているもの→(5)と(7)でみつかる ○形態素解析では辞書が必要.Nグラムでは機械的に処理が可能 ○検索漏れが少ない ×索引ファイルサイズが大きくなり,検索時間が遅くなる ×検索ノイズが多い(入社式は4月1日本社で行われた→2グラム?で検索される)検索エンジンによる
On-page factors + Off-page factors
• Webページの評価(検索順位をあげる) → On-page factors(ページ内要因) + Off-page factors(ページ外要因) • ページ内要因:Webページ内の情報(キーワード出現回数, キーワードの配置,<title>タグ, <h1>-<h6>タグ, サイト内リンクなど)を評価 • ページ外要因:リンク分析(数,質,関連性,時間,信頼性) +アンカーテキストによりページを評価On-page factors (テキスト要素の最適化1)
テキストの論理構造,コンテンツを明確化 →クローラに好まれるWebサイトの制作 →本来のHTMLの利用 ①スタイルシート(CSS)やJavaScriptは外部ファイルにする (論理構造と視覚情報は分離する) ②キーワード抽出箇所:タイトル,見出し,第1段落,最終段落, 各段落の最初と最後(<meta>タグは,90年代,評価対象で あったが,スパムに多用されたため,現在は無視される) ③ <title>タグ:ページ遷移に沿ってキーワードを具体化 (海外旅行→欧州旅行→パリ3日間). 全ページに同じキーワードは駄目(共通キーワードは可) 偏ったキーワード(ecサイトで,商品名orショップ名だけを キーワードとする)は駄目. キーワードの個数は1-2個(ネット利用者調査より) 不必要に類似キーワードを繰り返さない→スパム行為テキスト要素の最適化2
④見出しタグ<hx>:文章論理構造 (h1:標題,h2:部,h3:章,h4:節,h5:項,h6:小見出し). クローラは<h1>重視→<h1>を多用するとスパムと判断される ⑤画像タグ<img>:クローラは画像理解できないので, alt属性に画像を説明する適切なキーワードを記載 (例)グーグルバナーの表示 <a href="http://www.google.co.jp/"> <img src = http://www.google.com/logos/Logo_40wht.gifborder="0" alt="Google" align="middle" width="128" height="53"> </a>
Off-page factors (リンクの評価1:重要度)
• リンク分析:数,質,関連性,信頼性,時間の総合評価 (ページランクアルゴリズムはリンク分析の一部にしかすぎない) • ページランクアルゴリズム:被リンクの数と質の評価 +アンカーテキスト(10年前. miserable failure) 重要度に課題:Web全体からみた重要度であって, 特定話題(検索クエリー)からみた重要度ではない. 信頼度に課題:スパムに弱い. • 関連性:relevance(A,B)>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コンビニ
リンクの評価2:信頼性
• 重要度だけでは,大量のWebサイトを巧妙に開設し,そこか らリンクを張りページランクをあげる事は依然可能. • 信頼性:友達の友達は信用.その友達の友達は?その友達 の友達は??という考え方.審査により予め信頼できるWeb サイト群を決め,そこから信頼値を割り当てる. 重 要 度 信頼度 • 時間:開設期間が長い程,信頼性は高い. 急激なリンク数の増加は不自然であり信頼性を低くする . 優良? スパム? 新規? マニア? Yahoo研究者のTrustRank: http://www.vldb.org/conf/2004/RS15P3.PDF Googleは2005年にTrustRankを商標化したが、 現在は使用中止?(別のアルゴリズム採用?)Web上の広告
• バナー広告
元来「垂れ幕」の意 帯状の広告画像が宣伝用の垂れ幕 を連想• キーワード広告
検索キーワードに関連す るWebサイトを提示 クリック回数で広告効果が計れるキーワード広告(1)
• 1999年Altavistaによって試みられる
• 広告枠をオークションで売り、クリックされた
分だけ広告料を課金
• ユーザのニーズに合った広告が期待できる
• 現在は数十億ドル規模のビジネスに
キーワード広告(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キーワード広告(3)
• オーバーチュア:入札金額で表示順位が決まる
– 順位付け:クリック単価上限の高い順 – 実際のクリック単価:一つ下位のクリック単価+1円• Google:広告のクリック率も加味した表示順位
– 順位付け:クリック単価上限×クリック率の高い順 – 実際のクリック単価:一つ下位のクリック単価上限×クリッ ク率÷自広告のクリック率+1円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日当たりの上限金額設定可能。
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は?