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の各手法を比較可能にするた めに評価セットを提案 – データセット – 性能評価手法 • 代表的な手法で評価セットをテストする 論文の章立て 1. 2. 3. 4. 5. 6. Introduction The Matching Problem The Evaluation Problem Building a Large Scale Mapping Dataset The Empirical Evaluation Discussion of Results 1. 2. 3. 4. Complexity Discrimination Ability Incrementality Correctness 7. Conclusions 2 Matching Problem • やりたいこと – 部分は似ているが全体としては異なる構造を 持つ、２つの階層構造を統合したい 代表的なMatching手法 • Syntactic matching – ラベルの字面から類似度を測る • Semantic matching – WordNetなどの語彙体系を用いて、 概念間の類似および上位下位関係も測る 3 The Evaluation Problem • さまざまな手法が提案されているが比較評価 ができていないのが現状 • 本論文の提案 – Webディレクトリを用いた 巨大な評価用データセットの作成 – Matching結果に対する評価指標の作成 Matching結果に対する評価指標 • データセットとしてWebディレクトリを考える – 各概念（ディレクトリ）はインスタンス（文書）を持つ – 一致する文書数から概念間の関係を計算可能であるとい う仮説に基づいて評価指標を作る 概念AとBが似ている度合い • 一致している部分が多いほど0に近づく A B A B Equivalence ＝ 概念AがBの上位概念である度合い • 概念Aと概念B、概念Aと概念Bの親、概念Bと概念A の子、で共通している部分が多いと0に近づく A B Generalization ＝ Bの親 A B Aの子 概念AがBの下位概念である度合い • 概念Aと概念B、概念Aと概念Bの子、概念Bと概念A の親、で共通している部分が多いと0に近づく A B 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：ラベルをシソーラスにマッピング – 例：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
© Copyright 2024 ExpyDoc
