JP5508232B2 - クエリ推薦装置、クエリ推薦方法、クエリ推薦プログラム - Google Patents

Description

本発明は、検索エンジンの検索ログに基づきユーザに推薦クエリを提供する技術に関する。

近年、インターネット上の情報は急激に増加し、ユーザが必要な情報を検索する検索エンジンの重要性が高まっている。この検索エンジンには、ユーザの検索状況を示すログファイルが蓄積されているため、該ログファイルを分析し、検索サービスの向上に利用する試みが行われている。

表１は、一般的なログファイルを示している。ここでは「日付」、「ユーザＩＤ」、「クエリ名」、「クリックＵＲＬ」、「ランキング順位」の項目に関する情報が記録されている。具体的には、「日付」の項目にはユーザが検索結果のＵＲＬをクリックした日付が記録され、「ユーザＩＤ」の項目には検索クエリを用いて検索したユーザの所有するＩＤが記録され、「クエリ名」の項目にはユーザが検索に利用したクエリ名が記録され、「クリックＵＲＬ」の項目にはユーザが検索結果中でクリックしたＵＲＬが記録され、「ランキング順位」の項目にはクリックＵＲＬの検索ランキングの順位が記録される。

検索エンジンでは、このようなログファイルをユーザの検索行動の効率化、例えば推薦クエリの提示に利用している。この推薦クエリは、図１に示すように、ユーザが検索エンジンに投入したクエリと、検索結果をクリックしたＵＲＬとをペアにした二部グラフを用いて定められている。図１中、左側のｑ₁〜ｑ₃はユーザ投入のクエリ名を示し、右側のｕ₁〜ｕ₅は検索結果からユーザがクリックしたＵＲＬを示し、該両者がエッジで連結されている。このような二部グラフを解析し、結び付きの強いクエリを推薦クエリとして用いている。

ところが、二部グラフに基づく推薦クエリの提示は、利用頻度の高いクエリはログファイル中の検索ログが多く有効であるものの、利用頻度の少ないクエリでは検索ログが少ないため、関連するクエリも少なく、推薦できるクエリが希少となる問題が生じる。

そこで、利用頻度の少ないクエリに対するクエリ推薦技術が非特許文献１に提案されている。ここではユーザ投入のクエリと実際にクリックしたＵＲＬとを結び付けたクリックグラフ（二部グラフ）と、ユーザ投入のクエリと実際にはクリックしていないＵＲＬとを結び付けたスキップグラフを用いてクエリを推薦している。図２は、図１のクリックグラフから得られるスキップグラフ例を示し、該スキップグラフによればクリックグラフでは繋がりのないクエリ同士が繋がりをもつようになり（例えばｑ₁．ｑ₂．ｑ₃がｕ₂を介して繋がりを持つ）、ユーザに推薦するクエリ数を増やすことができる。

ここではクリックグラフから得られる特徴量は、クリックされたＵＲＬで繋がるクエリ同士の明示的な関連度として扱っている。また、スキップグラフから得られる特徴量は、ユーザのクリックしていないＵＲＬを介して繋がるクエリ同士の暗黙的な関連度として扱っている。このようなクリックグラフから得られるクエリ間の特徴量と、スキップグラフから得られるクエリ間の特徴量との総和を用いて、ユーザに推薦するクエリを抽出している。

Yang Song,Li-wei He,"Optimal Rare Query Suggestion With Implicit User Feedback",ACM WWW 2010,April 26-30,2010

しかしながら、非特許文献１の手法では、対象としているクエリの検索結果に対して、クリックしていないＵＲＬにスキップグラフのエッジを作成して重みを与えていくことから、該当するＵＲＬをクリックしないユーザ数が多くなると大きな重みが与えられてしまう。これではユーザの未クリックＵＲＬをクエリに関連しないＵＲＬと想定した場合に無関係のクエリが多く推薦され、ユーザの検索効率が悪化するおそれがある。

また、ログファイルを用いてスキップグラフを作成するにあたって、ログファイル中にはクエリとクリック関係の無いＵＲＬが多数存在するため、関連するクエリと判断されるクエリ同士が多くなり、この点でも無関係なクエリが数多く推薦されるおそれがある。

