狠狠撸

Linking and Building Ontologies
on Linked Data
Rahul Parundekar, Craig A. Knoblock, and Jose Luis Ambite.

University of Southern California,
Information Sciences Institute and Department of Computer Science.

International Semantic Web Conference 2011

SWIM Seminar 2013/02/19. Hiroyuki Inoue.

Outline
?背景
?提案手法
?実験と評価
?関連研究
?まとめ

背景
? Linked Data の Web の成長が著しい
? 幅広いドメインで 316億トリプル（2011年9月）
? 政府（42%），地理（19.4%），生命科学（9.6%），など…

? “辞飞濒:蝉补尘别础蝉”
? 同じ意味のリソース同士を接続するプロパティ
? 着実に増加している（LODクラウド中の10%）
? しかしオントロジレベルでの接続はあまり増えていない
? 190ソースのうち，15のみで利用されている

“辞飞濒:蝉补尘别础蝉”

Source A Source B

Ontology Level

No links
Populated Place City

Instance Level

owl:sameAs
Tsukuba City of Tsukuba

目的と問題
?目的: オントロジの連携を見つける，増やす
? 連携: alignments
? 連携は，Semantic Web における相互運用性に重要
? “Semantic Interoperability”
? 機械が推論，知識の発見，他の機械とやり取りするために必要

?問題: 接続されていないオントロジ
? 190のソースのうち，15だけ接続がある
? 既存の接続関係が包括的に満足できるものではないだろう

著者らのアプローチ
?Linked Data からオントロジの連携を自動生成
? LDにおける，インスタンス同士の等価接続
（”owl:sameAs”）を利用
? 集合論を用いて，概念同士の連携を見つける

?連携を見つけ出すための新しい概念の導入
? 拡張概念の導入
? “rdf:type” だけで得られるクラス区分では材料が足らない
? Restriction Classes

対象とするデータソース（1/2）
? Linked Geo Data (http://linkedgeodata.org/)
? Open Street Map から生成された約20億トリプルの地理空間データ
? 機械学習ベースのヒューリスティックを用いて，型情報，
空間距離，地名などが DBpedia にリンク

? GeoNames（http://geonames.org/）
? 約800万の地理情報．GeoNames Ontology による構造化
? “Feature”クラスのインスタンスで構成される，それぞれ
? “FeatureClass”（行政区域，有名な場所，など）と，
? “FeatureCode”（FeatureClassのサブカテゴリ）を持つ

対象とするデータソース（2/2）
? DBpedia (http://dbpedia.org/)
? Wikipedia から構造化情報を抽出した辞書，150万オブジェクト
? Linked Data の Web のハブとなる
? 今回は，“rdf:type” と info-box の情報だけ利用
? Linked Geo Data, GeoNames は “辞飞濒:蝉补尘别础蝉” でリンク

? Geospecies（http://lod.geospecies.org/）
? クラス分類の曖昧さを解決するための，生物学のタキソノミ
? DBpedia と “skos:closeMatch” でリンク

? MGIとGeneID（http://bio2rdf.blogspot.jp/)
? Mouse Genome Information と遺伝子ID（Gene ID）DB
? MGI インスタンスから GeneIDへ “bio2RDF:xGeneID” でリンク

Ontology Alignment Using Linked Data

提案手法
?概要
? データ分析と統計的手法の利用
? “Common Extension Comparison” アプローチの拡張
? 似たクラスのインスタンス同士でインターセクションをテストする
? オントロジマッチングの一手法

?特徴（Novel features）
? Linked Data の Web における等価接続を利用する
? クラス定義を “rdf:type” だけでなく，他の情報からも生成
? 生成したクラスの集合から，オントロジ間の連携を見つけ出す

连携の発见（概要）
データセットにおける全ての
インスタンスの集合
インスタンス集合 (featureClass=P)

インスタンス集合(rdf:type=City)

GeoNames DBpedia

Img(r1) r2

GeoNames における，ある制約?クラスのインスタンス集合が，
DBpediaにおける，ある制約?クラスのインスタンス集合に対応

Restriction Classes
?プロパティと値の組合せで定義される制約クラス
? “rdf:type” だけでは不十分なことがある
? クラス分類の粒度が，データセットで異なる
? GeoNames で場所の記述に用いられるクラスは “gn:feature”
? DBpedia には場所の記述に用いられるクラスがいくつもある
? 街（City），郡（County），州（State），国（Country），…

? そこで，リソースが持つプロパティとその値から
制約クラス（Restriction Classes）を作る

Restriction Classes の構築
?プロパティと値の冪集合から構築される
? 例）GeoNames における1リソース（Saudi Arabia）
? rdf:type = geonames:Feature（場所クラス） independent
political
? featureCode = geonames:A.PCLI （独立国家） entity
? featureClass = geonames:A （国，州，領域）

組合せが指数関数的に増えるので，
オントロジ間の連携を探す前に，
データに対して前処理，探索空間の削減を行う

データへの前処理
? １）現在対象としているクラスと関係ないものを削除

? ２）連携の生成に関係無さそうなプロパティを削除

? ３）インスタンスデータはRDBに格納する
? URIを主キーとして，1インスタンスを一行で格納する（?vector?）
? 多値のプロパティについては複数行に分けて格納する
? DISTINCT でプロパティ値を取るので，複数行に分割されても問題ない

? 等価プロパティ(?owl:sameAs?)でJoinすることで，
2つのオントロジから ?vector? の組合せを取得することができ
る（?instance pair?）

探索と枝刈り（1/3）
? Restriction class 同士の組合せで探索
[(pi1 = vij )(pk = vl2 )]
2

? 深さ優先探索，探索候補数: O(n2m2)
? n: 対象２ソースで，プロパティが多い方のプロパティ最大数
? m: 任意のプロパティの，重複を除いた最大インスタンス数

? 枝刈り（探索空間の削減）
? １）閾値で枝刈り
? ２）明らかに包含関係がある場合は探索しない
? ３）制約を緩める制約クラスの追加は行わない（探索しない）
? ４）（２ページ後で説明）

2)明らかに包含関係があるものは枝刈り

3)制約を緩めるクラスは追加しない

