一般論文

DBSJ Journal, Vol.7, No.4
March 2009

ク リック ロ グ 解 析 に よ る 情 報 要 求
ベースの検索結果ランキング
Ranking Search Results based on Information Needs in conjunction with Click
Log Analysis

ユーザが検索エンジンのインタフェースにキーワード (クエリと呼ぶ) を入力すると, 検索エンジンはこの大量のインデクス内を走査し, クエリに適合しているであろう順にページをランキング付けして返す. そしてユーザはこの結果を見て, 自分の情報要求を満たせそうだと判断した検索結果をクリックし, そのページ内を閲覧していく. この検索結果画面の閲覧において，ユーザは一般的に上位の検索結果しか見ないという事実が知られている

村田 眞哉
松浦 由美子 ♠戸田 浩之
片岡 良治 ♣

[1]．これは経験的にユーザが検索結果上位のみを信頼しているという事や, 下位を閲覧するにはブラウザのスクロールなどの多少の追加の操作が必要になることによって, 閲覧が阻害されているといった事が理由と考えられる.

Masaya MURATA
Yumiko MATSUURA

Hiroyuki TODA
Ryoji KATAOKA

キーワードベースのランキング [2] によりユーザが投入したクエ♥♦

ユーザが望む検索結果を上位に提示するため，従来研究では
リを本文中にたくさん含むページを優先したり, リンク解析ベースの手法 [3][4] により良質なページから多くのリンクを集める

検索エンジンにおいて, 検索結果上位における精度というもの

ページを優先的に提示したりしている. 一方, 我々はユーザが検はその性能を決定付け, かつユーザに有用性を印象づける重要な

索結果上位に表示される事を望んでいるページとは，単純にクエ要素の一つになっている. この領域の検索精度を上げる為には，

リを多く含むページや被リンク数が多いページではなく，ユーザ

ユーザがクエリで表現した情報要求を満たす事ができるページをがクエリで表現した情報要求を満たす事ができるページであると特定し, 検索結果上位に提示させるランキングアルゴリズムが必考える．上述したキーワードベースやリンク解析ベースのランキ要となる. 本論文では検索エンジンのログを解析することで，こングはこのようなページを直接特定しようとするものではなく,の情報要求ベースのランキングを実現する手法を提案する.

必ずしも適切な検索結果が提示できていない. そこで本論文ではPrecision at a higher rank in search results is oneof the important factors that determines the performance of the search engine and impresses users with
its usefulness. In order to raise the precision, we
need to devise a ranking algorithm that can specify
pages closely corresponding to the information needsof the query and boosting them into a higher rank.
In this paper, we propose a ranking method basedon the information needs by analyzing click logs.

ベースのランキングを提案する.

上述のアイデアを直接的に考慮したランキング, つまり情報要求提案手法では, 「検索エンジンのクリックログ」および「検索結果として表示されるページのタイトル, スニペット」を利用する事で, クエリに込められた情報要求およびページが満たせる
情報要求を明確化し, これらの一致度に沿った検索結果ランキングを実現する. 評価実験は商用の検索エンジンであるモバイル
goo1 のインデクスおよびログを利用して行った. 結果は我々のランキングに対する考え，及びクリックログの解析法を支持するものであり, 提案手法の有効性を示唆するものであった.
以下, 2 章で関連研究, そして 3 章で提案手法について説明す

1.

はじめに

検索エンジンは, あらゆる情報の取得源として欠かせない存在になっている. 検索エンジンは World Wide Web(WWW) 上にる. そして 4 章で評価実験について示し, この実験結果を基に提案手法の有効性を議論をする. そして 5 章で本論文をまとめる.

2.

関連研究

膨大に存在するページをあらかじめダウンロードし, その大量の我々の提案手法はまず検索エンジンのクリックログを解析し,データ (インデクスと呼ぶ) を内部に保存して持っている. 近年,

クエリとページの間のクリック関係を基にユーザがクエリで表現

