3rd Lecture

ビッグデータアナリティクス第3回
大規模Web情報処理
岩爪道昭
（独）情報通信研究機構
ユニバーサルコミュニケーション研究所
サイバー攻撃対策総合研究センター
[email protected]
概要
1.
2.
3.
4.
5.
6.
ビッグデータとしてWeb
Webクローリング
Webリンク解析
大規模Web情報処理の実例
Webの未来
演習およびレポート課題について
21/10/2014
Michiaki Iwazume, NICT, all right reserved. 2
1. ビッグデータとしてのWeb
11/13/2013
Michiaki Iwazume, NICT, all right reserved. 3
ビッグデータとしてのWeb
•
•
•
•
2006年全世界のWebページ総数537億と予測(by 山名）
2008年 Googleが把握するURL数が1兆を突破（by Google)
2010年全世界のWebの情報量は、800EB (0.8ZB)（by IDC）
現在？？？ (もはや誰も正確な数を把握できていない）
Webは、我々とって最も身近で、社会・
経済にとって欠くことのできない
『ビッグデータ』のひとつ
11/10/2013
Michiaki Iwazume, NICT, all right reserved. 4
Webは何故ここまで発展したのか？
Michiaki Iwazume, NICT, all right reserved. 5
Webとは？
•Webの起源
 Invented by Tim Berners‐Lee in 1989
 First Web Browser – October 1990
 First Web Server – November 1990
T.B. Lee presents the W3 in CERN ‐ 1993
W3C ‐ 1993 • Tim Berners Lee’s Vision (T.B.Lee, 1998):
“The dream behind the Web is of a common information space in which we communicate by sharing information. Its universality is essential: the fact that a hypertext link can point to anything, be it personal, local or global, be it draft or highly polished. .
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 6
Webとは？ [T.B.L et al 1994]
•
•
A system of interlinked hypertext documents accessed
via the Internet.
With a web browser a user views web pages that may
contain text, images, videos, and other multimedia and
navigates between them using hyperlinks.
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 7
Webの基本アーキテクチャ
[T.B.Lee et at al 1994]
The Web is an information space in which the items of interest, referred to as resources, are marked up by a set of rules (i.e. HTML),
identified by global identifiers called Uniform Resource Identifiers (URI) using the Hypertext Transfer Protocol (HTTP). 20/11/2012
Michiaki Iwazume, NICT, all right reserved. 8
世界最初のWebページ
http://www.w3.org/History/19921103hypertext/hypertext/WWW/TheProject.html
Michiaki Iwazume, NICT, all right reserved. 9
世界最初のWeb検索ディレクトリ
http://www.w3.org/History/19921103-hypertext/
hypertext/DataSources/bySubject/Overview.html
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 10
Web検索システムの歴史（90年代）
• Characterised by large indexes but crude retrieval techniques
• World Wide Web Worm (WWWW), 1993
– First Search Engine
– Indexed titles and headers only
• Yahoo, 1994
– Human edited directory (still is!)
• WebCrawler, 1994
– First search engine to search the text of the web page • AltaVista, 1995
– Natural language querying with Boolean operators
– Huge index
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 11
初期のGoogle
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 12
初期のGoogleの構造
[L.Page and S. Bring 1998]
Michiaki Iwazume, NICT, all right reserved. 13
初期のGoogleの構造
[L.Page and S. Bring 1998]
20/11/2012
14
Michiaki Iwazume, NICT, all right reserved. 14
何故グーグルはここまで成功したのか？
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 15
何故Webはここまで成功したのか？
•
•
•
•
•
単純（simple）
ネットワーク（networked）
拡張性（extensible）
頑健性（tolerant）
オープンスタンダード（open
standards)
• 無料・安価（free or cheap）
• 面白い（fun）
：
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 16
2. Webクローリング
Michiaki Iwazume, NICT, all right reserved. 17
Webクローラはどのように動くのか？
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 18
シンプルなクローリング手順
• Initialize queue with URLs of known seed pages（初期化）
• Repeat（繰り返し）
– Take URL from a queue
– Fetch and parse a page
– extract URLs from the page
– Add URLs to the queue (URL frontier)
※ちゃんとリンクが張られているという仮定
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 19
シンプルなクローラのイメージ
URLs crawled
and parsed
Unseen Web
Seed
pages
URLs frontier
Web
20
20/11/2012
Michiaki Iwazume, NICT, all right reserved. シンプルなクローラの問題
• 1プロセス、１台のマシンでは間に合わない
– 全ての処理を並列化する必要がある
• 悪意のあるページへの対応
– スパムページ
– スパイダートラップ（動的生成ページ）
• その他
– 収集先サイトのレイテンシ（遅延）／バンド幅変化
– Webサイト管理者側ポリシー問題
• どれくらいの深さまでクロールを許すか？
– ミラーサイトや重複ページの存在
• クローラのお行儀良さ（politeness)
Michiaki Iwazume, NICT, all right reserved. 21
実際的なクローラに必要な機能
• 行儀良さ: 許可されたページのみの収集
robots.txt尊守
• ロバスト性：悪意のあるページへの対処
• 並列分散性：複数の計算機、プロセッサ上で
並列分散化してクローリングプロセスを実行
• スケーラビリティ: 計算機資源を段階的に追
加することでより大規模な収集が可能なアー
キテクチャ
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 22
実際的なクローラに必要な機能
• パフォーマンス: 利用可能な計算機および
ネットワーク資源を最大限に活用する
• 効率性：よいページを優先的に集める
• 継続性 : 更新ページ、新規ページの継続的な
収集
• 拡張性: 新しいデータへの適用
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 23
より実際的なクローラ
Sec. 20.1.1
URLs crawled
and parsed
Unseen Web
Seed
Pages
URL frontier
Crawling thread
24
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 修正されたクローリング手順
1. Pick a URL from the frontier
2. Fetch the document at the URL
– DNS resolution
3. Parse the URL
– Extract links from it to other docs (URLs
4. Check if URL has content already seen
– If not, add to indexes
5. For each extracted URL
– Ensure it passes certain URL filter tests
– Check if it is already in the frontier (duplicate URL elimination)
Michiaki Iwazume, NICT, all right reserved. 25
修正されたクローラアーキテクチャ
Sec. 20.2.1
DNS
WWW
Doc
FP’s
robots
filters
URL
set
Content
seen?
URL
filter
Dup
URL
elim
Parse
Fetch
URL Frontier
Michiaki Iwazume, NICT, all right reserved. 26
Robots.txtの記述例
“searchengine”という名前のクローラ以外、い
かなるクローラも“/yoursite/temp/”で始まる
URLにアクセスしてはならない
User-agent: *
Disallow: /yoursite/temp/
User-agent: searchengine
Disallow:
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 27
ビッグデータについておさらい
■ビッグデータとは？
ビッグデータを特徴付ける「３つのV」
大サイズの動画から、
小サイズだが無数の
twitterまで
サイズおよび数における⼤規模性
Volume
定型・非定型を
問わない多種
多様なデータ
高頻度で生成され
続けるデータ
Variety
データの多様性
Velocity
処理のリアルタイム性
28
ビッグデータ時代のクローラ
ビッグデータをクロール
するには？
29
ビッグデータ時代のクローラ
■ Volume
大量（数）のデータを収集・格納
① 億を超える件数のURLを保存・管理し、高速に検索
⇒クロール対象URLの抽出処理、収集済みURL
のチェック
② 効率よくデータを収集するスケジューリング
⇒限られた時間・リソースの範囲内で、必要とす
るデータを収集
⇒特定のサーバにアクセスが集中しない制御
③ Near Dupulicateなページを判別して除外
⇒不要ページの保存によるストレージ圧迫回避
30
ビッグデータ時代のクローラ
■Velocity
収集率（単位時間あたりの収集量）を向上
① 非同期で分散してクロール
⇒shared nothingな構成とし、ノードの追加によ
りスケーラビリティを確保
② 更新間隔を推定し、更新データのみを効率的に収集
⇒収集済みページに再アクセスして初めて更新
の有無が判明するため、無用な更新前のアク
セスは収集率の低下原因
③ ネットワーク帯域を最大限に活用＆連続クロール
⇒しかし特定のサーバにアクセスが集中しては
ならない
31
ビッグデータ時代のクローラ
■Variety
多様な形式のデータを収集
① HTMLファイル以外のクロール
⇒画像・音声・動画ファイル
ストリーミング系（動画）など
② 独自API提供サービスのクロール
⇒Twitterなど、個別サービスに合わせてインタ
フェースを切り替え可能な仕組み
③ SNSなどのソーシャルネットワーク系のクロール
⇒個人のアカウントを用いたクロール
 なお、これらクロールに関しては、技術的な課題の他に、
法的・制度的な問題（著作権やプライバシーなど）にも十
分な配慮が必要
National Institute of Information and Communications Technology
32
クローラを扱った先⾏事例
名称
特徴
IRLbot[Lee 2007]
サーバ1台構成で41日間63億ページをクロール
KVSを利用した高速URL管理やスパム回避機能
UbiCrawler[Boldi 2004]
単一障害点のない完全分散アーキテクチャ
Agent数に比例するスループット
Mercator[Najork 2001]
分散構成で1日5,000万ページのクロール実績
Socio Senceのクローラ
[田村 2008,2010]
更新頻度推定によるスケジューリング
二次記憶管理技法について
e‐Societyのクローラ
[詹 2010] [森本 2011]
特定言語Webページ収集のフォーカストクローラ
時間計算量O(1)でのスケジューリング技法
以上の先行研究は、ビッグデータのクロールにとって有益
な成果であるが、クローラ実装は非公開
33
オープンソース系クローラ
名称
特徴
項目
Heritrix
Nutch
Heritrix
モジュールの組み換えに
より、処理内容を柔軟に
変更可能。設定も細かく
指定でき、利便性が高い。
スケジューリング
×
×
NearDuplicate
×
×
分散クロール
×
○
全文検索エンジンLucene
用のインデックスを生成可
能。Hadoopを用いた分散
処理によるスケーラビリ
ティあり。
更新間隔推定
×
×
クロール対象
△
×
拡張性
○
○
ドキュメント
×
○
Nutch
それぞれ完成度は高く、有益なアプリケーション
 高機能化のためには、コードの解析が必要
34
３．Webリンク解析
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 35
Webはどんな構造をしているのか？
[B.Broder et al 2000]
Michiaki Iwazume, NICT, all right reserved. 36
ページランク
• 基本的な考え方
– Webのリンク構造に基づく
– Webページは”ノード” 、
リンクは、”エッジ“
– フォワードリンク（外に出るエッジ）
– バックリンク（内に入ってくるエッジ）
– ページA、Bは、ページCのバックリンク
（インエッジ）
– ページCは、ページA, Bのフォワード
リンク（アウトエッジ）
• 仮定：
– A から Cへのリンクを投票とみなす
– 沢山リンクされるページは重要
– ランキングの高いページからのバックリンクは、そうでな
いページからのリンクよりもスコアが高い
Michiaki Iwazume, NICT, all right reserved. 37
ページランク[Bring and Page 1998]
• ランダムサーフモデル
– 任意のページを起点
– ランダムウォーク：そのページから出ているリンク
の中からランダムに選択、リンク先に移動
– ランダムジャンプ：Web上のあらゆるページの中
から１つをランダムに選択肢、そこにジャンプ
– 長い時間が経過すると、サーファーが各ページに
滞在する確率、一定の定常状態に収束
（マルコフ過程）
1/3
1/3
1/3
Michiaki Iwazume, NICT, all right reserved. 38
ページランクの計算（単純版）
r(Pi)  c 
PjBpi
r(Pj)
Nj
Pi : Webページ Pi
Bpi : ページPi のバックリンク集合
Nj : ページPj のアウトリングの総数
C : 正規化係数（定数）
r ( Pj )
1/Nj
1/Nj
1/Nj
r ( Pi )
Michiaki Iwazume, NICT, all right reserved. 39
ページランクの計算（修正版）
現実のWebグラフは、全てのページがリンクで相互に接続しているとは限らない！
→ 単純化されたモデルは計算できない
２
５
１
４
３
７
６
1
r´(Pi)  cr(Pi)  (1 c) 
 n n  n
n : 隣接行列の行数
Michiaki Iwazume, NICT, all right reserved. 40
演習：Rによるページランク計算
以下の有効グラフ（Webグラフ）のページランクを計算してみよう
１
２
４
３
有効グラフ（Webグラフ）
0110
1010
0000
1000
隣接行列
【準備】グラフ解析パッケージ“igraph”のインストール
> install.packages(“igraph")
①隣接行列の作成
library(igraph) #igraphパッケージのセット
dg <- matrix(c(
+ 0, 1, 1, 0,
+ 1, 0, 1, 0,
+ 0, 0, 0, 0,
+ 1, 0, 0, 0),
+ nrow = 4, ncol = 4, byrow = TRUE)
Michiaki Iwazume, NICT, all right reserved. 41
演習：Rによるページランク計算
②隣接行列（グラフネットワーク）の描画
#隣接行列dgが正しくセットされたかの確認
>dg
[1,]
[2,]
[3,]
[4,]
[,1] [,2] [,3] [,4]
0
1 1 0
1
0 1 0
0
0 0 0
1
0 0 0
>g <- graph.adjacency(dg, mode = “directed”) #グラフオブジェクトを生成
#plot()でグラフネットワークを描画
>plot(g)
Michiaki Iwazume, NICT, all right reserved. 42
演習：Rによるページランク計算
③ページランクの計算
#隣接行列dgが正しくセットされたかの確認
>dg
[1,]
[2,]
[3,]
[4,]
[,1] [,2] [,3] [,4]
0
1 1 0
1
0 1 0
0
0 0 0
1
0 0 0
> page.rank(g, directed = TRUE)$vector #page.rank関数による計算
[1] 0.3063548 0.2405390 0.3427680 0.1103382
④正規化係数c(damping値）によるスコアの変化
> page.rank(g, directed = TRUE, damping = 1.0)$vector #c=1.0
[1] 0.30303030 0.24242424 0.36363636 0.09090909
> page.rank(g, directed = TRUE, damping = 0.2)$vector #c=0.2
[1] 0.2800517 0.2412753 0.2654028 0.2132701
Michiaki Iwazume, NICT, all right reserved. 43
情報分析システムWISDOMを支える情報基盤
 計算機
 サーバ：252 ノード (1156 CPU)
 4 コア, 8 GB メモリ, 1.5–2 TB ローカルストレージ
 360TB ファイルサーバ (NAS + GPFS)
 Webクローラ
 クローリング速度: 最大1000万ページ/日
 収集URL総数: 17億件以上
 Web アーカイブ
 HTML 文書:
 検索インデクス:
10億ページ
1.2億ページ
情報分析システムＷＩＳＤＯＭを支える計算機基盤
45
WISDOMを支える計算機基盤
・億単位の超大量データを並列高速処理するためのシステム構成
・現在世界大４位の日本が誇るスパコン・ＴＳＵＢＡＭＥ（東工大）にWISDOM
の分析エンジンを移植し、解析を試みたところ・・・
 取り扱うファイル数が多過ぎて、ファイルシステムがダウン（松岡先生にお叱り
を受けた・・）
 ファイル数を減らして実行してみたところ、ファイルのアップ／ダウンロード等
事前事後作業も含め１億ページの解析に約２ヵ月を要した（解析処理のみで
あれば２～３週間程度）
→民間のクラウドサービスではデータの送受信にコストがかかり過ぎ使いづらい
・CPUの演算速度を重視したスパコン（PCクラスタ）では、データの読み書き
による遅延（I/Oレイテンシ）ボトルネック
46
WISDOMにおけるデータ管理の現状と課題
リソースの制約および検索結果の品質のためクローラに収集された
データは段階的（バッチジョブ的）に検索対象として選択・解析
・1回のクロールで収集したWebページを1ファイルに
まとめて出力。
・抽出されたリンクURLがURL DBに登録される。
・クローラ出力のHTMLファイルを保存し、IDやクロー
ル日時をキーとする管理DBを作成。
・リンク解析用のリンク情報ファイルを作成する。
・言語解析対象ページを選択し、キャッシュHTMLの
形式で登録。
・登録した各ページから、言語解析済みデータとして
Web標準フォーマット、及びInlink情報をまとめたア
ンカー情報ファイルを作成。
・Web標準フォーマットおよびアンカー情報ファイルか
ら検索タームを取り出したTERMファイルを作成する。
・検索対象の1.2億ページを選択し、そのTERMファイ
ルから検索インデックスを作成。
・検索時はインデックスを検索し、適合する1000ペー
ジを分析対象として選択。
現状のアーキテクチャではスケールアウトしない
47
技術的課題・チャレンジ
•
•
•
•
•
スケーラビリティ
• クローラ、ＵＲＬＤＢ、クロールデータプールがスケールアウトしない
データ冗長性
• データが冗長化されていないためハードウェア障害に弱い（貴重な
情報資源を消失するリスク）
→ 仮想分散ストレージの必要性
リアルタイム性：
• クローリングから分析サービスまで３日かかる
• ＴＳＵＢＡＫＩのインデックス更新
（１ページ単位のインデックス更新ができない）
• データ管理：インデックス更新
複数拠点による並列分散クローリング／データ管理
通常のクローラで取得できないデータへの対応
• Twitterのようなストリームデータ（マイクロブログ）への
対応（クローリング、解析）
• ＳＮＳサイトのクローリング
• データ落ちしたスレッド系サイト
48
リンク解析によるSPAMページ判定
• 主に金銭的、経済的理由から検索エンジンの
ランキング上位にあげるために作成（主に自
動生成）される悪意のあるページ
• SPAMページの種類
– コンテンツスパム
– リンクスパム
– なりすまし
Michiaki Iwazume, NICT, all right reserved. 49
これは何のページ！？
一見、文章はまとも？
実は、
Wikipediaから
のコピペ
Wikipediaへのリンク
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 50
Link Structure of the Site
対象ページ
全てが同様にコピペ
による自動生成ページ
対象ページ
51
WikiPedia
Michiaki Iwazume, NICT, all right reserved. リンク解析によるSPAMページ[Leon2010]
• スパム判定: Webグラフ中の強連結構造を抽
出(Recall=90.9%, Precision=73.2%の精度)
• ページランクによるランキング
クロール
文書
Webグラフ
作成
スパム判定
Michiaki Iwazume, NICT, all right reserved. ページランク
判定
52
5. 未来のWeb
20/11/2012
Michiaki Iwazume, NICT, all right reserved. 53
Webの未来は?[T.B.Lee1998]
There was a second part of the dream, too, dependent on the Web being so generally used that it became a realistic mirror (or in fact the primary embodiment) of the ways in which we work and play and socialize. That was that once the state of our interactions was on line, we could then use computers to help us analyse it, make sense of what we are doing, where we individually fit in, and how we can better work together.”
Michiaki Iwazume, NICT, all right reserved. 54
Webの過去・現在・未来
eras
description
Basic value resouce
Pre Web 1980’
calculate
The desktop is the platform
Computations
(No network effect)
Web1.0: 90’s
read
Surfing Web: The browser is the platform
Hyper‐linking of
documents
Web2.0: 00’s
write
Social Web: The web is the platform Social dimension of linkage
properties
Web3.0: 10’s
discover
Semantic Web: The data is the platform
URI‐based semantic linkages and data
Web 4.0: 20’s
Execute
(cyber physical system)
Meta‐computing: The network is the platform web of things (embedded system, RDIF, sensor network)
Connection & production in a global computing system for everything
Web ∞
combine all
Almost everything is a web service(?)
New inter‐creativity
Michiaki Iwazume, NICT, all right reserved. 55
新たなWeb：Linked Open Data
Michiaki Iwazume, NICT, all right reserved. 56
6．演習・レポート課題
Michiaki Iwazume, NICT, all right reserved. 57
課題１
下記のようなWebグラフ（有効グラフ）のRageRankを
Rを用いて計算せよ．
２
５
１
４
３
８
(a)隣接行列dgを求めよ
(b) plot()関数で有効グラフ図を描画せよ
(c) 隣接行列のPageRank値を計算せよ
(d) damping = 0.2とした場合のPageRank
値を計算し、(c)の結果と比較検証せよ
７
６
９
Michiaki Iwazume, NICT, all right reserved. 58
課題２
以下のクローリングプログラムの問題点とその解決
方法について論ぜよ(1000文字以内）
urlqueue := (some carefully selected set of seed urls)
while urlqueue is not empty:
myurl := urlqueue.getlastanddelete()
mypage := myurl.fetch()
fetchedurls.add(myurl)
newurls := mypage.extracturls()
for myurl in newurls:
if myurl not in fetchedurls and not in urlqueue:
urlqueue.add(myurl)
addtoinvertedindex(mypage)
Michiaki Iwazume, NICT, all right reserved. 59
レポートの提出方法
 課題の記載項目：
 授業名，課題番号（第一回課題），名前，学籍番号，メールアドレスを最初に
記載
 課題1：(1)隣接行列dgの作成と確認結果, (2)plot(g)で生成したグラフネット
ワークの画像,(3)page.rank(g)の実行結果、(4)damping値を0.2に設定した際
のpage.rank(g)の実行結果,および(3)との違いに関する考察
 課題2：1000字以内の考察文
 宛先：bda‐[email protected]
 件名：BDA‐日付‐学籍番号‐名前 (例：BDA‐20141017‐1251079‐
MichiakiIwazume)  ファイル形式：PDF
 ファイル名：件名と同じ
 提出締切：10/31(金)
Michiaki Iwazume, NICT, all right reserved. 60

Download Report