DEIM Forum 2009 C4-3

関連単語抽出アルゴリズムを用いたクエリ拡張
大石 哲也†

峯恒憲††

長谷川隆三††

藤田博††

越村 三幸††† 九州大学大学院システム情報科学府 〒 819–0395 福岡県福岡市西区元岡 744†† 九州大学大学院システム情報科学研究院
E-mail: †oishi@ar.is.kyushu-u.ac.jp
あらまし Web 検索では，検索エンジンによって得られた結果がユーザの必要としている情報ではないことがしばしばある．この問題を解決する一つの方法として検索エンジンに与えるクエリを改善するクエリ拡張がある．クエリに含まれる語としてユーザの意図する適切な語を生成し追加することで Web 検索結果の改善に大きな効果がある．本
稿では，ユーザの意図する語を生成するための方法として，センテンス間の距離に注目した関連単語抽出アルゴリズ
ムを提案する．このアルゴリズムは重要な語の近くに出現する単語は重要であるという考えに基づいている．さらに，
このアルゴリズムを適合性フィードバックの一手法である RSV と組み合わせることで，検索エンジンを利用した初期
検索結果の検索精度の改善に役立つこと，その結果は RSV 単独で行った場合よりも検索精度が向上することを実験に
より示す．
キーワード

適合性フィードバック，クエリ拡張，Web 検索

A Method for Query Generation Using the Related Word Extraction
Algorithm
Tetsuya OISHI† , Tsunenori MINE†† , Ryuzo HASEGAWA†† , Hiroshi FUJITA†† , and Miyuki
KOSHIMURA††† Graduate School of Information Science and Electrical Engineering, Kyushu University
Motooka 744, Nishi-ku, Fukuoka-shi, Fukuoka-ken, 819–0395, Japan†† Faculty of Information Science and Electrical Engineering, Kyushu University
E-mail: †oishi@ar.is.kyushu-u.ac.jp
Abstract When searching for information a user wants, search engines often return lots of results unintended by
the user. Query expansion is a promising approach to solve this problem. In the query expansion research, one of
big issues is to generate appropriate keywords representing the user’s intention. This paper proposes the related–
word-extraction-algorithm (RWEA) which pays attention to the distance between sentences where keywords in theoriginal query appear. The RWEA is based on the idea that a word nearby important words is also important. We
conducted several experiments to illustrate the validity of the RWEA. The results promise the eﬀectiveness of the
RWEA for improving search results.
Key words Relevance Feedback, Query Expansion, Web Retrieval

1. は じ め にを取得できないことがしばしばある．その一つの理由に，ユー
ザが検索に利用するキーワード（以下，クエリ）に曖昧さがあ

有用な情報の宝庫である World Wide Web (以下，Web) は，り，そのため検索エンジンがユーザの意図を特定することが困

現在，研究や仕事で利用するユーザだけでなく，一般のユーザ

難であることが挙げられる．さらに，検索エンジンから得られによっても日常的に利用されている．たとえば何か物事を調べる情報が膨大で，ユーザがすべての情報を閲覧することが困難る際には，書籍を閲覧する前に，検索エンジンを利用することであるためである．このような事情から，ユーザが必要とするが一般的となってきている．

情報が，必要としない多くの情報の中に埋もれてしまい，必要

しかし検索エンジンを利用しても，ユーザが必要とする情報とする情報を見つけることができない結果を招いている．

ユーザが求める検索結果を提示する方法の一つとして，検索

大石ら [4] は，ユーザのスケジュールを考慮した Web 検索シエンジンに与えるキーワードを増やすクエリの拡張が考えられステムを提案した．このシステムは，ユーザがあらかじめ入力

る．一般に検索エンジンに複数のキーワードを与えると ANDしておいたスケジュールを解析し，それを基に Web 検索を行検索を行うので，検索結果のページ数を削減できる．もしユーい，ユーザの状況に合わせた検索を自動的に行う．この中で，

ザが調べたい事柄に関連する複数の適切なキーワードを検索

スケジュールを解析する部分に本稿で提案する関連単語抽出ア

エンジンに与えることができれば，適切なページをユーザに提ルゴリズムと類似のアルゴリズム（旧アルゴリズムと呼ぶ）が示できる．しかし調べたい事柄に関連する適切なキーワードを適用されている．具体的には，スケジュール入力の際，ユーザ

ユーザが検索エンジンに必ずしも与えることができるとは限らにはそのスケジュールのタイトルと詳細を入力させ，それを旧ない．

アルゴリズムによって解析して関連単語を発見する．その際，そこで本稿では，クエリ拡張を行うための新たな手法として，