WWW 上のページは爆発的に増加しており, それに従いインデクスの量も膨大になっている.

した情報要求と, ページが満たせる情報要求を表現する. そしてこれらの類似度を算出し, ランキングに反映させる. つまり提案
手法はクエリとページの両方を，それぞれの情報要求に沿って拡♥

正会員 日本電信電話株式会社 NTT サイバーソリューション
研究所 murata.masaya@lab.ntt.co.jp♦
正会員 日本電信電話株式会社 NTT サイバーソリューション
研究所 toda.hiroyuki@lab.ntt.co.jp♠
日本電信電話株式会社 NTT サイバーソリューション研究所♣

matsuura.yumiko@lab.ntt.co.jp
正会員 日本電信電話株式会社 NTT サイバーソリューション
研究所 kataoka.ryoji@lab.ntt.co.jp

1張する手法であると言える. 従ってクエリ拡張法，ページ拡張法，
そしてそれらの混合手法それぞれに属する関連研究を紹介する．

2.1

クエリ拡張法

クエリ拡張法とはクエリに関係するキーワード群を特定，選択
し，クエリと共に AND もしくは OR 検索を実行する手法であ1

http://mobile.goo.ne.jp/

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009
我々の提案手法は上述した Ricardo の手法とは異なり, クエリ

り，それらキーワード群によって検索結果の絞り込みもしくは網羅的な検索を行うことを目的としている.

の拡張においてクリックした検索結果の本文に含まれるキーワー

Cui らはクリックログを解析することで，クエリを構成する
キーワードと関連が高いキーワード群を判明させ, クエリ拡張を行う手法を提案している [5]. Cui らの手法はクエリとそれでドを用いるのではなく, そのタイトルとスニペットに含まれるクするか否かの判断を，そのタイトルとスニペットにより行うのユーザがクリックしたページをそれぞれキーワードにまで細分化

で，これを用いることでユーザがクエリで示した情報要求の表現

し, これらキーワード同士の関連度合をクリック関係に基づき算の精度が高まることが期待できる. 次に，Ricardo の手法は投入出するものである. そしてこの度合に基づき入力されたクエリとされたクエリと異なる情報要求を持つクエリでページがユーザに関連が高いキーワード群を特定し, クエリ拡張を実行する．

キーワードを用いる. なぜなら一般にユーザは検索結果をクリッ

よりクリックされている際の負のフィードバック (つまりランキ

村田らもクリックログを解析することで得られる, クエリに対ング下位に下げる効果) が考慮されていない．また，彼らの手法して関連が高いキーワードでクエリ拡張を行う手法を提案していはクリックが全くされていないページ (ゼロクリックページ) にる [6]. 村田らはアクセスが集中している検索結果のタイトルと対しては適用できない．クリックされるか否かはランキング上位

スニペットには, ユーザをクリックに導いた魅力的なキーワードにあるかどうかに強く依存するところが大きく，例え下位に存在が存在すると仮定し, このキーワードでクエリ拡張を実行するこ

しクリックがされていないページでも，クエリに対する適合度合とが重要であると考えた. そしてアクセスの集中度合を検索結果を考えることは重要である．

上で隣り合うページ間の相対的なクリック回数で定義する事により，多くの検索結果中からアクセス集中ページを特定し，クエリ

3.

拡張を実行することで検索精度の向上を実現している．

2.2

ページ拡張法

提案手法

我々は検索結果の上位に, ユーザがクエリで表現した情報要求を満たす事ができるページを表示することを目指す. これと同様

ページ拡張法とは, クリックログの分析等に基づきページに関な目的を持ったランキング手法を情報要求ベースのランキングと係あるキーワード群を特定，選択し，ページのインデクスに追加名付ける. この手法を実現する際の解決すべき課題は以下になる.

する手法であり, それらキーワード群によって検索が行われた場
合のページの優先度を向上させることを目的としている.

