情報検索のためのトピック適応型単語クラスタリング
綱川 隆司 y二宮 崇 zy
宮尾 祐介 x
辻井 潤一 xzy 東京大学 大学院情報理工学系研究科 コンピュータ科学専攻
z 科学技術振興機構
x 東京大学 大学院情報学環
ftuna, ninomi, yusuke, tsujiig@is.s.u-tokyo.ac.jp

1

はじめに

情報検索の分野において，クエリ（問い合わせ）に適合する文書を検索する際にキーワードマッチを用いると，クエリ中の単語を直接含まない文書を探し出すことができない．このため，クエリの各単語やその内容に関連する単語を新たにクエリに付け加えるクエリ拡張と呼ばれる手法が研究されてきた [1]．クエリ拡張手法の一つとして単語の共起情報を用いて自動的に構築されたシソーラ
スを用いる手法が挙げられる [2]．クエリに含まれる単語からシソーラスを引いて関連する単語をクエリに追加する．
このようなシソーラスは検索対象とする文書集合，あるいはその他の大量のテキストなどから自動的に構築されるが，その際にテキストがどのようなトピックを持っているかを考慮しないと，シソーラスに細かいトピックや分野といった情報が含まれず，クエリが求めるトピックに合致した単語が選ばれるとは限らなくなる．
本論文では文書クラスタリングを用いていくつかの文書クラスタを形成し，各文書クラスタごとに単語クラスタリングを行うことにより各文書クラスタのトピックに特化した単語クラスタを生成することを目指す．この際疎データ問題に対処するために，文書がクラスタに帰属する度合いを求めるファジィクラスタリング法を適用する．
さらに，単語クラスタを生成するための単語間の類似度を用いて，情報検索のクエリ拡張手法の一つである概念ベースクエリ拡張 [4] に文書クラスタの考えを導入して，その有効性を考察する．

2
2.1

背景

ji = (1 + log tf ji) idf i;
idf i = log(N=Ni):d

