(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＾は、ソフトマックス関数を用いてＲＮＮの状態ベクトルから次の測位タイミングにおける特徴ベクトルを算出するためのパラメータである。
【００６３】
次に、本実施形態におけるグリッド訪問回数計算部２２が実行する計算処理について、図１３に示すフローチャートを用いて詳細に説明する。グリッド訪問回数計算部２２は、ＲＮＮを用いたサンプリングシミュレーションによって、各々のタイムステップにおける移動経路となる各々のグリッドの訪問回数を算出する。
【００６４】
ステップＳ６０１では、グリッド訪問回数計算部２２が、各々のタイムステップにおける各々のグリッドの訪問回数を表す、Ｍ×Ａのグリッド訪問回数行列Ｐの全要素を零ベクトルで初期化する。ここで、Ｍはサンプリングシミュレーションにおける最大サンプリング回数であり、例えば、Ｍ＝１００である。また、Ａは緯度経度空間におけるグリッドの総数である。
【００６５】
ステップＳ６０３では、グリッド訪問回数計算部２２が、初期の状態ベクトルｈ＾を零ベクトルで初期化する。
【００６６】
ステップＳ６０５では、グリッド訪問回数計算部２２が、移動先予測モデルパラメータデータベース１８からＲＮＮモデルのパラメータを取得し、取得したＲＮＮモデルのパラメータを用いてＲＮＮモデルを構築する。この際、グリッド訪問回数計算部２２は、上述した通り、現在の測位タイミングのグリッドＩＤから生成されたｏｎｅ−ｈｏｔ表現の特徴ベクトルと、直前の測位タイミングにおけるＲＮＮモデルから得られた状態ベクトルをＲＮＮモデルに入力することにより、次の測位タイミングにおける予測結果の特徴ベクトル及び状態ベクトルを出力する。
【００６７】
ここで、予測結果の特徴ベクトルは、各々のグリッドへの遷移確率とみなすことができる。以下、現在の測位タイミングのグリッドｇのグリッドＩＤから生成されたｏｎｅ−ｈｏｔ表現の特徴ベクトル、及び、直前の測位タイミングにおいてＲＮＮモデルから得られた状態ベクトルｈ＾とし、ＲＮＮモデルを用いて得られる関数ＲＮＮ（グリッドｇ，状態ベクトルｈ＾)と表記する。
【００６８】
ステップＳ６０７では、グリッド訪問回数計算部２２が、シミュレーション試行回数である変数ｉが１からＮになるまでの間、ループ内の処理を繰り返すループＡを開始する。なお、例えば、Ｎ＝１０００である。
【００６９】
ステップＳ６０９では、グリッド訪問回数計算部２２が、グリッドＩＤ抽出部１４により、入力情報に含まれる測位データの系列に対して上述した予測時の抽出処理を実行することによって得られたグリッドＩＤの系列をＧとすると、グリッドＩＤの系列Ｇにおける各々の要素のグリッドＩＤのグリッドｇのグリッド毎にループ内の処理を繰り返すループＢを開始する。
【００７０】
ステップＳ６１１では、グリッド訪問回数計算部２２が、下記（１）式に基づいて、ＲＮＮモデルを用いてグリッドｇ及び１ステップ前の状態ベクトルｈ＾から、各々のグリッドへの遷移確率ｐ＾を算出し、さらに状態ベクトルｈ＾を更新する。
【００７１】
【数１】
0006521835.tif 000002
【００７２】
ステップＳ６１３では、グリッド訪問回数計算部２２が、グリッドＩＤの系列Ｇ内の全てのグリッドｇについてループ内の処理を実行したか否かを判定し、否定判定となった場合はループ内の処理を繰り返し、肯定判定となった場合はループＢを終了してステップＳ６１５に移行する。
【００７３】
ステップＳ６１５では、グリッド訪問回数計算部２２が、サンプリングの回数である変数ｋが１からＭになるまでの間、ループ内の処理を繰り返すループＣを開始する。なお、Ｍはサンプリングの上限回数であり、例えば、Ｍ＝１００である。
【００７４】
ステップＳ６１７では、グリッド訪問回数計算部２２が、次のステップに移動した場合のグリッドとなるグリッドｇを、各々のグリッドへの遷移確率ｐ＾に従ってランダムサンプリングする。
【００７５】
ステップＳ６１９では、グリッド訪問回数計算部２２が、グリッドｇに最も近い目的地候補ｄとの距離が閾値εより近いか否かを判定する。本実施形態では、例えば、１ステップでユーザが移動する距離の平均値を閾値εとし、例えば、ε＝１００ｍ（メートル）である。ステップＳ６１９で肯定判定となった場合はステップＳ６２５に移行し、否定判定となった場合はステップＳ６２１に移行する。
【００７６】
ステップＳ６２１では、グリッド訪問回数計算部２２が、下記（２）式に基づいて、タイムステップｊにおいて訪問したグリッドｇに対応するグリッド訪問回数行列Ｐ＾のｊ行ｇ番目の要素Ｐj,gに１を加算する。
【００７７】
【数２】
0006521835.tif 000003
【００７８】
ステップＳ６２３では、グリッド訪問回数計算部２２が、上記（１）式に基づいて、ＲＮＮモデルを用いて、グリッドｇ、及び１つ前の測位タイミングの状態ベクトルｈ＾から、各々のグリッドへの遷移確率ｐ＾を算出し、更に、状態ベクトルｈ＾を更新する。
【００７９】
ステップＳ６２５では、グリッド訪問回数計算部２２が、変数ｋがＭになったか否かを判定し、否定判定となった場合はループ内の処理を繰り返し、肯定判定となった場合はループＣを終了してステップＳ６２７に移行する。
【００８０】
ステップＳ６２７では、グリッド訪問回数計算部２２が、変数ｉがＮになったか否かを判定し、否定判定となった場合はループＡ内の処理を繰り返し、肯定判定となった場合はループＡを終了する。
【００８１】
次に、本実施形態における移動経路確率分布計算部２４が実行する出力処理について、図１４に示すフローチャートを用いて詳細に説明する。
【００８２】
ステップＳ７０１では、移動経路確率分布計算部２４が、グリッド訪問回数計算部２２から、グリッド訪問回数行列Ｐ＾を取得する。
【００８３】
ステップＳ７０３では、移動経路確率分布計算部２４が、下記（３）式に基づいて、入力時間ｔと測位データの系列の測位データの測位時間間隔Ｔから、入力時間ｔに対応するタイムステップｊを算出する。
【００８４】
【数３】
0006521835.tif 000004
【００８５】
ステップＳ７０５では、移動経路確率分布計算部２４が、下記（４）式に基づいて、タイムステップｊにおける移動経路確率分布ｒ＾を算出する。なお、Ｋはグリッドの総数を表す。またｒ＾の各々の要素は入力時間ｔ経過後にユーザがｒ＾の各々の要素に対応するグリッドに存在する確率を表す。
【００８６】
【数４】
0006521835.tif 000005
【００８７】
ステップＳ７０７では、移動経路確率分布計算部２４が、算出した移動経路確率分布ｒ＾を、表示手段に表示したり記憶手段に記憶したりすることにより出力する。
【００８８】
以上のように、本実施形態に係る移動経路予測装置１０は、測位データ系列履歴データベース１２から緯度と経度の組である測位データの系列の履歴を取得し、取得した測位データの系列の履歴に含まれる測位データの系列に測位データを一定の時間間隔で補間し、測位データが補間された測位データの系列に基づいてグリッドＩＤの系列を抽出する。また、移動経路予測装置１０は、グリッドＩＤの系列からＲＮＮモデルを学習し、学習したＲＮＮモデルのパラメータを移動先予測モデルパラメータデータベース１８に記憶させる。
【００８９】
また、移動経路予測装置１０は、入力した測位データの系列を取得し、取得した測位データの系列に測位データを一定の時間間隔で補間し、補間された測位データの系列に基づいてグリッドＩＤの系列を抽出する。そして、移動経路予測装置１０は、移動先予測モデルパラメータデータベース１８からパラメータを取得してＲＮＮモデルを構築し、目的地候補データベース２０から目的地候補を取得し、抽出したグリッドＩＤの系列からＲＮＮモデルを用いたサンプリングシミュレーションによってグリッド訪問回数行列を算出し、算出したグリッド訪問回数行列と入力時間に基づいて移動経路の確率分布を算出し、算出した移動経路の確率分布を出力する。
【００９０】
このように、ユーザの位置を測位した測位データの系列の履歴に対して、ユーザの移動先を予測するＲＮＮモデルを学習し、学習したＲＮＮモデルを用いたサンプリングシミュレーションによって、目的地候補への移動をシミュレーションする過程で、各々の時刻における各々の移動経路への訪問回数を算出することで、任意の時刻におけるユーザの移動経路を確率分布として予測することが可能となる。
【００９１】
なお、本実施形態では、図１に示す機能の構成要素の動作をプログラムとして構築し、移動経路予測装置１０として利用されるコンピュータにインストールして実行させるが、これに限らず、ネットワークを介して流通させても良い。
【００９２】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールしたり、配布したりしても良い。
【符号の説明】
【００９３】
１０  移動経路予測装置
１２  測位データ系列履歴データベース
１３  即位データ系列補間部
１４  グリッドＩＤ抽出部
１６  移動先予測モデル学習部
１８  移動先予測モデルパラメータデータベース
２０  目的地候補データベース
２２  グリッド訪問回数計算部
２４  移動経路確率分布計算部
【図１】
0006521835.tif 000006
【図２】
0006521835.tif 000007
【図３】
0006521835.tif 000008
【図４】
0006521835.tif 000009
【図５】
0006521835.tif 000010
【図６Ａ】
0006521835.tif 000011
【図６Ｂ】
0006521835.tif 000012
【図６Ｃ】
0006521835.tif 000013
【図７】
0006521835.tif 000014
【図８】
0006521835.tif 000015
【図９】
0006521835.tif 000016
【図１０】
0006521835.tif 000017
【図１１】
0006521835.tif 000018
【図１２】
0006521835.tif 000019
【図１３】
0006521835.tif 000020
【図１４】
0006521835.tif 000021