(57)【特許請求の範囲】
【請求項１】
検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示するクエリ推薦装置であって、
検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、
前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、
グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、
グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出手段と、
前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、
特徴量合成手段の合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦装置。
【請求項２】
検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示するクエリ推薦装置であって、
検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、
前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、
グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、
グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の設定した位置情報に基づくクエリ間の距離と、前記抽出手段の算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出手段と、
前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、
特徴量合成手段の合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦装置。
【請求項３】
前記抽出手段は、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
該クリック確率に基づき各ＵＲＬのエントロピーを算出し、各エントロピーの最大値をもって各ＵＲＬのエントロピーを正規化し、
正規化されたエントリピーを各ＵＲＬの重要度とすることを特徴とする請求項１または２のいずれか１項に記載のクエリ推薦装置。
【請求項４】
クリックグラフ特徴量抽出手段は、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
該クリック確率に基づき一方のクエリからＵＲＬを経由して他方のクエリに到達する前記到達確率を算出する
ことを特徴とする請求項１〜３のいずれか１項に記載のクエリ推薦装置。
【請求項５】
検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示する装置の実行するクエリ推薦方法であって、
検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、
前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、
グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、
グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出ステップと、
前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、を有し、
特徴量合成ステップで合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦方法。
【請求項６】
検索クエリ記憶手段に格納された検索ログに基づきユーザに推薦クエリを提示する装置の実行するクエリ推薦方法であって、
検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、
前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、
グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、
グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで設定した位置情報に基づくクエリ間の距離と、前記抽出ステップで算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出ステップと、
前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、有し、
特徴量合成ステップで合成したクエリ間の特徴量を、予め設定された閾値と対比した結果に応じてユーザに推薦クエリを提示することを特徴とするクエリ推薦方法。
【請求項７】
前記抽出ステップにおいて、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
該クリック確率に基づき各ＵＲＬのエントロピーを算出し、各エントロピーの最大値をもって各ＵＲＬのエントロピーを正規化し、
正規化されたエントリピーを各ＵＲＬの重要度とすることを特徴とする請求項５または６のいずれか１項に記載のクエリ推薦方法。
【請求項８】
クリックグラフ特徴量抽出ステップにおいて、クエリ投入回数に対するＵＲＬのクリック回数に基づき各ＵＲＬのクリック確率を算出し、
該クリック確率に基づき一方のクエリからＵＲＬを経由して他方のクエリに到達する前記到達確率を算出する
ことを特徴とする請求項５〜７のいずれか１項に記載のクエリ推薦方法。
【請求項９】
請求項１〜４のいずれか１項に記載のクエリ推薦装置としてコンピュータを機能させるクエリ推薦プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索エンジンの検索ログに基づきユーザに推薦クエリを提供する技術に関する。
【背景技術】
【０００２】
近年、インターネット上の情報は急激に増加し、ユーザが必要な情報を検索する検索エンジンの重要性が高まっている。この検索エンジンには、ユーザの検索状況を示すログファイルが蓄積されているため、該ログファイルを分析し、検索サービスの向上に利用する試みが行われている。
【０００３】
【表１】
0005508232.tif 000002
【０００４】
表１は、一般的なログファイルを示している。ここでは「日付」、「ユーザＩＤ」、「クエリ名」、「クリックＵＲＬ」、「ランキング順位」の項目に関する情報が記録されている。具体的には、「日付」の項目にはユーザが検索結果のＵＲＬをクリックした日付が記録され、「ユーザＩＤ」の項目には検索クエリを用いて検索したユーザの所有するＩＤが記録され、「クエリ名」の項目にはユーザが検索に利用したクエリ名が記録され、「クリックＵＲＬ」の項目にはユーザが検索結果中でクリックしたＵＲＬが記録され、「ランキング順位」の項目にはクリックＵＲＬの検索ランキングの順位が記録される。
【０００５】
検索エンジンでは、このようなログファイルをユーザの検索行動の効率化、例えば推薦クエリの提示に利用している。この推薦クエリは、図１に示すように、ユーザが検索エンジンに投入したクエリと、検索結果をクリックしたＵＲＬとをペアにした二部グラフを用いて定められている。図１中、左側のｑ1〜ｑ3はユーザ投入のクエリ名を示し、右側のｕ1〜ｕ5は検索結果からユーザがクリックしたＵＲＬを示し、該両者がエッジで連結されている。このような二部グラフを解析し、結び付きの強いクエリを推薦クエリとして用いている。
【０００６】
ところが、二部グラフに基づく推薦クエリの提示は、利用頻度の高いクエリはログファイル中の検索ログが多く有効であるものの、利用頻度の少ないクエリでは検索ログが少ないため、関連するクエリも少なく、推薦できるクエリが希少となる問題が生じる。
【０００７】
そこで、利用頻度の少ないクエリに対するクエリ推薦技術が非特許文献１に提案されている。ここではユーザ投入のクエリと実際にクリックしたＵＲＬとを結び付けたクリックグラフ（二部グラフ）と、ユーザ投入のクエリと実際にはクリックしていないＵＲＬとを結び付けたスキップグラフを用いてクエリを推薦している。図２は、図１のクリックグラフから得られるスキップグラフ例を示し、該スキップグラフによればクリックグラフでは繋がりのないクエリ同士が繋がりをもつようになり（例えばｑ1．ｑ2．ｑ3がｕ2を介して繋がりを持つ）、ユーザに推薦するクエリ数を増やすことができる。
【０００８】
ここではクリックグラフから得られる特徴量は、クリックされたＵＲＬで繋がるクエリ同士の明示的な関連度として扱っている。また、スキップグラフから得られる特徴量は、ユーザのクリックしていないＵＲＬを介して繋がるクエリ同士の暗黙的な関連度として扱っている。このようなクリックグラフから得られるクエリ間の特徴量と、スキップグラフから得られるクエリ間の特徴量との総和を用いて、ユーザに推薦するクエリを抽出している。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Yang Song,Li-wei He,"Optimal Rare Query Suggestion With Implicit User Feedback",ACM WWW 2010,April 26-30,2010
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、非特許文献１の手法では、対象としているクエリの検索結果に対して、クリックしていないＵＲＬにスキップグラフのエッジを作成して重みを与えていくことから、該当するＵＲＬをクリックしないユーザ数が多くなると大きな重みが与えられてしまう。これではユーザの未クリックＵＲＬをクエリに関連しないＵＲＬと想定した場合に無関係のクエリが多く推薦され、ユーザの検索効率が悪化するおそれがある。
【００１１】
また、ログファイルを用いてスキップグラフを作成するにあたって、ログファイル中にはクエリとクリック関係の無いＵＲＬが多数存在するため、関連するクエリと判断されるクエリ同士が多くなり、この点でも無関係なクエリが数多く推薦されるおそれがある。
【００１２】
本発明は、上述のような従来技術の問題点を解決するためになされたものであり、高精度の推薦クエリをユーザに提供し、ユーザの検索効率の向上に貢献することを解決課題としている。
【課題を解決するための手段】
【００１３】
そこで、本発明は、検索ログ中、クリックされたＵＲＬで結び付けられる各クエリの検索ログを順次抽出し、抽出された検索ログ中のＵＲＬ、即ちクエリ間に介在するＵＲＬの重要度を算出する。このＵＲＬの重要度に基づきスキップグラフにおけるクエリ間の特徴量を算出することで、検索結果におけるクリック状況（例えばクリックされなかったＵＲＬが多い等）の影響を軽減してクエリ間の関連度を算出し、より高精度の推薦クエリを抽出する。このときクエリ間の距離も用いてスキップグラフにおけるクエリ間の特徴量を算出することもできる。これにより関連度の低いクエリの特徴量を小さくすることが可能となる。
【００１４】
具体的には、本発明に係るクエリ推薦装置の一態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出手段と、前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、特徴量合成手段の合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。
【００１５】
本発明に係るクエリ推薦装置の他の態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出手段と、前記抽出手段の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成手段と、グラフ作成手段の作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出手段と、グラフ作成手段の作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出手段の設定した位置情報に基づくクエリ間の距離と、前記抽出手段の算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出手段と、前記各特徴量抽出手段の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成手段と、を備え、特徴量合成手段の合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。
【００１６】
本発明に係るクエリ推薦方法の一態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出し、抽出された検索ログ内のＵＲＬの重要度を各クエリのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで算出したＵＲＬの重要度をもって算出するスキップグラフ特徴量抽出ステップと、前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、を有し、特徴量合成ステップで合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。
【００１７】
本発明に係るクエリ推薦方法の他の態様は、検索クエリ記憶手段からクリックされたＵＲＬで結び付けられる各クエリの検索ログを抽出する際に、該ＵＲＬで順次結び付けられるクエリの位置情報をクエリ間のＵＲＬ数に応じて設定し、該ＵＲＬの重要度を各クエリからのクリック確率に基づき算出するクエリ関連ログ抽出ステップと、前記抽出ステップで抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結させたクリックグラフと、各クエリと未クリックのＵＲＬとをエッジで連結させたスキップグラフとを作成するグラフ作成ステップと、グラフ作成ステップで作成したクリックグラフにおけるクエリ間の特徴量をＵＲＬ経由の到達確率に応じて算出するクリックグラフ特徴量抽出ステップと、グラフ作成ステップで作成したスキップグラフにおけるクエリ間の特徴量を、前記抽出ステップで設定した位置情報に基づくクエリ間の距離と、前記抽出ステップで算出した前記ＵＲＬの重要度とを用いて算出するスキップグラフ特徴量抽出ステップと、前記各特徴量抽出ステップで算出した特徴量を合成して最終的なクエリ間の特徴量を算出する特徴量合成ステップと、有し、特徴量合成ステップで合成したクエリ間の特徴量に応じてユーザに推薦クエリを提示することを特徴とする。
【００１８】
なお、本発明は、前記装置としてコンピュータを機能させるプログラムの態様としてもよい。このプログラムは、ネットワークや記録媒体などを通じて提供することができる。
【発明の効果】
【００１９】
本発明によれば、高精度の推薦クエリをユーザに提供でき、ユーザの検索効率の向上に貢献することができる。
【図面の簡単な説明】
【００２０】
【図１】クリックグラフ（二部グラフ）例。
【図２】スキップグラフ例。
【図３】本発明の実施形態に係るクエリ推薦装置の構成例。
【図４】同  クエリ推薦方法のフローチャート。
【図５】図４中のＳ０１のクエリ位置算出を示すフローチャート。
【図６】同  ＵＲＬの重要度算出を示すフローチャート。
【図７】同  クリックグラフからクエリ間の特徴量算出例を示す説明図。
【発明を実施するための形態】
【００２１】
≪装置構成例≫
図３に基づき本発明の実施形態に係るクエリ推薦装置の構成例を説明する。この推薦装置１は、検索エンジンの検索ログに基づきクリックグラフとスキップグラフとを作成し、該両グラフから得られるクエリ間の関連度、即ちクエリ間の特徴量を用いてユーザに推薦クエリを提示する。
【００２２】
具体的には、前記推薦装置１は、検索サービスを提供する検索エンジンと連携し、通常のコンピュータのハードウェアリソース、例えばＣＰＵ，メモリ（ＲＡＭ），ハードディスクドライブ装置，通信デバイスなどを備える。このハードウェアリソースとソフトウェアリソース（ＯＳ．アプリケーションなど）との協働の結果、前記推薦装置１は、検索クエリ記憶部２，クエリ関連ログ抽出部３，クリックグラフ作成部４，クリックグラフ特徴量抽出部５，スキップグラフ作成部６，スキップグラフ特徴量抽出部７，特徴量合成部８を実装する。
【００２３】
この記憶部２には、検索エンジンに投入された検索クエリ群と検索結果などの検索ログ（ログファイル）が格納されている。ここでは検索エンジンの検索ログに連動してメモリ（ＲＡＭ）あるいはハードディスクドライブ装置などの記憶装置に該検索ログをデータ格納する。表２は、前記記憶部２の格納データ例を示し、表１と同様に「日付」、「ユーザＩＤ」、「クエリ名」、「クリックＵＲＬ」、「ランキング順位」の項目に関する情報が記録されている。
【００２４】
【表２】
0005508232.tif 000003
【００２５】
前記抽出部３は、前記記憶部２を参照してクリックされたＵＲＬで繋がる各クエリ、即ち該ＵＲＬで結び付けられる各クエリの検索ログを順次抽出する。このときクリックされたＵＲＬを介して順次結び付けられるクエリの位置情報を、クエリ間に介在するＵＲＬ数に応じて設定する。また、抽出された検索ログ内のＵＲＬ、即ち前記クエリ間に介在するＵＲＬの重要度を算出する。ここではクエリの利用頻度（クエリ投入回数に対するＵＲＬのクリック回数）に基づきＵＲＬのクリック確率を算出し、該クリック確率に基づきＵＲＬのエントロピーを算出する。このエントロピーを、各ＵＲＬのエントロピーの最大値で正規化する。正規化されたエントロピーをＵＲＬの重要度に利用する。
【００２６】
前記グラフ作成部４は、前記抽出部３の抽出した検索ログに基づき各クエリとクリックされたＵＲＬとをエッジで連結したクリックグラフを作成し、前記特徴量抽出部５は、前記グラフ作成部４で作成したクリックグラフにおけるクエリ間の特徴量、即ちクエリ間の明示的な関連度を一方のクエリからＵＲＬを経由して他方のＵＲＬに到達する確率に基づき算出する。その際にクエリの投入回数に対するＵＲＬのクリック回数の割合を利用する。
【００２７】
前記グラフ作成部６は、前記抽出部３の抽出した検索ログに基づき各クエリとクリックされていないＵＲＬとをエッジで連結したスキップグラフを作成し、前記特徴量抽出部７は、スキップグラフにおけるクエリ間の特徴量、即ちクエリ間の暗黙的な関連度を、前記抽出手段の算出したＵＲＬの重要度と各クエリの位置情報に基づく距離を用いて算出する。
【００２８】
前記合成部８は、前記各特徴量抽出手段５．７の算出した特徴量を合成して最終的なクエリ間の特徴量を算出する。ここで合成されたクエリ間の特徴量に応じてユーザに提示する推薦クエリが抽出される。抽出された推薦クエリは、インターネット経由でユーザ所有の端末（ＰＣ，携帯電話など）に表示される。
【００２９】
≪処理ステップ≫
以下、図４に基づき前記推薦装置１の処理ステップを説明する。ここではクエリｑ１を処理対象のクエリとする事例を説明する。このクエリｑ１が図示省略の入力部に入力されて処理が開始される。
【００３０】
Ｓ０１：前記抽出部３は、図示省略の入力部にクエリｑ１が入力されると、前記記憶部２にアクセスし、クエリｑ1から順にクリックされたＵＲＬで結び付けられる各クエリの検索ログ（クリックログ）のサブセットを抽出する。このとき前記抽出部３は、該検索ログ内における各クエリの位置情報を設定し、各ＵＲＬの重要度を算出する。なお、前記サブセット・各クエリの位置情報・各ＵＲＬの重要度は、前記グラフ作成部４．６に出力される。
【００３１】
図５に基づき各クエリの位置情報の設定例を説明する。ここではクエリｑ1から順にＵＲＬのクリック関係を有するクエリ（いわゆる関連クエリ）の位置情報を設定する。この関連クエリの位置情報をクエリｑ1からの最小距離、即ちクエリｑ1からの最小経由ＵＲＬ数に応じて設定する。まず、処理の開始にあたってＳ１２．Ｓ１３の処理回数の最大値「Ｎ＿ｍａｘ」が設定される。この処理例では「Ｎ＿ｍａｘ＝２」とし、初期値「Ｎ＝０」で処理を開始する（Ｓ１１）。なお、「Ｎ＿ｍａｘ」の値は適宜調整することができるものとする。
【００３２】
つぎに「Ｎ＝Ｎ＋１＝１」とし、Ｎの値「１」をｑ1の検索ログ内における位置情報に設定し（Ｓ１２）、クエリｑ１を対象とする第１回目の検索ログ抽出を行う。すなわち、ｑ1をクエリに持つ検索ログからＵＲＬを抽出し、併せて該ＵＲＬに結び付くクエリ、即ち該ＵＲＬとクリック関係を有するクエリを含む検索ログを抽出する（Ｓ１３）。
【００３３】
この抽出後に「Ｎ＝Ｎ＿ｍａｘ」が成立するか否かを確認する（Ｓ１４）。確認の結果、成立すればＳ１５に進む一方、成立しなければＳ１２に戻る。この段階では「Ｎ＝１」であるため、「Ｎ＝Ｎ＿ｍａｘ」は成立しない。したがって、Ｓ１２に戻って「Ｎ＝Ｎ＋１＝２」とし、前記抽出された検索ログに含まれるｑ1以外のクエリ（関連クエリ１）について、検索ログ内の位置情報をＮの値「２」に設定する（Ｓ１２）。ここで設定されたｑ1以外のクエリを対象とする第２回目の検索ログ抽出を行う。
【００３４】
すなわち、位置情報「２」に設定されたクエリを含む検索ログを抽出し、併せて該検索ログに含まれるＵＲＬに結び付くクエリを抽出する（Ｓ１３）。この段階では「Ｎ＝２」なため、Ｓ１４が成立し、Ｓ１５に進む。Ｓ１５では、「Ｎ＝Ｎ＋１＝３」とし、最後にＳ１３で抽出されたクエリ（関連クエリ２）について検索ログ内の位置情報をＮの値「３」に設定（関連クエリ１を除く）して処理を終了する。これによりクエリｑ1から順次ＵＲＬ経由で結び付く各クエリの位置情報を最小経由のＵＲＬ数に応じて設定することができる。なお、この設定例では位置情報は「Ｎ＋１」（ＵＲＬ数＋１）で設定されている。
【００３５】
図６に基づきＵＲＬの重要度の算出方法を説明する。まず、処理の開始により前記サブセット中の各ＵＲＬとクリック関係を有するクエリとを抽出する（Ｓ２１）。ここでは一例として式（１）のＵＲＬを対象とし、該式（１）のＵＲＬとクリック関係を有するクエリｑi（ｉ＝１，２，・・・，ｎ）を抽出する。
【００３６】
【数１】
0005508232.tif 000004
【００３７】
つぎにＳ２１で抽出したクエリｑiの利用頻度から式（１）のＵＲＬのクリック確率を算出する（Ｓ２２）。すなわち、クエリｑiの前記サブセット内における投入回数を基に式（２）を用いて、式（１）のＵＲＬに対するクリック確率（Ｐik）を算出する。
【００３８】
【数２】
0005508232.tif 000005
【００３９】
ここでは式（１）のＵＲＬとクリック関係を有するすべてのクエリｑi（ｉ＝１，２，・・・，ｎ）に対して、式（２）を用いてクリック確率（Ｐik）を算出する。そして、Ｓ２２で算出したクリック確率（Ｐik）を基に式（１）のＵＲＬのエントロピーＥkを、式（３）を用いて算出する（Ｓ２３）。
【００４０】
【数３】
0005508232.tif 000006
【００４１】
最後にＳ２１〜Ｓ２３の処理を前記サブセットに含まれるすべてのＵＲＬに対して実行し、各ＵＲＬのエントロピーＥkの最大値を用いて式（４）で正規化する（Ｓ２４）。正規化されたエントロピーＥkを各ＵＲＬの重要度とする。
【００４２】
【数４】
0005508232.tif 000007
【００４３】
Ｓ０２：前記グラフ作成部４は、前記抽出部３からの出力情報のうちＳ０１で抽出された前記サブセットを基にクリックグラフを作成する。このクリックグラフの作成方法を説明する。ここで前記サブセットが表２の検索ログであれば、ｑ1のクエリからはｕ１．ｕ４のＵＲＬがクリックされているため、図１のクリックグラフに示すように、ｑ1からｕ1．ｕ4へそれぞれエッジを連結させる。同様に表２の検索ログに基づきｑ2．ｑ3に対しても同様にクリックグラフを作成する。すなわち、ｑ2からｕ3．ｕ5にエッジを連結し、ｑ3からｕ1．ｕ5へエッジを連結させる。このようにクリックグラフを作成し、作成されたクリックグラフを前記抽出部３からの出力情報（クリック確率Ｐikを含む。）と併せて前記特徴量抽出部５に出力する。
【００４４】
Ｓ０３：前記特徴量抽出部５は、Ｓ０２で作成されたクリックグラフにおけるエッジの重み、即ちクエリ間の特徴量（関連度）を算出する。このクリックグラフからの特徴量は式（５）〜（７）を用いて算出する。
【００４５】
【数５】
0005508232.tif 000008
【００４６】
【数６】
0005508232.tif 000009
【００４７】
【数７】
0005508232.tif 000010
【００４８】
式（５）〜（７）を用いてクリックグラフにおけるすべてのクエリ間の特徴量を計算する。ここで「ｃｌｉｃｋ＿ｖａｌｕｅij」は、クエリｑiとクエリｑjの関連性を表す特徴量を示している。また、「ｋ」は式（１）のＵＲＬを示し、「Ｐik×Ｐkj」はクエリｑiを出発して式（１）のＵＲＬを経由し、式（１）のＵＲＬからクエリｑjへ到達する確率を示している。図７にクリックグラフにおけるクエリｑ1とクエリｑ2の関連性を表す特徴量「ｃｌｉｃｋ＿ｖａｌｕｅ12」を対象とした具体的な計算方法を示しておく。なお、算出したクエリ間の特徴量は前記合成部８に出力される。
【００４９】
Ｓ０４：前記グラフ作成部６は、前記抽出部３からの出力情報のうちＳ０１で抽出された前記サブセットを基にスキップグラフを作成する。このスキップグラフの作成方法を説明する。ここではＳ０２と同様に前記サブセットが表２の検索ログとする。このときｑ1に着目するとｕ1．ｕ4はクリックされているが、ｕ2．ｕ3．ｕ5はクリックされていない。そこで、ｑ1からクリックされていないｕ2．ｕ3．ｕ5に対して、図２に示すように、エッジを連結させる。
【００５０】
また、ｑ2．ｑ3に対しても、ｑ2からクリックされていないｕ1．ｕ2．ｕ4にエッジを連結し、ｑ3からクリックされていないｕ2．ｕ3．ｕ4にエッジを連結させる。このようにスキップグラフを作成し、作成したスキップグラフを前記抽出部３からの出力情報と併せて前記特徴量抽出部７に出力する。
【００５１】
Ｓ０５：前記特徴量抽出部７は、Ｓ０４で作成されたスキップグラフにおけるエッジの重み、即ちクエリ間の特徴量（クエリ間の関連度）を算出する。このとき前記グラフ作成部６からの出力情報中、各クエリの位置情報に基づくクエリ間の距離（ｑiの位置−ｑjの位置）を算出する。
【００５２】
このクエリ間の距離と前記出力情報中のＵＲＬの重要度Ｅkとを用いて、スキップグラフにおけるクエリ間の特徴量を算出する。この算出には式（８）を用いるものとし、算出されたクエリ間の特徴量は前記合成部８に出力される。
【００５３】
【数８】
0005508232.tif 000011
【００５４】
Ｓ０６：前記合成部８は、Ｓ０３．Ｓ０５で前記各特徴量抽出部５．７から出力されたクリックグラフの特徴量とスキップグラフの特徴量とを合成し、最終的なクエリ間の特徴量を算出する。この算出には式（９）を用いる。
【００５５】
【数９】
0005508232.tif 000012
【００５６】
式（９）中、「α」は「０〜１．０」までの実数を示し、予め任意の値に設定することができる。以下、「α」の値に「０．７」を設定し、クエリとして「恋愛占い」，「心理テスト」，「タロット占い」，「姓名判断」，「誕生日占い」を対象とした事例を説明する。ここではクリックグラフからは表３に示すクエリ間の特徴量が得られ、スキップグラフからは表４に示すクエリ間の特徴量が得られたとする。
【００５７】
【表３】
0005508232.tif 000013
【００５８】
【表４】
0005508232.tif 000014
【００５９】
このとき「恋愛占い」についてクエリ間の特徴量は、
「恋愛占い」⇒「心理テスト」＝０．７×０．０＋０．３×０．４＝０．１２
「恋愛占い」⇒「タロット占い」＝０．７×０．５＋０．３×０．２＝０．４１
「恋愛占い」⇒「姓名判断」  ＝０．７×０．０＋０．３×０．３＝０．０９
「恋愛占い」⇒「誕生日占い」＝０．７×０．１＋０．３×０．０＝０．０７
と算出される。
【００６０】
算出された特徴量が閾値を超えていれば、推薦クエリとして抽出される一方、閾値を超えていなければ、推薦クエリとして抽出されないものとする。この閾値は仕様に応じて適宜に調整できるものとする。例えば閾値を「０．１」に設定すれば、「心理テスト」と「タロット占い」が推薦クエリとして抽出される。抽出される推薦クエリは、インターネット経由でユーザ所有の端末に表示されてユーザに提示される。
【００６１】
このような前記推薦装置１によれば、スキップグラフにおけるクエリ間の特徴量を算出するにあたって、式（８）に示すように、クエリ間を結び付けるＵＲＬの重要度Ｅkを利用するため、検索ログ中のクリック状況（クリックされていないＵＲＬが多いなど）の影響が軽減される。したがって、非特許文献１のように検索ログ中の未クリックＵＲＬが増加するほど前記特徴量が大きくはならず、これによりユーザに高精度の推薦クエリを提示でき、ユーザの検索効率の向上に貢献できる。
【００６２】
このとき非特許文献１では、スキップグラフを作成する際にクエリとクリック関係に無いすべてのＵＲＬにエッジを作成しているため、関連度の低いクエリとＵＲＬにもエッジが作成されるものの、前記推薦装置１の式（８）によれば、ＵＲＬで結び付けられるクエリ間の距離（ｑ1の位置−ｑjの位置）を考慮しているため、かかるクエリ間の関連度を低くすることができ、この点でも精度のよい推薦クエリをユーザに提示できる。
【００６３】
なお、本発明は、上記実施形態に限定されるものではなく、例えばスキップグラフおけるクエリ間の特徴量算出にあたってＵＲＬの重要度Ｅkのみを用いることもできる。この場合にはＳ１２．Ｓ１５の位置情報の設定を行うことなく、式（８）中から「１／ｑ1の位置−ｑjの位置＋１」を削除すればよい。このときＵＲＬで結び付けられるクエリ間の距離は考慮されないものの、検索ログ中のクリック状況（クリックされていないＵＲＬが多いなど）の影響が軽減される効果を得ることができる。
【００６４】
≪プログラムなど≫
本発明は、前記推薦装置１の各部２〜８の一部もしくは全部として、コンピュータを機能させる文書検索プログラムとして構成することもできる。このプログラムによれば、Ｓ０１〜Ｓ０６．Ｓ１１〜Ｓ１５．Ｓ２１〜Ｓ２４の一部あるいは全部をコンピュータに実行させることが可能となる。
【００６５】
前記プログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，ＢＤ−ＲＯＭ，ＢＤ−Ｒ，ＢＤ−ＲＥなどの記録媒体に記録して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。
【符号の説明】
【００６６】
１…クエリ推薦装置
２…検索クエリ記憶部（検索クエリ記憶手段）
３…クエリ関連ログ抽出部（クエリ関連ログ抽出手段）
４…クリックグラフ作成部（グラフ作成手段）
５…クリックグラフ特徴量抽出部（クリックグラフ特徴量抽出手段）
６…スキップグラフ作成部（グラフ作成手段）
７…スキップグラフ特徴量抽出部（スキップグラフ特徴量抽出手段）
８…特徴量合成部（特徴量合成手段）
【図１】
0005508232.tif 000015
【図２】
0005508232.tif 000016
【図３】
0005508232.tif 000017
【図４】
0005508232.tif 000018
【図５】
0005508232.tif 000019
【図６】
0005508232.tif 000020
【図７】
0005508232.tif 000021