論文

DBSJ Letters Vol.6, No.4

検索結果中のアクセス集中サイトを利用したクエリ拡張法の提案
A Query Expansion Method Using Access Concentration Sites in Search Result

1.

はじめに近年モバイル環境からの Web アクセスが増え、アクセス可能なモバイルサイトが爆発的に増加している。これに伴いモバイルサイトに対する検索サービスの需要が高まり、モバイル検索のランキング精度向上が重要な研究課題となっている。
しかしウェブサイトに対する従来の有効なランキング手法をそ村田 眞哉 ♥
松浦 由美子 ♠戸田 浩之 ♦
片岡 良治 ♣

Masaya MURATA
Yumiko MATSUURA

Hiroyuki TODA
Ryoji KATAOKAのままモバイルサイトに応用しても、例えば以下に挙げるモバイ
ルサイト特有の性質により必ずしもよいランキング結果を得ることができない。

1. モバイルサイトは画面が狭いモバイル端末向けに作られているため、テキスト量がウェブサイトと比べ圧倒的に少ない

2. 有料の公式サイトや企業が運営しているサイトが多いことから、一般のウェブサイト群で見られるような有益な情報に近年、モバイルコンテンツ検索に対する有効なランキング手法の研究が盛んに行われている。有望な手法の一つにクエリ拡張が対してリンクが張られているというよりは、サイト内をナビゲートする為のリンクが多い挙げられるが、実際のサーチエンジンでの利用を考えた場合には、計算コストの面から少ない拡張語数で精度を上げる事が必要とされている。そこで我々はクリックログに着目し、クリックが集中している検索結果のタイトルやスニペット (アクセス集中サイト) にはユーザが有用だと判断した表現があり、そこから取得

1 は Okapi BM25[1] のような bag-of-words ranking functionの困難を、 2 はウェブサイト集合に重要度の順序構造を導入した
PageRank[2] のような link-based ranking の困難を意味している。さらに追い撃ちをかけるのが、クエリのキーワード数の少なされるキーワードがそのような拡張語の候補になるのではないさである [3]。携帯端末の予測変換機能により、各キーワードのかと考えた。そこでアクセス集中サイトをクリックログから的確

スペルはウェブサイト検索に比べて正確にはなるが、テンキーのに判別する方法を考案し、そこから取得される拡張語によるク打ちにくさによりキーワード数は少なくなる [4]。

エリ拡張法と、拡張語と初期のクエリに対する近傍性に基づく

そこで我々はユーザが検索結果を見て、実際にクリックするまre-ranking を結び付けた新手法を提案し、実験により検証した。

でに至る行動を考えた。そして、ユーザは検索結果のタイトルやスニペットを見て、有用だと判断したらクリックするのではない

Many studies are underway on ranking algorithms for mobile contents search. Query expansion is a quite promising method, but we need toachieve high search eﬀectiveness with few expansion
terms to reduce the calculation cost. Our solution
is to focus on click logs, considering that there areexpressions that users have found useful in the title and snippet of search results clicked intensively(access concentration sites) and these expressions
become expansion term candidates. We introduce
a technique that can precisely identify the accessconcentration sites using click logs and present a
new method in which we combine a query expansion
method using these terms with re-ranking based on
the proximity of those terms with the original query.
We verify our method in an experiment.

かと仮定した。以降、本論文ではこのクリックが集中している検索結果のタイトルとスニペットのことをアクセス集中サイトと呼ぶ。しかしながらアクセス集中サイトを特定し、このサイトに高スコアを与えるだけの手法は正しくない。なぜならタイトルやスニペットが良いからといっても、そのサイト自体が必ずしも良いとは言えないからである。そこで我々はクエリ拡張 (queryexpansion) を利用することを考えた。
我々の仮定によると、クリックが集中している検索結果のタイトルやスニペットにはユーザが有用だと判断したキーワードがある。従ってこのキーワードを含むサイトがクエリに対する正解サイトである可能性が高いということになり、このキーワードでクエリ拡張を行うことで検索結果の精度向上が期待できる。このアイデアを実現するためには以下の課題を解決しなければならない。