旧アルゴリズムで必要となるキーワード群にはスケジュールのクエリ中のキーワードと関連性の強い語を抽出する関連単語抽

タイトルを，関連するテキストにはその詳細を用いている．こ出アルゴリズムを提案する．つぎに，このアルゴリズムの有効れにより，ユーザの状況に合わせた検索要求に合致した文書を性を示すために，新たなクエリ拡張システムを提案する．提案

検索結果の上位に表示することに成功している．本稿で提案すシステムでは，適合性フィードバック手法である Robertson’s

るアルゴリズムと旧アルゴリズムとの違いは，旧アルゴリズム

Selection Value (RSV) [3] での単語の重みづけに，この関連単が語と語の間の距離に着目して，語の有用度評価を行っていた

語抽出アルゴリズムを用いて単語の抽出と評価を行い，これをのに対して，提案アルゴリズムでは，文間の距離に着目してい基にクエリ拡張を行う．

ることが挙げられる．

このシステムの有効性を示すため，2 つの比較実験を行った．まず，提案システムと RSV だけを利用したクエリ拡張を

3. システムの概要比較した．その結果，RSV だけを利用した場合よりも平均精度

我々の提案するシステムの処理の流れは以下の通りである．

（MAP）が高くなった．次に，提案システムとオリジナルのク

3. 1 クエリの入力

エリを利用した結果を比較した．このとき，オリジナルのクエ

ユーザがシステムにクエリ（検索単語）を入力する．

リが，平均精度 0.8 以下と曖昧性が強い場合には，提案システ

3. 2 適合文書，不適合文書の決定

ムの方が平均精度が高くなるという結果を得た．

ユーザにクエリを入力してもらい，クエリを既存の検索エン以下，2 節では関連研究について紹介し，3 節では提案シスジンに与えることで，文書を取得する．ここで取得した文書を，テムの概要について述べる．4 節では関連単語抽出アルゴリズ

ユーザに評価をしてもらい，適合文書，不適合文書を決定する．

ムとそれを用いた単語の有用度算出方法について述べ，5 節で適合文書とはユーザの検索要求に合致している文書で，不適合実験結果について議論する．

文書とはユーザの検索要求に合致しない文書のことである．

2. 関 連 研 究

3. 3 関連単語の候補を抽出
3. 2 節で取得した文書から関連単語の候補となる語を高速形

現在までに，関連単語の抽出やそれを利用した検索システム

態素解析システム MeCab [12] を用いて抽出する．MeCab は，に関する研究がいくつか行われてきた．例えば，大塚と喜連

文を与えると形態素に分解し，品詞，読み，活用などの情報を

川 [5] は大規模なアクセスログから関連語を抽出する研究を行っ

返すシステムである．

た．彼らは，統計的に偏りなく抽出されたユーザの Web 検索

例えば，「関連単語を抽出」という文は “関連”，“単語”，“を”，の際の検索単語とそれによって閲覧したページを解析すること“抽出” と分解される．この場合，本システムでは品詞が名詞でで，関連単語を得た．この研究は，既存の検索エンジンで用いある語のみを抽出する．つまり，この例では，“関連”，“単語”，ている不特定多数のユーザによって検索された頻度や，クリッ“抽出” の 3 語が抽出される．しかし，MeCab では “関連単語”

クされた結果などを組み合わせて関連語を提案する方法と同等のような複合語は各単語に分解されてしまうため，それらの単またはそれ以上の精度を示している．

語を再び結合し，連結語として抽出する．

岡部と山田 [6] は，ユーザからの最小のフィードバックによ3. 4 関連語の有用度を算出

り検索単語の拡張を行い，検索効率の向上を図ったシステムを

3. 3 節で抽出した語に対して，関連単語抽出アルゴリズム

提案した．このシステムはトランスダクティブ学習という機械（RWEA）と Robertson’s Selection Value（RSV）を用いて関学習法を用いて実現されている．この手法により，トランスダ

連語としての有用度を算出する．有用度の算出に用いられていクティブ学習を用いない従来手法と比べ再現率が約 0.07 向上

る RWEA は，各単語の抽出元となるセンテンス間の距離に着している．正田ら [2] は，ユーザが与えたクエリでの検索結果目している手法であり，4. 1 節で詳しく説明する．また，RSVの上位 R 件を適合文書，それ以下を不適合文書として RSV を

は適合文書，不適合文書それぞれの出現頻度に着目している手用いてクエリ拡張を行い，新たなクエリの重みにより初期の検法であり，4. 2 節で説明する．

索結果をソートする方法を提案している．この研究で，RSV な