本発明は、上述のような従来技術の問題点を解決するためになされたものであり、高精度の推薦クエリをユーザに提供し、ユーザの検索効率の向上に貢献することを解決課題としている。

そこで、本発明は、検索ログ中、クリックされたＵＲＬで結び付けられる各クエリの検索ログを順次抽出し、抽出された検索ログ中のＵＲＬ、即ちクエリ間に介在するＵＲＬの重要度を算出する。このＵＲＬの重要度に基づきスキップグラフにおけるクエリ間の特徴量を算出することで、検索結果におけるクリック状況（例えばクリックされなかったＵＲＬが多い等）の影響を軽減してクエリ間の関連度を算出し、より高精度の推薦クエリを抽出する。このときクエリ間の距離も用いてスキップグラフにおけるクエリ間の特徴量を算出することもできる。これにより関連度の低いクエリの特徴量を小さくすることが可能となる。

具体的には、本発明に係るクエリ推薦装置の一態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出手段と、前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、特徴量合成手段の合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。

本発明に係るクエリ推薦装置の他の態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の設定した位置情報に基づくクエリ間の距離と、前記抽出手段の算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出手段と、前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、特徴量合成手段の合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。

本発明に係るクエリ推薦方法の一態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出ステップと、前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、を有し、特徴量合成ステップで合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。

本発明に係るクエリ推薦方法の他の態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで設定した位置情報に基づくクエリ間の距離と、前記抽出ステップで算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出ステップと、前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、有し、特徴量合成ステップで合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。

なお、本発明は、前記装置としてコンピュータを機能させるプログラムの態様としてもよい。このプログラムは、ネットワークや記録媒体などを通じて提供することができる。

本発明によれば、高精度の推薦クエリをユーザに提供でき、ユーザの検索効率の向上に貢献することができる。

クリックグラフ（二部グラフ）例。 スキップグラフ例。 本発明の実施形態に係るクエリ推薦装置の構成例。 同 クエリ推薦方法のフローチャート。 図４中のＳ０１のクエリ位置算出を示すフローチャート。 同 ＵＲＬの重要度算出を示すフローチャート。 同 クリックグラフからクエリ間の特徴量算出例を示す説明図。

≪装置構成例≫
図３に基づき本発明の実施形態に係るクエリ推薦装置の構成例を説明する。この推薦装置１は、検索エンジンの検索ログに基づきクリックグラフとスキップグラフとを作成し、該両グラフから得られるクエリ間の関連度、即ちクエリ間の特徴量を用いてユーザに推薦クエリを提示する。

具体的には、前記推薦装置１は、検索サービスを提供する検索エンジンと連携し、通常のコンピュータのハードウェアリソース、例えばＣＰＵ，メモリ（ＲＡＭ），ハードディスクドライブ装置，通信デバイスなどを備える。このハードウェアリソースとソフトウェアリソース（ＯＳ．アプリケーションなど）との協働の結果、前記推薦装置１は、検索クエリ記憶部２，クエリ関連ログ抽出部３，クリックグラフ作成部４，クリックグラフ特徴量抽出部５，スキップグラフ作成部６，スキップグラフ特徴量抽出部７，特徴量合成部８を実装する。

この記憶部２には、検索エンジンに投入された検索クエリ群と検索結果などの検索ログ（ログファイル）が格納されている。ここでは検索エンジンの検索ログに連動してメモリ（ＲＡＭ）あるいはハードディスクドライブ装置などの記憶装置に該検索ログをデータ格納する。表２は、前記記憶部２の格納データ例を示し、表１と同様に「日付」、「ユーザＩＤ」、「クエリ名」、「クリックＵＲＬ」、「ランキング順位」の項目に関する情報が記録されている。

前記抽出部３は、前記記憶部２を参照してクリックされたＵＲＬで繋がる各クエリ、即ち該ＵＲＬで結び付けられる各クエリの検索ログを順次抽出する。このときクリックされたＵＲＬを介して順次結び付けられるクエリの位置情報を、クエリ間に介在するＵＲＬ数に応じて設定する。また、抽出された検索ログ内のＵＲＬ、即ち前記クエリ間に介在するＵＲＬの重要度を算出する。ここではクエリの利用頻度（クエリ投入回数に対するＵＲＬのクリック回数）に基づきＵＲＬのクリック確率を算出し、該クリック確率に基づきＵＲＬのエントロピーを算出する。このエントロピーを、各ＵＲＬのエントロピーの最大値で正規化する。正規化されたエントロピーをＵＲＬの重要度に利用する。