1)閾値で枝刈り

? 枝刈り４(a)）
? Restriction class を追加しても変化がない場合 r1 ?r2 = r1 (i.e.r1 ? r2 )

? 探索は辞書順で行う(b)

仮説の評価（スコアリング）（1/2）
? 確信度を計算して，得られた仮説を評価する
? 像 r1 を計算（I(r1)）
? ソース２において，ソース１と “辞飞濒:蝉补尘别础蝉” リンクで
“instance pair” を構成するインスタンス集合
? I(r1) および r2 を用いて P(recision), R(ecall) を計算
? 誤差を許容する，緩めの定義として R?,P? を用意

I(r1 )? r2 I(r1 )? r2
P= R=
r2 r1

仮説の評価（スコアリング）（2/2）
? 計算例
? Restriction class A(r1): “lgd:gnis%3AST_alpha=NJ”
? Restriction class B(r2):
? “dbpedia:Place#type=http://dbpedia.org/resource/City_(New_Jersey)”
? I(r ) = 39, r2 = 40,
1 I(r1 )? r2 = 39,
39 39
P' = = 0.97 ? 0.90, R' = = 1.0 ? 0.90
40 39

よって，AとBのRestriction classは equivalent と言える

暗黙の連携の排除
? 推移還元（Transitive reduction）

対象データと前処理の結果
? 対象データ

? 前処理の結果
? 連携の最小支持度(閾値)は ?10?

結果
? Source1, Source2 を設定し，連携を導出
? ?best matches?: P=1, R=1（の事を言っているのでは…）
? ?before?, ?after?: implied relations の削除前?後
? 暗黙の連携の削除により，結果の整理と，最も興味深い連携がよく分かった

考察
? 提案手法は暗黙の ?閉じた世界? を仮定する
? 実際の Linked Data がどうなっているのか
? インスタンスがオントロジとどう対応しているのか，把握できた
? ?閉じた世界?（データセットの内側）を利用することで上手くいった

? ?開けた世界? でやろうとしても
欠損したインスタンスのカテゴライズは困難
? １）まだ探索できていない，
? ２）探索されているが意図されてデータセットに含まれていない，
? ３）探索されているがミスでデータセットに含まれていない

? 数多くの連携（等価，包含）を見つけ出すことができた
? 実データを基に構築されているオントロジの構築，改善に貢献する

関連研究（1/2）
? Ontology Matching [12]
? terminological（術語的）: linguistic and IR techniques [11]
? structural（構造的）: graph matching [15]
? semantic（意味論的）: model-based

? FCA-merge algorithm [18]
? 二つのオントロジからラティスを作り，マージ
? （提案手法と異なり）マージにはエキスパート(ユーザ)が必要

? Duckham ら [10]
? 地理空間ドメインに対するオントロジの融合?連携手法
? （提案手法と異なり）存在するクラスしか考慮しない
? 一方，著者らは ?type? に限らない

関連研究（2/2）
? GLUE system [9]
? instance-based similarity approach
? インスタンスが持つラベル(テキスト)をクラス分類に用いる
? 他のオントロジの概念と比較して，属するか判定する
? （提案手法では）Linked Data の “辞飞濒:蝉补尘别础蝉” を利用する

関連研究（Linked Data関連）
? Brizerら [7]: インスタンスマッチング

? Raimondら [17]
? 音楽（アーティスト，レコード，トラックなど）に対して，
? 文字列，グラフマッチングを用いて，２つのDB間の連携を探す
? また，（提案手法と異なり）個人の音楽収集情報も利用する

? Nikolovら [2]
? 異なるリソースを ?owl:sameAs? の推移閉包でクラスタ分解
? あるクラスタ内では，全てのインスタンスが等価になるようにする
? それぞれのクラスタのインスタンスをリラベル
? 共通部分集合のサイズで近似値を計算して，クラスを等価とする
? クラスへの再割当てステップを繰り返し，より等価なリンクを生成

まとめ，今後の課題
? オントロジ間の包含?等価連携を見つけるアルゴリズムを提案
? 制約クラスの導入と，それらを組み合わせる
? 本稿では地理空間，動物のデータに対して自動で連携を発見
? しかし，他の一般的な Linked Data に適用可能である

? 今後の課題
? スケーラビリティの改善
? 仮説の連携を探索するパフォーマンスを向上させたい
? 前の研究（ソースからのモデル構築）と連携させたい
? クロスドメインなデータセットに対して適用したい
? 特に，生物医学なLinked Dataに対して

狠狠撸

Swim_2013_02_19_jpn

More Related Content

Swim_2013_02_19_jpn