♥

日本電信電話株式会社 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• アクセス集中サイトの的確な特定• 計算コストの面からできるだけ少ない拡張語 (1〜5 個) で大きな精度向上を得られること
これら課題に対して我々はクリックログを解析することでアクセス集中サイトを的確に特定し、そのタイトルとスニペットから拡張語を取得する方法を考案した。そしてこの拡張語によるクエリ拡張と、拡張語とクエリに対する近傍性に基づく検索結果の日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4

re-ranking を結び付けた新手法を提案し、計算機実験により検証した。この結果を報告する。
以下、2 章で関連研究、3 章で本論文に用いたベースライン、4章で我々の提案手法について説明し、 5 章でその実験結果を検証する。そして 6 章で本論文をまとめる。

2.

• 拡張語とクエリとの近傍性に基づく検索結果の re-ranking

4.1

アクセス集中サイトを用いたクエリ拡張

我々は数多くのユーザが有用だと判断し、クリックが集中しているサイト (アクセス集中サイト) から拡張語を的確に取得したい。そこでクリックログを解析し、検索結果のランク vs クリッ
ク回数の座標上でグラフを描き、一般的な傾向である指数関数的関連研究減少曲線と比べて傾きが大きく変化しているサイトに注目する。
クリックログを利用する一般的なクエリ拡張は、まず入力されたクエリとクリックログを照合し clicked sites を特定することから始まる。そしてこれを基に拡張語を取得する。 Cui らはクリッ

これは通常とは異なるサイトがそこに存在することを意味しており、その一つ後ランクのサイトのクリック回数が相対的に大きく減少しているサイトがアクセス集中サイトであると仮定した。

クログから clicked sites を特定し、その中の各ワードに対してクエリとの共起確率を計算し、この値の高い拡張語を用いてクエリ拡張を行っている [5]。しかしながら彼らの結果によると、拡張語 30〜50 個で最大精度を出しており、実用面から見ると計算コストがかかってしまう。

Shen らはクエリの変更過程 (re-formulation) にも注目している [6]。ユーザはクエリを入力し検索結果を眺め、もしこれが希望通りでなかったらクエリをより良いものに変更すると考えられる。このクエリの re-formulation はクリックログから取得可能で、彼らはこの過去一連の re-formulation を効果的に取り扱うことで現在のクエリを補完し、検索精度の向上を実現している。

Zhuang ら、Parikh らもクエリの re-formulation を利用する同様な手法を考案しているが、Shen らと異なるのはクエリの re-formulation をクエリ拡張ではなく、検索結果に対するre-ranking に用いている点である [7] [8]。

3.

 log(1 + tf (ti , dj )) × idf (ti )i=1

ゆえにその一つ後ろのサイトは通常と比べて傾きが大きく減少する

Fig. 1 A curve example of click number versus results
curves to be intensively accessed. The inclination to the1. 我々が採用したベースライン 1 は文章長で正規化した tf ·idf法である。クエリ q が形態素 ti , (i = 1, 2, 3, · · · , n) から成るとし、ドキュメントを dj と表す。このドキュメント dj のscore(dj , q) =ランク vs クリック回数の曲線例。上に凸の山ができているランクのサイトにアクセスが鋭く集中していると考える。

rank. We consider sites that demonstrate strongly-peaked

ベースライン

スコア値は

図1log lengthj

next rank site considerably decreases compared with anormal curve.

なぜならユーザに有用だと判断されたサイトは数多くクリックさ(1)で与えられる。ここで lengthj はドキュメント dj の文章長を表す。そしてこのスコア値の高いサイトから順に並べ、これを検索結果とする。

れ、この座標上に上に凸の山ができると考えられるからである。
図 1 を例にとり、この考えを詳しく説明する。横軸が検索結果のランク、縦軸がクリック回数である。クリックログに対して全クエリを用いて解析し、描いた曲線を任意クエリ曲線、クエリを一つ固定して描かれた曲線を特定クエリ曲線と呼ぶ。もしこの図