3. 5 拡張クエリの生成

ど実験で用いたパラメータの最適な組み合わせを発見し，その組み合わせを用いた結果，精度は向上している．

3. 4 節の 2 つの手法を用いて計算された有用度を基に拡張ク
エリを生成する．拡張クエリとは，ユーザが与えたクエリを基表1に拡張されたクエリである．

距離による単語の評価例

キーワード K

AB

テキスト T

AGB

EG

AFC

FH

DE

BVA (tj )

5

4

3

2

1

体的には，有用度の高い語から順に，ユーザが与えたクエリにBVB (tj )

5

4

3

2

1

数語追加したものを拡張クエリとする．

BVA (tj )

3

4

5

4

3

BV (tj )

13

12

11

8

5

例えば元のクエリが “A” と “B” であるときに，拡張クエリとは元のクエリに “C” を追加した “A”，“B”，“C” である．具3. 6 検索結果を提示
3. 5 節で得られた拡張クエリを既存の検索エンジンに与える．
その検索結果をユーザに提示する．

4. 関連単語の有用度

表 2 出現位置 j での期待値 EBV (j) とそれを用いた評価値 EBV (tj )の例
キーワード K

AB

テキスト T

AGB

EG

AFC

FH

DE

本節では，関連単語の有用度の算出に用いる 2 つの方法にBV (tj )

13

12

11

8

5

ついて述べる．1 つは関連単語抽出アルゴリズムで，もう 1 つ

EBV (j)

3

3.6

3.8

3.6

3

EBV (tj )

4.33

3.33

2.89

2.22

1.67

は Robertson’s Selection Value である．以下，これらの説明をする．

4. 1 関連単語抽出アルゴリズム

れらを順に並べたものである．各ブロック内はそのセンテンス

4. 1. 1 アルゴリズムの概要

内に含まれる名詞のみを出現順に並べ，保持している．また，

本アルゴリズムは，あるキーワード群 K とその K に関する

形態素解析した結果，同一単語が複数回出現してもそれらは別

テキスト T に現れる単語の中から，K に関連し，重要だと思われる単語群を抽出し，それらを出力するものである．単語群ののものとみなす．

4. 1. 2 単語の評価

抽出では，K や T で出現する単語間の距離に着目し，これをテキスト T 内で出現する単語の評価は以下の手順で行う．

基準に各単語を評価し，結果として出力する単語群を形成する．

（ 1 ） ki (i = 1 · · · m) を基準に tj (j = 1 · · · n) の基礎評価値

今回用いている提案アルゴリズムは旧アルゴリズムを少し改(BasicV alue)BV (tj ) を計算．

良し，単語一語ずつの距離ではなく，単語が含まれるセンテン（ 2 ） BV (tj ) の平滑化．

ス間での距離を用いている．センテンスとは，文を意味し，句（ 3 ） 単語の出現頻度による最終評価値 (Score)S(wl ) を計算．

点または終止符などで終わる，それだけで意味が通る語のかた

BV (tj ) の算出

まりである．
センテンス間の距離の重要性
上述の通り，本アルゴリズムでは単語が含まれるセンテンス

本アルゴリズムはキーワード群 K を基に，K とテキスト T
で出現する単語間の距離を中心に単語の評価を行うことを目的としており，はじめにその基本となる評価値を求める．

間の距離を重要視している．具体的には，文書中で出現する単まず，キーワード ki による tj の評価値を BVki (tj ) と表記す語が含まれるセンテンスの順番に注目しており，「ある単語 A がる．この BVki (tj ) を次式により求める．ここで j0 は，ki を含

文書中に出現した場合，単語 A 付近のセンテンスに出現していむセンテンス tj0 の添数とする．

る単語ほど A に関連性が強い単語であろう」という考えに基づいている．

BVki (tj ) = n − |j − j0 |(1)

つ ま り，∃wr ∈ tq (ki = wr ) の と き BVki (tq ) = n と準備
アルゴリズムについて説明する前に，準備として以下の記号を定義する．

し ，tq の 1 つ 隣 の セ ン テ ン ス tq−1 ,tq+1 は BVki (tq−1 ) =BVki (tq+1 ) = n − 1，tq の 2 つ隣のセンテンス tq−2 ,tq+2 は•

K …関連単語を抽出するための基になるキーワード群

BVki (tq−2 ) = BVki (tq+2 ) = n − 2，…と各 tj に対して ki に•

T …キーワード群 K に関するテキスト

よる基礎評価値 BVki (tq ) を与える．以上の計算をすべての•ki (i = 1 · · · m)…キーワード群 K に含まれるテキスト