前記グラフ作成部４は、前記抽出部３の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結したクリックグラフを作成し、前記特徴量抽出部５は、前記グラフ作成部４で作成したクリックグラフにおけるクエリ間の特徴量、即ちクエリ間の明示的な関連度を一方のクエリからＵＲＬを経由して他方のＵＲＬに到達する確率に基づき算出する。その際にクエリの投入回数に対するＵＲＬのクリック回数の割合を利用する。

前記グラフ作成部６は、前記抽出部３の抽出した検索ログに基づき各クエリとクリックされていないＵＲＬとをエッジで連結したスキップグラフを作成し、前記特徴量抽出部７は、スキップグラフにおけるクエリ間の特徴量、即ちクエリ間の暗黙的な関連度を、前記抽出手段の算出したＵＲＬの重要度と各クエリの位置情報に基づく距離を用いて算出する。

前記合成部８は、前記各特徴量抽出手段５．７の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する。ここで合成されたクエリ間の特徴量に応じてユーザに提示する推薦クエリが抽出される。抽出された推薦クエリは、インターネット経由でユーザ所有の端末（ＰＣ，携帯電話など）に表示される。

≪処理ステップ≫
以下、図４に基づき前記推薦装置１の処理ステップを説明する。ここではクエリｑ１を処理対象のクエリとする事例を説明する。このクエリｑ１が図示省略の入力部に入力されて処理が開始される。

Ｓ０１：前記抽出部３は、図示省略の入力部にクエリｑ１が入力されると、前記記憶部２にアクセスし、クエリｑ₁から順にクリックされたＵＲＬで結び付けられる各クエリの検索ログ（クリックログ）のサブセットを抽出する。このとき前記抽出部３は、該検索ログ内における各クエリの位置情報を設定し、各ＵＲＬの重要度を算出する。なお、前記サブセット・各クエリの位置情報・各ＵＲＬの重要度は、前記グラフ作成部４．６に出力される。

図５に基づき各クエリの位置情報の設定例を説明する。ここではクエリｑ₁から順にＵＲＬのクリック関係を有するクエリ（いわゆる関連クエリ）の位置情報を設定する。この関連クエリの位置情報をクエリｑ₁からの最小距離、即ちクエリｑ₁からの最小経由ＵＲＬ数に応じて設定する。まず、処理の開始にあたってＳ１２．Ｓ１３の処理回数の最大値「Ｎ＿ｍａｘ」が設定される。この処理例では「Ｎ＿ｍａｘ＝２」とし、初期値「Ｎ＝０」で処理を開始する（Ｓ１１）。なお、「Ｎ＿ｍａｘ」の値は適宜調整することができるものとする。

つぎに「Ｎ＝Ｎ＋１＝１」とし、Ｎの値「１」をｑ₁の検索ログ内における位置情報に設定し（Ｓ１２）、クエリｑ１を対象とする第１回目の検索ログ抽出を行う。すなわち、ｑ₁をクエリに持つ検索ログからＵＲＬを抽出し、併せて該ＵＲＬに結び付くクエリ、即ち該ＵＲＬとクリック関係を有するクエリを含む検索ログを抽出する（Ｓ１３）。

この抽出後に「Ｎ＝Ｎ＿ｍａｘ」が成立するか否かを確認する（Ｓ１４）。確認の結果、成立すればＳ１５に進む一方、成立しなければＳ１２に戻る。この段階では「Ｎ＝１」であるため、「Ｎ＝Ｎ＿ｍａｘ」は成立しない。したがって、Ｓ１２に戻って「Ｎ＝Ｎ＋１＝２」とし、前記抽出された検索ログに含まれるｑ₁以外のクエリ（関連クエリ１）について、検索ログ内の位置情報をＮの値「２」に設定する（Ｓ１２）。ここで設定されたｑ₁以外のクエリを対象とする第２回目の検索ログ抽出を行う。