2. ベースライン 2 は疑似フィードバック (pseudo-feedback) にのように、任意クエリ曲線に対して特定クエリ曲線が、あるランよるクエリ拡張である。拡張語の取得先としてクエリに対ク箇所に上に凸の山を描いているならば、このランクのサイトにする検索結果上位 10 件を使用する。検索結果のタイトルとアクセスが鋭く集中していると考える。これは極端な例ではある

スニペットを形態素 ti , (i = 1, 2, 3, · · · , n) に分解し、そのが、本提案手法はこのアクセス集中度合の微妙な変化を、特定クlog(1 + tf (ti , dj )) · idf (ti ) が高いものから順に拡張語として採用し、クエリ拡張を実行する。

エリ曲線のランク r とランク r + 1 における傾きで捉える。
クエリに対するあるサイトのランク rq,j とその一つ後のランク rq,j + 1 のサイトに注目し、それぞれのクリック回数を4.

提案手法

提案手法はクリックログを用いたクエリ拡張がベースであるが、従来との違いは以下にある。

• アクセス集中サイトを用いたクエリ拡張

2

cc1 (q, rq,j )、cc1 (q, rq,j + 1) とする。また全クエリに対する検索結果のランク rj と rj +1 のクリック回数を T cc2 (rj )、T cc2 (rj +1) とすると、Inc(q, dj ) = arctan ((cc1 (q, rq,j + 1) − cc1 (q, rq,j ))/1)+ arctan ((T cc2 (rj + 1) − T cc2 (rj ))/1)

日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4の負値が大きいサイトがアクセス集中サイトで、この絶対値がアクセス集中度合であると言える。なぜならアクセス集中サイトのbaseline eq.(1)pseudo-feedbackeq.(4)eq.(4) & eq.(5)44

次のランクのサイトは、相対的にクリック回数が大きく減少し、集中度合の高いサイトほどこの減少量が大きいと考えられるから42である。arctan(x) は傾きを角度に変換する関数であり、これを用いる理由を以下に述べる。一般的に上位ランクのサイトほど数多くクリックされる傾向があるので、上位ランクの傾きは下位ラ40ンクと比べて簡単に大きくなり、これでは正確にアクセス集中サイトを抽出することができない。そこで約 x = 2 以降で急激に38値の増加が減少する arctan(x) の性質を利用し、このバイアスを軽減した。結果、値域は −1.5  Inc(q, dj )  1.5 になる。第2 項目は下位ランクのクリック偶発性に対処する項である。 そしてこの Inc(q, dj ) が −2.0 より小さいランクのサイトをアクセス3651015202530

集中サイトとみなし、そこから拡張語群を取得した。
図2

拡張語の順序付けは、Inc(q, dj ) の絶対値に拡張語の IDF を掛けた

w(ti ) =

縦軸は MAP、横軸は拡張語の数。直線は 3 節のベースラ

イン 1 で、▲がベースライン 2 の疑似フィードバックによるクエリ拡張、■がアクセス集中サイトを用いたクエリ拡張、●がidf (ti ) × log(1 + |Inc(q, dj )|)(2)

さらに■を拡張語のクエリに対する近傍性に基づき re-ranking

djした実験結果を表すの値で行い、この上位 N 個でクエリ拡張を実行し、式 (1) に基Fig. 2 Vertical axis is MAP and horizontal axis is theづき検索を行う。

number of expansion terms. Straight line plots our base-

4.2

line 1 at Section 3, ▲ line plots the query expansion with拡 張 語 の ク エ リ に 対 す る 近 傍 性 に 基 づ く re-ranking

pseudo-feedback(baseline 2), ■ line plots the query expansion with access concentration sites, ● plots the re-

4.1 節の方法で得られる拡張語はドキュメント中のクエリに対し、近い距離 (近傍) にあることでさらなる効果を生むと期待でranking of ■ based on the proximity of expansion terms

