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

Size: px

Start display at page:

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

るるみかつもと
6 years ago
Views:

1 情報学科 CS コース情報システム (3 年後期 ) 講義ノートー第 11 回ー Web 分析と意味モデリング田中克己角谷和俊

2 Web の分析 Web 分析の観点コンテンツ Web テキスト,XML 自然言語処理, テキストマイニングクラスタリング, 要約, トピック検出構造ハイパーリンク解析, グラフ構造コミュニティ, クローリング利用 Web ログ, トランザクション解析アクセスブラウジング履歴協調フィルタリング構造に基づいたページ重要度の計算 HITS アルゴリズム特定トピックに関する有用なページを出力 Page Rank アルゴリズムページのランキング手法 2

3 HITS アルゴリズム HITS (Hypertext Induced Topic Search) 質問依存ランキング (query dependent ranking) 特定トピックに関する有用なページを出力 Web ページの有用性の評価基準 ( 相互依存する関係 ) オーソリティ特定トピックに関する情報源ハブとして価値の高いページからリンクを張られているハブオーソリティへのハイパーリンクの集合オーソリティとして価値の高いページへリンクを張っている 3

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 S R 4

5 すべてのページの auth(n) = hub(n) = 1 スコアが収束するまで以下を繰り返す auth(n) = Σ hub(m), for all m n hub(n) = Σ auth(m), for all m n Auth=1 Auth=0 Hub=6 Hub=30 Hub=146 Auth=2 Auth=10 Auth=50 Hub=1 Hub=0 Auth=1 Auth=0 Hub=4 Hub=20 Hub=100 Auth=2 Auth=10 Auth=50 Hub=1 Hub=0 Auth=1 Auth=0 Hub=4 Hub=16 Hub=68 Auth=2 Auth=10 Auth=46 Hub=1 Hub=0 Auth=1 Auth=0 Hub=1 Hub=6 Hub=22 Auth=1 Auth=6 Auth=22 Hub=1 Hub=0 5

6 PageRank 質問非依存ランキング (query independent ranking) 多くの良質なページからリンクされているページは, やはり良質なページである ε R(A) = + (1-ε) n B such that B A n は対象とする Web ページの総数 ε は定数 (0.1 から 0.2 の範囲の値 ) R(B) outdegree(b) outdegree(b) はページ B から出るリンクの総数ランダムにリンクをたどる閲覧者がページ A を訪れる確率に対応 ε/n は任意のページにジャンプする確率 ( 外に対してリンクを持たないページの値が不当に大きくなるのを防ぐ ) 6

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

8 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 部コアグラフを構成するページ集合はトピックが明確なコミュニティに対応している 9

10 コミュニティとコアファン (i 個 ) とセンター (j 個 ) からなる完全二部グラフセンターファン (2,3) コア ( 仮定 ) ほぼすべてのコミュニティはコアを含むほぼすべてのコアはコミュニティを形成する Web 全体に出現するすべてのコアを数え上げる入力 : コアのサイズ (i,j) 出力 : ウェブグラフ内のすべての (i,j) コア 10

11 Web のグラフ構造 (2000) SCC: Strongly Connected Component Region SCC IN OUT TENDRILS DISC. Total Size 56,463,993 43,343,168 43,166,185 43,797,944 16,777, ,549,046 11

12 Semantic Web Web 上にある文書などの意味を扱う技術 Tim Berners-Lee が提唱 (1998) Web 上のデータや情報の意味をコンピュータに理解可能にメタデータ : データについてのデータ RDF 相互運用可能な形でリソースを記述するための枠組み RDF Schema RDF 記述を解釈するための定義スキーマオントロジコンテンツの相互互換のための枠組み URI Web のリソースを識別するもの Name Space 複数語彙の区別混在を可能にする枠組み 12

13 RDF (Resource Description Format) 特定のアプリケーションや知識を前提とせずに, 相互運用可能な形でリソースを記述するための枠組みモデルと構文 ( リソース, プロパティ, 値 ) リソース RDF で記述されるすべてのもの (URI で指定 ) プロパティ値リソース記述に用いられる, 特徴関係属性などプロパティの意味はスキーマにより記述 Creater Tanaka 13

14 RDF 記述 <rdf:rdf> <rdf:description about= <s:creator>tanaka</s:creater> </rdf:description> </rdf:rdf> ( リソースを値に持つRDF 記述 ) <rdf:rdf> <rdf:description about= <s:creator rdf:resource= v:name= Tanaka v: = tanaka@kyoto-u.ac.jp /> </rdf:description> </rdf:rdf> tanaka@kyoto-u.ac.jp Creater Name Tanaka 14

15 RDF Schema RDF 記述を解釈するための定義オブジェクト指向リソースのプロパティ定義クラス間の関係値の制約条件 ( 文字列数字値の範囲など ) クラス定義 Resource, Class, Property Type( タイプ定義 ),subclassof( クラス間の関係 ), subpropetyof( プロパティ間の関係 ) range( プロパティ値の範囲の定義 ),domain( プロパティを持つクラスを示す定義 ) 15

16 RDF Schema の例 <rdf:rdf xml:lang= ja > xmlns:rdf= http// xmlns:rdfs= <rdf:description ID= 自動車 > <rdf:type resource= /> <rdfs:subclassof rdf:resouce= rdf-schema#resource /> </rdf:description> <rdf:description ID= 乗用車 > <rdf:type resource= /> <rdfs:subclassof rdf:resouce= # 自動車 /> </rdf:description> 16

17 分類体系と推論ルール集オントロジ知識が知識体系の中でどこに位置づけられるか Web 上の記述は, 表現方法や語彙が異なる概念間の相互関係を定義することで意味的な関係付けを行う ( 上位関係, 同義関係 ) オントロジ記述言語 OWL クラス定義要素が満たすべき性質によってクラスを定義 (DefinedClass, PrimitiveCLass, EnumerationClass プロパティ定義定義域 ( クラス ) と値域 ( クラスあるいはデータ型 ) を与える対応付ける要素の数 17

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)) 記述の分散 PrimitiveClass(Person, slot(shoesize, range=xsd:decimal)) 18

19 OWL によるクラス階層の記述例動物 (Animal) は, 年齢 (age) を持つ動物は, オス (Male) とメス (Female) に分かれる人間 (Person) には, 配偶者 (hasspouse) をもつものもある男性 (Man) は, 人間かつオスである PrimitiveClass (Person, slot(hasspouse, range =Person, optional, siglevalued) Animal age PrimitiveClass (Male, supers (Animal)) PrimitiveClass (Femele, supers (Animal)) PrimitiveClass (Animal, slot(age, range =xsd:integer, required, singlevalued)) Person hasspouse Male age Female age DefinedClass (Man, supers(person, Male)) Man age hasspouse Disjoint (Male, Female) Individual(Ichiro, Man, (age, xsd:integer, 13)) 19

20 20

21 21

22 22

23 23

24 24

国立国会図書館ダブリンコアメタデータ記述

国立国会図書館ダブリンコアメタデータ記述 -------------------------------------------------------------------------------- Title: 国立国会図書館ダブリンコアメタデータ記述 Creator: 国立国会図書館 Latest Version: http://ndl.go.jp/jp/library/data/meta/2011/12/dcndl.pdf

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

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