すなわち、位置情報「２」に設定されたクエリを含む検索ログを抽出し、併せて該検索ログに含まれるＵＲＬに結び付くクエリを抽出する（Ｓ１３）。この段階では「Ｎ＝２」なため、Ｓ１４が成立し、Ｓ１５に進む。Ｓ１５では、「Ｎ＝Ｎ＋１＝３」とし、最後にＳ１３で抽出されたクエリ（関連クエリ２）について検索ログ内の位置情報をＮの値「３」に設定（関連クエリ１を除く）して処理を終了する。これによりクエリｑ₁から順次ＵＲＬ経由で結び付く各クエリの位置情報を最小経由のＵＲＬ数に応じて設定することができる。なお、この設定例では位置情報は「Ｎ＋１」（ＵＲＬ数＋１）で設定されている。

図６に基づきＵＲＬの重要度の算出方法を説明する。まず、処理の開始により前記サブセット中の各ＵＲＬとクリック関係を有するクエリとを抽出する（Ｓ２１）。ここでは一例として式（１）のＵＲＬを対象とし、該式（１）のＵＲＬとクリック関係を有するクエリｑ_i（ｉ＝１，２，・・・，ｎ）を抽出する。

つぎにＳ２１で抽出したクエリｑ_iの利用頻度から式（１）のＵＲＬのクリック確率を算出する（Ｓ２２）。すなわち、クエリｑ_iの前記サブセット内における投入回数を基に式（２）を用いて、式（１）のＵＲＬに対するクリック確率（Ｐ_ik）を算出する。

ここでは式（１）のＵＲＬとクリック関係を有するすべてのクエリｑ_i（ｉ＝１，２，・・・，ｎ）に対して、式（２）を用いてクリック確率（Ｐ_ik）を算出する。そして、Ｓ２２で算出したクリック確率（Ｐ_ik）を基に式（１）のＵＲＬのエントロピーＥ_kを、式（３）を用いて算出する（Ｓ２３）。

最後にＳ２１〜Ｓ２３の処理を前記サブセットに含まれるすべてのＵＲＬに対して実行し、各ＵＲＬのエントロピーＥ_kの最大値を用いて式（４）で正規化する（Ｓ２４）。正規化されたエントロピーＥ_kを各ＵＲＬの重要度とする。

Ｓ０２：前記グラフ作成部４は、前記抽出部３からの出力情報のうちＳ０１で抽出された前記サブセットを基にクリックグラフを作成する。このクリックグラフの作成方法を説明する。ここで前記サブセットが表２の検索ログであれば、ｑ₁のクエリからはｕ１．ｕ４のＵＲＬがクリックされているため、図１のクリックグラフに示すように、ｑ₁からｕ₁．ｕ₄へそれぞれエッジを連結させる。同様に表２の検索ログに基づきｑ₂．ｑ₃に対しても同様にクリックグラフを作成する。すなわち、ｑ₂からｕ₃．ｕ₅にエッジを連結し、ｑ₃からｕ₁．ｕ₅へエッジを連結させる。このようにクリックグラフを作成し、作成されたクリックグラフを前記抽出部３からの出力情報（クリック確率Ｐ_ikを含む。）と併せて前記特徴量抽出部５に出力する。

Ｓ０３：前記特徴量抽出部５は、Ｓ０２で作成されたクリックグラフにおけるエッジの重み、即ちクエリ間の特徴量（関連度）を算出する。このクリックグラフからの特徴量は式（５）〜（７）を用いて算出する。

式（５）〜（７）を用いてクリックグラフにおけるすべてのクエリ間の特徴量を計算する。ここで「ｃｌｉｃｋ＿ｖａｌｕｅ_ij」は、クエリｑ_iとクエリｑ_jの関連性を表す特徴量を示している。また、「ｋ」は式（１）のＵＲＬを示し、「Ｐ_ik×Ｐ_kj」はクエリｑ_iを出発して式（１）のＵＲＬを経由し、式（１）のＵＲＬからクエリｑ_jへ到達する確率を示している。図７にクリックグラフにおけるクエリｑ₁とクエリｑ₂の関連性を表す特徴量「ｃｌｉｃｋ＿ｖａｌｕｅ₁₂」を対象とした具体的な計算方法を示しておく。なお、算出したクエリ間の特徴量は前記合成部８に出力される。

