情報アクセスと知的処理 (4)

検索モデル

本日のゴール

検索モデル

情報検索システムの核となるのは 検索モデル。文書検索システムの場合、

これらを何らかの方法で比較し、 検索質問に適合する文書を見つけ出す仕組みのことを検索モデルと呼ぶ。

索引比較によって検索を行う検索モデル

ここでは重要な2つだけを取り上げる。

ブーリアンモデル

ブーリアンモデルでは、検索質問を構成する語がそれぞれ、 その語を含む文書集合と対応している。 よって、論理演算子による演算は、文書集合どうしの集合演算と考えることができる。 例えば、語 t1 と 語 t2 の両方が出現する文書集合を得たい場合、 検索質問は次のようになる。

t1 AND t2

これは t1 を含む文書集合と、 t2 を含む文書集合との交わりを表している。 それぞれの集合を {d1, d3, d4, d5}、 {d1, d2, d3} であるとすれば、 交わりは {d1, d3} となる。

検索モデル

検索システムとしては、以下の仕組みが必要。

前者を実現する構造は、転置ファイル (inverted file) と呼ばれる。 「転置」という名の由来は、ある文書においてどんな語が出現しているか、の逆であるため。

文書ID出現頻度
t1d11
d35
d42
d53
t2d13
d23
d32

単純なブーリアンモデルでは出現頻度の情報は不要だが、 モデルに何らかの拡張をして頻度情報を利用することが多い。

ベクトル空間モデル

d1d2d3d4d5
t1|10523|
t2|03320|
t3|32040|
t4|66875|
t5|41400|
t6|05032|
d1 の文書ベクトル = [ 1 0 3 6 4 0 ]

ベクトル空間モデル

d1d2d3d4d5
t1|10523|
t2|03320|
t3|32040|
t4|66875|
t5|41400|
t6|05032|
d1 の文書ベクトル = [ 1 0 3 6 4 0 ]

ベクトル空間モデル

ベクトルの類似度

内積を使う方法や、コサイン (余弦) を使う方法など、さまざまなものが提案されている。 最もよく用いられているのはコサイン (コサイン類似度と呼ぶことも)。 コサインはベクトルのなす角に対応するものなので、 ベクトルの大きさ (ノルム) は無視することになる。 これは語の重みの絶対値によらず、 語と語の重みのバランスが似通っている文書を類似度が高いとする方法であるといえる。

ベクトル空間モデルでは、類似度により文書のランキングが可能。 一方、AND や OR のような論理演算はできない。

簡単な実装

  1. まず転置ファイルを用いて、検索質問の語を1つでも含む文書の集合を求める。
  2. その文書集合内の各文書に対して、検索質問との類似度をベクトル計算により求める。
  3. その類似度によりランキングする。

速度を度外視すれば、比較的簡単なプログラムで実現することができる。

実装例: WAMと連想検索 (1)

実装例: WAMと連想検索 (2)

実装例: WAMと連想検索 (3)

WAM を用いた連想検索エンジン GETA

rensou_description.png

文書で検索/再検索ができる。

実装例: WAMと連想検索 (4)

連想検索を利用したサービス

新書マップの開発スタッフには本学科の卒業生が参加 (完成後 Yahoo! Japan に転職)

Webページ検索: リンク構造解析

Webの検索エンジンでは、Webページ間のリンク構造を利用したランキングが行われている。 リンクを張っているのはWebコンテンツの作成者であるので、これは集合知の一種と考えることができる。

代表的アルゴリズム

PageRank: リンク構造解析

Google 検索が採用しているアルゴリズムは非公開であるが、その基礎となるアルゴリズムは PageRank(ページランク)と呼ばれ、広く知られている。

PageRank は「多くの良質なページからリンクされているページは、やはり良質なページである」 という考え方に基づいて、全てのページの重要度(=PageRank)を求める。 これは再帰的な関係であるため、行列計算が必要となる。

PageRank の概念図
PageRank の概念図 (Page et al. (1998) Figure 2 'Simplified Page Calculation' より引用(の引用))

HITSアルゴリズム: リンク構造解析

リンク構造解析を用いる手法の代表例として、PageRank より若干複雑な HITSアルゴリズムがある。 HITSアルゴリズムでは、重要なノードとしてオーソリティとハブの2種類を考え、 リンク集的なサイト(ハブ)を別に扱っているところに特徴がある。

参考サイト

リンク構造解析の応用

PageRank の「多くの良質なページからリンクされているページは、やはり良質なページである」 という考え方は、ハイパーリンクと似た関係にあるものに応用できる。

参考: ネットワーク分析

ソーシャルネットワークの分析では、リンク構造解析よりもネットワーク分析の手法が役立つ。

Webページ検索のランキング

リンク構造解析はページの良し悪しを教えてくれるが、検索語に対する良し悪しではない。

さまざまな指標を反映させてランキングをしている。

SEO

SEO (Search Engine Optimization; 検索エンジン最適化)

意味のある対策

不正な対策

不正に順位を操作したと見なされると検索結果から除外され「Google八分」となる。