ki (i = 1 · · · m) で行う．

T で出現する m 個のキーワード（テキスト T での出現順に
k1 , k 2 , k 3 , · · · km ）•tj (j = 1 · · · n)…テキスト T で出現する n 個のセンテン

ス（出現順に t1 , t2 , t3 , · · · tn ）•それぞれの tj において BVki (tj ) の和を BV (tj ) とする．即ち，BV (tj ) は次式により求める．

wl (l = 1 · · · o)…テキスト T で出現する o 個の単語（出現順に w1 , w2 , w3 , · · · wo ）
但し，km はテキスト内に出現するキーワードは同一の語でBV (tj ) =m∑

BVki (tj )

(2)

i=1

表 1 に BV (tj ) を求める例を示す．例より，キーワード群 Kに含まれている単語のあるセンテンスを中心に，それに近いセ

あっても区別する．wl はテキスト T を高速形態素解析システ

ンテンスほど高評価を得ていることがわかる．

ム MeCab で形態素解析し，その結果得られた名詞のみを抽出

BV (tj ) の平滑化

し，それらを出現順に並べたものである．また，tj はテキスト

前節で求められた BV (tj ) は，センテンス tj がテキスト T

T をセンテンス毎に分け，各センテンスを 1 ブロックとし，そで出現する位置を考えると不公平である．テキスト T の端に出

表 4 単語毎の S(w)

現するセンテンス tj (j = 1，n) については 1 ≦ BVki (tj ) ≦ n
であるのに対し，テキスト T の中央に出現するセンテンス tn/2

wlについては n/2 ≦ BVki (tn/2 ) ≦ n である．よって，BV (tj ) のS(w) 4.62 4.33 2.89 1.67

A

とり得る値の期待値はセンテンス tj の出現位置 j によって異な

wl

E

B
F

C

D

G

H

S(w) 3.19 3.27 4.90 2.22

り，このままでは T の中央に出現するセンテンスは必然的に与えられる評価値が大きくなってしまい，公平な評価はできない．
こ の問題 を 解決 するた め に，求めた BV (tj ) をセンテンついて重要なセンテンスであるので，そのセンテンスの tf を 1

ス tj の 出 現 位 置 j で の 評 価 値 の 期 待 値 を 用 い て 平 滑 化とするのではなく，単語 wl の出現回数とするべきと考えたかを 行 う．セ ン テ ン ス tj の 出 現 位 置 j で の 評 価 値 の 期 待 値

らである．

(ExpectationBasicValue)EBV (j) は以下の式で求められる．

そして，得られた AveEBV (wl ) と V (wl ) を用いて以下の式

1{n(n + 2j − 1) − 2j(j − 1)}2nでテキスト T で出現する単語 wl の評価値 S(wl ) を計算する．

EBV (j) =(3)

ここで，n はテキスト T 内の全センテンス数である．
本アルゴリズムでは，平滑化後の評価値を EBV (tj ) とし，
以下の式で計算する．

BV (tj )EBV (tj ) =EBV (j)S(wl ) = AveEBV (wl ) × V (wl )(6)

こうして求められた S(wl ) を，本アルゴリズムでのテキスト

T 内で出現する単語 wl の評価値とする．
表 3 に S(wl ) 算出までの例を示し，表 4 に各単語 w 毎の

(4)

S(w) を示す．テキスト T 内では単語 A，E，F，G が 2 回出現
しているので tf (wl ) は 2 となっており，その他の単語につい表 2 に EBV (j) を計算し，EBV (tj ) を求めるまでの例を示す．EBV (j) は出現位置 j での評価値の期待値であるので，中心付近 (j = n/2 付近) の値が大きくなっている．当然だがEBV (j) は中心をピークとして左右対称になっている．これにより BV (tj ) では出現位置により不公平な評価を得ていたものが平滑化されている．

ては tf 値は 1 となっている．重み V (wj ) は tf 値を基に計算しているので，tf 値が 1 の単語については 1，2 回出現している単語については 1 より大きな値をとっている．そして最終的な単語の評価値 S(wl ) が求められ，本アルゴリズムでは，テキスト T 内の単語は，評価値の大きい G，A，B，F，E，C，H，D の順でキーワード群 K へ関連度が高いとみなす．

S(wl ) の算出

4. 2 Robertson’s Selection Value

