"検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第1の場所情報算出ステップと、前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第2の場所情報算出ステップと、場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、を有することを特徴とするクエリの場所推定方法。前記クエリ間遷移確率算出ステップにおいて、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる請求項1記載のクエリの場所推定方法。前記URL間遷移確率算出ステップにおいて、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる請求項1記載のクエリの場所推定方法。前記第1の場所情報算出ステップにおいて、前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、前記第2の場所情報算出ステップにおいて、前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、前記場所判定ステップにおいて、前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする請求項1記載のクエリの場所推定方法。検索サービスにおいて、クエリの場所を推定するクエリの場所推定装置であって、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、前記検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、前記クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置において、前記関連度算出手段は、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数に基づいてクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出手段と、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出手段を有し、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第1の場所情報算出手段と、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第2の場所情報算出手段と、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定手段と、を更に有することを特徴とするクエリの場所推定装置。前記クエリ間遷移確率算出手段は、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる請求項5記載のクエリの場所推定装置。前記URL間遷移確率算出手段は、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる請求項5記載のクエリの場所推定装置。前記第1の場所情報算出手段は、前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分する手段を含み、前記第2の場所情報算出手段は、前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分する手段を含み、前記場所判定手段は、前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出する手段と、前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出する手段と、前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする手段と、を含む請求項5記載のクエリの場所推定装置。コンピュータを、請求項5乃至8のいずれか1項に記載のクエリの場所推定装置の各手段として機能させるクエリの場所推定プログラム。しかしながら、クエリが関係する場所例えば、クエリ渋谷デパートは渋谷に関するクエリを特定することを目的とし、従来手法を用いてクエリに関連度の高い他のクエリが関連する場所を利用する場合、場所とは関係のないクエリの結びつきが問題になることがある。例えば、横浜のデパートでアクセサリを販売しており、渋谷のデパートではアクセサリを販売していない場合に、図3に示すようなクリックグラフが存在するものとする。このとき、クエリデパートアクセサリでは横浜でアクセサリを販売しているため、横浜のデパートに関連するURL2URL3をクリックしている。しかし、従来手法を用いてクエリ間の関連度を算出し、クエリデパートアクセサリとクエリ渋谷デパートの関連度が大きい場合、渋谷ではアクセサリを販売していないためクエリデパートアクセサリが渋谷でも利用できると判断される。他の例として、図4のようにクエリデパートアクセサリがクエリ渋谷デパートとクエリ横浜デパートとの関連度が小さい場合は、クエリデパートアクセサリは利用できる場所が特定できない。しかし、クエリデパートアクセサリでクリックしているURL2、URL3はともに横浜のデパートに関係するURLのため、クエリデパートアクセサリは横浜で利用できるクエリと考えるのが妥当である。このように、クエリ間の関連度を用いてクエリが利用できる場所を特定するには、従来手法のみでは適用できないという問題がある。本発明は、上記の点に鑑みなされたもので、クエリ間の関連度とクエリとクリック関係にあるURL群の場所に対する関連度を用いて、クエリが利用できる場所を推定することが可能なクエリの場所推定方法及び装置及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明請求項1は、検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第1の場所情報算出ステップと、前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第2の場所情報算出ステップと、場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、を有する。また、本発明請求項2は、前記クエリ間遷移確率算出ステップにおいて、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる。また、本発明請求項3は、前記URL間遷移確率算出ステップにおいて、クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる。また、本発明請求項4は、前記第1の場所情報算出ステップにおいて、前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、前記第2の場所情報算出ステップにおいて、前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、前記場所判定ステップにおいて、前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする。従来の技術では、クエリ間の関連度によるクエリの場所的な繋がりを特定する目的において、クエリとURLのクリック関係を2部グラフにして関連度を算出する場合、クリック関係の特徴によって場所的な繋がりがないクエリとの関連度が高い可能性がある。これに対し、本発明によれば、クエリ間の関連度による場所信頼度とクエリとクリック関係にあるURL群の場所信頼度を用いることにより、クエリ間の場所信頼度が小さい場合でもURL群の場所信頼度を用いて場所を推定でき、また、URL群の場所信頼度が小さい場合でも、クエリ間の場所信頼度を用いて場所を推定できる。以下図面と共に、本発明の実施の形態を説明する。図5は、本発明の一実施の形態におけるクエリの場所推定装置の構成を示す。同図に示す装置は、クエリ入力部1、検索ログ抽出部2、クエリ間遷移確率算出部3、URL間遷移確率算出部4、場所情報算出部5、場所判定部6、検索ログ記憶部7、場所キーワード記憶部8、場所URL記憶部9から構成される。上記の検索ログ記憶部7、場所キーワード記憶部8、場所URL記憶部9は、ハードディスク等の記憶媒体に設けられる。検索ログ記憶部7は、図6に示すように、日付、ユーザID、クエリ名、クリックURLからなる検索ログを格納する。以下に、上記の構成の装置の処理を検索ログ抽出処理とクエリ場所推定処理に分けて説明する。<検索ログ抽出処理>クエリ入力部1にクエリq1が入力されると、検索ログ抽出部2にq1を出力する。検索ログ抽出部2は、クエリq1を取得すると、検索ログ記憶部7にアクセスし、クエリq1に関連するログを抽出する。検索ログを抽出する方法について、図7のフローチャートを用いて説明する。図7は、本発明の一実施の形態における検索ログ抽出処理のフローチャートである。ステップ101検索ログ抽出部2は、はじめに、Nmaxの値を設定する。本実施の形態では、Nmax=2とし、N=0とする。ステップ102検索ログ抽出部2は、N=N1とし、クエリ入力部1から取得したクエリq1を持つクリックURLを検索ログ記憶部7から検索する。ここでは、図6の1行目と3行目を検索してURL1,URL2を抽出する。ステップ103検索ログ抽出部2は、検索ログ記憶部7からURL1,URL2をクリックURLにもつクエリを抽出する。具体的には、図6の検索ログからURL1をクリックURLにもつクエリとしてq2を抽出し、URL2をクリックURLにもつクエリとしてq3を抽出する。ステップ104NがNmax以下である場合は、N=N1としてステップ102に移行し、ステップ103で抽出したクエリq2、q3のクリックURLを抽出する。NがNmaxと同値となったら当該処理を終了する。本例ではN=2となった時点で検索ログを出力する。検索ログ抽出部2は、上記の処理で抽出した検索ログをクエリq1に関連する検索ログとし、クエリ間遷移確率算出部3とURL間遷移確率算出部4に出力する。<クエリ場所推定処理>クエリ間遷移確率算出部3とURL間遷移確率算出部4は、検索ログ抽出部2から検索ログを取得すると、クエリとURLの二部グラフを作成し、それぞれクエリ間の遷移確率とURL間の遷移確率を算出する。以下にクエリ間の遷移確率、URL間の遷移確率を用いてクエリの場所を判定する方法を説明する。図8は、本発明の一実施の形態におけるクエリの場所推定処理のフローチャートである。ステップ201クエリ間遷移確率算出部3は、検索ログ記憶部7から検索ログを読み出し、検索ログの各クエリに対し、クエリとクリック関係にあるURLii=1,2,...,nを抽出する。ステップ202クエリ間遷移確率算出部3は、クエリとURLによる二部グラフを作成する。二部グラフとは、検索ログにおけるクエリとクリック関係にあるURLをエッジで結んだものであり、クエリ同士、URL同士ではエッジを結ばないグラフである。ここでは、検索ログが図6のように与えられると、図9のような二部グラフを作成する。ステップ203クエリ間遷移確率算出部3は、ステップ201で抽出したクエリの検索ログ内のクリック回数を基に、以下の式1でクエリURLkへのクリック確率を算出する。上記式における分子のqiからURLkへのクリック回数とは、検索ログにおいて全ユーザがqiをクエリとして得た検索結果に対し、URLkをクリックした回数である。また、分母のqiの全クリック回数とは、検索ログにおいて全ユーザがqiを使って検索した検索結果のURLをクリックした回数を示している。図10に算出例を示す。上記の式において、URLkとクリック関係にある全てのクエリqii=1,2,...,nに対して、URLkへのクリック確率を算出する。次に、クエリqiとクエリqjの遷移確率pijを以下の式2を用いて算出する。上記の式において、pik、pkjは図10に示すように、クエリqiからURLk、qjからURLkへのクリック回数により求まる。また、pijを算出する際の総和は、クエリqiとURLk、URLkとクエリqjを結ぶ全てのURLkk=1,2,...,nに対して算出する。このpijをクエリ間の遷移確率とし、この算出例を図11に示す。クエリ間遷移確率算出部3は、当該pijを場所情報算出部5に出力する。ステップ204URL間遷移確率算出部4において、ステップ201で抽出したクエリの検索ログ内のクリック回数を基に下記の式3でクエリqkへのクリック確率を算出する。上記式における分子のURLiからqkへのクリック回数とは、検索ログにおいて全ユーザがqkをクエリとして得た検索結果に対しURLiをクリックした回数である。また、分母のURLiの全クリック回数とは、検索ログにおいて全ユーザがqkを使って検索した検索結果のURLiをクリックした回数を示している。図12に算出例を示す。上記の式において、qkとクリック関係にある全てのURLii=1,2,...,nに対して、qkへのクリック確率を算出する。次に、URLiとURLjの遷移確率pijを下記の式を用いて算出する。上記の式において、pik,pkjは図12に示すようにURLiからqk、URLjからqkへのクリック回数により求まる。また、pijを算出する際の総和は、URLiとqk、qkとURLjを結ぶ全てのqkk=1,2、...nに対して算出する。このpijをURL間の遷移確率とし、URL間の遷移確率の算出例を図13に示す。また、算出されたURL間の遷移確率を場所情報算出部5へ出力する。ステップ205場所情報算出部5は、ステップ203、ステップ204で算出されたクエリ間、URL間の遷移確率をクエリ間遷移確率算出部3、URL間遷移確率算出部4から取得し、それらに含まれている各クエリ、各URLに場所情報を付与する。まず、はじめに、場所情報算出部5は、各クエリの表記渋谷デパートなどに該当する場所情報を場所キーワード記憶部8内から取り出す。ここで、場所キーワード記憶部8には図14に示すように、地名としての渋谷のキーワードに対して場所情報の渋谷区や、施設名日本スカイツリーのキーワードに対して台東区の場所情報が入っている。例えば、図11のクエリ渋谷デパートには、クエリ内の渋谷に該当する渋谷区の場所情報を得る。ここで、クエリの表記において、場所キーワード記憶部8に該当するキーワードが存在しない場合、場所情報を付与できない場合もある。次に、場所情報算出部5は、各URLに該当する場所情報を場所URL記憶部9から取り出す。ここで、場所URL記憶部9には、図15に示すようなURLに対する場所情報が格納されており、本実施の形態では、図15に示すようなURLに対する情報が格納されているものとして説明する。ここで、場所URL記憶部9内に存在しないURLには場所情報が付与できない。ステップ206場所情報算出部5は、各クエリに対し、場所ベクトルを算出する。この場所ベクトルの次元は場所キーワード記憶部8、場所URL記憶部9に含まれる全ての場所情報渋谷区などで構成される。例えば、クエリ渋谷デパートは渋谷区の場所情報が付加されているため、図16のようなベクトルとなる。このクエリqiの場所ベクトルを下記の方法で算出する。1クエリqiに場所情報が付加されている時:場所情報に該当するベクトルの要素を10とし、それ以外の要素を0とする。2クエリqiに場所情報が付加されていない時:ステップ203で算出したクエリ間の遷移確率を基に、下記の式でクエリqiのベクトルを算出する。上記の式において、pijはqiとqjの遷移確率であり、qvectorはクエリqjの場所ベクトルである。ステップ207場所情報算出部5は、各URLに対し場所ベクトルを算出する。この場所ベクトルの次元は、場所キーワード記憶部8、場所URL記憶部9に含まれる全ての場所情報渋谷区などで構成される。例えば、図16のURL1は場所情報として台東区が該当するため、図17のようなベクトルとなる。URLiの場所ベクトルは下記の方法で算出する。1URLiに場所情報が付加されている時:場所情報に該当するベクトルの要素を10とし、それ以外の要素を0とする。2URLiに場所情報が付加されていない時:ステップ204で算出したURL間の遷移確率を基に、下記の式でURLiのベクトルを算出する。上記の式において、pijは、URLiとURLjの遷移確率であり、URLvectorはURLjの場所ベクトルである。ステップ208場所判定部6は、クエリの場所を特定するため、クエリの場所ベクトルから算出する信頼度と、クエリとクリック関係にあるURLの場所ベクトルから算出される信頼度を算出する。クエリqiの場所ベクトルから算出する信頼度qtrustは下記の式で算出する。ここで、lkはクエリの場所ベクトルqvectorの要素を示している。上記の式7はクエリqiの場所ベクトルの各要素の場所に対する推定確率としたときのエントロピーである。そのため、qtrustの値が大きい場合は、場所を特定できる確率が高いことを示す。クエリとクリック関係にあるURLの場所ベクトルから算出する信頼度URLtrustは下記の式で算出する。ここで、lkはクエリとクリック関係にあるURLの場所ベクトルを足し合わせたベクトルΣURLvectorの要素を示している。上記の式8は、クエリとクリック関係にあるURLiの場所ベクトルの総和において、各要素を場所に対する推定確率としたときのエントロピーである。そのため、URLtrustの値が大きい場合は、場所を特定できる確率が高いことを示す。この2つの信頼度を基に、クエリqiの場所推定値を下記の式9で算出する。クエリの場所推定値=qtrust×URLtrust上記の式のクエリqiの場所推定値が設定した閾値以上であればクエリqiの場所を特定できたものと判断する。このとき、qtrustとURLtrustの値の大きさを比較し、下記の方法でクエリqiの場所を付与する。1qtrustの値が大きい場合:qvectorの要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。2URLtrustの値が大きい場合:ΣURLvectorの要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。なお、本発明を実施する上で、クエリとURLに場所情報が付与してある必要があるが、一部のクエリ、URLに場所情報が付与されている場合でも、クエリ、URLの場所を推定できる。なお、上記の図5に示すクエリの場所推定装置の各構成要素の各機能をプログラムとして構築し、場所推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更応用が可能である。"