Ｓ０４：前記グラフ作成部６は、前記抽出部３からの出力情報のうちＳ０１で抽出された前記サブセットを基にスキップグラフを作成する。このスキップグラフの作成方法を説明する。ここではＳ０２と同様に前記サブセットが表２の検索ログとする。このときｑ₁に着目するとｕ₁．ｕ₄はクリックされているが、ｕ₂．ｕ₃．ｕ₅はクリックされていない。そこで、ｑ₁からクリックされていないｕ₂．ｕ₃．ｕ₅に対して、図２に示すように、エッジを連結させる。

また、ｑ₂．ｑ₃に対しても、ｑ₂からクリックされていないｕ₁．ｕ₂．ｕ₄にエッジを連結し、ｑ₃からクリックされていないｕ₂．ｕ₃．ｕ₄にエッジを連結させる。このようにスキップグラフを作成し、作成したスキップグラフを前記抽出部３からの出力情報と併せて前記特徴量抽出部７に出力する。

Ｓ０５：前記特徴量抽出部７は、Ｓ０４で作成されたスキップグラフにおけるエッジの重み、即ちクエリ間の特徴量（クエリ間の関連度）を算出する。このとき前記グラフ作成部６からの出力情報中、各クエリの位置情報に基づくクエリ間の距離（ｑ_iの位置−ｑ_jの位置）を算出する。

このクエリ間の距離と前記出力情報中のＵＲＬの重要度Ｅ_kとを用いて、スキップグラフにおけるクエリ間の特徴量を算出する。この算出には式（８）を用いるものとし、算出されたクエリ間の特徴量は前記合成部８に出力される。

Ｓ０６：前記合成部８は、Ｓ０３．Ｓ０５で前記各特徴量抽出部５．７から出力されたクリックグラフの特徴量とスキップグラフの特徴量とを合成し、最終的なクエリ間の特徴量を算出する。この算出には式（９）を用いる。

式（９）中、「α」は「０〜１．０」までの実数を示し、予め任意の値に設定することができる。以下、「α」の値に「０．７」を設定し、クエリとして「恋愛占い」，「心理テスト」，「タロット占い」，「姓名判断」，「誕生日占い」を対象とした事例を説明する。ここではクリックグラフからは表３に示すクエリ間の特徴量が得られ、スキップグラフからは表４に示すクエリ間の特徴量が得られたとする。

このとき「恋愛占い」についてクエリ間の特徴量は、
「恋愛占い」⇒「心理テスト」＝０．７×０．０＋０．３×０．４＝０．１２
「恋愛占い」⇒「タロット占い」＝０．７×０．５＋０．３×０．２＝０．４１
「恋愛占い」⇒「姓名判断」 ＝０．７×０．０＋０．３×０．３＝０．０９
「恋愛占い」⇒「誕生日占い」＝０．７×０．１＋０．３×０．０＝０．０７
と算出される。

算出された特徴量が閾値を超えていれば、推薦クエリとして抽出される一方、閾値を超えていなければ、推薦クエリとして抽出されないものとする。この閾値は仕様に応じて適宜に調整できるものとする。例えば閾値を「０．１」に設定すれば、「心理テスト」と「タロット占い」が推薦クエリとして抽出される。抽出される推薦クエリは、インターネット経由でユーザ所有の端末に表示されてユーザに提示される。

このような前記推薦装置１によれば、スキップグラフにおけるクエリ間の特徴量を算出するにあたって、式（８）に示すように、クエリ間を結び付けるＵＲＬの重要度Ｅ_kを利用するため、検索ログ中のクリック状況（クリックされていないＵＲＬが多いなど）の影響が軽減される。したがって、非特許文献１のように検索ログ中の未クリックＵＲＬが増加するほど前記特徴量が大きくはならず、これによりユーザに高精度の推薦クエリを提示でき、ユーザの検索効率の向上に貢献できる。

このとき非特許文献１では、スキップグラフを作成する際にクエリとクリック関係に無いすべてのＵＲＬにエッジを作成しているため、関連度の低いクエリとＵＲＬにもエッジが作成されるものの、前記推薦装置１の式（８）によれば、ＵＲＬで結び付けられるクエリ間の距離（ｑ₁の位置−ｑ_jの位置）を考慮しているため、かかるクエリ間の関連度を低くすることができ、この点でも精度のよい推薦クエリをユーザに提示できる。