ただし，tf ji は文書 dj に単語 ti が出現した回数1，Ni は単語 ti が出現する文書の数とする．文~ d~0) は 2 つの文書ベクトル間書間の類似度 sim(d;の余弦で定義される:

0~ d~) =sim(d;~0d~  d:~jjd~0jjd

この文書ベクトルと文書間の類似度を用いて，

jFuzzy c-means 法 [3] は，クラスタリングの対象x が単一のクラスタに属するようにするのではなく，各クラスタ C への帰属度 Æ 2 [0; 1] をkjk求めるファジィクラスタリングの一種である．

k

Fuzzy c-means 法により各文書 d のクラスタ Cへの帰属度 Æ を求める．Fuzzy c-means 法のアjk

ルゴリズムは以下の通りである．
入力: クラスタ数 c，ファジィ化パラメータ m(>~j (j = 1; : : : ; n)．
1)2，文書ベクトル d
出力: 帰属度 Æjk (j = 1; : : : ; N ; k = 1; : : : ; c)，クラスタ中心 ~vk (k = 1; : : : ; c)．

jkjk

1. 文書 d のクラスタ C への帰属度 Æ (j =1; : : : ; N ; k = 1; : : : ; c) の初期値を適当に定める．

k を以下の式で更新する．
PN Æ m d~
j=1 jk j :~vk = PN
j=1 Æjk m

2. 各クラスタの中心 ~v

Fuzzy c-means 法を用いた文書クラスタリングj

文書集合を fd1; : : : ; dN g，文書に含まれる単語集合を ft1; : : : ; tM g とすると，文書 dj の特徴を表す文書ベクトル d~j = (dj 1; : : : ; djM ) は以下のように定義される:

1tf ji = 0 のときは dji = 0 とする．
2

本論文の実験では m = 1:5 とした．

jk (j = 1; : : :; N ; k = 1; : : : ; c) を以

3. 帰属度 Æ

クエリと単語 t の類似度を下の式で更新する．

82! 1 13 1>
c~X>
sim(dj ; ~vk0 )5><4~
sim(d;~v)
0
jkk =1
Æjk =>~j ; ~>(sim(dvk ) > 0)>:0~(sim(dj ; ~vk ) = 0)csimqt(q; t) = ~q mと定義すると，! ~MX~tit
simqt(q; t) =qi~ti~ti=1
MMX ~ti ~t X=qi=qi sim(~ti ; ~t):i=1 ~ti ~t i=1


Similarity Thesaurus

ij = (1 + log df ij ) itf j ;itf j = log(M=Mj ):ただし，df ij は単語 ti が文書 dj に出現した回
数3 ，Mj は文書 dj が含む異なり単語数とする．
w



単語間の類似度 sim(~t; ~t0) は，文書の場合と同様に以下の式で定義される．
sim(~t; ~t0) =2.3~t ~t0:j~tjj~t0j

iq = (1 + log tf )  idf :このクエリに対して，クエリの概念を表す仮想的qc を 2.2 節の ~ti を用いて以下のな単語ベクトル ~ように定義する．

MXqici=1

q =~
3



j j



jj j

単語 t をクエリ q に追加する場合は，simqt(q; t)の値を重みとして用いることができる．クエリ拡張に用いる単語を制限するために，閾値 T を定めて以下のように拡張クエリを求める．

e = (8qe1; : : : ; qeM );>q; t )< simqt(q; ti ) simqt(PM q i
qei =i=1 i>:0（それ以外）q~!
 T:

拡張したクエリ ~q+~qe を用いて，各文書 dj に対~q+~qe ) の値をスコアとしてし，s(dj ) = sim(dj ; ~ランク付けすることができる．

3 文書クラスタを用いた単語クラスタリン
3.1

本論文では概念ベースクエリ拡張 [4] と呼ばれる手法を用いて，前節の文書クラスタ別の単語間類似度による精度向上への有効性を確かめる．概念ベースクエリ拡張では，クエリをベクトル空間モデルを用いてベクトル化し，それに最も近い単語ベクトルを持つ単語をクエリに追加する．
クエリは文書で与えられることを想定しており，クエリ q に含まれる単語の重みベクトルをq = (q1; : : : ; qM ) で表す．各 qi は 2.1 節の文書ベ~クトルと同様に以下の式で定義される．

ij

グと情報検索概念ベースクエリ拡張

i



j

Similarity thesaurus [5] は単語クラスタリングにおける単語類似度を定義する一手法であり，ある2 つの単語 t; t0 に対し，t の各文書における出現頻度のベクトルと t0 の各文書における出現頻度のベクトルの余弦を t; t0 間の類似度とする．
単 語 ti の 特 徴 を 表 す ベ ク ト ル ~ti=(wi1; : : : ; wiN ) を次の式で定める．

j

4. クラスタ中心が変化しなくなるまで Step 2,3 を繰り返す．
2.2~t~jtj

ii~t:j~tj

df ij = 0 のときは wij = 0 とする．

文書クラスタを用いた単語クラスタリング

文書クラスタリングの結果を用いるときは，単語ベクトル ~ti を次のように変形する．文書 dj の文
書クラスタ Ck への帰属度を Æjk とすると，文書クラスタ Ck における単語ベクトル ~tik は，( )k(k )(k )i = (wi1 ; : : : ; wiN );(k )wij= Æjk (1 + log df ij ) itf j :~t(k) ~t0(k)で表される．類似度は simk (t; t0 ) =で~t(k) ~t0(k)~t( )jjjj

求められる．
各文書クラスタ Ck について異なる類似度 simkが得られるため，それを用いた単語クラスタリン
グの結果もそれぞれ異なったものになり，文書クラスタの性質を反映した単語クラスタを生成できると考えられる（図 1 参照）．
各文書が単一のクラスタに属すハードクラスタ
リングを用いた場合，すなわち Æjk 2 f0; 1g の場
合は，各文書クラスタ内に出現する単語のみでそᢥᦠ㓸ว

表 1: テストセット

accumulator

テストセット

内容

文書数

クエリ数

multiplier

CACM

コンピュータ科学
図書館学
図書館学
医学
電子工学

3204

5214604160043910333011429

93

ISI
LISA
MED
NPL

accumulator

accumulator
multiplier

multiplierᢥᦠ䉪䊤䉴䉺䌁

表 2: 平均適合率
c は文書クラスタ数．ideal はセット B の各文書に対してもとのテスト集合に対応するクラスタを割り当てた場合．

ᢥᦠ䉪䊤䉴䉺䌂

条件
クエリ拡張なし概念ベースクエリ拡張
スコア s0 ，c = 1
スコア s0 ，c = 5
スコア s0 ，c = 10
スコア s0 ，ideal
スコア s00 ，c = 1
スコア s00 ，c = 5
スコア s00 ，c = 10
スコア s00 ，ideal（加算器）と multiplier （乗算器）を類義語として扱える分野と扱えない分野が存在するとき，文書クラスタごとの単語クラスタリングによってその特徴をとらえることができる．

accumulator

図 1: 文書クラスタ別の単語クラスタリング
れぞれ単語クラスタリングを行ったのと等価になる．この場合は全文書集合に対する単語クラスタリングに比べてデータ量が少なくなり生成される単語クラスタの質が落ちる可能性がある．ソフトクラスタリングを用いれば，データ量を保ったまま文書クラスタの性質を単語クラスタに反映させることが期待できる．
3.2

概念ベースクエリ拡張において拡張されるクエリ
qe は 文書クラスタごとに異なる．各文書クラス~
タ Ck に対する simk (t; t0 ) を用いた拡張クエリを(k )qe とする．
~q; ~vk ) をクエリと各文書クラスタの関連度 sim(~用いて拡張クエリの重み付けを行うと式 (1) が得られる．

!
c
X(k )
q+
~sim(~q; ~vk )~
qe:
(1)
k=1
各文書のクラスタへの帰属度 Æjk を考慮し，文s0 (dj ) = d~j 

書とクエリが同じトピックに属するときにスコアを大きくするよう修正すると，(2) が得られる．

cXj Æjk sim(~q; ~vk):
k=1

j4

B
0.05010.23380.06490.23750.06470.24070.06540.23800.0651|

0.0676

0.23750.06470.22670.06270.21290.0589|0.08082 つの実験用セットを作成して情報検索の実験を行った．
A. CACM

概念ベースクエリ拡張への適用

s00 (d ) = s0 (d )A
0.1903(2)

実験

前節で導いたスコアリング法の有効性を確認するため，表 1 に示したテストセットから以下のB. CACM + ISI + LISA + MED + NPL

テストセットに含まれる単語のうちストップワードはあらかじめ取り除いた．クエリのうちそのクエリに対する正解の文書数が 0 であるものは除いた4 ．拡張前のクエリによるランク付けと，s0 , s00 によるランク付けを文書クラスタ数を変化させて精度評価を行った．評価は再現率がf0; 0:1; 0:2; : : :; 1g の 11 点についての適合率で行い，その平均値を平均適合率として算出した．ク
エリ拡張の閾値 T は，各実験においてそれぞれ平均適合率が高くなる値を選んだ．
テストセット A, B に対して，クエリをそのまま検索に用いる手法，概念ベースクエリ拡張に基づく手法，スコアとして s0 ; s00，文書クラスタ数として c = 1; 5; 10 を用いる手法の各々の平均適合率を表 2 に示した．また各テスト集合をそれぞれ文書クラスタとみなした場合の平均適合率も示した．再現率の各点における適合率のグラフは図2, 3 に示した．
4

表 1 のクエリ数は取り除いた後の数を表す．

precision

0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0orig. query
concept based
c=1
c=5
c=10

00.2

0.4

0.6

0.8

1

precision

recall
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0orig. queryc=1
c=5
c=105 まとめ

00.2

0.4

0.6

0.8

1recall

図 2: セット A の適合率-再現率カーブ（上段：スコア s0 ，下段：スコア s00）

0.2
orig. query
concept based
c=1
c=5
c=10
ideal

0.15
precision

テストセット A および B において，拡張前のクエリの適合率に対して概念ベースクエリ拡張を用いた方が適合率が高くなった．文書クラスタリ
ングを適用した例では，スコア s0 を用いた場合は平均適合率に大きな差は見られず，スコア s00を用いた場合は適合率の低下が観測された．
一方で，文書クラスタリングの代わりに各テストセットを文書クラスタとみなした場合では，スコア s00 について比較的改善がみられた．これは文書クラスタリングをより精密に行うことで精度を改善できる可能性を示していると考えられる．
クエリ拡張の最適な閾値 T はスコアリング手法やクラスタ数，テスト集合によって大きく変化するため，これを効率よく発見するのは今後の課題である．

0.1

本論文では文書のファジィクラスタリングを用いて文書集合に対して各トピック（文書クラスタ）への帰属度を求め，それを用いたトピックに特化した単語クラスタの生成，および概念ベースクエ
リ拡張を用いた情報検索への応用を試みた．情報検索での実験では文書クラスタリングによる効果ははっきりと現れなかったが，文書クラスタリングの精密化により効果が出る可能性もある．今後の課題として，式 (1), (2) によるスコアリング
では全ての文書に対して同じクエリの拡張を行っているが，クエリの拡張を文書ごとに行うことによって，各文書の性質を反映したクエリ拡張による精度の向上を目指したい．

参考文献[1] Ricardo Baeza-Yates and Berthier Ribeiro-Neto.

0.05

Modern Information Retrieval.

ACM

Press/

Addison-Wesley, 1999.

00

0.2

0.4

0.6

0.8

1orig. query
c=1
c=5
c=10
ideal

0.15

Exper-thesaurus

con-

Proceedings of the ACM-SIGIRConference on Research and Development in Information Retrieval, pages 77{88, 1992.
struction.

0.2

precision[2] Carolyn J. Crouch and Bokyung Yang.
iments in automatic statisticalrecall

In[3] J. C. Dunn.

A fuzzy relative of the ISODATA

process and its use in detecting compact well-0.1

separated clusters.

Journal of Cybernetics, 3:32{57, 1974.

0.05[4] Yonggang Qiu and Hans-Peter Frei.

Concept-

Proceedings of SIGIR93, 16th ACM International Conference on Research and Development in Information Retrieval, pages 160{169, Pittsburgh, US, 1993.
based query expansion. In000.20.40.6

0.81recall

図 3: セット B の適合率-再現率カーブ（上段：スコア s0 ，下段：スコア s00）

[5] P. Schauble and D. Knaus. The various roles ofProceedings of the 16th
Annual Conference of the \Gesellschaft fur Klassi kation e.V.", pages 282{290, 1992.
information structures. In