Xue らはクエリとページの間にクリック関係がある場合, それはクエリとページとの情報要求レベルでの結び付きであると考え, このクエリでページのインデクスを拡張する手法を提案した[7]. このクリック関係を解析する上で問題となるのは, クエリページ間のクリック構造が疎であることである. そこで Xue らは, 同一のページをクリックしたクエリ同士の情報要求は類似しており, また同一のクエリでユーザにクリックされたページ同士が満たせる情報要求も類似しているという仮定を置き, クエリ-

1. クエリの情報要求の表現(Information Need of Query, INQ)
2. ページが満たせる情報要求の表現(Information Need satisfied by Page, INP)
3. クエリ-ページ間の情報要求の類似度に基づくランキング
我々は検索エンジンのクリックログの解析結果を利用することで, これらの課題を解決する. 以下 3.1 節で課題 1 の, 3.2 節で課
題 2 の, そして 3.3 節で課題 3 の解決法を説明する.

3.1

課題 1: クエリの情報要求 (INQ) の表現

ページ間で実際のクリックが存在しない場合においても，情報要我々は検索エンジンのクリックログを解析することで, この課

求レベルで類似度が高いクエリであればそれをインデクス拡張に

題を解決することができると考えた. なぜなら一般にユーザは各使用する手法を提案した.

検索結果のタイトルとスニペットを閲覧し，情報要求に適合して

2.3

混合手法

Ricardo らはクエリ拡張のみならず, 検索対象であるページがどのようなクエリでクリックされているのかについても注目しいそうだと判断したものをクリックすると考えられ，クリックロ
グにはこのクリックの情報が残されているからである．クエリの情報要求 (INQ) の表現のため，次の仮定を置く.

た [8]. Ricardo らの手法はまず, クエリをそれでユーザがクリッ• INQ は，そのクエリでユーザがクリックした検索結果のタクした検索結果の本文のキーワードを用いてベクトルで表現し,イトルとスニペットで表現することができる

そのベクトル間の類似度を基にクエリの集合をクラスタリング
する. そしてあるクエリ q とあるページ p の間のランキングス

この仮定に基づき，INQ は以下の手順で表現される.

コア sim(q, p) を決定する際に, もし q が属するクラスター内の他のクエリ qi , (i = 1, · · · , n) からも p がよくクリックされている場合, これは p が q と情報要求レベルで似たような他のクエ
リ qi , (i = 1, · · · , n) からもよくクリックされているという事実を意味するので，そのランキングスコア sim(q, p) を高くしている. つまり拡張されたクエリとページ間の類似度のみならず, そ1. クリックログを解析し, クエリ q で検索が行われた時にクリックされた各ページ pi , (i = 1, · · · , n) のクリック回数
c(q, pi ) を特定する
2. 各ページのタイトルとスニペットを取得し, それらを形態素解析して内容語2 tj , (j = 1, · · · , m) のみを抽出し, キーワーのページが他にどのような情報要求を持つクエリでクリックされているのかについても考慮したランキング手法である.

2

2

名詞と用言の語幹 (動詞, 形容詞など)

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

図1

DBSJ Journal, Vol.7, No.4
March 2009

クエリの情報要求 (INQ) のベクトル表現

図 2 ページが満たせる情報要求 (INP) のベクトル表現

Fig. 1 Representation of INQ vector

Fig. 2 Representation of INP Vector
ドベクトル v(q, pi ) を算出する. ベクトル v(q, pi ) の各要素

INP(p) =は内容語の tf (tj , pi ) · idf (tj ) 重みである. tf (tj , pi ) はその∀qk ∈Qc(qk , p) × INQ(qk )∀qk ∈Qc(qk , p)(2)

ページ pi のタイトルとスニペットにおける内容語 tj の出現
頻度, idf (tj ) はモバイル goo の全インデクス内における内ここで Q は全クエリの集合を表す. 図 2 にページと INQ ベク

容語 tj の Inverse Document Frequency である.

トルのクリックの関係, そしてこの関係から得られる INP ベク

