情報システム 第11回講義資料

情報学科CSコース情報システム（３年後期）

講義ノート

ー第１１回ー

Web分析と意味モデリング

田中克己

角谷和俊

2

Webの分析

„

Web分析の観点

„

コンテンツ

„ Webテキスト，XML „ 自然言語処理，テキストマイニング „ クラスタリング，要約，トピック検出 „

構造

„ ハイパーリンク解析，グラフ構造 „ コミュニティ，クローリング „

利用

„ Webログ，トランザクション解析 „ アクセス・ブラウジング履歴 „ 協調フィルタリング „

構造に基づいたページ重要度の計算

„

HITSアルゴリズム

特定トピックに関する有用なページを出力 „

Page Rankアルゴリズム

ページのランキング手法

3

HITSアルゴリズム

HITS (Hypertext Induced Topic Search)

„

質問依存ランキング(query dependent ranking)

特定トピックに関する有用なページを出力

„

Webページの有用性の評価基準

(相互依存する関係)

オーソリティ

特定トピックに関する情報源 ハブとして価値の高いページからリンクを張られている

ハブ

オーソリティへのハイパーリンクの集合 オーソリティとして価値の高いページへリンクを張っている

4

オーソリティとハブの計算

„

特定トピックに関する有用な

Webページを取得

検索エンジンのキーワード検索で

200ページ程度を

取得

(root set)

„

root setにbase setを追加

(約1000～3000ページ) root setからのリンク先ページ

root setへのリンクがあるページ

„

base setのページについて以下を計算

auth(n) = Σ hub(m), for all m → n hub(n) = Σ auth(m), for all m ← n

R

5

Auth=1

Auth=1

Auth=1

Hub=1

Hub=1

Hub=1

Auth=1

Hub=1

Auth=1

Auth=1

Auth=1

Auth=1

Hub=1

Hub=1

Hub=1

Hub=1

Auth=

2

Auth=

2

Auth=

2

Hub=1

Hub=1

Hub=1

Auth=

2

Hub=1

Auth=

0

Auth=

0

Auth=

0

Auth=

0

Hub=1

Hub=1

Hub=1

Hub=1

Auth=2

Auth=2

Auth=2

Hub=

6

Hub=

4

Hub=

4

Auth=2

Hub=

2

Auth=0

Auth=0

Auth=0

Auth=0

Hub=

0

Hub=

0

Hub=

0

Hub=

0

Auth=

10

Auth=

10

Auth=

10

Hub=6

Hub=4

Hub=4

Auth=

6

Hub=2

Auth=0

Auth=0

Auth=0

Auth=0

Hub=0

Hub=0

Hub=0

Hub=0

Auth=10

Auth=10

Auth=10

Hub=

30

Hub=

20

Hub=

16

Auth=6

Hub=

6

Auth=0

Auth=0

Auth=0

Auth=0

Hub=0

Hub=0

Hub=0

Hub=0

Auth=

50

Auth=

50

Auth=

46

Hub=30

Hub=20

Hub=16

Auth=

22

Hub=6

Auth=0

Auth=0

Auth=0

Auth=0

Hub=0

Hub=0

Hub=0

Hub=0

Auth=50

Auth=50

Auth=46

Hub=

146

Hub=

100

Hub=

68

Auth=22

Hub=

22

Auth=0

Auth=0

Auth=0

Auth=0

Hub=0

Hub=0

Hub=0

Hub=0

すべてのページの

auth(n) = hub(n) = 1

スコアが収束するまで以下を繰り返す

　

_{auth(n) = Σ hub(m), for all m → n}

6

PageRank

„

ランダムにリンクをたどる閲覧者がページAを訪れる確率に対応

„

ε/nは任意のページにジャンプする確率

(外に対してリンクを持たないページの値が不当に大きくなるのを防ぐ)