きる。なぜならボディに対する拡張語はアクセス集中サイトのスwith the original query.

ニペットから取得しており、我々の検索システムのスニペットは結果はベースラインの MAP が 35.2% であるのに対して、予備クエリを中心とする決まった形態素数分を表示するからである。

実験の結果最も精度の高かった疑似フィードバックによるクエリ

ゆえに本手法を我々のような検索システムに適用すると、拡張語拡張は拡張語数 1〜5 個で平均 MAP41.23% である。式 (2) にを取得する段階において、自動で拡張語にクエリに対する近接性基づくアクセス集中サイトを用いたクエリ拡張では拡張語数 1を含ませていることになるからである。これを踏まえ、4.1 節の〜5 個で平均 MAP42.51%、さらに式 (3) によりこの検索結果クエリ拡張で得た検索結果上位 100 件をさらに re-ranking するを re-ranking する我々の提案手法では拡張語数 1〜5 個で平均ことを考える1 。
クエリを中心とする形態素数 25 個分の窓 L を検索結果の各ドMAP が 43.23% になっている。また最大 MAP は拡張語数 2 個で 44.5% に達している。これはベースラインの精度を大幅に改キュメントボディから抜き出し、この中に拡張語 ti が含まれて善しており、本提案手法の有効性を実証している。この結果はアいればそれに対応する値 (式 2) を加算していく。窓 L に n(ti )クセス集中サイトから得られる拡張語がクエリに対する highly個の拡張語 ti が含まれる場合の re-ranking ドキュメントスコア
値 r score(dj , q) は、最初の検索結果のドキュメントスコア値をrelevant terms であることを意味しており、クエリに対する近傍性と結びつけることによって、少ない拡張語数 (１〜5 個) でのscore(dj , q) とすると、クエリ拡張の精度をさらに向上させる効果があることを示していr score(dj , q) = score(dj , q) +n(ti ) × w(ti )(3)ti ∈Ljで与えられる。このスコアの大きいサイトから順に並べ、これをる。精度が向上したクエリ群に明確な共通性は無いが、固有名詞(人名、店名、商品名) などが比較的多く含まれていた。表 1、2に有効であったクエリの一部例を、title、snippet それぞれから取得された拡張語と共に記す。

最終検索結果とする。この re-ranking までの一連の処理が我々の提案手法である。

5.

実験結果

6.

まとめ

以上、本論文ではアクセス集中サイトを多くの検索結果の中からクリックログを解析することにより判別し、そこから取得され実験結果を図 2 に示す。
13

近接検索でもよいる拡張語を用いてクエリ拡張を行い、拡張語のクエリに対する近傍性に基づき検索結果を re-ranking する新手法を提案し、モバ

日本データベース学会 Letters Vol.6, No.4

論文

DBSJ Letters Vol.6, No.4

表1「あかひげ」に対して抽出された拡張語の例

Table 1 An example of expansion terms for “akahige”

1位
2位
3位

傾き正規化

疑似フィードバック

シソ酢 (from title)、薬局 (from snippet)akahige(from title)、
全国温泉 (from snippet)

薬局、NEW

あか、あかあか、新橋薬局、泊まれる

表2「トイザらス」に対して抽出された拡張語の例

Table 2 An example of expansion terms for “toizarasu”

傾き正規化

1位
2位
3位

疑似フィードバック

日本トイザらス、 BLYTHEROOM、
日本トイザらス

PRMobile、遊ベル
Bee、PR

トイザらス DC、マイトカイザー

Plaza、ネタなべ

イルコンテンツに対して実験を行った。この結果により、本論文の目的であった、少ない拡張語数 (1〜5 個) でベースラインを大きく上回る精度を得ることを達成し、本提案手法の有効性を実証した。
我々の提案手法は、数多くのユーザが有用だと判断したアクセス集中サイトから拡張語を的確に取得し、これに基づきクエリ拡張を行うことが重要であるという考えの下に成り立っている。そこで一つのクエリを固定してクリックログを解析し、検索結果ランク vs クリック回数の座標上でこの曲線を描き、傾きに注目した。数多くのユーザが有用だと判断し、クリックが集中するサイトのランクと次のランクの間のクリック回数には大きな差ができるはずである。なぜならこのようなサイトは座標上に上に凸の山