3. こ の v(q, pi ) を 用 い て, ク エ リ の 情 報 要 求 を 表 現 す る
INQ(q) ベクトルを以下の式で定義する.


INQ(q) =∀pi ∈Pc(q, pi ) × v(q, pi )∀pi ∈Pる. つまり INQ ベクトルの時と同じく, INP ベクトルの生成もc(q, pi )トルについて示す. 算出された INP ベクトルは URL と対応付
けて DB へ保存され, 検索結果のランキングを行う際に参照されオフライン処理である.

(1)

3.3

課題 3: クエリ-ページ間の情報要求の類似度に基づくランキング

ここで P は全検索結果の集合を表す. 図 1 にクエリとページのクエリ q の INQ(q) ベクトルとページ p の INP(p) ベクト

クリックの関係, そしてこの関係から得られる INQ ベクトルにつルが上式 (1), (2) で求められると, それら同士のコサイン類似

いて示す. 算出された INQ ベクトルはクエリと対応付けて DB

度をとることで，単純な情報要求の類似度 (Simple Information
Need Matching, SINM) を計算することができる．

へ保存され, 検索結果のランキングを行う際に参照される. つま
り INQ ベクトルの生成はオフライン処理である.

3.2

課題 2: ページが満たせる情報要求 (INP) の表現

我々は検索エンジンのクリックログを解析することで, この課
題 2 も解決されると考えた. この解決法は検索結果のクリックに対する一般的な考え方である, 検索結果はユーザの情報要求に合っていそうだと判断されたらクリックされるから導き出される

SIN M (q, p) = cos(INQ(q), INP(p))

ここで更に，INP(p) はページ p が多くのクエリによりクリッ
クされていればいるほどその表現の精度が高まると考えられるので，以下の INP(p) に対するクエリの寄与個数 N (p)次の仮定に基づく.

• INP は, それをクリックしたユーザの INQ で表現するこ

1. クリックログを解析し, ページ p をユーザがクリックした際のクエリ qk , (k = 1, · · · , l) とそのクリック回数 c(qk , p) を特定する

2. これらクエリ qk の情報要求を表す INQ(qk ) ベクトルと, そのクリック回数 c(qk , p) を用いて，INP(p) ベクトルを以下の式で定義する. つまり INQ ベクトルの定義の時と同様に,
クリック回数による加重平均である.

3



T (p)

N (p) =c(qi , p)/max c(p)(4)

iとができる．
この仮定に基づき，INP は以下の手順で表現される.

(3)を考慮に入れ，式 (3) の単純な情報要求の類似度を改良する．ここで T (p) はページ p をクリックしたユーザが入力した異なるク
エリの総数で，max c(p) はこれらクエリの内，最大のクリック回数である．例えばあるページが 2 つの異なるクエリによりクリックされ，それぞれのクリック回数が 100 と 1 であったとすると，このページの N (p) は 100/100 + 1/100 = 1.01 である．つまりクリック回数が 1 のクエリの INP(p) への寄与は，他のクエリと比べて相対的に微小なため，約 1 つのクエリにより INP(p)は算出されたと見なす．

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009

このクエリの寄与個数 N (p) を用いて，情報要求の類似度(Information Need Matching, INM) を以下の式で計算する．

IN M (q, p) = 1 − 1/(1 + N (p))

α

· SIN M (q, p)(5)

IN M (q, p) は，クエリの情報要求ベクトル INQ(q) とページが満たせる情報要求ベクトル INP(p) の類似度 SIN M (q, p) が高
く，かつ INP(p) に対するクエリの寄与個数 N (p) が大きくなればなるほどこの INP(p) の精度も高いので，結果として高い値を持つ．逆に，SIN M (q, p) が高くても，N (p) が小さければその INP(p) の精度も低いので，IN M (q, p) は低い値を持つ．αはこの N (p) の効果のコントロールパラメータで，次章の評価実
験では α = 0, 1, 2, 3 と振ってその影響を調べた． α = 0 の場合，
IN M (q, p) は式 (3) の SIN M (q, p) となる．
IN M (q, p) を用いてランキングスコア score(q, p) を以下の式