本アルゴリズムはセンテンス間の距離を最重要視して評価値計算を行っているが，それに加えて TF/IDF 法などで用いられるテキスト内での単語の出現頻度 T F (T ermF requency) の概
念も考慮する．つまり，テキスト T 内で複数回出現した単語はある程度重要視すべきである，ということである．
まず，テキスト T 内で複数回出現した単語についてその単Robertson’s Selection Value(RSV) では，単語 w が適合文
書集合のみに偏って出現し，不適合文書集合にはほとんど出現
しない場合ほど，評価値が高くなる特徴がある．
RSV は以下の式で求められる．
RSVw =

df ++えば，単語 wa と単語 wb (a =| b) が同じ単語だったとすると，

+
+
(dfw
+0.5)/(R+ −dfw
+0.5)

−
−
(dfw
+0.5)/(R− −dfw
+0.5)

•

R+ … 適合文書数

AveEBV (wl ) = EBV (wl ) である．

•

dfw+ … 語 w を含む適合文書数•

R− … 不適合文書数•

dfw− … 語 w を含む不適合文書数
α … 制御パラメータ (0 <
=α<
= 1)

式で表される重み V (wl ) を計算する．

V (wl ) = 1 +tf (wl )log tf (wl )
n

(5)

}

(7)

式 (7) で用いられているパラメータは以下の通りである．

となる．無論，T 内で出現が 1 回のみの単語 wl に関してはさらに単語 wl の tf 値 (T 内での出現回数) を用いて以下の−

dfw +dfw+(1 − α) log

語の EBV (wl ) の平均値 AveEBV (wl ) を計算しておく．例

AveEBV (wa ) = AveEBV (wb ) = (EBV (wa )+EBV (wb ))/2

df + +df −

