情報システム基礎論2：第 12回 (担当：古賀文書の類似検索 1 文書の

情報システム基礎論２：第 12 回 (担当：古賀)
文書の類似検索
2014 年 7 月 8 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
文書の類似検索
1
この問題は文書データベース S が与えられた時に、クエリ文書 q に類似する文書を探す問題である。こ
こで「類似する」とは「同じ話題を取り扱っている」程度の類似性を想定する。S に含まれる文書数を n
とし、T1 , T2 , · · · , Tn を S の要素とする。直感的には q と共通の単語を多く含む文書を見つければよい。類
似検索の手順は以下のようになる。
1. 各文書をベクトルとして表現
2. ベクトル間での類似検索により、類似文書を発見
文書特徴のベクトル表現
2
2.1
文書からの単語情報抽出
文書は含まれる単語によって、性質を特徴づけできる。そこで、文書 (T とする) の単語情報をあらかじ
め抽出しておく。
• 形態素解析: 日本語では文章から単語の切れ目を見つけるのが難しい。そこで形態素解析により文
書を単語に分割する。代表的な形態素解析ソフトウェアとして mecab がある。
http://mecab.googlecode.com/svn/trunk/mecab/doc/index.html
例： mecab の実行結果
直感名詞, サ変接続,*,*,*,*, 直感, チョッカン, チョッカン
的名詞, 接尾, 形容動詞語幹,*,*,*, 的, テキ, テキ
に助詞, 格助詞, 一般,*,*,*, に, ニ, ニ
は助詞, 係助詞,*,*,*,*, は, ハ, ワ
q 名詞, 固有名詞, 組織,*,*,*,*
と助詞, 格助詞, 一般,*,*,*, と, ト, ト
共通名詞, サ変接続,*,*,*,*, 共通, キョウツウ, キョーツー
の助詞, 連体化,*,*,*,*, の, ノ, ノ
単語名詞, 一般,*,*,*,*, 単語, タンゴ, タンゴ
を助詞, 格助詞, 一般,*,*,*, を, ヲ, ヲ
多く名詞, 副詞可能,*,*,*,*, 多く, オオク, オーク
含む動詞, 自立,*,*, 五段・マ行, 基本形, 含む, フクム, フクム
文書名詞, 一般,*,*,*,*, 文書, ブンショ, ブンショ
を助詞, 格助詞, 一般,*,*,*, を, ヲ, ヲ
見つけれ動詞, 自立,*,*, 一段, 仮定形, 見つける, ミツケレ, ミツケレ
1
ば助詞, 接続助詞,*,*,*,*, ば, バ, バ
よい形容詞, 非自立,*,*, 形容詞・アウオ段, 基本形, よい, ヨイ, ヨイ
。記号, 句点,*,*,*,*,。,。,。
• ステミング (stemming): 英語では名詞の複数形や動詞の過去形など、同じ単語の語尾のみが異な
ることがある。文書を特徴付けする際に、これらを違う単語として扱うのは得策ではない。これら
を同じ単語と見なせるように、語幹を取り出す。
例：’fishing’, ’fished’ ’fisher’ → fish
日本語の場合は活用形の違いを無視して、同じ単語とみなすなどがステミングの例。
• Stop Word の除去:
– 日本語の助詞 (て、に、を、は)・助動詞 (です、ます、だ)・代名詞・接続詞
– 英語の冠詞 (a, the)、前置詞 (before, after)、接続詞 (but, and)
などはほとんどすべての文書に出現し、文書を識別する手がかりにならない。このような単語を Stop
Word と言う。Stop Word の除去は文書解析の重要な前処理の 1 つである。英語の Stop Word のリ
ストの入手は容易。
• (S の中で) 多くの文書に出現する単語、出現頻度の極端に少ない単語の除去:
– Stop Word 以外であっても S のほとんどの文書に出現する単語は、文書の特徴付けに貢献し
ない。 – 逆に出現頻度が極端に少ない単語はきわめて特殊な単語であり、クエリ文書に含まれない可能
性が高い。
よって、これらの単語を除去する。
上記の過程を経て残った単語の集合 VT を T の索引語と呼ぶ。
2.2
Bag-of-Words モデル
Bag-of-Words モデルは代表的なテキスト表現モデルである。文書 T を T が含む単語の集合 (つまり VT )
として表現する。文法や単語の出現順序を考慮しない非常に単純なモデルであるが実用性は高い。
例： T =”Study at the graduate school covers a wide range of subjects” の集合表現は
{study, graduate, school, cover, wide, range, subject}
“at”, “the”, “a”, “of” は Stop Word として除去。
2.3
文書のベクトル表現
定義 1 Vocabulary =
n
[
VTi : S の全文書の索引語の和集合。
i=1
2
定義 2 d = |Vocabulary|: S の全文書の索引語の総種類数。出現頻度が極端に多い/少ない単語を除去して
d は数千程度の値にすることが多い。
• wj ∈ Vocabulary: j 番目の索引語 (1 ≤ j ≤ d)。
文書 Ti は d 次元ベクトル ai = (v1 , v2 , · · · , vd ) として表現できる。代表的なベクトル表現法は 2 種類。
1. TF 法 (Term Frequency): 単語の出現頻度によって文章を特徴付ける。
vj =
要素の合計
Pd
j=1 vj
文書 Ti における単語 wj の出現回数
Ti に含まれる総索引語数
= 1 となるように正規化し、文書特徴が文書長に影響されることを防ぐ。
2. TF·IDF 法 (Term Frequency· Inverse Document Frequency)
vj = wj の TF × wj の IDF.
定義 3 (単語 w の Inverse Document Frequency) w が出現する文書の割合 (Document Frequency)
の逆数。多くの文書に出現し、文書識別に貢献しない単語の影響を小さくすることが目的。
w の IDF = log
n
.
w が出現する文書数
• w の IDF が低い＝ w の DF が高い ⇒ 多くの文書に出現するので文書識別に役立たない
• w の IDF が高い＝ w の DF が低い ⇒ 少ない文書にのみ出現するので文書識別に役立つ
例：表 1 は 4 つの文書 S = {T1 , T2 , T3 , T4 } に対する単語の出現回数を示す。
表 1: 文書集合 S
T1 T2 T3
w1 =weather
w2 =London
w3 =money
w4 =beer
3
3
0
4
3
0
4
3
4
0
16
0
T4
0
0
5
5
総単語数 10
10
20
10
• 文章 Ti の TF 法によるベクトル表現 (1 ≤ i ≤ 4)。
a1 = (0.3, 0.3, 0, 0.4), a2 = (0.3, 0, 0.4, 0.3), a3 = (0.2, 0, 0.8, 0), a4 = (0, 0, 0.5, 0.5)
• 文章 T1 の TF·IDF 法によるベクトル表現
w1 の DF=3, w2 の DF=1, w3 の DF=3, w4 の DF=3。よって、
4
4
a1 = (0.3 log , 0.3 log 4, 0, 0.4 log ).
3
3
London は T1 にしか現れないので weather よりも重み大。weather は 3 つの文章に出現し、T1 を識
別する手がかりとしては London より弱い。
3
クエリ q に対する類似検索
3
まず q から索引語を抽出し、d 次元ベクトル aq として表現する。q と Ti との類似度 sim(q,Ti ) を、2 つ
のベクトル aq と ai の類似度として計算し、S から類似度が高い文書を返す。
3.1
ベクトル間類似度
cos 類似度がよく使われる (式 (1))。cos 類似度は 2 つのベクトルの向きがどれだけ一致するかを表す。
sim(q,Ti ) =
aq · ai
.
|aq ||ai |
(1)
cos 類似度に対しては Locality-Sensitive Hashing が知られている。つまり、ハッシュテーブルを使って
類似度計算回数を削減することにより、検索を高速化可能。
4

Download Report