かじめ作成してある. 被験者には用意した検索課題に基づき, 各
検索結果を 4 段階評価 (S, A, B, C) してもらった. 各評価の基準はそれぞれ, 特に価値がある (ぴったり), 価値がある (目的に合っている/必要な情報が含まれる), まあまあ価値がある (部分的に目的に合う/部分的に必要な情報が含まれる), そして価値がない (目的に合っていない/必要な情報が全くない) である.
次に各クエリに対して S=A=適合，B=部分適合，C=不適合と見なし， 3 人の多数決を取ることで各ページに適合度合を付与した．もし 3 人の評価が適合，部分適合，不適合と割れた場合はその中心値を取り，そのページの適合度合は部分適合とした。この適合度合を基に多値適合判定データと, 高適合のページのみを正解とした二値適合判定データを用意した. これは検索結果上位に適合度合の高いページをもってくるという我々の研究目的を,で定義する．

score(q, p) = score o(q, p) ×

提案手法がどれだけ達成しうるか評価を行うために用意したデー
タである.



4.2

click?(p) 1 + IN M (q, p) +



1 − click?(p) · QP (q, p)

精度評価指標実験結果の精度評価は, 二値適合判定データを使用する検索結(6)

ここで，score o(q, p) は BM25 等の全文検索ランキングスコア，

QP (q, p) は INQ(p) とページ p の本文のキーワードベクトルとのコサイン類似度を意味する．この本文のキーワードベクト
ルは 3.1 節で述べたキーワードベクトルの算出法と同じである．

click?(p) はもしページ p が 1 回でもクリックされていれば 1，1
回もクリックされていなければ 0 を持つスイッチパラメータである．つまり 1 回もクリックされていないページ群 (ゼロクリック
ページ群) に対してはその QP (q, p) を基にランキングを計算する．検索対象となるページはこの score(q, p) によってランキン
グされ，クエリ q に対する検索結果としてユーザに提示される．

4.

これらクエリに対する適合性判定データは, 各クエリの検索結
果上位 200 件のページを, 被験者 3 人に評価してもらう事であら

評価実験

果上位 K 件の精度 (Precision at K), 平均平均適合率 (Mean
Average Precision, MAP), そ し て 多 値 適 合 判 定 デ ー タ を 使用する検索結果上位 K 件の正規化減損累積利得 (normalized
Discounted Cumulative Gain, nDCG at K) を用いて行った.
nDCG at K は以下の式で算出される

nDCGq = Mq

K(2r(j) − 1)/log(1 + j)

(7)

j=1

ここで，Mq は検索結果が理想的なランキングである場合にそのnDCGq の値を 1 にする正規化定数である．j は検索結果のラン
キング，r(j) はランキング j にあるページの適合度合である．

4.3

評価対象の手法

評価対象の手法は 4.3.1 節から 4.3.4 節に示す 4 つのベースラ

本章では, 提案手法の効果を検証するために行った検索精度のインと，4.3.5 節，4.3.6 節に示す 2 つの提案手法である．各ペー

評価実験について説明する. 4.1 節で使用したデータセットにつジはそれぞれの手法で算出されたスコアの高い順にランキングさいて，4.2 節で精度評価の指標について言及し, 4.3 節で評価対象

れ, その結果が検索結果として提示される. 同スコアのページがの各手法について説明する．そして 4.4 節で実験結果を示し, そ

複数ある場合には BM25 スコアの高いページを上位ランクに配の結果を基に提案手法の有効性を議論する.

置する.

4.1

4.3.1

データセット

ベースライン 1: BM25

本研究で行った一連の評価, 実験は, モバイル goo のインデク

ベースライン 1 は, キーワードベースのランキングとしてスレコード, クリックログ 3ヵ月分3 , 「JR 時刻表」, 「LOTO6」,