R +R
w
w
( R+
− Rw
+ +R− ){α log+−•

式 (7) で用いられてる定数 0.5 は，対数が取れるようにする

式 (5) （注 1）で使われるパラメータは以下の通りである．

ための調整値である．また，用いられている log は自然対数で•ある．

tf (wl ) … テキスト T 内での単語 wl の出現回数

n の意味と対比させると，tf の値は本来「テキスト T 内での4. 3 有用度算出

単語 wl が出現するセンテンスの数」とすべきである．しかし，

RSV は文書毎の評価のみから計算される為，ある程度の文

今回 tf の値を「テキスト T 内での単語 wl の出現回数」とし書数が必要となる問題がある．また，語 w が文書内のどの位た．これは，単語 wl が複数回出現したセンテンスはその語に置に出現しても同じ重みとなる問題もある．これらを解決する（注 1）：式 (5) は初めは tf の値のみを重みとしていた．しかし，これでは複数

ために関連単語抽出アルゴリズムを用いる．単語 w における

回出現した語が重要視され過ぎてほぼこの重みのみの評価値となる．次に，tf の

RSV の評価値を RSVw ，関連単語抽出アルゴリズムの評価値

値をセンテンスののべ数 n で割ったものを重みとした．この場合，重みが小さを S(w) とする．式としては以下のようになる．

すぎ，ほとんど意味をなさなかった．このような試行錯誤の結果，上のような式となった．

Score(w) = S(w) × RSVw(8)

表 3 S(wl ) 算出までの各値の例
キーワード K

AB

テキスト TA

EBV (wl )4.33 4.33 4.33 3.33 3.33 2.89 2.89 2.89 2.22 2.22 1.67 1.67

G

B

E

G

A

F

C

F

H

D

E

AveEBV (wl ) 3.61 3.83 4.33 2.50 3.83 3.61 2.56 2.89 2.56 2.22 1.67 2.50

rank
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

tf (wl )

2

2

1

2

2

1

2

1

1

2

V (wl )

1.28 1.28

1

1.28 1.28 1.28 1.28

2

1

1.28

1

1

1.28

S(wl )

4.62 4.90 4.33 3.19 4.90 4.62 3.27 2.89 3.27 2.22 1.67 3.19

評価順に並び替え
1 ◎2 ◎
7 ◎ →適合文書
8 ◎
15 ◎
3 ○
評価は
4 ○
◎ : すごく良い
5 ○○ : 良い6 ○△ : どちらとも言えない
10 ○
14 ○
×
: 悪い
11 △
××
: すごく悪い
16 △
の5段階
17 △
18 △
13 ×
20 ×
9 ×× →不適合文書
12 ××
19 ××

◎
◎
○
○
○
○
◎
◎
××
○
△
××
×
○
◎
△
△
△
××
×
↑
評価

“

”

“

”

“

”

“

”

“

2

表5 実験一覧
語数

クエリ

フィード

拡張手法

バック

goo による検索
提案手法

1語

クエリ拡張

1 語から 2 語

2語

3:pro1p
4:rsv1e
5:rsv1p

提案手法

明示的

7:pro2e擬似8:pro2p

RSV

明示的

9:rsv2e擬似10:rsv2p

提案手法

明示的

12:pro3e擬似13:pro3p

RSV

明示的

14:rsv3e

擬似15:rsv3p

クエリ拡張

6:goo2

goo による検索
クエリ拡張

図 1 検索結果をユーザの評価順に並び替え

5. 評 価 実 験

2:pro1e擬似擬似3 語から 4 語てもクエリの語の近辺に出現する語の方が有用度は高くなる．

明示的
明示的

RSV

2 語から 3 語

3語

これにより同様の文書に出現している語が複数存在したとし

1:goo1

goo による検索”

実験名

11:goo3

Web ページの上位 5 件を適合文書，下位 5 件を不適合文書とする．後者は，図 1 に示すように，並び替えた Web ページの上位 5 件を適合文書，下位 5 件を不適合文書とする．
これらの作業を各クエリに対して，各被験者に行ってもらう．

5. 1 実 験 方 法
1 語，2 語，3 語のクエリをそれぞれ 50 件ずつ用いて 3 人の被験者に Web 検索を行ってもらう．まず，検索エンジン goo
を用いて検索結果を評価する．続いて，RSV によって拡張されたクエリと，提案手法によって拡張されたクエリを用いて，検索結果を評価する．以下に詳細を示す．

5. 1. 1 goo による検索
2 語で構成されるクエリを 50 件用意した．これらを用いた検索エンジン goo による検索は以下のように行う．
（ 1 ） Web ページの評価
クエリを検索エンジン goo に与えて得られた検索結果の上位

20 件の Web ページを被験者が評価する．被験者は Web ペー

5. 1. 2 RSV によるクエリ拡張
適合文書と不適合文書に対して RSV を適用して，5. 1. 1 節
で使用したクエリを拡張する．RSV による評価で最も評価値の高い語を元のクエリに追加して拡張クエリを決定する．この
拡張クエリを用いて Web 検索を行う．そして，5. 1. 1 節と同様に Web ページを評価する．

5. 1. 3 提案手法によるクエリ拡張
適合文書と不適合文書に対して提案手法を適用して，5. 1. 1
節で使用したクエリを拡張する．
ここで適合文書に対して関連単語抽出アルゴリズムを適用す
る．関連単語抽出アルゴリズムは単一文書に適用するアルゴリ
ズムであるが，以下のように複数文書に適用する．適合文書をジを 5 段階（すごく良い，良い，どちらとも言えない，悪い，dk (k = 1, 2, · · · , n) としたとき，語 w の各適合文書における関すごく悪い）で評価する．

連単語抽出アルゴリズムの評価値を S(wdk )(k = 1, 2, · · · , n) と（ 2 ） Web ページの並び替え

すると，語 w の評価値 S(w) は∑n

Web ページを評価の良い順で並びかえ，同じ評価の Web
ページは，元の順位の昇順に並び替える．
（ 3 ） 適合文書，不適合文書の決定
ここで，擬似フィードバックと明示的フィードバックを用いて適合文書と不適合文書を決定する．前者は，並び替える前のS(w) =

k=1

S(wdk )n(9)として計算する．
適合文書と不適合文書に対して RSV を適用して，式 (9) を式 (8) に代入して得られた評価値の順番に語を並び替え，最も図 2 R10 と P1（1 語）の場合

図 6 R10 と P1（2 語）の場合

図 3 R20 と P1（1 語）の場合

図 7 R20 と P1（2 語）の場合

図 4 R10 と P2（1 語）の場合

図 8 R10 と P2（2 語）の場合

図 5 R20 と P2（1 語）の場合

図 9 R20 と P2（2 語）の場合

評価値の高い語を元のクエリに追加して拡張クエリを決定する．

5. 2 結この拡張クエリを用いて Web 検索を行う．そして，5. 1. 1 節と5. 1 節で行った実験は表 5 に示す 15 個の実験である．これら同様に Web ページを評価する．

果の各実験結果に対して，各クエリにに対して平均精度（Average

Precision: AP）を計算する．

表 6 各手法の MAP 値の比較

R10-P1 R20-P1 R10-P2 R20-P2

図 10 R10 と P1（3 語）の場合

1:goo10.04960.0786

0.11200.18782:pro1e

0.04220.06410.10090.1707

3:pro1p0.03270.05580.07990.1333

4:rsv1e0.03380.05390.08350.14495:rsv1p

0.02780.04790.0646

0.1122

6:goo20.1687

0.26620.30570.5147

7:pro2e0.16330.25210.28320.4856

8:pro2p0.12790.19890.24580.4222

9:rsv2e0.14420.21930.26520.449810:rsv2p

0.10920.17420.22890.390811:goo30.16770.27240.29180.5105

12:pro3e0.16480.25440.27690.480013:pro3p

0.13110.19960.24120.399414:rsv3e0.15580.22620.27160.451015:rsv3p

0.12790.1861

0.23690.3888•

評価が「すごく良い」である文書を適合文書（P1）•

評価が「すごく良い」と「良い」である文書を適合文書（P2）
これらのパターンの組み合わせて，R10-P1，R20-P1，R10図 11 R20 と P1（3 語）の場合

P2，R20-P2 の 4 つのパターンに関して MAP（Mean Average
Precision）を計算する．MAP を計算する時に用いる適合文書
数は各クエリとも 20 とする．
図 2 から図 13 は，goo による AP が変化するとき，各手法の MAP がどのように変化するか示した図である．各図の左縦軸は該当するクエリの件数，右縦軸は MAP，横軸は AP の閾値であり，棒グラフがクエリの件数，折れ線グラフが MAP を示している．例えば，図において，AP の閾値が「<= 0.8」であるとき，goo の AP が 0.8 より小さいようなすべてのクエリに対して，各手法の MAP をプロットしており，そのときの棒グラフの示す値が AP の閾値の条件を満たすクエリの件数であ

図 12 R10 と P2（3 語）の場合

る．R10 の AP は R20 の半分しか取りえない，すなわち，0.5以下の値しか取れないので，R10 のグラフは 0.5 以下で表示している．

5. 2. 1 R10 と R20 の比較
各手法の R10 における MAP と R20 における MAP を比較する．
表 6 は AP の閾値が 1.0 以下の時の各実験結果の MAP を示している．図 2 から図 13 より，R20 における MAP が R10 における MAP より高いことがわかる．しかし，表 6 より，どの実験結果を見ても，R20 における MAP は R10 における MAPの 1.45 倍から 1.75 倍にしかならない．これは上位 10 件にお図 13 R20 と P2（3 語）の場合

ける適合率（P@10）が上位 20 件における適合率（P@20）よりも高いことを示している．もし逆であれば，R20 における

このとき，平均精度を求める対象を以下の 2 パターンにする．

•

上位 10 件（R10）•

上位 20 件（R20）

また，適合文書を以下の 2 パターンで定義する．

MAP は R10 における MAP の 2 倍を超えるはずである．以上
より，1 位から 10 位までの適合 Web ページ数と，11 位から20 位までの適合 Web ページの数を比較すると，前者の方が多いことがわかる．

5. 2. 2 P1 と P2 の比較が出現するセンテンスと他のセンテンス間の距離に着目して，P1 と P2 を用いたときの MAP の変化を比較する．図 2 かクエリ内の語との関連度を計算する．

ら図 13 より，どの実験結果を見ても，P1 も P2 も似たような

提案システムの評価実験の結果，RSV だけを用いて再検索変化をする．同じ実験で P1 の MAP が P2 の MAP より低くを行った場合よりも，提案システムは精度の高いクエリ拡張をなるのは，P1 では「すごく良い」と評価された文書のみを適行うことができることを示した．さらに検索エンジン goo での合文書とするため，適合文書数が P2 と比較して少ないためで検索結果の MAP がある一定値よりも低い場合，すなわちクエ

ある．これらの図は，厳しい評価をするユーザだけでなく，甘リに曖昧さが強く goo の結果が思わしくない場合に，その検索

い評価をするユーザに対しても，goo による AP が，0.4 であ精度を改善できることを示した．

るクエリに対して提案手法のクエリ拡張が効果的に働くことを示している．

これらの実験の結果，提案システムは，ユーザがクエリに適切な語を追加できない場合，即ち，クエリに用いられている語

5. 2. 3 RSV と提案手法の比較が少ない場合でかつその語が検索語として有用でない場合に最提案手法を使用して拡張されたクエリによって得られた検索も精度が改善する，ということが確認できた．これは，当初の結果の MAP と，RSV によって得られた検索結果の MAP を目的である，「ユーザが適切なクエリを追加できない場合にシス比較する．

テムが自動的に関連語を追加するシステムの実現」に向けた第図 2 から図 13 と表 6 は，提案手法による MAP が RSV に一歩としては十分な結果を与えたと考える．

よる MAP より高いことを示している．これは，関連単語抽出

今回，予備実験として，ユーザに Web ページを評価してもアルゴリズムがほぼ常に RSV を効果的に強めていることを表らい，その評価情報を利用することで，適合文書と不適合文書している．一部逆転している部分があるが，これは対象となるに含まれる語を精度よく識別することができたが，Web ページ

クエリ数が少なかったり，擬似フィードバックによってユーザの評価には多くの時間を要し，そのためのユーザの負担は無視の意志を反映した単語を適切に取り出すことができなかったたできるものではない．そのため，このユーザの負担を軽減しつめだと考えられる．

つ，適合文書と不適合文書の選択を自動的に行うことが望まし

5. 2. 4 goo と提案手法の比較

い．実験では，クエリの語数，クエリ拡張手法，フィードバッ

クエリが 1 語の時（図 2 から図 5），どの実験結果も非常にク手法を変えて比較した．今後はクエリ拡張で関連単語抽出ア

低い MAP 値を取っている．これは goo による検索結果に適切

ルゴリズムのみを用いた場合も比較するために追加実験を行う．

な Web ページが含まれていないためであり，本研究で使用し謝辞 本研究の実験を行うにあたり，九州大学工学部電気情

たどの手法も効果的には働かない．
クエリが 2 語の時（図 6 から図 9），goo による AP がある
特定の値（各々0.4, 0.6, 0.4, 0.8）より小さいようなクエリに対して，明示的フィードバックを用いた提案手法（7:pro2e）による MAP が goo（6:goo2）による MAP より高くなった．表6 を見ると “6:goo2” の MAP が “7:pro2e” の MAP より高い値を示しているが，この値にはもともと goo で高い評価をされているクエリも含まれている．そのようなクエリに対してク
エリ拡張をする必要はないため，“6:goo2” で高い MAP 値を持つクエリを省くことで，上記のような結果となった．また，擬似フィードバックを用いた手法（8:pro2p，10:rsv2p）による

MAP が goo による MAP より高くなることはなかった．
クエリが 3 語の時（図 10 から図 13），2 語の時と同様な傾向を示した．2 語の時と異なるのは，提案手法と RSV の差（12:pro3e と 14:rsv3e，13:pro3p と 15:rsv3p）が小さくなって
おり，提案手法だけが効果的に働いているとは言えない．

6. お わ り に
本稿では，クエリ拡張を行うための一手法である関連単語抽
出アルゴリズムを提案した．そして，関連単語抽出アルゴリズ
ムと適合性フィードバック用アルゴリズムである RSV とを融合させて，初期クエリに対して検索エンジンから返された Web
ページへのユーザの評価情報を元に，新たなクエリを生成し，そのクエリを利用して再検索を行うシステムを試作した．関連
単語抽出アルゴリズムは，文書内頻度だけでなくクエリ内の語

報工学科の倉門浩二氏，田代祐一氏，中村徹氏には多大な協力をして頂いた．ここに深く感謝します．また, 本研究は科研費（20240003）の助成を受けたものである．
文

献[1] P. Lawrence, B. Sergey, M. Rajeev and W. Terry: “The
PageRank Citation Ranking: Bringing Order to the Web”,
Technical Report, Stanford University, 1998
[2] T. Masada, T. Kanazawa, A. Takasu and J. Adachi: “Improving Web Search by Query Expansion with a Small Number of Terms”, NTCIR-5 Workshop Meeting, (2005)[3] S. E. Robertson, On term selection for query expansion,
Journal of Documentation, v.46 n.4, p.359-364, Dec. 1990
[4] 大石 哲也，峯 恒憲，長谷川 隆三，藤田 博，越村 三幸，倉元 俊介，永田 廣人: “ユーザのスケジュールを考慮した Web 検索手法”, Joint Agent Workshop and Symposium 2007
[5] 大塚 真吾, 喜連川 優: “大規模アクセスログを用いた検索支援
システムの提案”, 日本データベース学会 Letters Vol.5, No.1,
2006[6] 岡部正幸, 山田誠二: “トランスダクティブ学習による最小文
書判定からのクエリ拡張”, 人工知能学会論文誌 21 巻 4 号 I,
pp.398-405, 2006
[7] 倉元 俊介, 永田 廣人, 大石 哲也, 峯 恒憲, 長谷川 隆三, 藤田 博,
越村 三幸: “単語間の距離を利用した関連単語抽出アルゴリズム”, 火の国情報シンポジウム 2007
[8] 馬場肇: “Google の秘密 - PageRank 徹底解説”, http://
www.kusastro.kyoto-u.ac.jp/ ~baba/wais/pagerank.html[9] goo, http://www.goo.ne.jp/[10] Google, http://www.google.co.jp/[11] Yahoo! JAPAN, http://www.yahoo.co.jp/[12] 高速形態素解析システム “MeCab”,
http://mecab.sourceforge.jp/