クエリの場所推定方法及び装置及びプログラム
【課題】 クエリ間の関連度とクエリとクリック関係にあるＵＲＬ群の場所に対する関連度を用いて、クエリが利用できる場所を推定する。
【解決手段】 本発明は、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録し、検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する。二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出し、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出する。クエリ間の遷移確率に基づいてクエリの場所推定値を算出し、URL間の遷移確率に基づいてURLの場所推定値を算出し、クエリの場所推定値とURLの場所推定値を用いてクエリの場所を判定する。
【解決手段】 本発明は、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録し、検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する。二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出し、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出する。クエリ間の遷移確率に基づいてクエリの場所推定値を算出し、URL間の遷移確率に基づいてURLの場所推定値を算出し、クエリの場所推定値とURLの場所推定値を用いてクエリの場所を判定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索サービスにおけるクエリのクリックログを用いたクエリの場所推定方法及び装置及びプログラムに係り、特に、一部のクエリや一部のURLに場所情報が付与されている場合に、場所情報が付与されていないクエリ、URLの場所を推定しながら、クエリの場所推定に関する信頼度を算出し、クエリのクリック分布に基づいたグラフ分析に適用するためのクエリの場所推定方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
近年、検索サービスにおけるユーザの検索状況を示すログファイルを分析し、検索サービスの向上に利用する試みが行われている。ここで、一般に検索ログには図１に示すような項目の情報が含まれている。
【０００３】
１．日付
２．ユーザＩＤ
３．クエリ名
４．クリックURL
５．ランキング順位
図１の日付の項目は、ユーザがURLをクリックした日付である。ユーザＩＤは、検索クエリを用いて検索したユーザのＩＤである。クエリ名は、ユーザが検索に利用したクエリ名である。クリックURLはユーザがクリックした検索結果のURLである。ランキング順位はユーザがクリックしたURLの検索ランキング順位である。
【０００４】
これらのログは、ユーザの検索行動の効率化に利用されている。その利用情報の一つにクエリ推薦がある。このクエリ推薦では、ユーザが投入したクエリとクリックしたURLが対になった図２のような二部グラフを用いて推薦している。図２の左側はユーザが投入したクエリ名であり、右側は検索結果からユーザがクリックしたURLを表している。また、ユーザがクエリを投入して実際にクリックしたURLをエッジで連結している。この二部グラフを解析し、結びつきの強いクエリを推薦クエリとして用いている。
【０００５】
ここで、検索ログを用いたクエリ推薦の代表的な技術として、クエリとURLの関連性を二部グラフを用いてクエリとURＬ間の関連性を算出する技術がある（例えば、非特許文献１参照）。この技術では、クエリとURLの関連性を二部グラフを用いて、クエリとURL間の関連性を算出している。
【０００６】
これらログファイルを用いて、ユーザが欲しいページを見つけやすいクエリを推薦する技術が存在する（例えば、非特許文献１参照）。この技術では、クエリとURLの関連性を二部グラフを用いて、クエリとURL間の関連性を算出する際に、同じ検索意図のクエリが同じURL群にアクセスしている性質を利用し、同じ検索意図のクエリをクラスタリングしている。クラスタリングしたクエリにおいて、関連度の高いクエリを代表クエリとしている。ユーザにクエリを推薦する場合は、ユーザが利用しようとするクエリに対し、そのクエリが属するクラスタリング内のクエリ群から関連度の高いクエリを推薦する。この技術により、ユーザはより検索精度の高いクエリで検索を行うことができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Hangbo Deng. Irwin King, Michael R. Lyu: Entropy-biased Models for Query Representation on the Click Graph, ACM SIGIR, pages 339-346, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、クエリが関係する場所（例えば、クエリ「渋谷 デパート」は渋谷に関するクエリ）を特定することを目的とし、従来手法を用いてクエリに関連度の高い他のクエリが関連する場所を利用する場合、場所とは関係のないクエリの結びつきが問題になることがある。
【０００９】
例えば、横浜のデパートでアクセサリを販売しており、渋谷のデパートではアクセサリを販売していない場合に、図３に示すようなクリックグラフが存在するものとする。このとき、クエリ「デパート アクセサリ」では横浜でアクセサリを販売しているため、横浜のデパートに関連するURL2, URL3をクリックしている。しかし、従来手法を用いてクエリ間の関連度を算出し、クエリ「デパート アクセサリ」とクエリ「渋谷 デパート」の関連度が大きい場合、渋谷ではアクセサリを販売していないためクエリ「デパート アクセサリ」が渋谷でも利用できると判断される。
【００１０】
他の例として、図４のようにクエリ「デパート アクセサリ」がクエリ「渋谷 デパート」とクエリ「横浜 デパート」との関連度が小さい場合は、クエリ「デパート アクセサリ」は利用できる場所が特定できない。しかし、クエリ「デパート アクセサリ」でクリックしているURL2、URL3はともに横浜のデパートに関係するURLのため、クエリ「デパート アクセサリ」は横浜で利用できるクエリと考えるのが妥当である。
【００１１】
このように、クエリ間の関連度を用いてクエリが利用できる場所を特定するには、従来手法のみでは適用できないという問題がある。
【００１２】
本発明は、上記の点に鑑みなされたもので、クエリ間の関連度とクエリとクリック関係にあるＵＲＬ群の場所に対する関連度を用いて、クエリが利用できる場所を推定することが可能なクエリの場所推定方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するため、本発明（請求項１）は、検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、
前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、
前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、
場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出ステップと、
前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出ステップと、
場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、を有する。
【００１４】
また、本発明（請求項２）は、前記クエリ間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる。
【００１５】
また、本発明（請求項３）は、前記URL間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる。
【００１６】
また、本発明（請求項４）は、前記第１の場所情報算出ステップにおいて、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、
前記第２の場所情報算出ステップにおいて、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、
前記場所判定ステップにおいて、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする。
【発明の効果】
【００１７】
従来の技術では、クエリ間の関連度によるクエリの場所的な繋がりを特定する目的において、クエリとURLのクリック関係を２部グラフにして関連度を算出する場合、クリック関係の特徴によって場所的な繋がりがないクエリとの関連度が高い可能性がある。これに対し、本発明によれば、クエリ間の関連度による場所信頼度とクエリとクリック関係にあるURL群の場所信頼度を用いることにより、クエリ間の場所信頼度が小さい場合でもURL群の場所信頼度を用いて場所を推定でき、また、URL群の場所信頼度が小さい場合でも、クエリ間の場所信頼度を用いて場所を推定できる。
【図面の簡単な説明】
【００１８】
【図１】従来の検索ログの例である。
【図２】従来技術におけるクエリ、URLのクリックグラフの例１である。
【図３】従来技術におけるクエリ、URLのクリックグラフの例２である。
【図４】従来技術におけるクエリ、URLのクリックグラフの例３である。
【図５】本発明の一実施の形態におけるクエリの場所推定装置の構成図である。
【図６】本発明の一実施の形態における検索ログ記憶部の例である。
【図７】本発明の一実施の形態における検索ログ抽出処理のフローチャートである。
【図８】本発明の一実施の形態におけるクエリの場所推定処理のフローチャートである。
【図９】本発明の一実施の形態におけるクエリ、URLの二部グラフの例である。
【図１０】本発明の一実施の形態におけるクエリ間の遷移確率算出例である。
【図１１】本発明の一実施の形態におけるクエリ間遷移確率算出部で算出されたクエリ間の遷移確率の例である。
【図１２】本発明の一実施の形態におけるURL間の遷移確率算出例である。
【図１３】本発明の一実施の形態におけるURL間遷移確率算出部で算出されたURL間の遷移確率の例である。
【図１４】本発明の一実施の形態における場所キーワード記憶部の例である。
【図１５】本発明の一実施の形態における場所URL記憶部の例である。
【図１６】本発明の一実施の形態における場所情報算出部で算出されるクエリ「渋谷 デパート」の場所ベクトルの例である。
【図１７】本発明の一実施の形態における場所情報算出部で算出されるURL1の場所ベクトルの例である。
【発明を実施するための形態】
【００１９】
以下図面と共に、本発明の実施の形態を説明する。
【００２０】
図５は、本発明の一実施の形態におけるクエリの場所推定装置の構成を示す。
【００２１】
同図に示す装置は、クエリ入力部１、検索ログ抽出部２、クエリ間遷移確率算出部３、URL間遷移確率算出部４、場所情報算出部５、場所判定部６、検索ログ記憶部７、場所キーワード記憶部８、場所URL記憶部９から構成される。
【００２２】
上記の検索ログ記憶部７、場所キーワード記憶部８、場所URL記憶部９は、ハードディスク等の記憶媒体に設けられる。
【００２３】
検索ログ記憶部７は、図６に示すように、日付、ユーザＩＤ、クエリ名、クリックURLからなる検索ログを格納する。
【００２４】
以下に、上記の構成の装置の処理を検索ログ抽出処理とクエリ場所推定処理に分けて説明する。
【００２５】
＜検索ログ抽出処理＞
クエリ入力部１にクエリq１が入力されると、検索ログ抽出部２にq１を出力する。検索ログ抽出部２は、クエリq1を取得すると、検索ログ記憶部７にアクセスし、クエリq１に関連するログを抽出する。
【００２６】
検索ログを抽出する方法について、図７のフローチャートを用いて説明する。
【００２７】
図７は、本発明の一実施の形態における検索ログ抽出処理のフローチャートである。
【００２８】
ステップ１０１） 検索ログ抽出部２は、はじめに、N_maxの値を設定する。本実施の形態では、N_max＝２とし、Ｎ＝０とする。
【００２９】
ステップ１０２） 検索ログ抽出部２は、Ｎ＝Ｎ＋１とし、クエリ入力部１から取得したクエリq1を持つクリックURLを検索ログ記憶部７から検索する。ここでは、図６の1行目と3行目を検索してURL１，URL２を抽出する。
【００３０】
ステップ１０３） 検索ログ抽出部２は、検索ログ記憶部７からURL１，URL２をクリックURLにもつクエリを抽出する。具体的には、図６の検索ログからURL１をクリックURLにもつクエリとしてq2を抽出し、URL２をクリックURLにもつクエリとしてq3を抽出する。
【００３１】
ステップ１０４） ＮがN_max以下である場合は、N＝N+1としてステップ１０２に移行し、ステップ１０３で抽出したクエリ（ｑ２、ｑ３）のクリックURLを抽出する。ＮがN_maxと同値となったら当該処理を終了する。本例ではＮ＝２となった時点で検索ログを出力する。
【００３２】
検索ログ抽出部２は、上記の処理で抽出した検索ログをクエリq１に関連する検索ログとし、クエリ間遷移確率算出部３とURL間遷移確率算出部４に出力する。
【００３３】
＜クエリ場所推定処理＞
クエリ間遷移確率算出部３とURL間遷移確率算出部４は、検索ログ抽出部２から検索ログを取得すると、クエリとURLの二部グラフを作成し、それぞれクエリ間の遷移確率とURL間の遷移確率を算出する。
【００３４】
以下にクエリ間の遷移確率、URL間の遷移確率を用いてクエリの場所を判定する方法を説明する。
【００３５】
図８は、本発明の一実施の形態におけるクエリの場所推定処理のフローチャートである。
【００３６】
ステップ２０１） クエリ間遷移確率算出部３は、検索ログ記憶部７から検索ログを読み出し、検索ログの各クエリに対し、クエリとクリック関係にあるURLｉ（i＝１，２，…，ｎ)を抽出する。
【００３７】
ステップ２０２） クエリ間遷移確率算出部３は、クエリとURLによる二部グラフを作成する。二部グラフとは、検索ログにおけるクエリとクリック関係にあるURLをエッジで結んだものであり、クエリ同士、URL同士ではエッジを結ばないグラフである。ここでは、検索ログが図６のように与えられると、図９のような二部グラフを作成する。
【００３８】
ステップ２０３） クエリ間遷移確率算出部３は、ステップ２０１で抽出したクエリの検索ログ内のクリック回数を基に、以下の式（1）でクエリURLkへのクリック確率を算出する。
【００３９】
【数１】
上記式(1)における分子のqiからURLkへのクリック回数とは、検索ログにおいて全ユーザがqiをクエリとして得た検索結果に対し、URLkをクリックした回数である。また、分母のqiの全クリック回数とは、検索ログにおいて全ユーザがqiを使って検索した検索結果のURLをクリックした回数を示している。
【００４０】
図１０に算出例を示す。上記の式において、URLkとクリック関係にある全てのクエリqi（i＝１，２，…，ｎ)に対して、URLkへのクリック確率を算出する。
【００４１】
次に、クエリqiとクエリqjの遷移確率pijを以下の式（2)を用いて算出する。
【００４２】
【数２】
上記の式(2)において、pik、pkjは図１０に示すように、クエリqiからURL k、qjからURLkへのクリック回数により求まる。また、pijを算出する際の総和は、クエリqiとURLk、URLkとクエリqjを結ぶ全てのURLk（ｋ＝１，２，…，ｎ）に対して算出する。このpijをクエリ間の遷移確率とし、この算出例を図１１に示す。クエリ間遷移確率算出部３は、当該pijを場所情報算出部５に出力する。
【００４３】
ステップ２０４） URL間遷移確率算出部４において、ステップ２０１で抽出したクエリの検索ログ内のクリック回数を基に下記の式（3）でクエリｑkへのクリック確率を算出する。
【００４４】
【数３】
上記式(3)における分子のURLiからqkへのクリック回数とは、検索ログにおいて全ユーザがq kをクエリとして得た検索結果に対しURLiをクリックした回数である。また、分母のURLiの全クリック回数とは、検索ログにおいて全ユーザがqkを使って検索した検索結果のURLiをクリックした回数を示している。
【００４５】
図１２に算出例を示す。上記の式(3)において、qkとクリック関係にある全てのURLi（i＝１，２，…，ｎ)に対して、qkへのクリック確率を算出する。
【００４６】
次に、URLiとURLjの遷移確率pijを下記の式(4)を用いて算出する。
【００４７】
【数４】
上記の式(4)において、pik，pkjは図１２に示すようにURL iからq k、URLjからqkへのクリック回数により求まる。また、pijを算出する際の総和は、URLiとqk、qkとURLjを結ぶ全てのqk（k＝１，２、…,n）に対して算出する。このpijをURL間の遷移確率とし、URL間の遷移確率の算出例を図１３に示す。また、算出されたURL間の遷移確率を場所情報算出部５へ出力する。
【００４８】
ステップ２０５） 場所情報算出部５は、ステップ２０３、ステップ２０４で算出されたクエリ間、URL間の遷移確率をクエリ間遷移確率算出部３、URL間遷移確率算出部４から取得し、それらに含まれている各クエリ、各URLに場所情報を付与する。
【００４９】
まず、はじめに、場所情報算出部５は、各クエリの表記（「渋谷 デパート」など）に該当する場所情報を場所キーワード記憶部８内から取り出す。ここで、場所キーワード記憶部８には図１４に示すように、地名としての「渋谷」のキーワードに対して場所情報の「渋谷区」や、施設名「日本スカイツリー」のキーワードに対して「台東区」の場所情報が入っている。例えば、図１１のクエリ「渋谷 デパート」には、クエリ内の「渋谷」に該当する「渋谷区」の場所情報を得る。ここで、クエリの表記において、場所キーワード記憶部８に該当するキーワードが存在しない場合、場所情報を付与できない場合もある。
【００５０】
次に、場所情報算出部５は、各URLに該当する場所情報を場所URL記憶部９から取り出す。ここで、場所URL記憶部９には、図１５に示すようなURLに対する場所情報が格納されており、本実施の形態では、図１５に示すようなURLに対する情報が格納されているものとして説明する。ここで、場所URL記憶部９内に存在しないURLには場所情報が付与できない。
【００５１】
ステップ２０６） 場所情報算出部５は、各クエリに対し、場所ベクトルを算出する。この場所ベクトルの次元は場所キーワード記憶部８、場所URL記憶部９に含まれる全ての場所情報（「渋谷区」など）で構成される。例えば、クエリ「渋谷 デパート」は渋谷区の場所情報が付加されているため、図１６のようなベクトルとなる。このクエリqiの場所ベクトルを下記の方法で算出する。
【００５２】
１）クエリqiに場所情報が付加されている時：場所情報に該当するベクトルの要素を1.0とし、それ以外の要素を０とする。
【００５３】
２）クエリｑiに場所情報が付加されていない時：ステップ２０３で算出したクエリ間の遷移確率を基に、下記の式(5)でクエリqiのベクトルを算出する。
【００５４】
【数５】
上記の式(5)において、pijはｑiとqjの遷移確率であり、q_vector(qj)はクエリqjの場所ベクトルである。
【００５５】
ステップ２０７） 場所情報算出部５は、各URLに対し場所ベクトルを算出する。この場所ベクトルの次元は、場所キーワード記憶部８、場所URL記憶部９に含まれる全ての場所情報（「渋谷区」など）で構成される。例えば、図１６のURL1は場所情報として「台東区」が該当するため、図１７のようなベクトルとなる。URLiの場所ベクトルは下記の方法で算出する。
【００５６】
１）URLiに場所情報が付加されている時：場所情報に該当するベクトルの要素を1.0とし、それ以外の要素を０とする。
【００５７】
２）URLiに場所情報が付加されていない時：ステップ２０４で算出したURL間の遷移確率を基に、下記の式(6)でURLiのベクトルを算出する。
【００５８】
【数６】
上記の式(6)において、pijは、URLiとURLjの遷移確率であり、URL_vector(URLj)はURLjの場所ベクトルである。
【００５９】
ステップ２０８） 場所判定部６は、クエリの場所を特定するため、クエリの場所ベクトルから算出する信頼度と、クエリとクリック関係にあるURLの場所ベクトルから算出される信頼度を算出する。
【００６０】
クエリqiの場所ベクトルから算出する信頼度q_trust(ｑi)は下記の式(7)で算出する。
【００６１】
【数７】
ここで、lkはクエリの場所ベクトルq_vector(qi)=(l１，l2，…,lk)の要素を示している。上記の式（7）はクエリqiの場所ベクトルの各要素の場所に対する推定確率としたときのエントロピーである。そのため、q_trust(qi)の値が大きい場合は、場所を特定できる確率が高いことを示す。
【００６２】
クエリとクリック関係にあるURLの場所ベクトルから算出する信頼度URL_trust(qi)は下記の式(8)で算出する。
【００６３】
【数８】
ここで、l kはクエリとクリック関係にあるURLの場所ベクトルを足し合わせたベクトルΣURL_vector(URLi)=(l1，l2，…，lk)の要素を示している。上記の式（8）は、クエリとクリック関係にあるURL iの場所ベクトルの総和において、各要素を場所に対する推定確率としたときのエントロピーである。そのため、URL_trust(q i)の値が大きい場合は、場所を特定できる確率が高いことを示す。
【００６４】
この２つの信頼度を基に、クエリqiの場所推定値を下記の式（9）で算出する。
【００６５】
クエリの場所推定値＝q_trust(q i)×URL_trust(q i) (9)
上記の式(9)のクエリqiの場所推定値が設定した閾値以上であればクエリｑiの場所を特定できたものと判断する。このとき、q_trust(qi)とURL_trust(qi)の値の大きさを比較し、下記の方法でクエリqiの場所を付与する。
【００６６】
１）q_trust(qi)の値が大きい場合：q_vector(qi)の要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。
【００６７】
２）URL_trust(q i)の値が大きい場合：ΣURL_vector(URLi)の要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。
【００６８】
なお、本発明を実施する上で、クエリとURLに場所情報が付与してある必要があるが、一部のクエリ、URLに場所情報が付与されている場合でも、クエリ、URLの場所を推定できる。
【００６９】
なお、上記の図５に示すクエリの場所推定装置の各構成要素の各機能をプログラムとして構築し、場所推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７１】
１ クエリ入力部
２ 検索ログ抽出部
３ クエリ間遷移確率算出部
４ URL間遷移確率算出部
５ 場所情報算出部
６ 場所判定部
７ 検索ログ記憶部
８ 場所キーワード記憶部
９ 場所URL記憶部
【技術分野】
【０００１】
本発明は、検索サービスにおけるクエリのクリックログを用いたクエリの場所推定方法及び装置及びプログラムに係り、特に、一部のクエリや一部のURLに場所情報が付与されている場合に、場所情報が付与されていないクエリ、URLの場所を推定しながら、クエリの場所推定に関する信頼度を算出し、クエリのクリック分布に基づいたグラフ分析に適用するためのクエリの場所推定方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
近年、検索サービスにおけるユーザの検索状況を示すログファイルを分析し、検索サービスの向上に利用する試みが行われている。ここで、一般に検索ログには図１に示すような項目の情報が含まれている。
【０００３】
１．日付
２．ユーザＩＤ
３．クエリ名
４．クリックURL
５．ランキング順位
図１の日付の項目は、ユーザがURLをクリックした日付である。ユーザＩＤは、検索クエリを用いて検索したユーザのＩＤである。クエリ名は、ユーザが検索に利用したクエリ名である。クリックURLはユーザがクリックした検索結果のURLである。ランキング順位はユーザがクリックしたURLの検索ランキング順位である。
【０００４】
これらのログは、ユーザの検索行動の効率化に利用されている。その利用情報の一つにクエリ推薦がある。このクエリ推薦では、ユーザが投入したクエリとクリックしたURLが対になった図２のような二部グラフを用いて推薦している。図２の左側はユーザが投入したクエリ名であり、右側は検索結果からユーザがクリックしたURLを表している。また、ユーザがクエリを投入して実際にクリックしたURLをエッジで連結している。この二部グラフを解析し、結びつきの強いクエリを推薦クエリとして用いている。
【０００５】
ここで、検索ログを用いたクエリ推薦の代表的な技術として、クエリとURLの関連性を二部グラフを用いてクエリとURＬ間の関連性を算出する技術がある（例えば、非特許文献１参照）。この技術では、クエリとURLの関連性を二部グラフを用いて、クエリとURL間の関連性を算出している。
【０００６】
これらログファイルを用いて、ユーザが欲しいページを見つけやすいクエリを推薦する技術が存在する（例えば、非特許文献１参照）。この技術では、クエリとURLの関連性を二部グラフを用いて、クエリとURL間の関連性を算出する際に、同じ検索意図のクエリが同じURL群にアクセスしている性質を利用し、同じ検索意図のクエリをクラスタリングしている。クラスタリングしたクエリにおいて、関連度の高いクエリを代表クエリとしている。ユーザにクエリを推薦する場合は、ユーザが利用しようとするクエリに対し、そのクエリが属するクラスタリング内のクエリ群から関連度の高いクエリを推薦する。この技術により、ユーザはより検索精度の高いクエリで検索を行うことができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Hangbo Deng. Irwin King, Michael R. Lyu: Entropy-biased Models for Query Representation on the Click Graph, ACM SIGIR, pages 339-346, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、クエリが関係する場所（例えば、クエリ「渋谷 デパート」は渋谷に関するクエリ）を特定することを目的とし、従来手法を用いてクエリに関連度の高い他のクエリが関連する場所を利用する場合、場所とは関係のないクエリの結びつきが問題になることがある。
【０００９】
例えば、横浜のデパートでアクセサリを販売しており、渋谷のデパートではアクセサリを販売していない場合に、図３に示すようなクリックグラフが存在するものとする。このとき、クエリ「デパート アクセサリ」では横浜でアクセサリを販売しているため、横浜のデパートに関連するURL2, URL3をクリックしている。しかし、従来手法を用いてクエリ間の関連度を算出し、クエリ「デパート アクセサリ」とクエリ「渋谷 デパート」の関連度が大きい場合、渋谷ではアクセサリを販売していないためクエリ「デパート アクセサリ」が渋谷でも利用できると判断される。
【００１０】
他の例として、図４のようにクエリ「デパート アクセサリ」がクエリ「渋谷 デパート」とクエリ「横浜 デパート」との関連度が小さい場合は、クエリ「デパート アクセサリ」は利用できる場所が特定できない。しかし、クエリ「デパート アクセサリ」でクリックしているURL2、URL3はともに横浜のデパートに関係するURLのため、クエリ「デパート アクセサリ」は横浜で利用できるクエリと考えるのが妥当である。
【００１１】
このように、クエリ間の関連度を用いてクエリが利用できる場所を特定するには、従来手法のみでは適用できないという問題がある。
【００１２】
本発明は、上記の点に鑑みなされたもので、クエリ間の関連度とクエリとクリック関係にあるＵＲＬ群の場所に対する関連度を用いて、クエリが利用できる場所を推定することが可能なクエリの場所推定方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するため、本発明（請求項１）は、検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、
前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、
前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、
場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出ステップと、
前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出ステップと、
場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、を有する。
【００１４】
また、本発明（請求項２）は、前記クエリ間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる。
【００１５】
また、本発明（請求項３）は、前記URL間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる。
【００１６】
また、本発明（請求項４）は、前記第１の場所情報算出ステップにおいて、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、
前記第２の場所情報算出ステップにおいて、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、
前記場所判定ステップにおいて、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする。
【発明の効果】
【００１７】
従来の技術では、クエリ間の関連度によるクエリの場所的な繋がりを特定する目的において、クエリとURLのクリック関係を２部グラフにして関連度を算出する場合、クリック関係の特徴によって場所的な繋がりがないクエリとの関連度が高い可能性がある。これに対し、本発明によれば、クエリ間の関連度による場所信頼度とクエリとクリック関係にあるURL群の場所信頼度を用いることにより、クエリ間の場所信頼度が小さい場合でもURL群の場所信頼度を用いて場所を推定でき、また、URL群の場所信頼度が小さい場合でも、クエリ間の場所信頼度を用いて場所を推定できる。
【図面の簡単な説明】
【００１８】
【図１】従来の検索ログの例である。
【図２】従来技術におけるクエリ、URLのクリックグラフの例１である。
【図３】従来技術におけるクエリ、URLのクリックグラフの例２である。
【図４】従来技術におけるクエリ、URLのクリックグラフの例３である。
【図５】本発明の一実施の形態におけるクエリの場所推定装置の構成図である。
【図６】本発明の一実施の形態における検索ログ記憶部の例である。
【図７】本発明の一実施の形態における検索ログ抽出処理のフローチャートである。
【図８】本発明の一実施の形態におけるクエリの場所推定処理のフローチャートである。
【図９】本発明の一実施の形態におけるクエリ、URLの二部グラフの例である。
【図１０】本発明の一実施の形態におけるクエリ間の遷移確率算出例である。
【図１１】本発明の一実施の形態におけるクエリ間遷移確率算出部で算出されたクエリ間の遷移確率の例である。
【図１２】本発明の一実施の形態におけるURL間の遷移確率算出例である。
【図１３】本発明の一実施の形態におけるURL間遷移確率算出部で算出されたURL間の遷移確率の例である。
【図１４】本発明の一実施の形態における場所キーワード記憶部の例である。
【図１５】本発明の一実施の形態における場所URL記憶部の例である。
【図１６】本発明の一実施の形態における場所情報算出部で算出されるクエリ「渋谷 デパート」の場所ベクトルの例である。
【図１７】本発明の一実施の形態における場所情報算出部で算出されるURL1の場所ベクトルの例である。
【発明を実施するための形態】
【００１９】
以下図面と共に、本発明の実施の形態を説明する。
【００２０】
図５は、本発明の一実施の形態におけるクエリの場所推定装置の構成を示す。
【００２１】
同図に示す装置は、クエリ入力部１、検索ログ抽出部２、クエリ間遷移確率算出部３、URL間遷移確率算出部４、場所情報算出部５、場所判定部６、検索ログ記憶部７、場所キーワード記憶部８、場所URL記憶部９から構成される。
【００２２】
上記の検索ログ記憶部７、場所キーワード記憶部８、場所URL記憶部９は、ハードディスク等の記憶媒体に設けられる。
【００２３】
検索ログ記憶部７は、図６に示すように、日付、ユーザＩＤ、クエリ名、クリックURLからなる検索ログを格納する。
【００２４】
以下に、上記の構成の装置の処理を検索ログ抽出処理とクエリ場所推定処理に分けて説明する。
【００２５】
＜検索ログ抽出処理＞
クエリ入力部１にクエリq１が入力されると、検索ログ抽出部２にq１を出力する。検索ログ抽出部２は、クエリq1を取得すると、検索ログ記憶部７にアクセスし、クエリq１に関連するログを抽出する。
【００２６】
検索ログを抽出する方法について、図７のフローチャートを用いて説明する。
【００２７】
図７は、本発明の一実施の形態における検索ログ抽出処理のフローチャートである。
【００２８】
ステップ１０１） 検索ログ抽出部２は、はじめに、N_maxの値を設定する。本実施の形態では、N_max＝２とし、Ｎ＝０とする。
【００２９】
ステップ１０２） 検索ログ抽出部２は、Ｎ＝Ｎ＋１とし、クエリ入力部１から取得したクエリq1を持つクリックURLを検索ログ記憶部７から検索する。ここでは、図６の1行目と3行目を検索してURL１，URL２を抽出する。
【００３０】
ステップ１０３） 検索ログ抽出部２は、検索ログ記憶部７からURL１，URL２をクリックURLにもつクエリを抽出する。具体的には、図６の検索ログからURL１をクリックURLにもつクエリとしてq2を抽出し、URL２をクリックURLにもつクエリとしてq3を抽出する。
【００３１】
ステップ１０４） ＮがN_max以下である場合は、N＝N+1としてステップ１０２に移行し、ステップ１０３で抽出したクエリ（ｑ２、ｑ３）のクリックURLを抽出する。ＮがN_maxと同値となったら当該処理を終了する。本例ではＮ＝２となった時点で検索ログを出力する。
【００３２】
検索ログ抽出部２は、上記の処理で抽出した検索ログをクエリq１に関連する検索ログとし、クエリ間遷移確率算出部３とURL間遷移確率算出部４に出力する。
【００３３】
＜クエリ場所推定処理＞
クエリ間遷移確率算出部３とURL間遷移確率算出部４は、検索ログ抽出部２から検索ログを取得すると、クエリとURLの二部グラフを作成し、それぞれクエリ間の遷移確率とURL間の遷移確率を算出する。
【００３４】
以下にクエリ間の遷移確率、URL間の遷移確率を用いてクエリの場所を判定する方法を説明する。
【００３５】
図８は、本発明の一実施の形態におけるクエリの場所推定処理のフローチャートである。
【００３６】
ステップ２０１） クエリ間遷移確率算出部３は、検索ログ記憶部７から検索ログを読み出し、検索ログの各クエリに対し、クエリとクリック関係にあるURLｉ（i＝１，２，…，ｎ)を抽出する。
【００３７】
ステップ２０２） クエリ間遷移確率算出部３は、クエリとURLによる二部グラフを作成する。二部グラフとは、検索ログにおけるクエリとクリック関係にあるURLをエッジで結んだものであり、クエリ同士、URL同士ではエッジを結ばないグラフである。ここでは、検索ログが図６のように与えられると、図９のような二部グラフを作成する。
【００３８】
ステップ２０３） クエリ間遷移確率算出部３は、ステップ２０１で抽出したクエリの検索ログ内のクリック回数を基に、以下の式（1）でクエリURLkへのクリック確率を算出する。
【００３９】
【数１】
上記式(1)における分子のqiからURLkへのクリック回数とは、検索ログにおいて全ユーザがqiをクエリとして得た検索結果に対し、URLkをクリックした回数である。また、分母のqiの全クリック回数とは、検索ログにおいて全ユーザがqiを使って検索した検索結果のURLをクリックした回数を示している。
【００４０】
図１０に算出例を示す。上記の式において、URLkとクリック関係にある全てのクエリqi（i＝１，２，…，ｎ)に対して、URLkへのクリック確率を算出する。
【００４１】
次に、クエリqiとクエリqjの遷移確率pijを以下の式（2)を用いて算出する。
【００４２】
【数２】
上記の式(2)において、pik、pkjは図１０に示すように、クエリqiからURL k、qjからURLkへのクリック回数により求まる。また、pijを算出する際の総和は、クエリqiとURLk、URLkとクエリqjを結ぶ全てのURLk（ｋ＝１，２，…，ｎ）に対して算出する。このpijをクエリ間の遷移確率とし、この算出例を図１１に示す。クエリ間遷移確率算出部３は、当該pijを場所情報算出部５に出力する。
【００４３】
ステップ２０４） URL間遷移確率算出部４において、ステップ２０１で抽出したクエリの検索ログ内のクリック回数を基に下記の式（3）でクエリｑkへのクリック確率を算出する。
【００４４】
【数３】
上記式(3)における分子のURLiからqkへのクリック回数とは、検索ログにおいて全ユーザがq kをクエリとして得た検索結果に対しURLiをクリックした回数である。また、分母のURLiの全クリック回数とは、検索ログにおいて全ユーザがqkを使って検索した検索結果のURLiをクリックした回数を示している。
【００４５】
図１２に算出例を示す。上記の式(3)において、qkとクリック関係にある全てのURLi（i＝１，２，…，ｎ)に対して、qkへのクリック確率を算出する。
【００４６】
次に、URLiとURLjの遷移確率pijを下記の式(4)を用いて算出する。
【００４７】
【数４】
上記の式(4)において、pik，pkjは図１２に示すようにURL iからq k、URLjからqkへのクリック回数により求まる。また、pijを算出する際の総和は、URLiとqk、qkとURLjを結ぶ全てのqk（k＝１，２、…,n）に対して算出する。このpijをURL間の遷移確率とし、URL間の遷移確率の算出例を図１３に示す。また、算出されたURL間の遷移確率を場所情報算出部５へ出力する。
【００４８】
ステップ２０５） 場所情報算出部５は、ステップ２０３、ステップ２０４で算出されたクエリ間、URL間の遷移確率をクエリ間遷移確率算出部３、URL間遷移確率算出部４から取得し、それらに含まれている各クエリ、各URLに場所情報を付与する。
【００４９】
まず、はじめに、場所情報算出部５は、各クエリの表記（「渋谷 デパート」など）に該当する場所情報を場所キーワード記憶部８内から取り出す。ここで、場所キーワード記憶部８には図１４に示すように、地名としての「渋谷」のキーワードに対して場所情報の「渋谷区」や、施設名「日本スカイツリー」のキーワードに対して「台東区」の場所情報が入っている。例えば、図１１のクエリ「渋谷 デパート」には、クエリ内の「渋谷」に該当する「渋谷区」の場所情報を得る。ここで、クエリの表記において、場所キーワード記憶部８に該当するキーワードが存在しない場合、場所情報を付与できない場合もある。
【００５０】
次に、場所情報算出部５は、各URLに該当する場所情報を場所URL記憶部９から取り出す。ここで、場所URL記憶部９には、図１５に示すようなURLに対する場所情報が格納されており、本実施の形態では、図１５に示すようなURLに対する情報が格納されているものとして説明する。ここで、場所URL記憶部９内に存在しないURLには場所情報が付与できない。
【００５１】
ステップ２０６） 場所情報算出部５は、各クエリに対し、場所ベクトルを算出する。この場所ベクトルの次元は場所キーワード記憶部８、場所URL記憶部９に含まれる全ての場所情報（「渋谷区」など）で構成される。例えば、クエリ「渋谷 デパート」は渋谷区の場所情報が付加されているため、図１６のようなベクトルとなる。このクエリqiの場所ベクトルを下記の方法で算出する。
【００５２】
１）クエリqiに場所情報が付加されている時：場所情報に該当するベクトルの要素を1.0とし、それ以外の要素を０とする。
【００５３】
２）クエリｑiに場所情報が付加されていない時：ステップ２０３で算出したクエリ間の遷移確率を基に、下記の式(5)でクエリqiのベクトルを算出する。
【００５４】
【数５】
上記の式(5)において、pijはｑiとqjの遷移確率であり、q_vector(qj)はクエリqjの場所ベクトルである。
【００５５】
ステップ２０７） 場所情報算出部５は、各URLに対し場所ベクトルを算出する。この場所ベクトルの次元は、場所キーワード記憶部８、場所URL記憶部９に含まれる全ての場所情報（「渋谷区」など）で構成される。例えば、図１６のURL1は場所情報として「台東区」が該当するため、図１７のようなベクトルとなる。URLiの場所ベクトルは下記の方法で算出する。
【００５６】
１）URLiに場所情報が付加されている時：場所情報に該当するベクトルの要素を1.0とし、それ以外の要素を０とする。
【００５７】
２）URLiに場所情報が付加されていない時：ステップ２０４で算出したURL間の遷移確率を基に、下記の式(6)でURLiのベクトルを算出する。
【００５８】
【数６】
上記の式(6)において、pijは、URLiとURLjの遷移確率であり、URL_vector(URLj)はURLjの場所ベクトルである。
【００５９】
ステップ２０８） 場所判定部６は、クエリの場所を特定するため、クエリの場所ベクトルから算出する信頼度と、クエリとクリック関係にあるURLの場所ベクトルから算出される信頼度を算出する。
【００６０】
クエリqiの場所ベクトルから算出する信頼度q_trust(ｑi)は下記の式(7)で算出する。
【００６１】
【数７】
ここで、lkはクエリの場所ベクトルq_vector(qi)=(l１，l2，…,lk)の要素を示している。上記の式（7）はクエリqiの場所ベクトルの各要素の場所に対する推定確率としたときのエントロピーである。そのため、q_trust(qi)の値が大きい場合は、場所を特定できる確率が高いことを示す。
【００６２】
クエリとクリック関係にあるURLの場所ベクトルから算出する信頼度URL_trust(qi)は下記の式(8)で算出する。
【００６３】
【数８】
ここで、l kはクエリとクリック関係にあるURLの場所ベクトルを足し合わせたベクトルΣURL_vector(URLi)=(l1，l2，…，lk)の要素を示している。上記の式（8）は、クエリとクリック関係にあるURL iの場所ベクトルの総和において、各要素を場所に対する推定確率としたときのエントロピーである。そのため、URL_trust(q i)の値が大きい場合は、場所を特定できる確率が高いことを示す。
【００６４】
この２つの信頼度を基に、クエリqiの場所推定値を下記の式（9）で算出する。
【００６５】
クエリの場所推定値＝q_trust(q i)×URL_trust(q i) (9)
上記の式(9)のクエリqiの場所推定値が設定した閾値以上であればクエリｑiの場所を特定できたものと判断する。このとき、q_trust(qi)とURL_trust(qi)の値の大きさを比較し、下記の方法でクエリqiの場所を付与する。
【００６６】
１）q_trust(qi)の値が大きい場合：q_vector(qi)の要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。
【００６７】
２）URL_trust(q i)の値が大きい場合：ΣURL_vector(URLi)の要素において、最も値の大きい要素に該当する場所をクエリqiの場所とする。
【００６８】
なお、本発明を実施する上で、クエリとURLに場所情報が付与してある必要があるが、一部のクエリ、URLに場所情報が付与されている場合でも、クエリ、URLの場所を推定できる。
【００６９】
なお、上記の図５に示すクエリの場所推定装置の各構成要素の各機能をプログラムとして構築し、場所推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７１】
１ クエリ入力部
２ 検索ログ抽出部
３ クエリ間遷移確率算出部
４ URL間遷移確率算出部
５ 場所情報算出部
６ 場所判定部
７ 検索ログ記憶部
８ 場所キーワード記憶部
９ 場所URL記憶部
【特許請求の範囲】
【請求項１】
検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、
前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、
前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、
場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出ステップと、
前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出ステップと、
場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、
を有することを特徴とするクエリの場所推定方法。
【請求項２】
前記クエリ間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる
請求項１記載のクエリの場所推定方法。
【請求項３】
前記URL間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる
請求項１記載のクエリの場所推定方法。
【請求項４】
前記第１の場所情報算出ステップにおいて、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、
前記第２の場所情報算出ステップにおいて、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、
前記場所判定ステップにおいて、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする
請求項１記載のクエリの場所推定方法。
【請求項５】
検索サービスにおいて、クエリの場所を推定するクエリの場所推定装置であって、
ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、
前記検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、
前記クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置において、
前記関連度算出手段は、
前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数に基づいてクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出手段と、
URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出手段を有し、
前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出手段と、
前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出手段と、
前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定手段と、
を更に有することを特徴とするクエリの場所推定装置。
【請求項６】
前記クエリ間遷移確率算出手段は、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる
請求項５記載のクエリの場所推定装置。
【請求項７】
前記URL間遷移確率算出手段は、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる
請求項５記載のクエリの場所推定装置。
【請求項８】
前記第１の場所情報算出手段は、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分する手段を含み、
前記第２の場所情報算出手段は、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分する手段を含み、
前記場所判定手段は、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出する手段と、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出する手段と、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする手段と、
を含む請求項５記載のクエリの場所推定装置。
【請求項９】
コンピュータを、
請求項５乃至８のいずれか１項に記載のクエリの場所推定装置の各手段として機能させるクエリの場所推定プログラム。
【請求項１】
検索サービスにおいて、ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、該検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、該クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置におけるクエリの場所推定方法であって、
前記関連度算出手段が、前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数を基にクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出ステップと、
前記関連度算出手段が、URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出ステップと、
場所情報算出手段が、前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出ステップと、
前記場所情報算出手段が、前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出ステップと、
場所判定手段が、前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定ステップと、
を有することを特徴とするクエリの場所推定方法。
【請求項２】
前記クエリ間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる
請求項１記載のクエリの場所推定方法。
【請求項３】
前記URL間遷移確率算出ステップにおいて、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる
請求項１記載のクエリの場所推定方法。
【請求項４】
前記第１の場所情報算出ステップにおいて、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分し、
前記第２の場所情報算出ステップにおいて、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分し、
前記場所判定ステップにおいて、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出し、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出し、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする
請求項１記載のクエリの場所推定方法。
【請求項５】
検索サービスにおいて、クエリの場所を推定するクエリの場所推定装置であって、
ユーザの投入したクエリと該クエリに対する検索結果においてクリックしたURLから構成される検索ログを記録する検索ログ記憶手段と、
前記検索ログから対象とするクエリに関連するクエリ群とURL群を抽出する検索ログ抽出手段と、
前記クエリとクリックされたURLから構成される二部グラフを作成し、二部グラフを用いてクエリ間、URL間の関連度を算出する関連度算出手段と、を有する装置において、
前記関連度算出手段は、
前記二部グラフにおいてクエリとURLを結ぶエッジの重みをクリック回数に基づいてクエリ間遷移確率算出ルールに基づいてクエリ間の遷移確率を算出するクエリ間遷移確率算出手段と、
URL間遷移確率算出ルールに基づいてURL間の遷移確率を算出するURL間遷移確率算出手段を有し、
前記クエリ間の遷移確率に基づいてクエリの場所推定値を算出する第１の場所情報算出手段と、
前記URL間の遷移確率に基づいてURLの場所推定値を算出する第２の場所情報算出手段と、
前記クエリの場所推定値と前記URLの場所推定値を用いてクエリの場所を判定する場所判定手段と、
を更に有することを特徴とするクエリの場所推定装置。
【請求項６】
前記クエリ間遷移確率算出手段は、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、該クエリから該URLへの遷移確率に基づいてクエリ間を結ぶURLを介した遷移確率を算出する前記クエリ間遷移確率算出ルールを用いる
請求項５記載のクエリの場所推定装置。
【請求項７】
前記URL間遷移確率算出手段は、
クエリの投入回数とURLへのクリック回数に基づいてエッジの重みを算出し、URLからクエリへの遷移確率に基づいてURL,間を結ぶクエリを介した遷移確率を算出する前記URL間遷移確率算出ルールを用いる
請求項５記載のクエリの場所推定装置。
【請求項８】
前記第１の場所情報算出手段は、
前記クエリの場所ベクトルを前記クエリ間の遷移確率を用いて他のクエリのもつ場所情報を当該クエリの場所ベクトルへ配分する手段を含み、
前記第２の場所情報算出手段は、
前記URLの場所ベクトルを前記URL間の遷移確率を用いて他のURLのもつ場所情報を当該URLの場所ベクトルへ配分する手段を含み、
前記場所判定手段は、
前記クエリの場所ベクトルの要素を確率として用い、クエリの場所信頼度として確率エントロピーを算出する手段と、
前記クエリとクリック関係にあるURLの場所ベクトルの総和の各ベクトル要素を確率として用い、URLの場所信頼度として確率エントロピーを算出する手段と、
前記クエリの場所信頼度と前記URLの場所信頼度を乗じたものをクエリの場所を判定する値としてもち、該値が閾値以上であればクエリの場所をクエリの場所ベクトルの要素の中で最も大きい値の要素に対応する場所をクエリの場所とする手段と、
を含む請求項５記載のクエリの場所推定装置。
【請求項９】
コンピュータを、
請求項５乃至８のいずれか１項に記載のクエリの場所推定装置の各手段として機能させるクエリの場所推定プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１３−１０９５８３（Ｐ２０１３−１０９５８３Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５４２２９（Ｐ２０１１−２５４２２９）
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
[ Back to top ]