(57)【特許請求の範囲】
【請求項１】
検索サービスのクエリに対する検索結果においてクリックされた日時と店舗を記録する検索ログ記憶手段と、該検索ログ記憶手段から対象とするクエリに関連するクエリ群と店舗群を抽出する検索ログ抽出手段と、該検索ログ抽出手段で抽出された情報に基づいて、該クエリとクリックされた店舗から構成される二部グラフを作成し、店舗間の遷移確率を算出する店舗クエリグラフ作成手段と、入力された店舗と入力された時間とに関連する特徴語を抽出する特徴語抽出手段と、店舗毎の行動キーワードと営業時間を格納した店舗情報記憶手段と、を有し、キーワードを抽出するキーワード抽出装置であって、
前記店舗クエリグラフ作成手段は、
前記二部グラフにおいてクエリと店舗間のエッジの重みを算出するエッジ重み算出手段と、
店舗の営業時間に応じて定まる店舗の時間重みと、該エッジの重みとから店舗間の遷移確率を算出する遷移確率算出手段と、
を有し、
前記特徴語抽出手段は、
時間を入力として、前記店舗情報記憶手段から店舗の行動キーワードを取得し、該時間に対応する前記店舗の時間重み、および、前記店舗間の遷移確率に基づいて、該行動キーワードの関連度を算出するキーワード関連度算出手段と、
該行動キーワードの関連度に基づいて、入力された店舗に対する特徴語を抽出するキーワード抽出手段と、
を有することを特徴とするキーワード抽出装置。
【請求項２】
前記遷移確率算出手段は、
前記店舗の時間重みに前記エッジの重みを掛け合わせて店舗間の遷移確率を算出する
請求項１記載のキーワード抽出装置。
【請求項３】
前記キーワード関連度算出手段は、
前記店舗の時間重み、および、前記店舗間の遷移確率との線形和によって、前記行動キーワードの関連度を算出する
請求項１記載のキーワード抽出装置。
【請求項４】
検索サービスのクエリに対する検索結果においてクリックされた日時と店舗を記録する検索ログ記憶手段と、該検索ログ記憶手段から対象とするクエリに関連するクエリ群と店舗群を抽出する検索ログ抽出手段と、該検索ログ抽出手段で抽出された情報に基づいて、該クエリとクリックされた店舗から構成される二部グラフを作成し、店舗間の遷移確率を算出する店舗クエリグラフ作成手段と、入力された店舗と入力された時間とに関連する特徴語を抽出する特徴語抽出手段と、店舗毎の行動キーワードと営業時間を格納した店舗情報記憶手段と、を有し、キーワードを抽出するキーワード抽出方法であって、
前記店舗クエリグラフ作成手段が、前記二部グラフにおいてクエリと店舗間のエッジの重みを算出し、店舗の営業時間に応じて定まる店舗の時間重みと、該エッジの重みとから店舗間の遷移確率を算出する遷移確率算出ステップと、
前記特徴語抽出手段が、時間を入力として、前記店舗情報記憶手段から店舗の行動キーワードを取得し、該時間に対応する前記店舗の時間重み、および、前記店舗間の遷移確率に基づいて、該行動キーワードの関連度を算出し、該行動キーワードの関連度に基づいて、入力された店舗に対する特徴語を抽出するキーワード抽出ステップと、
を行うことを特徴とするキーワード抽出方法。
【請求項５】
前記遷移確率算出ステップにおいて、
前記店舗の時間重みに前記エッジの重みを掛け合わせて店舗間の遷移確率を算出する
請求項４記載のキーワード抽出方法。
【請求項６】
前記キーワード抽出ステップにおいて、
前記店舗の時間重み、および、前記店舗間の遷移確率との線形和によって、前記行動キーワードの関連度を算出する
請求項４記載のキーワード抽出方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載のキーワード抽出装置の各手段として機能させるためのキーワード抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キーワード抽出装置及び方法及びプログラムに係り、特に、検索ログを用いてキーワードを抽出するためのキーワード抽出装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
近年、検索サービスにおける検索ログを用いてクエリ間やＵＲＬ間の関連性を算出し、クエリ推薦やＵＲＬ推薦に利用する試みが行われている。ここで、一般に検索ログは図1に示すように、日付、ユーザＩＤ、クエリ名、クリックＵＲＬ、店舗名（クリックしたＵＲＬのラベル名）等の情報が含まれている。
【０００３】
図1の日付項目は、ユーザがＵＲＬをクリックした日付である。ユーザＩＤは、検索クエリを用いて検索したユーザのＩＤである。クエリ名は、ユーザが検索に利用したクエリ名である。クリックＵＲＬは、ユーザがクリックした検索結果のＵＲＬである。店舗名はＵＲＬ先のページの内容を表す店舗名である（店舗の公式ページなど）。
【０００４】
これらの検索ログを基に、ユーザが投入したクエリとクリックしたＵＲＬが対になった図２のような二部グラフを用いてクエリ間やＵＲＬ間の関連性を算出する。図２の右側はユーザが投入したクエリ名であり、左側は検索結果からユーザがクリックしたＵＲＬを表している。
【０００５】
ここで、図２はでは、ＵＲＬとして図1の店舗名を記載している。また、ユーザがクエリを投入して実際にクリックした店舗名（クリックＵＲＬ）をエッジで連結している。この二部グラフを解析し、クエリ間や店舗間に結びつきが強い場合、それらは関連性が大きいとしている。
【０００６】
ここで、検索ログを用いたクエリ推薦の代表的な技術として、Dengらのクエリ推薦技術が存在する（例えば、非特許文献1参照）。この技術では、クエリと店舗名（クリックＵＲＬ）の関連性を二部グラフを用いて、クエリと店舗間の関連性を算出している。
【０００７】
前述の技術を用いて店舗情報検索ログに対して店舗同士の結びつきを算出するのに応用できる。ここで、店舗情報検索ログとは、クエリとその検索結果をクリックした店舗名から構成され、店舗間の関連性を算出できる。
【０００８】
この店舗に対する店舗情報として、店舗のキーワード（例：ネットカフェの行動キーワード「漫画を読む」）があった場合、関連する店舗のキーワードを用いて、店舗の関連するキーワードを抽出することが可能である。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Hongbo Deng, Irwin King, Michael R. Lyu: Entropy-biased Models for Query Representation on the click Graph, ACM SIGIR, pages 339-346, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来の技術では、店舗検索ログを用いてグラフ解析による関連情報を抽出した場合、店舗名とクエリに時間的なつながりを反映できないため、時間に依存しない店舗間の関連度が算出される。そのため、時間によらず関連するキーワードは同じである。
【００１１】
例えば、お昼の時間帯にランチを提供し、夜は居酒屋を営業するような店舗があった場合、従来手法では時間に依存せず「お昼を食べる」が関連するキーワードとして抽出される。
【００１２】
このように、時間に応じて関連するキーワードが異なる場合は、時間に依存しない従来手法は適用できない。
【００１３】
本発明は、上記の点に鑑みなされたもので、入力される時間に応じて関連するキーワードを抽出することが可能なキーワード抽出装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するため、本発明（請求項１）は、検索サービスのクエリに対する検索結果においてクリックされた日時と店舗を記録する検索ログ記憶手段と、該検索ログ記憶手段から対象とするクエリに関連するクエリ群と店舗群を抽出する検索ログ抽出手段と、該検索ログ抽出手段で抽出された情報に基づいて、該クエリとクリックされた店舗から構成される二部グラフを作成し、店舗間の遷移確率を算出する店舗クエリグラフ作成手段と、入力された店舗と入力された時間とに関連する特徴語を抽出する特徴語抽出手段と、店舗毎の行動キーワードと営業時間を格納した店舗情報記憶手段と、を有し、キーワードを抽出するキーワード抽出装置であって、
前記店舗クエリグラフ作成手段は、
前記二部グラフにおいてクエリと店舗間のエッジの重みを算出するエッジ重み算出手段と、
店舗の営業時間に応じて定まる店舗の時間重みと、該エッジの重みとから店舗間の遷移確率を算出する遷移確率算出手段と、
を有し、
前記特徴語抽出手段は、
時間を入力として、前記店舗情報記憶手段から店舗の行動キーワードを取得し、該時間に対応する前記店舗の時間重み、および、前記店舗間の遷移確率に基づいて、該行動キーワードの関連度を算出するキーワード関連度算出手段と、
該行動キーワードの関連度に基づいて、入力された店舗に対する特徴語を抽出するキーワード抽出手段と、を有する。
【００１５】
また、本発明（請求項２）は、前記遷移確率算出手段において、
前記店舗の時間重みに前記エッジの重みを掛け合わせて店舗間の遷移確率を算出する。
【００１７】
また、本発明（請求項３）は、前記キーワード関連度算出手段において、
前記店舗の時間重み、および、前記店舗間の遷移確率との線形和によって、前記行動キーワードの関連度を算出する。
【発明の効果】
【００１８】
本発明によれば、店舗検索ログを用いて店舗間の遷移確率を算出する際に、営業時間による重み関数を用いて店舗間の時間的なつながりを考慮した確率計算を行う。また、関連するキーワードに店舗間の遷移確率による値と、関連が有効な時間(店舗の営業時間)を用いて、時間を入力としてその時間に応じた関連するキーワードを抽出する。
【００１９】
これにより、入力される時間応じて関連する行動キーワードが変化するため、時間に対応する適切なキーワードを抽出することができる。
【図面の簡単な説明】
【００２０】
【図１】従来技術における店舗検索ログの例である。
【図２】従来の店舗・クエリグラフの例である。
【図３】本発明の医師実施の形態におけるキーワード抽出装置の構成図である。
【図４】本発明の一実施の形態における店舗検索ログ記憶部のデータ例である。
【図５】本発明の一実施の形態における店舗情報記憶部のデータ例（その１）である。
【図６】本発明の一実施の形態における店舗検索ログ抽出フローチャートである。
【図７】本発明の一実施の形態における遷移確率算出フローチャートである。
【図８】本発明の一実施の形態における店舗・クエリグラフの例である。
【図９】本発明の一実施の形態における遷移確率算出例である。
【図１０】本発明の一実施の形態における営業時間の重み関数である。
【図１１】本発明の一実施の形態における店舗間の遷移確率である。
【図１２】本発明の一実施の形態における店舗情報記憶部のデータ例（その２）である。
【図１３】本発明の一実施の形態における「ネットカフェ」に関する特徴語のリストである。
【発明を実施するための形態】
【００２１】
以下図面と共に、本発明の実施の形態を説明する。
【００２２】
図３は、本発明の一実施の形態におけるキーワード抽出装置の構成図である。
【００２３】
同図に示すキーワード抽出装置は、店舗名入力部１、店舗検索ログ抽出部２、店舗・クエリグラフ作成部３、店舗情報抽出部４、特徴語抽出部５、店舗検索ログ記憶部６、店舗情報記憶部７から構成される。
【００２４】
上記の店舗検索ログ記憶部６は、図４に示すように、日付、ユーザＩＤ、クエリ名、店舗名の項目のデータを格納する。
【００２５】
また、店舗情報記憶部７は、図５に示すように、店舗名、行動キーワード、営業時間の項目のデータを格納する。
【００２６】
店舗名入力部1に店舗名"shop1"が入力されると、店舗検索ログ抽出部２に"shop1"を出力する。
【００２７】
店舗検索ログ抽出部２は、取得した"shop1"に基づいて、店舗検索ログ記憶部６にアクセスし、"shop1"に関連する店舗検索ログを抽出する。
【００２８】
店舗検索ログを抽出する方法について図６を用いて説明する。
【００２９】
ステップ０）  店舗検索ログ抽出部２は、N_maxの値を設定する。本実施の形態では、N_max=2とし、N=0とする。
【００３０】
ステップ１）  次に、Ｎ＝Ｎ＋１とし、店舗検索ログ抽出部２は、店舗検索ログ記憶部６から"shop1"の店舗名を持つ行を検索する。ここでは、図４の１行目と２行目を検索して抽出する。
【００３１】
ステップ２）  店舗検索ログ抽出部２は、店舗検索ログ記憶部６から"shop1"に結びつくクエリを抽出する。次に、このクエリに結びつく店舗名を含む店舗検索ログを抽出する。具体的には、図４からの"shop1"を店舗名にもつクエリとしてｑ１、ｑ2を抽出し、ｑ１、ｑ2をクエリにもつ店舗名"shop3"、"shop4"を抽出する。
【００３２】
ステップ３）  NがN_max以下である場合にはステップ1に戻り、Nの値がN_maxと同値となったら処理を終了する。この場合、NがN_max以下であるため、ステップ1に戻り、N=N+1=2とし、上記で抽出した店舗検索ログに含まれる"shop1"以外の全ての店舗名"shop2"、"shop3"を含むクエリを抽出する。
【００３３】
これらの処理で抽出した店舗検索ログを"shop1"に関連する店舗検索ログとし、店舗・クエリグラフ作成部３に出力する。また、店舗検索ログから店舗名のみを店舗情報抽出部４に出力する。
【００３４】
店舗・クエリグラフ作成部３は、店舗検索ログ抽出部２から店舗検索ログを取得すると、店舗とクエリ間のグラフを作成し、店舗間の遷移確率を算出する。店舗間の遷移確率を算出する方法を図７を用いて説明する。
【００３５】
ステップ１０）  店舗・クエリグラフ作成部３は、店舗検索ログ抽出部２から店舗検索ログを取得し、店舗検索ログの各店舗名に対し、店舗名"shopk"とつながりのあるクエリｑｉ(ｉ=1，2，…，ｎ)を抽出する。
【００３６】
ステップ１１）  店舗・クエリグラフ作成部３は、二部グラフを作成する。二部グラフとは、店舗とクエリの対をエッジで結んだものでああり、店舗同士、クエリ同士ではエッジを結ばないグラフである。ここでは、店舗検索ログが図４のように与えられると、図８のような二部グラフを作成する。
【００３７】
ステップ１２）  ステップ１１で抽出した"shopi"の店舗検索ログ内のクリック回数を基に下記の式でクエリｑｋへのクリック確率pikを算出する。
【００３８】
【数１】
0005650606.tif 000002
上記式における分子の"shopi"からｑｋへのクリック回数とは、店舗検索ログにおいて全ユーザがｑｋをクエリとして得た検索結果に対し、"shopi"（shopiのＵＲＬ）をクリックした回数である。また、分母の"shopi"の全クリック回数とは、店舗検索ログにおいて全ユーザが"shopi"（shopiのＵＲＬ）をクリックした回数を示している。
【００３９】
図９に遷移確率の算出例を示す。上記の式において、クエリｑｋとクリック関係にある全ての店舗名"shopi" (ｉ=1，2，…，ｎ)に対して、クエリｑｋへのクリック確率を算出する。
【００４０】
ステップ１３）  店舗“shopi”の営業時間に応じた重み関数time(t)を作成する。この時間重み関数time(t)とは、当該キーワード抽出装置内でクエリｑｋが投入された時間ｔを基にクエリｑｋと店舗“shopi”を結びつける重みであり、この重みが０より大きい場合は、クエリｑｋと店舗“shopi”がtime(t)で結び付き、０の場合はクエリｑｋと店舗名は結びつかない。本実施の形態では、time(t)を店舗“shopi”の営業時間で決定している。また、このtime(t)は、全ての店舗に対して作成する。
【００４１】
図１０は、店舗"shopi"が10：00〜22：00までの営業時間の場合、営業時間内を1.0、営業時間外を2時間の幅をもって線形傾斜した台形の関数で増減させる例を示している。
【００４２】
ステップ１４）  店舗"shopi"と店舗"shopｊ"の遷移確率ｐijを、ステップ13の営業時間に応じた重み関数を用いて算出する。
【００４３】
【数２】
0005650606.tif 000003
上記の式において、pik、ｐkjは、図９に示すように、店舗"shopi"とｑｋ、店舗"shopｊ"とｑｋとのクリック回数により求まる。timeiは、店舗"shopi"の持つ時間重み関数であり、クエリｑｋが投入された時間で値が決定する。また、timejは店舗"shopｊ"のもつ時間重み関数であり、クエリｑｋが投入された時間で値が決定する。また、遷移確率pijを算出する際の総和は、店舗"shopi"とｑｋ、店舗ｑｋと"shopｊ"を結ぶ全てのクエリｑｋ（ｋ＝１，２，…，n）に対して算出する。
【００４４】
上記の店舗間の遷移確率を特徴語抽出部５に出力する。
【００４５】
店舗情報抽出部４は、店舗検索ログ抽出部２から店舗検索ログを取得すると、店舗検索ログに含まれる店舗名全てに関し、店舗情報記憶部７へ出力する。
【００４６】
特徴語抽出部５は、店舗・クエリグラフ作成部３から店舗間の遷移確率を取得し、店舗情報記憶部７から店舗情報を読み出して、各店舗ごとに遷移確率、遷移先の店舗情報から行動キーワードと営業時間をリスト化する。ここでは、店舗・クエリグラフ作成部３から図１１に示すような遷移確率と、店舗情報記憶部７から図１２のような店舗情報を取得したとき、「ネットカフェ」から遷移する「カフェ」、「ビジネスホテル」、「イタリアンカフェ」、「本屋」の店舗情報を基に、図１３に示すような特徴語のリスト（「ネットカフェ」に関する特徴語）を作成する。
【００４７】
図１３のリストを基に、時間を入力してその時間に適した特徴語として店舗の行動キーワードを抽出する。抽出する際には、下記の式を用いて行動キーワードの関連度を算出する。
【００４８】
関連度＝α遷移確率＋（1−α）timei(入力時間)
上記の式において、timei(入力時間)は図１０の重み関数を用いる。例として、α＝0.4、入力時間9:30を入力した場合、行動キーワードの「本を読む」は下記のように算出できる。
【００４９】
関連度＝0.４×0.3＋0.６×1.0＝0.72
このとき、行動キーワードの適合度の中で、「本を読む」の関連度が最も大きいため、時刻9:30を入力したときの「ネットカフェ」に最も関連する行動キーワードは「本を読む」となる。
【００５０】
また、α＝0.4、入力時間が23:00の場合は、行動キーワードの「睡眠をとる」は下記のように算出できる。
【００５１】
関連度＝0.４×0.5＋0．6×1.0＝0.8
このとき、行動キーワードの適合度の中で「睡眠をとる」の関連度が最も大きいため、時刻 23:00を入力したときの「ネットカフェ」に最も関連する行動キーワードは「睡眠」となる。
【００５２】
従来技術では、店舗検索ログを用いてグラフ解析による関連情報を抽出した場合、店舗名とクエリに時間的な繋がりを反映できないため、時間に依存しない店舗間の関連度が算出される。そのため、時間によらず「ネットカフェ」に関連する行動キーワードとして「睡眠をとる」といった行動キーワードが抽出される可能性がある。それに対し、本発明に寄れば、入力する時間に応じて関連する行動キーワードが変化し、実施の形態からわかるように、9:30を入力とすれば「本を読む」、23:00を入力とすれば「睡眠をとる」といった時間に応じた行動キーワードが抽出可能である。
【００５３】
なお、本発明は、上記の図３に示すキーワード抽出装置の構成要素の動作をプログラムとして構築し、キーワード抽出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５４】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５５】
１  店舗名入力部
２  店舗検索ログ抽出部
３  店舗・クエリグラフ作成部
４  店舗情報抽出部
５  特徴語抽出部
６  店舗検索ログ記憶部
７  店舗情報記憶部
【図１】
0005650606.tif 000004
【図２】
0005650606.tif 000005
【図３】
0005650606.tif 000006
【図４】
0005650606.tif 000007
【図５】
0005650606.tif 000008
【図６】
0005650606.tif 000009
【図７】
0005650606.tif 000010
【図８】
0005650606.tif 000011
【図９】
0005650606.tif 000012
【図１０】
0005650606.tif 000013
【図１１】
0005650606.tif 000014
【図１２】
0005650606.tif 000015
【図１３】
0005650606.tif 000016