なお、本発明は、上記実施形態に限定されるものではなく、例えばスキップグラフおけるクエリ間の特徴量算出にあたってＵＲＬの重要度Ｅ_kのみを用いることもできる。この場合にはＳ１２．Ｓ１５の位置情報の設定を行うことなく、式（８）中から「１／ｑ₁の位置−ｑ_jの位置＋１」を削除すればよい。このときＵＲＬで結び付けられるクエリ間の距離は考慮されないものの、検索ログ中のクリック状況（クリックされていないＵＲＬが多いなど）の影響が軽減される効果を得ることができる。

≪プログラムなど≫
本発明は、前記推薦装置１の各部２〜８の一部もしくは全部として、コンピュータを機能させる文書検索プログラムとして構成することもできる。このプログラムによれば、Ｓ０１〜Ｓ０６．Ｓ１１〜Ｓ１５．Ｓ２１〜Ｓ２４の一部あるいは全部をコンピュータに実行させることが可能となる。

前記プログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，ＢＤ−ＲＯＭ，ＢＤ−Ｒ，ＢＤ−ＲＥなどの記録媒体に記録して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。

１…クエリ推薦装置
２…検索クエリ記憶部（検索クエリ記憶手段）
３…クエリ関連ログ抽出部（クエリ関連ログ抽出手段）
４…クリックグラフ作成部（グラフ作成手段）
５…クリックグラフ特徴量抽出部（クリックグラフ特徴量抽出手段）
６…スキップグラフ作成部（グラフ作成手段）
７…スキップグラフ特徴量抽出部（スキップグラフ特徴量抽出手段）
８…特徴量合成部（特徴量合成手段）

Claims (9)

1. 検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示するクエリ推薦装置であって、
   検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、
   前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、
   グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、
   グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出手段と、
   前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、
   特徴量合成手段の合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦装置。
2. 検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示するクエリ推薦装置であって、
   検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、
   前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、
   グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、
   グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の設定した位置情報に基づくクエリ間の距離と、前記抽出手段の算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出手段と、
   前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、
   特徴量合成手段の合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦装置。
3. 前記抽出手段は、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
   該クリック確率に基づき各ＵＲＬのエントロピーを算出し、各エントロピーの最大値をもって各ＵＲＬのエントロピーを正規化し、
   正規化されたエントリピーを各ＵＲＬの重要度とすることを特徴とする請求項１または２のいずれか１項に記載のクエリ推薦装置。
4. クリックグラフ特徴量抽出手段は、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
   該クリック確率に基づき一方のクエリからＵＲＬを経由して他方のクエリに到達する前記到達確率を算出する
   ことを特徴とする請求項１〜３のいずれか１項に記載のクエリ推薦装置。
5. 検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示する装置の実行するクエリ推薦方法であって、
   検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、
   前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、
   グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、
   グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出ステップと、
   前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、を有し、
   特徴量合成ステップで合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦方法。
6. 検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示する装置の実行するクエリ推薦方法であって、
   検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、
   前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、
   グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、
   グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで設定した位置情報に基づくクエリ間の距離と、前記抽出ステップで算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出ステップと、
   前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、有し、
   特徴量合成ステップで合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦方法。
7. 前記抽出ステップにおいて、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
   該クリック確率に基づき各ＵＲＬのエントロピーを算出し、各エントロピーの最大値をもって各ＵＲＬのエントロピーを正規化し、
   正規化されたエントリピーを各ＵＲＬの重要度とすることを特徴とする請求項５または６のいずれか１項に記載のクエリ推薦方法。
8. クリックグラフ特徴量抽出ステップにおいて、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
   該クリック確率に基づき一方のクエリからＵＲＬを経由して他方のクエリに到達する前記到達確率を算出する
   ことを特徴とする請求項５〜７のいずれか１項に記載のクエリ推薦方法。
9. 請求項１〜４のいずれか１項に記載のクエリ推薦装置としてコンピュータを機能させるクエリ推薦プログラム。

Images