at TREC-3”. Proceedings of the Third Text REtrievalConference(TREC 1994)[2] Lawrence Page, Sergey Brin, Rajeev Motwani, TerryWinograd, “The PageRank Citation Ranking: Bringing
Order to the Web”. 1998
[3] Masaya Murata, Hiroyuki Toda, Yumiko Matsuura andRyoji Kataoka, “A Query Expansion Method Using Access Concentration Sites in Search Result”. Proceedingsof the DataBase and Web symposium (DBWeb 2007)[4] 佐野正弘, ” 大人が知らない携帯サイトの世界〜PC とは全く違うもう 1 つのネット文化〜” マイコミ新書, 2007[5] Hang Cui, Ji-Rong Wen, Jian-Yun Nie and Wei-Ying Ma,“Probabilistic Query Expansion Using Quer Logs”. Proceedings of the 11th international conference on World
Wide Web 2002, 325-332[6] Xuehua Shen, Bin Tan and ChengXiang Zhai, “ContextSensitive Information Retrieval Using Implicit Feedback”. Proceedings of the 28th annual international ACM
SIGIR conference on Research and development in information retrieval 2005, 43-50[7] Ziming Zhuang and Silviu Cucerzan : “Re-Ranking
Search Results UsingQuery Logs”. Proceedings of the15th ACM international conference[8] Jignashu Parikh and Shyam Kapur, “Unity: RelevanceFeedback using User Query Logs”. Proceedings of the
29th annual international ACM SIGIR conference on Research and development in information retrieval 2006,689-690

村田 眞哉 Masaya MURATAを描くと考えられるからである。そしてこの山の傾きの減少度合

NTT サイバーソリューション研究所 所属．2007 年早稲田大学

が大きくなればなる程、つまりこの山の底辺に対する傾きの角度

大学院理工学研究科修了．同年, 日本電信電話 (株) 入社. 情報検が大きくなればなる程、このランクのサイトが数多くのユーザを引き付け、有用だと判断された証拠になると考えたのである。
そしてもう一つ重要なことは、拡張語のクエリに対する近傍性である。今回利用した検索システムのスニペットはクエリを中心とする決まった形態素数分を表示する。ゆえに我々の手法をこのような検索システムに適用し取得した拡張語は、クエリの近傍にあればよりいっそうの効果があると期待できる。この考えに基づ
きクエリ拡張で得た検索結果を、拡張語のクエリに対する近傍性に基づき re-ranking した。
今後は本手法をさらに改善し、正例による正のフィードバックのみならず、負例による負のフィードバックも検討したい。そしてモバイルならではの問題と特徴を見極め、より多種多様なテストコレクションで実験を行う。

[文献][1] Stephen E. Robertson, Steve Walker, Susan Jones,
Micheline Hancock-Beaulieu, and Mike Gatford, “Okapi

4索の研究に従事. 情報処理学会正会員.

戸田 浩之 Hiroyuki TODA

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

松浦 由美子 Yumiko MATSUURANTT サイバーソリューション研究所 主任研究員．1993 年慶応義塾大学大学院理工学研究科修了．同年、日本電信電話 (株) 入社. マルチメディアの研究に従事. 情報処理学会会員.

片岡 良治 Ryoji KATAOKA

NTT サイバーソリューション研究所 主幹研究員．1987 年千葉大学大学院電子工学専攻修士課程修了．同年、日本電信電話 (株)入社. トランザクションの並行処理制御方式の研究、マルチメディア情報システムの研究、ポータルサービスシステムの研究開発に従事. 情報処理学会会員の研究に従事. 情報処理学会正会員.

日本データベース学会 Letters Vol.6, No.4