データ処理装置、データ処理方法、およびプログラム
【課題】より正確に、目的地までの経路および所要時間を予測することができるようにする。
【解決手段】学習メインプロセス部２３は、学習用データとしての移動履歴データをユーザの活動を表す確率モデルで表し、そのパラメータを学習する。目的地経由地検出部２５は、確率モデルの状態ノードのうち、目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する。現在地ノード推定部４１は、ユーザの現在地に相当する現在地ノードを推定する。目的地経由地予測部４２は、ユーザの現在地から目的地までの経路を探索する。予測ポストプロセス部３４は、探索された目的地への到達確率と所要時間を算出する。本発明は、例えば、移動履歴データから目的地を予測するデータ処理装置に適用できる。
【解決手段】学習メインプロセス部２３は、学習用データとしての移動履歴データをユーザの活動を表す確率モデルで表し、そのパラメータを学習する。目的地経由地検出部２５は、確率モデルの状態ノードのうち、目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する。現在地ノード推定部４１は、ユーザの現在地に相当する現在地ノードを推定する。目的地経由地予測部４２は、ユーザの現在地から目的地までの経路を探索する。予測ポストプロセス部３４は、探索された目的地への到達確率と所要時間を算出する。本発明は、例えば、移動履歴データから目的地を予測するデータ処理装置に適用できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、およびプログラムに関し、特に、より正確に、目的地までの経路および所要時間を予測することができるようにするデータ処理装置、データ処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０号（以下、先願１という）として先に提案している。先願１の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。先願１では、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの移動履歴の時系列データを学習した確率的状態遷移モデルを用いて、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【０００４】
さらに、本出願人は、先願１をさらに発展させ、「所定時間後」という現在時刻からの経過時間の指定がない場合であっても、複数の目的地への到達確率、経路、時間を予測する方法を、特願２００９−２０８０６４号（以下、先願２という）として提案した。先願２の方法では、確率的状態遷移モデルを構成するノードに、”移動状態”かまたは”滞在状態”の属性が付与された。そして、確率的状態遷移モデルを構成するノードの中から、目的地のノードとして”滞在状態”のノードを見つけることで、目的地の候補を自動的に検出することができた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００６】
【非特許文献１】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、先願２の予測方法では、次のような事象が発生していた。第１に、予測される目的地が実際の目的地ではなく、途中の経由地とすることがあった。これにより、途中の経由地から実際の目的地までが予測されないことがあった（第1の課題）。例えば、帰宅途中の駅での電車乗り換えや本屋への立ち寄りなどのため、所定時間滞在した場所が目的地と認識され、本来の目的地である自宅までの経路を予測できない場合があった。
【０００８】
第２に、予測結果として、ほぼ同一の経路を通る、似たような経路が複数提示され、ユーザにとって有益なその他の経路がユーザに提示なされないことがあった（第２の課題）。これは、頻繁に通り、バリエーションの多い経路と、頻繁に通らず、バリエーションの少ない経路とをうまく区別できないことに起因する。
【０００９】
本発明は、このような状況に鑑みてなされたものであり、より正確に、目的地までの経路および所要時間を予測することができるようにするものである。
【課題を解決するための手段】
【００１０】
本発明の一側面のデータ処理装置は、学習用データとして取得される、ユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、探索された前記目的地への到達確率と所要時間を算出する算出手段とを備える。
【００１１】
本発明の一側面のデータ処理方法は、ユーザの移動履歴データを処理するデータ処理装置が、学習用データとして取得される前記移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習し、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、探索された前記目的地への到達確率と所要時間を算出するステップを含む。
【００１２】
本発明の一側面のプログラムは、コンピュータを、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、探索された前記目的地への到達確率と所要時間を算出する算出手段として機能させるためのものである。
【００１３】
本発明の一側面においては、学習用データとして取得される移動履歴データが、ユーザの活動を表す確率モデルで表され、そのパラメータが学習され、学習により得られたパラメータを用いた確率モデルの状態ノードのうち、目的地および経由地に相当する目的地ノードおよび経由地ノードが推定され、学習用データとは別の、現在から所定時間以内のユーザの移動履歴データが、学習により得られたパラメータを用いた確率モデルに入力され、ユーザの現在地に相当する現在地ノードが推定され、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られた確率モデルとを用いて、ユーザの現在地から目的地までの経路が探索され、探索された目的地への到達確率と所要時間が算出される。
【発明の効果】
【００１４】
本発明の一側面によれば、より正確に、目的地までの経路および所要時間を予測することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【図２】予測システムのハードウエア構成例を示すブロック図である。
【図３】移動履歴データの例を示す図である。
【図４】HMMの例を示す図である。
【図５】left-to-right型のHMMの例を示す図である。
【図６】スパース制約を与えたHMMの例を示す図である。
【図７】学習プリプロセス部の詳細構成例を示すブロック図である。
【図８】学習プリプロセス部の処理について説明する図である。
【図９】移動属性識別付与部の詳細構成例を示すブロック図である。
【図１０】移動属性識別部の学習器の構成例を示すブロック図である。
【図１１】行動状態をカテゴリごとに分類する場合の分類例を示す図である。
【図１２】行動状態ラベリング部の処理例を説明する図である。
【図１３】行動状態ラベリング部の処理例を説明する図である。
【図１４】図１０の行動状態学習部の構成例を示すブロック図である。
【図１５】移動属性識別部の詳細構成例を示すブロック図である。
【図１６】移動属性識別部の学習器のその他の構成例を示すブロック図である。
【図１７】移動属性識別部のその他の構成例を示すブロック図である。
【図１８】学習プリプロセス部の処理を説明するフローチャートである。
【図１９】学習メインプロセス処理を説明するフローチャートである。
【図２０】学習ポストプロセス部の詳細構成例を示すブロック図である。
【図２１】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２２】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２３】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２４】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２５】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２６】目的地経由地検出部の処理について説明する図である。
【図２７】学習ブロック全体の処理を説明するフローチャートである。
【図２８】ツリー探索処理を説明するフローチャートである。
【図２９】ツリー探索処理をさらに説明する図である。
【図３０】ツリー探索処理をさらに説明する図である。
【図３１】ツリー探索処理における探索結果リストの例を示す図である。
【図３２】代表経路選択処理を説明するフローチャートである。
【図３３】予測ブロック全体の処理を説明するフローチャートである。
【図３４】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
［予測システムの構成例］
図１は、本発明を適用した予測システムの一実施の形態の構成例を示している。
【００１７】
図１の予測システム１は、学習ブロック１１、ユーザ別モデルパラメータ記憶部１２、および予測ブロック１３により構成される。
【００１８】
学習ブロック１１には、GPS (Global Positioning System)センサなどのセンサデバイス（不図示）において、所定の期間に取得された、所定の時刻におけるユーザの位置（緯度と経度）を示す時系列データが供給される。即ち、学習ブロック１１には、一定時間間隔（たとえば、１５秒間隔）で順次取得された位置（緯度および経度）のデータと、そのときの時刻の３次元からなる、ユーザの移動経路を示す時系列データ（以下、移動履歴データという。）が供給される。なお、時系列データを構成する、緯度、経度、および時刻の１組のデータを、適宜、３次元データともいう。
【００１９】
学習ブロック１１は、ユーザの移動履歴データを用いて、ユーザの活動モデル（ユーザの行動・活動パターンを表した状態モデル）を、確率的状態遷移モデルとして学習する学習処理を行う。
【００２０】
学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM（Hidden Markov Model）などの、隠れ状態を含む確率モデルを採用することができる。予測システム１では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図４乃至図６を参照して後述する。
【００２１】
ユーザ別モデルパラメータ記憶部１２は、学習ブロック１１の学習により得られた、ユーザの活動モデルを表すパラメータを記憶する。
【００２２】
予測ブロック１３は、学習ブロック１１の学習により得られたユーザ活動モデルのパラメータをユーザ別モデルパラメータ記憶部１２から取得する。そして、予測ブロック１３は、新たに取得されたユーザの移動履歴データに対し、学習により得られたパラメータを用いたユーザ活動モデルを用いて、ユーザの現在地を推定し、さらに現在地からの移動先となる目的地を予測する。さらに、予測ブロック１３は、予測した目的地までの到達確率、経路、および到達時間（所要時間）も算出する。なお、目的地は１つだけとは限らず、複数の目的地が予測されることもある。
【００２３】
学習ブロック１１および予測ブロック１３の詳細について説明する。
【００２４】
学習ブロック１１は、履歴データ蓄積部２１、学習プリプロセス部２２、学習メインプロセス部２３、学習ポストプロセス部２４、および目的地経由地検出部２５により構成される。
【００２５】
履歴データ蓄積部２１は、センサデバイスから供給される、ユーザの移動履歴データを、学習用データとして蓄積（記憶）する。履歴データ蓄積部２１は、移動履歴データを、必要に応じて学習プリプロセス部２２に供給する。
【００２６】
学習プリプロセス部２２は、センサデバイスから生じる課題を解決する。具体的には、学習プリプロセス部２２は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。また、学習プリプロセス部２２は、移動履歴データを構成する３次元データそれぞれに対し、同一場所に滞在（停止）している”滞在状態”か、または、移動している”移動状態”のいずれかの移動属性を付与する。移動属性付与後の移動履歴データが、学習メインプロセス部２３と目的地経由地検出部２５に供給される。
【００２７】
学習メインプロセス部２３は、ユーザ活動モデルを確率的状態遷移モデルにモデル化する。即ち、学習メインプロセス部２３は、ユーザの移動履歴を確率的状態遷移モデルにモデル化したときのパラメータを求める。学習により得られたユーザ活動モデルのパラメータは、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給される。
【００２８】
学習ポストプロセス部２４は、学習メインプロセス部２３の学習により得られたユーザ活動モデルを用いて、移動履歴データを構成する各３次元データを、ユーザ活動モデルの状態ノードに変換する。即ち、学習ポストプロセス部２４は、移動履歴データに対応する、ユーザ活動モデルの状態ノードの時系列データ（状態ノード系列データ）を生成する。その際、学習ポストプロセス部２４は、一般常識に基づくバイアスを加えることで、状態ノード系列データの一部修正を行う。学習ポストプロセス部２４は、変換および修正後の状態ノード系列データを目的地経由地検出部２５に供給する。
【００２９】
目的地経由地検出部２５は、学習プリプロセス部２２から供給された移動属性付与後の移動履歴データと、学習ポストプロセス部２４から供給された状態ノード系列データとを対応付ける。即ち、目的地経由地検出部２５は、移動履歴データを構成する各３次元データに、ユーザ活動モデルの状態ノードを割り当てる。
【００３０】
そして、目的地経由地検出部２５は、状態ノード系列データの各状態ノードのうち、移動属性が”滞在状態”の３次元データに対応する状態ノードに、目的地または経由地の属性を付与する。これにより、ユーザの移動履歴内の所定の場所（に対応する状態ノード）が、目的地かまたは経由地に割り当てられる。目的地経由地検出部２５により、状態ノードに付与された目的地、経由地の属性についての情報は、ユーザ別モデルパラメータ記憶部１２に供給され、記憶される。
【００３１】
予測ブロック１３は、バッファリング部３１、予測プリプロセス部３２、予測メインプロセス部３３、および、予測ポストプロセス部３４により構成される。
【００３２】
バッファリング部３１は、予測処理のためのリアルタイムに取得される移動履歴データをバッファリングする（記憶する）。なお、予測処理のための移動履歴データとしては、学習処理時の移動履歴データよりも短い期間のデータ、例えば、１００ステップ程度の移動履歴データがあれば十分である。バッファリング部３１は、常に、所定期間分の最新の移動履歴データを記憶するようにし、新たなデータが取得されたとき、記憶されているデータのうち最も古いデータを消去する。
【００３３】
予測プリプロセス部３２は、学習プリプロセス部２２と同様、センサデバイスから生じる課題を解決する。即ち、予測プリプロセス部３２は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。
【００３４】
予測メインプロセス部３３は、現在地ノード推定部４１と目的地経由地予測部４２により構成される。予測メインプロセス部３３には、ユーザ別モデルパラメータ記憶部１２から、学習ブロック１１の学習により得られた、ユーザ活動モデルを表すパラメータが供給される。
【００３５】
現在地ノード推定部４１は、予測プリプロセス部３２から供給される移動履歴データと、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する状態ノード（現在地ノード）を推定する。状態ノードの推定には、ビタビ最尤推定や軟判定ビタビ推定を採用することができる。
【００３６】
目的地経由地予測部４２は、現在地ノード推定部４１で推定された現在地ノードから遷移可能な複数の状態ノードでなるツリー構造において、目的地の状態ノード（目的地ノード）までのノード系列とその生起確率を算出する。なお、目的地の状態ノードへのノード系列（経路）には経由地のノードが含まれる場合もあるので、目的地経由地予測部４２は、目的地と同時に経由地も予測する。
【００３７】
予測ポストプロセス部３４は、同一目的地までの複数の経路の選択確率（生起確率）の和を到達確率として求める。また、予測ポストプロセス部３４は、目的地への経路のうち代表となる１以上の経路（以下、代表経路という。）を選択し、代表経路の所要時間を算出する。そして、予測ポストプロセス部３４は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力する。なお、経路の生起確率の代わりに頻度、目的地への到達確率の代わりに到達頻度を、予測結果として出力してもよい。
【００３８】
［予測システムのハードウエア構成例］
以上のように構成される予測システム１は、例えば、図２に示されるハードウエア構成を採用することができる。即ち、図２は、予測システム１のハードウエア構成例を示すブロック図である。
【００３９】
図２において、予測システム１は、３台のモバイル端末５１−１乃至５１−３とサーバ５２とにより構成されている。モバイル端末５１−１乃至５１−３は、同一機能を有する同型のモバイル端末５１であるが、モバイル端末５１−１乃至５１−３では、それを所有するユーザが異なる。従って、図２では、３台のモバイル端末５１−１乃至５１−３のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末５１が存在する。
【００４０】
モバイル端末５１は、無線通信及びインターネット等のネットワークを介した通信により、サーバ５２とデータの授受を行うことができる。サーバ５２は、モバイル端末５１から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ５２は、データ処理の処理結果を無線通信等によりモバイル端末５１に送信する。
【００４１】
従って、モバイル端末５１とサーバ５２は、無線または有線による通信を行う通信部を少なくとも有する。
【００４２】
さらに、モバイル端末５１が、図１の予測ブロック１３を備え、サーバ５２が、図１の学習ブロック１１とユーザ別モデルパラメータ記憶部１２を備える構成を採用することができる。
【００４３】
この構成が採用される場合、例えば、学習処理において、モバイル端末５１のセンサデバイスにより取得された移動履歴データがサーバ５２に送信される。サーバ５２は、受信した学習用の移動履歴データに基づき、ユーザ活動モデルを学習し、記憶する。そして、予測処理において、モバイル端末５１が、学習により得られたユーザ活動モデルのパラメータを取得し、リアルタイムに取得される移動履歴データから、ユーザの現在地ノードを推定し、さらに、目的地ノードと、そこまでの到達確率、代表経路、および所要時間を算出する。そして、モバイル端末５１は、予測結果を図示せぬ液晶ディスプレイ等の表示部に表示する。
【００４４】
以上のようなモバイル端末５１とサーバ５２との間の役割分担は、それぞれのデータ処理装置としての処理能力や通信環境に応じて、適宜、決定することができる。
【００４５】
学習処理は、処理に要する１回あたりの時間は非常に長いが、それほど頻繁に処理する必要はない。従って、一般的には、携行可能なモバイル端末５１よりもサーバ５２の方が処理能力が高いので、サーバ５２に、一日に一回程度蓄積された移動履歴データに基づいて学習処理（パラメータの更新）を行わせるようにすることができる。
【００４６】
一方、予測処理は、時々刻々とリアルタイムに更新される移動履歴データに対応させて迅速に処理し、表示することが望ましいので、モバイル端末５１で処理を行う方が望ましい。通信環境がリッチであれば、サーバ５２に予測処理も行わせ、予測結果のみをサーバ５２から受信する方が、携行可能な小型化が要求されるモバイル端末５１の負荷が軽減され、望ましい。
【００４７】
また、モバイル端末５１単独で、データ処理装置として学習処理および予測処理を高速に行うことが可能である場合には、図１の予測システム１の構成すべてをモバイル端末５１が備えるようにすることも勿論可能である。
【００４８】
［入力される移動履歴データの例］
図３は、予測システム１で取得された移動履歴データの例を示している。図３において、横軸は経度を表し、縦軸は緯度を表している。
【００４９】
図３に示される移動履歴データは、実験者の１ヶ月半程度の期間に蓄積された移動履歴データを示している。図３に示されるように、移動履歴データは、主に、自宅周辺と、勤務先などの４か所の外出先を移動したデータとなっている。なお、この移動履歴データには、人工衛星を捕捉できず、位置が飛んでいるデータも含まれている。
【００５０】
［エルゴディックHMMについて］
次に、予測システム１が、学習モデルとして採用するエルゴディックHMMについて説明する。
【００５１】
図４は、HMMの例を示している。
【００５２】
HMMは、状態ノードと状態ノード間遷移とを有する状態遷移モデルである。
【００５３】
図４は、３状態のHMMの例を示している。
【００５４】
図４において（以降の図においても同様）、丸印は、状態ノードを表し、矢印は、状態ノードの遷移を表す。なお、以下において、状態ノードは、単に、ノードまたは状態ともいう。
【００５５】
また、図４において、si（図４では、i=1,2,3）は、状態を表し、aijは、状態siから状態sjへの状態遷移確率を表す。さらに、bj(x)は、状態sjへの状態遷移時に、観測値xが観測される出力確率密度関数を表し、πiは、状態siが初期状態である初期確率を表す。
【００５６】
なお、出力確率密度関数bj(x)としては、例えば、正規確率分布等が用いられる。
【００５７】
ここで、HMM（連続HMM）は、状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiによって定義される。これらの状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiを、HMMのパラメータλ={aij,bj(x), πi,i=1,2,・・・,M，j=1,2,・・・,M}という。Mは、HMMの状態数を表す。
【００５８】
HMMのパラメータλを推定する方法としては、Baum-Welchの最尤推定法が広く利用されている。Baum-Welchの最尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【００５９】
Baum-Welchの最尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測（生起）される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータλの推定が行われる。ここで、xtは、時刻tに観測される信号（サンプル値）を表し、Tは、時系列データの長さ（サンプル数）を表す。
【００６０】
Baum-Welchの最尤推定法については、例えば、“パターン認識と機械学習（下）”，Ｃ．Ｍ．ビショップ著，P. 333（英語原書：“Pattern Recognition and Machine Learning (Information Science and Statistics) ”，Christopher M. BishopSpringer, New York, 2006.）（以下、文献Ａと称する）に記載されている。
【００６１】
なお、Baum-Welchの最尤推定法は、尤度最大化に基づくパラメータ推定方法ではあるが、最適性を保証するものではなく、HMMの構造やパラメータλの初期値によっては、局所解（ローカルミニマム）に収束することがある。
【００６２】
HMMは、音声認識で広く利用されているが、音声認識で利用されるHMMでは、一般に、状態の数や状態遷移の仕方等はあらかじめ決定される。
【００６３】
図５は、音声認識で利用されるHMMの例を示している。
【００６４】
図５のHMMは、left-to-right型と呼ばれる。
【００６５】
図５では、状態数は３になっており、状態遷移は、自己遷移（状態siから状態siへの状態遷移）と、左から右隣の状態への状態遷移とのみを許す構造に制約されている。
【００６６】
図５のHMMのように、状態遷移に制約があるHMMに対して、図４に示した、状態遷移に制約がないHMM、すなわち、任意の状態siから任意の状態sjへの状態遷移が可能なHMMは、エルゴディック(Ergodic)HMMと呼ばれる。
【００６７】
エルゴディックHMMは、構造としては最も自由度の高いHMMであるが、状態数が多くなると、パラメータλの推定が困難となる。
【００６８】
例えば、エルゴディックHMMの状態数が、１０００である場合、状態遷移の数は、１００万（＝１０００×１０００）となる。
【００６９】
したがって、この場合、パラメータλのうちの、例えば、状態遷移確率aijについては、１００万個の状態遷移確率aijを推定することが必要となる。
【００７０】
そこで、状態に対して設定する状態遷移には、例えば、スパース(Sparse)な構造であるという制約（スパース制約）をかけることができる。
【００７１】
ここで、スパースな構造とは、任意の状態から任意の状態への状態遷移が可能なエルゴディックHMMのような密な状態遷移ではなく、ある状態から状態遷移することができる状態が非常に限定されている構造である。なお、ここでは、スパースな構造であっても、他の状態への状態遷移は、少なくとも１つ存在し、また、自己遷移は存在することとする。
【００７２】
図６は、スパース制約を与えたHMMを示している。
【００７３】
ここで、図６では、２つの状態を結ぶ双方向の矢印は、その２つの状態の一方から他方への状態遷移と、他方から一方への状態遷移とを表す。また、図６において、各状態は、自己遷移が可能であり、その自己遷移を表す矢印の図示は、省略されている。
【００７４】
図６では、１６個の状態が、２次元空間上に格子状に配置されている。すなわち、図６では、横方向に、４個の状態が配置され、縦方向にも、４個の状態が配置されている。
【００７５】
いま、横方向に隣接する状態どうしの距離、及び、縦方向に隣接する状態どうしの距離を、いずれも１とすると、図６Ａは、距離が１以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７６】
また、図６Ｂは、距離が√２以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７７】
図１の例では、予測システム１に、移動履歴データx=x1,x2,・・・,xTが供給され、学習ブロック１１は、移動履歴データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【００７８】
即ち、ユーザの移動軌跡を表す各時刻の位置（緯度経度）のデータが、HMMの状態sjのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。学習ブロック１１は、各状態sjに対応する地図上の一点（平均μj）とその分散値σj２、および状態遷移確率aijを最適化する。
【００７９】
なお、状態siの初期確率πiは、一様な値に設定することができる。例えば、M個の状態siそれぞれの初期確率πiが、1/Mに設定される。
【００８０】
現在地ノード推定部４１は、学習により得られたユーザ活動モデル（HMM）に対して、ビタビアルゴリズムを適用し、移動履歴データx=x1,x2,・・・,xTが観測される尤度を最も大にする状態遷移の過程（状態の系列）（パス）（以下、最尤パスともいう）を求める。これにより、ユーザの現在地に対応する状態siが認識される。
【００８１】
ここで、ビタビアルゴリズムとは、各状態siを始点とする状態遷移のパスの中で、時刻tに、状態siから状態sjに状態遷移する状態遷移確率aijと、その状態遷移において、移動履歴データx=x1,x2,・・・,xTのうちの時刻tのサンプル値xtが観測される確率（出力確率密度関数bj(x)から求められる出力確率）とを、処理後時系列データxの長さTに亘って累積した値（生起確率）を最大にするパス（最尤パス）を決定するアルゴリズムである。ビタビアルゴリズムの詳細については上述の文献ＡのP.347に記載されている。
【００８２】
［学習プリプロセス部２２の構成例］
図７は、学習ブロック１１の学習プリプロセス部２２の詳細構成例を示すブロック図である。
【００８３】
学習プリプロセス部２２は、データ接続分割部７１、データ異常除去部７２、再サンプリング処理部７３、移動属性識別付与部７４、および滞在状態加工部７５により構成される。
【００８４】
データ接続分割部７１は、移動履歴データの接続および分割の処理を行う。データ接続分割部７１には、移動履歴データが、センサデバイスから、１日単位などの所定の単位でログファイルとして供給される。従って、本来、ある目的地への移動途中で連続すべき移動履歴データが、日付を跨いだために分割されて取得されることがある。データ接続分割部７１は、そのような分割された移動履歴データを接続する。具体的には、データ接続分割部７１は、１つのログファイル内の最後の３次元（緯度、経度、時刻）データと、そのログファイルの次に作成されたログファイル内の最初の３次元データの時間差が所定の時間内であれば、それらのファイル内の移動履歴データを接続する。
【００８５】
また、例えば、GPSセンサは、トンネルや地下では人工衛星を捕捉することができないため、移動履歴データの取得間隔が長くなることがある。移動履歴データが長い時間欠落している場合には、ユーザがどこにいたかを推定することが難しくなる。そこで、データ接続分割部７１は、取得された移動履歴データにおいて、前後の取得時刻の間隔が所定の時間間隔（以下、欠落閾値時間という。）以上ある場合に、その間隔の前後で移動履歴データを分割する。ここで、欠落閾値時間は、例えば、５分、１０分、１時間などである。
【００８６】
データ異常除去部７２は、移動履歴データの明らかな異常を除去する処理を行う。例えば、ある時刻の位置のデータが、その前後の位置と１００ｍ以上も離れていて、跳躍している場合、その位置のデータは異常である。そこで、データ異常除去部７２は、ある時刻の位置のデータが、その前後の両方の位置と所定の距離以上離れている場合、その３次元データを移動履歴データから除去する。
【００８７】
再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを、線形補間等により補完する処理を行う。即ち、取得時刻の時間間隔が欠落閾値時間以上である場合には、データ接続分割部７１により、移動履歴データが分割されるが、欠落閾値時間未満のデータの欠落は残っている。そこで、再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを補完する。
【００８８】
移動属性識別付与部７４は、移動履歴の３次元データそれぞれが、同一場所に滞在（停止）している”滞在状態”か、または、移動している”移動状態”のいずれであるかの移動属性を識別し、付与する。これにより、移動履歴データの各３次元データに移動属性が付与された、移動属性付き移動履歴データが生成される。
【００８９】
滞在状態加工部７５は、移動属性識別付与部７４から供給される移動属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。より具体的には、滞在状態加工部７５は、”滞在状態”の移動属性が所定時間（以下、滞在閾値時間という。）以上継続している場合、その前後で移動履歴データを分割する。また、滞在状態加工部７５は、”滞在状態”の移動属性が滞在閾値時間未満で継続している場合には、その滞在閾値時間以内の所定時間続く、”滞在状態”の複数の３次元データの位置のデータをホールドする（同一位置のデータに修正する）。これにより、同一の目的地や経由地の移動履歴データに対して複数の”滞在状態”ノードが割り当てられることを防止することができる。換言すれば、同一の目的地や経由地を複数のノードで表現することを防止することができる。
【００９０】
［学習プリプロセス部２２の処理］
図８は、学習プリプロセス部２２の学習プリプロセス処理を概念的に示したイメージ図である。
【００９１】
図８上段に示される、再サンプリング処理部７３によるデータ補完後の移動履歴データ８１に対して、移動属性識別付与部７４が、”滞在状態”または”移動状態”の移動属性を識別し、付与する。その結果、図８中段に示される、移動属性付き移動履歴データ８２が生成される。
【００９２】
図８中段の移動属性付き移動履歴データ８２において、”ｍ１”および”ｍ２”は、”移動状態”の移動属性を表し、”ｕ”は、”滞在状態”の移動属性を表す。なお、”ｍ１”と”ｍ２”は、同じ”移動状態”でも、移動手段（車、バス、電車、徒歩など）が異なる。
【００９３】
そして、図８中段の、移動属性付き移動履歴データ８２に対して、滞在状態加工部７５により、移動履歴データを分割およびホールドする処理が実行され、図８下段の、移動属性付き移動履歴データ８３（８３Ａおよび８３Ｂ）が生成される。
【００９４】
移動属性付き移動履歴データ８３では、移動属性付き移動履歴データ８２において２回目に発生した”移動状態”の箇所（３次元データ）で分割処理が行われ、移動属性付き移動履歴データ８３Ａと８３Ｂに分割されている。
【００９５】
分割処理では、最初に、移動属性付き移動履歴データ８２の２回目に発生した”移動状態”までと、それ以降の複数の３次元データとで分割され、２つの移動属性付き移動履歴データ８３Ａおよび８３Ｂとされる。次に、分割後の移動属性付き移動履歴データ８３Ａおよび８３Ｂのうち、時間的に早い移動属性付き移動履歴データ８３Ａの最後の滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられる。これにより、不要な移動履歴データが削除されるので、学習時間を短縮することができる。
【００９６】
なお、図８の例では、移動属性付き移動履歴データ８２の３回目に発生した” 複数の移動状態”の３次元データも滞在閾値時間以上の”移動状態”が続くデータであり、同様の分割処理が行われている。しかし、分割後の後ろの３次元データが存在しないため、滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられるのみとなっている。
【００９７】
一方、移動属性付き移動履歴データ８３Ａのうち、１回目の”移動状態”の移動履歴データでは、ホールド処理が実行されている。ホールド処理後は、３つの”移動状態”の３次元データ｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ，ｙｋ），（ｔｋ＋１，ｘｋ＋１，ｙｋ＋１）｝が、｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ−１，ｙｋ−１），（ｔｋ＋１，ｘｋ−１，ｙｋ−１）｝となっている。即ち、位置のデータが”移動状態”の最初の位置のデータに修正されている。なお、ホールド処理では、位置のデータは、”移動状態”の最初の位置のデータに変更するのではなく、位置の平均値、”移動状態”の期間の真ん中の時刻の位置のデータ等に変更してもよい。
【００９８】
［移動属性識別付与部７４の構成例］
図９は、移動属性識別付与部７４の詳細構成例を示すブロック図である。
【００９９】
移動属性識別付与部７４は、移動速度演算部９１、移動属性識別部９２、および移動属性付与部９３により構成される。
【０１００】
移動速度演算部９１は、供給される移動履歴データから移動速度を演算する。
【０１０１】
具体的には、一定の時間間隔でｋステップ目（ｋ個目）に得られるときの３次元データを、時刻ｔｋ、経度ｙｋ、緯度ｘｋと表すと、ｋステップ目のｘ方向の移動速度ｖｘｋおよびｙ方向の移動速度ｖｙｋは、次式（１）により計算することができる。
【０１０２】
【数１】
【０１０３】
式（１）では、緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【０１０４】
また、移動速度演算部９１は、式（１）で得られる移動速度ｖｘｋおよびｖｙｋからさらに、式（２）で表されるｋステップ目の移動速度ｖｋと進行方向の変化θｋを求め、これを利用することができる。
【０１０５】
【数２】
【０１０６】
式（２）で表される移動速度ｖｋと進行方向の変化θｋを利用する方が、式（１）の移動速度ｖｘｋおよびｖｙｋよりも以下の点で、特徴をうまく取り出すことができる。
【０１０７】
１．移動速度ｖｘｋおよびｖｙｋのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段（電車や徒歩など）であっても角度が異なった場合に識別できない可能性があるが、移動速度ｖｋであればそのような可能性が少ない。
２．移動速度の絶対的な大きさ（｜ｖ｜）だけで学習すると、機器のノイズによって生じる｜ｖ｜のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
３．移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【０１０８】
以上の理由から、本実施の形態では、移動速度演算部９１は、移動速度のデータとして、式（２）で表される移動速度ｖｋと進行方向の変化θｋを求め、移動属性識別部９２に供給する。
【０１０９】
移動速度演算部９１は、移動速度ｖｋと進行方向の変化θｋの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理（前処理）を行うことができる。
【０１１０】
なお、センサデバイスのなかには、移動速度を出力できるものも存在する。そのようなセンサデバイスが採用されている場合、移動速度演算部９１を省略し、センサデバイスが出力する移動速度をそのまま利用することができる。以下では、進行方向の変化θｋを、進行方向θｋと略記する。
【０１１１】
移動属性識別部９２は、供給される移動速度に基づいて移動属性を識別し、認識結果を移動属性付与部９３に供給する。より具体的には、移動属性識別部９２は、ユーザの行動状態（移動状態）を確率的状態遷移モデル（HMM）として学習し、学習により得られた確率的状態遷移モデルを用いて移動属性を識別する。移動属性としては、少なくとも”滞在状態”と”移動状態”が存在する必要がある。本実施の形態では、図１１等を参照して後述するように、移動属性識別部９２は、”移動状態”を、さらに徒歩、自転車、車など、複数の移動手段によって分類した移動属性を出力する。
【０１１２】
移動属性付与部９３は、再サンプリング処理部７３からの、移動履歴データを構成する３次元データそれぞれに対し、移動属性識別部９２で認識された移動属性を付与し、移動属性付き移動履歴データを生成して、滞在状態加工部７５に出力する。
【０１１３】
次に、図１０乃至図１７を参照して、移動属性識別部９２で使用される、ユーザの行動状態を表した確率的状態遷移モデルのパラメータの求め方について説明する。
【０１１４】
［移動属性識別部９２の学習器の第１の構成例］
図１０は、カテゴリHMMにより、移動属性識別部９２で使用される確率的状態遷移モデルのパラメータを学習する学習器１００Aの構成例を示している。
【０１１５】
カテゴリHMMでは、学習する教師データが予めどのカテゴリ（クラス）に属するデータであるのかが既知であり、カテゴリごとにHMMのパラメータが学習される。
【０１１６】
学習器１００Aは、移動速度データ記憶部１０１、行動状態ラベリング部１０２、および行動状態学習部１０３により構成される。
【０１１７】
移動速度データ記憶部１０１は、学習用データとしての移動速度の時系列データを記憶する。
【０１１８】
行動状態ラベリング部１０２は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（カテゴリ）として付与する。行動状態ラベリング部１０２は、移動速度のデータに行動状態が対応付けられたラベル済み移動速度データを行動状態学習部１０３に供給する。例えば、ｋステップ目の移動速度ｖｋと進行方向θｋに対して、行動状態を表すラベルMを付与したデータが行動状態学習部１０３に供給される。
【０１１９】
行動状態学習部１０３は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データを、カテゴリごとに分類し、カテゴリ単位で、ユーザ活動モデル（HMM）のパラメータを学習する。学習の結果得られたカテゴリ毎のパラメータは移動属性識別部９２に供給される。
【０１２０】
［行動状態の分類例］
図１１は、行動状態をカテゴリごとに分類する場合の分類例を示している。
【０１２１】
図１１に示されるように、まず、ユーザの行動状態は、滞在状態と移動状態に分類することができる。本実施の形態では、移動属性識別部９２が認識するユーザの行動状態としては、上述したように、少なくとも滞在状態と移動状態が存在する必要があるので、この２つに分類することは必須である。
【０１２２】
さらに、移動状態は、移動手段によって、電車、車（バスなども含む）、自転車、徒歩に分類することができる。電車は、さらに、特急、快速、ローカルなどに分類することができ、車は、さらに、高速、一般道などに分類することができる。また、徒歩は、走る、普通、散歩などに分類することができる。
【０１２３】
本実施の形態では、ユーザの行動状態を、図１１において斜線で示される“滞在”、“電車（快速）”、“電車（ローカル）”、“車（高速）”、“車（一般道）”、“自転車”、および“徒歩”に分類することとする。なお、“電車（特急）”は、学習用データが得られなかったため省略した。
【０１２４】
なお、カテゴリの分類の仕方が図１１に示した例に限定されるものではないことは言うまでもない。また、移動手段による移動速度の変化はユーザによって大きく異なるものではないので、学習用データとしての移動速度の時系列データは、認識対象のユーザのものである必要はない。
【０１２５】
［行動状態ラベリング部１０２の処理例］
次に、図１２および図１３を参照して、行動状態ラベリング部１０２の処理例について説明する。
【０１２６】
図１２は、行動状態ラベリング部１０２に供給される移動速度の時系列データの例を示している。
【０１２７】
図１２では、行動状態ラベリング部１０２から供給される移動速度のデータ（ｖ，θ）を、（ｔ，ｖ）および（ｔ，θ）の形で示している。図１２において、四角（■）のプロットは移動速度ｖを表し、丸（●）のプロットは進行方向θを表している。また、横軸は時間ｔを表し、右側の縦軸は進行方向θを、左側の縦軸は移動速度ｖを表す。
【０１２８】
図１２の時間軸の下方に示されている“電車（ローカル）”、“徒歩”、“滞在”の文字は、説明のため付加したものである。図１２の時系列データの最初は、ユーザが電車（ローカル）で移動中である場合の移動速度のデータであり、次が“徒歩”で移動中である場合、その次が“滞在”である場合の移動速度のデータとなっている。
【０１２９】
ユーザが“電車（ローカル）”で移動している場合、電車が駅で停車し、出発するとき加速し、再度減速して駅に停車することを繰り返すので、移動速度ｖのプロットが繰り返し上下に振れるという特徴が表れている。なお、電車が停止している場合でも移動速度が０になっていないのは、移動平均によるフィルタリング処理を行っているためである。
【０１３０】
また、ユーザが“徒歩”で移動している場合と“滞在”している場合は、最も区別しにくい状態であるが、移動平均によるフィルタリング処理により、移動速度ｖに明らかな違いが見られる。また、“滞在”では、進行方向θが瞬時に大きく変化する特徴がみられ、“徒歩”との差別化が容易であることがわかる。このように、移動平均によるフィルタリング処理、および、ユーザの移動を移動速度ｖと進行方向θで表すことにより、“徒歩”と“滞在”の区別が容易になっていることがわかる。
【０１３１】
なお、“電車（ローカル）”と“徒歩”の間の部分は、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分である。
【０１３２】
図１３は、図１２に示した時系列データに対して、ラベル付けを行う例を示している。
【０１３３】
例えば、行動状態ラベリング部１０２は、図１２に示した移動速度のデータをディスプレイに表示する。そして、ユーザは、ディスプレイに表示された移動速度のデータのうち、ラベル付けをしたい部分を矩形の領域で囲む操作を、マウスなどにより行う。また、ユーザは、指定したデータに対して付与するラベルをキーボードなどから入力する。行動状態ラベリング部１０２は、ユーザによって指定された矩形領域に含まれる移動速度のデータに、入力されたラベルを付与することにより、ラベル付けを行う。
【０１３４】
図１３では、“徒歩”に相当する部分の移動速度のデータを矩形の領域で指示した例が示されている。なお、このとき、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分については、指示する領域に含めないようにすることができる。時系列データの長さは、行動の違いが時系列データに明確に出る長さから決める。例えば、２０ステップ（１５秒×２０ステップ＝３００秒）程度とすることができる。
【０１３５】
［行動状態学習部１０３の構成例］
図１４は、図１０の行動状態学習部１０３の構成例を示すブロック図である。
【０１３６】
行動状態学習部１０３は、分類部１２１とHMM学習部１２２１乃至１２２７により構成される。
【０１３７】
分類部１２１は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データのラベルを参照し、ラベルに対応するHMM学習部１２２１乃至１２２７のいずれかに供給する。即ち、行動状態学習部１０３では、ラベル（カテゴリ）ごとにHMM学習部１２２が用意されており、行動状態ラベリング部１０２から供給されるラベル済み移動速度データが、ラベルごとに分類されて、供給される。
【０１３８】
HMM学習部１２２１乃至１２２７それぞれは、供給されるラベル済み移動速度データを用いて、学習モデル（HMM）を学習する。そして、HMM学習部１２２１乃至１２２７それぞれは、学習により得られるHMMのパラメータλを、図９の移動属性識別部９２に供給する。
【０１３９】
HMM学習部１２２１は、ラベルが“滞在”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２２は、ラベルが“徒歩”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２３は、ラベルが“自転車”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２４は、ラベルが“電車（ローカル）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２５は、ラベルが“車（一般道）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２６は、ラベルが“電車（快速）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２７は、ラベルが“車（高速）”である場合の、学習モデル（HMM）を学習する。
【０１４０】
［移動属性識別部９２の第１の構成例］
図１５は、学習器１００Aで学習されたパラメータを利用する場合の移動属性識別部９２である、移動属性識別部９２Aの構成例を示すブロック図である。
【０１４１】
移動属性識別部９２Aは、尤度計算部１４１１乃至１４１７と尤度比較部１４２とにより構成されている。
【０１４２】
尤度計算部１４１１は、HMM学習部１２２１の学習により得られたパラメータを用いて、移動速度演算部９１（図９）から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１１は、行動状態が“滞在”である尤度を計算する。
【０１４３】
尤度計算部１４１２は、HMM学習部１２２２の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１２は、行動状態が“徒歩”である尤度を計算する。
【０１４４】
尤度計算部１４１３は、HMM学習部１２２３の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１３は、行動状態が“自転車”である尤度を計算する。
【０１４５】
尤度計算部１４１４は、HMM学習部１２２４の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１４は、行動状態が“電車（ローカル）”である尤度を計算する。
【０１４６】
尤度計算部１４１５は、HMM学習部１２２５の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１５は、行動状態が“車（一般道）”である尤度を計算する。
【０１４７】
尤度計算部１４１６は、HMM学習部１２２６の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１６は、行動状態が“電車（快速）”である尤度を計算する。
【０１４８】
尤度計算部１４１７は、HMM学習部１２２７の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１７は、行動状態が“車（高速）”である尤度を計算する。
【０１４９】
尤度比較部１４２は、尤度計算部１４１１乃至１４１７それぞれから供給される尤度を比較し、尤度の最も高い行動状態を選択し、移動属性として出力する。
【０１５０】
［移動属性識別部９２の学習器の第２の構成例］
図１６は、マルチストリームHMMにより、移動属性識別部９２で使用されるユーザ活動モデルのパラメータを学習する学習器１００Bの構成例を示している。
【０１５１】
学習器１００Bは、移動速度データ記憶部１０１、行動状態ラベリング部１６１、および行動状態学習部１６２により構成される。
【０１５２】
行動状態ラベリング部１６１は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（行動モード）として付与する。行動状態ラベリング部１６１は、移動速度の時系列データ（ｖ，θ）と、それと関連付けられた行動モードMの時系列データを行動状態学習部１６２に供給する。
【０１５３】
行動状態学習部１６２は、マルチストリームHMMにより、ユーザの行動状態を学習する。
【０１５４】
ここで、マルチストリームHMMは、通常のHMMと同様な遷移確率を有する状態ノードから、複数の異なる確率法則に従うデータが出力されるようなHMMである。マルチストリームHMMでは、パラメータλのうち、出力確率密度関数bj(x)が時系列データごとに別々に用意される。マルチストリームHMMでは、異なる種類の時系列データ（ストリーム）を関連付けながら学習することができる。
【０１５５】
行動状態学習部１６２には、連続量である移動速度ｖと進行方向θの時系列データと、離散量である行動モードMの時系列データが供給される。行動状態学習部１６２は、各状態ノードから出力される移動速度の分布パラメータと、行動モードの確率を学習する。学習により得られたマルチストリームHMMによれば、例えば、移動速度の時系列データから、現在の状態ノードが求められる。そして、求められた状態ノードから、行動モードを認識することができる。
【０１５６】
カテゴリHMMを用いた第１の構成例では、HMMをカテゴリごとに７個用意する必要があるが、マルチストリームHMMでは１個のHMMで十分である。ただし、状態ノードの数は、第１の構成例において７個のカテゴリで使用された状態ノードの総数と同程度用意する必要がある。
【０１５７】
［移動属性識別部９２の第２の構成例］
図１７は、学習器１００Bで学習されたパラメータを利用する場合の移動属性識別部９２である、移動属性識別部９２Bの構成例を示すブロック図である。
【０１５８】
移動属性識別部９２Bは、状態ノード認識部１８１と行動モード認識部１８２により構成される。
【０１５９】
状態ノード認識部１８１は、学習器１００Bで学習されたマルチストリームHMMのパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データから、マルチストリームHMMの状態ノードを認識する。状態ノード認識部１８１は、認識された現在の状態ノードのノード番号を行動モード認識部１８２に供給する。
【０１６０】
行動モード認識部１８２は、状態ノード認識部１８１で認識された状態ノードで、最も確率の高い行動モードを、移動属性として出力する。
【０１６１】
［学習プリプロセス部２２の処理］
図１８は、学習プリプロセス部２２による学習プリプロセス処理のフローチャートである。
【０１６２】
学習プリプロセス処理では、最初に、ステップＳ１において、データ接続分割部７１は、移動履歴データの接続および分割の処理を行う。
【０１６３】
ステップＳ２において、データ異常除去部７２は、移動履歴データの明らかな異常を除去する処理を行う。
【０１６４】
ステップＳ３において、再サンプリング処理部７３は、取得時刻の時間間隔が滞在閾値時間未満の欠落データを、線形補間等により補完する処理を行う。
【０１６５】
ステップＳ４において、移動属性識別付与部７４は、移動履歴の３次元データそれぞれに対し、”滞在状態”かまたは”移動状態”の移動属性を識別し、付与する。
【０１６６】
ステップＳ５において、滞在状態加工部７５は、移動属性識別付与部７４から供給される属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。そして、滞在状態加工部７５は、加工処理後の、移動属性付き移動履歴データを学習メインプロセス部２３に出力して、処理を終了する。
【０１６７】
以上のように、学習プリプロセス部２２では、移動履歴データが、必要に応じて分割等され、移動属性が付与された、移動属性付き移動履歴データとされて、学習メインプロセス部２３に供給される。
【０１６８】
［学習メインプロセス部２３の処理］
次に、図１９のフローチャートを参照して、学習メインプロセス部２３の処理（学習メインプロセス処理）について説明する。
【０１６９】
学習メインプロセス処理では、初めに、ステップＳ１１において、学習メインプロセス部２３は、移動履歴データに対する各状態の尤度を計算する。具体的には、学習メインプロセス部２３は、ユーザ活動モデルを表すHMMの状態ｓiへの遷移時に、移動履歴データの時刻tの位置のデータｘtが出力されると仮定した場合の状態尤度Ｐ（ｓi｜ｘt）を、次式（３）により計算する。
【０１７０】
【数３】
なお、時刻ｔは、時系列データの測定時刻ではなく、時系列データの順番（ステップ数）を表し、１からＴ（時系列データのサンプル数）までの値をとる。
【０１７１】
また、式（３）のＤは、移動履歴データの次元数を示している。いまの場合、移動履歴データは、時刻、緯度、および経度の３次元なので、Ｄ＝３となる。そして、ｘt（１）、ｘt（２）、ｘt（３）が、それぞれ移動履歴データｘtの時刻、緯度、経度を表すものとする。また、状態ｓiへの遷移時に出力される移動履歴データの時刻、緯度、および経度の出力確率密度関数がそれぞれ単一正規分布に従い、μsi（１）、σsi（１）は、時刻の出力確率密度関数の中心値および標準偏差を表す。また、μsi（２）、σsi（２）は、緯度の出力確率密度関数の中心値および標準偏差を表し、μsi（３）、σsi（３）は、経度の出力確率密度関数の中心値および標準偏差を表すものとする。
【０１７２】
なお、式（３）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１７３】
学習メインプロセス部２３は、ステップＳ１１において、全ての状態ｓiと３次元データｘtの組み合わせについて、式（３）により状態尤度Ｐ（ｓi｜ｘt）を計算する。
【０１７４】
次に、ステップＳ１２において、学習メインプロセス部２３は、各時刻ｔにおける全ての状態ｓiのフォワード尤度αt（ｓi）を計算する。即ち、学習メインプロセス部２３は、次式（４）および（５）を用いて、時刻ｔにおける状態ｓiのフォワード尤度αt（ｓi）を時刻１から最終の時刻Ｔまで順番に計算する。
【０１７５】
【数４】
なお、式（４）のπsiは、状態ｓiの初期確率を表す。また、式（５）のａjiは、状態ｓjから状態ｓiへの状態遷移確率を表す。なお、初期確率πsiおよび状態遷移確率ａjiの初期値は、例えば、外部から与えられる。式（４）および式（５）は、Baum-Welchの最尤推定法のフォワードアルゴリズムにおいて一般的に用いられる式である。
【０１７６】
ステップＳ１３において、学習メインプロセス部２３は、各時刻ｔにおける全ての状態ｓiのバックワード尤度βt（ｓi）を計算する。即ち、学習メインプロセス部２３は、次式（６）および（７）を用いて、時刻ｔにおける状態ｓiのバックワード尤度βt（ｓi）を、最終の時刻Ｔから時刻１まで逆順に計算する。
【０１７７】
【数５】
【０１７８】
式（６）および式（７）は、Baum-Welchの最尤推定法のバックワードアルゴリズムにおいて一般的に用いられる式である。式（６）は、時刻Ｔに各状態ｓiである確率が全て等しいものとしている。
【０１７９】
このように、ステップＳ１１乃至Ｓ１３の処理により、移動履歴データに対する隠れマルコフモデルの各種の尤度が計算される。
【０１８０】
ステップＳ１４において、学習メインプロセス部２３は、初期確率、状態遷移確率を更新する。即ち、学習メインプロセス部２３は、各状態ｓiの初期確率πsi、各状態間の状態遷移確率ａijを、次の式（８）および式（９）で求まる初期確率πsi’、状態遷移確率ａij’にそれぞれ更新する。
【０１８１】
【数６】
式（８）および式（９）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１８２】
ステップＳ１５において、学習メインプロセス部２３は、観測確率を更新する。即ち、学習メインプロセス部２３は、各状態ｓiの出力確率密度関数の中心値μsi（ｄ）、分散σsi（ｄ）2を、次の式（１０）および式（１１）で求まる中心値μsi（ｄ）’、分散σsi（ｄ）’2にそれぞれ更新する。
【０１８３】
【数７】
なお、式（１０）および式（１１）のｄは、データの次元を表し、いまの場合、１，２、または３のいずれかとなる。式（１０）および式（１１）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１８４】
ステップＳ１６において、学習メインプロセス部２３は、パラメータの更新を終了するか否かを判定する。例えば、各尤度の増分が所定の値以下となり、パラメータの更新の収束条件を満たした場合、学習メインプロセス部２３は、パラメータの更新を終了すると判定する。あるいは、ステップＳ１１乃至Ｓ１５の処理を規定の回数繰り返し実行した場合、パラメータの更新を終了すると判定するとしてもよい。
【０１８５】
ステップＳ１６で、パラメータの更新を終了しないと判定された場合、処理はステップＳ１１に戻る。
【０１８６】
ステップＳ１１では、学習メインプロセス部２３は、更新されたパラメータに基づいて、各状態の尤度が計算される。即ち、ステップＳ１４およびＳ１５の処理で更新された、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータに基づいて、各状態の尤度が計算される。
【０１８７】
その後、同様にステップＳ１２乃至Ｓ１５の処理が実行される。これにより、状態ｓiの系列の各種の尤度、すなわち、状態尤度Ｐ（ｓi｜ｘt）、フォワード尤度αt（ｓi）、バックワード尤度βt（ｓi）が次第に増加し、最終的に最大になるように、HMMのパラメータの更新が行われる。そして、ステップＳ１６において、再度、パラメータの更新を終了するか否かが判定される。
【０１８８】
ステップＳ１６で、パラメータの更新を終了すると判定された場合、処理はステップＳ１７に進む。
【０１８９】
ステップＳ１７において、学習メインプロセス部２３は、最終的なパラメータをユーザ別モデルパラメータ記憶部１２と目的地経由地検出部２５（図１）に出力する。即ち、学習メインプロセス部２３は、最終的に求められた、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータを、ユーザ別モデルパラメータ記憶部１２と目的地経由地検出部２５（図１）に出力する。その後、学習メインプロセス処理は終了する。
【０１９０】
［学習ポストプロセス部２４の構成例］
次に、学習ポストプロセス部２４の詳細について説明する。
【０１９１】
図２０は、学習ポストプロセス部２４の詳細構成例を示すブロック図である。
【０１９２】
学習ポストプロセス部２４は、状態系列生成部２０１と状態系列修正部２０２により構成される。状態系列生成部２０１と状態系列修正部２０２には、学習メインプロセス部２３が学習により求めたパラメータが供給される。
【０１９３】
状態系列生成部２０１は、学習プリプロセス部２２で生成された移動属性付き移動履歴データを、ユーザ活動モデルの状態ノードの時系列データ（状態系列データ）に変換し、状態系列修正部２０２に供給する。具体的には、具体的には、状態系列生成部２０１は、学習メインプロセス部２３から供給されたパラメータに基づくユーザ活動モデルから、移動履歴データの各３次元データに対応するユーザ活動モデルを認識する。そして、状態系列生成部２０１は、認識結果としてのユーザの状態ノードsiを、順次、状態系列修正部２０２に供給する。
【０１９４】
状態系列修正部２０２は、状態系列生成部２０１から供給される状態系列データを必要に応じて修正し、修正後の状態系列データを、目的地経由地検出部２５（図１）に供給する。状態系列修正部２０２で状態系列データの修正がされない場合には、状態系列生成部２０１から供給される状態系列データが、そのまま、目的地経由地検出部２５に供給される。
【０１９５】
［状態系列修正部２０２の処理］
図２１乃至図２５を参照して、状態系列修正部２０２が行う状態系列データの修正処理について説明する。
【０１９６】
図２１は、状態系列修正部２０２による修正処理を示している。
【０１９７】
本実施の形態において、状態系列生成部２０１から供給される状態系列データは、ユーザの移動履歴に対応するデータである。ユーザの移動は、ある目的地から他の目的地へのleft-to-right型の状態遷移モデルに近似できると考えられる。
【０１９８】
そこで、状態系列修正部２０２は、状態系列生成部２０１から供給される状態系列データを、left-to-right型の状態系列データとなるように簡素化する修正を行う。
【０１９９】
状態系列修正部２０２は、状態系列データを、left-to-rightの制約を満たすように修正するために、最初に、状態系列データで、ループ、即ち、同一の状態ノードに戻る部分があるかどうかを探索する。そして、状態系列修正部２０２は、ループが検出された場合、そのループをマージ（その状態ノードを削除して親ノードに吸収）するか、または、スプリット（新たな状態ノードを生成して分割）する。
【０２００】
より詳しくは、状態系列修正部２０２は、ループ内のノード数が１つである場合には、マージすることによって、状態系列データを修正し、ループ内のノード数が２以上である場合には、スプリットすることによって、状態系列データを修正する。
【０２０１】
［状態系列修正部２０２のループ修正処理］
図２２は、状態系列修正部２０２によるループ修正処理のフローチャートを示している。状態系列修正部２０２は、所定のステップ数の状態系列データを記憶する内部メモリを有し、状態系列生成部２０１から、ある程度のステップ数の状態系列データが内部メモリに蓄積されたとき、この処理が開始される。
【０２０２】
初めに、ステップＳ３１において、状態系列修正部２０２は、状態系列生成部２０１から供給された状態系列データに対し、注目ノードを決定する。即ち、状態系列修正部２０２は、状態系列生成部２０１から供給された状態系列データのなかの先頭の状態ノードを選択し、それを注目ノードとする。
【０２０３】
ステップＳ３２において、状態系列修正部２０２は、注目ノードのノード番号が１つ前のノードと同じかを判定する。状態遷移が自己遷移である場合には、注目ノードのノード番号が同じとなる。従って、換言すれば、状態系列修正部２０２は、自己遷移であるか否かを判定する。なお、先頭の状態ノードが注目ノードである場合には、注目ノードのノード番号が１つ前のノードと同じであると判定する。
【０２０４】
ステップＳ３２で、注目ノードのノード番号が１つ前のノードと同じであると判定された場合、処理は後述するステップＳ３７に進む。
【０２０５】
一方、ステップＳ３２で、注目ノードのノード番号が１つ前のノードと同じではないと判定された場合、処理はステップＳ３３に進み、状態系列修正部２０２は、注目ノードが過去の状態系列に存在するかを判定する。状態系列データにループが存在し、ループして過去の状態系列に戻ってきたとき、ステップＳ３３において、注目ノードが過去の状態系列に存在すると判定される。
【０２０６】
ステップＳ３３で、注目ノードが過去の状態系列に存在しないと判定された場合、処理は後述するステップＳ３７に進む。
【０２０７】
一方、ステップＳ３３で、注目ノードが過去の状態系列に存在すると判定された場合、処理はステップＳ３４に進み、状態系列修正部２０２は、ループ内のノード数が１つであるかを判定する。
【０２０８】
ステップＳ３４で、ループ内のノード数が１つであると判定された場合、ステップＳ３５において、状態系列修正部２０２は、ループのノードを親ノード（戻り先のノード）にマージする。
【０２０９】
ステップＳ３４で、ループ内のノード数が２以上であると判定された場合、ステップＳ３６において、状態系列修正部２０２は、新しいノードを生成し、分割する。
【０２１０】
ステップＳ３５またはＳ３６の処理後、ステップＳ３７において、状態系列データに、注目ノードの次のノードがあるかを判定する。
【０２１１】
ステップＳ３７で、注目ノードの次のノードがあると判定された場合、ステップＳ３８において、状態系列修正部２０２は、次のノードを注目ノードに決定し、処理をステップＳ３２に戻す。
【０２１２】
一方、ステップＳ３７で、注目ノードの次のノードがないと判定された場合、即ち、状態系列生成部２０１から供給された状態系列データの全ての状態ノードについてループを探索した場合、処理は終了する。
【０２１３】
状態系列修正部２０２は、以上の処理を行うことにより、状態系列生成部２０１から供給される状態系列データを修正して、修正後の状態系列データを出力する。
【０２１４】
なお、本実施の形態では、状態系列修正部２０２が、検出されたループを、マージまたはスプリットのいずれで修正するかを、ループ内のノード数が１つであるか否かによって判断した。しかし、マージまたはスプリットのいずれで修正した場合に尤度が高くなるか、または、学習モデルの複雑さなど、その他の判断基準で、マージまたはスプリットのいずれで修正するかを判断するようにしてもよい。
【０２１５】
また、他の情報が使える場合にはそれを用いて、マージまたはスプリットのいずれで修正するかを判断することも可能である。たとえば、ループ内のノードが１つであっても、例えば、目的地候補のノードなど、重要なノードであるかもしれない。このような場合は、マージでなくて、スプリットの処理をすべきである。また、ループ内のノード数が２以上あっても、いずれも重要でないノードかもしれない。また、あるいは、全ノード数に制約があってこれ以上増やせない場合なども考えられる。このような場合には、状況に応じて変更をすればよい。
【０２１６】
［状態系列修正部２０２によるその他の修正処理の説明］
次に、状態系列修正部２０２による状態系列データのその他の修正処理の例を説明する。
【０２１７】
図２３は、１つのノードが複数の系列で共有されている共有ノードを修正する処理の例を示している。
【０２１８】
図２３の上段の状態遷移図において、斜線を付して示される真ん中のノードは、共有ノードとなっている。即ち、共有ノードの前後のノードは、それぞれ別々のノードとなっている。状態系列修正部２０２は、図２３の下段の状態遷移図のように、共有ノードをスプリット（新たな状態ノードを生成して分割）し、２つの系列に、元の状態系列データを修正する。
【０２１９】
ノードの尤度が低い場合には、本来別々のノードになるべきところが、初期条件、モデルのノード数の不足などで、学習時にローカルミニマムに陥って、このような共有ノードとなることがある。３次元データを表すノードでノードの尤度が低い場合とは、ノードが示す位置（中心位置）と、実際のデータの位置との距離が大きい場合を意味する。
【０２２０】
状態系列修正部２０２には、共有ノードをスプリットする処理を、状態系列データの修正処理として行わせることで、初期条件、モデルのノード数の不足などで発生した共有ノードを解消することができる。換言すれば、学習メインプロセス部２３による拘束条件（スパース制約によるエルゴディックHMM）では実現できない処理を、状態系列修正部２０２で事後的（付加的に）実現することができる。
【０２２１】
［状態系列修正部２０２の共有ノード修正処理］
図２４は、状態系列修正部２０２による共有ノード修正処理のフローチャートを示している。状態系列生成部２０１から、全ての状態系列データが内部メモリに蓄積されたとき、この処理が開始される。
【０２２２】
初めに、ステップＳ５１において、状態系列修正部２０２は、内部メモリに記憶されている状態系列データのなかで、尤度が所定値以下のノードである低尤度ノードを検索して、ステップＳ５２に進む。本実施の形態では、学習により得られたノードの中心位置と、実際のデータの位置との距離が大きいノードが、低尤度ノードとなる。
【０２２３】
ステップＳ５２において、状態系列修正部２０２は、低尤度ノードが検出されたかを判定する。
【０２２４】
ステップＳ５２で、低尤度ノードが検出されたと判定された場合、処理はステップＳ５３に進み、状態系列修正部２０２は、検出された低尤度ノードを注目ノードに決定する。
【０２２５】
ステップＳ５４において、状態系列修正部２０２は、注目ノードが共有ノードであるかを判定する。ステップＳ５４で、注目ノードが共有ノードではないと判定された場合、処理はステップＳ５１に戻る。
【０２２６】
一方、ステップＳ５４で、注目ノードが共有ノードであると判定された場合、処理はステップＳ５５に進み、状態系列修正部２０２は、前後のノードが複数あるかを判定する。
【０２２７】
ステップＳ５５で、前後のノードのいずれかが複数ないと判定された場合、処理はステップＳ５１に戻る。一方、ステップＳ５５で、前後のノードのいずれもが複数あると判定された場合、処理はステップＳ５６に進み、状態系列修正部２０２は、新しいノードを生成することにより、元の状態系列データを、２つの系列に修正する。ステップＳ５６の処理後も、処理はステップＳ５１に戻る。
【０２２８】
そして、上述したステップＳ５１乃至Ｓ５６の処理を繰り返し実行することで、全ての低尤度ノードが順次検出され、共有ノードがスプリットされる。
【０２２９】
全ての低尤度ノードが検出された場合、ステップＳ５２で、低尤度ノードが検出されなかったと判定され、処理がステップＳ５７に進む。そして、ステップＳ５７において、状態系列修正部２０２は、元の状態系列データに対し修正がなされた修正後の状態系列データを出力して、処理を終了する。低尤度ノードが１つも検出されない場合には、元の状態系列データがそのまま出力される。
【０２３０】
状態系列修正部２０２は、以上のような共有ノード修正処理を行って、状態系列生成部２０１から供給される状態系列データを修正することができる。
【０２３１】
なお、図２３および図２４に示した処理では、前と後ろの両方について複数の系列がある場合のみ、ノードをスプリットするようにした。しかし、図２５右側に示すように、前または後ろのいずれか一方のみ、複数の系列がある場合であっても、ノードをスプリットするようにしてもよい。
【０２３２】
また、図２５左側に示すように、前と後ろの両方で複数の系列が存在しない場合であっても、スプリットした方がノードの尤度が高くなる場合には、スプリットするようにしてもよい。いずれの場合においても、スプリットすることにより、尤度が修正前より高くなることが条件である。また、図２５左側に示すように、前と後ろの両方で複数の系列が存在しない場合のスプリットでは、修正前後でステップ数が変わらないように、修正対象のノードにおいて、自己遷移が発生していることも条件となる。
【０２３３】
以上のような状態系列修正部２０２による状態系列データの修正処理によれば、状態系列データに拘束を新しく加えるのみならず、学習でローカルミニマムに陥って十分、尤度を高くすることができなかった場合などの修正が可能である。
【０２３４】
図２３および図２４に示した処理では、学習用データに対する尤度のチェックを行っているが、学習用データと同時に得られた他のデータによる尤度のチェックを行うようにしてもよい。他のデータ系列のうち、学習モデルの中の状態遷移に影響を及ぼすものがあれば、通常、マルチモーダルモデルとして学習することになる。しかし、そのデータ系列の寄与が大きくない、あるいは、不定であるならば、寄与の大きなデータのみで学習するようにして、学習されたモデルから得られる状態系列データを状態系列修正部２０２における修正時にのみ、その影響を反映させることで、寄与の少ない時系列データが学習モデルに必要以上の影響を与えるのを回避することができる。
【０２３５】
［目的地経由地検出部２５の処理］
次に、図２６を参照して、目的地経由地検出部２５の処理について説明する。
【０２３６】
上述したように、学習メインプロセス部２３は、移動履歴データを分割およびホールドする処理が行われた後の（移動属性付き）移動履歴データを学習用データとして、ユーザ活動モデルのパラメータを学習する。そして、学習ポストプロセス部２４が、学習により求めたパラメータを用いて、移動履歴データに対応する状態系列データを生成する。
【０２３７】
図２６Ａは、図８下段に示した、学習プリプロセス部２２によって移動履歴データの分割およびホールドが行われた後の、移動属性付き移動履歴データ８３Ａおよび８３Ｂを示している。
【０２３８】
図２６Ｂは、図８下段に示した移動属性付き移動履歴データ８３Ａおよび８３Ｂに、対応する状態系列データを併せて示した図である。
【０２３９】
移動属性付き移動履歴データ８３Ａには、ｓ１，ｓ２，・・・，ｓｋ，・・・ｓｔの状態系列ノードが対応する。移動属性付き移動履歴データ８３Ｂには、ｓｔ＋１，ｓｔ＋２，・・・，ｓＴの状態系列ノードが対応する。
【０２４０】
目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、目的地の属性を付与する。図２６Ｂの例では、移動属性付き移動履歴データ８３Ａの状態ノードｓｔと、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴに対して、目的地の属性が付与される。状態ノードｓｔと状態ノードｓＴは、いずれも滞在状態が滞在閾値時間以上継続していた状態ノードである。このように、目的地経由地検出部２５によって、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードが、目的地に推定される。
【０２４１】
なお、図８を参照して説明した分割処理では、分割した移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”が、１つの”滞在状態”に縮減された。しかしながら、分割処理では、移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”のすべてを、消去するようにしてもよい。図２６Ａの例で説明すると、移動属性付き移動履歴データ８３Ａおよび８３Ｂそれぞれの最後の”滞在状態（ｕ）”の３次元データを省略するようにしてもよい。この場合には、目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の３次元データに対応する状態ノードに、目的地の属性を付与する。図２６Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｔの１つ前の状態ノードｓｔ−１、および、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴの１つ前の状態ノードｓＴ−１を目的地とすればよい。
【０２４２】
目的地経由地検出部２５は、また、１まとまりの移動属性付き移動履歴データの途中にある”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、経由地の属性を付与する。即ち、滞在状態の継続時間が１の分割閾値時間未満である移動履歴データに対応する状態ノードが、経由地に推定される。図２６Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｋが、経由地に決定される。
【０２４３】
なお、目的地経由地検出部２５は、図２６Ｃに示すように、移動手段が変更されたとき、変更前の最後の状態ノードｓｈにも、経由地の属性を付与するようにしてもよい。
【０２４４】
［学習ブロック１１の処理］
図２７のフローチャートを参照して、学習ブロック１１全体の処理について説明する。
【０２４５】
初めに、ステップＳ７１において、履歴データ蓄積部２１は、センサデバイスから供給される、移動履歴データを、学習用データとして蓄積する。
【０２４６】
ステップＳ７２において、学習プリプロセス部２２は、図１８を参照して説明した、学習プリプロセス処理を実行する。即ち、履歴データ蓄積部２１に蓄積されている移動履歴データの接続および分割の処理、移動履歴データを構成する３次元データそれぞれに、”滞在状態”または”移動状態”の移動属性の付与、などを行う。
【０２４７】
ステップＳ７３において、学習メインプロセス部２３は、ユーザの移動履歴を学習する。即ち、学習メインプロセス部２３は、ユーザの移動履歴をユーザ活動モデルとして確率的状態遷移モデル（HMM）にモデル化したときのパラメータを求める。学習により得られたパラメータは、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給され、ユーザ別モデルパラメータ記憶部１２で記憶される。
【０２４８】
ステップＳ７４において、学習ポストプロセス部２４は、学習により得られたユーザ活動モデルを用いて、移動履歴データに対応する状態ノード系列データを生成する。
【０２４９】
ステップＳ７５において、目的地経由地検出部２５は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、目的地の属性を付与する。より具体的には、目的地経由地検出部２５は、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードに、目的地の属性を付与する。
【０２５０】
ステップＳ７６において、目的地経由地検出部２５は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、経由地の属性を付与する。より具体的には、目的地経由地検出部２５は、滞在状態の継続時間が滞在閾値時間未満である移動履歴データに対応する状態ノードに、経由地の属性を付与する。
【０２５１】
ステップＳ７７において、目的地経由地検出部２５は、状態ノードに付与された目的地、経由地の属性についての情報を、ユーザ別モデルパラメータ記憶部１２に記憶させ、処理を終了する。
【０２５２】
［予測メインプロセス部３３の処理］
次に、予測ブロック１３が行う処理について説明する。
【０２５３】
初めに、予測メインプロセス部３３による、現在地ノード以降のツリー探索処理について説明する。
【０２５４】
現在地ノード以降のツリー探索処理は、予測メインプロセス部３３の現在地ノード推定部４１が推定した現在地ノードから、到達可能な目的地ノードと、そこまでの経路を求める処理である。到達可能な目的地ノードは、現在地ノードから遷移可能なノードで構成されるツリー構造の中に存在する。従って、ツリーを構成する状態ノードのなかから、目的地ノードを探索することで、目的地を予測することができる。また、現在地ノード以降のツリー探索処理において、経由地の属性が付与された状態ノード（以下、経由地ノードという。）が検出された場合には、経由地までの経路も記憶される。
【０２５５】
学習により得られたHMMの各状態siは、地図上の所定の点（位置）を表し、状態siと状態sjが結ばれているとき、状態siから状態sjを移動する経路を表していると考えることができる。
【０２５６】
この場合、状態siに対応する各点は、端点、通過点、分岐点、ループのいずれかに分類することができる。端点とは、自己遷移以外の確率が極めて小さく（自己遷移以外の確率が所定の値以下であり）、次に移動可能な点がない点である。通過点とは、自己遷移以外に有意な遷移が一つある、換言すれば、次に移動可能な点が一つある点である。分岐点とは、自己遷移以外に有意な遷移が二つ以上ある、換言すれば、次に移動可能な点が二つ以上ある点である。ループとは、これまで通過した経路上のどれかと一致する点である。
【０２５７】
目的地への経路を探索する場合、異なる経路がある場合には、それぞれの経路について必要時間等の情報を提示することが望まれる。そこで、可能な経路を過不足なく探索するために、次の条件を設定する。
（１）一度分岐した経路は再度合流した場合でも、別の経路とみなす。
（２）探索中の経路が分岐点に達した場合に、未探索リストを作成し、未探索リストの分岐先の探索を行う。
（３）経路内に端点またはループが現れた場合、その経路の探索を終了する。なお、現在の点から、１つ前の点に経路を逆戻りする場合はループに含む。
【０２５８】
図２８は、予測メインプロセス部３３の目的地経由地予測部４２による、現在地ノード以降のツリー探索処理のフローチャートである。
【０２５９】
図２８の処理では、最初に、ステップＳ９１において、目的地経由地予測部４２は、予測メインプロセス部３３の現在地ノード推定部４１により推定された現在地ノードを取得し、注目するノードである注目ノードに設定する。
【０２６０】
ステップＳ９２において、目的地経由地予測部４２は、注目ノードに遷移先があるかを判定する。ステップＳ９２で、注目ノードに遷移先がないと判定された場合、処理は後述するステップＳ１０１に進む。
【０２６１】
一方、ステップＳ９２で、注目ノードに遷移先があると判定された場合、処理はステップＳ９３に進み、目的地経由地予測部４２は、遷移先が目的地ノードであるかを判定する。
【０２６２】
ステップＳ９３で、遷移先が目的地ノードであると判定された場合、処理はステップＳ９４に進み、目的地経由地予測部４２は、これまでの経路（状態ノード系列）を内部メモリの探索結果リストに記憶する。ステップＳ９４の後、処理はステップＳ１０１に進む。
【０２６３】
一方、ステップＳ９３で、遷移先が目的地ノードではないと判定された場合、処理はステップＳ９５に進み、目的地経由地予測部４２は、遷移先が経由地ノードであるかを判定する。
【０２６４】
ステップＳ９５で、遷移先が経由地ノードであると判定された場合、処理はステップＳ９５に進み、目的地経由地予測部４２は、これまでの経路（状態ノード系列）を内部メモリの探索結果リストに記憶する。
【０２６５】
目的地までの代表経路、到達確率、および所要時間を予測結果として出力するためには、探索結果リストには、遷移先が目的地であるときの経路のみを記憶すればよい。しかしながら、遷移先が経由地であるときの経路も記憶することにより、経由地までの経路、確率、および時間が必要になったときに即座に求めることができる。
【０２６６】
ステップＳ９５で遷移先が経由地ノードではないと判定された場合、または、ステップＳ９６の後、処理はステップＳ９７に進み、目的地経由地予測部４２は、遷移先が分岐点かを判定する。
【０２６７】
ステップＳ９７で、遷移先が分岐点であると判定された場合、処理はステップＳ９８に進み、目的地経由地予測部４２は、分岐先の２つの状態ノードを内部メモリの未探索リストに記憶する（追加する）。ステップＳ９８の後、処理はステップＳ１０１に進む。なお、分岐先が探索中の経路のいずれかの状態ノードである場合はループとなるので、目的地経由地予測部４２は、その分岐先の状態ノードについては未探索リストに記憶させない。
【０２６８】
ステップＳ９７で、遷移先が分岐点ではないと判定された場合、処理はステップＳ９９に進み、目的地経由地予測部４２は、遷移先が端点であるかを判定する。ステップＳ９９で、遷移先が端点であると判定された場合、処理はステップＳ１０１に進む。
【０２６９】
一方、ステップＳ９９で、遷移先が端点ではないと判定された場合、処理はステップＳ１００に進み、目的地経由地予測部４２は、遷移先の状態ノードを注目ノードに設定し、処理をステップＳ９２に戻す。即ち、遷移先が、目的地ノード、経由地ノード、分岐点、および端点のいずれでもない場合には、探索対象の状態ノードが、遷移先の次の状態ノードに進められる。
【０２７０】
ステップＳ９４，Ｓ９８、またはＳ９９の処理の後、処理がステップＳ１０１に進められた場合、目的地経由地予測部４２は、未探索リストに登録されている状態ノードがあるか、即ち、未探索の分岐先があるかを判定する。
【０２７１】
ステップＳ１０１で、未探索の分岐先があると判定された場合、処理はステップＳ１０２に進み、目的地経由地予測部４２は、未探索リストの最上位の分岐先の状態ノードを、注目ノードに設定し、注目ノードまでの経路を読み出す。そして、処理がステップＳ９２に戻される。
【０２７２】
一方、ステップＳ１０１で、未探索の分岐先がないと判定された場合、ツリー探索処理は終了する。
【０２７３】
以上のように、ツリー探索処理では、ユーザの現在地ノードから遷移可能な状態ノードでなるツリー構造において、現在地ノードを出発点として、目的地ノード若しくは遷移先のない終端ノード（端点）になるまで全ての状態ノードを探索する処理が行われる。そして、ユーザの現在地から目的地までの経路が、現在地ノードからの状態ノード系列として、探索結果リストに記憶される。なお、ツリー探索処理は、探索回数が終了条件としての所定の回数を満たすまで探索するようにしてもよい。
【０２７４】
［ツリー探索処理の例］
図２９を参照して、目的地経由地予測部４２のツリー探索処理についてさらに説明する。
【０２７５】
図２９の例において、状態s１が現在地である場合、次のような３通りの経路が少なくとも探索されることになる。１つめの経路は、状態s１から状態s５，状態s６等を経由して状態s１０までの経路（以下、経路Ａともいう。）である。２つめの経路は、状態s１から状態s５，状態s１１，状態s１４，状態s２３等を経由して状態s２９までの経路（以下、経路Ｂともいう。）である。３つめの経路は、状態s１から状態s５，状態s１１，状態s１９，状態s２３等を経由して状態s２９までの経路（以下、経路Ｃともいう。）である。
【０２７６】
目的地経由地予測部４２は、探索された各経路が選択される確率（経路の選択確率）を計算する。経路の選択確率は、経路を構成する状態間の遷移確率を順次乗算することで求められる。ただし、次の状態に遷移する場合のみを考慮し、その場所に滞留する場合は考慮する必要がないので、学習により求められた各状態の状態遷移確率aijから、自己遷移確率を除いて規格化された遷移確率[aij]を用いて、経路の選択確率が求められる。
【０２７７】
自己遷移確率を除いて規格化された遷移確率[aij]は、次式（１２）で表すことができる。
【数８】
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【０２７８】
したがって、例えば、図２９の状態s５の状態遷移確率aijが、自己遷移確率a５，５＝０．５，遷移確率a５，６＝０．２，遷移確率a５，１１＝０．３である場合、状態s５から状態s６または状態s１１に分岐する場合の遷移確率[a５，６]および遷移確率[a５，１１]は、それぞれ、０．４，０．６となる。
【０２７９】
探索された経路の状態siのノード番号ｉが、（ｙ１，ｙ２，・・・，ｙｎ）であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式（１３）で表すことができる。
【数９】
【０２８０】
なお、実際には、通過点での規格化された遷移確率[aij]は１であるので、経路の選択確率は、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。従って、目的地経由地予測部４２は、図２８のツリー探索処理を実行しながら、同時に、選択された経路の選択確率を式（１３）により計算することができる。
【０２８１】
図２９の例では、経路Ａの選択確率は、０．４である。また、経路Ｂの選択確率は、０．２４＝０．６×０．４である。経路Ｃの選択確率は、０．３６＝０．６×０．６である。そして、計算された経路の選択確率の総和は１＝０．４＋０．２４＋０．３６であり、過不足ない探索を実現することができることがわかる。
【０２８２】
図２９の例では、現在地の状態s１から注目ノードが順次進められ、状態s４が注目ノードであるとき、遷移先の状態s５が分岐点であるため、図２８のステップＳ９８が実行され、図３０Ａに示されるように、分岐先の状態s１１と状態s６が未探索リストに記憶される。ここで、状態s１１と状態s６では、状態s１１の選択確率が高いため、状態s１１が未探索リストの上位に記憶される。
【０２８３】
そして、図２８のステップＳ１０１およびＳ１０２が実行され、未探索リストの上位に記憶されている、状態s１１が注目ノードに設定され、状態s１１以降の経路が探索される。状態s１１が注目ノードに設定されたとき、図３０Ｂに示されるように、未探索リストから、状態s１１が削除される。
【０２８４】
そして、状態s１１を注目ノードとして探索が進められると、状態s１４と状態s１９の分岐先が検出されるので、図２８のステップＳ９８が実行され、状態s１４と状態s１９が未探索リストに記憶される。このとき、状態s１４と状態s１９は、現在の未探索リストの最上位に記憶され、また、状態s１４と状態s１９では、状態s１９の選択確率が高いため、状態s１９が状態s１４より上位に記憶される。従って、未探索リストは、図３０Ｃに示されるようになる。
【０２８５】
以下同様に、図２８のステップＳ１０１およびＳ１０２が実行され、未探索リストの上位に記憶されている、状態s１９が注目ノードに設定され、状態s１９以降の経路が探索される。状態s１９が注目ノードに設定されたとき、図３０Ｄに示されるように、未探索リストから、状態s１９が削除される。
【０２８６】
以上のように、目的地経由地予測部４２によるツリー探索処理は、検出された分岐先を未探索リストの最上位に記録させることで、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される。
【０２８７】
なお、探索の深さが深くなる、換言すれば、現在地ノードを最上位として下位の階層が深くなることで、全てを探索することが難しいことも考えられる。そのような場合には、例えば、１）遷移確率の低い分岐先は探索しない、２）生起確率の低い経路は探索しない、３）探索する深さに制限を加える、４）探索する枝の数に制限を加える、などの条件を加えて、途中で探索を終了するようにしてもよい。
【０２８８】
図３１は、ツリー探索処理における探索結果リストの例を示している。
【０２８９】
深さ優先アルゴリズムによりツリー探索処理を行うことにより、探索結果リストには、選択確率の高い経路から順に登録される。
【０２９０】
図３１の例では、探索結果リストの１番目には、目的地ｇ１までの経路Ｒ１（ｒ１，ｒ２，ｒ３，ｒ４）が登録され、この経路Ｒ１が選択される確率はＰ１で、経路Ｒ１を使って目的地ｇ１までにかかる時間がＴ１である。探索結果リストの２番目には、目的地ｇ２までの経路Ｒ２（ｒ１，ｒ２，ｒ３，ｒ５）が登録され、この経路Ｒ２が選択される確率はＰ２で、経路Ｒ２を使って目的地ｇ２までにかかる時間がＴ２である。探索結果リストの３番目には、目的地ｇ３までの経路Ｒ３（ｒ１，ｒ２，ｒ６）が登録され、この経路Ｒ３が選択される確率はＰ３で、経路Ｒ３を使って目的地ｇ３までにかかる時間がＴ３である。
【０２９１】
探索結果リストの４番目には、経由地ｗ２までの経路Ｒ４（ｒ１，ｒ２，ｒ７）が登録され、この経路Ｒ４が選択される確率はＰ４で、経路Ｒ４を使って経由地ｗ２までにかかる時間がＴ４である。探索結果リストの５番目には、経由地ｗ１までの経路Ｒ５（ｒ１，ｒ８）が登録され、この経路Ｒ５が選択される確率はＰ５で、経路Ｒ５を使って経由地ｗ１までにかかる時間がＴ５である。
【０２９２】
探索結果リストの６番目には、目的地ｇ３までの経路Ｒ６（ｒ１，ｒ８，ｗ１，ｒ８，ｒ９）が登録され、この経路Ｒ６が選択される確率はＰ６で、経路Ｒ６を使って目的地ｇ３までにかかる時間がＴ６である。探索結果リストの７番目には、この経路Ｒ７が選択される確率はＰ７で、目的地ｇ２までの経路Ｒ７（ｒ１，ｒ１０，ｒ１１）が登録され、経路Ｒ７を使って目的地ｇ２までにかかる時間がＴ７である。
【０２９３】
目的地または経由地まで、各経路が選択される確率は、上述した式（１３）により計算される。さらに、目的地までの経路が複数存在する場合、その目的地までの複数の経路の選択確率の和が、目的地の到達確率となる。
【０２９４】
従って、図３１の例では、目的地ｇ２へ行くには、経路Ｒ２を利用する場合と、経路Ｒ７を利用する場合があり得るので、目的地ｇ２の到達確率は、は（Ｐ２＋Ｐ７）となる。同様に、目的地ｇ３へ行くには、経路Ｒ３を利用する場合と、経路Ｒ６を利用する場合があり得るので、目的地ｇ３の到達確率は、は（Ｐ３＋Ｐ６）となる。なお、目的地ｇ１の到達確率は、経路Ｒ１が選択される確率Ｐ１と同一である。
【０２９５】
［予測ポストプロセス部３４の処理］
次に、予測ポストプロセス部３４が行う処理について説明する。
【０２９６】
目的地または経由地まで、選択された経路で移動したときにかかる時間の求め方について説明する。
【０２９７】
例えば、現在時刻ｔ１の現在地が状態ｓｙ１であり、時刻（ｔ１，ｔ２，・・・，ｔｇ）における決定された経路が（ｓｙ１，ｓｙ２，・・・，ｓｙｇ）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ１，ｙ２，・・・，ｙｇ）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０２９８】
現在時刻ｔ１での現在地ｙ１は、現在地ノード推定部４１により確定しているので、現在時刻ｔ１の現在地がｙ１である確率Ｐｙ１（ｔ１）は、
Ｐｙ１（ｔ１）＝１である。
また、現在時刻ｔ１にｙ１以外の他の状態にいる確率は０である。
【０２９９】
一方、所定の時刻ｔｎにノード番号ｙｎにいる確率Ｐｙｎ（ｔｎ）は、
【数１０】
で表すことができる。式（１４）の右辺第一項は、もともとその位置ｙｎにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙｎ−１から位置ｙｎに遷移してきた場合の確率を表している。式（１４）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０３００】
目的地ｙｇへ到達するときの時刻ｔｇの予測値<ｔｇ>は、「その直前の時刻ｔｇ−１に目的地ｙｇの１つ前の位置ｙｇ−１にいて、時刻ｔｇに目的地ｙｇに移動する確率」を用いて、
【数１１】
と表すことができる。
【０３０１】
即ち、予測値<ｔｇ>は、現在時刻から、「その直前の時刻ｔｇ−１に状態ｓｙｇの１つ前の状態ｓｙｇ−１にいて、時刻ｔｇに状態ｓｙｇに移動するとき」までの時間の期待値で表される。
【０３０２】
以上より、所定の目的地または経由地まで、選択された経路で移動したときにかかる時間は、上述した式（１５）の予測値<ｔｇ>により求められる。
【０３０３】
図３１の例を使用して、目的地までの経路が探索された場合に、代表経路として選択する代表経路選択処理について説明する。
【０３０４】
図３１のような探索結果リストが得られた場合、探索結果リストには、選択確率が高いものから順に（上位に）登録されるので、選択確率が上位であり、目的地も異なる、探索結果リストの１番目乃至３番目が予測結果として出力される。即ち、経目的地ｇ１とその経路Ｒ１、目的地ｇ２とその経路Ｒ２、目的地ｇ３とその経路Ｒ３が、目的地とその代表経路として選択される。
【０３０５】
次に、探索結果リストの４番目および５番目は経由地までの経路であるためスキップされ、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６を代表経路とするかが検討される。この経路Ｒ６は、既に代表経路として選択されている、同一の目的地ｇ３の経路Ｒ３には含まれていない経由地ｗ１を利用するものとなっている。したがって、目的地ｇ３へ到達するための経路Ｒ６も、代表経路として選択される。
【０３０６】
次に、探索結果リストの７番目の、目的地ｇ２へ到達するための経路Ｒ７を代表経路とするかが検討される。この経路Ｒ７は、既に代表経路として選択されている、同一の目的地ｇ２と同じく、所定の経由地を経由しないものとなっている。したがって、目的地ｇ２へ到達するための経路Ｒ７は、代表経路として選択されない。
【０３０７】
このように、代表経路選択処理では、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路は、同一目的地であっても、予測結果として提示することができる。
【０３０８】
なお、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６は、［背景技術］に示した先願２の方法では、経由地ｗ１で探索が終了されていた。しかしながら、予測システム１によれば、経由地ｗ１で終了することなく、経由地ｗ１を利用して目的地ｇ３へ到達する経路まで探索することが可能となっている。
【０３０９】
予測システム１によれば、学習により得られた状態ノードに、目的地と経由地を区別して属性を付与することで、第１と第２の課題を解決することができる。
【０３１０】
図３２は、予測ポストプロセス部３４が行う代表経路選択処理のフローチャートである。
【０３１１】
初めに、ステップＳ１２１において、予測ポストプロセス部３４は、目的地経由地予測部４２で作成された探索結果リストから、経由地までの経路を除外し、目的地のみの探索結果リストである目的地リストを生成する。
【０３１２】
ステップＳ１２２において、予測ポストプロセス部３４は、目的地リストを目的地別に並び替えた目的地別目的地リストに変更する。このとき、予測ポストプロセス部３４は、同一の目的地内における順位を変えないように目的地別目的地リストを生成する。
【０３１３】
ステップＳ１２３において、予測ポストプロセス部３４は、目的地ごとの到達確率を算出する。目的地までの経路が１つしかない場合には、その経路の選択確率が到達確率となり、目的地まで複数の経路が存在する場合には、複数の選択確率（生起確率）の和が、その目的地の到達確率となる。
【０３１４】
ステップＳ１２４において、予測ポストプロセス部３４は、代表経路の選択に経由地を考慮するかを判定する。ステップＳ１２４で、経由地を考慮しないと判定された場合、処理はステップＳ１２５に進み、予測ポストプロセス部３４は、目的地別に、最上位の経路を、各目的地の代表経路として選択し、処理を終了する。その結果、目的地まで複数の経路が存在する場合には、選択確率の高い目的地までの経路が、各目的地の代表経路とされ、その所要時間が、目的地までの所要時間として提示される。なお、目的地が多数ある場合には、上位から、予め設定した個数の目的地のみを提示するようにさせることができる。
【０３１５】
一方、ステップＳ１２４で、経由地を考慮すると判定された場合、処理はステップＳ１２６に進み、予測ポストプロセス部３４は、目的地別目的地リストを、経由地なしの目的地別目的地リストと、経由地ありの目的地別目的地リストに分類する。
【０３１６】
そして、ステップＳ１２７において、予測ポストプロセス部３４は、経由地なしの目的地別目的地リストから、目的地別に、最上位の経路を代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地なしの経路が決定される。
【０３１７】
次に、ステップＳ１２８において、予測ポストプロセス部３４は、経由地ありの目的地別目的地リストを、さらに、経由地別に分類する。
【０３１８】
ステップＳ１２９において、予測ポストプロセス部３４は、経由地別の、経由地ありの目的地別目的地リストから、目的地別に、各経由地の最上位の経路を、代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地ありの経路が決定される。その結果、目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方が、各目的地の代表経路とされ、それぞれの所要時間が、目的地までの所要時間として提示される。
【０３１９】
以上により、代表経路選択処理は終了する。このように、目的地への経路が複数存在する場合、生起確率の上位を複数提示するよりも、経由地によって分類して提示する方が、ユーザが実際に感じる予測に近いものとすることができる。
【０３２０】
［予測ブロック１３全体の処理］
図３３のフローチャートを参照して、予測ブロック１３全体の処理について説明する。
【０３２１】
初めに、ステップＳ１４１において、バッファリング部３１は、予測処理のため、リアルタイムに取得される移動履歴データをバッファリングする。
【０３２２】
ステップＳ１４２において、予測プリプロセス部３２は、予測プリプロセス処理を実行する。具体的には、学習プリプロセス部２２が行う学習プリプロセス処理と同様の、移動履歴データの接続および分割の処理、移動履歴データの明らかな異常を除去する処理、および、欠落データを補完する処理を実行する。但し、移動履歴データを分割する際の基準となる滞在閾値時間は、学習プリプロセス処理と異なる時間であってもよい。
【０３２３】
ステップＳ１４３において、予測メインプロセス部３３は、学習ブロック１１の学習により得られたユーザ活動モデルのパラメータを、ユーザ別モデルパラメータ記憶部１２から取得する。このパラメータを取得する処理は、図３３の目的地を予測する処理とは別に、予め実行するようにしてもよい。
【０３２４】
ステップＳ１４４において、予測メインプロセス部３３の現在地ノード推定部４１は、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する状態ノード（現在地ノード）を推定する。より具体的には、現在地ノード推定部４１は、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、移動履歴データに対応する状態ノード系列データを算出する。そして、現在地ノード推定部４１は、状態ノード系列データの最後の状態ノードを現在地ノードとする。状態ノード系列データの算出には、ビタビアルゴリズムが採用される。
【０３２５】
ステップＳ１４５において、予測メインプロセス部３３の目的地経由地予測部４２は、図２８を参照して説明した、現在地ノード以降のツリー探索処理を実行する。ツリー探索処理と同時に、目的地および経由地までの経路（ノード系列）の生起確率も、式（１３）により求められる。
【０３２６】
ステップＳ１４６において、予測ポストプロセス部３４は、図３２を参照して説明した、代表経路の選択処理を実行する。
【０３２７】
ステップＳ１４７において、予測ポストプロセス部３４は、上述した式（１５）により、選択された各代表経路の所要時間を算出する。
【０３２８】
ステップＳ１４８において、予測ポストプロセス部３４は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力して、処理を終了する。
【０３２９】
以上のように、予測ブロック１３の処理では、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られたユーザ活動モデルとを用いて、ユーザの現在地から目的地までの経路が探索される。学習により得られた状態ノードに目的地と経由地の属性が付与されているので、経由地を目的地として予測することを防止することができる。
【０３３０】
また、学習により得られた状態ノードに目的地と経由地の属性が付与されているので、同一目的地への経路であっても、経由地なしの経路と、経由地ありの経路を代表経路として出力することができる。
【０３３１】
［コンピュータの構成例］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０３３２】
図３４は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３３３】
コンピュータにおいて、CPU（Central Processing Unit）２２１，ROM（Read Only Memory）２２２，RAM（Random Access Memory）２２３は、バス２２４により相互に接続されている。
【０３３４】
バス２２４には、さらに、入出力インタフェース２２５が接続されている。入出力インタフェース２２５には、入力部２２６、出力部２２７、記憶部２２８、通信部２２９、ドライブ２３０、およびGPSセンサ２３１が接続されている。
【０３３５】
入力部２２６は、キーボード、マウス、マイクロホンなどよりなる。出力部２２７は、ディスプレイ、スピーカなどよりなる。記憶部２２８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２２９は、ネットワークインタフェースなどよりなる。ドライブ２３０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２３２を駆動する。上述のセンサデバイスとしてのGPSセンサ２３１は、現在地の位置（緯度および経度）のデータと、そのときの時刻からなる３次元データを出力する。
【０３３６】
以上のように構成されるコンピュータでは、CPU２２１が、例えば、記憶部２２８に記憶されているプログラムを、入出力インタフェース２２５及びバス２２４を介して、RAM２２３にロードして実行することにより、上述した一連の処理が行われる。
【０３３７】
コンピュータ（CPU２２１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２３２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０３３８】
コンピュータでは、プログラムは、リムーバブル記録媒体２３２をドライブ２３０に装着することにより、入出力インタフェース２２５を介して、記憶部２２８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２２９で受信し、記憶部２２８にインストールすることができる。その他、プログラムは、ROM２２２や記憶部２２８に、あらかじめインストールしておくことができる。
【０３３９】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０３４０】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０３４１】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０３４２】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０３４３】
１ 予測システム， １１ 学習ブロック， １３ 予測ブロック， ２２ 学習プリプロセス部， ２３ 学習メインプロセス部， ２４ 学習ポストプロセス部， ２５ 目的地経由地検出部， ３２ 予測プリプロセス部， ３３ 予測メインプロセス部， ３４ 予測ポストプロセス部， ４１ 現在地ノード推定部， ４２ 目的地経由地予測部， ７４ 移動属性識別付与部， ７５ 滞在状態加工部， ９２ 移動属性識別部， ９３ 移動属性付与部
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、およびプログラムに関し、特に、より正確に、目的地までの経路および所要時間を予測することができるようにするデータ処理装置、データ処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０号（以下、先願１という）として先に提案している。先願１の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。先願１では、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの移動履歴の時系列データを学習した確率的状態遷移モデルを用いて、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【０００４】
さらに、本出願人は、先願１をさらに発展させ、「所定時間後」という現在時刻からの経過時間の指定がない場合であっても、複数の目的地への到達確率、経路、時間を予測する方法を、特願２００９−２０８０６４号（以下、先願２という）として提案した。先願２の方法では、確率的状態遷移モデルを構成するノードに、”移動状態”かまたは”滞在状態”の属性が付与された。そして、確率的状態遷移モデルを構成するノードの中から、目的地のノードとして”滞在状態”のノードを見つけることで、目的地の候補を自動的に検出することができた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００６】
【非特許文献１】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、先願２の予測方法では、次のような事象が発生していた。第１に、予測される目的地が実際の目的地ではなく、途中の経由地とすることがあった。これにより、途中の経由地から実際の目的地までが予測されないことがあった（第1の課題）。例えば、帰宅途中の駅での電車乗り換えや本屋への立ち寄りなどのため、所定時間滞在した場所が目的地と認識され、本来の目的地である自宅までの経路を予測できない場合があった。
【０００８】
第２に、予測結果として、ほぼ同一の経路を通る、似たような経路が複数提示され、ユーザにとって有益なその他の経路がユーザに提示なされないことがあった（第２の課題）。これは、頻繁に通り、バリエーションの多い経路と、頻繁に通らず、バリエーションの少ない経路とをうまく区別できないことに起因する。
【０００９】
本発明は、このような状況に鑑みてなされたものであり、より正確に、目的地までの経路および所要時間を予測することができるようにするものである。
【課題を解決するための手段】
【００１０】
本発明の一側面のデータ処理装置は、学習用データとして取得される、ユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、探索された前記目的地への到達確率と所要時間を算出する算出手段とを備える。
【００１１】
本発明の一側面のデータ処理方法は、ユーザの移動履歴データを処理するデータ処理装置が、学習用データとして取得される前記移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習し、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、探索された前記目的地への到達確率と所要時間を算出するステップを含む。
【００１２】
本発明の一側面のプログラムは、コンピュータを、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、探索された前記目的地への到達確率と所要時間を算出する算出手段として機能させるためのものである。
【００１３】
本発明の一側面においては、学習用データとして取得される移動履歴データが、ユーザの活動を表す確率モデルで表され、そのパラメータが学習され、学習により得られたパラメータを用いた確率モデルの状態ノードのうち、目的地および経由地に相当する目的地ノードおよび経由地ノードが推定され、学習用データとは別の、現在から所定時間以内のユーザの移動履歴データが、学習により得られたパラメータを用いた確率モデルに入力され、ユーザの現在地に相当する現在地ノードが推定され、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られた確率モデルとを用いて、ユーザの現在地から目的地までの経路が探索され、探索された目的地への到達確率と所要時間が算出される。
【発明の効果】
【００１４】
本発明の一側面によれば、より正確に、目的地までの経路および所要時間を予測することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【図２】予測システムのハードウエア構成例を示すブロック図である。
【図３】移動履歴データの例を示す図である。
【図４】HMMの例を示す図である。
【図５】left-to-right型のHMMの例を示す図である。
【図６】スパース制約を与えたHMMの例を示す図である。
【図７】学習プリプロセス部の詳細構成例を示すブロック図である。
【図８】学習プリプロセス部の処理について説明する図である。
【図９】移動属性識別付与部の詳細構成例を示すブロック図である。
【図１０】移動属性識別部の学習器の構成例を示すブロック図である。
【図１１】行動状態をカテゴリごとに分類する場合の分類例を示す図である。
【図１２】行動状態ラベリング部の処理例を説明する図である。
【図１３】行動状態ラベリング部の処理例を説明する図である。
【図１４】図１０の行動状態学習部の構成例を示すブロック図である。
【図１５】移動属性識別部の詳細構成例を示すブロック図である。
【図１６】移動属性識別部の学習器のその他の構成例を示すブロック図である。
【図１７】移動属性識別部のその他の構成例を示すブロック図である。
【図１８】学習プリプロセス部の処理を説明するフローチャートである。
【図１９】学習メインプロセス処理を説明するフローチャートである。
【図２０】学習ポストプロセス部の詳細構成例を示すブロック図である。
【図２１】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２２】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２３】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２４】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２５】状態系列修正部の状態系列データの修正処理について説明する図である。
【図２６】目的地経由地検出部の処理について説明する図である。
【図２７】学習ブロック全体の処理を説明するフローチャートである。
【図２８】ツリー探索処理を説明するフローチャートである。
【図２９】ツリー探索処理をさらに説明する図である。
【図３０】ツリー探索処理をさらに説明する図である。
【図３１】ツリー探索処理における探索結果リストの例を示す図である。
【図３２】代表経路選択処理を説明するフローチャートである。
【図３３】予測ブロック全体の処理を説明するフローチャートである。
【図３４】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
［予測システムの構成例］
図１は、本発明を適用した予測システムの一実施の形態の構成例を示している。
【００１７】
図１の予測システム１は、学習ブロック１１、ユーザ別モデルパラメータ記憶部１２、および予測ブロック１３により構成される。
【００１８】
学習ブロック１１には、GPS (Global Positioning System)センサなどのセンサデバイス（不図示）において、所定の期間に取得された、所定の時刻におけるユーザの位置（緯度と経度）を示す時系列データが供給される。即ち、学習ブロック１１には、一定時間間隔（たとえば、１５秒間隔）で順次取得された位置（緯度および経度）のデータと、そのときの時刻の３次元からなる、ユーザの移動経路を示す時系列データ（以下、移動履歴データという。）が供給される。なお、時系列データを構成する、緯度、経度、および時刻の１組のデータを、適宜、３次元データともいう。
【００１９】
学習ブロック１１は、ユーザの移動履歴データを用いて、ユーザの活動モデル（ユーザの行動・活動パターンを表した状態モデル）を、確率的状態遷移モデルとして学習する学習処理を行う。
【００２０】
学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM（Hidden Markov Model）などの、隠れ状態を含む確率モデルを採用することができる。予測システム１では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図４乃至図６を参照して後述する。
【００２１】
ユーザ別モデルパラメータ記憶部１２は、学習ブロック１１の学習により得られた、ユーザの活動モデルを表すパラメータを記憶する。
【００２２】
予測ブロック１３は、学習ブロック１１の学習により得られたユーザ活動モデルのパラメータをユーザ別モデルパラメータ記憶部１２から取得する。そして、予測ブロック１３は、新たに取得されたユーザの移動履歴データに対し、学習により得られたパラメータを用いたユーザ活動モデルを用いて、ユーザの現在地を推定し、さらに現在地からの移動先となる目的地を予測する。さらに、予測ブロック１３は、予測した目的地までの到達確率、経路、および到達時間（所要時間）も算出する。なお、目的地は１つだけとは限らず、複数の目的地が予測されることもある。
【００２３】
学習ブロック１１および予測ブロック１３の詳細について説明する。
【００２４】
学習ブロック１１は、履歴データ蓄積部２１、学習プリプロセス部２２、学習メインプロセス部２３、学習ポストプロセス部２４、および目的地経由地検出部２５により構成される。
【００２５】
履歴データ蓄積部２１は、センサデバイスから供給される、ユーザの移動履歴データを、学習用データとして蓄積（記憶）する。履歴データ蓄積部２１は、移動履歴データを、必要に応じて学習プリプロセス部２２に供給する。
【００２６】
学習プリプロセス部２２は、センサデバイスから生じる課題を解決する。具体的には、学習プリプロセス部２２は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。また、学習プリプロセス部２２は、移動履歴データを構成する３次元データそれぞれに対し、同一場所に滞在（停止）している”滞在状態”か、または、移動している”移動状態”のいずれかの移動属性を付与する。移動属性付与後の移動履歴データが、学習メインプロセス部２３と目的地経由地検出部２５に供給される。
【００２７】
学習メインプロセス部２３は、ユーザ活動モデルを確率的状態遷移モデルにモデル化する。即ち、学習メインプロセス部２３は、ユーザの移動履歴を確率的状態遷移モデルにモデル化したときのパラメータを求める。学習により得られたユーザ活動モデルのパラメータは、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給される。
【００２８】
学習ポストプロセス部２４は、学習メインプロセス部２３の学習により得られたユーザ活動モデルを用いて、移動履歴データを構成する各３次元データを、ユーザ活動モデルの状態ノードに変換する。即ち、学習ポストプロセス部２４は、移動履歴データに対応する、ユーザ活動モデルの状態ノードの時系列データ（状態ノード系列データ）を生成する。その際、学習ポストプロセス部２４は、一般常識に基づくバイアスを加えることで、状態ノード系列データの一部修正を行う。学習ポストプロセス部２４は、変換および修正後の状態ノード系列データを目的地経由地検出部２５に供給する。
【００２９】
目的地経由地検出部２５は、学習プリプロセス部２２から供給された移動属性付与後の移動履歴データと、学習ポストプロセス部２４から供給された状態ノード系列データとを対応付ける。即ち、目的地経由地検出部２５は、移動履歴データを構成する各３次元データに、ユーザ活動モデルの状態ノードを割り当てる。
【００３０】
そして、目的地経由地検出部２５は、状態ノード系列データの各状態ノードのうち、移動属性が”滞在状態”の３次元データに対応する状態ノードに、目的地または経由地の属性を付与する。これにより、ユーザの移動履歴内の所定の場所（に対応する状態ノード）が、目的地かまたは経由地に割り当てられる。目的地経由地検出部２５により、状態ノードに付与された目的地、経由地の属性についての情報は、ユーザ別モデルパラメータ記憶部１２に供給され、記憶される。
【００３１】
予測ブロック１３は、バッファリング部３１、予測プリプロセス部３２、予測メインプロセス部３３、および、予測ポストプロセス部３４により構成される。
【００３２】
バッファリング部３１は、予測処理のためのリアルタイムに取得される移動履歴データをバッファリングする（記憶する）。なお、予測処理のための移動履歴データとしては、学習処理時の移動履歴データよりも短い期間のデータ、例えば、１００ステップ程度の移動履歴データがあれば十分である。バッファリング部３１は、常に、所定期間分の最新の移動履歴データを記憶するようにし、新たなデータが取得されたとき、記憶されているデータのうち最も古いデータを消去する。
【００３３】
予測プリプロセス部３２は、学習プリプロセス部２２と同様、センサデバイスから生じる課題を解決する。即ち、予測プリプロセス部３２は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。
【００３４】
予測メインプロセス部３３は、現在地ノード推定部４１と目的地経由地予測部４２により構成される。予測メインプロセス部３３には、ユーザ別モデルパラメータ記憶部１２から、学習ブロック１１の学習により得られた、ユーザ活動モデルを表すパラメータが供給される。
【００３５】
現在地ノード推定部４１は、予測プリプロセス部３２から供給される移動履歴データと、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する状態ノード（現在地ノード）を推定する。状態ノードの推定には、ビタビ最尤推定や軟判定ビタビ推定を採用することができる。
【００３６】
目的地経由地予測部４２は、現在地ノード推定部４１で推定された現在地ノードから遷移可能な複数の状態ノードでなるツリー構造において、目的地の状態ノード（目的地ノード）までのノード系列とその生起確率を算出する。なお、目的地の状態ノードへのノード系列（経路）には経由地のノードが含まれる場合もあるので、目的地経由地予測部４２は、目的地と同時に経由地も予測する。
【００３７】
予測ポストプロセス部３４は、同一目的地までの複数の経路の選択確率（生起確率）の和を到達確率として求める。また、予測ポストプロセス部３４は、目的地への経路のうち代表となる１以上の経路（以下、代表経路という。）を選択し、代表経路の所要時間を算出する。そして、予測ポストプロセス部３４は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力する。なお、経路の生起確率の代わりに頻度、目的地への到達確率の代わりに到達頻度を、予測結果として出力してもよい。
【００３８】
［予測システムのハードウエア構成例］
以上のように構成される予測システム１は、例えば、図２に示されるハードウエア構成を採用することができる。即ち、図２は、予測システム１のハードウエア構成例を示すブロック図である。
【００３９】
図２において、予測システム１は、３台のモバイル端末５１−１乃至５１−３とサーバ５２とにより構成されている。モバイル端末５１−１乃至５１−３は、同一機能を有する同型のモバイル端末５１であるが、モバイル端末５１−１乃至５１−３では、それを所有するユーザが異なる。従って、図２では、３台のモバイル端末５１−１乃至５１−３のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末５１が存在する。
【００４０】
モバイル端末５１は、無線通信及びインターネット等のネットワークを介した通信により、サーバ５２とデータの授受を行うことができる。サーバ５２は、モバイル端末５１から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ５２は、データ処理の処理結果を無線通信等によりモバイル端末５１に送信する。
【００４１】
従って、モバイル端末５１とサーバ５２は、無線または有線による通信を行う通信部を少なくとも有する。
【００４２】
さらに、モバイル端末５１が、図１の予測ブロック１３を備え、サーバ５２が、図１の学習ブロック１１とユーザ別モデルパラメータ記憶部１２を備える構成を採用することができる。
【００４３】
この構成が採用される場合、例えば、学習処理において、モバイル端末５１のセンサデバイスにより取得された移動履歴データがサーバ５２に送信される。サーバ５２は、受信した学習用の移動履歴データに基づき、ユーザ活動モデルを学習し、記憶する。そして、予測処理において、モバイル端末５１が、学習により得られたユーザ活動モデルのパラメータを取得し、リアルタイムに取得される移動履歴データから、ユーザの現在地ノードを推定し、さらに、目的地ノードと、そこまでの到達確率、代表経路、および所要時間を算出する。そして、モバイル端末５１は、予測結果を図示せぬ液晶ディスプレイ等の表示部に表示する。
【００４４】
以上のようなモバイル端末５１とサーバ５２との間の役割分担は、それぞれのデータ処理装置としての処理能力や通信環境に応じて、適宜、決定することができる。
【００４５】
学習処理は、処理に要する１回あたりの時間は非常に長いが、それほど頻繁に処理する必要はない。従って、一般的には、携行可能なモバイル端末５１よりもサーバ５２の方が処理能力が高いので、サーバ５２に、一日に一回程度蓄積された移動履歴データに基づいて学習処理（パラメータの更新）を行わせるようにすることができる。
【００４６】
一方、予測処理は、時々刻々とリアルタイムに更新される移動履歴データに対応させて迅速に処理し、表示することが望ましいので、モバイル端末５１で処理を行う方が望ましい。通信環境がリッチであれば、サーバ５２に予測処理も行わせ、予測結果のみをサーバ５２から受信する方が、携行可能な小型化が要求されるモバイル端末５１の負荷が軽減され、望ましい。
【００４７】
また、モバイル端末５１単独で、データ処理装置として学習処理および予測処理を高速に行うことが可能である場合には、図１の予測システム１の構成すべてをモバイル端末５１が備えるようにすることも勿論可能である。
【００４８】
［入力される移動履歴データの例］
図３は、予測システム１で取得された移動履歴データの例を示している。図３において、横軸は経度を表し、縦軸は緯度を表している。
【００４９】
図３に示される移動履歴データは、実験者の１ヶ月半程度の期間に蓄積された移動履歴データを示している。図３に示されるように、移動履歴データは、主に、自宅周辺と、勤務先などの４か所の外出先を移動したデータとなっている。なお、この移動履歴データには、人工衛星を捕捉できず、位置が飛んでいるデータも含まれている。
【００５０】
［エルゴディックHMMについて］
次に、予測システム１が、学習モデルとして採用するエルゴディックHMMについて説明する。
【００５１】
図４は、HMMの例を示している。
【００５２】
HMMは、状態ノードと状態ノード間遷移とを有する状態遷移モデルである。
【００５３】
図４は、３状態のHMMの例を示している。
【００５４】
図４において（以降の図においても同様）、丸印は、状態ノードを表し、矢印は、状態ノードの遷移を表す。なお、以下において、状態ノードは、単に、ノードまたは状態ともいう。
【００５５】
また、図４において、si（図４では、i=1,2,3）は、状態を表し、aijは、状態siから状態sjへの状態遷移確率を表す。さらに、bj(x)は、状態sjへの状態遷移時に、観測値xが観測される出力確率密度関数を表し、πiは、状態siが初期状態である初期確率を表す。
【００５６】
なお、出力確率密度関数bj(x)としては、例えば、正規確率分布等が用いられる。
【００５７】
ここで、HMM（連続HMM）は、状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiによって定義される。これらの状態遷移確率aij、出力確率密度関数bj(x)、及び初期確率πiを、HMMのパラメータλ={aij,bj(x), πi,i=1,2,・・・,M，j=1,2,・・・,M}という。Mは、HMMの状態数を表す。
【００５８】
HMMのパラメータλを推定する方法としては、Baum-Welchの最尤推定法が広く利用されている。Baum-Welchの最尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【００５９】
Baum-Welchの最尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測（生起）される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータλの推定が行われる。ここで、xtは、時刻tに観測される信号（サンプル値）を表し、Tは、時系列データの長さ（サンプル数）を表す。
【００６０】
Baum-Welchの最尤推定法については、例えば、“パターン認識と機械学習（下）”，Ｃ．Ｍ．ビショップ著，P. 333（英語原書：“Pattern Recognition and Machine Learning (Information Science and Statistics) ”，Christopher M. BishopSpringer, New York, 2006.）（以下、文献Ａと称する）に記載されている。
【００６１】
なお、Baum-Welchの最尤推定法は、尤度最大化に基づくパラメータ推定方法ではあるが、最適性を保証するものではなく、HMMの構造やパラメータλの初期値によっては、局所解（ローカルミニマム）に収束することがある。
【００６２】
HMMは、音声認識で広く利用されているが、音声認識で利用されるHMMでは、一般に、状態の数や状態遷移の仕方等はあらかじめ決定される。
【００６３】
図５は、音声認識で利用されるHMMの例を示している。
【００６４】
図５のHMMは、left-to-right型と呼ばれる。
【００６５】
図５では、状態数は３になっており、状態遷移は、自己遷移（状態siから状態siへの状態遷移）と、左から右隣の状態への状態遷移とのみを許す構造に制約されている。
【００６６】
図５のHMMのように、状態遷移に制約があるHMMに対して、図４に示した、状態遷移に制約がないHMM、すなわち、任意の状態siから任意の状態sjへの状態遷移が可能なHMMは、エルゴディック(Ergodic)HMMと呼ばれる。
【００６７】
エルゴディックHMMは、構造としては最も自由度の高いHMMであるが、状態数が多くなると、パラメータλの推定が困難となる。
【００６８】
例えば、エルゴディックHMMの状態数が、１０００である場合、状態遷移の数は、１００万（＝１０００×１０００）となる。
【００６９】
したがって、この場合、パラメータλのうちの、例えば、状態遷移確率aijについては、１００万個の状態遷移確率aijを推定することが必要となる。
【００７０】
そこで、状態に対して設定する状態遷移には、例えば、スパース(Sparse)な構造であるという制約（スパース制約）をかけることができる。
【００７１】
ここで、スパースな構造とは、任意の状態から任意の状態への状態遷移が可能なエルゴディックHMMのような密な状態遷移ではなく、ある状態から状態遷移することができる状態が非常に限定されている構造である。なお、ここでは、スパースな構造であっても、他の状態への状態遷移は、少なくとも１つ存在し、また、自己遷移は存在することとする。
【００７２】
図６は、スパース制約を与えたHMMを示している。
【００７３】
ここで、図６では、２つの状態を結ぶ双方向の矢印は、その２つの状態の一方から他方への状態遷移と、他方から一方への状態遷移とを表す。また、図６において、各状態は、自己遷移が可能であり、その自己遷移を表す矢印の図示は、省略されている。
【００７４】
図６では、１６個の状態が、２次元空間上に格子状に配置されている。すなわち、図６では、横方向に、４個の状態が配置され、縦方向にも、４個の状態が配置されている。
【００７５】
いま、横方向に隣接する状態どうしの距離、及び、縦方向に隣接する状態どうしの距離を、いずれも１とすると、図６Ａは、距離が１以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７６】
また、図６Ｂは、距離が√２以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【００７７】
図１の例では、予測システム１に、移動履歴データx=x1,x2,・・・,xTが供給され、学習ブロック１１は、移動履歴データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【００７８】
即ち、ユーザの移動軌跡を表す各時刻の位置（緯度経度）のデータが、HMMの状態sjのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。学習ブロック１１は、各状態sjに対応する地図上の一点（平均μj）とその分散値σj２、および状態遷移確率aijを最適化する。
【００７９】
なお、状態siの初期確率πiは、一様な値に設定することができる。例えば、M個の状態siそれぞれの初期確率πiが、1/Mに設定される。
【００８０】
現在地ノード推定部４１は、学習により得られたユーザ活動モデル（HMM）に対して、ビタビアルゴリズムを適用し、移動履歴データx=x1,x2,・・・,xTが観測される尤度を最も大にする状態遷移の過程（状態の系列）（パス）（以下、最尤パスともいう）を求める。これにより、ユーザの現在地に対応する状態siが認識される。
【００８１】
ここで、ビタビアルゴリズムとは、各状態siを始点とする状態遷移のパスの中で、時刻tに、状態siから状態sjに状態遷移する状態遷移確率aijと、その状態遷移において、移動履歴データx=x1,x2,・・・,xTのうちの時刻tのサンプル値xtが観測される確率（出力確率密度関数bj(x)から求められる出力確率）とを、処理後時系列データxの長さTに亘って累積した値（生起確率）を最大にするパス（最尤パス）を決定するアルゴリズムである。ビタビアルゴリズムの詳細については上述の文献ＡのP.347に記載されている。
【００８２】
［学習プリプロセス部２２の構成例］
図７は、学習ブロック１１の学習プリプロセス部２２の詳細構成例を示すブロック図である。
【００８３】
学習プリプロセス部２２は、データ接続分割部７１、データ異常除去部７２、再サンプリング処理部７３、移動属性識別付与部７４、および滞在状態加工部７５により構成される。
【００８４】
データ接続分割部７１は、移動履歴データの接続および分割の処理を行う。データ接続分割部７１には、移動履歴データが、センサデバイスから、１日単位などの所定の単位でログファイルとして供給される。従って、本来、ある目的地への移動途中で連続すべき移動履歴データが、日付を跨いだために分割されて取得されることがある。データ接続分割部７１は、そのような分割された移動履歴データを接続する。具体的には、データ接続分割部７１は、１つのログファイル内の最後の３次元（緯度、経度、時刻）データと、そのログファイルの次に作成されたログファイル内の最初の３次元データの時間差が所定の時間内であれば、それらのファイル内の移動履歴データを接続する。
【００８５】
また、例えば、GPSセンサは、トンネルや地下では人工衛星を捕捉することができないため、移動履歴データの取得間隔が長くなることがある。移動履歴データが長い時間欠落している場合には、ユーザがどこにいたかを推定することが難しくなる。そこで、データ接続分割部７１は、取得された移動履歴データにおいて、前後の取得時刻の間隔が所定の時間間隔（以下、欠落閾値時間という。）以上ある場合に、その間隔の前後で移動履歴データを分割する。ここで、欠落閾値時間は、例えば、５分、１０分、１時間などである。
【００８６】
データ異常除去部７２は、移動履歴データの明らかな異常を除去する処理を行う。例えば、ある時刻の位置のデータが、その前後の位置と１００ｍ以上も離れていて、跳躍している場合、その位置のデータは異常である。そこで、データ異常除去部７２は、ある時刻の位置のデータが、その前後の両方の位置と所定の距離以上離れている場合、その３次元データを移動履歴データから除去する。
【００８７】
再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを、線形補間等により補完する処理を行う。即ち、取得時刻の時間間隔が欠落閾値時間以上である場合には、データ接続分割部７１により、移動履歴データが分割されるが、欠落閾値時間未満のデータの欠落は残っている。そこで、再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを補完する。
【００８８】
移動属性識別付与部７４は、移動履歴の３次元データそれぞれが、同一場所に滞在（停止）している”滞在状態”か、または、移動している”移動状態”のいずれであるかの移動属性を識別し、付与する。これにより、移動履歴データの各３次元データに移動属性が付与された、移動属性付き移動履歴データが生成される。
【００８９】
滞在状態加工部７５は、移動属性識別付与部７４から供給される移動属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。より具体的には、滞在状態加工部７５は、”滞在状態”の移動属性が所定時間（以下、滞在閾値時間という。）以上継続している場合、その前後で移動履歴データを分割する。また、滞在状態加工部７５は、”滞在状態”の移動属性が滞在閾値時間未満で継続している場合には、その滞在閾値時間以内の所定時間続く、”滞在状態”の複数の３次元データの位置のデータをホールドする（同一位置のデータに修正する）。これにより、同一の目的地や経由地の移動履歴データに対して複数の”滞在状態”ノードが割り当てられることを防止することができる。換言すれば、同一の目的地や経由地を複数のノードで表現することを防止することができる。
【００９０】
［学習プリプロセス部２２の処理］
図８は、学習プリプロセス部２２の学習プリプロセス処理を概念的に示したイメージ図である。
【００９１】
図８上段に示される、再サンプリング処理部７３によるデータ補完後の移動履歴データ８１に対して、移動属性識別付与部７４が、”滞在状態”または”移動状態”の移動属性を識別し、付与する。その結果、図８中段に示される、移動属性付き移動履歴データ８２が生成される。
【００９２】
図８中段の移動属性付き移動履歴データ８２において、”ｍ１”および”ｍ２”は、”移動状態”の移動属性を表し、”ｕ”は、”滞在状態”の移動属性を表す。なお、”ｍ１”と”ｍ２”は、同じ”移動状態”でも、移動手段（車、バス、電車、徒歩など）が異なる。
【００９３】
そして、図８中段の、移動属性付き移動履歴データ８２に対して、滞在状態加工部７５により、移動履歴データを分割およびホールドする処理が実行され、図８下段の、移動属性付き移動履歴データ８３（８３Ａおよび８３Ｂ）が生成される。
【００９４】
移動属性付き移動履歴データ８３では、移動属性付き移動履歴データ８２において２回目に発生した”移動状態”の箇所（３次元データ）で分割処理が行われ、移動属性付き移動履歴データ８３Ａと８３Ｂに分割されている。
【００９５】
分割処理では、最初に、移動属性付き移動履歴データ８２の２回目に発生した”移動状態”までと、それ以降の複数の３次元データとで分割され、２つの移動属性付き移動履歴データ８３Ａおよび８３Ｂとされる。次に、分割後の移動属性付き移動履歴データ８３Ａおよび８３Ｂのうち、時間的に早い移動属性付き移動履歴データ８３Ａの最後の滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられる。これにより、不要な移動履歴データが削除されるので、学習時間を短縮することができる。
【００９６】
なお、図８の例では、移動属性付き移動履歴データ８２の３回目に発生した” 複数の移動状態”の３次元データも滞在閾値時間以上の”移動状態”が続くデータであり、同様の分割処理が行われている。しかし、分割後の後ろの３次元データが存在しないため、滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられるのみとなっている。
【００９７】
一方、移動属性付き移動履歴データ８３Ａのうち、１回目の”移動状態”の移動履歴データでは、ホールド処理が実行されている。ホールド処理後は、３つの”移動状態”の３次元データ｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ，ｙｋ），（ｔｋ＋１，ｘｋ＋１，ｙｋ＋１）｝が、｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ−１，ｙｋ−１），（ｔｋ＋１，ｘｋ−１，ｙｋ−１）｝となっている。即ち、位置のデータが”移動状態”の最初の位置のデータに修正されている。なお、ホールド処理では、位置のデータは、”移動状態”の最初の位置のデータに変更するのではなく、位置の平均値、”移動状態”の期間の真ん中の時刻の位置のデータ等に変更してもよい。
【００９８】
［移動属性識別付与部７４の構成例］
図９は、移動属性識別付与部７４の詳細構成例を示すブロック図である。
【００９９】
移動属性識別付与部７４は、移動速度演算部９１、移動属性識別部９２、および移動属性付与部９３により構成される。
【０１００】
移動速度演算部９１は、供給される移動履歴データから移動速度を演算する。
【０１０１】
具体的には、一定の時間間隔でｋステップ目（ｋ個目）に得られるときの３次元データを、時刻ｔｋ、経度ｙｋ、緯度ｘｋと表すと、ｋステップ目のｘ方向の移動速度ｖｘｋおよびｙ方向の移動速度ｖｙｋは、次式（１）により計算することができる。
【０１０２】
【数１】
【０１０３】
式（１）では、緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【０１０４】
また、移動速度演算部９１は、式（１）で得られる移動速度ｖｘｋおよびｖｙｋからさらに、式（２）で表されるｋステップ目の移動速度ｖｋと進行方向の変化θｋを求め、これを利用することができる。
【０１０５】
【数２】
【０１０６】
式（２）で表される移動速度ｖｋと進行方向の変化θｋを利用する方が、式（１）の移動速度ｖｘｋおよびｖｙｋよりも以下の点で、特徴をうまく取り出すことができる。
【０１０７】
１．移動速度ｖｘｋおよびｖｙｋのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段（電車や徒歩など）であっても角度が異なった場合に識別できない可能性があるが、移動速度ｖｋであればそのような可能性が少ない。
２．移動速度の絶対的な大きさ（｜ｖ｜）だけで学習すると、機器のノイズによって生じる｜ｖ｜のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
３．移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【０１０８】
以上の理由から、本実施の形態では、移動速度演算部９１は、移動速度のデータとして、式（２）で表される移動速度ｖｋと進行方向の変化θｋを求め、移動属性識別部９２に供給する。
【０１０９】
移動速度演算部９１は、移動速度ｖｋと進行方向の変化θｋの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理（前処理）を行うことができる。
【０１１０】
なお、センサデバイスのなかには、移動速度を出力できるものも存在する。そのようなセンサデバイスが採用されている場合、移動速度演算部９１を省略し、センサデバイスが出力する移動速度をそのまま利用することができる。以下では、進行方向の変化θｋを、進行方向θｋと略記する。
【０１１１】
移動属性識別部９２は、供給される移動速度に基づいて移動属性を識別し、認識結果を移動属性付与部９３に供給する。より具体的には、移動属性識別部９２は、ユーザの行動状態（移動状態）を確率的状態遷移モデル（HMM）として学習し、学習により得られた確率的状態遷移モデルを用いて移動属性を識別する。移動属性としては、少なくとも”滞在状態”と”移動状態”が存在する必要がある。本実施の形態では、図１１等を参照して後述するように、移動属性識別部９２は、”移動状態”を、さらに徒歩、自転車、車など、複数の移動手段によって分類した移動属性を出力する。
【０１１２】
移動属性付与部９３は、再サンプリング処理部７３からの、移動履歴データを構成する３次元データそれぞれに対し、移動属性識別部９２で認識された移動属性を付与し、移動属性付き移動履歴データを生成して、滞在状態加工部７５に出力する。
【０１１３】
次に、図１０乃至図１７を参照して、移動属性識別部９２で使用される、ユーザの行動状態を表した確率的状態遷移モデルのパラメータの求め方について説明する。
【０１１４】
［移動属性識別部９２の学習器の第１の構成例］
図１０は、カテゴリHMMにより、移動属性識別部９２で使用される確率的状態遷移モデルのパラメータを学習する学習器１００Aの構成例を示している。
【０１１５】
カテゴリHMMでは、学習する教師データが予めどのカテゴリ（クラス）に属するデータであるのかが既知であり、カテゴリごとにHMMのパラメータが学習される。
【０１１６】
学習器１００Aは、移動速度データ記憶部１０１、行動状態ラベリング部１０２、および行動状態学習部１０３により構成される。
【０１１７】
移動速度データ記憶部１０１は、学習用データとしての移動速度の時系列データを記憶する。
【０１１８】
行動状態ラベリング部１０２は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（カテゴリ）として付与する。行動状態ラベリング部１０２は、移動速度のデータに行動状態が対応付けられたラベル済み移動速度データを行動状態学習部１０３に供給する。例えば、ｋステップ目の移動速度ｖｋと進行方向θｋに対して、行動状態を表すラベルMを付与したデータが行動状態学習部１０３に供給される。
【０１１９】
行動状態学習部１０３は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データを、カテゴリごとに分類し、カテゴリ単位で、ユーザ活動モデル（HMM）のパラメータを学習する。学習の結果得られたカテゴリ毎のパラメータは移動属性識別部９２に供給される。
【０１２０】
［行動状態の分類例］
図１１は、行動状態をカテゴリごとに分類する場合の分類例を示している。
【０１２１】
図１１に示されるように、まず、ユーザの行動状態は、滞在状態と移動状態に分類することができる。本実施の形態では、移動属性識別部９２が認識するユーザの行動状態としては、上述したように、少なくとも滞在状態と移動状態が存在する必要があるので、この２つに分類することは必須である。
【０１２２】
さらに、移動状態は、移動手段によって、電車、車（バスなども含む）、自転車、徒歩に分類することができる。電車は、さらに、特急、快速、ローカルなどに分類することができ、車は、さらに、高速、一般道などに分類することができる。また、徒歩は、走る、普通、散歩などに分類することができる。
【０１２３】
本実施の形態では、ユーザの行動状態を、図１１において斜線で示される“滞在”、“電車（快速）”、“電車（ローカル）”、“車（高速）”、“車（一般道）”、“自転車”、および“徒歩”に分類することとする。なお、“電車（特急）”は、学習用データが得られなかったため省略した。
【０１２４】
なお、カテゴリの分類の仕方が図１１に示した例に限定されるものではないことは言うまでもない。また、移動手段による移動速度の変化はユーザによって大きく異なるものではないので、学習用データとしての移動速度の時系列データは、認識対象のユーザのものである必要はない。
【０１２５】
［行動状態ラベリング部１０２の処理例］
次に、図１２および図１３を参照して、行動状態ラベリング部１０２の処理例について説明する。
【０１２６】
図１２は、行動状態ラベリング部１０２に供給される移動速度の時系列データの例を示している。
【０１２７】
図１２では、行動状態ラベリング部１０２から供給される移動速度のデータ（ｖ，θ）を、（ｔ，ｖ）および（ｔ，θ）の形で示している。図１２において、四角（■）のプロットは移動速度ｖを表し、丸（●）のプロットは進行方向θを表している。また、横軸は時間ｔを表し、右側の縦軸は進行方向θを、左側の縦軸は移動速度ｖを表す。
【０１２８】
図１２の時間軸の下方に示されている“電車（ローカル）”、“徒歩”、“滞在”の文字は、説明のため付加したものである。図１２の時系列データの最初は、ユーザが電車（ローカル）で移動中である場合の移動速度のデータであり、次が“徒歩”で移動中である場合、その次が“滞在”である場合の移動速度のデータとなっている。
【０１２９】
ユーザが“電車（ローカル）”で移動している場合、電車が駅で停車し、出発するとき加速し、再度減速して駅に停車することを繰り返すので、移動速度ｖのプロットが繰り返し上下に振れるという特徴が表れている。なお、電車が停止している場合でも移動速度が０になっていないのは、移動平均によるフィルタリング処理を行っているためである。
【０１３０】
また、ユーザが“徒歩”で移動している場合と“滞在”している場合は、最も区別しにくい状態であるが、移動平均によるフィルタリング処理により、移動速度ｖに明らかな違いが見られる。また、“滞在”では、進行方向θが瞬時に大きく変化する特徴がみられ、“徒歩”との差別化が容易であることがわかる。このように、移動平均によるフィルタリング処理、および、ユーザの移動を移動速度ｖと進行方向θで表すことにより、“徒歩”と“滞在”の区別が容易になっていることがわかる。
【０１３１】
なお、“電車（ローカル）”と“徒歩”の間の部分は、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分である。
【０１３２】
図１３は、図１２に示した時系列データに対して、ラベル付けを行う例を示している。
【０１３３】
例えば、行動状態ラベリング部１０２は、図１２に示した移動速度のデータをディスプレイに表示する。そして、ユーザは、ディスプレイに表示された移動速度のデータのうち、ラベル付けをしたい部分を矩形の領域で囲む操作を、マウスなどにより行う。また、ユーザは、指定したデータに対して付与するラベルをキーボードなどから入力する。行動状態ラベリング部１０２は、ユーザによって指定された矩形領域に含まれる移動速度のデータに、入力されたラベルを付与することにより、ラベル付けを行う。
【０１３４】
図１３では、“徒歩”に相当する部分の移動速度のデータを矩形の領域で指示した例が示されている。なお、このとき、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分については、指示する領域に含めないようにすることができる。時系列データの長さは、行動の違いが時系列データに明確に出る長さから決める。例えば、２０ステップ（１５秒×２０ステップ＝３００秒）程度とすることができる。
【０１３５】
［行動状態学習部１０３の構成例］
図１４は、図１０の行動状態学習部１０３の構成例を示すブロック図である。
【０１３６】
行動状態学習部１０３は、分類部１２１とHMM学習部１２２１乃至１２２７により構成される。
【０１３７】
分類部１２１は、行動状態ラベリング部１０２から供給されるラベル済み移動速度データのラベルを参照し、ラベルに対応するHMM学習部１２２１乃至１２２７のいずれかに供給する。即ち、行動状態学習部１０３では、ラベル（カテゴリ）ごとにHMM学習部１２２が用意されており、行動状態ラベリング部１０２から供給されるラベル済み移動速度データが、ラベルごとに分類されて、供給される。
【０１３８】
HMM学習部１２２１乃至１２２７それぞれは、供給されるラベル済み移動速度データを用いて、学習モデル（HMM）を学習する。そして、HMM学習部１２２１乃至１２２７それぞれは、学習により得られるHMMのパラメータλを、図９の移動属性識別部９２に供給する。
【０１３９】
HMM学習部１２２１は、ラベルが“滞在”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２２は、ラベルが“徒歩”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２３は、ラベルが“自転車”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２４は、ラベルが“電車（ローカル）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２５は、ラベルが“車（一般道）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２６は、ラベルが“電車（快速）”である場合の、学習モデル（HMM）を学習する。HMM学習部１２２７は、ラベルが“車（高速）”である場合の、学習モデル（HMM）を学習する。
【０１４０】
［移動属性識別部９２の第１の構成例］
図１５は、学習器１００Aで学習されたパラメータを利用する場合の移動属性識別部９２である、移動属性識別部９２Aの構成例を示すブロック図である。
【０１４１】
移動属性識別部９２Aは、尤度計算部１４１１乃至１４１７と尤度比較部１４２とにより構成されている。
【０１４２】
尤度計算部１４１１は、HMM学習部１２２１の学習により得られたパラメータを用いて、移動速度演算部９１（図９）から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１１は、行動状態が“滞在”である尤度を計算する。
【０１４３】
尤度計算部１４１２は、HMM学習部１２２２の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１２は、行動状態が“徒歩”である尤度を計算する。
【０１４４】
尤度計算部１４１３は、HMM学習部１２２３の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１３は、行動状態が“自転車”である尤度を計算する。
【０１４５】
尤度計算部１４１４は、HMM学習部１２２４の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１４は、行動状態が“電車（ローカル）”である尤度を計算する。
【０１４６】
尤度計算部１４１５は、HMM学習部１２２５の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１５は、行動状態が“車（一般道）”である尤度を計算する。
【０１４７】
尤度計算部１４１６は、HMM学習部１２２６の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１６は、行動状態が“電車（快速）”である尤度を計算する。
【０１４８】
尤度計算部１４１７は、HMM学習部１２２７の学習により得られたパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部１４１７は、行動状態が“車（高速）”である尤度を計算する。
【０１４９】
尤度比較部１４２は、尤度計算部１４１１乃至１４１７それぞれから供給される尤度を比較し、尤度の最も高い行動状態を選択し、移動属性として出力する。
【０１５０】
［移動属性識別部９２の学習器の第２の構成例］
図１６は、マルチストリームHMMにより、移動属性識別部９２で使用されるユーザ活動モデルのパラメータを学習する学習器１００Bの構成例を示している。
【０１５１】
学習器１００Bは、移動速度データ記憶部１０１、行動状態ラベリング部１６１、および行動状態学習部１６２により構成される。
【０１５２】
行動状態ラベリング部１６１は、移動速度データ記憶部１０１から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル（行動モード）として付与する。行動状態ラベリング部１６１は、移動速度の時系列データ（ｖ，θ）と、それと関連付けられた行動モードMの時系列データを行動状態学習部１６２に供給する。
【０１５３】
行動状態学習部１６２は、マルチストリームHMMにより、ユーザの行動状態を学習する。
【０１５４】
ここで、マルチストリームHMMは、通常のHMMと同様な遷移確率を有する状態ノードから、複数の異なる確率法則に従うデータが出力されるようなHMMである。マルチストリームHMMでは、パラメータλのうち、出力確率密度関数bj(x)が時系列データごとに別々に用意される。マルチストリームHMMでは、異なる種類の時系列データ（ストリーム）を関連付けながら学習することができる。
【０１５５】
行動状態学習部１６２には、連続量である移動速度ｖと進行方向θの時系列データと、離散量である行動モードMの時系列データが供給される。行動状態学習部１６２は、各状態ノードから出力される移動速度の分布パラメータと、行動モードの確率を学習する。学習により得られたマルチストリームHMMによれば、例えば、移動速度の時系列データから、現在の状態ノードが求められる。そして、求められた状態ノードから、行動モードを認識することができる。
【０１５６】
カテゴリHMMを用いた第１の構成例では、HMMをカテゴリごとに７個用意する必要があるが、マルチストリームHMMでは１個のHMMで十分である。ただし、状態ノードの数は、第１の構成例において７個のカテゴリで使用された状態ノードの総数と同程度用意する必要がある。
【０１５７】
［移動属性識別部９２の第２の構成例］
図１７は、学習器１００Bで学習されたパラメータを利用する場合の移動属性識別部９２である、移動属性識別部９２Bの構成例を示すブロック図である。
【０１５８】
移動属性識別部９２Bは、状態ノード認識部１８１と行動モード認識部１８２により構成される。
【０１５９】
状態ノード認識部１８１は、学習器１００Bで学習されたマルチストリームHMMのパラメータを用いて、移動速度演算部９１から供給される移動速度の時系列データから、マルチストリームHMMの状態ノードを認識する。状態ノード認識部１８１は、認識された現在の状態ノードのノード番号を行動モード認識部１８２に供給する。
【０１６０】
行動モード認識部１８２は、状態ノード認識部１８１で認識された状態ノードで、最も確率の高い行動モードを、移動属性として出力する。
【０１６１】
［学習プリプロセス部２２の処理］
図１８は、学習プリプロセス部２２による学習プリプロセス処理のフローチャートである。
【０１６２】
学習プリプロセス処理では、最初に、ステップＳ１において、データ接続分割部７１は、移動履歴データの接続および分割の処理を行う。
【０１６３】
ステップＳ２において、データ異常除去部７２は、移動履歴データの明らかな異常を除去する処理を行う。
【０１６４】
ステップＳ３において、再サンプリング処理部７３は、取得時刻の時間間隔が滞在閾値時間未満の欠落データを、線形補間等により補完する処理を行う。
【０１６５】
ステップＳ４において、移動属性識別付与部７４は、移動履歴の３次元データそれぞれに対し、”滞在状態”かまたは”移動状態”の移動属性を識別し、付与する。
【０１６６】
ステップＳ５において、滞在状態加工部７５は、移動属性識別付与部７４から供給される属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。そして、滞在状態加工部７５は、加工処理後の、移動属性付き移動履歴データを学習メインプロセス部２３に出力して、処理を終了する。
【０１６７】
以上のように、学習プリプロセス部２２では、移動履歴データが、必要に応じて分割等され、移動属性が付与された、移動属性付き移動履歴データとされて、学習メインプロセス部２３に供給される。
【０１６８】
［学習メインプロセス部２３の処理］
次に、図１９のフローチャートを参照して、学習メインプロセス部２３の処理（学習メインプロセス処理）について説明する。
【０１６９】
学習メインプロセス処理では、初めに、ステップＳ１１において、学習メインプロセス部２３は、移動履歴データに対する各状態の尤度を計算する。具体的には、学習メインプロセス部２３は、ユーザ活動モデルを表すHMMの状態ｓiへの遷移時に、移動履歴データの時刻tの位置のデータｘtが出力されると仮定した場合の状態尤度Ｐ（ｓi｜ｘt）を、次式（３）により計算する。
【０１７０】
【数３】
なお、時刻ｔは、時系列データの測定時刻ではなく、時系列データの順番（ステップ数）を表し、１からＴ（時系列データのサンプル数）までの値をとる。
【０１７１】
また、式（３）のＤは、移動履歴データの次元数を示している。いまの場合、移動履歴データは、時刻、緯度、および経度の３次元なので、Ｄ＝３となる。そして、ｘt（１）、ｘt（２）、ｘt（３）が、それぞれ移動履歴データｘtの時刻、緯度、経度を表すものとする。また、状態ｓiへの遷移時に出力される移動履歴データの時刻、緯度、および経度の出力確率密度関数がそれぞれ単一正規分布に従い、μsi（１）、σsi（１）は、時刻の出力確率密度関数の中心値および標準偏差を表す。また、μsi（２）、σsi（２）は、緯度の出力確率密度関数の中心値および標準偏差を表し、μsi（３）、σsi（３）は、経度の出力確率密度関数の中心値および標準偏差を表すものとする。
【０１７２】
なお、式（３）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１７３】
学習メインプロセス部２３は、ステップＳ１１において、全ての状態ｓiと３次元データｘtの組み合わせについて、式（３）により状態尤度Ｐ（ｓi｜ｘt）を計算する。
【０１７４】
次に、ステップＳ１２において、学習メインプロセス部２３は、各時刻ｔにおける全ての状態ｓiのフォワード尤度αt（ｓi）を計算する。即ち、学習メインプロセス部２３は、次式（４）および（５）を用いて、時刻ｔにおける状態ｓiのフォワード尤度αt（ｓi）を時刻１から最終の時刻Ｔまで順番に計算する。
【０１７５】
【数４】
なお、式（４）のπsiは、状態ｓiの初期確率を表す。また、式（５）のａjiは、状態ｓjから状態ｓiへの状態遷移確率を表す。なお、初期確率πsiおよび状態遷移確率ａjiの初期値は、例えば、外部から与えられる。式（４）および式（５）は、Baum-Welchの最尤推定法のフォワードアルゴリズムにおいて一般的に用いられる式である。
【０１７６】
ステップＳ１３において、学習メインプロセス部２３は、各時刻ｔにおける全ての状態ｓiのバックワード尤度βt（ｓi）を計算する。即ち、学習メインプロセス部２３は、次式（６）および（７）を用いて、時刻ｔにおける状態ｓiのバックワード尤度βt（ｓi）を、最終の時刻Ｔから時刻１まで逆順に計算する。
【０１７７】
【数５】
【０１７８】
式（６）および式（７）は、Baum-Welchの最尤推定法のバックワードアルゴリズムにおいて一般的に用いられる式である。式（６）は、時刻Ｔに各状態ｓiである確率が全て等しいものとしている。
【０１７９】
このように、ステップＳ１１乃至Ｓ１３の処理により、移動履歴データに対する隠れマルコフモデルの各種の尤度が計算される。
【０１８０】
ステップＳ１４において、学習メインプロセス部２３は、初期確率、状態遷移確率を更新する。即ち、学習メインプロセス部２３は、各状態ｓiの初期確率πsi、各状態間の状態遷移確率ａijを、次の式（８）および式（９）で求まる初期確率πsi’、状態遷移確率ａij’にそれぞれ更新する。
【０１８１】
【数６】
式（８）および式（９）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１８２】
ステップＳ１５において、学習メインプロセス部２３は、観測確率を更新する。即ち、学習メインプロセス部２３は、各状態ｓiの出力確率密度関数の中心値μsi（ｄ）、分散σsi（ｄ）2を、次の式（１０）および式（１１）で求まる中心値μsi（ｄ）’、分散σsi（ｄ）’2にそれぞれ更新する。
【０１８３】
【数７】
なお、式（１０）および式（１１）のｄは、データの次元を表し、いまの場合、１，２、または３のいずれかとなる。式（１０）および式（１１）は、Baum-Welchの最尤推定法で一般的に用いられる式である。
【０１８４】
ステップＳ１６において、学習メインプロセス部２３は、パラメータの更新を終了するか否かを判定する。例えば、各尤度の増分が所定の値以下となり、パラメータの更新の収束条件を満たした場合、学習メインプロセス部２３は、パラメータの更新を終了すると判定する。あるいは、ステップＳ１１乃至Ｓ１５の処理を規定の回数繰り返し実行した場合、パラメータの更新を終了すると判定するとしてもよい。
【０１８５】
ステップＳ１６で、パラメータの更新を終了しないと判定された場合、処理はステップＳ１１に戻る。
【０１８６】
ステップＳ１１では、学習メインプロセス部２３は、更新されたパラメータに基づいて、各状態の尤度が計算される。即ち、ステップＳ１４およびＳ１５の処理で更新された、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータに基づいて、各状態の尤度が計算される。
【０１８７】
その後、同様にステップＳ１２乃至Ｓ１５の処理が実行される。これにより、状態ｓiの系列の各種の尤度、すなわち、状態尤度Ｐ（ｓi｜ｘt）、フォワード尤度αt（ｓi）、バックワード尤度βt（ｓi）が次第に増加し、最終的に最大になるように、HMMのパラメータの更新が行われる。そして、ステップＳ１６において、再度、パラメータの更新を終了するか否かが判定される。
【０１８８】
ステップＳ１６で、パラメータの更新を終了すると判定された場合、処理はステップＳ１７に進む。
【０１８９】
ステップＳ１７において、学習メインプロセス部２３は、最終的なパラメータをユーザ別モデルパラメータ記憶部１２と目的地経由地検出部２５（図１）に出力する。即ち、学習メインプロセス部２３は、最終的に求められた、各状態ｓiの初期確率πsi、中心値μsi（ｄ）および分散σsi（ｄ）2、並びに、各状態間の状態遷移確率ａijを示すデータを、ユーザ別モデルパラメータ記憶部１２と目的地経由地検出部２５（図１）に出力する。その後、学習メインプロセス処理は終了する。
【０１９０】
［学習ポストプロセス部２４の構成例］
次に、学習ポストプロセス部２４の詳細について説明する。
【０１９１】
図２０は、学習ポストプロセス部２４の詳細構成例を示すブロック図である。
【０１９２】
学習ポストプロセス部２４は、状態系列生成部２０１と状態系列修正部２０２により構成される。状態系列生成部２０１と状態系列修正部２０２には、学習メインプロセス部２３が学習により求めたパラメータが供給される。
【０１９３】
状態系列生成部２０１は、学習プリプロセス部２２で生成された移動属性付き移動履歴データを、ユーザ活動モデルの状態ノードの時系列データ（状態系列データ）に変換し、状態系列修正部２０２に供給する。具体的には、具体的には、状態系列生成部２０１は、学習メインプロセス部２３から供給されたパラメータに基づくユーザ活動モデルから、移動履歴データの各３次元データに対応するユーザ活動モデルを認識する。そして、状態系列生成部２０１は、認識結果としてのユーザの状態ノードsiを、順次、状態系列修正部２０２に供給する。
【０１９４】
状態系列修正部２０２は、状態系列生成部２０１から供給される状態系列データを必要に応じて修正し、修正後の状態系列データを、目的地経由地検出部２５（図１）に供給する。状態系列修正部２０２で状態系列データの修正がされない場合には、状態系列生成部２０１から供給される状態系列データが、そのまま、目的地経由地検出部２５に供給される。
【０１９５】
［状態系列修正部２０２の処理］
図２１乃至図２５を参照して、状態系列修正部２０２が行う状態系列データの修正処理について説明する。
【０１９６】
図２１は、状態系列修正部２０２による修正処理を示している。
【０１９７】
本実施の形態において、状態系列生成部２０１から供給される状態系列データは、ユーザの移動履歴に対応するデータである。ユーザの移動は、ある目的地から他の目的地へのleft-to-right型の状態遷移モデルに近似できると考えられる。
【０１９８】
そこで、状態系列修正部２０２は、状態系列生成部２０１から供給される状態系列データを、left-to-right型の状態系列データとなるように簡素化する修正を行う。
【０１９９】
状態系列修正部２０２は、状態系列データを、left-to-rightの制約を満たすように修正するために、最初に、状態系列データで、ループ、即ち、同一の状態ノードに戻る部分があるかどうかを探索する。そして、状態系列修正部２０２は、ループが検出された場合、そのループをマージ（その状態ノードを削除して親ノードに吸収）するか、または、スプリット（新たな状態ノードを生成して分割）する。
【０２００】
より詳しくは、状態系列修正部２０２は、ループ内のノード数が１つである場合には、マージすることによって、状態系列データを修正し、ループ内のノード数が２以上である場合には、スプリットすることによって、状態系列データを修正する。
【０２０１】
［状態系列修正部２０２のループ修正処理］
図２２は、状態系列修正部２０２によるループ修正処理のフローチャートを示している。状態系列修正部２０２は、所定のステップ数の状態系列データを記憶する内部メモリを有し、状態系列生成部２０１から、ある程度のステップ数の状態系列データが内部メモリに蓄積されたとき、この処理が開始される。
【０２０２】
初めに、ステップＳ３１において、状態系列修正部２０２は、状態系列生成部２０１から供給された状態系列データに対し、注目ノードを決定する。即ち、状態系列修正部２０２は、状態系列生成部２０１から供給された状態系列データのなかの先頭の状態ノードを選択し、それを注目ノードとする。
【０２０３】
ステップＳ３２において、状態系列修正部２０２は、注目ノードのノード番号が１つ前のノードと同じかを判定する。状態遷移が自己遷移である場合には、注目ノードのノード番号が同じとなる。従って、換言すれば、状態系列修正部２０２は、自己遷移であるか否かを判定する。なお、先頭の状態ノードが注目ノードである場合には、注目ノードのノード番号が１つ前のノードと同じであると判定する。
【０２０４】
ステップＳ３２で、注目ノードのノード番号が１つ前のノードと同じであると判定された場合、処理は後述するステップＳ３７に進む。
【０２０５】
一方、ステップＳ３２で、注目ノードのノード番号が１つ前のノードと同じではないと判定された場合、処理はステップＳ３３に進み、状態系列修正部２０２は、注目ノードが過去の状態系列に存在するかを判定する。状態系列データにループが存在し、ループして過去の状態系列に戻ってきたとき、ステップＳ３３において、注目ノードが過去の状態系列に存在すると判定される。
【０２０６】
ステップＳ３３で、注目ノードが過去の状態系列に存在しないと判定された場合、処理は後述するステップＳ３７に進む。
【０２０７】
一方、ステップＳ３３で、注目ノードが過去の状態系列に存在すると判定された場合、処理はステップＳ３４に進み、状態系列修正部２０２は、ループ内のノード数が１つであるかを判定する。
【０２０８】
ステップＳ３４で、ループ内のノード数が１つであると判定された場合、ステップＳ３５において、状態系列修正部２０２は、ループのノードを親ノード（戻り先のノード）にマージする。
【０２０９】
ステップＳ３４で、ループ内のノード数が２以上であると判定された場合、ステップＳ３６において、状態系列修正部２０２は、新しいノードを生成し、分割する。
【０２１０】
ステップＳ３５またはＳ３６の処理後、ステップＳ３７において、状態系列データに、注目ノードの次のノードがあるかを判定する。
【０２１１】
ステップＳ３７で、注目ノードの次のノードがあると判定された場合、ステップＳ３８において、状態系列修正部２０２は、次のノードを注目ノードに決定し、処理をステップＳ３２に戻す。
【０２１２】
一方、ステップＳ３７で、注目ノードの次のノードがないと判定された場合、即ち、状態系列生成部２０１から供給された状態系列データの全ての状態ノードについてループを探索した場合、処理は終了する。
【０２１３】
状態系列修正部２０２は、以上の処理を行うことにより、状態系列生成部２０１から供給される状態系列データを修正して、修正後の状態系列データを出力する。
【０２１４】
なお、本実施の形態では、状態系列修正部２０２が、検出されたループを、マージまたはスプリットのいずれで修正するかを、ループ内のノード数が１つであるか否かによって判断した。しかし、マージまたはスプリットのいずれで修正した場合に尤度が高くなるか、または、学習モデルの複雑さなど、その他の判断基準で、マージまたはスプリットのいずれで修正するかを判断するようにしてもよい。
【０２１５】
また、他の情報が使える場合にはそれを用いて、マージまたはスプリットのいずれで修正するかを判断することも可能である。たとえば、ループ内のノードが１つであっても、例えば、目的地候補のノードなど、重要なノードであるかもしれない。このような場合は、マージでなくて、スプリットの処理をすべきである。また、ループ内のノード数が２以上あっても、いずれも重要でないノードかもしれない。また、あるいは、全ノード数に制約があってこれ以上増やせない場合なども考えられる。このような場合には、状況に応じて変更をすればよい。
【０２１６】
［状態系列修正部２０２によるその他の修正処理の説明］
次に、状態系列修正部２０２による状態系列データのその他の修正処理の例を説明する。
【０２１７】
図２３は、１つのノードが複数の系列で共有されている共有ノードを修正する処理の例を示している。
【０２１８】
図２３の上段の状態遷移図において、斜線を付して示される真ん中のノードは、共有ノードとなっている。即ち、共有ノードの前後のノードは、それぞれ別々のノードとなっている。状態系列修正部２０２は、図２３の下段の状態遷移図のように、共有ノードをスプリット（新たな状態ノードを生成して分割）し、２つの系列に、元の状態系列データを修正する。
【０２１９】
ノードの尤度が低い場合には、本来別々のノードになるべきところが、初期条件、モデルのノード数の不足などで、学習時にローカルミニマムに陥って、このような共有ノードとなることがある。３次元データを表すノードでノードの尤度が低い場合とは、ノードが示す位置（中心位置）と、実際のデータの位置との距離が大きい場合を意味する。
【０２２０】
状態系列修正部２０２には、共有ノードをスプリットする処理を、状態系列データの修正処理として行わせることで、初期条件、モデルのノード数の不足などで発生した共有ノードを解消することができる。換言すれば、学習メインプロセス部２３による拘束条件（スパース制約によるエルゴディックHMM）では実現できない処理を、状態系列修正部２０２で事後的（付加的に）実現することができる。
【０２２１】
［状態系列修正部２０２の共有ノード修正処理］
図２４は、状態系列修正部２０２による共有ノード修正処理のフローチャートを示している。状態系列生成部２０１から、全ての状態系列データが内部メモリに蓄積されたとき、この処理が開始される。
【０２２２】
初めに、ステップＳ５１において、状態系列修正部２０２は、内部メモリに記憶されている状態系列データのなかで、尤度が所定値以下のノードである低尤度ノードを検索して、ステップＳ５２に進む。本実施の形態では、学習により得られたノードの中心位置と、実際のデータの位置との距離が大きいノードが、低尤度ノードとなる。
【０２２３】
ステップＳ５２において、状態系列修正部２０２は、低尤度ノードが検出されたかを判定する。
【０２２４】
ステップＳ５２で、低尤度ノードが検出されたと判定された場合、処理はステップＳ５３に進み、状態系列修正部２０２は、検出された低尤度ノードを注目ノードに決定する。
【０２２５】
ステップＳ５４において、状態系列修正部２０２は、注目ノードが共有ノードであるかを判定する。ステップＳ５４で、注目ノードが共有ノードではないと判定された場合、処理はステップＳ５１に戻る。
【０２２６】
一方、ステップＳ５４で、注目ノードが共有ノードであると判定された場合、処理はステップＳ５５に進み、状態系列修正部２０２は、前後のノードが複数あるかを判定する。
【０２２７】
ステップＳ５５で、前後のノードのいずれかが複数ないと判定された場合、処理はステップＳ５１に戻る。一方、ステップＳ５５で、前後のノードのいずれもが複数あると判定された場合、処理はステップＳ５６に進み、状態系列修正部２０２は、新しいノードを生成することにより、元の状態系列データを、２つの系列に修正する。ステップＳ５６の処理後も、処理はステップＳ５１に戻る。
【０２２８】
そして、上述したステップＳ５１乃至Ｓ５６の処理を繰り返し実行することで、全ての低尤度ノードが順次検出され、共有ノードがスプリットされる。
【０２２９】
全ての低尤度ノードが検出された場合、ステップＳ５２で、低尤度ノードが検出されなかったと判定され、処理がステップＳ５７に進む。そして、ステップＳ５７において、状態系列修正部２０２は、元の状態系列データに対し修正がなされた修正後の状態系列データを出力して、処理を終了する。低尤度ノードが１つも検出されない場合には、元の状態系列データがそのまま出力される。
【０２３０】
状態系列修正部２０２は、以上のような共有ノード修正処理を行って、状態系列生成部２０１から供給される状態系列データを修正することができる。
【０２３１】
なお、図２３および図２４に示した処理では、前と後ろの両方について複数の系列がある場合のみ、ノードをスプリットするようにした。しかし、図２５右側に示すように、前または後ろのいずれか一方のみ、複数の系列がある場合であっても、ノードをスプリットするようにしてもよい。
【０２３２】
また、図２５左側に示すように、前と後ろの両方で複数の系列が存在しない場合であっても、スプリットした方がノードの尤度が高くなる場合には、スプリットするようにしてもよい。いずれの場合においても、スプリットすることにより、尤度が修正前より高くなることが条件である。また、図２５左側に示すように、前と後ろの両方で複数の系列が存在しない場合のスプリットでは、修正前後でステップ数が変わらないように、修正対象のノードにおいて、自己遷移が発生していることも条件となる。
【０２３３】
以上のような状態系列修正部２０２による状態系列データの修正処理によれば、状態系列データに拘束を新しく加えるのみならず、学習でローカルミニマムに陥って十分、尤度を高くすることができなかった場合などの修正が可能である。
【０２３４】
図２３および図２４に示した処理では、学習用データに対する尤度のチェックを行っているが、学習用データと同時に得られた他のデータによる尤度のチェックを行うようにしてもよい。他のデータ系列のうち、学習モデルの中の状態遷移に影響を及ぼすものがあれば、通常、マルチモーダルモデルとして学習することになる。しかし、そのデータ系列の寄与が大きくない、あるいは、不定であるならば、寄与の大きなデータのみで学習するようにして、学習されたモデルから得られる状態系列データを状態系列修正部２０２における修正時にのみ、その影響を反映させることで、寄与の少ない時系列データが学習モデルに必要以上の影響を与えるのを回避することができる。
【０２３５】
［目的地経由地検出部２５の処理］
次に、図２６を参照して、目的地経由地検出部２５の処理について説明する。
【０２３６】
上述したように、学習メインプロセス部２３は、移動履歴データを分割およびホールドする処理が行われた後の（移動属性付き）移動履歴データを学習用データとして、ユーザ活動モデルのパラメータを学習する。そして、学習ポストプロセス部２４が、学習により求めたパラメータを用いて、移動履歴データに対応する状態系列データを生成する。
【０２３７】
図２６Ａは、図８下段に示した、学習プリプロセス部２２によって移動履歴データの分割およびホールドが行われた後の、移動属性付き移動履歴データ８３Ａおよび８３Ｂを示している。
【０２３８】
図２６Ｂは、図８下段に示した移動属性付き移動履歴データ８３Ａおよび８３Ｂに、対応する状態系列データを併せて示した図である。
【０２３９】
移動属性付き移動履歴データ８３Ａには、ｓ１，ｓ２，・・・，ｓｋ，・・・ｓｔの状態系列ノードが対応する。移動属性付き移動履歴データ８３Ｂには、ｓｔ＋１，ｓｔ＋２，・・・，ｓＴの状態系列ノードが対応する。
【０２４０】
目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、目的地の属性を付与する。図２６Ｂの例では、移動属性付き移動履歴データ８３Ａの状態ノードｓｔと、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴに対して、目的地の属性が付与される。状態ノードｓｔと状態ノードｓＴは、いずれも滞在状態が滞在閾値時間以上継続していた状態ノードである。このように、目的地経由地検出部２５によって、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードが、目的地に推定される。
【０２４１】
なお、図８を参照して説明した分割処理では、分割した移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”が、１つの”滞在状態”に縮減された。しかしながら、分割処理では、移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”のすべてを、消去するようにしてもよい。図２６Ａの例で説明すると、移動属性付き移動履歴データ８３Ａおよび８３Ｂそれぞれの最後の”滞在状態（ｕ）”の３次元データを省略するようにしてもよい。この場合には、目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の３次元データに対応する状態ノードに、目的地の属性を付与する。図２６Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｔの１つ前の状態ノードｓｔ−１、および、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴの１つ前の状態ノードｓＴ−１を目的地とすればよい。
【０２４２】
目的地経由地検出部２５は、また、１まとまりの移動属性付き移動履歴データの途中にある”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、経由地の属性を付与する。即ち、滞在状態の継続時間が１の分割閾値時間未満である移動履歴データに対応する状態ノードが、経由地に推定される。図２６Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｋが、経由地に決定される。
【０２４３】
なお、目的地経由地検出部２５は、図２６Ｃに示すように、移動手段が変更されたとき、変更前の最後の状態ノードｓｈにも、経由地の属性を付与するようにしてもよい。
【０２４４】
［学習ブロック１１の処理］
図２７のフローチャートを参照して、学習ブロック１１全体の処理について説明する。
【０２４５】
初めに、ステップＳ７１において、履歴データ蓄積部２１は、センサデバイスから供給される、移動履歴データを、学習用データとして蓄積する。
【０２４６】
ステップＳ７２において、学習プリプロセス部２２は、図１８を参照して説明した、学習プリプロセス処理を実行する。即ち、履歴データ蓄積部２１に蓄積されている移動履歴データの接続および分割の処理、移動履歴データを構成する３次元データそれぞれに、”滞在状態”または”移動状態”の移動属性の付与、などを行う。
【０２４７】
ステップＳ７３において、学習メインプロセス部２３は、ユーザの移動履歴を学習する。即ち、学習メインプロセス部２３は、ユーザの移動履歴をユーザ活動モデルとして確率的状態遷移モデル（HMM）にモデル化したときのパラメータを求める。学習により得られたパラメータは、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給され、ユーザ別モデルパラメータ記憶部１２で記憶される。
【０２４８】
ステップＳ７４において、学習ポストプロセス部２４は、学習により得られたユーザ活動モデルを用いて、移動履歴データに対応する状態ノード系列データを生成する。
【０２４９】
ステップＳ７５において、目的地経由地検出部２５は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、目的地の属性を付与する。より具体的には、目的地経由地検出部２５は、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードに、目的地の属性を付与する。
【０２５０】
ステップＳ７６において、目的地経由地検出部２５は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、経由地の属性を付与する。より具体的には、目的地経由地検出部２５は、滞在状態の継続時間が滞在閾値時間未満である移動履歴データに対応する状態ノードに、経由地の属性を付与する。
【０２５１】
ステップＳ７７において、目的地経由地検出部２５は、状態ノードに付与された目的地、経由地の属性についての情報を、ユーザ別モデルパラメータ記憶部１２に記憶させ、処理を終了する。
【０２５２】
［予測メインプロセス部３３の処理］
次に、予測ブロック１３が行う処理について説明する。
【０２５３】
初めに、予測メインプロセス部３３による、現在地ノード以降のツリー探索処理について説明する。
【０２５４】
現在地ノード以降のツリー探索処理は、予測メインプロセス部３３の現在地ノード推定部４１が推定した現在地ノードから、到達可能な目的地ノードと、そこまでの経路を求める処理である。到達可能な目的地ノードは、現在地ノードから遷移可能なノードで構成されるツリー構造の中に存在する。従って、ツリーを構成する状態ノードのなかから、目的地ノードを探索することで、目的地を予測することができる。また、現在地ノード以降のツリー探索処理において、経由地の属性が付与された状態ノード（以下、経由地ノードという。）が検出された場合には、経由地までの経路も記憶される。
【０２５５】
学習により得られたHMMの各状態siは、地図上の所定の点（位置）を表し、状態siと状態sjが結ばれているとき、状態siから状態sjを移動する経路を表していると考えることができる。
【０２５６】
この場合、状態siに対応する各点は、端点、通過点、分岐点、ループのいずれかに分類することができる。端点とは、自己遷移以外の確率が極めて小さく（自己遷移以外の確率が所定の値以下であり）、次に移動可能な点がない点である。通過点とは、自己遷移以外に有意な遷移が一つある、換言すれば、次に移動可能な点が一つある点である。分岐点とは、自己遷移以外に有意な遷移が二つ以上ある、換言すれば、次に移動可能な点が二つ以上ある点である。ループとは、これまで通過した経路上のどれかと一致する点である。
【０２５７】
目的地への経路を探索する場合、異なる経路がある場合には、それぞれの経路について必要時間等の情報を提示することが望まれる。そこで、可能な経路を過不足なく探索するために、次の条件を設定する。
（１）一度分岐した経路は再度合流した場合でも、別の経路とみなす。
（２）探索中の経路が分岐点に達した場合に、未探索リストを作成し、未探索リストの分岐先の探索を行う。
（３）経路内に端点またはループが現れた場合、その経路の探索を終了する。なお、現在の点から、１つ前の点に経路を逆戻りする場合はループに含む。
【０２５８】
図２８は、予測メインプロセス部３３の目的地経由地予測部４２による、現在地ノード以降のツリー探索処理のフローチャートである。
【０２５９】
図２８の処理では、最初に、ステップＳ９１において、目的地経由地予測部４２は、予測メインプロセス部３３の現在地ノード推定部４１により推定された現在地ノードを取得し、注目するノードである注目ノードに設定する。
【０２６０】
ステップＳ９２において、目的地経由地予測部４２は、注目ノードに遷移先があるかを判定する。ステップＳ９２で、注目ノードに遷移先がないと判定された場合、処理は後述するステップＳ１０１に進む。
【０２６１】
一方、ステップＳ９２で、注目ノードに遷移先があると判定された場合、処理はステップＳ９３に進み、目的地経由地予測部４２は、遷移先が目的地ノードであるかを判定する。
【０２６２】
ステップＳ９３で、遷移先が目的地ノードであると判定された場合、処理はステップＳ９４に進み、目的地経由地予測部４２は、これまでの経路（状態ノード系列）を内部メモリの探索結果リストに記憶する。ステップＳ９４の後、処理はステップＳ１０１に進む。
【０２６３】
一方、ステップＳ９３で、遷移先が目的地ノードではないと判定された場合、処理はステップＳ９５に進み、目的地経由地予測部４２は、遷移先が経由地ノードであるかを判定する。
【０２６４】
ステップＳ９５で、遷移先が経由地ノードであると判定された場合、処理はステップＳ９５に進み、目的地経由地予測部４２は、これまでの経路（状態ノード系列）を内部メモリの探索結果リストに記憶する。
【０２６５】
目的地までの代表経路、到達確率、および所要時間を予測結果として出力するためには、探索結果リストには、遷移先が目的地であるときの経路のみを記憶すればよい。しかしながら、遷移先が経由地であるときの経路も記憶することにより、経由地までの経路、確率、および時間が必要になったときに即座に求めることができる。
【０２６６】
ステップＳ９５で遷移先が経由地ノードではないと判定された場合、または、ステップＳ９６の後、処理はステップＳ９７に進み、目的地経由地予測部４２は、遷移先が分岐点かを判定する。
【０２６７】
ステップＳ９７で、遷移先が分岐点であると判定された場合、処理はステップＳ９８に進み、目的地経由地予測部４２は、分岐先の２つの状態ノードを内部メモリの未探索リストに記憶する（追加する）。ステップＳ９８の後、処理はステップＳ１０１に進む。なお、分岐先が探索中の経路のいずれかの状態ノードである場合はループとなるので、目的地経由地予測部４２は、その分岐先の状態ノードについては未探索リストに記憶させない。
【０２６８】
ステップＳ９７で、遷移先が分岐点ではないと判定された場合、処理はステップＳ９９に進み、目的地経由地予測部４２は、遷移先が端点であるかを判定する。ステップＳ９９で、遷移先が端点であると判定された場合、処理はステップＳ１０１に進む。
【０２６９】
一方、ステップＳ９９で、遷移先が端点ではないと判定された場合、処理はステップＳ１００に進み、目的地経由地予測部４２は、遷移先の状態ノードを注目ノードに設定し、処理をステップＳ９２に戻す。即ち、遷移先が、目的地ノード、経由地ノード、分岐点、および端点のいずれでもない場合には、探索対象の状態ノードが、遷移先の次の状態ノードに進められる。
【０２７０】
ステップＳ９４，Ｓ９８、またはＳ９９の処理の後、処理がステップＳ１０１に進められた場合、目的地経由地予測部４２は、未探索リストに登録されている状態ノードがあるか、即ち、未探索の分岐先があるかを判定する。
【０２７１】
ステップＳ１０１で、未探索の分岐先があると判定された場合、処理はステップＳ１０２に進み、目的地経由地予測部４２は、未探索リストの最上位の分岐先の状態ノードを、注目ノードに設定し、注目ノードまでの経路を読み出す。そして、処理がステップＳ９２に戻される。
【０２７２】
一方、ステップＳ１０１で、未探索の分岐先がないと判定された場合、ツリー探索処理は終了する。
【０２７３】
以上のように、ツリー探索処理では、ユーザの現在地ノードから遷移可能な状態ノードでなるツリー構造において、現在地ノードを出発点として、目的地ノード若しくは遷移先のない終端ノード（端点）になるまで全ての状態ノードを探索する処理が行われる。そして、ユーザの現在地から目的地までの経路が、現在地ノードからの状態ノード系列として、探索結果リストに記憶される。なお、ツリー探索処理は、探索回数が終了条件としての所定の回数を満たすまで探索するようにしてもよい。
【０２７４】
［ツリー探索処理の例］
図２９を参照して、目的地経由地予測部４２のツリー探索処理についてさらに説明する。
【０２７５】
図２９の例において、状態s１が現在地である場合、次のような３通りの経路が少なくとも探索されることになる。１つめの経路は、状態s１から状態s５，状態s６等を経由して状態s１０までの経路（以下、経路Ａともいう。）である。２つめの経路は、状態s１から状態s５，状態s１１，状態s１４，状態s２３等を経由して状態s２９までの経路（以下、経路Ｂともいう。）である。３つめの経路は、状態s１から状態s５，状態s１１，状態s１９，状態s２３等を経由して状態s２９までの経路（以下、経路Ｃともいう。）である。
【０２７６】
目的地経由地予測部４２は、探索された各経路が選択される確率（経路の選択確率）を計算する。経路の選択確率は、経路を構成する状態間の遷移確率を順次乗算することで求められる。ただし、次の状態に遷移する場合のみを考慮し、その場所に滞留する場合は考慮する必要がないので、学習により求められた各状態の状態遷移確率aijから、自己遷移確率を除いて規格化された遷移確率[aij]を用いて、経路の選択確率が求められる。
【０２７７】
自己遷移確率を除いて規格化された遷移確率[aij]は、次式（１２）で表すことができる。
【数８】
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【０２７８】
したがって、例えば、図２９の状態s５の状態遷移確率aijが、自己遷移確率a５，５＝０．５，遷移確率a５，６＝０．２，遷移確率a５，１１＝０．３である場合、状態s５から状態s６または状態s１１に分岐する場合の遷移確率[a５，６]および遷移確率[a５，１１]は、それぞれ、０．４，０．６となる。
【０２７９】
探索された経路の状態siのノード番号ｉが、（ｙ１，ｙ２，・・・，ｙｎ）であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式（１３）で表すことができる。
【数９】
【０２８０】
なお、実際には、通過点での規格化された遷移確率[aij]は１であるので、経路の選択確率は、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。従って、目的地経由地予測部４２は、図２８のツリー探索処理を実行しながら、同時に、選択された経路の選択確率を式（１３）により計算することができる。
【０２８１】
図２９の例では、経路Ａの選択確率は、０．４である。また、経路Ｂの選択確率は、０．２４＝０．６×０．４である。経路Ｃの選択確率は、０．３６＝０．６×０．６である。そして、計算された経路の選択確率の総和は１＝０．４＋０．２４＋０．３６であり、過不足ない探索を実現することができることがわかる。
【０２８２】
図２９の例では、現在地の状態s１から注目ノードが順次進められ、状態s４が注目ノードであるとき、遷移先の状態s５が分岐点であるため、図２８のステップＳ９８が実行され、図３０Ａに示されるように、分岐先の状態s１１と状態s６が未探索リストに記憶される。ここで、状態s１１と状態s６では、状態s１１の選択確率が高いため、状態s１１が未探索リストの上位に記憶される。
【０２８３】
そして、図２８のステップＳ１０１およびＳ１０２が実行され、未探索リストの上位に記憶されている、状態s１１が注目ノードに設定され、状態s１１以降の経路が探索される。状態s１１が注目ノードに設定されたとき、図３０Ｂに示されるように、未探索リストから、状態s１１が削除される。
【０２８４】
そして、状態s１１を注目ノードとして探索が進められると、状態s１４と状態s１９の分岐先が検出されるので、図２８のステップＳ９８が実行され、状態s１４と状態s１９が未探索リストに記憶される。このとき、状態s１４と状態s１９は、現在の未探索リストの最上位に記憶され、また、状態s１４と状態s１９では、状態s１９の選択確率が高いため、状態s１９が状態s１４より上位に記憶される。従って、未探索リストは、図３０Ｃに示されるようになる。
【０２８５】
以下同様に、図２８のステップＳ１０１およびＳ１０２が実行され、未探索リストの上位に記憶されている、状態s１９が注目ノードに設定され、状態s１９以降の経路が探索される。状態s１９が注目ノードに設定されたとき、図３０Ｄに示されるように、未探索リストから、状態s１９が削除される。
【０２８６】
以上のように、目的地経由地予測部４２によるツリー探索処理は、検出された分岐先を未探索リストの最上位に記録させることで、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される。
【０２８７】
なお、探索の深さが深くなる、換言すれば、現在地ノードを最上位として下位の階層が深くなることで、全てを探索することが難しいことも考えられる。そのような場合には、例えば、１）遷移確率の低い分岐先は探索しない、２）生起確率の低い経路は探索しない、３）探索する深さに制限を加える、４）探索する枝の数に制限を加える、などの条件を加えて、途中で探索を終了するようにしてもよい。
【０２８８】
図３１は、ツリー探索処理における探索結果リストの例を示している。
【０２８９】
深さ優先アルゴリズムによりツリー探索処理を行うことにより、探索結果リストには、選択確率の高い経路から順に登録される。
【０２９０】
図３１の例では、探索結果リストの１番目には、目的地ｇ１までの経路Ｒ１（ｒ１，ｒ２，ｒ３，ｒ４）が登録され、この経路Ｒ１が選択される確率はＰ１で、経路Ｒ１を使って目的地ｇ１までにかかる時間がＴ１である。探索結果リストの２番目には、目的地ｇ２までの経路Ｒ２（ｒ１，ｒ２，ｒ３，ｒ５）が登録され、この経路Ｒ２が選択される確率はＰ２で、経路Ｒ２を使って目的地ｇ２までにかかる時間がＴ２である。探索結果リストの３番目には、目的地ｇ３までの経路Ｒ３（ｒ１，ｒ２，ｒ６）が登録され、この経路Ｒ３が選択される確率はＰ３で、経路Ｒ３を使って目的地ｇ３までにかかる時間がＴ３である。
【０２９１】
探索結果リストの４番目には、経由地ｗ２までの経路Ｒ４（ｒ１，ｒ２，ｒ７）が登録され、この経路Ｒ４が選択される確率はＰ４で、経路Ｒ４を使って経由地ｗ２までにかかる時間がＴ４である。探索結果リストの５番目には、経由地ｗ１までの経路Ｒ５（ｒ１，ｒ８）が登録され、この経路Ｒ５が選択される確率はＰ５で、経路Ｒ５を使って経由地ｗ１までにかかる時間がＴ５である。
【０２９２】
探索結果リストの６番目には、目的地ｇ３までの経路Ｒ６（ｒ１，ｒ８，ｗ１，ｒ８，ｒ９）が登録され、この経路Ｒ６が選択される確率はＰ６で、経路Ｒ６を使って目的地ｇ３までにかかる時間がＴ６である。探索結果リストの７番目には、この経路Ｒ７が選択される確率はＰ７で、目的地ｇ２までの経路Ｒ７（ｒ１，ｒ１０，ｒ１１）が登録され、経路Ｒ７を使って目的地ｇ２までにかかる時間がＴ７である。
【０２９３】
目的地または経由地まで、各経路が選択される確率は、上述した式（１３）により計算される。さらに、目的地までの経路が複数存在する場合、その目的地までの複数の経路の選択確率の和が、目的地の到達確率となる。
【０２９４】
従って、図３１の例では、目的地ｇ２へ行くには、経路Ｒ２を利用する場合と、経路Ｒ７を利用する場合があり得るので、目的地ｇ２の到達確率は、は（Ｐ２＋Ｐ７）となる。同様に、目的地ｇ３へ行くには、経路Ｒ３を利用する場合と、経路Ｒ６を利用する場合があり得るので、目的地ｇ３の到達確率は、は（Ｐ３＋Ｐ６）となる。なお、目的地ｇ１の到達確率は、経路Ｒ１が選択される確率Ｐ１と同一である。
【０２９５】
［予測ポストプロセス部３４の処理］
次に、予測ポストプロセス部３４が行う処理について説明する。
【０２９６】
目的地または経由地まで、選択された経路で移動したときにかかる時間の求め方について説明する。
【０２９７】
例えば、現在時刻ｔ１の現在地が状態ｓｙ１であり、時刻（ｔ１，ｔ２，・・・，ｔｇ）における決定された経路が（ｓｙ１，ｓｙ２，・・・，ｓｙｇ）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ１，ｙ２，・・・，ｙｇ）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０２９８】
現在時刻ｔ１での現在地ｙ１は、現在地ノード推定部４１により確定しているので、現在時刻ｔ１の現在地がｙ１である確率Ｐｙ１（ｔ１）は、
Ｐｙ１（ｔ１）＝１である。
また、現在時刻ｔ１にｙ１以外の他の状態にいる確率は０である。
【０２９９】
一方、所定の時刻ｔｎにノード番号ｙｎにいる確率Ｐｙｎ（ｔｎ）は、
【数１０】
で表すことができる。式（１４）の右辺第一項は、もともとその位置ｙｎにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙｎ−１から位置ｙｎに遷移してきた場合の確率を表している。式（１４）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０３００】
目的地ｙｇへ到達するときの時刻ｔｇの予測値<ｔｇ>は、「その直前の時刻ｔｇ−１に目的地ｙｇの１つ前の位置ｙｇ−１にいて、時刻ｔｇに目的地ｙｇに移動する確率」を用いて、
【数１１】
と表すことができる。
【０３０１】
即ち、予測値<ｔｇ>は、現在時刻から、「その直前の時刻ｔｇ−１に状態ｓｙｇの１つ前の状態ｓｙｇ−１にいて、時刻ｔｇに状態ｓｙｇに移動するとき」までの時間の期待値で表される。
【０３０２】
以上より、所定の目的地または経由地まで、選択された経路で移動したときにかかる時間は、上述した式（１５）の予測値<ｔｇ>により求められる。
【０３０３】
図３１の例を使用して、目的地までの経路が探索された場合に、代表経路として選択する代表経路選択処理について説明する。
【０３０４】
図３１のような探索結果リストが得られた場合、探索結果リストには、選択確率が高いものから順に（上位に）登録されるので、選択確率が上位であり、目的地も異なる、探索結果リストの１番目乃至３番目が予測結果として出力される。即ち、経目的地ｇ１とその経路Ｒ１、目的地ｇ２とその経路Ｒ２、目的地ｇ３とその経路Ｒ３が、目的地とその代表経路として選択される。
【０３０５】
次に、探索結果リストの４番目および５番目は経由地までの経路であるためスキップされ、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６を代表経路とするかが検討される。この経路Ｒ６は、既に代表経路として選択されている、同一の目的地ｇ３の経路Ｒ３には含まれていない経由地ｗ１を利用するものとなっている。したがって、目的地ｇ３へ到達するための経路Ｒ６も、代表経路として選択される。
【０３０６】
次に、探索結果リストの７番目の、目的地ｇ２へ到達するための経路Ｒ７を代表経路とするかが検討される。この経路Ｒ７は、既に代表経路として選択されている、同一の目的地ｇ２と同じく、所定の経由地を経由しないものとなっている。したがって、目的地ｇ２へ到達するための経路Ｒ７は、代表経路として選択されない。
【０３０７】
このように、代表経路選択処理では、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路は、同一目的地であっても、予測結果として提示することができる。
【０３０８】
なお、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６は、［背景技術］に示した先願２の方法では、経由地ｗ１で探索が終了されていた。しかしながら、予測システム１によれば、経由地ｗ１で終了することなく、経由地ｗ１を利用して目的地ｇ３へ到達する経路まで探索することが可能となっている。
【０３０９】
予測システム１によれば、学習により得られた状態ノードに、目的地と経由地を区別して属性を付与することで、第１と第２の課題を解決することができる。
【０３１０】
図３２は、予測ポストプロセス部３４が行う代表経路選択処理のフローチャートである。
【０３１１】
初めに、ステップＳ１２１において、予測ポストプロセス部３４は、目的地経由地予測部４２で作成された探索結果リストから、経由地までの経路を除外し、目的地のみの探索結果リストである目的地リストを生成する。
【０３１２】
ステップＳ１２２において、予測ポストプロセス部３４は、目的地リストを目的地別に並び替えた目的地別目的地リストに変更する。このとき、予測ポストプロセス部３４は、同一の目的地内における順位を変えないように目的地別目的地リストを生成する。
【０３１３】
ステップＳ１２３において、予測ポストプロセス部３４は、目的地ごとの到達確率を算出する。目的地までの経路が１つしかない場合には、その経路の選択確率が到達確率となり、目的地まで複数の経路が存在する場合には、複数の選択確率（生起確率）の和が、その目的地の到達確率となる。
【０３１４】
ステップＳ１２４において、予測ポストプロセス部３４は、代表経路の選択に経由地を考慮するかを判定する。ステップＳ１２４で、経由地を考慮しないと判定された場合、処理はステップＳ１２５に進み、予測ポストプロセス部３４は、目的地別に、最上位の経路を、各目的地の代表経路として選択し、処理を終了する。その結果、目的地まで複数の経路が存在する場合には、選択確率の高い目的地までの経路が、各目的地の代表経路とされ、その所要時間が、目的地までの所要時間として提示される。なお、目的地が多数ある場合には、上位から、予め設定した個数の目的地のみを提示するようにさせることができる。
【０３１５】
一方、ステップＳ１２４で、経由地を考慮すると判定された場合、処理はステップＳ１２６に進み、予測ポストプロセス部３４は、目的地別目的地リストを、経由地なしの目的地別目的地リストと、経由地ありの目的地別目的地リストに分類する。
【０３１６】
そして、ステップＳ１２７において、予測ポストプロセス部３４は、経由地なしの目的地別目的地リストから、目的地別に、最上位の経路を代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地なしの経路が決定される。
【０３１７】
次に、ステップＳ１２８において、予測ポストプロセス部３４は、経由地ありの目的地別目的地リストを、さらに、経由地別に分類する。
【０３１８】
ステップＳ１２９において、予測ポストプロセス部３４は、経由地別の、経由地ありの目的地別目的地リストから、目的地別に、各経由地の最上位の経路を、代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地ありの経路が決定される。その結果、目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方が、各目的地の代表経路とされ、それぞれの所要時間が、目的地までの所要時間として提示される。
【０３１９】
以上により、代表経路選択処理は終了する。このように、目的地への経路が複数存在する場合、生起確率の上位を複数提示するよりも、経由地によって分類して提示する方が、ユーザが実際に感じる予測に近いものとすることができる。
【０３２０】
［予測ブロック１３全体の処理］
図３３のフローチャートを参照して、予測ブロック１３全体の処理について説明する。
【０３２１】
初めに、ステップＳ１４１において、バッファリング部３１は、予測処理のため、リアルタイムに取得される移動履歴データをバッファリングする。
【０３２２】
ステップＳ１４２において、予測プリプロセス部３２は、予測プリプロセス処理を実行する。具体的には、学習プリプロセス部２２が行う学習プリプロセス処理と同様の、移動履歴データの接続および分割の処理、移動履歴データの明らかな異常を除去する処理、および、欠落データを補完する処理を実行する。但し、移動履歴データを分割する際の基準となる滞在閾値時間は、学習プリプロセス処理と異なる時間であってもよい。
【０３２３】
ステップＳ１４３において、予測メインプロセス部３３は、学習ブロック１１の学習により得られたユーザ活動モデルのパラメータを、ユーザ別モデルパラメータ記憶部１２から取得する。このパラメータを取得する処理は、図３３の目的地を予測する処理とは別に、予め実行するようにしてもよい。
【０３２４】
ステップＳ１４４において、予測メインプロセス部３３の現在地ノード推定部４１は、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する状態ノード（現在地ノード）を推定する。より具体的には、現在地ノード推定部４１は、学習ブロック１１の学習により得られたユーザ活動モデルを用いて、移動履歴データに対応する状態ノード系列データを算出する。そして、現在地ノード推定部４１は、状態ノード系列データの最後の状態ノードを現在地ノードとする。状態ノード系列データの算出には、ビタビアルゴリズムが採用される。
【０３２５】
ステップＳ１４５において、予測メインプロセス部３３の目的地経由地予測部４２は、図２８を参照して説明した、現在地ノード以降のツリー探索処理を実行する。ツリー探索処理と同時に、目的地および経由地までの経路（ノード系列）の生起確率も、式（１３）により求められる。
【０３２６】
ステップＳ１４６において、予測ポストプロセス部３４は、図３２を参照して説明した、代表経路の選択処理を実行する。
【０３２７】
ステップＳ１４７において、予測ポストプロセス部３４は、上述した式（１５）により、選択された各代表経路の所要時間を算出する。
【０３２８】
ステップＳ１４８において、予測ポストプロセス部３４は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力して、処理を終了する。
【０３２９】
以上のように、予測ブロック１３の処理では、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られたユーザ活動モデルとを用いて、ユーザの現在地から目的地までの経路が探索される。学習により得られた状態ノードに目的地と経由地の属性が付与されているので、経由地を目的地として予測することを防止することができる。
【０３３０】
また、学習により得られた状態ノードに目的地と経由地の属性が付与されているので、同一目的地への経路であっても、経由地なしの経路と、経由地ありの経路を代表経路として出力することができる。
【０３３１】
［コンピュータの構成例］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０３３２】
図３４は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０３３３】
コンピュータにおいて、CPU（Central Processing Unit）２２１，ROM（Read Only Memory）２２２，RAM（Random Access Memory）２２３は、バス２２４により相互に接続されている。
【０３３４】
バス２２４には、さらに、入出力インタフェース２２５が接続されている。入出力インタフェース２２５には、入力部２２６、出力部２２７、記憶部２２８、通信部２２９、ドライブ２３０、およびGPSセンサ２３１が接続されている。
【０３３５】
入力部２２６は、キーボード、マウス、マイクロホンなどよりなる。出力部２２７は、ディスプレイ、スピーカなどよりなる。記憶部２２８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２２９は、ネットワークインタフェースなどよりなる。ドライブ２３０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体２３２を駆動する。上述のセンサデバイスとしてのGPSセンサ２３１は、現在地の位置（緯度および経度）のデータと、そのときの時刻からなる３次元データを出力する。
【０３３６】
以上のように構成されるコンピュータでは、CPU２２１が、例えば、記憶部２２８に記憶されているプログラムを、入出力インタフェース２２５及びバス２２４を介して、RAM２２３にロードして実行することにより、上述した一連の処理が行われる。
【０３３７】
コンピュータ（CPU２２１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体２３２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０３３８】
コンピュータでは、プログラムは、リムーバブル記録媒体２３２をドライブ２３０に装着することにより、入出力インタフェース２２５を介して、記憶部２２８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２２９で受信し、記憶部２２８にインストールすることができる。その他、プログラムは、ROM２２２や記憶部２２８に、あらかじめインストールしておくことができる。
【０３３９】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０３４０】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０３４１】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０３４２】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０３４３】
１ 予測システム， １１ 学習ブロック， １３ 予測ブロック， ２２ 学習プリプロセス部， ２３ 学習メインプロセス部， ２４ 学習ポストプロセス部， ２５ 目的地経由地検出部， ３２ 予測プリプロセス部， ３３ 予測メインプロセス部， ３４ 予測ポストプロセス部， ４１ 現在地ノード推定部， ４２ 目的地経由地予測部， ７４ 移動属性識別付与部， ７５ 滞在状態加工部， ９２ 移動属性識別部， ９３ 移動属性付与部
【特許請求の範囲】
【請求項１】
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備えるデータ処理装置。
【請求項２】
前記移動履歴データを構成する各３次元データに対し、少なくとも滞在状態または移動状態を識別する移動属性識別手段をさらに備え、
前記目的地経由地推定手段は、前記滞在状態が所定の閾値時間以上継続する前記移動履歴データに対応する前記状態ノードを前記目的地ノードに推定し、前記滞在状態の継続時間が前記所定の閾値時間未満である前記移動履歴データに対応する前記状態ノードを前記経由地ノードに推定する
請求項１に記載のデータ処理装置。
【請求項３】
滞在状態が前記所定の閾値時間以上継続している前記移動履歴データを、同一位置のデータに修正するデータ加工手段をさらに備え、
前記学習手段は、前記データ加工手段により加工された前記学習用データを用いて、前記確率モデルのパラメータを学習する
請求項２に記載のデータ処理装置。
【請求項４】
前記学習手段は、前記ユーザの活動を表す確率モデルとして、隠れマルコフモデルを採用し、前記隠れマルコフモデルで前記移動履歴データをモデル化したときの尤度が最大となるように前記パラメータを学習する
請求項１に記載のデータ処理装置。
【請求項５】
前記現在地推定手段は、現在から所定時間以内の前記ユーザの移動履歴データに対応する、学習により得られた前記パラメータを用いた前記確率モデルの状態ノード系列データを算出し、算出された前記状態ノード系列データの最終ノードを、前記ユーザの現在地に相当するノードとする
請求項１に記載のデータ処理装置。
【請求項６】
前記探索手段は、前記ユーザの前記現在地ノードから遷移可能な状態ノードでなるツリー構造において、前記現在地ノードを出発点として、前記目的地ノード若しくは遷移先のない終端ノードになるまで全ての状態ノードを探索したか、または、探索回数が終了条件としての所定の回数を満たすまで探索し、前記ユーザの現在地から目的地までの経路を、前記現在地ノードからの状態ノード系列として求める
請求項１に記載のデータ処理装置。
【請求項７】
前記探索手段は、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される
請求項６に記載のデータ処理装置。
【請求項８】
前記算出手段は、探索された前記目的地ノードへの状態ノード系列の、規格化された遷移確率の同時確率を演算することで、前記目的地までの経路の選択確率を算出する
請求項１に記載のデータ処理装置。
【請求項９】
前記算出手段は、前記目的地への経路が複数存在する場合、複数の前記選択確率の和により、前記目的地への到達確率を算出する
請求項８に記載のデータ処理装置。
【請求項１０】
前記算出手段は、探索結果の前記ユーザの現在地から目的地までの経路のうち、目的地別に選択確率の最も高い経路を、各目的地の代表経路とし、その所要時間を、前記目的地までの所要時間として算出する
請求項８に記載のデータ処理装置。
【請求項１１】
前記算出手段は、前記目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方を、各目的地の代表経路とし、それぞれの所要時間を、前記目的地までの所要時間として算出する
請求項８に記載のデータ処理装置。
【請求項１２】
前記算出手段は、前記目的地までの所要時間を、現在時刻から、前記目的地ノードの直前の状態ノードにいて、前記目的地ノードに移動するときまでの時間の期待値として算出する
請求項１に記載のデータ処理装置。
【請求項１３】
ユーザの移動履歴データを処理するデータ処理装置が、
学習用データとして取得される前記移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習し、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
探索された前記目的地への到達確率と所要時間を算出する
ステップを含むデータ処理方法。
【請求項１４】
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させるためのプログラム。
【請求項１】
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備えるデータ処理装置。
【請求項２】
前記移動履歴データを構成する各３次元データに対し、少なくとも滞在状態または移動状態を識別する移動属性識別手段をさらに備え、
前記目的地経由地推定手段は、前記滞在状態が所定の閾値時間以上継続する前記移動履歴データに対応する前記状態ノードを前記目的地ノードに推定し、前記滞在状態の継続時間が前記所定の閾値時間未満である前記移動履歴データに対応する前記状態ノードを前記経由地ノードに推定する
請求項１に記載のデータ処理装置。
【請求項３】
滞在状態が前記所定の閾値時間以上継続している前記移動履歴データを、同一位置のデータに修正するデータ加工手段をさらに備え、
前記学習手段は、前記データ加工手段により加工された前記学習用データを用いて、前記確率モデルのパラメータを学習する
請求項２に記載のデータ処理装置。
【請求項４】
前記学習手段は、前記ユーザの活動を表す確率モデルとして、隠れマルコフモデルを採用し、前記隠れマルコフモデルで前記移動履歴データをモデル化したときの尤度が最大となるように前記パラメータを学習する
請求項１に記載のデータ処理装置。
【請求項５】
前記現在地推定手段は、現在から所定時間以内の前記ユーザの移動履歴データに対応する、学習により得られた前記パラメータを用いた前記確率モデルの状態ノード系列データを算出し、算出された前記状態ノード系列データの最終ノードを、前記ユーザの現在地に相当するノードとする
請求項１に記載のデータ処理装置。
【請求項６】
前記探索手段は、前記ユーザの前記現在地ノードから遷移可能な状態ノードでなるツリー構造において、前記現在地ノードを出発点として、前記目的地ノード若しくは遷移先のない終端ノードになるまで全ての状態ノードを探索したか、または、探索回数が終了条件としての所定の回数を満たすまで探索し、前記ユーザの現在地から目的地までの経路を、前記現在地ノードからの状態ノード系列として求める
請求項１に記載のデータ処理装置。
【請求項７】
前記探索手段は、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される
請求項６に記載のデータ処理装置。
【請求項８】
前記算出手段は、探索された前記目的地ノードへの状態ノード系列の、規格化された遷移確率の同時確率を演算することで、前記目的地までの経路の選択確率を算出する
請求項１に記載のデータ処理装置。
【請求項９】
前記算出手段は、前記目的地への経路が複数存在する場合、複数の前記選択確率の和により、前記目的地への到達確率を算出する
請求項８に記載のデータ処理装置。
【請求項１０】
前記算出手段は、探索結果の前記ユーザの現在地から目的地までの経路のうち、目的地別に選択確率の最も高い経路を、各目的地の代表経路とし、その所要時間を、前記目的地までの所要時間として算出する
請求項８に記載のデータ処理装置。
【請求項１１】
前記算出手段は、前記目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方を、各目的地の代表経路とし、それぞれの所要時間を、前記目的地までの所要時間として算出する
請求項８に記載のデータ処理装置。
【請求項１２】
前記算出手段は、前記目的地までの所要時間を、現在時刻から、前記目的地ノードの直前の状態ノードにいて、前記目的地ノードに移動するときまでの時間の期待値として算出する
請求項１に記載のデータ処理装置。
【請求項１３】
ユーザの移動履歴データを処理するデータ処理装置が、
学習用データとして取得される前記移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習し、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
探索された前記目的地への到達確率と所要時間を算出する
ステップを含むデータ処理方法。
【請求項１４】
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルで表し、そのパラメータを学習する学習手段と、
学習により得られた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【公開番号】特開２０１１−２５２８４４（Ｐ２０１１−２５２８４４Ａ）
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願番号】特願２０１０−１２８０６８（Ｐ２０１０−１２８０６８）
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年１２月１５日（２０１１．１２．１５）
【国際特許分類】
【出願日】平成２２年６月３日（２０１０．６．３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]