幅広く用いられている BM25 である. クエリ q が形態素 ti ,「浜崎あゆみ」，「YouTube」，「引っ越し業者」などのクエリ 51 個

(i = 1, · · · , n) から成るとすると, ページ p との BM 25(q, p) ス
コアは以下で定義される.

を使用している. これらクエリに対する BM25 の検索結果上位

100 件をそれぞれの手法でリランキングし, その検索結果の精度を評価する. これらクエリ 51 個はモバイル goo のクエリ投入数

BM 25(q, p) =i=1

ランキングにおける中〜上位から，インフォメーショナル，ナビ
ゲーショナル，トランザクショナルなどのクエリのタイプ [9] に偏りが生じないよう選択した.
3

2007 年 9 月 1 日から 11 月 30 日まで

4n

wp (ti )(8)(k1 + 1)tf (ti , p)
|N | − df (ti ) + 0.5
× log
K + tf (ti , p)
df (ti ) + 0.5


dl(p)
K = k1 1 − b + b
avpl

wp (ti ) =日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文

DBSJ Journal, Vol.7, No.4
March 2009
表 1 各ベースラインの Precision at K と MAP

ここで tf (ti , p) はページ p 内におけるクエリの形態素 ti の出現

Table 1 Precision at K and MAP for baselines

頻度, N はインデクス内の全ページ数, そして df (ti ) は ti を含む

Method
BM25
PF
CN
INQ

ページのインデクス内における頻度である. dl(p) はページ p の長さ, avdl はインデクス内におけるページの平均長である. b と

k1 はパラメータで, 実験的に b = 0.75, k1 = 1.2 に設定した.

4.3.2

ベースライン 2: Pseduo-Feedback(PF)ベースライン 2 は検索結果の擬似フィードバック [10] で，検

P(5)
45.5
41.6
50.2
45.5

P(10)
42.5
42.4
46.9
47.1

MAP
48.9
48.4
50.7
50.9

索結果上位 K 件のタイトルとスニペットを使用してクエリを拡張する手法である．そして拡張されたクエリ EQ(q) と各ページ

表2

各ベースライン間の有意差 (**, *，n.s. はそれぞれ 1%,の本文のキーワードベクトル PC(p) とのコサイン類似度を計算

5% 有意差，そして有意差無しを意味する． )する．この類似度を基にランキングを以下の式で決定する．

Table 2 Signiﬁcant diﬀerences between pairs of baseline

score(q, p) = BM 25(q, p) · 1.0 + cos(EQ(q), PC(p))

(9)methods(**, * and n.s. denote p < 0.01, 0.01 < p < 0.05,
and no signiﬁcant diﬀerence, respectively)

K = 10, 20, 50 とパラメータを振った結果，精度に大きな違いが見られなかったため K = 20 を採用した．

4.3.3

ベースライン 3: Click Number(CN)ベースライン 3 はクリックログを解析することで得られる, 各ページのクリック回数を使用する手法である．このクリック回数

p(5)
p(10)
MAP

INQ
CN
n.s.
n.s.
n.s.

INQ
PF
n.s.
**
**

INQ
BM25
n.s.
*
**

CN
PF
*
n.s.
n.s.

CN
BM25
n.s.
**
**

PF
BM25
n.s.
n.s.
n.s.

c(q, p) を用いてランキングを以下の式で決定する．
score(q, p) = BM 25(q, p) + c(q, p)

4.3.4

(10)
次に提案手法 1，2 である INM，SINM の Precision at K とMAP を表 3 に示す．この表 3 から INM，SINM 共に最も有効

ベースライン 4:

Information Need of Query(INQ)
ベースライン 4 は, 3.1 節の式 (1) で算出されるクエリの情報
要求ベクトル INQ(q) と各ページの本文のキーワードベクトルであったベースラインを上回る精度を得ていることがわかり，特に INM の精度向上が著しいことがわかる．

PC(p) とのコサイン類似度を使用する手法である．この類似度を基にランキングを以下の式で決定する．

