Hello World!!

IIR10章まとめ

勉強 IIR

10章では、XMLにおける探索において。

主なサーチエンジンは、構造化されていないテキストが検索対象だが、ここでは、構造化されているドキュメント(ここではXML)における検索を考える。

以下の例で説明する。

 
Shakespeare 
Macbeth 
 
 
Macbeth’s castle 
Will I with wine and wassail ...

DOM

XMLデータをパースして、メモリ中に木構造を生成するものを、DOM(Documents Object Model)という。

以下、上記の例からDOMにより生成された木構造である。

XPath

XMLドキュメントの特定の部分を指定する言語構文。

例えば、

act/scene

と指定すると、以下のようにたどる。

Schema

XMLドキュメントの論理的構造を定義する言語。

DTD(Document Type Declaration)が標準的。

XML検索

1.ドキュメントのどの部分を検索結果として返せばよいのか

どの部分がクエリにマッチする結果であるかを決めるのは難しい。

そこで、以下のstructured document retrieval principleというものがある。

検索システムは、常にクエリに対応して最も明確な部分を結果として返すべきである。

しかし、実際にこの原則を満たすようにアルゴリズムを実装できるかどうかは別問題。

2.ドキュメントのどの部分をインデックスにするか

以下の4つのアプローチがある。

オーバーラップのない擬似的なドキュメントへとまとめる

欠点は、1つの木が他と切り離されているため、それだけでは意味をなさない可能性があること。

トップダウン

根要素(root elements)のみを扱い、検索結果への後処理で子要素を見付ける。

欠点は、ある要素の適合性とその子要素の適合性は一致しないことがあること。

ボトムアップ

トップダウンとは逆に、葉要素(leaf elements)のみを扱い、検索結果への後処理で親要素を見付ける。

欠点は、ある要素の適合性とその親要素の適合性は一致しないことがあること。

全ての要素をインデキシング

欠点は、意味のあまりない要素が多いため、かなり冗長になること。

以上4つのアプローチにはそれぞれに欠点がある。

3.ネスト要素をどうするか

ネスト要素は冗長性を引き起こすため、要素集合を制限するのが普通である。

VSM

上で見たように、XMLの検索には様々な問題点があるので、これらにVSMで対応する。

VSMの各次元を、XMLパス $c$ とターム $t$ のペア[tex: ]に拡張する。

すなわち、これまでのようにタームのみに着目するのではなく、構造にも着目する。

構造の類似度は以下のように求める。

$c_q$ : クエリパス
$c_d$ : ドキュメントパス
$|c_q|$ : クエリパス上のノード数
$|c_d|$ : ドキュメントバス上のノード数

具体的に以下の例で考えてみる。

破線は、その間に任意のノードを挿入可能であることを意味する。

$C_R$ は以下のようになる。

$C_R(c_{q_3}, c_{d_2})$ = 4/4 = 1.0
$C_R(c_{q_4}, c_{d_3})$ = 0
$C_R(c_{q_4}, c_{d_2})$ = 3/4 = 0.75
$C_R(c_{q_4}, c_{d_3})$ = 3/5 = 0.6

コサイン類似度にこの $C_R$ を加味すると、以下のようになる。

XML検索の評価

ここでは、XMLにおける標準的なベンチマークであるINEX(INitiative for the Evaluation of XML retrieval)について説明する。

INEXには以下の2つのタイプがある。

CO(content-only)

ドキュメントの内容のみに着目する。言ってしまえば今まで通り。

CAS(content-and-structure)

ドキュメントの内容と構造に着目する。当然CAより評価は複雑になる。

CASでは、内容と構造の2次元で適合性を評価する。

まず、内容(rel)は以下の4段階に分ける。

3…非常に適合
2…まあまあ適合
1…少し適合
0…不適合

次に、構造(cov)を以下の4段階に分ける。

E…メイントピックをとらえており、情報量が十分
S…メイントピックはとらえているが、情報量が不十分
L…関係のあるトピックはとらえているが、メイントピックではない
N…関係のあるトピックをとらえていない

これらの情報を組み合わせて、以下のようにQを求める。

そしてこのQの値を、適合率・再現率・F値などの導出に用いる。