重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラム
【課題】入力されたクエリに関連して、重要度の高いクエリを判定して出力できる重要クエリ抽出装置を提供する。
【解決手段】重要クエリ抽出装置１０は、クエリを取得するクエリ取得部１１と、クエリログを記憶するクエリログ記憶部１７と、取得クエリを第１ノードに設定する第１ノード設定部１２１と、前記クエリログから第１ノードのクエリに含まれる単語を含むクエリを抽出して第２ノードに設定する第２ノード設定部１２２と、各ノード間に有向エッジを追加し、そのスコアを設定するスコア設定部１３と、スコアに基づいて重要ノードを特定し、そのクエリを重要クエリとして出力するクエリ出力部１４とを備える。スコア設定部１３は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する。
【解決手段】重要クエリ抽出装置１０は、クエリを取得するクエリ取得部１１と、クエリログを記憶するクエリログ記憶部１７と、取得クエリを第１ノードに設定する第１ノード設定部１２１と、前記クエリログから第１ノードのクエリに含まれる単語を含むクエリを抽出して第２ノードに設定する第２ノード設定部１２２と、各ノード間に有向エッジを追加し、そのスコアを設定するスコア設定部１３と、スコアに基づいて重要ノードを特定し、そのクエリを重要クエリとして出力するクエリ出力部１４とを備える。スコア設定部１３は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のクエリのなかで重要なクエリを抽出する重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムに関する。
【背景技術】
【０００２】
インターネット上の情報を検索するシステムとして、キーワード検索機能を備えたサーチエンジンが用いられている。
この際、検索を行うユーザが、適切なキーワードを入力できない可能性もある。このため、キーワードを入力したユーザに対して、より適切なクエリを提示する方法が提案されている（例えば、特許文献１参照）。
【０００３】
特許文献１では、クエリの発生頻度と、前記クエリに関するユーザ満足度スコアとに基づいてクエリランクを計算し、このクエリランクが高順位のクエリを抽出する。そして、入力されたクエリに対して類似度の高いクエリであり、かつ、前記クエリランクが高順位のクエリを修正クエリとして提供する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−５３５０９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記特許文献１では、スペルミスを含むクエリであっても、そのクエリの入力頻度が高い場合には、高ランクと判定されてしまうため、必ずしもユーザの望むクエリが高ランクと判定されていないという問題があった。
【０００６】
本発明の目的は、入力されたクエリに関連して、重要度の高いクエリを判定して出力できる重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明の重要クエリ抽出装置は、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得部と、前記クエリ取得部で取得されたクエリを、クエリログとして順次記憶するクエリログ記憶部と、前記クエリ取得部で取得したクエリを第１ノードに設定する第１ノード設定部と、前記クエリログ記憶部に記憶されているクエリログから、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定部と、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定部と、前記スコア設定部で設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力部とを備え、前記スコア設定部は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【０００８】
本発明によれば、クエリログ記憶部は、端末装置からインターネットなどのネットワークを介して送信されるキーワード検索用のクエリを、順次記憶してクエリログとして記憶する。たとえば、ウェブページをキーワードで検索する検索サーバに対して、各端末装置からクエリが入力されると、このクエリは検索サーバから本発明の重要クエリ抽出装置に転送され、前記クエリログ記憶部に記憶される。従って、本発明の重要クエリ抽出装置は、ウェブページ等の各種検索サーバに組み込まれていてもよいし、検索サーバとデータ通信可能に構成されていてもよい。
そして、端末装置からクエリが入力されると、第１ノード設定部は、その入力クエリを第１ノードに設定する。第２ノード設定部は、第1ノードのクエリに含まれる単語を含むクエリを前記クエリログ記憶部から抽出して第２ノードに設定する。
たとえば、入力クエリとして、歌手名である「Ａ」という固有名詞と、「曲」という歌手の属性に関連する言葉の二つの単語が入力された場合、第１ノード設定部は、「Ａ 曲」という二つの単語を含むクエリを第１ノードに設定する。また、第２ノード設定部は、「Ａ」という単語を含むクエリと、「曲」という単語を含むクエリを抽出し、第２ノードに設定する。たとえば、第２ノードとして設定されるクエリには、「Ａ」、「Ａ、画像」、「Ａ、歌詞」など、過去に固有名詞「Ａ」を含んで入力された各種クエリと、「歌詞、曲」など、過去に「曲」を含んで入力された各種クエリが抽出され、これらにより複数の第２ノードが設定される。
【０００９】
スコア設定部は、各ノード間に有向エッジを追加し、有向エッジのスコアを設定する。この際、第２ノードが複数ある場合には、有向エッジは、第１ノードと各第２ノード間だけでなく、第２ノード間にも設定される。この際、スコア設定部は、２つのノード間の有向エッジのスコアを、有向エッジの方向によって設定する。すなわち、第１ノードおよび第２ノード間の有向エッジは、第２ノードから第１ノードに向かう第１の有向エッジと、逆方向の第２の有向エッジとの２つが設定され、各有向エッジはそれぞれスコアが設定される。
２つのノード間の各有向エッジのスコアは、２つのノードに共通する単語の希少性が高い場合に高くなる。希少性を表す数値とは、たとえば、クエリログ記憶部に記憶されたクエリログにおいて、その単語が含まれるクエリの数であり、このクエリの数が少ないほど希少性が高いと判断できる。たとえば、歌手名である「Ａ」という単語は、「曲」といった普通名詞に比べると、クエリ履歴の数も少なくなる。「曲」という単語は、他の歌手名等と共に入力されることも多いからである。なお、この希少性は、たとえば、単語のデータベースを作成しておき、単語毎に希少性を表す数値を設定しておいてもよい。
【００１０】
また、有向エッジのスコアは、有向エッジが向かう方向のノードにおける単語数も考慮して設定される。たとえば、単語数が多いほどスコアが低くなり、少ないほどスコアが高くなるように設定する。すなわち、第１ノードとして、「Ａ（歌手名）、曲」の２つの単語が入力されている場合に、第２ノードとして歌手名「Ａ」のみのノードと、「Ａ、Ｂ、Ｃ」の３名の歌手名が設定されたノードとを想定した場合、歌手名Ａと曲をクエリとして入力したユーザにとって、他の歌手名Ｂ，Ｃは検索キーワードとしては不要であり、ノイズとなってしまう。このため、歌手名「Ａ」のみのクエリのほうが重要となる。前記「Ｂ，Ｃ」はいずれも固有名詞であるため、単語の希少性のみでスコアを設定しようとすると、前記２つのクエリでスコアの差が出にくい。一方、単語数もスコアの算出に加えれば、単語数が少ないほどスコアが高くなり、前記歌手名「Ａ」のみのクエリのスコアを高くできる。
【００１１】
以上のように、希少性の高い単語を入力している場合、ユーザはその単語に関係する情報を最も要求していると推定できる。また、希少性の高い単語を含んでいても、クエリ内の単語数が多い場合には、その他の単語がノイズとなって適切な検索結果が得られない可能性がある。従って、その単語を含むクエリで単語数が少ないものが最も重要度の高いクエリと判定でき、本発明によればクエリログ記憶部に記憶されたクエリログから重要クエリを的確に抽出できる。このようにして抽出した重要クエリは、クエリ出力部によって、ユーザの端末装置等に出力される。このため、端末装置を操作するユーザは、スペルミスや誤表記を含まない、例えば固有表現の正しい表記などの重要クエリを得ることができる。
【００１２】
また、端末装置を操作するユーザは、クエリ候補として重要クエリを選択できる。従って、入力したクエリの検索結果として適切なものが無かった場合などに、本発明の重要クエリ抽出装置から出力された重要クエリを選択して再度検索することで、適切な検索結果を得ることができる。
【００１３】
本発明の重要クエリ抽出装置において、前記スコア設定部は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成されるノードが存在する場合は、そのノードに向かう有向エッジのスコアを最も高く設定し、前記クエリ出力部は、前記有向エッジのスコアが最も高いノードのクエリを重要クエリとして出力することが好ましい。
スコア設定部は、単語数が少ないクエリほどエッジのスコアを高くし、希少性の高い単語ほどエッジのスコアを高くする。このため、入力されたクエリに含まれる単語のなかで、最も希少性の高い単語が１つのみ含まれたクエリのノードに向かうエッジのスコアが最も高い値となる。従って、クエリ出力部は、スコアの高いノードのクエリを重要クエリとして出力する。
このため、歌手名Ａのように固有名詞のみのクエリがクエリログ記憶部の履歴に存在すれば、そのクエリが重要クエリとして出力され、ユーザがその重要クエリを用いて検索すれば、その固有名詞に関する検索結果を得ることができる。
【００１４】
本発明の重要クエリ抽出装置において、前記スコア設定部は、ノードｉからノードｊに向かうエッジのスコアをH_{i,j}、ノードｊに設定されたクエリを構成する単語数をN_q_j、前記クエリログ記憶部において単語ｗを含むクエリ数を示す数値をDF(w)、ノードｉおよびノードｊに含まれる単語に関するDF(w)の逆数を加算した値をΣ_{w∈q_i∩q_j}1/DF(w)とした場合に、前記エッジのスコアを以下の式（１）で求めることが好ましい。
［数１］
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w)) ……（１）
【００１５】
この式（１）を用いれば、ノードｊの単語数が分母となっているので、単語数が多いほどスコアが小さくなる。また、各ノードに共通する単語に関し、その単語を含むクエリの数を示すDF(w)の逆数を、共通する単語分だけ加算している。従って、クエリ数が少ない単語、つまり希少性の高い単語ほど、スコアが大きくなる。
従って、前記スコアは、単語数が少なく、各ノードに共通する単語の希少性が高い場合に値が大きくなり、このスコアが大きくなればクエリの重要度も高くなると判定できる。
【００１６】
本発明の重要クエリ抽出方法は、コンピュータにより、重要クエリを抽出する重要クエリ抽出方法であって、前記コンピュータは、クエリの履歴が記憶されたクエリログ記憶部を備え、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、前記クエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行し、前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【００１７】
本発明の重要クエリ抽出プログラムは、コンピュータに、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、クエリの履歴が記憶されたクエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行させる重要クエリ抽出プログラムであって、前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【００１８】
これらの重要クエリ抽出方法および重要クエリ抽出プログラムにおいても、前記重要クエリ抽出装置と同様の作用効果を奏することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態にかかる検索システムの構成を示すブロック図。
【図２】本実施形態の有向グラフを示す図。
【図３】本実施形態の重要クエリ抽出処理を示すフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態を図面に基づいて説明する。
図１には、本発明の重要クエリ抽出装置１０を用いた検索システム１を示す。
検索システム１は、重要クエリ抽出装置１０と、ウェブページの情報を収集・検索する情報検索装置２０と、端末装置３０とを備えている。重要クエリ抽出装置１０および情報検索装置２０と、端末装置３０とは、図示略のインターネットを介して通信可能に構成されている。また、重要クエリ抽出装置１０および端末装置３０によって、検索補助システムが構成されている。
【００２１】
インターネットは、ＴＣＰ／ＩＰなどの汎用のプロトコルに基づくインターネットである。各端末装置３０は、移動しながらインターネットに接続可能であることが好ましい。このため、端末装置３０は、携帯電話網を介してインターネットに接続したり、無線ＬＡＮ（ＬＯＣＡＬ ＡＲＥＡ ＮＥＴＷＯＲＫ）を介してインターネットに接続する。
なお、端末装置３０を重要クエリ抽出装置１０や情報検索装置２０に接続させるための構成は、インターネットに限定されず、無線媒体により情報が送受信可能な複数の基地局がネットワークを構成する通信回線網や放送網などのネットワーク、さらには、データを直接受信するための媒体となる無線媒体自体など、データを送受信させるいずれの構成も利用できる。
【００２２】
重要クエリ抽出装置１０や情報検索装置２０は、ハードウェア構成として、ＲＡＭ（ＲＡＮＤＯＭ ＡＣＣＥＳＳ ＭＥＭＯＲＹ）やＲＯＭ（ＲＥＡＤ ＯＮＬＹ ＭＥＭＯＲＹ）等の図示しない記憶手段と、ＣＰＵ（ＣＥＮＴＲＡＬ ＰＲＯＣＥＳＳＩＮＧ ＵＮＩＴ）等の制御手段と、を備えたサーバ装置で構成されている。ＲＡＭはデータなどを一時的に記憶できる一時領域などを有しており、ＲＯＭはＯＳ（ＯＰＥＲＡＴＩＮＧ ＳＹＳＴＥＭ：基本ソフトウェア）や各種サーバを制御するプログラム、各種アプリケーション、各種データ等が格納されている。ＣＰＵは、これらの記憶手段に格納されているプログラムを読み出し、このプログラムに従って各種処理を行う。特に、重要クエリ抽出装置１０は、記憶手段に記憶された重要クエリ抽出プログラムを読み出して、後述する重要クエリ抽出方法を実行する。
【００２３】
［情報検索装置］
情報検索装置２０は、図１に示すように、クローラ部２１と、ウェブページデータベース（ＷＥＢページＤＢ）２２と、サーチエンジン２３を備えている。
クローラ部２１は、インターネット上のウェブページを巡回し、その内容を収集し、前記ＷＥＢページＤＢ２２に登録する検索ロボットである。
サーチエンジン２３は、全文検索などを行うものであり、端末装置３０から検索用のキーワードが入力されると、前記ＷＥＢページＤＢ２２を用いてキーワードを検索し、その検索結果を端末装置３０に出力する。
このような情報検索装置２０は、従来から知られているものであり、詳細な説明は省略する。
【００２４】
［重要クエリ抽出装置］
重要クエリ抽出装置１０は、図１に示すように、クエリ取得部１１、ノード設定部１２、スコア設定部１３、クエリ出力部１４、クエリログ記憶部１７、クエリ関係記憶部１８を備えている。ノード設定部１２は、第１ノード設定部１２１と、第２ノード設定部１２２とを備える。
【００２５】
クエリ取得部１１は、端末装置３０から情報検索装置２０に入力されるクエリを、情報検索装置２０から入手し、クエリログ記憶部１７に記憶する。このため、クエリログ記憶部１７には、様々な端末装置３０から情報検索装置２０に入力された過去のクエリの履歴が記憶される。
また、クエリ取得部１１は、今回、情報検索装置２０から入力されたクエリをノード設定部１２に出力する。
【００２６】
ノード設定部１２は、クエリ取得部１１で取得した各クエリの関係を示す有向グラフのノードを設定し、クエリ関係記憶部１８に記憶する。
このノード設定部１２における処理を、具体例に基づいて説明する。
まず、ノード設定部１２において設定されてクエリ関係記憶部１８に記憶される有向グラフ（クエリの関係モデル）の一例について、図２に基づいて説明する。
図２に示す有向グラフは、歌手名ABCDEFと曲の２つの単語を含むクエリが入力された場合の例である。
【００２７】
すなわち、ノード設定部１２の第１ノード設定部１２１は、入力されたクエリ「ABCDEF、曲」を第１ノード４１に設定する。
次に、第２ノード設定部１２２は、第１ノード４１に含まれる単語「ABCDEF」と「曲」を含むクエリをクエリログ記憶部１７から抽出し、第２ノードに設定する。図２の例では、第２ノードとして、歌手名「ABCDEF」のみのノード４２、「ABCDEF、画像」の２つの単語からなるノード４３、「ABCDEF、歌詞」の２つの単語からなるノード４４、「歌詞、曲」の２つの単語からなるノード４５、「曲」のみからなるノード４６が設定されている。
なお、歌手名をスペルミスした「ABGDEF」というクエリ４７も履歴に記憶されている。従来のように、類似クエリも抽出している場合は、このクエリ４７も第２ノードに設定されて後述するエッジが設けられるが、本実施形態では類似クエリにはエッジは設定されない。このため、図２ではエッジ部分に「×」印を付けている。
【００２８】
各ノード４１〜４５間には、有向エッジ５１〜７０が設定されている。すなわち、２つのノード間には、一方のノードから他方のノードに向かう有向エッジと、逆方向の有向エッジの２本のエッジが設定される。
ノード設定部１２は、図２に示すような有効グラフを作成し、クエリ関係記憶部１８に記憶する。
【００２９】
スコア設定部１３は、各有向エッジ５１〜７０のスコアを設定する。スコア設定部１３は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性とに基づいて設定する。
具体的には、スコア設定部１３は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成される有向ノードに向かうエッジのスコアを最も高く設定する。
単語の希少性は、クエリの履歴において、前記単語が含まれるクエリの数によって判定される。すなわち、クエリ数が少ないほど、希少性が高いと判定できる。歌手名のような固有名詞と、曲、画像、歌詞のような普通名詞とを比較すると、通常、固有名詞のほうが、その単語を含むクエリの数も少なくなり、希少性も高くなる。このため、図２のグラフでは、希少性の高い単語（歌手名ABCDEF）のみで構成されるノード４２に向かう有向エッジ５１，５７，５９が最も高いスコアになる。
【００３０】
スコア設定部１３における具体的なスコアの算出式の一例は以下の式（２）に示す通りである。
［数２］
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w)) ……（２）
【００３１】
ここで、H_{i,j}は、ノードｉからノードｊに向かう有向エッジのスコアを表す。また、N_q_jは、ノードｊに設定されたクエリq_jを構成する単語数を表す。さらに、DF(w)は単語ｗの希少性を示す数値であり、本実施形態では、クエリログ記憶部１７のクエリ履歴において、その単語ｗを含むクエリの数である。Σ_{w∈q_i∩q_j} 1/DF(w)は、ノードｉに設定されたクエリq_iと、ノードｊに設定されたクエリq_jに共通する単語ｗに関するDF(w)の逆数を、両クエリに共通する単語の分だけ加算した値を示す。
【００３２】
有向エッジ５１，５２における前記スコアの算出例を説明する。
有向エッジ５１は、ノード４１(前記式２のノードｉ)からノード４２(前記式２のノードｊ)に向かうエッジである。そして、ノード４２に設定されたクエリの単語数（N_q_j）は、歌手名ABCDEFのみであるから「１」となる。また、歌手名ABCDEFを含むクエリの数が、クエリログ記憶部１７の履歴の中に1000個あった場合、DF(ABCDEF)＝1000となる。
ノード４１，４２に共通する単語はABCDEFのみであるから、Σ_{w∈q_i∩q_j} 1/DF(w)＝1/1000である。すると、スコアH_{i,j}は、1/1＊1/1000＝0.001である。
【００３３】
一方、有向エッジ５２の場合、ノード４１に設定されたクエリの単語数は「２」である。
ノード４１，４２に共通する単語はABCDEFのみであるから、Σ_{w∈q_i∩q_j} 1/DF(w)＝1/1000である。すると、スコアH_{i,j}は、1/2＊1/1000＝0.0005であり、前記有向エッジ５１に比べて小さくなる。
【００３４】
有向エッジ５７，５９は、共通する単語がABCDEFで同じであり、かつ、エッジが向かう方向のノードの単語数が「１」で共通するため、有向エッジ５１と同じスコアになる。
また、有向エッジ５３〜６２は、共通する単語がABCDEFで同じであり、かつ、エッジが向かう方向のノードの単語数が「２」で共通するため、有向エッジ５２と同じスコアになる。
【００３５】
一方、有向エッジ６３〜７０は、２つのノードに共通する単語が「曲」や「歌詞」である。このような普通名詞は、クエリログに記憶されているクエリ数も多くなる。単語「曲」のクエリ数が１万個であれば、DF(曲)＝10000となる。このため、有向エッジ６７、６９のスコアは、1/1＊1/10000＝0.0001であり、有向エッジ６３，６４，６８，７０のスコアは、1/2＊1/10000＝0.00005である。
単語「歌詞」のクエリ数が8000個であれば、DF(歌詞)＝8000となり、有向エッジ６５，６６のスコアは、1/2＊1/8000＝0.0000625である。
スコア設定部１３は、各有向エッジのスコアを、クエリ関係記憶部１８の有向グラフに記憶する。具体的には、スコアH_{i,j}を行列と見なしてスコアを設定する。
【００３６】
クエリ出力部１４は、スコア設定部１３で設定された有向エッジのスコアのなかで最も高い値の有向エッジを探し、その有向エッジが向かう方向のノードを重要と判定する。前記図２の例では、有向エッジ５１，５７，５９のスコアが最も高い値となる。従って、クエリ出力部１４は、ノード４２が重要と判定する。そこで、クエリ出力部１４は、ノード４２のクエリ「ABCDEF」を重要クエリとして、端末装置３０に出力する。
このため、ユーザは、重要クエリ抽出装置１０から提供された重要クエリを利用した検索を行うことができ、求める情報を得ることができる。
【００３７】
［重要クエリ抽出装置の動作］
次に、重要クエリ抽出装置１０における重要クエリ抽出処理に関し、図３のフローチャートに基づいて説明する。図３に示す処理は、前述したように、重要クエリ抽出プログラムを実行することで実施される。
重要クエリ抽出装置１０のクエリ取得部１１は、端末装置３０から送信されるクエリを取得する（ステップＳ１１）。クエリ取得部１１は、取得したクエリをクエリログ記憶部１７に記憶し、かつ、ノード設定部１２に出力する。
ノード設定部１２の第１ノード設定部１２１は、取得したクエリを第１ノードに設定する（ステップＳ１２）。
【００３８】
次に、第２ノード設定部１２２は、第１ノードの単語を含むクエリを、クエリログ記憶部１７から抽出し、第２ノードを設定する（ステップＳ１３）。また、第２ノード設定部１２２は、各ノード間に有向のエッジを設定して、クエリ間の関係を示すモデルとして有向グラフを作成し、クエリ関係記憶部１８に記憶する（ステップＳ１４）。
【００３９】
次に、スコア設定部１３は、前記各エッジのスコアを算出し、クエリ関係記憶部１８に記憶する（ステップＳ１５）。
クエリ出力部１４は、前記各エッジのスコアで最も高い値を検索し、重要クエリを抽出する（ステップＳ１６）。
さらに、クエリ出力部１４は、抽出した重要クエリを、端末装置３０に出力する（ステップＳ１７）。
以上により、重要クエリの抽出処理が終了する。重要クエリ抽出装置１０は、端末装置３０からクエリが入力されるたびに、前記ステップＳ１１〜Ｓ１７の処理を実行する。
【００４０】
端末装置３０においては、重要クエリ抽出装置１０から出力された重要クエリが表示される。そして、ユーザが表示されたクエリを選択すると、端末装置３０は、サーチエンジン２３にクエリを出力し、その検索結果を取得して表示する。
【００４１】
［実施形態の作用効果］
以上の実施形態によれば、以下の作用効果を奏することができる。
重要クエリ抽出装置１０は、端末装置３０から入力されたクエリに含まれる単語を有するクエリをクエリログ記憶部１７から抽出して各ノードに設定する。そして、各ノード間のエッジのスコアを、各ノード間に共通する単語の希少性を示す値と、エッジが向かう方向のノードの単語数に基づいて設定し、希少性の高い単語であり、かつ、単語数が少ないノードに向かうエッジのスコアが高くなるように設定した。このため、固有名詞と、普通名詞からなるクエリを入力した場合、その固有名詞単独のクエリがクエリログ記憶部１７に記憶されていれば、そのクエリを重要クエリとして抽出し、端末装置３０に出力できる。通常、固有名詞のような希少性の高い、つまりクエリログに記憶されている数が少ない単語を入力している場合、ユーザはその単語に関係する情報を最も要求していると推定できる。従って、その単語を含むクエリで単語数が少ないものが最も重要度の高いクエリと判定できる。
このため、端末装置３０のユーザは、重要クエリ抽出装置１０からスペルミスや誤表記を含まない、例えば固有表現の正しい表記などの重要クエリを得ることができ、この重要クエリを用いて新たな検索を行うことで、求める情報を入手できる可能性が高まる。
【００４２】
また、本実施形態では、単語の希少性を表す数値として、前記クエリログ記憶部１７に記憶されたクエリ数としている。このため、各ノードの設定も、エッジのスコアの算出も、クエリログ記憶部１７に記憶されたクエリログ（履歴）のみに基づいて行うことができる。すなわち、本実施形態では、前記重要クエリを抽出するには、クエリ履歴をクエリログ記憶部１７に記憶しておくだけでよく、たとえば、各ユーザが複数のクエリをどのように入力したか等の行動履歴が保存されたログなどを用意する必要がない。このため、システム的な負荷が小さく、簡易なシステムで重要クエリを抽出できる。
【００４３】
さらに、スペルミスを含む類似クエリの入力頻度が高い場合であっても、本実施形態では、一致する単語を含むクエリのみをノードに設定し、類似する単語にはエッジが設定されない。このため、スペルミスを含む類似クエリが重要クエリと誤って判定されることを防止できる。
【００４４】
［変形例］
なお、本発明は、上述した実施形態に限定されるものではなく、本発明の目的を達成できる範囲で、以下に示される変形をも含むものである。
たとえば、上記実施形態では、情報検索装置２０と、重要クエリ抽出装置１０とを別々のサーバ装置で構成していたが、これらを１つのサーバ装置で構成してもよい。
【００４５】
また、エッジのスコアを算出するための式としては、前記式（２）に記載されたものに限定されない。すなわち、クエリの単語の希少性が高いほどスコアが高くなり、かつ、クエリに含まれる単語数が少ないほどスコアが高くなるような式であればよい。
【産業上の利用可能性】
【００４６】
本発明は、入力されたクエリに関連して、重要度の高いクエリを判定して出力できる重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムとして利用できる。
【符号の説明】
【００４７】
１…検索システム、１０…重要クエリ抽出装置、１１…クエリ取得部、１２…ノード設定部、１２１…第１ノード設定部、１２２…第２ノード設定部、１３…スコア設定部、１４…クエリ出力部、１７…クエリログ記憶部、１８…クエリ関係記憶部、２０…情報検索装置、３０…端末装置。
【技術分野】
【０００１】
本発明は、複数のクエリのなかで重要なクエリを抽出する重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムに関する。
【背景技術】
【０００２】
インターネット上の情報を検索するシステムとして、キーワード検索機能を備えたサーチエンジンが用いられている。
この際、検索を行うユーザが、適切なキーワードを入力できない可能性もある。このため、キーワードを入力したユーザに対して、より適切なクエリを提示する方法が提案されている（例えば、特許文献１参照）。
【０００３】
特許文献１では、クエリの発生頻度と、前記クエリに関するユーザ満足度スコアとに基づいてクエリランクを計算し、このクエリランクが高順位のクエリを抽出する。そして、入力されたクエリに対して類似度の高いクエリであり、かつ、前記クエリランクが高順位のクエリを修正クエリとして提供する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−５３５０９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、前記特許文献１では、スペルミスを含むクエリであっても、そのクエリの入力頻度が高い場合には、高ランクと判定されてしまうため、必ずしもユーザの望むクエリが高ランクと判定されていないという問題があった。
【０００６】
本発明の目的は、入力されたクエリに関連して、重要度の高いクエリを判定して出力できる重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
本発明の重要クエリ抽出装置は、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得部と、前記クエリ取得部で取得されたクエリを、クエリログとして順次記憶するクエリログ記憶部と、前記クエリ取得部で取得したクエリを第１ノードに設定する第１ノード設定部と、前記クエリログ記憶部に記憶されているクエリログから、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定部と、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定部と、前記スコア設定部で設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力部とを備え、前記スコア設定部は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【０００８】
本発明によれば、クエリログ記憶部は、端末装置からインターネットなどのネットワークを介して送信されるキーワード検索用のクエリを、順次記憶してクエリログとして記憶する。たとえば、ウェブページをキーワードで検索する検索サーバに対して、各端末装置からクエリが入力されると、このクエリは検索サーバから本発明の重要クエリ抽出装置に転送され、前記クエリログ記憶部に記憶される。従って、本発明の重要クエリ抽出装置は、ウェブページ等の各種検索サーバに組み込まれていてもよいし、検索サーバとデータ通信可能に構成されていてもよい。
そして、端末装置からクエリが入力されると、第１ノード設定部は、その入力クエリを第１ノードに設定する。第２ノード設定部は、第1ノードのクエリに含まれる単語を含むクエリを前記クエリログ記憶部から抽出して第２ノードに設定する。
たとえば、入力クエリとして、歌手名である「Ａ」という固有名詞と、「曲」という歌手の属性に関連する言葉の二つの単語が入力された場合、第１ノード設定部は、「Ａ 曲」という二つの単語を含むクエリを第１ノードに設定する。また、第２ノード設定部は、「Ａ」という単語を含むクエリと、「曲」という単語を含むクエリを抽出し、第２ノードに設定する。たとえば、第２ノードとして設定されるクエリには、「Ａ」、「Ａ、画像」、「Ａ、歌詞」など、過去に固有名詞「Ａ」を含んで入力された各種クエリと、「歌詞、曲」など、過去に「曲」を含んで入力された各種クエリが抽出され、これらにより複数の第２ノードが設定される。
【０００９】
スコア設定部は、各ノード間に有向エッジを追加し、有向エッジのスコアを設定する。この際、第２ノードが複数ある場合には、有向エッジは、第１ノードと各第２ノード間だけでなく、第２ノード間にも設定される。この際、スコア設定部は、２つのノード間の有向エッジのスコアを、有向エッジの方向によって設定する。すなわち、第１ノードおよび第２ノード間の有向エッジは、第２ノードから第１ノードに向かう第１の有向エッジと、逆方向の第２の有向エッジとの２つが設定され、各有向エッジはそれぞれスコアが設定される。
２つのノード間の各有向エッジのスコアは、２つのノードに共通する単語の希少性が高い場合に高くなる。希少性を表す数値とは、たとえば、クエリログ記憶部に記憶されたクエリログにおいて、その単語が含まれるクエリの数であり、このクエリの数が少ないほど希少性が高いと判断できる。たとえば、歌手名である「Ａ」という単語は、「曲」といった普通名詞に比べると、クエリ履歴の数も少なくなる。「曲」という単語は、他の歌手名等と共に入力されることも多いからである。なお、この希少性は、たとえば、単語のデータベースを作成しておき、単語毎に希少性を表す数値を設定しておいてもよい。
【００１０】
また、有向エッジのスコアは、有向エッジが向かう方向のノードにおける単語数も考慮して設定される。たとえば、単語数が多いほどスコアが低くなり、少ないほどスコアが高くなるように設定する。すなわち、第１ノードとして、「Ａ（歌手名）、曲」の２つの単語が入力されている場合に、第２ノードとして歌手名「Ａ」のみのノードと、「Ａ、Ｂ、Ｃ」の３名の歌手名が設定されたノードとを想定した場合、歌手名Ａと曲をクエリとして入力したユーザにとって、他の歌手名Ｂ，Ｃは検索キーワードとしては不要であり、ノイズとなってしまう。このため、歌手名「Ａ」のみのクエリのほうが重要となる。前記「Ｂ，Ｃ」はいずれも固有名詞であるため、単語の希少性のみでスコアを設定しようとすると、前記２つのクエリでスコアの差が出にくい。一方、単語数もスコアの算出に加えれば、単語数が少ないほどスコアが高くなり、前記歌手名「Ａ」のみのクエリのスコアを高くできる。
【００１１】
以上のように、希少性の高い単語を入力している場合、ユーザはその単語に関係する情報を最も要求していると推定できる。また、希少性の高い単語を含んでいても、クエリ内の単語数が多い場合には、その他の単語がノイズとなって適切な検索結果が得られない可能性がある。従って、その単語を含むクエリで単語数が少ないものが最も重要度の高いクエリと判定でき、本発明によればクエリログ記憶部に記憶されたクエリログから重要クエリを的確に抽出できる。このようにして抽出した重要クエリは、クエリ出力部によって、ユーザの端末装置等に出力される。このため、端末装置を操作するユーザは、スペルミスや誤表記を含まない、例えば固有表現の正しい表記などの重要クエリを得ることができる。
【００１２】
また、端末装置を操作するユーザは、クエリ候補として重要クエリを選択できる。従って、入力したクエリの検索結果として適切なものが無かった場合などに、本発明の重要クエリ抽出装置から出力された重要クエリを選択して再度検索することで、適切な検索結果を得ることができる。
【００１３】
本発明の重要クエリ抽出装置において、前記スコア設定部は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成されるノードが存在する場合は、そのノードに向かう有向エッジのスコアを最も高く設定し、前記クエリ出力部は、前記有向エッジのスコアが最も高いノードのクエリを重要クエリとして出力することが好ましい。
スコア設定部は、単語数が少ないクエリほどエッジのスコアを高くし、希少性の高い単語ほどエッジのスコアを高くする。このため、入力されたクエリに含まれる単語のなかで、最も希少性の高い単語が１つのみ含まれたクエリのノードに向かうエッジのスコアが最も高い値となる。従って、クエリ出力部は、スコアの高いノードのクエリを重要クエリとして出力する。
このため、歌手名Ａのように固有名詞のみのクエリがクエリログ記憶部の履歴に存在すれば、そのクエリが重要クエリとして出力され、ユーザがその重要クエリを用いて検索すれば、その固有名詞に関する検索結果を得ることができる。
【００１４】
本発明の重要クエリ抽出装置において、前記スコア設定部は、ノードｉからノードｊに向かうエッジのスコアをH_{i,j}、ノードｊに設定されたクエリを構成する単語数をN_q_j、前記クエリログ記憶部において単語ｗを含むクエリ数を示す数値をDF(w)、ノードｉおよびノードｊに含まれる単語に関するDF(w)の逆数を加算した値をΣ_{w∈q_i∩q_j}1/DF(w)とした場合に、前記エッジのスコアを以下の式（１）で求めることが好ましい。
［数１］
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w)) ……（１）
【００１５】
この式（１）を用いれば、ノードｊの単語数が分母となっているので、単語数が多いほどスコアが小さくなる。また、各ノードに共通する単語に関し、その単語を含むクエリの数を示すDF(w)の逆数を、共通する単語分だけ加算している。従って、クエリ数が少ない単語、つまり希少性の高い単語ほど、スコアが大きくなる。
従って、前記スコアは、単語数が少なく、各ノードに共通する単語の希少性が高い場合に値が大きくなり、このスコアが大きくなればクエリの重要度も高くなると判定できる。
【００１６】
本発明の重要クエリ抽出方法は、コンピュータにより、重要クエリを抽出する重要クエリ抽出方法であって、前記コンピュータは、クエリの履歴が記憶されたクエリログ記憶部を備え、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、前記クエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行し、前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【００１７】
本発明の重要クエリ抽出プログラムは、コンピュータに、検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、クエリの履歴が記憶されたクエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行させる重要クエリ抽出プログラムであって、前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定することを特徴する。
【００１８】
これらの重要クエリ抽出方法および重要クエリ抽出プログラムにおいても、前記重要クエリ抽出装置と同様の作用効果を奏することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態にかかる検索システムの構成を示すブロック図。
【図２】本実施形態の有向グラフを示す図。
【図３】本実施形態の重要クエリ抽出処理を示すフローチャート。
【発明を実施するための形態】
【００２０】
以下、本発明の実施形態を図面に基づいて説明する。
図１には、本発明の重要クエリ抽出装置１０を用いた検索システム１を示す。
検索システム１は、重要クエリ抽出装置１０と、ウェブページの情報を収集・検索する情報検索装置２０と、端末装置３０とを備えている。重要クエリ抽出装置１０および情報検索装置２０と、端末装置３０とは、図示略のインターネットを介して通信可能に構成されている。また、重要クエリ抽出装置１０および端末装置３０によって、検索補助システムが構成されている。
【００２１】
インターネットは、ＴＣＰ／ＩＰなどの汎用のプロトコルに基づくインターネットである。各端末装置３０は、移動しながらインターネットに接続可能であることが好ましい。このため、端末装置３０は、携帯電話網を介してインターネットに接続したり、無線ＬＡＮ（ＬＯＣＡＬ ＡＲＥＡ ＮＥＴＷＯＲＫ）を介してインターネットに接続する。
なお、端末装置３０を重要クエリ抽出装置１０や情報検索装置２０に接続させるための構成は、インターネットに限定されず、無線媒体により情報が送受信可能な複数の基地局がネットワークを構成する通信回線網や放送網などのネットワーク、さらには、データを直接受信するための媒体となる無線媒体自体など、データを送受信させるいずれの構成も利用できる。
【００２２】
重要クエリ抽出装置１０や情報検索装置２０は、ハードウェア構成として、ＲＡＭ（ＲＡＮＤＯＭ ＡＣＣＥＳＳ ＭＥＭＯＲＹ）やＲＯＭ（ＲＥＡＤ ＯＮＬＹ ＭＥＭＯＲＹ）等の図示しない記憶手段と、ＣＰＵ（ＣＥＮＴＲＡＬ ＰＲＯＣＥＳＳＩＮＧ ＵＮＩＴ）等の制御手段と、を備えたサーバ装置で構成されている。ＲＡＭはデータなどを一時的に記憶できる一時領域などを有しており、ＲＯＭはＯＳ（ＯＰＥＲＡＴＩＮＧ ＳＹＳＴＥＭ：基本ソフトウェア）や各種サーバを制御するプログラム、各種アプリケーション、各種データ等が格納されている。ＣＰＵは、これらの記憶手段に格納されているプログラムを読み出し、このプログラムに従って各種処理を行う。特に、重要クエリ抽出装置１０は、記憶手段に記憶された重要クエリ抽出プログラムを読み出して、後述する重要クエリ抽出方法を実行する。
【００２３】
［情報検索装置］
情報検索装置２０は、図１に示すように、クローラ部２１と、ウェブページデータベース（ＷＥＢページＤＢ）２２と、サーチエンジン２３を備えている。
クローラ部２１は、インターネット上のウェブページを巡回し、その内容を収集し、前記ＷＥＢページＤＢ２２に登録する検索ロボットである。
サーチエンジン２３は、全文検索などを行うものであり、端末装置３０から検索用のキーワードが入力されると、前記ＷＥＢページＤＢ２２を用いてキーワードを検索し、その検索結果を端末装置３０に出力する。
このような情報検索装置２０は、従来から知られているものであり、詳細な説明は省略する。
【００２４】
［重要クエリ抽出装置］
重要クエリ抽出装置１０は、図１に示すように、クエリ取得部１１、ノード設定部１２、スコア設定部１３、クエリ出力部１４、クエリログ記憶部１７、クエリ関係記憶部１８を備えている。ノード設定部１２は、第１ノード設定部１２１と、第２ノード設定部１２２とを備える。
【００２５】
クエリ取得部１１は、端末装置３０から情報検索装置２０に入力されるクエリを、情報検索装置２０から入手し、クエリログ記憶部１７に記憶する。このため、クエリログ記憶部１７には、様々な端末装置３０から情報検索装置２０に入力された過去のクエリの履歴が記憶される。
また、クエリ取得部１１は、今回、情報検索装置２０から入力されたクエリをノード設定部１２に出力する。
【００２６】
ノード設定部１２は、クエリ取得部１１で取得した各クエリの関係を示す有向グラフのノードを設定し、クエリ関係記憶部１８に記憶する。
このノード設定部１２における処理を、具体例に基づいて説明する。
まず、ノード設定部１２において設定されてクエリ関係記憶部１８に記憶される有向グラフ（クエリの関係モデル）の一例について、図２に基づいて説明する。
図２に示す有向グラフは、歌手名ABCDEFと曲の２つの単語を含むクエリが入力された場合の例である。
【００２７】
すなわち、ノード設定部１２の第１ノード設定部１２１は、入力されたクエリ「ABCDEF、曲」を第１ノード４１に設定する。
次に、第２ノード設定部１２２は、第１ノード４１に含まれる単語「ABCDEF」と「曲」を含むクエリをクエリログ記憶部１７から抽出し、第２ノードに設定する。図２の例では、第２ノードとして、歌手名「ABCDEF」のみのノード４２、「ABCDEF、画像」の２つの単語からなるノード４３、「ABCDEF、歌詞」の２つの単語からなるノード４４、「歌詞、曲」の２つの単語からなるノード４５、「曲」のみからなるノード４６が設定されている。
なお、歌手名をスペルミスした「ABGDEF」というクエリ４７も履歴に記憶されている。従来のように、類似クエリも抽出している場合は、このクエリ４７も第２ノードに設定されて後述するエッジが設けられるが、本実施形態では類似クエリにはエッジは設定されない。このため、図２ではエッジ部分に「×」印を付けている。
【００２８】
各ノード４１〜４５間には、有向エッジ５１〜７０が設定されている。すなわち、２つのノード間には、一方のノードから他方のノードに向かう有向エッジと、逆方向の有向エッジの２本のエッジが設定される。
ノード設定部１２は、図２に示すような有効グラフを作成し、クエリ関係記憶部１８に記憶する。
【００２９】
スコア設定部１３は、各有向エッジ５１〜７０のスコアを設定する。スコア設定部１３は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性とに基づいて設定する。
具体的には、スコア設定部１３は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成される有向ノードに向かうエッジのスコアを最も高く設定する。
単語の希少性は、クエリの履歴において、前記単語が含まれるクエリの数によって判定される。すなわち、クエリ数が少ないほど、希少性が高いと判定できる。歌手名のような固有名詞と、曲、画像、歌詞のような普通名詞とを比較すると、通常、固有名詞のほうが、その単語を含むクエリの数も少なくなり、希少性も高くなる。このため、図２のグラフでは、希少性の高い単語（歌手名ABCDEF）のみで構成されるノード４２に向かう有向エッジ５１，５７，５９が最も高いスコアになる。
【００３０】
スコア設定部１３における具体的なスコアの算出式の一例は以下の式（２）に示す通りである。
［数２］
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w)) ……（２）
【００３１】
ここで、H_{i,j}は、ノードｉからノードｊに向かう有向エッジのスコアを表す。また、N_q_jは、ノードｊに設定されたクエリq_jを構成する単語数を表す。さらに、DF(w)は単語ｗの希少性を示す数値であり、本実施形態では、クエリログ記憶部１７のクエリ履歴において、その単語ｗを含むクエリの数である。Σ_{w∈q_i∩q_j} 1/DF(w)は、ノードｉに設定されたクエリq_iと、ノードｊに設定されたクエリq_jに共通する単語ｗに関するDF(w)の逆数を、両クエリに共通する単語の分だけ加算した値を示す。
【００３２】
有向エッジ５１，５２における前記スコアの算出例を説明する。
有向エッジ５１は、ノード４１(前記式２のノードｉ)からノード４２(前記式２のノードｊ)に向かうエッジである。そして、ノード４２に設定されたクエリの単語数（N_q_j）は、歌手名ABCDEFのみであるから「１」となる。また、歌手名ABCDEFを含むクエリの数が、クエリログ記憶部１７の履歴の中に1000個あった場合、DF(ABCDEF)＝1000となる。
ノード４１，４２に共通する単語はABCDEFのみであるから、Σ_{w∈q_i∩q_j} 1/DF(w)＝1/1000である。すると、スコアH_{i,j}は、1/1＊1/1000＝0.001である。
【００３３】
一方、有向エッジ５２の場合、ノード４１に設定されたクエリの単語数は「２」である。
ノード４１，４２に共通する単語はABCDEFのみであるから、Σ_{w∈q_i∩q_j} 1/DF(w)＝1/1000である。すると、スコアH_{i,j}は、1/2＊1/1000＝0.0005であり、前記有向エッジ５１に比べて小さくなる。
【００３４】
有向エッジ５７，５９は、共通する単語がABCDEFで同じであり、かつ、エッジが向かう方向のノードの単語数が「１」で共通するため、有向エッジ５１と同じスコアになる。
また、有向エッジ５３〜６２は、共通する単語がABCDEFで同じであり、かつ、エッジが向かう方向のノードの単語数が「２」で共通するため、有向エッジ５２と同じスコアになる。
【００３５】
一方、有向エッジ６３〜７０は、２つのノードに共通する単語が「曲」や「歌詞」である。このような普通名詞は、クエリログに記憶されているクエリ数も多くなる。単語「曲」のクエリ数が１万個であれば、DF(曲)＝10000となる。このため、有向エッジ６７、６９のスコアは、1/1＊1/10000＝0.0001であり、有向エッジ６３，６４，６８，７０のスコアは、1/2＊1/10000＝0.00005である。
単語「歌詞」のクエリ数が8000個であれば、DF(歌詞)＝8000となり、有向エッジ６５，６６のスコアは、1/2＊1/8000＝0.0000625である。
スコア設定部１３は、各有向エッジのスコアを、クエリ関係記憶部１８の有向グラフに記憶する。具体的には、スコアH_{i,j}を行列と見なしてスコアを設定する。
【００３６】
クエリ出力部１４は、スコア設定部１３で設定された有向エッジのスコアのなかで最も高い値の有向エッジを探し、その有向エッジが向かう方向のノードを重要と判定する。前記図２の例では、有向エッジ５１，５７，５９のスコアが最も高い値となる。従って、クエリ出力部１４は、ノード４２が重要と判定する。そこで、クエリ出力部１４は、ノード４２のクエリ「ABCDEF」を重要クエリとして、端末装置３０に出力する。
このため、ユーザは、重要クエリ抽出装置１０から提供された重要クエリを利用した検索を行うことができ、求める情報を得ることができる。
【００３７】
［重要クエリ抽出装置の動作］
次に、重要クエリ抽出装置１０における重要クエリ抽出処理に関し、図３のフローチャートに基づいて説明する。図３に示す処理は、前述したように、重要クエリ抽出プログラムを実行することで実施される。
重要クエリ抽出装置１０のクエリ取得部１１は、端末装置３０から送信されるクエリを取得する（ステップＳ１１）。クエリ取得部１１は、取得したクエリをクエリログ記憶部１７に記憶し、かつ、ノード設定部１２に出力する。
ノード設定部１２の第１ノード設定部１２１は、取得したクエリを第１ノードに設定する（ステップＳ１２）。
【００３８】
次に、第２ノード設定部１２２は、第１ノードの単語を含むクエリを、クエリログ記憶部１７から抽出し、第２ノードを設定する（ステップＳ１３）。また、第２ノード設定部１２２は、各ノード間に有向のエッジを設定して、クエリ間の関係を示すモデルとして有向グラフを作成し、クエリ関係記憶部１８に記憶する（ステップＳ１４）。
【００３９】
次に、スコア設定部１３は、前記各エッジのスコアを算出し、クエリ関係記憶部１８に記憶する（ステップＳ１５）。
クエリ出力部１４は、前記各エッジのスコアで最も高い値を検索し、重要クエリを抽出する（ステップＳ１６）。
さらに、クエリ出力部１４は、抽出した重要クエリを、端末装置３０に出力する（ステップＳ１７）。
以上により、重要クエリの抽出処理が終了する。重要クエリ抽出装置１０は、端末装置３０からクエリが入力されるたびに、前記ステップＳ１１〜Ｓ１７の処理を実行する。
【００４０】
端末装置３０においては、重要クエリ抽出装置１０から出力された重要クエリが表示される。そして、ユーザが表示されたクエリを選択すると、端末装置３０は、サーチエンジン２３にクエリを出力し、その検索結果を取得して表示する。
【００４１】
［実施形態の作用効果］
以上の実施形態によれば、以下の作用効果を奏することができる。
重要クエリ抽出装置１０は、端末装置３０から入力されたクエリに含まれる単語を有するクエリをクエリログ記憶部１７から抽出して各ノードに設定する。そして、各ノード間のエッジのスコアを、各ノード間に共通する単語の希少性を示す値と、エッジが向かう方向のノードの単語数に基づいて設定し、希少性の高い単語であり、かつ、単語数が少ないノードに向かうエッジのスコアが高くなるように設定した。このため、固有名詞と、普通名詞からなるクエリを入力した場合、その固有名詞単独のクエリがクエリログ記憶部１７に記憶されていれば、そのクエリを重要クエリとして抽出し、端末装置３０に出力できる。通常、固有名詞のような希少性の高い、つまりクエリログに記憶されている数が少ない単語を入力している場合、ユーザはその単語に関係する情報を最も要求していると推定できる。従って、その単語を含むクエリで単語数が少ないものが最も重要度の高いクエリと判定できる。
このため、端末装置３０のユーザは、重要クエリ抽出装置１０からスペルミスや誤表記を含まない、例えば固有表現の正しい表記などの重要クエリを得ることができ、この重要クエリを用いて新たな検索を行うことで、求める情報を入手できる可能性が高まる。
【００４２】
また、本実施形態では、単語の希少性を表す数値として、前記クエリログ記憶部１７に記憶されたクエリ数としている。このため、各ノードの設定も、エッジのスコアの算出も、クエリログ記憶部１７に記憶されたクエリログ（履歴）のみに基づいて行うことができる。すなわち、本実施形態では、前記重要クエリを抽出するには、クエリ履歴をクエリログ記憶部１７に記憶しておくだけでよく、たとえば、各ユーザが複数のクエリをどのように入力したか等の行動履歴が保存されたログなどを用意する必要がない。このため、システム的な負荷が小さく、簡易なシステムで重要クエリを抽出できる。
【００４３】
さらに、スペルミスを含む類似クエリの入力頻度が高い場合であっても、本実施形態では、一致する単語を含むクエリのみをノードに設定し、類似する単語にはエッジが設定されない。このため、スペルミスを含む類似クエリが重要クエリと誤って判定されることを防止できる。
【００４４】
［変形例］
なお、本発明は、上述した実施形態に限定されるものではなく、本発明の目的を達成できる範囲で、以下に示される変形をも含むものである。
たとえば、上記実施形態では、情報検索装置２０と、重要クエリ抽出装置１０とを別々のサーバ装置で構成していたが、これらを１つのサーバ装置で構成してもよい。
【００４５】
また、エッジのスコアを算出するための式としては、前記式（２）に記載されたものに限定されない。すなわち、クエリの単語の希少性が高いほどスコアが高くなり、かつ、クエリに含まれる単語数が少ないほどスコアが高くなるような式であればよい。
【産業上の利用可能性】
【００４６】
本発明は、入力されたクエリに関連して、重要度の高いクエリを判定して出力できる重要クエリ抽出装置、重要クエリ抽出方法および重要クエリ抽出プログラムとして利用できる。
【符号の説明】
【００４７】
１…検索システム、１０…重要クエリ抽出装置、１１…クエリ取得部、１２…ノード設定部、１２１…第１ノード設定部、１２２…第２ノード設定部、１３…スコア設定部、１４…クエリ出力部、１７…クエリログ記憶部、１８…クエリ関係記憶部、２０…情報検索装置、３０…端末装置。
【特許請求の範囲】
【請求項１】
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得部と、
前記クエリ取得部で取得されたクエリを、クエリログとして順次記憶するクエリログ記憶部と、
前記クエリ取得部で取得したクエリを第１ノードに設定する第１ノード設定部と、
前記クエリログ記憶部に記憶されているクエリログから、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定部と、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定部と、
前記スコア設定部で設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力部とを備え、
前記スコア設定部は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出装置。
【請求項２】
請求項１に記載の重要クエリ抽出装置において、
前記スコア設定部は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成されるノードが存在する場合は、そのノードに向かう有向エッジのスコアを最も高く設定し、
前記クエリ出力部は、前記有向エッジのスコアが最も高いノードのクエリを重要クエリとして出力する
ことを特徴とする重要クエリ抽出装置。
【請求項３】
請求項１または請求項２に記載の重要クエリ抽出装置において、
前記スコア設定部は、ノードｉからノードｊに向かうエッジのスコアをH_{i,j}、ノードｊに設定されたクエリを構成する単語数をN_q_j、前記クエリログ記憶部において単語ｗを含むクエリ数を示す数値をDF(w)、ノードｉおよびノードｊに含まれる単語に関するDF(w)の逆数を加算した値をΣ_{w∈q_i∩q_j} 1/DF(w)とした場合に、前記エッジのスコアを、
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w))
で求める
ことを特徴とする重要クエリ抽出装置。
【請求項４】
コンピュータにより、重要クエリを抽出する重要クエリ抽出方法であって、
前記コンピュータは、
クエリの履歴が記憶されたクエリログ記憶部を備え、
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、
前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、
前記クエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、
前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行し、
前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出方法。
【請求項５】
コンピュータに、
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、
前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、
クエリの履歴が記憶されたクエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、
前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行させる重要クエリ抽出プログラムであって、
前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出プログラム。
【請求項１】
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得部と、
前記クエリ取得部で取得されたクエリを、クエリログとして順次記憶するクエリログ記憶部と、
前記クエリ取得部で取得したクエリを第１ノードに設定する第１ノード設定部と、
前記クエリログ記憶部に記憶されているクエリログから、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定部と、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定部と、
前記スコア設定部で設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力部とを備え、
前記スコア設定部は、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出装置。
【請求項２】
請求項１に記載の重要クエリ抽出装置において、
前記スコア設定部は、入力されたクエリに含まれる単語の中で、最も希少性の高い単語のみで構成されるノードが存在する場合は、そのノードに向かう有向エッジのスコアを最も高く設定し、
前記クエリ出力部は、前記有向エッジのスコアが最も高いノードのクエリを重要クエリとして出力する
ことを特徴とする重要クエリ抽出装置。
【請求項３】
請求項１または請求項２に記載の重要クエリ抽出装置において、
前記スコア設定部は、ノードｉからノードｊに向かうエッジのスコアをH_{i,j}、ノードｊに設定されたクエリを構成する単語数をN_q_j、前記クエリログ記憶部において単語ｗを含むクエリ数を示す数値をDF(w)、ノードｉおよびノードｊに含まれる単語に関するDF(w)の逆数を加算した値をΣ_{w∈q_i∩q_j} 1/DF(w)とした場合に、前記エッジのスコアを、
H_{i,j}＝1/N_q_j＊(Σ_{w∈q_i∩q_j} 1/DF(w))
で求める
ことを特徴とする重要クエリ抽出装置。
【請求項４】
コンピュータにより、重要クエリを抽出する重要クエリ抽出方法であって、
前記コンピュータは、
クエリの履歴が記憶されたクエリログ記憶部を備え、
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、
前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、
前記クエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、
前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行し、
前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出方法。
【請求項５】
コンピュータに、
検索キーワードとなる単語が含まれるクエリを取得するクエリ取得ステップと、
前記クエリ取得ステップで取得したクエリを第１ノードに設定する第１ノード設定ステップと、
クエリの履歴が記憶されたクエリログ記憶部に記憶されているクエリの履歴から、前記第１ノードのクエリに含まれる単語を含むクエリを抽出し、抽出されたクエリを第２ノードに設定する第２ノード設定ステップと、
前記各ノード間に有向エッジを追加し、各有向エッジのスコアを設定するスコア設定ステップと、
前記スコア設定ステップで設定されたスコアに基づいて重要ノードを特定し、そのノードに設定されたクエリを重要クエリとして出力するクエリ出力ステップとを実行させる重要クエリ抽出プログラムであって、
前記スコア設定ステップは、一方のノードから他方のノードに向かう有向エッジのスコアを、他方のノードに含まれる単語数と、各ノードに共通する単語の希少性を表す数値とに基づいて設定する
ことを特徴する重要クエリ抽出プログラム。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２０１３−８８９２３（Ｐ２０１３−８８９２３Ａ）
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願番号】特願２０１１−２２７０９０（Ｐ２０１１−２２７０９０）
【出願日】平成２３年１０月１４日（２０１１．１０．１４）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願日】平成２３年１０月１４日（２０１１．１０．１４）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
[ Back to top ]