(57)【特許請求の範囲】
【請求項１】
ユーザから入力されたクエリに基づいてクリックログからユーザが意図した検索結果を得られる可能性が高いクエリを提示するための推薦クエリ抽出装置であって、
ユーザから入力されたクエリを取得するクエリ入力手段と、
過去に入力されたクエリと該クエリによってアクセスされたURLの組からなるクリックログが格納されたクリックログ記憶手段と、
前記入力されたクエリに基づいて前記クリックログ記憶手段を検索することにより得られたURLと該クエリから２部グラフを生成する２部グラフ構築手段と
前記２部グラフに含まれるクエリについてそれぞれのスコアを計算するスコア算出手段と、
前記スコアの上位から順に所定の数のクエリを選択し、出力する推薦クエリ出力手段と、
を有し、
前記２部グラフ構築手段は、
前記入力されたクエリが前記クリックログ記憶手段に存在しない場合は、検索エンジンを介して、該クエリに対応するURLを取得し、前記２部グラフに追加するURL検索手段を含む
ことを特徴とする推薦クエリ抽出装置。
【請求項２】
前記URL検索手段は、
前記検索エンジンを介して取得したURLを記憶手段に格納し、１番目のURLを起点として、所定の２部グラフに含まれるべきクエリの下限値ｎ−１個のクエリ及び該ｎ−１個のクエリからアクセスされたURLを前記２部グラフに追加する手段を含む
請求項１記載の推薦クエリ抽出装置。
【請求項３】
前記２部グラフ構築手段は、
前記２部グラフに含まれるクエリの数を所定の推薦するクエリの数ｋで除した前記２部グラフの評価値を求め、該評価値が所定の評価値の下限値よりも大きい２部グラフを出力する手段を含む
請求項１記載の推薦クエリ抽出装置。
【請求項４】
ユーザから入力されたクエリに基づいてクリックログからユーザが意図した検索結果を得られる可能性が高いクエリを提示するための推薦クエリ抽出方法であって、
ユーザから入力されたクエリを取得するクエリ入力手段と、
過去に入力されたクエリと該クエリによってアクセスされたURLの組からなるクリックログが格納されたクリックログ記憶手段と、
前記入力されたクエリに基づいて前記クリックログ記憶手段を検索することにより得られたURLと該クエリから２部グラフを生成する２部グラフ構築手段と、
前記２部グラフに含まれるクエリについてそれぞれのスコアを計算するスコア算出手段と、
前記スコアの上位から順に所定の数のクエリを選択し、出力する推薦クエリ出力手段と、
を有する装置において、
前記２部グラフ構築手段が、前記入力されたクエリが前記クリックログ記憶手段に存在しない場合は、検索エンジンを介して、該クエリに対応するURLを取得し、前記２部グラフに追加するURL検索ステップを行う
ことを特徴とする推薦クエリ抽出方法。
【請求項５】
前記URL検索ステップにおいて、
前記検索エンジンを介して取得したURLを記憶手段に格納し、１番目のURLを起点として、所定の２部グラフに含まれるべきクエリの下限値ｎ−１個のクエリ及び該n−１個のクエリからアクセスされたURLを前記２部グラフに追加する
請求項４記載の推薦クエリ抽出方法。
【請求項６】
前記２部グラフ構築手段が、前記２部グラフに含まれるクエリの数を所定の推薦するクエリの数ｋで除した前記２部グラフの評価値を求め、該評価値が所定の評価値の下限値よりも大きい２部グラフを出力するステップを更に行う
請求項４記載の推薦クエリ抽出方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の推薦クエリ抽出装置の各手段として機能させるための推薦クエリ抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推薦クエリ抽出装置及び方法及びプログラムに係り、特に、ユーザが意図した検索結果を得られる可能性が高いクエリを提示するための推薦クエリ抽出装置及び方法及びプログラムに関する。
【０００２】
ユーザが入力するクエリは、ユーザの意図した検索結果を得るために適切であるとは限らないが、推薦されたクエリを選択することで、ユーザは容易に入力するクエリを変更し、検索を再試行することができる。例えば、［コーヒー豆の種類］に関する文書を検索するために『豆の種類』というクエリを入力したユーザに対して、『コーヒー豆 種類』や『豆 ブランド』というクエリを推薦する動作が可能である。
【背景技術】
【０００３】
以下に、クエリを推薦するための従来技術を説明するが、最初に、本明細書における用語について説明する。
【０００４】
『クエリ』とは、文書を検索するためにユーザがシステムに入力する文字列をいう。検索する文書はクエリに含まれるキーワードを含む文書であり、クエリが複数のキーワードを含む場合はそれらのキーワードを同時に含む文書を指す。例えば、コーヒー豆の種類に関する文書を検索するために『コーヒー豆 種類』というクエリを入力すると、『コーヒー豆』と『種類』の両方のキーワードを含む文書を検索することができる。
【０００５】
『クリックログ』とは、ハードディスク等の記憶手段に保持されている、過去の複数のユーザがシステムに入力したクエリと、そのクエリに対してシステムが出力した検索結果の中からユーザが選択したURLを指す。例えば、あるユーザＡがクエリaを入力してURL１を選択し、別のユーザＢがクエリｂを入力してURL２を選択した場合、クリックログには、
｛クエリａ，URL１｝
｛クエリｂ，URL２｝
が保持される。
【０００６】
『スコア』とは、あるクエリをユーザに推薦したときにユーザがそのクエリを選択する可能性を表す指標を指す。例えば、『豆の種類』という入力クエリに対して『豆知識』というクエリが0.9のスコアをもち、「コーヒー豆の種類」というクエリが1.5のスコアをもつとき、スコアを考慮することで後者を優先して推薦することができる。
【０００７】
クエリを推薦するための従来の第1の技術として、過去の複数のユーザがシステムに入力したクエリと当該クエリに対してシステムが出力した検索結果の中からユーザが選択したURLからなるクリックログに、入力クエリが含まれる場合に２部グラフを構築し、推薦候補となるクエリを生成する技術がある（例えば、非特許文献1参照）。ここで、２部グラフとは、グラフ理論において、頂点集合を二つの部分集合に分割して各集合内の頂点同士の間には辺がないようにできるグラフのことである。当該技術のクエリ抽出装置の構成を図１に示す。同図に示す装置は、ユーザから入力されたクエリを取得するクエリ入力部１、入力されたクエリを用いて２部グラフを構築する２部グラフ構築部２、クリックログが格納されたクリックログ記憶部５、装置内の各構成要素で用いられるパラメータを保持するパラメータ記憶部４、２部グラフに含まれるそれぞれのクエリについてスコアを計算するスコア計算部７、スコアに基づいてパラメータ記憶部４のパラメータで指定されている個数分のクエリを抽出する推薦クエリ出力部８から構成される。
【０００８】
上記のパラメータ記憶部４は、図２に示すように、パラメータとして、以下の内容を保持する。
【０００９】
ｎ：２部グラフに含まれるべきクエリの数の下限；
ｍ：スコア計算における反復回数；
ｋ：推薦するクエリの数；
上記の２部グラフ構築部２の動作を図３に示す。
【００１０】
まず、２部グラフ構築部２は、クエリ入力部１からクエリｑを受け取り、ｑのみを含む２部グラフＧを作成する（ステップ１）。次に、クリックログ記憶部５にｑが存在するかを判定し（ステップ２）、存在する場合は（ステップ３、Yes）、ｑを起点として、クエリとURLのアクセス関係に基づいて、ｎ−１個のクエリと当該クエリからアクセスされたURLを２部グラフＧに追加する（ステップ４）。
【００１１】
また、従来の第２の技術として、クリックログに入力クエリが含まれていなくとも、検索エンジンによって検索されたURLを用いることにより、候補を推薦する技術がある（例えば、非特許文献2参照）。
【００１２】
また、従来の第３の技術として、各クエリに対する検索結果の類似性を用いてクエリ同士の類似性を推定し、入力クエリに類似しているクエリをユーザに推薦する技術がある（例えば、非特許文献３参照）。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Qiaozhu Mei, Dengyong Zhou, Kenneth Church: Query suggestion using hitting time, In Proceedings of CIKM '08, pages 469 - 478, ACM, 2008.
【非特許文献２】US 2005/0055341 A1: System and method for providing search query refinements, Paul Haahr et al.
【非特許文献３】特開2001-202390号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、上記従来の第１の技術は、クリックログに含まれるクエリに対して、検索エンジンの性能に依存しない置き換え型のクエリ推薦が可能であるが、推薦する候補を生成するためにはクリックログが必要であり、クリックログに入力クエリが含まれないと推薦候補を生成できないため、十分な容量のクリックログが必要になるという問題がある。
【００１５】
また、上記従来の第２の技術は、クリックログに含まれないクエリに対するクエリ推薦が可能であるが、検索エンジンによって検索されたURLを必要とするため、検索エンジンの性能がクエリ推薦の結果に大きく影響し、選択される可能性の高い候補を推薦できない場合がある。
【００１６】
また、上記従来の第３の技術は、クエリに対する検索結果の類似性に基づくクエリ推薦が可能であるが、人間が判断した結果（本発明におけるクリックログに相当する）を用いないため、検索結果がクエリ推薦の結果に大きく影響し、選択される可能性の高い候補を推薦できない場合がある。
【００１７】
本発明は、上記の点に鑑みなされたもので、クリックログの記憶容量が小さくても置き換え型クエリ推薦を可能とし、また、選択される可能性の高い候補を優先させて表示することが可能な推薦クエリ抽出装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するため、本発明（請求項１）は、ユーザから入力されたクエリに基づいてクリックログからユーザが意図した検索結果を得られる可能性が高いクエリを提示するための推薦クエリ抽出装置であって、
ユーザから入力されたクエリを取得するクエリ入力手段と、
過去に入力されたクエリと該クエリによってアクセスされたURLの組からなるクリックログが格納されたクリックログ記憶手段と、
前記入力されたクエリに基づいて前記クリックログ記憶手段を検索することにより得られたURLと該クエリから２部グラフを生成する２部グラフ構築手段と、
前記２部グラフに含まれるクエリについてそれぞれのスコアを計算するスコア算出手段と、
前記スコアの上位から順に所定の数のクエリを選択し、出力する推薦クエリ出力手段と、
を有し、
前記２部グラフ構築手段は、
前記入力されたクエリが前記クリックログ記憶手段に存在しない場合は、検索エンジンを介して、該クエリに対応するURLを取得し、前記２部グラフに追加するURL検索手段を含むことを特徴とする。
【００１９】
また、本発明（請求項２）は、前記URL検索手段において、
前記検索エンジンを介して取得したURLを記憶手段に格納し、１番目のURLを起点として、所定の２部グラフに含まれるべきクエリの下限値ｎ−１個のクエリ、及び該ｎ−１個のクエリからアクセスされたURLを前記２部グラフに追加する手段を含む。
【００２０】
また、本発明（請求項３）は、前記２部グラフ構築手段において、
前記２部グラフに含まれるクエリの数を所定の推薦するクエリの数ｋで除した前記２部グラフの評価値を求め、該評価値が所定の評価値の下限値よりも大きい２部グラフを出力する手段を含む。
【発明の効果】
【００２１】
本発明によれば、クリックログに含まれない入力クエリに対して、当該クエリの一部または全部を置き換えたクエリを推薦する置き換え型のクエリ推薦が可能となるため、クリックログの記憶容量が小さくても置き換え型クエリ推薦が可能となる。
【００２２】
また、入力クエリがクリックログに含まれるときには、検索エンジンの性能に依存せず、人間が判断した結果のみを用いて推薦するクエリのスコアを算出することが可能であるため、選択される可能性の高い候補を先に表示することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】第1の従来技術のクエリ抽出装置の構成図である。
【図２】第1の従来技術のパラメータ記憶部のパラメータを示す図である。
【図３】第1の従来技術の２部グラフ構築部のフローチャートである。
【図４】本発明の一実施の形態におけるクエリ抽出装置の構成図である。
【図５】本発明の一実施の形態におけるパラメータ記憶部の例である。
【図６】本発明の一実施の形態におけるクリックログ記憶部の格納例である。
【図７】本発明の一実施の形態における２部グラフ構築部のフローチャートである。
【発明を実施するための形態】
【００２４】
以下、図面と共に本発明の実施の形態を説明する。
【００２５】
図４は、本発明の一実施の形態におけるクエリ抽出装置の構成を示す。
【００２６】
同図に示すクエリ抽出装置は、クエリ入力部１、２部グラフ構築部２０、検索エンジン３０、パラメータ記憶部４０、クリックログ記憶部５、インデックス記憶部６０、スコア計算部７、推薦クエリ出力部８から構成される。
【００２７】
クエリ入力部１、クリックログ記憶部５、スコア計算部７、推薦クエリ出力部８は、従来の第１の技術と同様である。
【００２８】
クエリ入力部１は、ユーザが入力したクエリを受け取る。
【００２９】
２部グラフ構築部２０は、入力されたクエリを受け取り、当該クエリに基づいてクリックログ記憶部５を検索することにより得られたURLと該クエリから２部グラフを生成し、クリックログ記憶部５に入力されたクエリが存在しない場合には、検索エンジン３０を用いてURLを取得して２部グラフを構築する。処理の詳細について後述する。
【００３０】
パラメータ記憶部４０は、図５に示すように、２部グラフに含まれるべきクエリの数の下限ｎ、２部グラフの評価値の下限ｕ、スコアの計算における反復回数m、推薦するクエリの数ｋを格納する。これらのパラメータは、実装する際の計算機資源や利用目的に応じて事前に決定し、クエリ入力部１にクエリが入力される前にパラメータ記憶部４０に格納しておく。
【００３１】
インデックス記憶部６０は、文書の検索においてクエリと文書の照合を効率的に行うために、検索対象となる多くの文書の見出し情報を保持し、検索エンジン３０により参照される。見出し情報の作成と更新は、クエリ推薦とは無関係に行われるものであり、予め構築されているものとする。当該見出し情報の作成及び更新の処理については、例えば、文献１"B. Brin, L. Page: The anatomy of a large-scale hypertextual Web search engine, 1998"に記載の方法により実現することが可能である。なお、見出し情報の作成・更新については、本発明の範囲外であるため詳細な説明は省略する。
【００３２】
クリックログ記憶部５は、過去の複数のユーザが文書を検索するために入力したクエリと、そのクエリに対して得られた検索結果の中からユーザが選択したURLを保持する。例えば、過去のあるユーザAがクエリａを入力してURL1を選択し、次にユーザＢがクエリｂを入力してURL2を選択した場合、クリックログ記憶部５には図６のように、クエリａとURL1，クエリｂとURL2のペアが保持される。
【００３３】
検索エンジン３０は、インデックス記憶部６０を用いて、クエリｑに含まれるキーワードを含む文書を検索し、それらの文書のURLのリストを検索結果として出力する。例えば、上記の文献１のFigure4.に示される方法により実現可能である。
【００３４】
スコア計算部７は、２部グラフｇに含まれるクエリq以外のクエリについて、それぞれのスコアを計算する。本発明では、２部グラフ構築部２０から出力される２部グラフは、所定の値以上の評価値を有するものである。具体的には、文献２"Qiaozhu Mei, Dengyong Zhou, Kenneth Church: Query suggestion using hitting time, In Proceedings of CIKM '08, pages 469-478, ACM, 2008."の技術を用いることにより実現できる。
【００３５】
推薦クエリ出力部８は、スコア計算部７で求められたスコアをもとにしてｋ個（２部グラフに含まれるべきクエリの数の下限値）のクエリを選び出し、推薦クエリとして出力する。具体的には、スコアが付与されたクエリの集合Ｑをスコアの順に並び替え、ユーザが選択する可能性の高い順にｋ個のクエリを選び出し、推薦クエリとして出力する。具体的には文献２の技術を用いることにより実現可能である。
【００３６】
次に、上記の２部グラフ構築部２０の処理について詳述する。
【００３７】
図７は、本発明の一実施の形態における２部グラフ構築部のフローチャートである。
【００３８】
ステップ１００）  ２部グラフ構築部２０は、クエリ入力部１からクエリｑを取得し、ｑのみを含む２部グラフＧを作成する。
【００３９】
ステップ１１０）  クエリｑに基づいてクリックログ記憶部５を参照し、当該クエリｑが存在するかを判定する。
【００４０】
ステップ１２０）  クエリｑが存在する場合はステップ１３０に移行し、存在しない場合はステップ１４０に移行する。
【００４１】
ステップ１３０）  クエリｑを起点として、クエリとURLのアクセス関係を元に、n−1個のクエリとそれらからアクセスされたURLをメモリ（図示せず）上の２部グラフＧに追加し、当該処理を終了する。
【００４２】
ステップ１４０）  クエリｑがクリックログ記憶部５に格納されていない場合は、検索エンジン３０を介して、クエリｑに対応するURLを受け取り、URLのカウンタをｉ＝１とする。なお、取得したURLはメモリ（図示せず）に格納しておくものとする。
【００４３】
ステップ１５０）  ｉ番目のURLを起点として、クエリとURLのアクセス関係に基づいて、検索エンジン３０による検索結果のi番目のURLをアクセス関係の起点として、ｎ−１個のクエリと当該クエリからアクセスされたURLをクリックログ記憶部５から取り出し、２部グラフＧに追加する。なお、ｎはパラメータ記憶部４０に格納されている２部グラフに含まれるべきクエリの数の下限である。
【００４４】
ステップ１６０）  ２部グラフＧの評価値を算出する。評価値は、
評価値＝｜Q|／k
ただし、｜Q|は２部グラフGに含まれるクエリの数であり、ｋはパラメータ記憶部４０に格納されているパラメータで指定された推薦するクエリの数である。
【００４５】
ステップ１７０）  ステップ１６０で求められた評価値がパラメータ記憶部４０に格納されているグラフＧの評価値の下限ｕ以上であるかを判定し、ｕ以上である場合は当該処理を終了し、ｕより小さい値である場合はステップ１８０に移行する。
【００４６】
ステップ１８０）  カウンタをｉ＝ｉ＋１としてステップ１５０に戻る。
【００４７】
本発明では、入力クエリがクリックログ記憶部５に存在しなくとも、上記のステップ１１０〜１３０において、入力クエリに関連するURLのリストを、検索エンジン３０を介して取得することで２部グラフを構築することができる。クリックログは、入力クエリに対する検索結果から人間がURLを選択することで生成されるので、ステップ１４０で取得するURLは入力クエリに対するクリックログの候補と考えることができ、したがって、クリックログの代替とすることができる。これにより、クエリ抽出装置が探索できるクリックログの容量が小さく（例えば、期間が直前の１ヶ月間のみ）、入力クエリがクリックログに存在しない可能性が高い場合でも２部グラフを構築できる。２部グラフを構築できれば、スコア計算部７の処理を従来技術と同様に行うことでクエリ推薦が可能となる。
【００４８】
一方、クリックログ記憶部５にクエリが存在する場合には、当該クリックログのみに基づいてグラフを構築するため、人間の判断を反映することができ、選択される可能性が高いクエリを推薦することができる。
【００４９】
さらに、評価値を算出し、所定の値以上の２部グラフをスコア計算部７に出力することにより、選択される可能性の高い候補を優先させて出力することが可能となる。
【００５０】
上記の、図４に示すクエリ入力部１、２部グラフ構築部２０、スコア計算部７、推薦クエリ出力部８の動作をプログラムとして構築し、クエリ抽出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５１】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５２】
１  クエリ入力部
２，２０  ２部グラフ構築部
４，４０  パラメータ記憶部
５  クリックログ記憶部
７  スコア計算部
８  推薦クエリ出力部
３０  検索エンジン
６０  インデックス記憶部
【図１】
0005589009.tif 000002
【図２】
0005589009.tif 000003
【図３】
0005589009.tif 000004
【図４】
0005589009.tif 000005
【図５】
0005589009.tif 000006
【図６】
0005589009.tif 000007
【図７】
0005589009.tif 000008