score(q, p) = BM 25(q, p)· 1.0+cos(INQ(q), PC(p))



表 3 INM，SINM の Precision at K と MAP(11)

この手法はクリック回数に基づくクエリ拡張法の一種で, 検索結果の精度向上に対して有効であることが知られている [6]．

4.3.5

提案手法 1:

Simple Information Need Matching(SINM)

Table 3 Precision at K and MAP for INM and SINM

Method
CN
INQ
SINM
INM

P(5)
50.2
45.5
54.1
55.3

P(10)
46.9
47.1
52.0
52.5

MAP
50.7
50.9
52.8
55.0

提案手法 1 は, 3.3 節の式 (5) において α = 0 と設定した手法である．検索結果のランキングは 3.3 節の式 (6) により行われる．

4.3.6

提案手法 2:

Information Need Matching(INM)

図 3 に INM と SINM，そして INQ と CN の nDCG at K の結果を示す．縦軸が nDCG at K ，横軸が検索結果上位 K 件で提案手法 2 は, 3.3 節の式 (5) において α = 0 と設定した手ある．図 3 から多値適合判定データにおいても，提案手法は各法である．検索結果のランキングは 3.3 節の式 (6) により行われベースラインに対して大幅な精度向上を達成していることがわかる．α = 1, 2, 3 とパラメータを振った結果，精度に大きな違いがる．特に本研究の目的であった検索結果上位 1 ≤ K ≤ 20 にお見られなかったため α = 2 を採用した．

ける精度向上が著しいことがわかる．

4.4

実験結果

表 4 に INM, SINM, INQ, CN 間のウィルコクソンの符号付

最初に各ベースラインの Precision at K と MAP の値を表 1

順位和検定による統計的有意差を示す．この表 4 から最も効果的に示す．各精度評価指標の内，最大の精度を太字で記した．そしな手法は INM であることがわかる．この結果は 3.3 節の式 (4)て表 2 に各ベースライン間のウィルコクソンの符号付順位和検で導入したクエリの寄与個数 N (p) の有効性を意味しており，ク定による統計的有意差を示す．これら表 1，表 2 から最も有効な

エリの情報要求ベクトル INQ(q) とページが満たせる情報要求

ベースラインは INQ と CN であることがわかる．従って提案手

ベクトル INP(p) との単純な類似度を，この N (p) により改良

法 1，2 の検索精度の比較は INQ と CN に対して行う．

することで更なる精度向上を得られることが確認された．

5

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月

一般論文
80

DBSJ Journal, Vol.7, No.4
March 2009

[文献]

CN
INQ
SINM
INM

78
76
74
NDCG

72
70
68
66
64
62
60
58
5

10

15

20

25

30

35

40

45

50

K

図 3 INM, SINM, INQ, CN の NDCG at K

Fig. 3 NDCG at K for INM and SINM for varying K
表4

INM，SINM，INQ，CN 間の有意差 (**, *，n.s. はそれぞれ 1%, 5% 有意差，そして有意差無しを意味する． )Table 4 Signiﬁcant diﬀerences between our proposed
methods and two baseline methods(**, * and n.s. denotep < 0.01, 0.01 < p < 0.05, and no signiﬁcant diﬀerence,
respectively)

5.

p(5)
p(10)
MAP

INM
SINM
n.s.
n.s.
n.s.

INM
INQ
**
**
**

INM
CN
n.s.
*
**

SINM
INQ
*
*
n.s.

SINM
CN
n.s.
*
n.s.

NDCG(10)NDCG(20)
NDCG(50)
NDCG(100)

n.s.
n.s.
n.s.
n.s.

**
*
**
**

*
*
**
*

n.s.
n.s.
n.s.
n.s.

n.s.
n.s.
n.s.
n.s.

まとめ

