(57)【特許請求の範囲】
【請求項１】
グリッドＩＤの系列から移動経路を予測するＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）モデルのパラメータを記憶する目的地予測モデルパラメータデータベースと、
空間的位置を示す測位データの系列から、空間的位置を分割して得られる分割領域であるグリッドを示すグリッドＩＤの系列を抽出するグリッドＩＤ抽出部と、
前記目的地予測モデルパラメータデータベースから前記ＲＮＮモデルのパラメータを取得して前記ＲＮＮモデルを構築し、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって各々の目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測する目的地予測部と、
を備えた目的地予測装置。
【請求項２】
前記測位データの系列の履歴から抽出されたグリッドＩＤの系列から前記ＲＮＮモデルを学習し、学習した前記ＲＮＮモデルのパラメータを前記目的地予測モデルパラメータデータベースに記憶させる目的地予測モデル学習部を更に備えた
請求項１記載の目的地予測装置。
【請求項３】
前記目的地予測部は、前記サンプリングシミュレーションにおいて、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列に基づき、前記ＲＮＮモデルを用いて、前記測位データの系列の最終点に対応するグリッドから各グリッドへの遷移確率、及び状態ベクトルを算出し、
算出した前記遷移確率をグリッド間の距離に応じた重みによって補正し、補正した前記遷移確率に基づき、次のステップに移動するグリッドをサンプリングし、前記遷移確率と前記状態ベクトルとを前記ＲＮＮモデルに入力して前記次のステップにおける前記遷移確率及び前記状態ベクトルを算出することを繰り返す
請求項１又は２記載の目的地予測装置。
【請求項４】
前記目的地予測部は、前記遷移確率を補正する際に、前記遷移確率を、グリッド間の距離に応じた重みと前記遷移確率とのアダマール積を用いて補正する
請求項３記載の目的地予測装置。
【請求項５】
前記目的地予測部は、前記測位データの系列の履歴における各系列の最終点の空間的位置を前記目的地候補として、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測する
請求項１〜４の何れか１項記載の目的地予測装置。
【請求項６】
グリッドＩＤ抽出部、及び目的地予測部を備えた目的地予測装置が行う目的地予測方法であって、
前記グリッドＩＤ抽出部が、空間的位置を示す測位データの系列から、空間的位置を分割して得られる分割領域であるグリッドを示すグリッドＩＤの系列を抽出するステップと、
前記目的地予測部が、グリッドＩＤの系列から移動経路を予測するＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）モデルのパラメータを記憶する目的地予測モデルパラメータデータベースから前記ＲＮＮモデルのパラメータを取得して前記ＲＮＮモデルを構築し、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって各々の目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測するステップと、
を有する目的地予測方法。
【請求項７】
グリッドＩＤ抽出部、目的地予測モデル学習部、及び目的地予測部を備えた目的地予測装置が行う請求項６記載の目的地予測方法であって、
前記目的地予測モデル学習部が、前記測位データの系列の履歴から抽出されたグリッドＩＤの系列から前記ＲＮＮモデルを学習し、学習した前記ＲＮＮモデルのパラメータを前記目的地予測モデルパラメータデータベースに記憶させるステップを更に有する
請求項６記載の目的地予測方法。
【請求項８】
コンピュータを、請求項１〜５の何れか１項記載の目的地予測装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地予測装置、目的地予測方法、及び目的地予測プログラムに係り、特に、観測された位置情報の系列である測位データから、ユーザの次の目的地を精度良く推定することを実現するための目的地予測装置、目的地予測方法、及び目的地予測プログラムに関する。
【背景技術】
【０００２】
ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）、Ｗｉ−Ｆｉチップ等の測位機能が搭載された携帯電話、スマートフォン等の携帯端末の普及によって、ユーザの位置を測位した測位データを容易に取得できるようになった。そこで、過去から現在までの測位データを用いて、ユーザの目的地を予測することができれば、予測結果に応じた情報推薦、生活支援等の幅広いサービスに応用可能である。
【０００３】
上記測位データを用いてユーザの目的地を予測する従来の方法として、系列マイニングを用いた方法が知られている。この系列マイニングを用いた方法では、例えば、まずユーザが携帯する携帯端末によるＧＰＳの測位データから、マイニング処理によってユーザの滞在地域を抽出する。さらに、複数の滞在地域間の遷移行動をマルコフモデルとして表現して遷移確率を計算することにより、ある場所に滞在しているユーザが次に滞在するであろう滞在地域である目的地を予測するものである（例えば、非特許文献１や非特許文献２を参照。）
【０００４】
上述した従来の方法では、滞在地間の遷移行動を一次マルコフモデル等の短期的な状態の依存性を考慮したモデルに基づいて目的地を予測していた。一方、長期的な状態の依存性を考慮することで、より小さな誤差で目的地を予測することが期待される。
【０００５】
長期的な状態の依存性を考慮した効率的な目的地予測の方法として、測位データの系列を離散的なグリッド空間で表現し、グリッド間の遷移をＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）を用いてモデリングし、ＲＮＮモデルから得られる遷移確率に基づいて目的地を予測する方法が考えられる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Andy Yuan Xue, Rui Zhang, Yu Zheng, Xing Xie, Jin Huang, Zhenghua Xu, "Destination prediction by sub-trajectory synthesis and privacy protection against such prediction", In Proc. of ICDE’13, pp.254-265 (2013).
【非特許文献２】Andy Yuan Xue, Jianzhong Qi, Xing Xie, Rui Zhang, Jin Huang, Yuan Li, "Solving the data sparsity problem in destination prediction", VLDB J.24(2), pp.219-243 (2015).
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところが、上述したＲＮＮモデルを用いた方法では、離散化されたグリッド間の遷移をモデリングする際に、グリッド間の空間的な近接性が考慮されていない。そのため、モデルが物理的には起こり得ない空間的に大きく離れた遷移を予測してしまうことがあり、これが予測誤差を悪化させてしまうという問題があった。
【０００８】
本発明は、以上のような事情に鑑みてなされたものであり、ユーザの目的地を空間的な近接性を考慮しつつ精度良く予測することができる目的地予測装置、目的地予測方法、及び目的地予測プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明の目的地予測装置は、グリッドＩＤの系列から移動経路を予測するＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）モデルのパラメータを記憶する目的地予測モデルパラメータデータベースと、空間的位置を示す測位データの系列から、空間的位置を分割して得られる分割領域であるグリッドを示すグリッドＩＤの系列を抽出するグリッドＩＤ抽出部と、前記目的地予測モデルパラメータデータベースから前記ＲＮＮモデルのパラメータを取得して前記ＲＮＮモデルを構築し、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって各々の目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測する目的地予測部と、を備える。
【００１０】
前記測位データの系列の履歴から抽出されたグリッドＩＤの系列から前記ＲＮＮモデルを学習し、学習した前記ＲＮＮモデルのパラメータを前記目的地予測モデルパラメータデータベースに記憶させる目的地予測モデル学習部を更に備えるようにしても良い。
【００１１】
また、前記目的地予測部は、前記サンプリングシミュレーションにおいて、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列に基づき、前記ＲＮＮモデルを用いて、前記測位データの系列の最終点に対応するグリッドから各グリッドへの遷移確率、及び状態ベクトルを算出し、算出した前記遷移確率をグリッド間の距離に応じた重みによって補正し、補正した前記遷移確率に基づき、次のステップに移動するグリッドをサンプリングし、前記遷移確率と前記状態ベクトルとを前記ＲＮＮモデルに入力して前記次のステップにおける前記遷移確率及び前記状態ベクトルを算出することを繰り返すようにしても良い。
【００１２】
また、前記目的地予測部は、前記遷移確率を補正する際に、前記遷移確率を、グリッド間の距離に応じた重みと前記遷移確率とのアダマール積を用いて補正するようにしても良い。
【００１３】
また、前記目的地予測部は、前記測位データの系列の履歴における各系列の最終点の空間的位置を前記目的地候補として、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測するようにしても良い。
【００１４】
上記目的を達成するために、本発明の目的地予測方法は、グリッドＩＤ抽出部、及び目的地予測部を備えた目的地予測装置が行う目的地予測方法であって、前記グリッドＩＤ抽出部が、空間的位置を示す測位データの系列から、空間的位置を分割して得られる分割領域であるグリッドを示すグリッドＩＤの系列を抽出するステップと、前記目的地予測部が、グリッドＩＤの系列から移動経路を予測するＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）モデルのパラメータを記憶する目的地予測モデルパラメータデータベースから前記ＲＮＮモデルのパラメータを取得して前記ＲＮＮモデルを構築し、前記グリッドＩＤ抽出部により抽出された前記グリッドＩＤの系列から前記ＲＮＮモデル、及びグリッド間の距離を用いたサンプリングシミュレーションによって各々の目的地候補への訪問可能性を算出し、算出した各々の目的地候補への訪問可能性に基づき目的地を予測するステップと、を有する。
【００１５】
なお、グリッドＩＤ抽出部、目的地予測モデル学習部、及び目的地予測部を備えた目的地予測装置が行う目的地予測方法であって、前記目的地予測モデル学習部が、前記測位データの系列の履歴から抽出されたグリッドＩＤの系列から前記ＲＮＮモデルを学習し、学習した前記ＲＮＮモデルのパラメータを前記目的地予測モデルパラメータデータベースに記憶させるステップを更に有するようにしても良い。
【００１６】
上記目的を達成するために、本発明の目的地予測プログラムは、コンピュータを、本発明の目的地予測装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明によれば、ユーザの目的地を空間的な近接性を考慮しつつ精度良く予測することが可能となる。
【図面の簡単な説明】
【００１８】
【図１】実施形態に係る目的地予測装置の構成の一例を示す機能ブロック図である。
【図２】実施形態に係る測位データ系列履歴情報の一例を示す模式図である。
【図３】実施形態に係る目的地予測モデルパラメータ情報の一例を示す模式図である。
【図４】実施形態に係る目的地候補情報の一例を示す模式図である。
【図５】実施形態に係る入力情報の一例を示す模式図である。
【図６】実施形態に係る目的地予測装置により実行される学習フェーズにおける処理の流れを示すフローチャートである。
【図７】実施形態に係る目的地予測装置により実行される予測フェーズにおける処理の流れを示すフローチャートである。
【図８】実施形態に係る目的地予測装置により実行される初期の抽出処理の流れを示すフローチャートである。
【図９】実施形態に係る目的地予測装置により実行されるデータ入力時の抽出処理の流れを示すフローチャートである。
【図１０】実施形態に係る目的地予測装置により実行される学習処理の流れを示すフローチャートである。
【図１１】実施形態に係るＲＮＮの構造を示す模式図である。
【図１２】実施形態に係る目的地予測装置により実行される予測処理の流れを示すフローチャートである。
【図１３】実施形態に係る目的地予測装置により実行される近接遷移確率計算処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について図面を用いて説明する。なお、本実施形態では、ユーザがＧＰＳ、Ｗｉ−Ｆｉチップ等が搭載された携帯端末を携帯して目的地に向かう場合について説明する。
【００２０】
また、本実施形態では、測位データの系列の履歴に対して、ユーザの次の移動先を予測するＲＮＮ（ｒｅｃｕｒｒｅｎｔ  ｎｅｕｒａｌ  ｎｅｔｗｏｒｋ）モデル（下記の非特許文献３及び非特許文献４を参照）を学習した後、ＲＮＮモデルを用いたサンプリングシミュレーションによって目的地候補への訪問可能性を算出する。これにより、長期にわたる状態の依存性の考慮しつつデータスパースネス問題の解決することが可能となり、ユーザの未来の目的地をより高精度に予測できる。
【００２１】
［非特許文献３］Sepp Hochreiter and Jurgen Schmidhuber, "Long short-term memory", Neural Computation 9 (8): pp.1735-1780 (1997).
【００２２】
［非特許文献４］Felix A. Gers, Nicol N. Schraudolph, and Jurgen Schmidhuber, "Learning precise timing with LSTM recurrent networks", Journal of Machine Learning Research, vol. 3, pp.115-143 (2002).
【００２３】
図１に示すように、本実施形態に係る目的地予測装置１０は、測位データ系列履歴データベース１２、グリッドＩＤ抽出部１４、目的地予測モデル学習部１６、目的地予測モデルパラメータデータベース１８、目的地候補データベース２０、及び、目的地予測部２２を備える。
【００２４】
測位データ系列履歴データベース１２は、一例として図２に示すように、ユーザが上記携帯端末を携帯して移動した際に、当該携帯端末により測位された空間的位置を示す測位データ（本実施形態では、緯度及び経度の組）の識別ＩＤが整数値で表された測位番号、測位データの一部として測位された緯度、測位データの一部として測位された経度、及び、測位された時刻がそれぞれ対応付けられた測位データ系列履歴情報が記憶される。測位データ系列履歴情報において、ユーザの一連の移動において複数の異なる時刻に各々測位された複数の測位データにより、測位データの系列が構成される。
【００２５】
グリッドＩＤ抽出部１４は、空間的位置を複数に分割し、分割した分割領域である各々のグリッドに識別ＩＤであるグリッドＩＤを整数値で割り当てる。また、グリッドＩＤ抽出部１４は、測位データ系列履歴データベース１２に記憶されている測位データの系列に基づいて、各々の測位データの緯度及び経度の組に対してグリッドＩＤを対応付けることにより、グリッドＩＤの系列を抽出する。
【００２６】
目的地予測モデル学習部１６は、グリッドＩＤ抽出部１４により抽出されたグリッドＩＤの系列から、次の移動先となるグリッドを予測するためのＲＮＮモデルを学習する。また、目的地予測モデル学習部１６は、学習したＲＮＮモデルのパラメータを、目的地予測モデルパラメータデータベース１８に記憶させる。なお、ＲＮＮモデル、及びＲＮＮモデルの学習方法については、後述する。
【００２７】
目的地予測モデルパラメータデータベース１８は、一例として図３に示すように、ＲＮＮモデルのパラメータのパラメータ名、及び、ＲＮＮモデルのパラメータのパラメータ値がそれぞれ対応付けられた目的地予測モデルパラメータ情報が記憶される。
【００２８】
目的地候補データベース２０は、一例として図４に示すように、目的地候補の識別ＩＤが整数値で表された目的地候補番号、目的地候補の緯度、及び、目的地候補の経度がそれぞれ対応付けられた目的地候補情報が記憶される。
【００２９】
本実施形態では、測位データの複数の系列から、各々の測位データの系列の最終点の緯度及び経度の組をそれぞれ目的地候補として抽出し、抽出した緯度及び経度の組を目的地候補の緯度及び経度とすることにより、目的地候補情報を構築する。
【００３０】
しかしながら、目的地候補情報を構築する方法はこれに限らず、測位データの各々の系列の最終点をＫ−ｍｅａｎｓクラスタリング、Ｍｅａｎ−ｓｈｉｆｔクラスタリング等によりクラスタリングし、クラスタリングされた部分集合を目的地候補としても良い。この場合には、部分集合に含まれる最終点の緯度及び経度の平均値、中央値等をそれぞれ目的地候補の緯度及び経度とすることにより、目的地候補情報を構築すると良い。
【００３１】
目的地予測部２２は、目的地の予測を行う際の予測対象の測位データ、すなわちユーザの現在の位置までの移動経路の少なくとも一部を示す測位データとして入力された入力情報に基づき、学習されたＲＮＮモデルのパラメータを用いることにより構築されたＲＮＮモデルと、目的地候補情報と、グリッド間の距離情報とを用いて、サンプリングシミュレーションを行い、各々の目的地候補への訪問可能性を算出し、算出した各々の目的と候補への訪問可能性に基づきユーザの目的地を予測する。
【００３２】
なお、上述した入力情報は、目的地の予測を行う際に予測対象とする測位データの系列であり、一例として図５に示すように、緯度及び経度の組が測位された測位データの識別ＩＤが整数値で表された測位番号、測位データの一部である緯度、測位データの一部である経度、及び、測位された時刻がそれぞれ対応付けられた情報である。そして、目的地予測部２２は、入力情報に含まれる測位データの系列から、グリッドＩＤ抽出部１４により抽出されたグリッドＩＤの系列に基づき、上述したように、ＲＮＮモデルのパラメータを用いることにより構築されたＲＮＮモデルと、目的地候補情報と、グリッド間の距離情報とを用いて、ユーザの目的地を予測する。
【００３３】
目的地予測部２２は、近接遷移確率計算部４を含んで構成されている。
近接遷移確率計算部２４は、グリッド間の距離に基づく重みベクトルを用いて、各々のグリッドについて、グリッド間の距離に応じた近接遷移確率を計算する。また、近接遷移確率計算部２４は、各々のグリッドへの遷移確率を、計算した近接遷移確率に補正するように更新する。
【００３４】
また、目的地予測部２２は、サンプリングシミュレーションを行う際に、測位データの系列から抽出されたグリッドＩＤの系列に基づき、ＲＮＮモデルを用いて、測位データの系列の最終点に対応するグリッドから各グリッドへの遷移確率、及び状態ベクトルを算出する。そして、目的地予測部２２は、算出した遷移確率をグリッド間の距離に応じた重みによって補正し、補正した遷移確率に基づき、次のステップに移動するグリッドをサンプリングし、遷移確率と状態ベクトルとをＲＮＮモデルに入力して次のステップにおける遷移確率及び状態ベクトルを算出することを繰り返す。
【００３５】
なお、本実施形態に係る目的地予測装置１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、各種プログラムを記憶するＲＯＭ（Read Only Memory）を備えたコンピュータ装置で構成される。また、目的地予測装置１０を構成するコンピュータは、ハードディスクドライブ、不揮発性メモリ等の記憶部を備えていても良い。本実施形態では、ＣＰＵがＲＯＭ、ハードディスク等の記憶部に記憶されているプログラムを読み出して実行することにより、上記のハードウェア資源とプログラムとが協働し、上述した機能が実現される。
【００３６】
また、本実施形態では、測位データ系列履歴データベース１２、目的地予測モデルパラメータデータベース１８、及び、目的地候補データベース２０は、目的地予測装置１０の内部に設けられているが、これに限らず、目的地予測装置１０の外部に設けられていても構わない。
【００３７】
以上のような機能を備えた目的地予測装置１０によって実行される処理は、ＲＮＮモデルのパラメータを記憶するための学習フェーズと、入力した入力情報に基づいて目的地を予測するための予測フェーズと、に分けられる。
【００３８】
まず、本実施形態に係る目的地予測装置１０による学習フェーズにおける処理の流れの概要を、図６に示すフローチャートを用いて説明する。
【００３９】
ステップＳ１０１では、グリッドＩＤ抽出部１４が、測位データ系列履歴データベース１２から測位データ系列履歴情報を取得し、取得した測位データ系列履歴情報に含まれる測位データの系列に基づいて、グリッドＩＤの系列を抽出するデータ入力時の抽出処理を行う。なお、データ入力時の抽出処理については、図９に示すフローチャートを用いて後述する。
【００４０】
ステップＳ１０３では、目的地予測モデル学習部１６が、抽出されたグリッドＩＤの系列から、ＲＮＮモデルを学習する学習処理を行う。なお、学習処理については、図１０に示すフローチャートを用いて後述する。
【００４１】
ステップＳ１０５では、目的地予測モデル学習部１６が、学習したＲＮＮモデルのパラメータを目的地予測モデルパラメータデータベース１８に記憶させる。
【００４２】
次に、本実施形態に係る目的地予測装置１０による予測フェーズにおける処理の流れの概要を、図７に示すフローチャートを用いて説明する。
【００４３】
ステップＳ２０１では、グリッドＩＤ抽出部１４が、入力情報を入力し、入力した入力情報に含まれる測位データの系列に基づいて、グリッドＩＤの系列を抽出するデータ入力時の抽出処理を行う。なお、データ入力時の抽出処理については、図９に示すフローチャートを用いて後述する。
【００４４】
ステップＳ２０３では、目的地予測部２２が、目的地予測モデルパラメータデータベース１８からＲＮＮモデルのパラメータを取得すると共に、目的地候補データベース２０から目的地候補情報を取得する。また、目的地予測部２２が、抽出されたグリッドＩＤの系列から、取得したＲＮＮモデルのパラメータを用いて構築されたＲＮＮモデルと、取得した目的地候補情報とを用いて、ユーザの目的地を予測する予測処理を行う。なお、予測処理については、図１２に示すフローチャートを用いて後述する。
【００４５】
ここで、本実施形態におけるグリッドＩＤ抽出部１４の処理について詳細に説明する。なお、グリッドＩＤ抽出部１４は、目的地の予測の開始時に行う初期の抽出処理と、測位データの系列を入力した際に行うデータ入力時の抽出処理と、を行う。
【００４６】
まず、グリッドＩＤ抽出部１４の初期の抽出処理の流れを、図８に示すフローチャートを用いて説明する。なお、初期の抽出処理は、データ入力時の抽出処理に先立って行われる処理である。
【００４７】
ステップＳ３０１では、グリッドＩＤ抽出部１４が、緯度経度空間を一定間隔の格子状に分割することにより、各々矩形状の領域である複数のグリッドを作成する。
【００４８】
なお、緯度経度空間を分割する方法はこれに限らず、緯度及び経度の各々の組が何れかの分割領域に含まれるように分割されれば良く、例えば下記の非特許文献５に開示された公知技術であるジオハッシュを用いて分割しても良い。また、本実施形態では、緯度経度空間を一定間隔の格子状に分割することにより各々形状が等しい複数のグリッドを作成するが、グリッドの形状はこれに限らず、サイズ又は形状が異なる複数のグリッドを作成しても良い。
【００４９】
［非特許文献５］  Kisung Lee, Raghu K. Ganti, Mudhakar Srivatsa, Ling Liu, "Efficient spatial query processing for big data", In Proc. of SIGSPATIAL’14, pp.469-472 (2014). 
【００５０】
ステップＳ３０３では、グリッドＩＤ抽出部１４が、分割で得られた各々のグリッドに、グリッドＩＤとして整数値を割り当てる。本実施形態では、グリッドＩＤ抽出部１４は、０から順に値を１ずつ増やしつつ各々のグリッドに整数値を割り当てることにより、複数のグリッドの各々でグリッドＩＤが重複することを回避する。
【００５１】
次に、グリッドＩＤ抽出部１４のデータ入力時の抽出処理の流れを、図９に示すフローチャートを用いて説明する。
【００５２】
ステップＳ４０１では、グリッドＩＤ抽出部１４が、入力された入力情報に含まれる測位データの系列の各々の測位データについて、対応するグリッドを決定する。
【００５３】
ステップＳ４０３では、グリッドＩＤ抽出部１４が、対応するグリッドに割り当てられた整数値の系列をグリッドＩＤの系列として目的地予測部２２に出力する。
【００５４】
次に、本実施形態における目的地予測モデル学習部１６が実行する学習処理について、図１０に示すフローチャートを用いて詳細に説明する。
【００５５】
以下、数式内においてはベクトルをボールド表示で表し、本文中においてはベクトルの記号に「＾」を付して表す。
【００５６】
ステップＳ５０１では、グリッドＩＤ抽出部１４が、測位データ系列履歴データベース１２から測位データ系列履歴情報を取得し、取得した測位データ系列履歴情報に含まれる測位データの系列に基づいて、上述した学習時の抽出処理により得られたグリッドＩＤの系列を抽出する。また、グリッドＩＤ抽出部１４が、全てのグリッド数の次元からなるｏｎｅ−ｈｏｔ表現の特徴ベクトルの系列を算出する。なお、ここでいうｏｎｅ−ｈｏｔ表現の特徴ベクトルは、対応するグリッドＩＤの要素が１となり、それ以外の要素が０となるバイナリベクトルである。
【００５７】
ステップＳ５０３では、目的地予測モデル学習部１６が、算出した特徴ベクトルの系列を教師データとして、任意の測位タイミングの特徴ベクトルに対して次の測位タイミングの特徴ベクトルを予測するＲＮＮモデルを学習する。なお、ＲＮＮの手法としては、上述した非特許文献３に開示された公知技術であるＬＳＴＭ（ｌｏｎｇ  ｓｈｏｒｔ  ｔｅｒｍ  ｍｅｍｏｒｙ）を備えたＲＮＮ、上述した非特許文献４に開示された公知技術である忘却ゲート付のＬＳＴＭを備えたＲＮＮ等、公知技術を利用することが可能である。
【００５８】
図１１に示すように、ＲＮＮモデルを用いた次の測位タイミングの特徴ベクトルの予測では、まず、パラメータに基づいて現在の測位タイミングにおけるｏｎｅ−ｈｏｔ表現の特徴ベクトルを求め（Ｓ３０）、求めた特徴ベクトルを低次元に埋め込む（Ｓ３２）。具体的には、モデルパラメータの一つであるｗembed＾と、ｏｎｅ−ｈｏｔ表現の特徴ベクトルとの積を取ることで、別のベクトル空間に埋め込まれた特徴ベクトルを得る。
【００５９】
次に、得られた特徴ベクトルと、前の測位タイミングにおけるＲＮＮモデルを用いて得られた潜在的な状態ベクトル（Ｓ３４）とを入力し、上述した非特許文献３に開示されたＬＳＴＭ等を用いて現在の測位タイミングにおける状態ベクトルを算出する（Ｓ３６）。
【００６０】
最後に、算出した状態ベクトルから、ソフトマックス関数を用いて、次の測位タイミングにおける特徴ベクトル、すなわち各々のグリッドへの移動確率を予測する（Ｓ３８）。
【００６１】
なお、ＲＮＮの学習には、上述した非特許文献３に開示されているＴｒｕｎｃａｔｅｄ  ＢＰＴＴ（Ｔｒｕｎｃａｔｅｄ  ｂａｃｋ  ｐｒｏｐａｇａｔｉｏｎ  ｔｈｒｏｕｇｈ  ｔｉｍｅ）等の手法を利用することが可能である。
【００６２】
ステップＳ５０５では、学習したＲＮＮモデルのパラメータを、目的地予測モデルパラメータデータベース１８に記憶させる。なお、図３に示した目的地予測モデルパラメータ情報は、上述したＬＳＴＭを備えたＲＮＮモデルのパラメータの一例である。すなわち、ｗembed＾は、ｏｎｅ−ｈｏｔ表現の入力特徴ベクトルを低次元の別のベクトル空間に埋め込むためのパラメータである。また、ｗin＾は、ＬＳＴＭのｉｎｐｕｔ  ｇａｔｅにおけるパラメータであり、ｗout＾は、ｏｕｔｐｕｔ  ｇａｔｅにおけるパラメータであり、ｗc＾は、ｍｅｍｏｒｙ  ｃｅｌｌにおけるパラメータである。また、ｗsoftmax＾は、ソフトマックス関数を用いてＲＮＮの状態ベクトルから次の測位タイミングにおける特徴ベクトルを算出するためのパラメータである。
【００６３】
次に、本実施形態における目的地予測部２２が実行する予測処理について、図１２に示すフローチャートを用いて詳細に説明する。
【００６４】
本来、ＲＮＮモデルは、現在の測位タイミングから一つ先の測位タイミングへ遷移する際の遷移先の状態を推定するモデルである。しかし、目的地を推定する場合においては、現在地から目的地に一度のステップでたどり着くとは限らない。そのため、一般的なＲＮＮモデルの利用方法では、目的地の予測を実現することができない。
【００６５】
そこで、本実施形態では、目的地予測部２２が、現在の測位タイミングまでのグリッドＩＤの系列を入力して、ＲＮＮモデルを用いて複数ステップの遷移をランダムサンプリングによってシミュレーションし、各々の目的地候補へ到達する回数をカウントする。カウントされた値は、入力に対する次の各々の目的地候補への訪問可能性とみなすことができる。そのため、このカウントされた値に基づいて目的地を決定する。
【００６６】
以下、目的地を決定する具体的な方法を詳細に説明する。
【００６７】
ステップＳ６０１では、目的地予測部２２が、各々の目的地候補への訪問可能性を表す訪問確率ベクトルＰ＾を零ベクトルで初期化する。
【００６８】
ステップＳ６０３では、目的地予測部２２が、初期の状態ベクトルｈ＾を零ベクトルで初期化する。
【００６９】
ステップＳ６０５では、目的地予測部２２が、目的地予測モデルパラメータデータベース１８からＲＮＮモデルのパラメータを取得し、取得したＲＮＮモデルのパラメータを用いてＲＮＮモデルを構築する。この際、目的地予測部２２は、上述した通り、現在の測位タイミングのグリッドＩＤから生成されたｏｎｅ−ｈｏｔ表現の特徴ベクトルと、直前の測位タイミングにおけるＲＮＮモデルから得られた状態ベクトルをＲＮＮモデルに入力することにより、次の測位タイミングにおける予測結果の特徴ベクトル及び状態ベクトルを出力する。
【００７０】
ここで、予測結果の特徴ベクトルは、各々のグリッドへの遷移確率とみなすことができる。以下、処理対象とするグリッドｇのグリッドＩＤから生成されたｏｎｅ−ｈｏｔ表現の特徴ベクトル、及び、処理対象とするグリッドｇの１つ前の測位タイミングにおいてＲＮＮモデルから得られた状態ベクトルｈ＾とし、ＲＮＮモデルを用いて得られる関数ＲＮＮ（グリッドｇ，状態ベクトルｈ＾)と表記する。
【００７１】
ステップＳ６０７では、目的地予測部２２が、シミュレーション試行回数である変数ｉが１からＮになるまでの間、ループ内の処理を繰り返すループＡを開始する。なお、例えば、Ｎ＝１０００である。
【００７２】
ステップＳ６０９では、目的地予測部２２が、グリッドＩＤ抽出部１４により、入力情報に含まれる測位データの系列に対して上述した予測時の抽出処理を実行することによって得られたグリッドＩＤの系列をＧとすると、グリッドＩＤの系列Ｇにおける各々の要素のグリッドＩＤのグリッドｇ毎にループ内の処理を繰り返すループＢを開始する。
【００７３】
ステップＳ６１１では、目的地予測部２２が、下記（１）式に基づいて、ＲＮＮモデルを用いてグリッドｇ及び１つ前の測位タイミングの状態ベクトルｈ＾から、各々のグリッドへの遷移確率ｐ＾を算出し、さらに状態ベクトルｈ＾を更新する。
【００７４】
【数１】
0006543215.tif 000002
【００７５】
ステップＳ６１３では、目的地予測部２２が、グリッドＩＤの系列Ｇ内の全てのグリッドｇについてループ内の処理を実行したか否かを判定し、否定判定となった場合はループ内の処理を繰り返し、肯定判定となった場合はループＢを終了してステップＳ６１５に移行する。
【００７６】
ステップＳ６１５では、目的地予測部２２が、サンプリングの回数である変数ｊが１からＭになるまでの間、ループ内の処理を繰り返すループＣを開始する。なお、Ｍはサンプリングの上限回数であり、例えば、Ｍ＝１００である。
【００７７】
ステップＳ６１６では、目的地予測部２２の近接遷移確率計算部２４が、各々のグリッドへの遷移確率ｐ＾を更新する近接遷移確率計算処理を実行する。以下、図１３に示す近接遷移確率計算処理の流れを示すフローチャートを参照して、近接遷移確率計算処理の流れについて説明する。
【００７８】
ステップＳ７０１では、近接遷移確率計算部２４が、グリッドｇから全｜Ｇ｜個のグリッドへの距離に基づく重みベクトルｓ＾を下記（２）式に基づいて計算する。
【００７９】
【数２】
0006543215.tif 000003
【００８０】
ここで、Ｄｉｓｔ（…，…）は、２つのグリッド間の距離［メートル］を表す。σは、各要素の重みのばらつき度合を決定する固定値であり、本実施形態では、σ＝２００［メートル］とする。
【００８１】
ステップＳ７０３では、近接遷移確率計算部２４が、重みベクトルｓ＾、及び各々のグリッドへの遷移確率ｐ＾に基づいて、下記（３）式に従って、各々のグリッドへの近接遷移確率を計算し、各々のグリッドへの遷移確率ｐ＾を更新して、図１２のステップＳ６１７に移行する。
【００８２】
【数３】
0006543215.tif 000004
【００８３】
ここで、上記（３）式中の「○」は、ベクトルのアダマール積を表す。
【００８４】
このように、各々のグリッドへの遷移確率を、グリッド間の距離に応じて補正し、後述するように、補正した各々のグリッドへの遷移確率に基づき、次のステップに移動するグリッドをサンプリングすることにより、物理的には起こり得ない空間的に大きく離れた遷移を予測してしまうことを回避でき、それによってより小さな誤差で目的地を予測することが可能となる。
【００８５】
図１２のステップＳ６１７では、目的地予測部２２が、次のステップに移動した場合のグリッドとなるグリッドｇを、各々のグリッドへの遷移確率ｐ＾に従ってランダムサンプリングする。
【００８６】
ステップＳ６１９では、目的地予測部２２が、グリッドｇに最も近い目的地候補ｄとの距離が閾値εより近いか否かを判定する。本実施形態では、１ステップでユーザが移動する距離の平均値を閾値εとし、例えば、ε＝１００ｍ（メートル）である。ステップＳ６１９で肯定判定となった場合はステップＳ６２５に移行し、否定判定となった場合はステップＳ６２１に移行する。
【００８７】
ステップＳ６２１では、目的地予測部２２が、上記（１）式に基づいて、ＲＮＮモデルを用いて、グリッドｇ及び１ステップ前の状態ベクトルｈ＾から、各々のグリッドへの遷移確率ｐ＾を算出し、更に、状態ベクトルｈ＾を更新する。
【００８８】
ステップＳ６２３では、目的地予測部２２が、変数ｊがＭになったか否かを判定し、否定判定となった場合はループ内の処理を繰り返し、肯定判定となった場合はループＣを終了してステップＳ６２７に移行する。
【００８９】
ステップＳ６２５では、目的地予測部２２が、下記（４）式に基づいて、目的地候補ｄに対応する訪問確率ベクトルＰ＾の要素Ｐｄに１を加算する。
【００９０】
【数４】
0006543215.tif 000005
【００９１】
ステップＳ６２７では、目的地予測部２２が、変数ｉがＮになったか否かを判定し、否定判定となった場合はループＡ内の処理を繰り返し、肯定判定となった場合はループＡを終了してステップＳ６２９に移行する。
【００９２】
ステップＳ６２９では、目的地予測部２２が、各々の目的地候補への訪問可能性を表す訪問確率ベクトルＰ＾から、最も訪問する可能性の高い目的地候補のグリッドＩＤを算出する。
【００９３】
ステップＳ６３１では、目的地予測部２２が、目的地候補データベース２０から取得した目的地候補情報から、算出したグリッドＩＤと一致する目的地候補の緯度及び経度を取得して、表示手段に表示したり記憶手段に記憶したりすることにより出力する。
【００９４】
以上のように、本実施形態に係る目的地予測装置１０は、測位データ系列履歴情報から緯度及び経度の組である測位データの系列の履歴を受け取り、受け取った測位データの系列の履歴に含まれる測位データの系列に基づいて、グリッドＩＤの系列を抽出する。また、目的地予測装置１０は、グリッドＩＤの系列からＲＮＮモデルを学習し、学習したＲＮＮモデルのパラメータを目的地予測モデルパラメータ情報として記憶する。
【００９５】
目的地予測装置１０は、入力情報として測位データの系列を受け取り、受け取った測位データの系列に基づいてグリッドＩＤの系列を抽出する。また、目的地予測装置１０は、目的地予測モデルのパラメータを取得してＲＮＮモデルを構築し、抽出したグリッドＩＤの系列からＲＮＮモデルを用いたサンプリングシミュレーションによって各々の目的地候補への訪問可能性を算出し、算出した訪問可能性を、グリッド間の距離に応じて補正し、補正した訪問可能性に基づいて目的地の予測結果として目的地の緯度及び経度を出力する。
【００９６】
このように、ユーザの測位データの系列の履歴を用いてＲＮＮモデルを学習し、新たに取得したユーザの測位データの系列からＲＮＮモデルを用いたサンプリングシミュレーションを行う。この方法により、長期にわたる状態の依存性を考慮することができる。さらに、同様の方法により、新たなユーザの測位データの系列に対して、一部のみ包含する学習データを基に目的地の予測を行えるため、従来のマルコフモデルを三次以上に拡張する場合よりも、少ない移動パターンの学習データを用意すればよく、これにより、データスパースネスの問題を解決できる。また、物理的には起こり得ない空間的に大きく離れた遷移を予測してしまうことを回避でき、それによってより小さな誤差で目的地を予測することが可能となる。以上の効果を踏まえて、目的地候補への訪問可能性を算出するので、ユーザの目的地を精度良く予測することが可能になる。
【００９７】
なお、本実施形態では、空間的位置を示す測位データとして、緯度及び経度の組を用いる場合について説明したが、これに限らず、空間的位置を示す測位データとして、目的地を予測する空間において位置を特定できる情報を用いれば良い。
【００９８】
また、本実施形態では、図１に示す機能の構成要素の動作をプログラムとして構築し、目的地予測装置１０として利用されるコンピュータにインストールして実行させるが、これに限らず、ネットワークを介して流通させても良い。
【００９９】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールしたり、配布したりしても良い。
【符号の説明】
【０１００】
１０  目的地予測装置
１２  測位データ系列履歴データベース
１４  グリッドＩＤ抽出部
１６  目的地予測モデル学習部
１８  目的地予測モデルパラメータデータベース
２０  目的地候補データベース
２２  目的地予測部
【図１】
0006543215.tif 000006
【図２】
0006543215.tif 000007
【図３】
0006543215.tif 000008
【図４】
0006543215.tif 000009
【図５】
0006543215.tif 000010
【図６】
0006543215.tif 000011
【図７】
0006543215.tif 000012
【図８】
0006543215.tif 000013
【図９】
0006543215.tif 000014
【図１０】
0006543215.tif 000015
【図１１】
0006543215.tif 000016
【図１２】
0006543215.tif 000017
【図１３】
0006543215.tif 000018