R(A) = + (1-

ε

₎

∑

outdegree(B)

R(B)

ε

n

B such that B → A outdegree(B) はページBから出るリンクの総数 εは定数(0.1から0.2の範囲の値) nは対象とするWebページの総数

„

質問非依存ランキング

(query independent ranking)

「

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

ページである

」

7

PageRank

あるページの PageRank を、そ のページに存在 する発リンク数で 割った数が、それ ぞれ被リンク先の PageRank に加算 される

8

9

Web Trawling

„

関連性のあるページ集合であるコミュニティ

„

ハイパーリンクのグラフ構造を利用して発見

„

Web全体に含まれているコミュニティをすべて数えあ

げることが目標

„

数テラバイト規模のウェブアーカイブからコミュニティ

抽出実験を行い、

10万以上のコミュニティを抽出

„

コミュニティの抽出

i個の頂点のおのおのからj個の頂点すべてに対する

有向辺が存在するような完全

2部部ラフKi, jと，少な

くとも一つの

_{Ki, jを含んでいるようなi+j個の頂点から}

無く

_{2部コアグラフCi,jを定義}

結果

„ i=j=3程度の2部コアグラフがWeb中に数十万個存在する „ 2部コアグラフを構成するページ集合はトピックが明確なコミュ ニティに対応している

10

コミュニティとコア

„

ファン（i個）とセンター（j個）からなる完全二部グラフ

(仮定)

„

ほぼすべてのコミュニティはコアを含む

„

ほぼすべてのコアはコミュニティを形成する

„

Web全体に出現するすべてのコアを数え上げる

„

入力：　コアのサイズ(i,j)

„

出力：　ウェブグラフ内のすべての(i,j)コア

ファン

センター

(2,3)コア

11

http://www9.org/w9cdrom/160/160.html

Webのグラフ構造

Region SCC IN OUT TENDRILS DISC. Total

Size 56,463,993 43,343,168 43,166,185 43,797,944 16,777,756 203,549,046

SCC: Strongly Connected Component

12

Semantic Web

Web上にある文書などの「意味」を扱う技術

„

Tim Berners-Leeが提唱（1998）

„

Web上のデータや情報の意味をコンピュータに理解可能に

„

メタデータ：データについてのデータ

„

RDF

相互運用可能な形でリソースを記述するための枠組み „

RDF Schema

RDF記述を解釈するための定義スキーマ „

オントロジ

コンテンツの相互互換のための枠組み „

URI

Webのリソースを識別するもの „

Name Space

複数語彙の区別・混在を可能にする枠組み

13

RDF

(Resource Description Format)

特定のアプリケーションや知識を前提とせずに，相互運

用可能な形でリソースを記述するための枠組み

„

モデルと構文

（リソース，プロパティ，値）

„

リソース

RDFで記述されるすべてのもの(URIで指定) „

プロパティ

„ リソース記述に用いられる，特徴･関係・属性など „ プロパティの意味はスキーマにより記述 „

値

14

RDF記述

<rdf:RDF>

<rdf:Description about=http://kyoto-u.ac.jp/abc.html> <s:Creator>Tanaka</s:Creater>

</rdf:Description> </rdf:RDF>

（リソースを値に持つ_RDF記述）

<rdf:RDF>

<rdf:Description about=http://kyoto-u.ac.jp/abc.html> <s:Creator rdf:resource=“http://kyoto-u.ac.jp/id/1716”

v:Name=“Tanaka”

v:Email=“tanaka@kyoto-u.ac.jp”/> </rdf:Description>

</rdf:RDF>

http://kyoto-u.ac.jp/abc.html

Creater

_{http://kyoto-u.ac.jp/id/1716}

tanaka@kyoto-u.ac.jp Tanaka

Email

15

RDF Schema

„

RDF記述を解釈するための定義

„

オブジェクト指向

„

リソースのプロパティ定義

„

クラス間の関係

„

値の制約条件（文字列・数字・値の範囲など）

„

クラス定義

„

Resource, Class, Property

„

Type(タイプ定義），subClassOf（クラス間の関係）,

subPropetyOf（プロパティ間の関係）

„

range(プロパティ値の範囲の定義），domain(プロパティ

16

RDF Schemaの例

<rdf:RDF xml:lang=“ja”> xmlns:rdf=“http//www.w3.org/1999/02/22-rdf/syntax-ns# xmlns:rdfs=“http://www.w3.org/2000/01/rdf-sehema#>” <rdf:Description ID=“自動車自動車自動車自動車”> <rdf:type resource=“http://www.w3.org/2000/01/rdf-schema#Class”/> <rdfs:subClassOf rdf:resouce=“http://www.w3.org/2000/01/ rdf-schema#Resource” /> </rdf:Description> <rdf:Description ID=“乗用車乗用車乗用車乗用車”>

<rdf:type resource= “http://www.w3.org/2000/01/rdf-schema#Class”/> <rdfs:subClassOf rdf:resouce=“#自動車”/>

17

オントロジ

„

「分類体系」と「推論ルール集」

„ 知識が知識体系の中でどこに位置づけられるか „ Web上の記述は，表現方法や語彙が異なる „ 概念間の相互関係を定義することで意味的な関係付けを行う（上 位関係，同義関係） „

オントロジ記述言語OWL

„ クラス定義 要素が満たすべき性質によってクラスを定義 （DefinedClass, PrimitiveCLass, EnumerationClass

„ プロパティ定義

定義域（クラス）と値域（クラスあるいはデータ型）を与える 対応付ける要素の数

18

OWLの言語仕様の特徴

階層構造の表現

PrimitiveClass(Man, supers(Person, Male)) SubPropertyOf(hasMother, hasParent)

同等性の表現

SameClass(HumanBeing, Person) SamePropertyAs(shoesize, bootsize)

非重複性の表現

Disjoint(Male, Female)

クラスに対する制約の表現

DefinedClass(Adult, supers(Person), slot(age, range=foo:over19, required)

集合演算を使った表現

DefinedClass(Person, unionOf(Man, Woman))

記述の分散

19

OWLによるクラス階層の記述例

„ 動物(Animal)は，年齢(age)を持つ „ 動物は，オス(Male)とメス（Female)に分かれる „ 人間(Person)には，配偶者(hasSpouse)をもつものもある „ 男性（Man)は，人間かつオスである Animal age Female age Male age Man age hasSpouse Person hasSpouse

PrimitiveClass (Male, supers (Animal)) PrimitiveClass (Femele, supers (Animal))

PrimitiveClass (Animal, slot(age, range =xsd:integer, required, singlevalued))

Disjoint (Male, Female)

Individual(Ichiro, Man, (age, xsd:integer, 13))

DefinedClass (Man,

supers(Person, Male))

PrimitiveClass (Person, slot(hasSpouse, range =Person, optional, siglevalued)