Semantic Web 輪読会 2005年12月20日 濱崎雅弘 産業技術総合研究所 A Large Scale Taxonomy Mapping Evaluation Paolo Avesani(1), Fausto Giunchiglia(2), Mikalai yatskevich(2) (1) ITC-IRST (2) Dept. of Information and Communication Technology, University of Trento Semantic Web 輪読会 2005年12月20日 濱崎雅弘 産業技術総合研究所

Taxonomy mappingとは 二つの階層構造があったときに，対応する階層を発見する 利用例： 家電量販店のネット通販を統合したサイトを作ろう！ でも各ショップごとに分類が違うからカタログ作りも大変だ・・ 　　→mapping手法によって自動でカタログ統合が可能に 家電 家電 どのカテゴリが， どのカテゴリに対応？ 冷蔵庫 テレビ ラジオ 冷蔵庫 AV機器 液晶 プラズマ TV コンポ

本論文の目的 Taxonomy Mappingの各手法を比較可能にするために評価セットを提案 代表的な手法で評価セットをテストする データセット 性能評価手法 代表的な手法で評価セットをテストする

論文の章立て Introduction The Matching Problem The Evaluation Problem Building a Large Scale Mapping Dataset The Empirical Evaluation Discussion of Results Complexity Discrimination Ability Incrementality Correctness Conclusions

2 Matching Problem やりたいこと 部分は似ているが全体としては異なる構造を 持つ、２つの階層構造を統合したい

代表的なMatching手法 Syntactic matching Semantic matching ラベルの字面から類似度を測る WordNetなどの語彙体系を用いて、 概念間の類似および上位下位関係も測る

3 The Evaluation Problem さまざまな手法が提案されているが比較評価ができていないのが現状 本論文の提案 Webディレクトリを用いた 巨大な評価用データセットの作成 Matching結果に対する評価指標の作成

Matching結果に対する評価指標 データセットとしてWebディレクトリを考える 各概念（ディレクトリ）はインスタンス（文書）を持つ 一致する文書数から概念間の関係を計算可能であるという仮説に基づいて評価指標を作る

概念AとBが似ている度合い 一致している部分が多いほど0に近づく A B Equivalence ＝ A B

概念AがBの上位概念である度合い 概念Aと概念B、概念Aと概念Bの親、概念Bと概念Aの子、で共通している部分が多いと0に近づく Generalization ＝ Bの親 A B Aの子

概念AがBの下位概念である度合い 概念Aと概念B、概念Aと概念Bの子、概念Bと概念Aの親、で共通している部分が多いと0に近づく Specialization ＝ Aの親 A B Bの子

4 Building a Large Scale Mapping Dataset 評価用データセットとしてWebディレクトリを用いる Webディレクトリを用いる利点 それぞれが厳密なフォーマットにしたがっているわけではないがある程度の類似性があり、一般的なトピックをそれぞれカバーしている URLによって文書の同一性が保証される

評価データセットの作り方 対象とするWebディレクトリはGoogle、LookSmart、Yahooの３つ Step1. クロールしてデータを取得 Step2. ３つのディレクトリすべてが持っているURL以外は削除 Step3. URL数の少ないノードは削除（今回は10個以下） Step4. 使えそうなブランチを手作業で選択 Step5. 評価値を計算してノード間の関係を求める 三つの評価値を全ノードの組み合わせに対して計算し、 評価値を全体で[0,1]に正規化する。 閾値以下の評価値は削除する（今回は0.5） ある組み合わせに対して最も高い評価値が示す関係(類似、上位、下位)を、その組み合わせの関係とみなす

5 The Empirical Evaluation 複数の手法で実際に評価セットでテストする COMA S-Match Base line (適当につくったアルゴリズム）

COMA データスキーマの統合を目的とした，Matchingシステム 複数の手法を併用している点に特徴がある http://www.vldb.org/conf/2002/S17P03.pdf http://dbs.uni-leipzig.de/Research/meta-Dateien/COMA-vldb02.pdf

S-Match Step1：ラベルをシソーラスにマッピング Step2:ノードの概念を求める 例：Pictures → Picture、Wine and Cheese → Wine & Cheese Step2:ノードの概念を求める シソーラスにマッピングしたラベルを、現在地からルートまでさかのぼってつなげる Step3:ラベル間の類似度をシソーラスを使って計算 Step4:ラベル間の類似度からノード間の類似度を計算 http://drops.dagstuhl.de/opus/volltexte/2005/37/pdf/04391.GiunchigliaFausto1.Paper.37.pdf

Base line パス（を構成するラベル）の字面のマッチだけを使う 類似関係： 上位・下位関係： パスが字面も含めて同じ 一方のパスがもう一方の中に包含されている

結果

6 Discussion Results 提案する評価セットを4つの軸で評価する Complexity：問題として複雑かどうか Discrimination ability：手法ごとの特色が現れるか Incrementality：手法の弱点を発見できるか Corectness：評価の正確さ

6.1 Complexity COMAやS-Matchは70-80%のrecallと論文では報告されていたが、評価セットでは40%弱だった 問題は十分に難しかった

6.2 Discrimination Ability S-MatchとCOMAではそれぞれ発見できたペアが異なっている 各手法の差が現れた

6.3 Incrementality システムの問題発見に貢献できた S-Matchの例： 「Nazca_Lines」と「Nazca」が意味的に同じであることを発見できなかった アーティスト名をアルファベット順で分類するなど、概念的には変化のない分類の影響を受けてしまった その他１０件ほどの問題点がわかり、それを元にS-Match++を作成した システムの問題発見に貢献できた

6.4 Correctness 問題ない誤り率であった 人手で評価セットによるMapping結果を確認したところ、60%程度が分析できたところで2~3%の誤りがあった 十分に巨大なデータセットの場合、Annotatorでも分類結果は20％程度しか一致しない傾向がある 問題ない誤り率であった

7 Conclusion Taxonomy Matchingのための評価セットを提案 評価セットを四つの指標で検討し、妥当性を示した Complexity Discrimination ability Incrementality Correctness