以上, 本論文では検索エンジンの性能を決定付け, かつユーザにその有用性を印象づける重要な要素の一つである検索結果上位の精度を大幅に改善するため, ユーザがクエリで表現した情報要求を満たすことができるページ群を特定し, それらを検索結果上位に提示するランキング手法を提案した.
提案手法はまず検索エンジンのクリックログを解析すること
で，クエリとページの間のクリック関係を取得する．次にこのクリック関係を利用して，クエリの情報要求とページが満たせる情[1] B. J. Jansen and A. Spink: “An Analysis of Web Documents Retrieved and Viewed”. Proc. of ICOMP’03,
pp.65-69, 2003.
[2] Beaulieu M., M. Gatford, X. Huang, S. E. Robertson,
S. Walker and P. Williams: “Okapi at TREC-3”. In
Overview of TREC-3, 1995.
[3] S. Brin and L. Page: “The Anatomy of a Large-Scale
Hypertextual Web Search Engine”. Proc. of WWW7,
pp.107-117, 1998.
[4] J. M. Kleinberg: “Authoritative sources in a hyperlinked environment” J. of the ACM, pp. 604-632, 1999.
[5] H. Cui, J. Wen, J. Nie and W. Ma : “Probabilistic Query Expansion Using Query Logs”. Proc. of
WWW’02, pp.325-332, 2002.
[6] M. Murata, H. Toda, Y. Matsuura and R. Kataoka:“Improving Mobile Web-IR using Access Concentration
Sites” Proc. of WISE’08, pp.221-234, 2008.
[7] G. R. Xue, H. J. Zeng, Z. Chen, Y. Yu, W. Y. Ma, W. S.
Xi and W. G. Fan: “Optimizing Web Search Using Web
Click-through Data” Proc. of CIKM, pp.19-26, 2004.
[8] R. Baeza-Yates: “Applications of Web Query Mining”
Proc. of ECIR’05, pp.7-22, 2005.
[9] A. Broder: “A taxonomy of web search.” ACM SIGIR
Forum, 36(2), 2002.
[10] T. Masada, T. Kanazawa, A. Takasu and J. Adachi:“Improving Web Search by Query Expansion with a
Small Number of Terms” Proc. of NTCIR-5, 2005.

村田 眞哉 Masaya MURATA
NTT サイバーソリューション研究所 所属．2007 年早稲田大学
大学院理工学研究科修了．同年, 日本電信電話 (株) 入社. 以来，情報検索の研究に従事. 日本データベース学会会員.

戸田 浩之 Hiroyuki TODA

NTT サイバーソリューション研究所 所属．2007 年筑波大学大学院システム情報工学研究科博士後期課程修了. 1999 年日本電信電話 (株) 入社. 以来，情報検索，情報抽出の研究に従事. 博士(工学). ACM SIGIR, 情報処理学会, 電子情報通信学会会員.

松浦 由美子 Yumiko MATSUURA

NTT サイバーソリューション研究所 主任研究員．1993 年慶応報要求をキーワードベクトルで表現し， これらの類似度を検索

義塾大学大学院理工学研究科修了．同年，日本電信電話 (株) 入

結果のランキングに反映させる．

社. 以来，マルチメディアの研究に従事. 情報処理学会会員.

提案手法は実際の検索エンジンのログ及びインデクスを利用した評価実験によりその有効性, 特に検索結果上位ランクの精度向片岡 良治 Ryoji KATAOKA

NTT サイバーソリューション研究所 主幹研究員．1987 年千葉

上に対して非常に効果的であることが実証された. また，その際大学大学院電子工学専攻修士課程修了．同年，日本電信電話 (株)に必要となる INQ ベクトルと INP ベクトルの生成はオフライ

入社. 以来，トランザクションの並行処理制御方式の研究，マルン処理で行われ，かつ通常の全文検索に追加される計算コスト

チメディア情報システムの研究，ポータルサービスシステムの研も少ないので実用的である．今後は他のデータセットを複数用い

究開発に従事. 情報処理学会会員.

て，提案手法の性能を評価する.

6

日本データベース学会論文誌 Vol.7, No.4
2009 年 3 月