場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラム
【課題】 個人の現在地と興味に加え、個人の空き時間に応じたパーソナライズドルートの推薦を可能とする。
【解決手段】 本発明は、複数人の行動履歴から導出される場所間の遷移しやすさを捉えるマルコフモデルに基づいて求められた確率と、個人の行動履歴に反映された個人の嗜好を捉えるトピックモデルに基づいて求められた確率の２つの確率値の２項演算を行うことで、動作主が現在地をスタート地点とした各ルートを通る確率を求め、算出した確率値をもとに、各個人毎の推薦ルートを決定する。さらに、複数の場所を含むルートの旅行時間を算出し、旅行時間に関する制約条件を満たすルートを推薦する。
【解決手段】 本発明は、複数人の行動履歴から導出される場所間の遷移しやすさを捉えるマルコフモデルに基づいて求められた確率と、個人の行動履歴に反映された個人の嗜好を捉えるトピックモデルに基づいて求められた確率の２つの確率値の２項演算を行うことで、動作主が現在地をスタート地点とした各ルートを通る確率を求め、算出した確率値をもとに、各個人毎の推薦ルートを決定する。さらに、複数の場所を含むルートの旅行時間を算出し、旅行時間に関する制約条件を満たすルートを推薦する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムに係り、特に複数人のGPS（Global Positioning System）データに元に基づいてトラベルルートを推薦するための場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
従来技術として、ＧＰＳなどの実世界における行動ログに基づく行動予測・推薦技術が存在する。例えば、位置データのログから動作主が滞在した地点を抽出し、代表地点間の遷移をマルコフモデルでモデル化することで次に訪れる地点を予測する方法がある（例えば、非特許文献１参照）。
【０００３】
また、位置データのログに基づき、動作主がある地域にどの程度詳しいか、どれくらい多くの人がその場所を訪れているかという観点で、ある地点や、地点間を結ぶルートの重要度を算出する方法がある（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D. Ashbrook and T. starner, Uing GPS to Learn Significant Locations and Predict Movement Across Multiple Users, in Personal and ubiquitous computing, Vol.7, No. 5, pp.275-286 (2003).
【非特許文献２】Y. Zheng, L. Zhang, X. Xie and W. Ma, Mining Interesting Locations and Travel Sequences from GPS Trajectories, in Proc, Int. Conf. on World Wide Web, pp. 791-800 (2009).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術は、場所間の推移をマルコフモデルでモデル化しており、過去に多くの人が辿ったルートから順に推薦する特徴がある。その結果、アートに興味のある人には美術館を、スポーツに興味のある人には野球場を優先的に推薦するといった、個人の多様な興味に応じたルートを推薦することができなかった。
【０００６】
また、従来技術は、個人の空き時間を考慮したルート推薦を行っていない。その結果、空き時間を大幅に上回る、もしくは、下回る非現実的なルートが推薦されてしまう問題が存在した。
【０００７】
本発明は、上記の点に鑑みなされたもので、個人の現在地と興味に加え、個人の空き時間に応じたパーソナライズドルートの推薦を可能とするための場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
図１は、本発明の原理構成図である。
【０００９】
本発明（請求項１）は、複数人のＧＰＳデータに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段４と、
移動履歴記憶手段４から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段７１と、
移動履歴記憶手段４から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段７２と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成手段７１とトピックモデル生成手段７２が算出した確率の二項演算で求める行動モデル生成手段７３と、を有する。
【００１０】
本発明（請求項２）は、複数人のＧＰＳデータに基づいてトラベルルートを推薦する装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成手段とトピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成手段と、を有する。
【００１１】
また、本発明（請求項３）は、請求項２のトラベルルート推薦装置に、
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出手段と、
旅行時間記憶手段を参照し、旅行時間の制約条件を満たすルートに関して、行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成手段と、を更に加えた構成である。
【００１２】
また、本発明（請求項４）は、請求項３のトラベルルート推薦装置に、
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段と、
行動ログ記憶手段からＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出手段と、
行動ログ記憶手段から代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出手段と、を更に加えた構成である。
【００１３】
図２は、本発明の原理を説明するための図である。
【００１４】
本発明（請求項５）は、複数人のＧＰＳデータに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップ（ステップ１）と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップ（ステップ２）と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成ステップとトピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップ（ステップ３）と、を行う。
【００１５】
本発明（請求項６）は、複数人のＧＰＳデータに基づいてトラベルルートを推薦する方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成ステップとトピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
行動モデル生成ステップを繰り返し実行し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成ステップと、を行う。
【００１６】
また、本発明（請求項７）は、上記の請求項６のトラベルルート推薦方法において、
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出ステップと、
旅行時間記憶手段を参照し、旅行時間の制約条件を満たすルートに関して、行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成ステップと、を更に行う。
【００１７】
また、本発明（請求項８）は、上記の請求項７のトラベルルート推薦方法において、
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段から該ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出ステップと、
行動ログ記憶手段から代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出ステップと、を更に行う。
【００１８】
本発明（請求項９）は、請求項１に記載の場所存在確率算出装置を構成する各手段としてコンピュータを機能させるための場所存在確率算出プログラムである。
【００１９】
本発明（請求項１０）は、請求項２乃至４のいずれか１項に記載のトラベルルート推薦装置を構成する各手段としてコンピュータを機能させるためのトラベルルート推薦プログラムである。
【発明の効果】
【００２０】
上記のように本発明によれば、複数人の行動履歴から導き出される場所間の遷移のしやすさを捉えるマルコフモデル、個人の行動履歴に反映された個人の嗜好を捉えるトピックモデルの二項演算による行動モデルに基づき、個人の現在地と、興味に応じたパーソナライズド推薦を実現可能である。また、時間制約を用いて個人が旅行に費やすことができる時間を考慮することで、個人の現在地と興味に加え、個人の空き時間に応じたパーソナライズドルート推薦を実現できる。
【図面の簡単な説明】
【００２１】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の第１の実施の形態におけるトラベルルート推薦装置のブロック図である。
【図４】本発明の第１の実施の形態におけるルート生成部のフローチャートである。
【図５】本発明の第１の実施の形態における行動ログ格納装置に格納されている行動ログの一例である。
【図６】本発明の第１の実施の形態における代表地点抽出部と位置情報変換部の動作例を説明するための図である。
【図７】本発明の第１の実施の形態における代表地点格納部に格納されている代表地点情報の一例である。
【図８】本発明の第１の実施の形態における移動履歴格納部に格納されている移動履歴の一例である。
【図９】本発明の第１の実施の形態における出力部からの出力例である。
【図１０】本発明の第２の実施の形態におけるトラベルルート推薦装置のブロック図である。
【図１１】本発明の第２の実施の形態における時間制約付きルート生成部のフローチャートである。
【図１２】本発明の第２の実施の形態における出力部からの出力例である。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
［第１の実施の形態］
以下、トラベルルート推薦装置の実施の形態について図面を参照して説明する。
【００２４】
図３は、本発明の第１の実施の形態におけるトラベルルート推薦装置のブロック図を示す。
【００２５】
同図に示すトラベルルート推薦装置は、移動履歴変換部２、代表地点格納部３、移動履歴格納部４、操作部５、検索部６、モデル生成部７、ルート生成部８、出力部９から構成される。このうち、操作部５、移動履歴変換部２は、外部の行動ログ格納装置１と接続されている。
【００２６】
行動ログ格納装置１は、トラベルルート推薦装置から解析され得る行動ログを格納しており、トラベルルート推薦装置からの要求に従って、行動ログを読み出し、当該情報をトラベルルート推薦装置に送信する。行動ログは、例えば、GPSデータであり、位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなる情報である。但し、行動ログは、テキストタグ情報を含まなくてもよい。いま、動作主をｕで表すと、各行動ログは、
【００２７】
【数１】
で表される。このうち、位置情報
【００２８】
【数２】
は、例えば、緯度、経度の組み合わせで表される情報であり、時間情報
【００２９】
【数３】
は、例えば、位置情報の測定時間であるが、動作主が各行動ログを取得した順序が保存できる形式であればよい。テキストタグ情報
【００３０】
【数４】
は、例えば、位置情報に関連して付与されたタグの集合であり、地名や店舗名などである。行動ログ格納装置１は、Ｗｅｂページを保持するＷｅｂサーバや、データベースを具備するデータベースサーバ等である。
【００３１】
移動履歴変換部２は、代表地点抽出部２１と、位置情報変換部２２と、代表タグ抽出部２３とを具備する。行動ログ格納装置１に格納されている動作主ｕに関する行動ログは、位置情報のシーケンスである移動履歴が
【００３２】
【数５】
で表すことができる。τ―１は、動作主ｕの全行動ログ数であり、移動履歴中の各位置情報は時間情報に基づいてソートされているものとする。移動履歴変換部２は、行動ログ格納装置１に格納されている各行動ログの位置情報に基づき、多くの人が訪れる代表地点を特定し（代表地点抽出部２１）、各代表地点を特徴的に表すテキストタグを抽出し（代表タグ抽出部２３）、更に、移動履歴ｈuに含まれるそれぞれの位置情報
【００３３】
【数６】
を、代表地点集合に含まれるいずれかの代表地点に変換する（位置情報変換部２２）。
代表地点抽出部２１は、行動ログ格納装置１に格納されている各行動ログの位置情報に基づき、多くの人々が訪れる代表地点を特定する。代表地点の特定は、最頻値探索問題を解くことに等しい。一般に、点（位置情報）の集まりがどのように分布しているかを示す関数は密度関数と呼ばれる。この密度関数は空間上の任意の位置における点の密度を表し、関数値が高いところの周辺には点がたくさん集まり、低いところにはあまり無いことを示す。代表地点抽出部２１において、最頻値探索問題の最頻値とは、この密度関数の極大値（局所的な最大値）として定義され、対応する極大値点は空間上の点の密度が局所的に最も高いところを示す。例えば、最頻値探索問題を解く手法として、ミーンシフト法（文献：Y. Cheng. Mean shift, mode seeking, and clustering. IEEE trans. Pattern Anal. And Machine Intell., 17(8), pp. 790-799 (1995)）を用いることが考えられる。代表地点抽出部２１の結果は、代表地点格納部３に格納する。
【００３４】
位置情報変換部２２は、クラスタリング手法を用いて、移動履歴ｈuに含まれるそれぞれの位置情報
【００３５】
【数７】
を代表地点抽出部２１で得られた代表地点集合に含まれるいずれかの代表地点に変換する。例えば、クラスタリング法として、ミーンシフトクラスタリング法が考えられる。ミーンシフトクラスタリング法は、ミーンシフト法の計算過程を利用し、各位置情報をその収束先の最頻値点（代表地点）でラベル付けする。この他にも、k-means法等、既存のクラスタリングアルゴリズムを適用し、各クラスタ重心を代表地点とし、各位置情報がどのクラスタに含まれたかの結果を用いて、各行動ログの位置情報をいずれかの代表地点に対応させてもよい。今後、説明の簡略化のため、変換後の位置情報も同じ記号
【００３６】
【数８】
で表現している。変換した結果、移動履歴ｈu中に連続する位置情報（代表地点）が存在する場合は、それらをまとめてひとつの位置情報として扱ってもよい。連続する位置情報をまとめた場合、動作主がその位置を訪れた時間と、出発した時間の中央値を、纏めた位置情報の新たな時間情報とする。なお、連続する位置情報は、動作主が同一の代表地点付近で複数の行動ログを残したことを意味する。位置情報変換部２２の結果は、移動履歴格納部４に格納する。
【００３７】
代表タグ抽出部２３は、行動ログ格納装置1を参照して、代表地点抽出部２１で得られた各代表地点を特徴的に表すテキストタグを抽出する。各代表地点を代表するテキストタグは、代表地点抽出部２の結果、各代表地点に対応させた行動ログ（のテキストタグ情報）集合から導き出す。例えば、テキストタグＶが、どの程度、各代表地点Ｒの内容を表すのにふさわしいかを示す代表性スコアは、以下の式で計算することができる。
【００３８】
【数９】
n(ｖ,ｒ)は、各代表地点Ｒについて、テキストタグＶを含む行動ログ数、もしくは動作主数である。ｎ（ｖ）は、行動ログ格納装置１に格納されている全データ中における、テキストタグＶを含む行動ログ数、もしくは動作主数である。この他にも、条件付き確率Ｐ（ｖ│ｒ）、リフト値Ｐ（ｖ│ｒ）／Ｐ（ｖ）、ｔｆ−ｉｄｆ値等、他の重み付け手法を用いた計算結果を代表スコアとしてもよい。各代表地点において、代表性スコアの高い上位数件のテキスト情報を、各代表地点を代表する代表タグとする。代表タグ抽出部２３は、代表地点格納部３に格納する。
【００３９】
代表地点格納部３は、代表地点抽出部２１と代表タグ抽出部２３で得られた、代表地点に関連する情報を格納する。代表地点に関する情報とは、代表地点抽出部２１で得られた代表地点を一意に識別するＩＤ、代表地点の緯度、経度、代表タグ抽出部２３で得られた代表タグからなる情報であり、移動履歴格納部３には、これらの情報が保存され、復元可能なものであればなんでもよい。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００４０】
移動履歴格納部４は、位置情報のシーケンスである動作主の移動履歴を、代表地点のシーケンスへと変換する位置情報変換部２２の結果を格納する。具体的には、移動履歴と、動作主を一意に識別するＩＤを格納する。移動履歴格納部４は、移動履歴、及び、動作主を一意に識別するＩＤが保存され、復元可能なものであればなんでもよい。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００４１】
操作部５は、行動ログ格納装置１、及び移動履歴格納部４のデータに対するユーザからの各種操作を受け付ける。各種操作とは、格納された情報を登録、修正、削除する操作等である。また、操作部５は、代表地点格納部３に格納された代表地点情報を装置のユーザに提示することも可能である。ユーザは、提示された情報の中から単一、もしくは、複数の代表地点を選択することで、推薦を行う対象となる動作主に関する行動ログ、及び、移動履歴情報として登録することが可能である。なお、複数の代表地点を選択する場合は、それらを訪れた順序情報も判別可能な形式で入力する。操作部５の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等、何でもよい。操作部５は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００４２】
検索部６は、推薦を行う対象となる動作主情報と、ルート制約条件を受け付ける。動作主情報は、動作主ｕを特定する情報である。例えば、移動履歴格納部４に格納されている動作主を一意に識別するＩＤがこれに該当するが、移動履歴格納部４に格納された移動履歴と同形式の移動履歴そのものを入力として受け付けてもよい。本装置は、同一の移動履歴を持つ複数の動作主に同様の結果を提示する。そのため、移動履歴そのものが入力の場合は、移動履歴格納部４に格納されたデータの中で、受け付けた移動履歴と同じ移動履歴を持ついずれかの動作主が指定されたものとして扱う。もし、同じ移動履歴が存在しない場合は、移動履歴格納部４の移動履歴の系列の中から、受け付けた移動履歴と類似性の高いものを選択する。類似性を測る指標としては、例えば、編集距離がある。編集距離は２つのシーケンスが与えられた場合に、一方のシーケンスをもう一方のシーケンスに変換する操作（追加、削除、置換）の最小ステップで定義されるシーケンス間の類似性を測るための指標である。「ルートの制約条件」とは、推薦して欲しいルートの個数や、単一のルートに含まる位置情報の個数である。３個以上１０個以下というように、単一のルートに含まれる位置情報の個数の範囲を指定してもよい。
【００４３】
なお、検索部６の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等、何でもよい。検索部６は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００４４】
モデル生成部７は、マルコフモデル生成部７１と、トピックモデル生成部７２と、行動モデル生成部７３とを具備する。モデル生成部７は、移動履歴格納部４の移動履歴に基づき、時間ｔ−１に位置ｒt-1にいる動作主ｕが、時間ｔに位置ｒｔを訪れる確率
【００４５】
【数１０】
を算出する。モデル生成部７は、検索部６によって指定されたｈuの（ユーザｕ）の
【００４６】
【数１１】
を算出する。
【００４７】
マルコフモデル生成部７１は、移動履歴格納部４の移動履歴に基づいて、マルコフモデルを生成する。マルコフモデルは、時系列データを扱う確率モデルとして広く用いられている。以後、説明の簡略化のため、１次マルコフモデルを用いて説明をするが、他の次数のマルコフモデルを用いてもよい。１次マルコフモデルの場合、動作主が次に訪れる位置は一つ前に訪れた位置に依存し、以下の式で計算することができる。
【００４８】
【数１２】
【００４９】
【数１３】
は、最尤推定によって以下の式で計算することができる。
【００５０】
【数１４】
【００５１】
【数１５】
は、全移動履歴中で、位置ｒt-1の後に位置ｒｔ訪れたことを示す移動履歴数である。また、n(ｒt-1)は、全移動履歴中で、ｒt-1を訪れたことを示す移動履歴数である。
【００５２】
トピックモデル生成部７２は、移動履歴格納部4の移動履歴に基づいて、トピックモデルを生成する。トピックモデルにおいては、ある動作主が訪れる各場所は、ユーザ固有のトピック比率に従ってあるトピックを選択した後、そのトピックに固有の場所出現確率分布に従って生成されると仮定して、動作主の行動を確率モデルで表現する。トピックモデルにおいては、潜在トピックｚ∈Ｚ＝｛ｚ1，…，zK｝が与えられ、hｕとｒｔが独立であると（仮定）したときに、移動履歴hｕの動作主が場所ｒｔを訪れる確率を以下の式で計算することができる。
【００５３】
【数１６】
ここで、Ｐ（ｚ|hｕ）は、動作主の興味を示しており、動作主ｕがトピックｚに興味を持つ確率である。例えば、変数ｚは、「スポーツ」や「アート」などの興味トピックを表すために用意された変数である。また、Ｐ（ｒt│ｚ）はトピックｚにおけるトレンドを表現しており、トピックｚにおいて場所ｒｔが選択される確率である。例えば、「スポーツ」というトピックからは、「野球場」や「サッカー場」などの場所が高い確率で選択される。
【００５４】
つまり、トピックモデルは、移動履歴hｕの動作主ｕが場所ｒｔを訪れた情報を学習データとし、これらの学習データが、"ある動作主が訪れる各場所は、ユーザ固有のトピック比率に従ってあるトピックｚを選択した後、そのトピックｚに固有の場所出現確率分布に従って生成された"と仮定した上で、潜在トピックｚに関するｐ（ｚ│hｕ）、Ｐ（ｒｔ│ｚ）を学習する手法である。なお、トピックｚは典型的には「スポーツ」や「アート」などのトピックを表すために用意された変数であるが、その変数が実際にどのようなトピックかを表すかは不明でよい。つまり、トピックモデルは、変数ｚに関する確率ｐ（ｚ│hｕ）、Ｐ（ｒｔ│ｚ）を学習するものである。
【００５５】
トピックモデルの代表例として、Probabilistic Latent Semantic Analysis（T. Hofmann. Probabilistic Latent Semantic Analysis , in Proc. Conf. on Uncertainty in Artificial Intelligence (UAI), pp. 289-296 (1999)）やLatent Dirichlet Allocation（D.M. Baei, A.Y. Ng, and M.I. Jordan. Latent Dirichlet Allocation, in Journal of Machine Learning Research (JMLR), vol. 3, pp. 993-1022 (2003).）などがあるが、どのモデルを用いて求めてもよい。
【００５６】
行動モデル生成部７３は、時間ｔ−1に場所ｒt-1にいる動作主ｕが、時間ｔに訪れる場所ｒtを訪れる確率P(ｒｔ|ｒt-1，hｕ)を、マルコフモデル生成部７１によって得られた結果と、トピックモデル生成部７２によって得られた結果の二項演算によって導出する。例えば、マルコフモデルとトピックモデルを組み合わせる方法としてユニグラムリスケーリング（D. Gildea and T. Hofmann. Topic-based Language Models Using EM, in Proc. EUROSPEECH, pp. 2167-2170 (1999)）がある。ユニグラムリスケーリング法は、以下の式で計算できる。
【００５７】
【数１７】
Ｐ(ｒｔ)は、位置(ｒt)を訪れる確率で、以下の式で計算することができる。
【００５８】
【数１８】
Ｎは、全移動履歴数である。Ｃ(ｒt-1，hｕ)は正規化項である。Ｐ(ｒｔ|ｒt-1)とＰ(ｒｔ|hｕ)は、それぞれ、マルコフモデル生成部７１とトピックモデル生成部７２によって導出した確率モデルである。
【００５９】
ルート生成部８は、検索部６のルート制約条件と、モデル生成部７の結果に基づいて、動作主ｕが訪れる確率の高い、動作主ｕの現在地からのルートを求める。本実施の形態におけるルート制約条件とは、推薦して欲しいルートの個数Ｋや、一つのルートに含まれる位置情報の個数Ｍ（ルート長）または個数Ｍの範囲である。である。つまり、ルート生成部８は、長さがＭで動作主ｕが訪れる確率の高いＫ個のトラベルルートを求める。例えば、ルート生成部８は、図４に示すフローチャートによって求めることができる。入力は、動作主ｕに関する移動履歴hｕ、一つのルートに含まれる位置情報の個数Ｍ（ルート長）、推薦して欲しいルートの個数Ｋである。
【００６０】
出力は、Ｋ個のルートを格納とした配列Ａである。また、ｓは訪れた位置のシーケンスであるルート、ｍsはｍに含まれる位置の個数、ｐsはｓが選択される確率、ｓlastはｓ中で最後に訪れた位置、ｓ+rは位置ｒを訪れた場合に更新されたルートである。以下、図４に従って説明する。
【００６１】
まず、以下の各値
配列Ａ←Φ；
一時変数ｋ←１；
優先度付きキューＱ←Φ；
を初期化し（ステップ１０１）、現在地
【００６２】
【数１９】
を優先度付きキューＱに追加する（ステップ１０２）。優先度付きキューＱは、取り出し操作（ポップ）によって最も優先度の高い一つの要素を返すデータ構造である。本装置においては、優先度が確率値ｐsで与えられる優先度付きキューを用いる。つまり、最も確率値の高い要素を優先度付きキューＱに返す。キューＱから最も高い確率値のルートｓを取り出し（ステップ１０４）、そのルートｓが制約条件（ルート長mｓがM）を満たすかどうかを調べる（ステップ１０５，１０７）。満たす場合は（ステップ１０５、Ｙｅｓ）、ルートsを配列Aに追加する（ステップ１０６）。もしルートｓが条件を満たさない場合は、現在地（ルートｓにおける最後の位置）から他の位置へのサブルートｓを追加した新たなルートを生成する（ステップ１０９）。同時に、生成したルートの確率値
【００６３】
【数２０】
を計算する（ステップ１０８）。上記のプロセスをＫ個のルートが配列Ａに追加させるまで繰り返す（ステップ１０３、Ｙｅｓ）。
【００６４】
出力部９は、ルート生成部８で得られたモデルに基づき、訪れる確率の高いルートから順に出力する。ここで、出力とは、ディスプレイへの表示、プリンタへの印字、音出力、外部装置への送信等を含む概念である。出力部９は、ディスプレイやスピーカ等の出力デバイスを含むと考えても含まないと考えてもよい。出力部９は、出力デバイスのドライバソフトまたは、出力デバイスのドライバソフトと出力デバイス等で実現され得る。
【００６５】
以下、具体的な例を用いて第１の実施の形態の処理について説明する。
【００６６】
図５は、本発明の第１の実施の形態における行動ログ格納装置に格納されている行動ログの一例を示す。また、図６は、本発明の一実施の形態における代表地点抽出部と位置情報変換部の動作を説明するための図であり、行動ログ格納装置1に格納される各データを位置情報（緯度、経度）に基づいて地図上にマッピングした例である。図６中の白丸で表される点は各行動ログであり、図５中の「動作主１」と「動作主２」の移動履歴はそれぞれ、黒線矢印と点線矢印で表される。
【００６７】
代表地点抽出部２１は、行動ログ格納装置1に格納される（各行動ログの）位置情報の分布に基づいて、位置情報が集中している位置（図６の『代表地点ａ』から『代表地点ｄ』）を特定する。さらに、位置情報変換部２２により、代表地点を中心とした円に含まれる各行動ログ（図６中の白丸）を各代表地点（図６中の黒丸）に対応させる。
【００６８】
図７は、本発明の第１の実施の形態における代表地点格納部に格納されている代表地点情報の一例である。同図において、代表タグ属性は、代表タグ抽出部３によって各代表地点に対して付与されたテキストタグ情報である。
【００６９】
図８は、本発明の第１の実施の形態における移動履歴格納部に格納される移動履歴の一例である。同図では、図６の黒線矢印で示される「動作主１」の移動履歴は、「代表地点ａ→代表地点ｂ→代表地点ｃ→代表地点ｄ」となる。
【００７０】
以上のように、位置情報変換部２２により、各移動履歴を代表地点からなる移動履歴に変換し、類似した移動履歴を同一の移動履歴として集約させることが可能である。
【００７１】
図９は、本発明の第１の実施の形態における出力部の出力の一例である。
【００７２】
出力部９は、訪れる確率の高いルートから順に出力する。ルートに含まれる各代表地点は、移動履歴格納部３に格納されている情報をもとに代表タグによって表されているが、緯度・経度で表される位置情報そのものを出力してもよい。指定されたルート制約条件は、ルートの個数と、ルート内に含まれる代表地点数である。図９の例においては、過去の移動履歴に、テーマパークである「東京××××ランド」が含まれている。本装置では、「テーマパークが好き」という動作主の嗜好情報をトピックモデルによって汲み取り、同じテーマパークの「ユニオンスタジオ」を優先して提示することが可能である。また、図９の出力例においては、検索部６によって指定された、推薦を行う対象となる動作主情報（移動履歴hｕ）と、受け付けたルート制約条件も出力している。
【００７３】
［第２の実施の形態］
以下に、本発明の第２の実施の形態について図面を参照して説明する。
【００７４】
図１０は、本発明の第２の実施の形態におけるトラベルルート推薦装置のブロック図である。同図において、第１の実施の形態における図３と同一構成部分には同一符号を付す。
【００７５】
同図に示すトラベルルート推薦装置は、移動履歴変換部２（代表地点抽出部２１、位置情報変換部２２、代表タグ抽出部２３）、代表地点格納部３、移動履歴格納部４、操作部５、モデル生成部７、出力部９については、第１の実施の形態と共通である。また、操作部５と移動履歴変換部２は、行動ログ格納装置１に接続されている点についても同様であるので、その説明を省略する。
【００７６】
本実施の形態では、新たに、時間制約付き検索部１０、旅行時間算出部１１、旅行時間格納部１２、時間制約付きルート生成部１４が加えられ、また、時間制約付きルート生成部１４には、外部の旅行時間格納装置１３が接続されている。以下、これらの要素について説明する。
【００７７】
時間制約付き検索部１０は、第１の実施の形態における検索部６と同様のルート制約条件に加え、時間制約をルートの制約条件として受け付ける。「時間制約」とは、例えば、推薦して欲しいルートの総旅行時間である。時間制約付き検索部１０の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等で何でもよい。時間制約付き検索部１０は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００７８】
旅行時間算出部１１は、移動履歴格納部４に格納された移動履歴情報に基づいて、任意の複数の位置を含むルートの旅行時間を算出する手段である。「旅行時間」は、場所間の移動時間であるが、一つの場所の滞在時間を旅行時間の中に含めてもよい。旅行時間の算出方法としては、例えば、平均移動時間、平均滞在時間や、移動時間分布、滞在時間分布における最頻値を旅行時間とする方法等があるが、何を用いても良い。
【００７９】
旅行時間格納部１２は、旅行時間算出部１１によって得られた任意の複数の位置を含むルートの旅行時間の結果を格納する。旅行時間格納部１２は、データの構造が保存され、復元可能なものであればなんでも良い。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００８０】
旅行時間格納装置１３は、任意の複数位置を含むルートの旅行時間を格納しており、時間制約付きルート生成部１４からの要求に従って、旅行時間情報を読み出し、当該情報を時間制約付きルート生成部１４に送信する。旅行時間格納装置１３は、カーナビゲーションサービスを提供するＷｅｂサーバや、予め登録された辞書、データベースを具備するデータベースサーバ等である。
【００８１】
時間制約付きルート生成部１４は、時間制約付き検索部１０で指定されたルート制約条件を満たす中で、動作主ｕが訪れる確率の高い現在地からのルートを求める。本実施の形態における「ルート制約条件」とは、推薦して欲しいルートの個数Ｋや、総旅行時間である。例えば、時間制約付きルート生成部１４は、最良優先探索アルゴリズムによって、図１１に示すフローチャートによって求めることができる。
【００８２】
入力は、動作主ｕに関する移動履歴ｈu、時間制約条件（時間下限ｔlowerと上限ｔupperで表される動作主の空き時間）、推薦して欲しいルートの個数Kである。出力は、K個のルートを格納した配列Ａである。また、ｓは訪れた位置のシーケンスであるルート、tｓはｓの旅行時間、ｐsはｓが選択される確率、ｓlastはｓ中で最後に訪れた単一の位置、ｓ+1は位置ｒを訪れた場合に更新されたルートである。
【００８３】
まず、以下の値
配列の初期化：Ａ←Φ；
一時変数の初期化：ｋ←１；
優先度付きキューの初期化：Ｑ←Φ；
を初期化し（ステップ２０１）、現在地
【００８４】
【数２１】
を優先度付きキューＱに追加する（ステップ２０２）。優先度付きキューＱは、取り出し操作（ポップ）によって最も優先度の高い一つの要素を返すメモリ（図示せず）内のデータ構造である。本装置においては、優先度画確率値ｐsで与えられる優先度付きキューを用いる。つまり、最も確率値の高い要素を優先度付きキューＱは返す。キューＱから最も高い確率値のルートｓを取り出し（ステップ２０４）、そのルートが時間制約条件を満たすか動かを調べる（ステップ２０５）。もし、ルートｓが条件を満たさない場合は、現在地（ルートｓにおける最後の位置）から他の位置へのサブルートをｓに追加した新たなルートを生成する（ステップ２０６）。同時に、生成したルートの確率値と旅行時間を計算する（ステップ２０８，２０９）。「TravelTime」関数は、２つの位置間の旅行時間を返す関数であり、この関数は、旅行時間格納部１２、もしくは、旅行時間格納装置１３のデータを利用することで実現し得る。上記のプロセスをＫ個のルートが配列Ａに追加されるまで繰り返す（ステップ２１０，２０３）。
【００８５】
図１２は、本発明の第２の実施の形態における出力部の出力の一例である。第１の実施の形態と同様、出力部９は、訪れる確率の高いルートから順に出力する。指定されたルート制約条件は、ルートの個数と総旅行時間である。時間制約付き検索部１０で指定された時間制約条件を考慮してルートの到達確率を計算し、ルート自身に加えてルートを辿るのにかかる時間情報（総旅行時間、場所間の旅行時間）も同時に出力する特徴がある。
【００８６】
本実施の形態のように、時間制約条件を受け付けて、当該制約条件を満たすルートを推薦することにより、空き時間を大幅に上回る、もしくは下回る非現実的なルートが推薦されることがなくなる。
【００８７】
また、上記の第1の実施の形態における図３、第２の実施の形態における図１０に示す装置の構成要素の動作をプログラムとして構築し、トラベルルート推薦装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８８】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８９】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９０】
１ 行動ログ格納装置
２ 移動履歴変換部
３ 代表地点格納部
４ 移動履歴記憶手段、移動履歴格納部
５ 操作部
６ 検索部
７ モデル生成部
８ ルート生成部
９ 出力部
１０ 時間制約付き検索部
１１ 旅行時間算出部
１２ 旅行時間格納部
１３ 旅行時間格納装置
１４ 時間制約付きルート生成部
２１ 代表地点抽出部
２２ 位置情報変換部
２３ 代表タグ抽出部
７１ マルコフモデル生成手段
７２ トピックモデル生成手段
７３ 行動モデル生成手段
【技術分野】
【０００１】
本発明は、場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムに係り、特に複数人のGPS（Global Positioning System）データに元に基づいてトラベルルートを推薦するための場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
従来技術として、ＧＰＳなどの実世界における行動ログに基づく行動予測・推薦技術が存在する。例えば、位置データのログから動作主が滞在した地点を抽出し、代表地点間の遷移をマルコフモデルでモデル化することで次に訪れる地点を予測する方法がある（例えば、非特許文献１参照）。
【０００３】
また、位置データのログに基づき、動作主がある地域にどの程度詳しいか、どれくらい多くの人がその場所を訪れているかという観点で、ある地点や、地点間を結ぶルートの重要度を算出する方法がある（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D. Ashbrook and T. starner, Uing GPS to Learn Significant Locations and Predict Movement Across Multiple Users, in Personal and ubiquitous computing, Vol.7, No. 5, pp.275-286 (2003).
【非特許文献２】Y. Zheng, L. Zhang, X. Xie and W. Ma, Mining Interesting Locations and Travel Sequences from GPS Trajectories, in Proc, Int. Conf. on World Wide Web, pp. 791-800 (2009).
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術は、場所間の推移をマルコフモデルでモデル化しており、過去に多くの人が辿ったルートから順に推薦する特徴がある。その結果、アートに興味のある人には美術館を、スポーツに興味のある人には野球場を優先的に推薦するといった、個人の多様な興味に応じたルートを推薦することができなかった。
【０００６】
また、従来技術は、個人の空き時間を考慮したルート推薦を行っていない。その結果、空き時間を大幅に上回る、もしくは、下回る非現実的なルートが推薦されてしまう問題が存在した。
【０００７】
本発明は、上記の点に鑑みなされたもので、個人の現在地と興味に加え、個人の空き時間に応じたパーソナライズドルートの推薦を可能とするための場所存在確率算出装置及び方法及びプログラム及びトラベルルート推薦装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
図１は、本発明の原理構成図である。
【０００９】
本発明（請求項１）は、複数人のＧＰＳデータに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段４と、
移動履歴記憶手段４から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段７１と、
移動履歴記憶手段４から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段７２と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成手段７１とトピックモデル生成手段７２が算出した確率の二項演算で求める行動モデル生成手段７３と、を有する。
【００１０】
本発明（請求項２）は、複数人のＧＰＳデータに基づいてトラベルルートを推薦する装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成手段とトピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成手段と、を有する。
【００１１】
また、本発明（請求項３）は、請求項２のトラベルルート推薦装置に、
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出手段と、
旅行時間記憶手段を参照し、旅行時間の制約条件を満たすルートに関して、行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成手段と、を更に加えた構成である。
【００１２】
また、本発明（請求項４）は、請求項３のトラベルルート推薦装置に、
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段と、
行動ログ記憶手段からＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出手段と、
行動ログ記憶手段から代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出手段と、を更に加えた構成である。
【００１３】
図２は、本発明の原理を説明するための図である。
【００１４】
本発明（請求項５）は、複数人のＧＰＳデータに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップ（ステップ１）と、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップ（ステップ２）と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成ステップとトピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップ（ステップ３）と、を行う。
【００１５】
本発明（請求項６）は、複数人のＧＰＳデータに基づいてトラベルルートを推薦する方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、マルコフモデル生成ステップとトピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
行動モデル生成ステップを繰り返し実行し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成ステップと、を行う。
【００１６】
また、本発明（請求項７）は、上記の請求項６のトラベルルート推薦方法において、
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出ステップと、
旅行時間記憶手段を参照し、旅行時間の制約条件を満たすルートに関して、行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成ステップと、を更に行う。
【００１７】
また、本発明（請求項８）は、上記の請求項７のトラベルルート推薦方法において、
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段から該ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出ステップと、
行動ログ記憶手段から代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出ステップと、を更に行う。
【００１８】
本発明（請求項９）は、請求項１に記載の場所存在確率算出装置を構成する各手段としてコンピュータを機能させるための場所存在確率算出プログラムである。
【００１９】
本発明（請求項１０）は、請求項２乃至４のいずれか１項に記載のトラベルルート推薦装置を構成する各手段としてコンピュータを機能させるためのトラベルルート推薦プログラムである。
【発明の効果】
【００２０】
上記のように本発明によれば、複数人の行動履歴から導き出される場所間の遷移のしやすさを捉えるマルコフモデル、個人の行動履歴に反映された個人の嗜好を捉えるトピックモデルの二項演算による行動モデルに基づき、個人の現在地と、興味に応じたパーソナライズド推薦を実現可能である。また、時間制約を用いて個人が旅行に費やすことができる時間を考慮することで、個人の現在地と興味に加え、個人の空き時間に応じたパーソナライズドルート推薦を実現できる。
【図面の簡単な説明】
【００２１】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の第１の実施の形態におけるトラベルルート推薦装置のブロック図である。
【図４】本発明の第１の実施の形態におけるルート生成部のフローチャートである。
【図５】本発明の第１の実施の形態における行動ログ格納装置に格納されている行動ログの一例である。
【図６】本発明の第１の実施の形態における代表地点抽出部と位置情報変換部の動作例を説明するための図である。
【図７】本発明の第１の実施の形態における代表地点格納部に格納されている代表地点情報の一例である。
【図８】本発明の第１の実施の形態における移動履歴格納部に格納されている移動履歴の一例である。
【図９】本発明の第１の実施の形態における出力部からの出力例である。
【図１０】本発明の第２の実施の形態におけるトラベルルート推薦装置のブロック図である。
【図１１】本発明の第２の実施の形態における時間制約付きルート生成部のフローチャートである。
【図１２】本発明の第２の実施の形態における出力部からの出力例である。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
［第１の実施の形態］
以下、トラベルルート推薦装置の実施の形態について図面を参照して説明する。
【００２４】
図３は、本発明の第１の実施の形態におけるトラベルルート推薦装置のブロック図を示す。
【００２５】
同図に示すトラベルルート推薦装置は、移動履歴変換部２、代表地点格納部３、移動履歴格納部４、操作部５、検索部６、モデル生成部７、ルート生成部８、出力部９から構成される。このうち、操作部５、移動履歴変換部２は、外部の行動ログ格納装置１と接続されている。
【００２６】
行動ログ格納装置１は、トラベルルート推薦装置から解析され得る行動ログを格納しており、トラベルルート推薦装置からの要求に従って、行動ログを読み出し、当該情報をトラベルルート推薦装置に送信する。行動ログは、例えば、GPSデータであり、位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなる情報である。但し、行動ログは、テキストタグ情報を含まなくてもよい。いま、動作主をｕで表すと、各行動ログは、
【００２７】
【数１】
で表される。このうち、位置情報
【００２８】
【数２】
は、例えば、緯度、経度の組み合わせで表される情報であり、時間情報
【００２９】
【数３】
は、例えば、位置情報の測定時間であるが、動作主が各行動ログを取得した順序が保存できる形式であればよい。テキストタグ情報
【００３０】
【数４】
は、例えば、位置情報に関連して付与されたタグの集合であり、地名や店舗名などである。行動ログ格納装置１は、Ｗｅｂページを保持するＷｅｂサーバや、データベースを具備するデータベースサーバ等である。
【００３１】
移動履歴変換部２は、代表地点抽出部２１と、位置情報変換部２２と、代表タグ抽出部２３とを具備する。行動ログ格納装置１に格納されている動作主ｕに関する行動ログは、位置情報のシーケンスである移動履歴が
【００３２】
【数５】
で表すことができる。τ―１は、動作主ｕの全行動ログ数であり、移動履歴中の各位置情報は時間情報に基づいてソートされているものとする。移動履歴変換部２は、行動ログ格納装置１に格納されている各行動ログの位置情報に基づき、多くの人が訪れる代表地点を特定し（代表地点抽出部２１）、各代表地点を特徴的に表すテキストタグを抽出し（代表タグ抽出部２３）、更に、移動履歴ｈuに含まれるそれぞれの位置情報
【００３３】
【数６】
を、代表地点集合に含まれるいずれかの代表地点に変換する（位置情報変換部２２）。
代表地点抽出部２１は、行動ログ格納装置１に格納されている各行動ログの位置情報に基づき、多くの人々が訪れる代表地点を特定する。代表地点の特定は、最頻値探索問題を解くことに等しい。一般に、点（位置情報）の集まりがどのように分布しているかを示す関数は密度関数と呼ばれる。この密度関数は空間上の任意の位置における点の密度を表し、関数値が高いところの周辺には点がたくさん集まり、低いところにはあまり無いことを示す。代表地点抽出部２１において、最頻値探索問題の最頻値とは、この密度関数の極大値（局所的な最大値）として定義され、対応する極大値点は空間上の点の密度が局所的に最も高いところを示す。例えば、最頻値探索問題を解く手法として、ミーンシフト法（文献：Y. Cheng. Mean shift, mode seeking, and clustering. IEEE trans. Pattern Anal. And Machine Intell., 17(8), pp. 790-799 (1995)）を用いることが考えられる。代表地点抽出部２１の結果は、代表地点格納部３に格納する。
【００３４】
位置情報変換部２２は、クラスタリング手法を用いて、移動履歴ｈuに含まれるそれぞれの位置情報
【００３５】
【数７】
を代表地点抽出部２１で得られた代表地点集合に含まれるいずれかの代表地点に変換する。例えば、クラスタリング法として、ミーンシフトクラスタリング法が考えられる。ミーンシフトクラスタリング法は、ミーンシフト法の計算過程を利用し、各位置情報をその収束先の最頻値点（代表地点）でラベル付けする。この他にも、k-means法等、既存のクラスタリングアルゴリズムを適用し、各クラスタ重心を代表地点とし、各位置情報がどのクラスタに含まれたかの結果を用いて、各行動ログの位置情報をいずれかの代表地点に対応させてもよい。今後、説明の簡略化のため、変換後の位置情報も同じ記号
【００３６】
【数８】
で表現している。変換した結果、移動履歴ｈu中に連続する位置情報（代表地点）が存在する場合は、それらをまとめてひとつの位置情報として扱ってもよい。連続する位置情報をまとめた場合、動作主がその位置を訪れた時間と、出発した時間の中央値を、纏めた位置情報の新たな時間情報とする。なお、連続する位置情報は、動作主が同一の代表地点付近で複数の行動ログを残したことを意味する。位置情報変換部２２の結果は、移動履歴格納部４に格納する。
【００３７】
代表タグ抽出部２３は、行動ログ格納装置1を参照して、代表地点抽出部２１で得られた各代表地点を特徴的に表すテキストタグを抽出する。各代表地点を代表するテキストタグは、代表地点抽出部２の結果、各代表地点に対応させた行動ログ（のテキストタグ情報）集合から導き出す。例えば、テキストタグＶが、どの程度、各代表地点Ｒの内容を表すのにふさわしいかを示す代表性スコアは、以下の式で計算することができる。
【００３８】
【数９】
n(ｖ,ｒ)は、各代表地点Ｒについて、テキストタグＶを含む行動ログ数、もしくは動作主数である。ｎ（ｖ）は、行動ログ格納装置１に格納されている全データ中における、テキストタグＶを含む行動ログ数、もしくは動作主数である。この他にも、条件付き確率Ｐ（ｖ│ｒ）、リフト値Ｐ（ｖ│ｒ）／Ｐ（ｖ）、ｔｆ−ｉｄｆ値等、他の重み付け手法を用いた計算結果を代表スコアとしてもよい。各代表地点において、代表性スコアの高い上位数件のテキスト情報を、各代表地点を代表する代表タグとする。代表タグ抽出部２３は、代表地点格納部３に格納する。
【００３９】
代表地点格納部３は、代表地点抽出部２１と代表タグ抽出部２３で得られた、代表地点に関連する情報を格納する。代表地点に関する情報とは、代表地点抽出部２１で得られた代表地点を一意に識別するＩＤ、代表地点の緯度、経度、代表タグ抽出部２３で得られた代表タグからなる情報であり、移動履歴格納部３には、これらの情報が保存され、復元可能なものであればなんでもよい。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００４０】
移動履歴格納部４は、位置情報のシーケンスである動作主の移動履歴を、代表地点のシーケンスへと変換する位置情報変換部２２の結果を格納する。具体的には、移動履歴と、動作主を一意に識別するＩＤを格納する。移動履歴格納部４は、移動履歴、及び、動作主を一意に識別するＩＤが保存され、復元可能なものであればなんでもよい。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００４１】
操作部５は、行動ログ格納装置１、及び移動履歴格納部４のデータに対するユーザからの各種操作を受け付ける。各種操作とは、格納された情報を登録、修正、削除する操作等である。また、操作部５は、代表地点格納部３に格納された代表地点情報を装置のユーザに提示することも可能である。ユーザは、提示された情報の中から単一、もしくは、複数の代表地点を選択することで、推薦を行う対象となる動作主に関する行動ログ、及び、移動履歴情報として登録することが可能である。なお、複数の代表地点を選択する場合は、それらを訪れた順序情報も判別可能な形式で入力する。操作部５の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等、何でもよい。操作部５は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００４２】
検索部６は、推薦を行う対象となる動作主情報と、ルート制約条件を受け付ける。動作主情報は、動作主ｕを特定する情報である。例えば、移動履歴格納部４に格納されている動作主を一意に識別するＩＤがこれに該当するが、移動履歴格納部４に格納された移動履歴と同形式の移動履歴そのものを入力として受け付けてもよい。本装置は、同一の移動履歴を持つ複数の動作主に同様の結果を提示する。そのため、移動履歴そのものが入力の場合は、移動履歴格納部４に格納されたデータの中で、受け付けた移動履歴と同じ移動履歴を持ついずれかの動作主が指定されたものとして扱う。もし、同じ移動履歴が存在しない場合は、移動履歴格納部４の移動履歴の系列の中から、受け付けた移動履歴と類似性の高いものを選択する。類似性を測る指標としては、例えば、編集距離がある。編集距離は２つのシーケンスが与えられた場合に、一方のシーケンスをもう一方のシーケンスに変換する操作（追加、削除、置換）の最小ステップで定義されるシーケンス間の類似性を測るための指標である。「ルートの制約条件」とは、推薦して欲しいルートの個数や、単一のルートに含まる位置情報の個数である。３個以上１０個以下というように、単一のルートに含まれる位置情報の個数の範囲を指定してもよい。
【００４３】
なお、検索部６の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等、何でもよい。検索部６は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００４４】
モデル生成部７は、マルコフモデル生成部７１と、トピックモデル生成部７２と、行動モデル生成部７３とを具備する。モデル生成部７は、移動履歴格納部４の移動履歴に基づき、時間ｔ−１に位置ｒt-1にいる動作主ｕが、時間ｔに位置ｒｔを訪れる確率
【００４５】
【数１０】
を算出する。モデル生成部７は、検索部６によって指定されたｈuの（ユーザｕ）の
【００４６】
【数１１】
を算出する。
【００４７】
マルコフモデル生成部７１は、移動履歴格納部４の移動履歴に基づいて、マルコフモデルを生成する。マルコフモデルは、時系列データを扱う確率モデルとして広く用いられている。以後、説明の簡略化のため、１次マルコフモデルを用いて説明をするが、他の次数のマルコフモデルを用いてもよい。１次マルコフモデルの場合、動作主が次に訪れる位置は一つ前に訪れた位置に依存し、以下の式で計算することができる。
【００４８】
【数１２】
【００４９】
【数１３】
は、最尤推定によって以下の式で計算することができる。
【００５０】
【数１４】
【００５１】
【数１５】
は、全移動履歴中で、位置ｒt-1の後に位置ｒｔ訪れたことを示す移動履歴数である。また、n(ｒt-1)は、全移動履歴中で、ｒt-1を訪れたことを示す移動履歴数である。
【００５２】
トピックモデル生成部７２は、移動履歴格納部4の移動履歴に基づいて、トピックモデルを生成する。トピックモデルにおいては、ある動作主が訪れる各場所は、ユーザ固有のトピック比率に従ってあるトピックを選択した後、そのトピックに固有の場所出現確率分布に従って生成されると仮定して、動作主の行動を確率モデルで表現する。トピックモデルにおいては、潜在トピックｚ∈Ｚ＝｛ｚ1，…，zK｝が与えられ、hｕとｒｔが独立であると（仮定）したときに、移動履歴hｕの動作主が場所ｒｔを訪れる確率を以下の式で計算することができる。
【００５３】
【数１６】
ここで、Ｐ（ｚ|hｕ）は、動作主の興味を示しており、動作主ｕがトピックｚに興味を持つ確率である。例えば、変数ｚは、「スポーツ」や「アート」などの興味トピックを表すために用意された変数である。また、Ｐ（ｒt│ｚ）はトピックｚにおけるトレンドを表現しており、トピックｚにおいて場所ｒｔが選択される確率である。例えば、「スポーツ」というトピックからは、「野球場」や「サッカー場」などの場所が高い確率で選択される。
【００５４】
つまり、トピックモデルは、移動履歴hｕの動作主ｕが場所ｒｔを訪れた情報を学習データとし、これらの学習データが、"ある動作主が訪れる各場所は、ユーザ固有のトピック比率に従ってあるトピックｚを選択した後、そのトピックｚに固有の場所出現確率分布に従って生成された"と仮定した上で、潜在トピックｚに関するｐ（ｚ│hｕ）、Ｐ（ｒｔ│ｚ）を学習する手法である。なお、トピックｚは典型的には「スポーツ」や「アート」などのトピックを表すために用意された変数であるが、その変数が実際にどのようなトピックかを表すかは不明でよい。つまり、トピックモデルは、変数ｚに関する確率ｐ（ｚ│hｕ）、Ｐ（ｒｔ│ｚ）を学習するものである。
【００５５】
トピックモデルの代表例として、Probabilistic Latent Semantic Analysis（T. Hofmann. Probabilistic Latent Semantic Analysis , in Proc. Conf. on Uncertainty in Artificial Intelligence (UAI), pp. 289-296 (1999)）やLatent Dirichlet Allocation（D.M. Baei, A.Y. Ng, and M.I. Jordan. Latent Dirichlet Allocation, in Journal of Machine Learning Research (JMLR), vol. 3, pp. 993-1022 (2003).）などがあるが、どのモデルを用いて求めてもよい。
【００５６】
行動モデル生成部７３は、時間ｔ−1に場所ｒt-1にいる動作主ｕが、時間ｔに訪れる場所ｒtを訪れる確率P(ｒｔ|ｒt-1，hｕ)を、マルコフモデル生成部７１によって得られた結果と、トピックモデル生成部７２によって得られた結果の二項演算によって導出する。例えば、マルコフモデルとトピックモデルを組み合わせる方法としてユニグラムリスケーリング（D. Gildea and T. Hofmann. Topic-based Language Models Using EM, in Proc. EUROSPEECH, pp. 2167-2170 (1999)）がある。ユニグラムリスケーリング法は、以下の式で計算できる。
【００５７】
【数１７】
Ｐ(ｒｔ)は、位置(ｒt)を訪れる確率で、以下の式で計算することができる。
【００５８】
【数１８】
Ｎは、全移動履歴数である。Ｃ(ｒt-1，hｕ)は正規化項である。Ｐ(ｒｔ|ｒt-1)とＰ(ｒｔ|hｕ)は、それぞれ、マルコフモデル生成部７１とトピックモデル生成部７２によって導出した確率モデルである。
【００５９】
ルート生成部８は、検索部６のルート制約条件と、モデル生成部７の結果に基づいて、動作主ｕが訪れる確率の高い、動作主ｕの現在地からのルートを求める。本実施の形態におけるルート制約条件とは、推薦して欲しいルートの個数Ｋや、一つのルートに含まれる位置情報の個数Ｍ（ルート長）または個数Ｍの範囲である。である。つまり、ルート生成部８は、長さがＭで動作主ｕが訪れる確率の高いＫ個のトラベルルートを求める。例えば、ルート生成部８は、図４に示すフローチャートによって求めることができる。入力は、動作主ｕに関する移動履歴hｕ、一つのルートに含まれる位置情報の個数Ｍ（ルート長）、推薦して欲しいルートの個数Ｋである。
【００６０】
出力は、Ｋ個のルートを格納とした配列Ａである。また、ｓは訪れた位置のシーケンスであるルート、ｍsはｍに含まれる位置の個数、ｐsはｓが選択される確率、ｓlastはｓ中で最後に訪れた位置、ｓ+rは位置ｒを訪れた場合に更新されたルートである。以下、図４に従って説明する。
【００６１】
まず、以下の各値
配列Ａ←Φ；
一時変数ｋ←１；
優先度付きキューＱ←Φ；
を初期化し（ステップ１０１）、現在地
【００６２】
【数１９】
を優先度付きキューＱに追加する（ステップ１０２）。優先度付きキューＱは、取り出し操作（ポップ）によって最も優先度の高い一つの要素を返すデータ構造である。本装置においては、優先度が確率値ｐsで与えられる優先度付きキューを用いる。つまり、最も確率値の高い要素を優先度付きキューＱに返す。キューＱから最も高い確率値のルートｓを取り出し（ステップ１０４）、そのルートｓが制約条件（ルート長mｓがM）を満たすかどうかを調べる（ステップ１０５，１０７）。満たす場合は（ステップ１０５、Ｙｅｓ）、ルートsを配列Aに追加する（ステップ１０６）。もしルートｓが条件を満たさない場合は、現在地（ルートｓにおける最後の位置）から他の位置へのサブルートｓを追加した新たなルートを生成する（ステップ１０９）。同時に、生成したルートの確率値
【００６３】
【数２０】
を計算する（ステップ１０８）。上記のプロセスをＫ個のルートが配列Ａに追加させるまで繰り返す（ステップ１０３、Ｙｅｓ）。
【００６４】
出力部９は、ルート生成部８で得られたモデルに基づき、訪れる確率の高いルートから順に出力する。ここで、出力とは、ディスプレイへの表示、プリンタへの印字、音出力、外部装置への送信等を含む概念である。出力部９は、ディスプレイやスピーカ等の出力デバイスを含むと考えても含まないと考えてもよい。出力部９は、出力デバイスのドライバソフトまたは、出力デバイスのドライバソフトと出力デバイス等で実現され得る。
【００６５】
以下、具体的な例を用いて第１の実施の形態の処理について説明する。
【００６６】
図５は、本発明の第１の実施の形態における行動ログ格納装置に格納されている行動ログの一例を示す。また、図６は、本発明の一実施の形態における代表地点抽出部と位置情報変換部の動作を説明するための図であり、行動ログ格納装置1に格納される各データを位置情報（緯度、経度）に基づいて地図上にマッピングした例である。図６中の白丸で表される点は各行動ログであり、図５中の「動作主１」と「動作主２」の移動履歴はそれぞれ、黒線矢印と点線矢印で表される。
【００６７】
代表地点抽出部２１は、行動ログ格納装置1に格納される（各行動ログの）位置情報の分布に基づいて、位置情報が集中している位置（図６の『代表地点ａ』から『代表地点ｄ』）を特定する。さらに、位置情報変換部２２により、代表地点を中心とした円に含まれる各行動ログ（図６中の白丸）を各代表地点（図６中の黒丸）に対応させる。
【００６８】
図７は、本発明の第１の実施の形態における代表地点格納部に格納されている代表地点情報の一例である。同図において、代表タグ属性は、代表タグ抽出部３によって各代表地点に対して付与されたテキストタグ情報である。
【００６９】
図８は、本発明の第１の実施の形態における移動履歴格納部に格納される移動履歴の一例である。同図では、図６の黒線矢印で示される「動作主１」の移動履歴は、「代表地点ａ→代表地点ｂ→代表地点ｃ→代表地点ｄ」となる。
【００７０】
以上のように、位置情報変換部２２により、各移動履歴を代表地点からなる移動履歴に変換し、類似した移動履歴を同一の移動履歴として集約させることが可能である。
【００７１】
図９は、本発明の第１の実施の形態における出力部の出力の一例である。
【００７２】
出力部９は、訪れる確率の高いルートから順に出力する。ルートに含まれる各代表地点は、移動履歴格納部３に格納されている情報をもとに代表タグによって表されているが、緯度・経度で表される位置情報そのものを出力してもよい。指定されたルート制約条件は、ルートの個数と、ルート内に含まれる代表地点数である。図９の例においては、過去の移動履歴に、テーマパークである「東京××××ランド」が含まれている。本装置では、「テーマパークが好き」という動作主の嗜好情報をトピックモデルによって汲み取り、同じテーマパークの「ユニオンスタジオ」を優先して提示することが可能である。また、図９の出力例においては、検索部６によって指定された、推薦を行う対象となる動作主情報（移動履歴hｕ）と、受け付けたルート制約条件も出力している。
【００７３】
［第２の実施の形態］
以下に、本発明の第２の実施の形態について図面を参照して説明する。
【００７４】
図１０は、本発明の第２の実施の形態におけるトラベルルート推薦装置のブロック図である。同図において、第１の実施の形態における図３と同一構成部分には同一符号を付す。
【００７５】
同図に示すトラベルルート推薦装置は、移動履歴変換部２（代表地点抽出部２１、位置情報変換部２２、代表タグ抽出部２３）、代表地点格納部３、移動履歴格納部４、操作部５、モデル生成部７、出力部９については、第１の実施の形態と共通である。また、操作部５と移動履歴変換部２は、行動ログ格納装置１に接続されている点についても同様であるので、その説明を省略する。
【００７６】
本実施の形態では、新たに、時間制約付き検索部１０、旅行時間算出部１１、旅行時間格納部１２、時間制約付きルート生成部１４が加えられ、また、時間制約付きルート生成部１４には、外部の旅行時間格納装置１３が接続されている。以下、これらの要素について説明する。
【００７７】
時間制約付き検索部１０は、第１の実施の形態における検索部６と同様のルート制約条件に加え、時間制約をルートの制約条件として受け付ける。「時間制約」とは、例えば、推薦して欲しいルートの総旅行時間である。時間制約付き検索部１０の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等で何でもよい。時間制約付き検索部１０は、マウス等の入力手段のデバイスドライバや、メニュー画面の制御ソフトウェアで実現され得る。
【００７８】
旅行時間算出部１１は、移動履歴格納部４に格納された移動履歴情報に基づいて、任意の複数の位置を含むルートの旅行時間を算出する手段である。「旅行時間」は、場所間の移動時間であるが、一つの場所の滞在時間を旅行時間の中に含めてもよい。旅行時間の算出方法としては、例えば、平均移動時間、平均滞在時間や、移動時間分布、滞在時間分布における最頻値を旅行時間とする方法等があるが、何を用いても良い。
【００７９】
旅行時間格納部１２は、旅行時間算出部１１によって得られた任意の複数の位置を含むルートの旅行時間の結果を格納する。旅行時間格納部１２は、データの構造が保存され、復元可能なものであればなんでも良い。例えば、データベースや、予め備えられた汎用的な記憶装置（メモリやハードディスク装置）の特定領域に記憶される。
【００８０】
旅行時間格納装置１３は、任意の複数位置を含むルートの旅行時間を格納しており、時間制約付きルート生成部１４からの要求に従って、旅行時間情報を読み出し、当該情報を時間制約付きルート生成部１４に送信する。旅行時間格納装置１３は、カーナビゲーションサービスを提供するＷｅｂサーバや、予め登録された辞書、データベースを具備するデータベースサーバ等である。
【００８１】
時間制約付きルート生成部１４は、時間制約付き検索部１０で指定されたルート制約条件を満たす中で、動作主ｕが訪れる確率の高い現在地からのルートを求める。本実施の形態における「ルート制約条件」とは、推薦して欲しいルートの個数Ｋや、総旅行時間である。例えば、時間制約付きルート生成部１４は、最良優先探索アルゴリズムによって、図１１に示すフローチャートによって求めることができる。
【００８２】
入力は、動作主ｕに関する移動履歴ｈu、時間制約条件（時間下限ｔlowerと上限ｔupperで表される動作主の空き時間）、推薦して欲しいルートの個数Kである。出力は、K個のルートを格納した配列Ａである。また、ｓは訪れた位置のシーケンスであるルート、tｓはｓの旅行時間、ｐsはｓが選択される確率、ｓlastはｓ中で最後に訪れた単一の位置、ｓ+1は位置ｒを訪れた場合に更新されたルートである。
【００８３】
まず、以下の値
配列の初期化：Ａ←Φ；
一時変数の初期化：ｋ←１；
優先度付きキューの初期化：Ｑ←Φ；
を初期化し（ステップ２０１）、現在地
【００８４】
【数２１】
を優先度付きキューＱに追加する（ステップ２０２）。優先度付きキューＱは、取り出し操作（ポップ）によって最も優先度の高い一つの要素を返すメモリ（図示せず）内のデータ構造である。本装置においては、優先度画確率値ｐsで与えられる優先度付きキューを用いる。つまり、最も確率値の高い要素を優先度付きキューＱは返す。キューＱから最も高い確率値のルートｓを取り出し（ステップ２０４）、そのルートが時間制約条件を満たすか動かを調べる（ステップ２０５）。もし、ルートｓが条件を満たさない場合は、現在地（ルートｓにおける最後の位置）から他の位置へのサブルートをｓに追加した新たなルートを生成する（ステップ２０６）。同時に、生成したルートの確率値と旅行時間を計算する（ステップ２０８，２０９）。「TravelTime」関数は、２つの位置間の旅行時間を返す関数であり、この関数は、旅行時間格納部１２、もしくは、旅行時間格納装置１３のデータを利用することで実現し得る。上記のプロセスをＫ個のルートが配列Ａに追加されるまで繰り返す（ステップ２１０，２０３）。
【００８５】
図１２は、本発明の第２の実施の形態における出力部の出力の一例である。第１の実施の形態と同様、出力部９は、訪れる確率の高いルートから順に出力する。指定されたルート制約条件は、ルートの個数と総旅行時間である。時間制約付き検索部１０で指定された時間制約条件を考慮してルートの到達確率を計算し、ルート自身に加えてルートを辿るのにかかる時間情報（総旅行時間、場所間の旅行時間）も同時に出力する特徴がある。
【００８６】
本実施の形態のように、時間制約条件を受け付けて、当該制約条件を満たすルートを推薦することにより、空き時間を大幅に上回る、もしくは下回る非現実的なルートが推薦されることがなくなる。
【００８７】
また、上記の第1の実施の形態における図３、第２の実施の形態における図１０に示す装置の構成要素の動作をプログラムとして構築し、トラベルルート推薦装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８８】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８９】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００９０】
１ 行動ログ格納装置
２ 移動履歴変換部
３ 代表地点格納部
４ 移動履歴記憶手段、移動履歴格納部
５ 操作部
６ 検索部
７ モデル生成部
８ ルート生成部
９ 出力部
１０ 時間制約付き検索部
１１ 旅行時間算出部
１２ 旅行時間格納部
１３ 旅行時間格納装置
１４ 時間制約付きルート生成部
２１ 代表地点抽出部
２２ 位置情報変換部
２３ 代表タグ抽出部
７１ マルコフモデル生成手段
７２ トピックモデル生成手段
７３ 行動モデル生成手段
【特許請求の範囲】
【請求項１】
複数人のＧＰＳ（Global Positioning System）データに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成手段と前記トピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
を有することを特徴とする場所存在確率算出装置。
【請求項２】
複数人のＧＰＳデータに基づいてトラベルルートを推薦する装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成手段と前記トピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成手段と、
を有することを特徴とするトラベルルート推薦装置。
【請求項３】
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出手段と、
前記旅行時間記憶手段を参照し、前記旅行時間の制約条件を満たすルートに関して、前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成手段と、
を更に有する請求項２記載のトラベルルート推薦装置。
【請求項４】
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段と、
前記行動ログ記憶手段から前記ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出手段と、
前記行動ログ記憶手段から前記代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出手段と、
を更に有する請求項３記載のトラベルルート推薦装置。
【請求項５】
複数人のＧＰＳ（Global Positioning System）データに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成ステップと前記トピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
を行うことを特徴とする場所存在確率算出方法。
【請求項６】
複数人のＧＰＳデータに基づいてトラベルルートを推薦する方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成ステップと前記トピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
前記行動モデル生成ステップを繰り返し実行し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成ステップと、
を行うことを特徴とするトラベルルート推薦方法。
【請求項７】
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出ステップと、
前記旅行時間記憶手段を参照し、前記旅行時間の制約条件を満たすルートに関して、前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成ステップと、
を更に行う請求項６記載のトラベルルート推薦方法。
【請求項８】
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段から該ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出ステップと、
前記行動ログ記憶手段から前記代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出ステップと、
を更に行う請求項７記載のトラベルルート推薦方法。
【請求項９】
請求項１に記載の場所存在確率算出装置を構成する各手段としてコンピュータを機能させるための場所存在確率算出プログラム。
【請求項１０】
請求項２乃至４のいずれか１項に記載のトラベルルート推薦装置を構成する各手段としてコンピュータを機能させるためのトラベルルート推薦プログラム。
【請求項１】
複数人のＧＰＳ（Global Positioning System）データに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成手段と前記トピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
を有することを特徴とする場所存在確率算出装置。
【請求項２】
複数人のＧＰＳデータに基づいてトラベルルートを推薦する装置であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段と、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成手段と、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成手段と、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成手段と前記トピックモデル生成手段が算出した確率の二項演算で求める行動モデル生成手段と、
前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成手段と、
を有することを特徴とするトラベルルート推薦装置。
【請求項３】
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出手段と、
前記旅行時間記憶手段を参照し、前記旅行時間の制約条件を満たすルートに関して、前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成手段と、
を更に有する請求項２記載のトラベルルート推薦装置。
【請求項４】
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段と、
前記行動ログ記憶手段から前記ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出手段と、
前記行動ログ記憶手段から前記代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出手段と、
を更に有する請求項３記載のトラベルルート推薦装置。
【請求項５】
複数人のＧＰＳ（Global Positioning System）データに基づいて動作主が次に各場所に存在する確率を算出するための場所存在確率算出方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成ステップと前記トピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
を行うことを特徴とする場所存在確率算出方法。
【請求項６】
複数人のＧＰＳデータに基づいてトラベルルートを推薦する方法であって、
動作主の位置情報のシーケンスである移動履歴を格納した移動履歴記憶手段を有するコンピュータが、
前記移動履歴記憶手段から動作主の移動履歴を取得して、ある場所を訪れる確率をマルコフモデルに基づいて算出するマルコフモデル生成ステップと、
前記移動履歴記憶手段から前記動作主の移動履歴を取得して、ある場所を訪れる確率をトピックモデルに基づいて算出するトピックモデル生成ステップと、
ある移動履歴を持つ動作主がある場所を訪れる確率を、前記マルコフモデル生成ステップと前記トピックモデル生成ステップで算出された確率の二項演算で求める行動モデル生成ステップと、
前記行動モデル生成ステップを繰り返し実行し、ある移動履歴を持つ動作主があるルートを通る確率を求めるルート生成ステップと、
を行うことを特徴とするトラベルルート推薦方法。
【請求項７】
複数人の移動履歴情報の集計結果に基づいて、複数の場所を含むルートの旅行時間を算出し、旅行時間記憶手段に格納する旅行時間算出ステップと、
前記旅行時間記憶手段を参照し、前記旅行時間の制約条件を満たすルートに関して、前記行動モデル生成手段を繰り返し適用し、ある移動履歴を持つ動作主があるルートを通る確率を求める時間制約付きルート生成ステップと、
を更に行う請求項６記載のトラベルルート推薦方法。
【請求項８】
複数人の位置情報、時間情報、テキストタグ情報、動作主を一意に識別する動作主情報とからなるＧＰＳデータを格納した行動ログ記憶手段から該ＧＰＳデータを取得して、多くの人々が訪れる代表地点を特定し、各ＧＰＳデータを該代表地点のいずれかに変換する代表地点抽出ステップと、
前記行動ログ記憶手段から前記代表地点を特徴的に表すテキストタグ情報を抽出する代表タグ抽出ステップと、
を更に行う請求項７記載のトラベルルート推薦方法。
【請求項９】
請求項１に記載の場所存在確率算出装置を構成する各手段としてコンピュータを機能させるための場所存在確率算出プログラム。
【請求項１０】
請求項２乃至４のいずれか１項に記載のトラベルルート推薦装置を構成する各手段としてコンピュータを機能させるためのトラベルルート推薦プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−１７０４５３（Ｐ２０１１−１７０４５３Ａ）
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願番号】特願２０１０−３１６２０（Ｐ２０１０−３１６２０）
【出願日】平成２２年２月１６日（２０１０．２．１６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年９月１日（２０１１．９．１）
【国際特許分類】
【出願日】平成２２年２月１６日（２０１０．２．１６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]