(57)【要約】【課題】未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにする。【解決手段】学習メインプロセス部２３は、学習用データとしての移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める。学習用データとしての移動履歴データが供給された場合、学習メインプロセス部２３は、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、既知の場合は、既存モデルのパラメータの更新を行い、未知の場合は、新規モデルを生成し、既存モデルと結合した更新モデルを生成する。本発明は、例えば、移動履歴データから目的地を予測するデータ処理装置に適用できる。【選択図】図１
2012008659.tif 000002
【特許請求の範囲】
【請求項１】
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備え、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段と
を有し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
データ処理装置。
【請求項２】
前記新規モデル生成手段は、前記確率モデルとして、一つの状態ノードが前記ユーザの移動履歴データの少なくとも２つの連続するサンプルを反映するモデルを採用する
請求項１に記載のデータ処理装置。
【請求項３】
前記一つの状態ノードが前記ユーザの移動履歴データの少なくとも２つの連続するサンプルを反映するモデルは、一つの状態ノードへの遷移時に、前記ユーザの移動履歴データの少なくとも２つの連続するサンプルを同時に出力するモデルである
請求項２に記載のデータ処理装置。
【請求項４】
前記一つの状態ノードが前記ユーザの移動履歴データの少なくとも２つの連続するサンプルを反映するモデルは、さらに、left-to-rightの制約を設定したモデルである
請求項３に記載のデータ処理装置。
【請求項５】
前記新規モデル生成手段は、Baum-Welchの最尤推定法により、前記確率モデルのパラメータを求める
請求項１に記載のデータ処理装置。
【請求項６】
前記新規モデル生成手段は、前記Baum-Welchの最尤推定法により、前記未知の経路の移動履歴データに対応する前記新規モデルのパラメータを求め、前記未知の経路の移動履歴データを前記新規モデルの状態ノードに変換したノード系列データを生成し、各状態ノードの状態頻度と遷移頻度を計算して、前記未知の経路の移動履歴データの前記新規モデルのパラメータに対応する前記ノード系列データのパラメータを求める
請求項５に記載のデータ処理装置。
【請求項７】
前記既知未知判定手段は、前記新たな学習用データが既知の経路の移動履歴データであると判定した場合、前記既知の経路の移動履歴データを前記既存モデルの状態ノードに変換したノード系列データを生成し、
前記パラメータ更新手段は、前記既知の経路の移動履歴データを前記既存モデルの状態ノードに変換したノード系列データから、各状態ノードの状態頻度と遷移頻度を更新し、前記既存モデルのパラメータとしての前記ノード系列データのパラメータを更新する
請求項６に記載のデータ処理装置。
【請求項８】
前記既知未知判定手段は、前記既存モデルに未知の経路の移動履歴データを引き受ける一つの状態ノードを追加した未知状態追加モデルにより、前記新たな学習用データとしての移動履歴データに対応する状態ノードを認識し、前記新たな学習用データとしての移動履歴データに対応する前記未知状態追加モデルのノード系列データの観測尤度を求め、求められた観測尤度の大きさから、既知または未知の判定を行う
請求項６に記載のデータ処理装置。
【請求項９】
前記既存モデルに追加される、未知の経路の移動履歴データを引き受ける一つの状態ノードの、前記既知モデルの各状態ノードとの間の遷移確率は、既知モデルの状態ノード間の遷移確率のどれよりも低く、分散値は、移動履歴データの取り得る範囲を網羅する値である
請求項８に記載のデータ処理装置。
【請求項１０】
前記既知未知判定手段は、前記未知状態追加モデルのノード系列データの観測尤度に対し、既知と未知の二状態で構成され、自己遷移する確率が大きいHMMを用いてビタビ判定を行うことにより、既知または未知の判定を行う
請求項８に記載のデータ処理装置。
【請求項１１】
前記既知未知判定手段は、前記未知の経路の移動履歴データが前記既知の経路の移動履歴データと接続されている場合、その接続先の前記既知の経路の移動履歴データに対応する状態ノードも出力し、
前記新規モデル結合手段は、前記既存モデルがM個、前記新規モデルがN個の状態ノードからなる場合、前記更新モデルの遷移確率を定義する(M＋N)行(M＋N)列の遷移確率テーブルを生成し、
生成した前記遷移確率テーブルの第１行第１列から第M行M列の左上領域の各要素が、前記既存モデルの状態ノードの遷移確率に対応し、
生成した前記遷移確率テーブルの第(M＋１)行第(M＋１)列から第(M＋N)行(M＋N)列の右下領域の各要素が、前記新規モデルの状態ノードの遷移確率に対応し、
生成した前記遷移確率テーブルの第１行第(M+1)列から第M行(M＋N)列の右上領域の各要素が、前記新規モデルが前記既存モデルのノード系列データの後に接続されるときの接続先の状態ノードに対応し、
生成した前記遷移確率テーブルの第（M+1）行第１列から第(M＋N)行M列の左下領域の各要素が、前記新規モデルの後に前記既存モデルのノード系列データが接続されるときの接続先の状態ノードに対応する
請求項１に記載のデータ処理装置。
【請求項１２】
前記移動履歴データを構成する各３次元データに対し、少なくとも滞在状態または移動状態を識別する移動属性識別手段をさらに備え、
前記目的地経由地推定手段は、前記滞在状態が所定の閾値時間以上継続する前記移動履歴データに対応する前記状態ノードを前記目的地ノードに推定し、前記滞在状態の継続時間が前記所定の閾値時間未満である前記移動履歴データに対応する前記状態ノードを前記経由地ノードに推定する
請求項１に記載のデータ処理装置。
【請求項１３】
ユーザの移動履歴データを処理するデータ処理装置の、
学習手段が、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求め、
目的地経由地推定手段が、求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
現在地推定手段が、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
探索手段が、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
算出手段が、探索された前記目的地への到達確率と所要時間を算出する
ステップを含み、
前記学習手段のステップでは、
既知未知判定手段が、前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、
パラメータ更新手段が、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新し、
新規モデル生成手段が、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求め、
新規モデル結合手段が、前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段のステップでは、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
データ処理方法。
【請求項１４】
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させ、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段
としての機能を含み、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
ためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理方法、およびプログラムに関し、特に、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにするデータ処理装置、データ処理方法、およびプログラムに関する。
【背景技術】
【０００２】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである（例えば、特許文献１，２、非特許文献１）。
【０００３】
本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願２００９−１８０７８０号（以下、先願１という）として先に提案している。先願１の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。先願１では、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの移動履歴の時系列データ（移動履歴データ）を学習した確率的状態遷移モデルを用いて、ユーザの現在の位置を認識し、所定時間後のユーザの行き先（場所）を予測する例が示されている。
【０００４】
さらに、本出願人は、先願１を発展させ、「所定時間後」という現在時刻からの経過時間の指定がない場合であっても、複数の目的地への到達確率、経路、時間を予測する方法を、特願２００９−２０８０６４号（以下、先願２という）として提案した。先願２の方法では、確率的状態遷移モデルを構成する状態ノードに、”移動状態”かまたは”滞在状態”の属性が付与された。そして、確率的状態遷移モデルを構成する状態ノードの中から、目的地の状態ノードとして”滞在状態”の状態ノードを見つけることで、目的地の候補を自動的に検出することができた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−１３４０８０号公報
【特許文献２】特開２００８−２０４０４０号公報
【非特許文献】
【０００６】
【非特許文献１】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、学習データとして新たに取得された移動履歴データを用いて追加学習する場合、学習時間を短縮させるため、新たに取得された移動履歴データのみを学習する差分学習を行うのが一般的である。
【０００８】
しかしながら、差分学習は、通常、同一のモデルのパラメータを変化させるものである。新たに取得された移動履歴データが既知の経路を再度移動したデータであれば、既存の確率的状態遷移モデルのパラメータを更新させればよい。しかし、取得された移動履歴データがこれまでの学習にない未知の経路を移動したデータであれば、新たな状態ノードを追加し、追加した状態ノードに学習させることが望ましいが、従来の差分学習では、ユーザの行動範囲のトポロジーを成長させることは難しい。
【０００９】
本発明は、このような状況に鑑みてなされたものであり、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにするものである。
【課題を解決するための手段】
【００１０】
本発明の一側面のデータ処理装置は、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備え、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段と
を有し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる。
【００１１】
本発明の一側面のデータ処理方法は、
ユーザの移動履歴データを処理するデータ処理装置の、
学習手段が、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求め、
目的地経由地推定手段が、求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
現在地推定手段が、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
探索手段が、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
算出手段が、探索された前記目的地への到達確率と所要時間を算出する
ステップを含み、
前記学習手段のステップでは、
既知未知判定手段が、前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、
パラメータ更新手段が、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新し、
新規モデル生成手段が、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求め、
新規モデル結合手段が、前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段のステップでは、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる。
【００１２】
本発明の一側面のプログラムは、
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させ、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段
としての機能を含み、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
ためのプログラムである。
【００１３】
本発明の一側面においては、学習手段において、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータが求められ、目的地経由地推定手段において、求められたパラメータを用いた確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードが推定され、現在地推定手段において、学習用データとは別の、現在から所定時間以内のユーザの移動履歴データが、学習により得られたパラメータを用いた確率モデルに入力され、ユーザの現在地に相当する現在地ノードが推定され、探索手段において、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られた確率モデルとを用いて、ユーザの現在地から目的地までの経路が探索され、算出手段において、探索された目的地への到達確率と所要時間が算出される。
学習手段では、既知未知判定手段において、確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかが判定され、パラメータ更新手段において、新たな学習用データが既知の経路の移動履歴データであると判定された場合、既に求めた確率モデルである既存モデルのパラメータが更新され、新規モデル生成手段において、新たな学習用データが未知の経路の移動履歴データであると判定された場合、未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータが求められ、新規モデル結合手段において、既存モデルのパラメータと、新規モデルのパラメータを合成することで、既存モデルと新規モデルを結合した更新モデルが生成され、目的地経由地推定手段、現在地推定手段、探索手段、および算出手段のステップでは、確率モデルが新たな学習用データにより更新された場合、更新後の確率モデルを用いた処理が行われる。
【発明の効果】
【００１４】
本発明の一側面によれば、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができる。
【図面の簡単な説明】
【００１５】
【図１】本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【図２】予測システムのハードウエア構成例を示すブロック図である。
【図３】移動履歴データの例を示す図である。
【図４】HMMの例を示す図である。
【図５】left-to-right型のHMMの例を示す図である。
【図６】スパース制約を与えたHMMの例を示す図である。
【図７】学習プリプロセス部の詳細構成例を示すブロック図である。
【図８】学習プリプロセス部の処理について説明する図である。
【図９】移動属性識別付与部の詳細構成例を示すブロック図である。
【図１０】移動属性識別部の学習器の構成例を示すブロック図である。
【図１１】行動状態をカテゴリごとに分類する場合の分類例を示す図である。
【図１２】行動状態ラベリング部の処理例を説明する図である。
【図１３】行動状態ラベリング部の処理例を説明する図である。
【図１４】図１０の行動状態学習部の構成例を示すブロック図である。
【図１５】移動属性識別部の詳細構成例を示すブロック図である。
【図１６】移動属性識別部の学習器のその他の構成例を示すブロック図である。
【図１７】移動属性識別部のその他の構成例を示すブロック図である。
【図１８】学習プリプロセス部の処理を説明するフローチャートである。
【図１９】図１の学習メインプロセス部の詳細構成例を示すブロック図である。
【図２０】既知未知判定部の詳細な構成例を示すブロック図である。
【図２１】未知状態ノード追加部による未知状態追加モデルの構築処理を説明するフローチャートである。
【図２２】未知状態追加モデルの初期確率テーブルを説明する図である。
【図２３】未知状態追加モデルの遷移確率テーブルを説明する図である。
【図２４】未知状態追加モデルの中心値テーブルを説明する図である。
【図２５】未知状態追加モデルの分散値テーブルを説明する図である。
【図２６】既知未知判定部の既知未知判定処理を説明する説明するフローチャートである。
【図２７】既知未知判定処理を行った結果の例を示す図である。
【図２８】既知未知判定処理を行った結果の例を示す図である。
【図２９】新規モデル生成部の詳細な構成例を示すブロック図である。
【図３０】通常の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の状態siのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。学習ブロック１１は、各状態siに対応する地図上の一点（中心値μi）とその分散値σi２、および状態遷移確率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センサは、トンネルや地下では人工衛星を捕捉することができないため、移動履歴データの取得間隔が長くなることがある。移動履歴データが長い時間欠落している場合には、ユーザがどこにいたかを推定することが難しくなる。そこで、データ接続分割部７１は、取得された移動履歴データにおいて、前後の取得時刻の間隔が所定の時間間隔（以下、欠落閾値時間という。）以上ある場合に、その間隔の前後で移動履歴データを分割する。ここで、欠落閾値時間は、例えば、５分、１０分、１時間などである。
【００９０】
データ異常除去部７２は、移動履歴データの明らかな異常を除去する処理を行う。例えば、ある時刻の位置のデータが、その前後の位置と１００ｍ以上も離れていて、跳躍している場合、その位置のデータは異常である。そこで、データ異常除去部７２は、ある時刻の位置のデータが、その前後の両方の位置と所定の距離以上離れている場合、その３次元データを移動履歴データから除去する。
【００９１】
再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを、線形補間等により補完する処理を行う。即ち、取得時刻の時間間隔が欠落閾値時間以上である場合には、データ接続分割部７１により、移動履歴データが分割されるが、欠落閾値時間未満のデータの欠落は残っている。そこで、再サンプリング処理部７３は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを補完する。
【００９２】
移動属性識別付与部７４は、移動履歴の３次元データそれぞれが、同一場所に滞在（停止）している”滞在状態”か、または、移動している”移動状態”のいずれであるかの移動属性を識別し、付与する。これにより、移動履歴データの各３次元データに移動属性が付与された、移動属性付き移動履歴データが生成される。
【００９３】
滞在状態加工部７５は、移動属性識別付与部７４から供給される移動属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。より具体的には、滞在状態加工部７５は、”滞在状態”の移動属性が所定時間（以下、滞在閾値時間という。）以上継続している場合、その前後で移動履歴データを分割する。また、滞在状態加工部７５は、”滞在状態”の移動属性が滞在閾値時間未満で継続している場合には、その滞在閾値時間以内の所定時間続く、”滞在状態”の複数の３次元データの位置のデータをホールドする（同一位置のデータに修正する）。これにより、同一の目的地や経由地の移動履歴データに対して複数の”滞在状態”ノードが割り当てられることを防止することができる。換言すれば、同一の目的地や経由地を複数のノードで表現することを防止することができる。
【００９４】
［学習プリプロセス部２２の処理］
図８は、学習プリプロセス部２２の学習プリプロセス処理を概念的に示したイメージ図である。
【００９５】
図８上段に示される、再サンプリング処理部７３によるデータ補完後の移動履歴データ８１に対して、移動属性識別付与部７４が、”滞在状態”または”移動状態”の移動属性を識別し、付与する。その結果、図８中段に示される、移動属性付き移動履歴データ８２が生成される。
【００９６】
図８中段の移動属性付き移動履歴データ８２において、”ｍ１”および”ｍ２”は、”移動状態”の移動属性を表し、”ｕ”は、”滞在状態”の移動属性を表す。なお、”ｍ１”と”ｍ２”は、同じ”移動状態”でも、移動手段（車、バス、電車、徒歩など）が異なる。
【００９７】
そして、図８中段の、移動属性付き移動履歴データ８２に対して、滞在状態加工部７５により、移動履歴データを分割およびホールドする処理が実行され、図８下段の、移動属性付き移動履歴データ８３（８３Ａおよび８３Ｂ）が生成される。
【００９８】
移動属性付き移動履歴データ８３では、移動属性付き移動履歴データ８２において２回目に発生した”移動状態”の箇所（３次元データ）で分割処理が行われ、移動属性付き移動履歴データ８３Ａと８３Ｂに分割されている。
【００９９】
分割処理では、最初に、移動属性付き移動履歴データ８２の２回目に発生した”移動状態”までと、それ以降の複数の３次元データとで分割され、２つの移動属性付き移動履歴データ８３Ａおよび８３Ｂとされる。次に、分割後の移動属性付き移動履歴データ８３Ａおよび８３Ｂのうち、時間的に早い移動属性付き移動履歴データ８３Ａの最後の滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられる。これにより、不要な移動履歴データが削除されるので、学習時間を短縮することができる。
【０１００】
なお、図８の例では、移動属性付き移動履歴データ８２の３回目に発生した” 複数の移動状態”の３次元データも滞在閾値時間以上の”移動状態”が続くデータであり、同様の分割処理が行われている。しかし、分割後の後ろの３次元データが存在しないため、滞在閾値時間以上の複数の”移動状態”の３次元データが、１つの”滞在状態”の３次元データにまとめられるのみとなっている。
【０１０１】
一方、移動属性付き移動履歴データ８３Ａのうち、１回目の”移動状態”の移動履歴データでは、ホールド処理が実行されている。ホールド処理後は、３つの”移動状態”の３次元データ｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ，ｙｋ），（ｔｋ＋１，ｘｋ＋１，ｙｋ＋１）｝が、｛（ｔｋ−１，ｘｋ−１，ｙｋ−１），（ｔｋ，ｘｋ−１，ｙｋ−１），（ｔｋ＋１，ｘｋ−１，ｙｋ−１）｝となっている。即ち、位置のデータが”移動状態”の最初の位置のデータに修正されている。なお、ホールド処理では、位置のデータは、”移動状態”の最初の位置のデータに変更するのではなく、位置の平均値、”移動状態”の期間の真ん中の時刻の位置のデータ等に変更してもよい。
【０１０２】
［移動属性識別付与部７４の構成例］
図９は、移動属性識別付与部７４の詳細構成例を示すブロック図である。
【０１０３】
移動属性識別付与部７４は、移動速度演算部９１、移動属性識別部９２、および移動属性付与部９３により構成される。
【０１０４】
移動速度演算部９１は、供給される移動履歴データから移動速度を演算する。
【０１０５】
具体的には、一定の時間間隔でｋステップ目（ｋ個目）に得られるときの３次元データを、時刻ｔｋ、経度ｙｋ、緯度ｘｋと表すと、ｋステップ目のｘ方向の移動速度ｖｘｋおよびｙ方向の移動速度ｖｙｋは、次式（１）により計算することができる。
【０１０６】
【数１】
2012008659.tif 000003
【０１０７】
式（１）では、緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【０１０８】
また、移動速度演算部９１は、式（１）で得られる移動速度ｖｘｋおよびｖｙｋからさらに、式（２）で表されるｋステップ目の移動速度ｖｋと進行方向の変化θｋを求め、これを利用することができる。
【０１０９】
【数２】
2012008659.tif 000004
【０１１０】
式（２）で表される移動速度ｖｋと進行方向の変化θｋを利用する方が、式（１）の移動速度ｖｘｋおよびｖｙｋよりも以下の点で、特徴をうまく取り出すことができる。
【０１１１】
１．移動速度ｖｘｋおよびｖｙｋのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段（電車や徒歩など）であっても角度が異なった場合に識別できない可能性があるが、移動速度ｖｋであればそのような可能性が少ない。
２．移動速度の絶対的な大きさ（｜ｖ｜）だけで学習すると、機器のノイズによって生じる｜ｖ｜のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
３．移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【０１１２】
以上の理由から、本実施の形態では、移動速度演算部９１は、移動速度のデータとして、式（２）で表される移動速度ｖｋと進行方向の変化θｋを求め、移動属性識別部９２に供給する。
【０１１３】
移動速度演算部９１は、移動速度ｖｋと進行方向の変化θｋの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理（前処理）を行うことができる。
【０１１４】
なお、センサデバイスのなかには、移動速度を出力できるものも存在する。そのようなセンサデバイスが採用されている場合、移動速度演算部９１を省略し、センサデバイスが出力する移動速度をそのまま利用することができる。以下では、進行方向の変化θｋを、進行方向θｋと略記する。
【０１１５】
移動属性識別部９２は、供給される移動速度に基づいて移動属性を識別し、認識結果を移動属性付与部９３に供給する。より具体的には、移動属性識別部９２は、ユーザの行動状態（移動状態）を確率的状態遷移モデル（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の状態ノードを認識する。状態ノード認識部１８１は、認識された現在の状態ノードのノード番号を行動モード認識部１８２に供給する。
【０１６４】
行動モード認識部１８２は、状態ノード認識部１８１で認識された状態ノードで、最も確率の高い行動モードを、移動属性として出力する。
【０１６５】
［学習プリプロセス部２２の処理］
図１８は、学習プリプロセス部２２による学習プリプロセス処理のフローチャートである。
【０１６６】
学習プリプロセス処理では、最初に、ステップＳ１において、データ接続分割部７１が、移動履歴データの接続および分割の処理を行う。
【０１６７】
ステップＳ２において、データ異常除去部７２が、移動履歴データの明らかな異常を除去する処理を行う。
【０１６８】
ステップＳ３において、再サンプリング処理部７３が、取得時刻の時間間隔が滞在閾値時間未満の欠落データを、線形補間等により補完する処理を行う。
【０１６９】
ステップＳ４において、移動属性識別付与部７４が、移動履歴の３次元データそれぞれに対し、”滞在状態”かまたは”移動状態”の移動属性を識別し、付与する。
【０１７０】
ステップＳ５において、滞在状態加工部７５が、移動属性識別付与部７４から供給される属性付き移動履歴データに基づいて、移動属性が”滞在状態”の３次元データを加工する。そして、滞在状態加工部７５は、加工処理後の、移動属性付き移動履歴データを学習メインプロセス部２３に出力して、処理を終了する。
【０１７１】
以上のように、学習プリプロセス部２２では、移動履歴データが、必要に応じて分割等された後、移動属性が付与されることにより、移動属性付き移動履歴データとされて、学習メインプロセス部２３に供給される。
【０１７２】
［学習メインプロセス部２３の詳細構成例］
図１９は、学習ブロック１１の学習メインプロセス部２３の詳細構成例を示すブロック図である。
【０１７３】
学習メインプロセス部２３は、既知未知判定部２０１、新規モデル生成部２０２、新規モデル結合部２０３、パラメータ更新部２０４、および更新モデル整理部２０５により構成される。
【０１７４】
学習プリプロセス部２２（図１）から供給される移動履歴データが、既知未知判定部２０１に供給される。また、少なくとも１回以上、学習メインプロセス部２３による学習が既に行われている場合、ユーザ別モデルパラメータ記憶部１２（図１）から、先の学習により得られたユーザ活動モデルのパラメータが、既存モデルのパラメータとして取得される。既存モデルのパラメータは、既知未知判定部２０１、新規モデル結合部２０３、およびパラメータ更新部２０４に供給される。
【０１７５】
既知未知判定部２０１は、学習プリプロセス部２２から供給された移動履歴データが既知の経路の移動履歴データであるか否か判定する。なお、２回目以降の学習では、供給された移動履歴データの一部が未知の経路の移動履歴データで、残りの一部が既知の経路の移動履歴データとなっていることもある。既知未知判定部２０１は、既知と判定された移動履歴データについては、移動履歴データの各３次元データが既存モデルのどの状態ノードに相当するか推定する。そして、既知未知判定部２０１は、既知の移動履歴データと、それに対応するノード系列データをパラメータ更新部２０４に供給する。
【０１７６】
一方、既知未知判定部２０１は、供給された移動履歴データが未知の経路の移動履歴データであると判定した場合、未知の経路の移動履歴データを新規モデル生成部２０２に供給する。また、未知の経路の移動履歴データが既知の経路の移動履歴データと接続されている場合、既知未知判定部２０１は、未知の経路の移動履歴データの接続先となる、前後の既知の移動履歴データに対応する既存モデルの状態ノードを新規モデル生成部２０２に供給する。なお、未知の移動履歴データの後の既存モデルの状態ノードが存在しない場合、例えば、既知の経路から未知の経路を通って未知の目的地へ到達し、戻ってくるような場合には、前の既存モデルの状態ノードのみが新規モデル生成部２０２に供給される。
【０１７７】
１回目の学習では、学習プリプロセス部２２から供給された移動履歴データすべてが未知の移動履歴データとして新規モデル生成部２０２に供給される。また、１回目の学習では、前後の既存モデルの状態ノードは存在しないので、新規モデル生成部２０２への供給はない。
【０１７８】
新規モデル生成部２０２は、既知未知判定部２０１から供給された未知の移動履歴データを用いてユーザ活動モデルを学習する。即ち、新規モデル生成部２０２は、未知の移動履歴データを確率的状態遷移モデルでモデル化したときのパラメータを求め、新規モデル結合部２０３に供給する。ここで学習されたユーザ活動モデルが、先の学習により得られている既存モデルとは別の、新規モデルとなる。なお、１回目の学習と２回目以降の学習は、学習対象の未知の移動履歴データのデータ量が異なるのみであり、同一の学習により、ユーザ活動モデルのパラメータを求めることができる。
【０１７９】
新規モデル生成部２０２は、学習により得られた新規モデルのパラメータを、新規モデル結合部２０３に供給する。また、新規モデル生成部２０２は、前後の既存モデルの状態ノードが既知未知判定部２０１から供給された場合には、その前後の既存モデルの状態ノードも、新規モデル結合部２０３に供給する。
【０１８０】
新規モデル結合部２０３は、２回目以降の学習において、未知の移動履歴データに基づいて、先の学習により得られている既存モデルを更新する。即ち、新規モデル結合部２０３は、未知の移動履歴データの前後の既存モデルの状態ノードに基づいて、既存モデルに、新規モデル生成部２０２からの新規モデルを結合し、更新後のユーザ活動モデルを生成する。新規モデル結合部２０３により更新されたユーザ活動モデルは、未知の移動履歴データに応じて状態ノードが追加されたトポロジー更新モデルである。
【０１８１】
なお、新規モデル結合部２０３において、新規モデル生成部２０２からの新規モデルと結合される既存モデルは、学習メインプロセス部２３に供給された移動履歴データに既知の経路の移動履歴データが全く含まれていない場合には、ユーザ別モデルパラメータ記憶部１２（図１）から取得された既存モデルとなる。一方、学習メインプロセス部２３に供給された移動履歴データに既知の経路の移動履歴データが一部含まれている場合には、新規モデルと結合される既存モデルは、パラメータ更新部２０４で更新された既存モデルとなる。
【０１８２】
パラメータ更新部２０４は、既知の移動履歴データと、それに対応するノード系列データに基づいて、先の学習により得られている既存モデルを更新する。更新された既存モデルのパラメータは、新規モデル結合部２０３と更新モデル整理部２０５に出力される。パラメータ更新部２０４による更新では、上述したように状態ノードの追加はない。
【０１８３】
更新モデル整理部２０５は、新規モデル結合部２０３により更新されたトポロジー更新モデル、または、パラメータ更新部２０４により更新されたパラメータ更新モデルのなかで、自己遷移のみで、他の状態ノードからの遷移が無い状態ノードを消去し、更新モデルを整理する。整理後の更新モデルのパラメータが、学習（更新学習）により得られたユーザ活動モデルのパラメータとして、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給される。
【０１８４】
次に、既知未知判定部２０１の詳細についてさらに説明する。
【０１８５】
［既知未知判定部２０１の詳細構成例］
図２０は、既知未知判定部２０１の詳細な構成例を示すブロック図である。
【０１８６】
学習メインプロセス部２３によって、少なくとも１回は学習処理が実行されている場合、既存モデルのパラメータがユーザ別モデルパラメータ記憶部１２（図１）から既存モデル構築部２２１に供給される。既存モデル構築部２２１は、供給された既存モデルのパラメータに基づいて、既存モデルを構築し、未知状態ノード追加部２２２に供給する。
【０１８７】
なお、１回も学習処理が実行されていない状態においては、既存モデル構築部２２１には、既存モデルの初期パラメータが予め設定されている。既存モデルの初期パラメータは、ノード数が１で、その１個の状態ノードの遷移確率が自己遷移のみ、中心値が３次元データ（時刻、経度、緯度）の取り得る範囲外の値、分散値が分散最小値、ノード頻度が１に設定されている。少なくとも１回の学習処理が実行され、ユーザ別モデルパラメータ記憶部１２（図１）から既存モデルのパラメータが供給されることで、既存モデルの初期パラメータが上書きされ、消去される。
【０１８８】
未知状態ノード追加部２２２は、既存モデル構築部２２１で構築された既存モデルに、未知の移動履歴データを引き受ける一つの状態ノード（以下、未知状態ノードと称する。）を追加する。これにより、既存モデルに１つの状態ノードが追加された学習モデル（以下、未知状態追加モデルと称する。）が構築され、状態ノード推定部２２３に供給される。
【０１８９】
状態ノード推定部２２３は、未知状態ノード追加部２２２から供給された未知状態追加モデルを用いたビタビアルゴリズムにより、供給された移動履歴データの各３次元データに対応する未知状態追加モデルの状態ノードを推定する。未知状態追加モデルには、未知の移動履歴データを引き受ける１つのノードが追加されているので、入力された移動履歴データが未知の移動履歴データであっても、ビタビ推定が破綻なく行われる。仮に、移動履歴データを引き受ける１つのノードが追加されていない場合には、未知の移動履歴データに対しては、対応する状態ノードが見つからず、ビタビ推定が破綻する。
【０１９０】
サンプル別尤度計算部２２４は、既知未知判定に用いる指標としての観測尤度の期待値を計算する。時刻ｔにおける観測尤度の期待値はL(t)で求められる。移動履歴データが既知の経路のデータである場合、観測尤度の期待値L(t)は大きくなり、移動履歴データが未知の経路のデータである場合、観測尤度の期待値L(t)は小さくなる。
【０１９１】
既知未知判定部２２６は、観測尤度の期待値L(t)の時系列データ（観測尤度系列データ）に対して、既知未知モデル記憶部２２５に記憶されている、既知未知の二状態モデルを用いたビタビ判定を行うことで、既知または未知の判定を行う。
【０１９２】
既知未知ポスト処理部２２７は、状態ノード推定部２２３が未知と推定した状態ノードで、既知未知判定部２２６が既知と判定したものを、未知に修正する。即ち、未知の判定は、状態ノード推定部２２３による推定結果が優先される。
【０１９３】
また、既知未知ポスト処理部２２７は、修正後の判定結果を参照して学習プリプロセス部２２（図１）から供給される移動履歴データを、新規モデル生成部２０２またはパラメータ更新部２０４に出力する。即ち、既知未知ポスト処理部２２７は、判定結果が既知である移動履歴データを、それに対応するノード系列データとともにパラメータ更新部２０４（図１９）に供給する。一方、既知未知ポスト処理部２２７は、判定結果が未知である移動履歴データを、新規モデル生成部２０２に供給する。未知の移動履歴データが既知の移動履歴データと接続されている場合には、既知未知ポスト処理部２２７は、未知の移動履歴データの接続先となる、前後の既知の移動履歴データに対応する既存モデルの状態ノードも新規モデル生成部２０２に供給する。
【０１９４】
［未知状態追加モデルの構築処理］
図２１のフローチャートを参照して、未知状態ノード追加部２２２による未知状態追加モデルの構築処理について説明する。
【０１９５】
初めに、ステップＳ２１において、未知状態ノード追加部２２２は、未知状態追加モデルの各状態ノードの初期確率を格納した、未知状態追加モデルの初期確率テーブルを生成する。
【０１９６】
初期確率テーブルは、図２２に示すように、既存モデルのM個の状態ノードに未知の移動履歴データを引き受ける１個の状態ノードを追加した（M+１）行１列のテーブルで、各状態ノードの初期確率は、例えば、等確率の１／（M+１）に設定される。
【０１９７】
ステップＳ２２において、未知状態ノード追加部２２２は、未知状態追加モデルの各状態ノードの遷移確率を格納した、未知状態追加モデルの遷移確率テーブルを生成する。
【０１９８】
遷移確率テーブルは、図２３に示すように、（M+１）行（M+１）列のテーブルで構成される。遷移確率テーブルでは、第１行第１列乃至第M行第M列の既存モデルの各状態間の状態遷移確率aijに（１−eps）が乗算される。また、遷移確率テーブルの第（M+１）列の各要素には、一番下の（M+１）行を除いて、epsが設定され、第（M+１）行の各要素には、一番下の（M+１）行を除いて、epsが設定される。ここで、epsは、例えば、1.0E-8程度の、１より十分小さい所定の値であり、既存モデルの状態ノード間の遷移確率のどれよりも低い。この未知状態追加モデルでは、既存モデルの各状態ノードから未知状態ノードへの遷移確率がepsで、未知状態ノードから既存モデルの各状態ノードへの遷移確率もepsに設定されたことを表す。また、第（M+１）行第（M+１）列の要素は未知状態ノードの自己遷移確率を表し、（１−M×eps）である。図２３の未知状態追加モデルでは、各行の総和が１となる。
【０１９９】
ステップＳ２３において、未知状態ノード追加部２２２は、未知状態追加モデルの各状態ノードの観測確率の中心値μsi（ｄ）を格納した、未知状態追加モデルの中心値テーブルを生成する。
【０２００】
図２４は、ステップＳ２３で生成される未知状態追加モデルの中心値テーブルを示している。未知状態追加モデルの中心値テーブルの列数は、移動履歴データの次元数Dに対応し、行数は状態ノードの数に対応する。従って、本実施の形態では、未知状態追加モデルの中心値テーブルは、（M+１）行３列で構成される。そして、未知状態追加モデルの中心値テーブルは、既存モデルのM行D列の中心値テーブルに、第（M+１）行目として、未知状態ノードの中心値μsM+1（１）＝E１，μsM+1（２）＝E２，μsM+1（３）＝E３の１行が追加された形となっている。
【０２０１】
ここで、E１，E２，E３それぞれには、任意の値を設定することができる。例えば、E１は、時刻の取り得る値（０時から２４時）の中心値である「１２」、E２およびE３は、緯度、経度の取り得る値（−１８０から１８０まで）の中心値である０とすることができる。また例えば、E１、E２、およびE３それぞれは、既存モデルのM個の中心値μs１（ｄ）乃至μsM（ｄ）の平均値とすることができる。
【０２０２】
ステップＳ２４において、未知状態ノード追加部２２２は、未知状態追加モデルの各状態ノードの観測確率の分散値σsi（ｄ）’2を格納した、未知状態追加モデルの分散値テーブルを生成する。
【０２０３】
図２５は、ステップＳ２４で生成される未知状態追加モデルの分散値テーブルを示している。未知状態追加モデルの分散値テーブルの列数は、移動履歴データの次元数Dに対応し、行数は状態ノードの数に対応する。従って、本実施の形態では、未知状態追加モデルの分散値テーブルは、（M+１）行３列で構成される。そして、未知状態追加モデルの分散値テーブルは、既存モデルのM行D列の分散値テーブルに、第（M+１）行目として、未知状態ノードの分散値σsM+1（１）２＝V１，σsM+1（２）２＝V２，σsM+1（３）２＝V３の１行が追加された形となっている。
【０２０４】
ここで、V１，V２，V３それぞれには、任意の値を設定することができるが大きい値であることが望ましい。例えば、V１は、０時から２４時の取り得る範囲を網羅できるように、「１２」の二乗より大きい値に設定する。V２およびV３は、−１８０から１８０までの緯度、経度の取り得る範囲を網羅できるように、１８０の二乗より大きい値に設定する。
【０２０５】
以上の処理により、未知状態追加モデルの各パラメータが設定され、未知状態追加モデルが構築される。
【０２０６】
[サンプル別尤度計算部２２４の観測尤度の計算]
次に、サンプル別尤度計算部２２４が行う観測尤度の計算について説明する。
【０２０７】
サンプル別尤度計算部２２４は、既知未知判定に用いる指標としての観測尤度の期待値L(t)を計算する。観測尤度の期待値L(t)は、次式（３）により計算することができる。
【数３】
2012008659.tif 000005
【０２０８】
ここで、N(xt｜μsi，σsi２)は、状態ノードsiから観測データxtを観測する観測尤度を表す。観測データは（μsi，σsi２)の正規分布に従う。また、δ（si，ｔ）は、時刻ｔの観測データxtが状態ノードsiから出力された確率である。この確率δ（si，ｔ）は、ビタビアルゴリズムを用いて算出されたものである。具体的には、確率δ（si，ｔ）は、次の１）、２）の処理によって算出される。１）状態ノードsiに到達する一つ前の状態ノードsi-1のうち、ビタビ推定確率と観測尤度N(Xt｜μsi，σsi２)の積が最も大きい状態ノードが選択される。２）選択された一つ前の状態ノードsi-1のビタビ推定確率の観測尤度に比例するように、現在の状態ノードsiのビタビ推定確率が規格化される。１）は、現在までの移動履歴データを、モデルの遷移の制約を考慮しながらビタビアルゴリズムで最尤推定することを意味し、２）は、最尤推定で生き残った尤度を規格化することで、現在どの状態ノードにいるかの確率を算出していることを意味している。
【０２０９】
次式（３）により計算される観測尤度の期待値L(t)は、未知状態追加モデルが観測データを十分に説明できるのであれば大きくなる。一方、未知状態追加モデルが観測データを十分に説明できない場合と、観測データが未知状態ノードで説明される場合には、観測尤度の期待値L(t)は小さくなる。従って、観測尤度の期待値L(t)の大きさで、既知または未知の判定を行うことができる。なお、以下では、観測尤度の期待値L(t)を、単に、観測尤度L(t)と称する。
【０２１０】
[既知未知判定部２２６の既知未知判定処理]
次に、図２６のフローチャートを参照して、サンプル別尤度計算部２２４で計算された観測尤度L(t)を用いて既知または未知の判定を行う、既知未知判定部２２６の既知未知判定処理について説明する。
【０２１１】
初めに、ステップＳ３１において、既知未知判定部２２６は、ノード系列データに対応する観測尤度L(t)の時系列データを、サンプル別尤度計算部２２４から取得する。そして、既知未知判定部２２６は、観測尤度L(t)の時系列データのそれぞれを、対数尤度logL(t)に変換する。即ち、既知未知判定部２２６は、各時刻ｔの観測尤度L(t)の対数を計算する。
【０２１２】
ステップＳ３２において、既知未知判定部２２６は、対数尤度logL(t)を飽和させた飽和対数尤度を求める処理を行う。具体的には、既知未知判定部２２６は、対数尤度logL(t)から、所定のオフセット（閾値）を減算して所定の値で除算した結果を、tanh関数に入力することで、対数尤度logL(t)を飽和させる。ステップＳ３１およびＳ３２の処理により、観測尤度L(t)が、−１から１までの範囲を取るパラメータに変換される。
【０２１３】
ステップＳ３３において、既知未知判定部２２６は、既知と未知の二状態で構成されるHMMを用いてビタビ判定を行うことにより、飽和対数尤度に対し既知未知判定を行う。
【０２１４】
既知状態と未知状態の二状態で構成されるHMMは、次式（４）で表される。
【数４】
2012008659.tif 000006
即ち、既知状態と未知状態の初期確率πはともに同確率（0.5）である。また、ユーザの移動履歴を考えた場合、既知状態と未知状態が頻繁に入れ替わることは考えにくく、既知の経路を移動している場合も未知の経路を移動している場合も切り替わった後はある程度連続して続くと考えられる。従って、遷移確率Ａは、１より非常に小さいな所定の値をεとして、既知状態と未知状態のそれぞれで自己遷移する確率が大きくなるように設定される。観測確率としては、既知状態が１、未知状態が−１を中心に分布し、分散値として１が設定されている。
【０２１５】
図２７と図２８は、ある２つの観測尤度L(t)の時系列データに対して、図２７の既知未知判定処理を行った結果を示している。
【０２１６】
図２７および図２８において、上段のグラフは、観測尤度L(t)の時系列データを対数尤度logL(t)に変換した結果を示し、中段のグラフは、対数尤度logL(t)を飽和させた飽和対数尤度を示し、下段のグラフは、既知未知判定結果を示している。既知未知判定結果は、”−１”が未知を表し、”１”が既知を表す。
【０２１７】
図２７および図２８を参照すると、仮に、対数尤度logL(t)を単純に所定の閾値と比較するようにした場合には、頻繁に既知と未知が入れ替わることがある。しかしながら、上述したように、ユーザの移動行動は通常ある意図をもってなされるため、既知状態と未知状態が頻繁に入れ替わることは考えにくい。
【０２１８】
そこで、既知状態と未知状態のそれぞれで自己遷移する確率が大きくなるように設定した二状態の隠れマルコフモデルにより判定することで、下段の既知未知判定結果が示すように、適切なタイミングで既知未知が切り替わるようにすることができる。飽和対数尤度の計算結果を見ると、図２７では、短時間だけ既知状態が発生したり、図２８では、チャタリングが発生したりしているが、既知未知判定結果は、安定した既知または未知の状態が得られている。従って、図２７の既知未知判定処理により、観測尤度L(t)の時系列データに対して、安定した既知未知の判定ができている。
【０２１９】
なお、既知未知の判定の方法は、観測尤度L(t)の時系列データに基づいて、既知または未知の２値に弁別することができればよいので、上記の方法に限られない。例えば、観測尤度L(t)の時系列データに、ローパスフィルタを施し、既知または未知に２値化するような方法でもよい。
【０２２０】
また、上述のビタビ推定やローパスフィルタを使った既知未知判定では、状態ノード推定部２２３において未知と推定された状態ノードが既知と判定されることが稀にある。このような場合は、次の（１）か（２）のいずれかの方法を採用することができる。（１）状態ノードの推定結果（即ち、未知）を、上述の既知未知判定の判定結果よりも優先する。（２）未知の推定結果の状態ノードが出現する前または後の状態ノードの推定結果（即ち、既知）で置き換える。ここで、置き換える元となる状態ノードは、未知の推定結果の状態ノードが出現する前または後のいずれか一方に予め決定しておいてもよいし、前または後ろの状態ノードのうち、観測尤度の大きい方の状態ノードとするようにしてもよい。（１）では、推定結果を優先し、判定結果を未知に修正することになり、（２）では、判定結果を優先し、推定結果を既知に修正することになる。
【０２２１】
次に、新規モデル生成部２０２の詳細について説明する。
【０２２２】
[新規モデル生成部２０２の詳細構成例]
図２９は、新規モデル生成部２０２の詳細な構成例を示すブロック図である。
【０２２３】
新規モデル生成部２０２は、新規モデル初期化部２４１、新規モデル制約部２４２、新規モデル学習部２４３、ノード系列判定部２４４、パラメータ再計算部２４５、および新規モデル整理部２４６により構成される。
【０２２４】
新規モデル生成部２０２には、既知未知判定部２０１から、未知の移動履歴データが供給される。また、未知の移動履歴データが既知の移動履歴データと接続されている場合には、未知の移動履歴データの前後の既存モデルの状態ノードも供給される。既知未知判定部２０１から供給される未知の移動履歴データと前後の既存モデルの状態ノードは、新規モデル生成部２０２の各部が必要に応じて取得することができる。
【０２２５】
新規モデル初期化部２４１は、供給された未知の移動履歴データのサンプル数と同数の状態ノード数のHMMを、新規モデルとして宣言する（メモリ確保して生成する）。
【０２２６】
新規モデル制約部２４２は、新規モデル初期化部２４１で宣言した新規モデルに、left-to-rightの制約を設定する。これは、一回の移動行動は、強い一方向性の制約があること、また、仮に移動方向に一方向性がなくても、時間は常に一方向性があることによる。
【０２２７】
新規モデル学習部２４３は、未知の移動履歴データを用いて新規モデルを学習する。即ち、新規モデル学習部２４３は、既知未知判定部２０１から供給された未知の移動履歴データを用いて、新規モデルを表すleft-to-rightの制約が与えられたHMMのパラメータを求める。
【０２２８】
ノード系列判定部２４４は、新規モデル学習部２４３の学習により得られた新規モデルを用いて、未知の移動履歴データの３次元データそれぞれを、新規モデルの状態ノードsiに変換したノード系列データを生成し、パラメータ再計算部２４５に供給する。具体的には、ノード系列判定部２４４は、新規モデル学習部２４３から供給されたパラメータに基づく新規モデルから、入力されたユーザの時刻、緯度、および経度に対応するユーザの現在の状態ノードsiを認識する処理を、未知の移動履歴データの最初のステップから最後のステップまで繰り返す。
【０２２９】
パラメータ再計算部２４５は、ノード系列判定部２４４から供給されるノード系列データを基に、移動履歴データのHMMのパラメータに対応するノード系列データのパラメータを計算する。即ち、パラメータ再計算部２４５は、未知の移動履歴データのHMMの初期確率πi、状態遷移確率aij、および観測確率（中心値μiと分散値σi２）に対応する、ノード系列データの初期確率<πi>、状態遷移確率<aij>、および観測確率（中心値<μi>と分散値<σi２>）を計算する。以下において、”<  >”で囲まれた初期確率πi、状態遷移確率aij、および観測確率（中心値μiと分散値σi２）は、ノード系列データで再計算されたパラメータを表す。
【０２３０】
また、パラメータ再計算部２４５は、各状態遷移の遷移頻度<trans_cntｉｊ>と各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>を計算しておく。
【０２３１】
ここで、遷移頻度<trans_cntｉｊ>は、状態ノードsiから状態ノードsjに遷移する頻度（カウント値）を表し、ｉ＝１乃至N，ｊ＝１乃至N（Nは、時系列データの最後のノード番号（＝ノード数））である。状態頻度<cnt_alli>は、全てのノード系列データにおける状態ノードsiの総数であり、状態初期頻度<cnt_starti>は、ノード系列データの先頭が状態ノードsiである個数である。
【０２３２】
一般に、更新後の初期確率πi_update、状態遷移確率aij_update、および観測確率の中心値μi_updateと分散値σi_update２は、次のように表すことができる。
【数５】
2012008659.tif 000007
πi_current、aij_current、並びにμi_current及びσi_current２は、既存のノード系列データの状態ノードｓiの初期確率、状態遷移確率、並びに観測確率の中心値および分散値である。また、πi_new、aij_new、並びにμi_new及びσi_new２は、追加分のノード系列データの状態ノードｓiの初期確率、状態遷移確率、並びに観測確率の中心値および分散値である。ｎi_currentとｎi_newは、ノード系列データの状態ノードｓiの既存部分のノード数と追加部分のノード数である。
【０２３３】
従って、パラメータ再計算部２４５が各状態遷移の遷移頻度<trans_cntｉｊ>と各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>を計算して記憶しておくことで、次の更新の計算が容易になる。
【０２３４】
なお、頻度を計算して記憶する代わりに、頻度を確率的にカウントして、非整数の成分を扱ってもよい。さらに、頻度の代わりに、頻度×平均値、頻度×分散値のようなパラメータを記憶してもよい。
【０２３５】
パラメータ再計算部２４５は、状態初期頻度<cnt_starti>とともに、ノード系列判定部２４４から供給されるノード系列データの総数であるノード系列データ数<seq_cnt>も計算しておく。
【０２３６】
新規モデル整理部２４６は、新規モデル初期化部２４１が宣言した新規モデルとしてのHMMの各状態ノードsiのなかで、使用されない状態ノードを消去することで、新規モデルを整理する。具体的には、新規モデル整理部２４６は、パラメータ再計算部２４５で計算された状態頻度<cnt_alli>が０の状態ノードsiを消去する。新規モデル整理部２４６により整理された後の新規モデル（のパラメータ）が、新規モデル結合部２０３に出力される。また、未知の移動履歴データの前後の既存モデルの状態ノードも既知未知判定部２０１から供給されていた場合には、それも、併せて新規モデル結合部２０３に出力される。
【０２３７】
[新規モデル学習部２４３の学習処理]
次に、図３０乃至図３３を参照して、新規モデル学習部２４３の学習処理について説明する。
【０２３８】
初めに、図３０および図３１を参照して、通常のHMMによる学習モデルと、新規モデル学習部２４３が行う学習モデルの違いについて説明する。
【０２３９】
ユーザの移動履歴をHMMのように離散状態でモデル化する場合、通常、移動経路を一定の時間間隔でサンプルしたデータをモデル化する。移動履歴のデータを取得する際に、省電力の要請などの理由からサンプリング間隔を細かくできず、十分なサンプルが得られない場合、サンプル数とノード数があまり変わらないか、ノード数に比べてサンプル数が少ない状況が起こり得る。このような状況で、観測されるデータが所定の位置の周囲に正規分布する状態ノードを仮定する場合、一つのサンプルを一つのノードでモデル化することがある。この場合、ノードの分散値は非常に小さい値（あるいは０）に収束し、サンプルの近傍はモデル化されないことになる。従って、サンプリングされたサンプル間の経路はモデル化されない。
【０２４０】
図３０は、移動履歴を通常のHMMによりモデル化したときの概念図を示している。図３０の直線（線分）はユーザの実際の移動経路を示し、バツ印（×）が移動履歴データとして取得されたサンプル、サンプルを囲む丸（○）がノードを示している。
【０２４１】
図３０に示すように、近くにサンプルが得られなかった場所（領域）はモデル化されないので、例えば、電車のような速い移動速度で移動しているような場合、サンプルとサンプルの間の経路はモデル化されない。一方、徒歩のような遅い移動速度で移動している場合、一つのノードで複数のサンプルをモデル化する場合がある。このような場合には、移動履歴をノードで適切に表現できていないことがある。
【０２４２】
また、同一の移動経路を二回通過した場合に、ノードの分散値が非常に小さい値（あるいは０）に収束していると、二回目の通過した位置は、一回目の通過のときに表現されたノードでモデル化されず、異なるノードが割り当てられることがある。
【０２４３】
このような問題を回避するためには、ノードの分散値に下限を設定し、サンプルから所定の領域の経路を必ずモデル化するようにさせることが考えられる。
【０２４４】
しかし、分散値を大きくすると、異なる経路を同一の経路とみなす可能性も高くなる。例えば、平行に進む異なる経路を同一の経路とみなすおそれが生じる。さらに、分散値を大きくすると、移動速度の遅いときの移動履歴データを高い精度で再現することが難しくなる。逆に、分散値が小さくしすぎると、移動速度が速いときの移動履歴データを同一の経路と認識できなくなる。実際の移動履歴データのサンプルは、移動速度の違いで様々な距離感覚となるため、全てに適したノードの分散値の下限を決定するのは困難である。
【０２４５】
そこで、新規モデル学習部２４３は、図３１に示すように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようなモデルを仮定することで、サンプルとサンプルの間の経路をモデル化する。新規モデル全体では、新規モデル学習部２４３は、各ノードが二つの連続するサンプルを順次つないだモデル化を行う。これにより、鎖で繋がれるように、経路全体の領域がもれなく新規モデルで表現することができる。
【０２４６】
また、サンプルとサンプルの間隔が長くても、二つのサンプル間を含むようにモデル化しているので、ノードの分散値は小さく設定することができる。逆に、サンプルとサンプルの間隔が短い場合も同様にモデル化できるため、スケールフリーなモデル化を実現することができる。
【０２４７】
なお、後述するように、新規モデル学習部２４３は、一つの状態ノードが連続する３つ以上のサンプルを反映するようにモデル化することも可能であり、一つの状態ノードがいくつのサンプルを反映するようにモデル化するかは、適宜、決定することができる。
【０２４８】
図３２は、新規モデル学習部２４３の学習モデルをグラフィカルモデルで表したものである。
【０２４９】
図３２Aの学習モデルは、現在のある状態ノードが、現在のデータと、一つ前（一つ後ろ）の２つのサンプルを観測するモデルである。図３２Ａでは、一つの状態ノードからの矢印が、下と右下にあるが、下と左下に向かう矢印のあるモデルでもよい。
【０２５０】
なお、本実施の形態では、図３１に示したように、一つの状態ノードが二つの連続するサンプルを表現するモデルを採用するが、一つの状態ノードが３以上の連続するサンプルを表現するモデルを採用することもできる。図３２Ｂのモデルは、一つの状態ノードが３つの連続するサンプルを表現するモデルのグラフィカルモデルである。
【０２５１】
[新規モデル学習部２４３の新規モデル学習処理]
次に、図３３のフローチャートを参照して、新規モデル学習部２４３の新規モデル学習処理について説明する。
【０２５２】
初めに、ステップＳ５１において、新規モデル学習部２４３は、未知の移動履歴データに対する各状態の尤度を計算する。具体的には、新規モデル学習部２４３は、ユーザ活動モデルを表すHMMの状態ｓiへの遷移時に、移動履歴データの２つのサンプル、時刻tの位置のデータｘtと時刻t＋１の位置のデータｘt＋１が出力されると仮定した観測尤度Ｐ（ｘt，ｘt＋１｜ｓi）を、次式（５）により計算する。
【０２５３】
【数６】
2012008659.tif 000008
なお、時刻ｔは、時系列データの測定時刻ではなく、時系列データの順番（ステップ数）を表し、１からＴ（時系列データのサンプル数）までの値をとる。また、式（５）のｘt（１）、ｘt（２）、ｘt（３）は、それぞれ移動履歴データｘtの時刻、緯度、経度を表すものとする。さらに、式（５）のN()は、単一正規分布を表し、μsi（１）、σsi（１）２は、時刻の単一正規分布の中心値および分散値を表す。また、μsi（２）、σsi（２）２は、緯度の単一正規分布の中心値および分散値を表し、μsi（３）、σsi（３）２は、経度の単一正規分布の中心値および分散値を表すものとする。
【０２５４】
観測尤度Ｐ（ｘt，ｘt＋１｜ｓi）は、元の時系列データと、一つずれた時系列データの同時分布なので、それぞれの観測系列の分布の積となっている。
【０２５５】
なお、一つの状態ノードがW個以上の連続するサンプルを表現するモデルの観測尤度Ｐ（ｘt，・・・，ｘt＋W｜ｓi）は、次式（６）で表すことができる。勿論、時系列データの次元数Dも３より大きい値に一般化することも可能である。
【数７】
2012008659.tif 000009
【０２５６】
ステップＳ５１では、全ての状態ｓiと３次元データｘtの組み合わせについて、式（５）による観測尤度Ｐ（ｘt，ｘt＋１｜ｓi）が、新規モデル学習部２４３によって計算される。
【０２５７】
次に、ステップＳ５２において、新規モデル学習部２４３は、各時刻ｔにおける全ての状態ｓiのフォワード尤度αt（ｓi）を計算する。即ち、新規モデル学習部２４３は、次の式（７）および式（８）により、時刻ｔにおける状態ｓiのフォワード尤度αt（ｓi）を時刻１から最終の時刻Ｔまで順番に計算する。
【０２５８】
【数８】
2012008659.tif 000010
なお、式（７）のπsiは、状態ｓiの初期確率を表す。また、式（８）のajiは、状態ｓjから状態ｓiへの状態遷移確率を表す。なお、初期確率πsiおよび状態遷移確率ajiの初期値は、例えば、外部から与えられる。
【０２５９】
ステップＳ５３において、新規モデル学習部２４３は、各時刻ｔにおける全ての状態ｓiのバックワード尤度βt（ｓi）を計算する。即ち、新規モデル学習部２４３は、次の式（９）および式（１０）により、時刻ｔにおける状態ｓiのバックワード尤度βt（ｓi）を、最終の時刻Ｔから時刻１まで逆順に計算する。
【０２６０】
【数９】
2012008659.tif 000011
式（９）では、時刻Ｔに各状態ｓiである確率が全て等しいものとされている。
【０２６１】
このように、ステップＳ５１乃至Ｓ５３の処理により、移動履歴データに対する隠れマルコフモデルの各種の尤度が計算される。
【０２６２】
ステップＳ５４において、新規モデル学習部２４３は、初期確率、状態遷移確率を更新する。即ち、新規モデル学習部２４３は、各状態ｓiの初期確率πsi、各状態間の状態遷移確率aijを、次の式（１１）および式（１２）で求まる初期確率πsi’、状態遷移確率aij’にそれぞれ更新する。
【０２６３】
【数１０】
2012008659.tif 000012
式（１１）および式（１２）は、Baum-Welchの最尤推定法で一般的に用いられる式に、観測尤度Ｐ（ｘt，ｘt＋１｜ｓi）を適用したものである。
【０２６４】
ステップＳ５５において、新規モデル学習部２４３は、観測確率を更新する。即ち、新規モデル学習部２４３は、各状態ｓiの観測確率（確率分布）の中心値μsi（ｄ）、分散値σsi（ｄ）2を、次の式（１３）および式（１４）で求まる中心値μsi（ｄ）’、分散値σsi（ｄ）’2にそれぞれ更新する。
【０２６５】
【数１１】
2012008659.tif 000013
式（１３）および式（１４）のｄは、データの次元Dに対応し、１，２、または３のいずれかとなる。
【０２６６】
一つの状態ノードがW個以上の連続するサンプルを表現するモデルで、次元数がDである場合の観測確率の中心値μsi（ｄ）’および分散値σsi（ｄ）’2は、次の式（１５）および式（１６）で求めることができる。
【数１２】
2012008659.tif 000014
【０２６７】
式（１３）および式（１５）の中心値μsi（ｄ）’、並びに、式（１４）および式（１６）の分散値σsi（ｄ）’2は、尤度を最小化する式を解くことで、容易に算出することができる。
【０２６８】
ステップＳ５６において、新規モデル学習部２４３は、パラメータの更新を終了するか否かを判定する。例えば、各尤度の増分が所定の値以下となり、パラメータの更新の収束条件を満たした場合、新規モデル学習部２４３は、パラメータの更新を終了すると判定する。あるいは、ステップＳ５１乃至Ｓ５５の処理を規定の回数繰り返し実行した場合、パラメータの更新を終了すると判定するとしてもよい。
【０２６９】
ステップＳ５６で、パラメータの更新を終了しないと判定された場合、処理はステップＳ５１に戻る。
【０２７０】
ステップＳ５１では、新規モデル学習部２４３は、更新されたパラメータに基づいて、各状態の尤度が計算される。即ち、ステップＳ５４およびＳ５５の処理で更新された、各状態ｓiの初期確率πsi’、中心値μsi（ｄ）’および分散値σsi（ｄ）’2、並びに、各状態間の状態遷移確率aij’を示すデータに基づいて、各状態の尤度が計算される。
【０２７１】
その後、同様にステップＳ５２乃至Ｓ５５の処理が実行される。これにより、状態ｓiの系列の各種の尤度、すなわち、観測尤度Ｐ（ｘt，ｘt＋１｜ｓi）、フォワード尤度αt（ｓi）、バックワード尤度βt（ｓi）が次第に増加し、最終的に最大になるように、HMMのパラメータの更新が行われる。そして、ステップＳ５６において、再度、パラメータの更新を終了するか否かが判定される。
【０２７２】
ステップＳ５６で、パラメータの更新を終了すると判定された場合、処理はステップＳ５７に進む。
【０２７３】
ステップＳ５７において、新規モデル学習部２４３は、最終的なパラメータをノード系列判定部２４４に出力する。即ち、新規モデル学習部２４３は、最終的に求められた、各状態ｓiの初期確率πsi’、中心値μsi（ｄ）’および分散値σsi（ｄ）’2、並びに、各状態間の状態遷移確率aij’を示すデータをノード系列判定部２４４に出力して、処理を終了する。
【０２７４】
[パラメータ再計算部２４５のパラメータ再計算処理]
次に、図３４のフローチャートを参照して、パラメータ再計算部２４５のパラメータ再計算処理について説明する。
【０２７５】
初めに、ステップＳ７１において、パラメータ再計算部２４５は、ノード系列判定部２４４から供給される全てのノード系列データを対象として、各状態遷移の遷移頻度<trans_cntｉｊ>（ｉ＝１乃至N，ｊ＝１乃至N，Nは、時系列データの最後のノード番号（＝ノード数））をカウントする。
【０２７６】
ステップＳ７２において、パラメータ再計算部２４５は、ノード系列判定部２４４から供給される全てのノード系列データを対象として、各状態ノードsiの状態頻度<cnt_alli>、状態初期頻度<cnt_starti>、およびノード系列データ数<seq_cnt>をカウントする。
【０２７７】
ステップＳ７３において、パラメータ再計算部２４５は、ノード系列データの初期確率<πi>’と状態遷移確率<aij>’を計算（更新）する。ノード系列データの初期確率<πi>’および状態遷移確率<aij>’は、次の式（１７）および式（１８）により計算することができる。
【数１３】
2012008659.tif 000015
【０２７８】
ステップＳ７４において、パラメータ再計算部２４５は、ノード系列データの観測確率、即ち、各状態ノードsiの中心値<μj>’と分散値<σj２>’を計算（更新）する。各状態ノードsiの中心値<μj>’と分散値<σj２>’は、次の式（１９）および式（２０）により計算することができる。
【０２７９】
【数１４】
2012008659.tif 000016
式（１９）及び式（２０）において、ｘt_kは、移動履歴データの３次元データｘtのうち、状態ノードsiに対応する３次元データを表す。従って、ｘt_kの個数は、状態ノードsiの状態頻度<cnt_alli>と等しくなる。
【０２８０】
なお、一つの状態ノードがW個以上の連続するサンプルを表現するモデルでは、各状態ノードsiの中心値<μj>’と分散値<σj２>’は、次の式（２１）および式（２２）により計算することができる。
【数１５】
2012008659.tif 000017
【０２８１】
以上で、パラメータ再計算部２４５によるパラメータ再計算処理は終了する。
【０２８２】
なお、図３２のグラフィカルモデルを用いていることが、図２９の新規モデル学習部２４３（式（５），式（６）、式（１３）乃至式（１６））と、パラメータ再計算部２４５（式（１９）乃至式（２２））に反映されている。従って、例えば、処理を簡略化する要請があるならば、図２９のパラメータ再計算部２４５のみに、図３２のグラフィカルモデルを反映しただけの実施例でもよい。この場合、図２９の新規モデル学習部２４３には、通常のバウムウエルチアルゴリズムによる学習を採用することができる。また、さらに簡略化するならば、通常のバウムウエルチアルゴリズムの代わりに、取得した移動履歴データに対して、前から順に番号を割り振って、これを状態ノードの番号とするような処理に変更してもよい。この場合、図７の移動属性識別付与部７４で与えられた移動属性を見て、現在の移動履歴の３次元データの移動属性が滞在状態でなければ、一つ前の３次元データに割り振られた番号を１大きくした番号が、状態ノードの番号として割り振られる。一方、現在の移動履歴の３次元データの移動属性が滞在状態であれば、一つ前の３次元データに割り振られた番号と同じ番号が状態ノードの番号として割り振られる。
【０２８３】
[新規モデル生成部２０２の新規モデル生成処理]
図３５は、新規モデル生成部２０２が行う新規モデル生成処理全体のフローチャートである。
【０２８４】
初めに、ステップＳ９１において、新規モデル初期化部２４１は、既知未知判定部２０１から供給された未知の移動履歴データを取得し、それに対応する新規モデルを生成する。即ち、新規モデル初期化部２４１は、取得した未知の移動履歴データのサンプル数と同数の状態ノード数のHMMを生成する。
【０２８５】
ステップＳ９２において、新規モデル制約部２４２は、新規モデル初期化部２４１で生成したHMMにleft-to-rightの制約を設定する。
【０２８６】
ステップＳ９３において、新規モデル学習部２４３は、未知の移動履歴データを用いて新規モデルを学習する。即ち、ステップＳ９３では、新規モデルは、図３１に示したように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようなモデルとして、図３３を参照して説明した新規モデル学習処理が実行される。
【０２８７】
ステップＳ９４において、ノード系列判定部２４４は、ステップＳ９３の新規モデル学習処理により得られた新規モデルを用いて、未知の移動履歴データに対応するノード系列データを生成し、パラメータ再計算部２４５に供給する。
【０２８８】
ステップＳ９５において、パラメータ再計算部２４５は、ノード系列判定部２４４から供給されるノード系列データを基に、移動履歴データのHMMのパラメータに対応するノード系列データのパラメータを計算する。より具体的には、パラメータ再計算部２４５は、ノード系列データの初期確率<πi>’、状態遷移確率<aij>’、および各状態ノードsiの中心値<μj>’と分散値<σj２>’を計算する。また、パラメータ再計算部２４５は、各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>も計算する。
【０２８９】
ステップＳ９６において、新規モデル整理部２４６は、生成した新規モデルとしてのHMMの各状態ノードsiのなかで、使用されない状態ノードを消去することで、新規モデルを整理する。そして、新規モデル整理部２４６は、整理後の新規モデルのパラメータと、未知の移動履歴データの前後の既存モデルの状態ノードも既知未知判定部２０１から供給されていた場合には、それも、新規モデル結合部２０３に出力して、処理を終了する。
【０２９０】
[新規モデル結合部２０３のトポロジー更新モデル生成処理]
次に、先の学習により得られている既存モデルと、未知の移動履歴データにより生成された新規モデルを結合し、トポロジー更新モデルを生成する新規モデル結合部２０３のトポロジー更新モデル生成処理について説明する。
【０２９１】
まず、説明の前提として、以下の変数を定義する。
【０２９２】
既存モデル          ：xhmm
新規モデル          ：yhmm
トポロジー更新モデル：zhmm
【０２９３】
既存モデルxhmm、新規モデルyhmm、トポロジー更新モデルzhmmそれぞれは、次の変数を有する。なお、以下のhmmは、学習モデル（HMM）に共通の表記であり、既存モデルのときはxhmmと、新規モデルのときはyhmmと、トポロジー更新モデルのときはzhmmと読み替える。
状態ノード数                          ：hmm.node
既存モデルxhmmの状態ノード数xhmm.node＝M
新規モデルyhmmの状態ノード数yhmm.node＝N
トポロジー更新モデルzhmmの状態ノード数zhmm.node＝M+N
学習対象の時系列データの次元数D      ：hmm.D
各状態ノードの初期確率πi            ：hmm.pi(i)
hmm全体の初期確率hmm.piは、hmm.node行１列のテーブル（初期確率テーブル）となる。
各状態ノードの遷移確率aij            ：hmm.a(i,j)
hmm全体の遷移確率hmm.aは、hmm.node行hmm.node列のテーブル（遷移確率テーブル）となる。
各状態ノードの確率分布の中心値μi    ：hmm.mu(i)
hmm全体の確率分布の中心値hmm.muは、hmm.node行hmm.D列のテーブル（中心値テーブル）となる。
各状態ノードの確率分布の分散値σi２  ：hmm.sigma2(i)
hmm全体の確率分布の分散値hmm.sigma2は、hmm.node行hmm.D列のテーブル（分散値テーブル）となる。
学習した時系列データの数seq_cnt    ：hmm.seq_cnt
各状態ノードの状態頻度cnt_alli      ：hmm.cnt_all(i)
hmm全体の状態頻度hmm.cnt_allは、hmm.node行１列のテーブル（状態頻度テーブル）となる。
【０２９４】
図３６のフローチャートを参照して、新規モデル結合部２０３によるトポロジー更新モデル生成処理について説明する。
【０２９５】
初めに、ステップＳ１０１において、新規モデル結合部２０３は、トポロジー更新モデルの初期確率zhmm.piを計算する。
【０２９６】
ステップＳ１０１では、まず、新規モデル結合部２０３は、既存モデルがM個、新規モデルがN個の状態ノードからなるので、図３７Aに示すように、初期確率zhmm.piとしての(M＋N)行１列の初期確率テーブルを生成する。
【０２９７】
そして、新規モデル結合部２０３は、トポロジー更新モデルの初期確率テーブルの第１行乃至第M行の第m行に（m=１，２，・・，M）は、図３７Aに示すように、既存モデルの初期確率xhmm.pi(m)に、既存モデルの時系列データ数xhmm.seq_cntを乗算した値を設定する。また、トポロジー更新モデルの初期確率テーブルの第（M＋１）行乃至第（M＋N）行の第（M+n）行（n=１，２，・・・，N）には、新規モデルの初期確率yhmm.pi(n)に、新規モデルの時系列データ数yhmm.seq_cntを乗算した値を設定する。
【０２９８】
そして、図３７Bに示されるように、トポロジー更新モデルの初期確率テーブルの各行が、初期確率テーブルの全要素の総和SUM_piで除算されることで規格化され、トポロジー更新モデルの初期確率テーブルzhmm.piの生成が終了する。
【０２９９】
次に、ステップＳ１０２において、新規モデル結合部２０３は、トポロジー更新モデルの時系列データ数zhmm.seq_cntを計算する。具体的には、新規モデル結合部２０３は、既存モデルの時系列データ数xhmm.seq_cntと、新規モデルの時系列データ数yhmm.seq_cntの和を計算し、トポロジー更新モデルの時系列データ数zhmm.seq_cntとする。
【０３００】
ステップＳ１０３において、新規モデル結合部２０３は、トポロジー更新モデルの遷移確率zhmm.aと状態頻度zhmm.cnt_allを計算する。
【０３０１】
ステップＳ１０３では、まず、新規モデル結合部２０３は、既存モデルがM個、新規モデルがN個の状態ノードからなるので、図３８に示すように、(M＋N)行(M＋N)列の遷移確率テーブルを生成する。なお、遷移確率テーブルの第１行第１列から第M行M列を左上領域、第(M＋１)行第(M＋１)列から第(M＋N)行(M＋N)列を右下領域、第１行第(M+1)列から第M行(M＋N)列を右上領域、第（M+1）行第１列から第(M＋N)行M列を左下領域という。
【０３０２】
そして、新規モデル結合部２０３は、生成した遷移確率テーブルの左上領域の各要素に、既存モデルの状態ノードsmの遷移確率xhmm.a(m,j)に、既存モデルの状態ノードsmの状態頻度xhmm.cnt_all(m)を乗算した値を設定する（j=１，・・・，M）。
【０３０３】
また、新規モデル結合部２０３は、生成した遷移確率テーブルの右下領域の各要素に、新規モデルの状態ノードsmの遷移確率yhmm.a(m,j)に、新規モデルの状態ノードsmの状態頻度yhmm.cnt_all(m)を乗算した値を設定する（j=１，・・・，M）。
【０３０４】
なお、図３８では、紙面の制約上、xhmm.a(m,j)×xhmm.cnt_all(m)、yhmm.a(m,j)×yhmm.cnt_all(m)と、同一行についてはまとめて図示している。
【０３０５】
さらに、新規モデル結合部２０３は、生成した遷移確率テーブルの右上領域の各要素については、基本的に”０”を代入する。ただし、未知の移動履歴データの前の既存モデルの状態ノードが、新規モデル生成部２０２から供給され、新規モデルが既存モデルのノード系列データの後に接続される場合、その接続先の状態ノードに対応する要素のみ、”１”が代入される。具体的には、接続先の状態ノードがsｉである場合、第ｉ行第（M+1）列の要素に、”１”が設定される。
【０３０６】
同様に、新規モデル結合部２０３は、生成した遷移確率テーブルの左下領域の各要素については、基本的に”０”を代入する。ただし、未知の移動履歴データの後の既存モデルの状態ノードが、新規モデル生成部２０２から供給され、新規モデルの後に既存モデルのノード系列データが接続される場合、その接続先の状態ノードに対応する要素のみ、”１”が代入される。具体的には、接続先の状態ノードがsｊである場合、第(M＋N)行第ｊ列の要素に、”１”が設定される。
【０３０７】
次に、新規モデル結合部２０３は、図３９に示すように、生成した遷移確率テーブルの左上領域と右下領域について、行方向の和を演算することにより、トポロジー更新モデルの状態頻度zhmm.cnt_allを計算する。図３９の状態頻度テーブルは、(M＋N)行１列のテーブルによりなる。
【０３０８】
最後に、新規モデル結合部２０３は、図４０に示すように、図３８の遷移確率テーブルの左上領域と右下領域の各行を、トポロジー更新モデルの状態頻度テーブルの各行zhmm.cnt_all(i)で除算して、規格化する。以上で、トポロジー更新モデルの遷移確率テーブルの生成が終了する。
【０３０９】
そして、処理はステップＳ１０４に進み、新規モデル結合部２０３は、トポロジー更新モデルの確率分布の中心値zhmm.muおよび分散値zhmm.sigma2を計算する。
【０３１０】
ステップＳ１０４では、既存モデルがM個、新規モデルがN個の状態ノードからなるので、トポロジー更新モデルの中心値zhmm.muに対応する中心値テーブルは、（M＋N)行D列で構成される。
【０３１１】
図４１に示すように、(M＋N)行D列の中心値テーブルの第１行から第M行の各行には、既存モデルの中心値xhmm.mu(i,1)，xhmm.mu(i,2)，xhmm.mu(i,3)が代入される（i=１，・・・，M）。また、(M＋N)行D列の中心値テーブルの第（M+1）行から第（M+N）行の各行には、新規モデルの中心値yhmm.mu(i,1)，yhmm.mu(i,2)，yhmm.mu(i,3)が代入される（i=１，・・・，N）。ここで、xhmm.mu(i,1)及びyhmm.mu(i,1)は、移動履歴データの時刻の中心値であり、xhmm.mu(i,2)及びyhmm.mu(i,2)は、移動履歴データの緯度の中心値であり、xhmm.mu(i,3)及びyhmm.mu(i,3)は、移動履歴データの経度の中心値である。
【０３１２】
同様に、トポロジー更新モデルの確率分布の分散値zhmm.sigma2に対応する分散値テーブルも、(M＋N)行D列で構成される。
【０３１３】
図４２に示すように、(M＋N)行D列の分散値テーブルの第１行から第M行の各行には、既存モデルの分散値xhmm.sigma2(i,1)，xhmm.sigma2(i,2)，xhmm.sigma2(i,3)が代入される（i=１，・・・，M）。また、(M＋N)行D列の分散値テーブルの第（M+1）行から第（M+N）行の各行には、新規モデルの分散値yhmm.sigma2(i,1)，yhmm.sigma2(i,2)，yhmm.sigma2(i,3)が代入される（i=１，・・・，N）。ここで、xhmm.sigma2(i,1)及びyhmm.sigma2(i,1)は、移動履歴データの時刻の分散値であり、xhmm.sigma2(i,2)及びyhmm.sigma2(i,2)は、移動履歴データの緯度の分散値であり、xhmm.sigma2(i,3)及びyhmm.sigma2(i,3)は、移動履歴データの経度の分散値である。
【０３１４】
そして、処理はステップＳ１０５に進み、新規モデル結合部２０３は、トポロジー更新モデルのパラメータを更新モデル整理部２０５に出力する。即ち、トポロジー更新モデルの初期確率zhmm.pi、時系列データ数zhmm.seq_cnt、遷移確率zhmm.a、状態頻度zhmm.cnt_all、並びに、確率分布の中心値zhmm.muおよび分散値zhmm.sigma2が更新モデル整理部２０５に出力される。以上で、トポロジー更新モデル生成処理は終了する。
【０３１５】
[パラメータ更新部２０４のパラメータ更新処理]
次に、パラメータ更新部２０４によるパラメータ更新処理について説明する。
【０３１６】
図４３は、パラメータ更新部２０４が行うパラメータ更新処理全体のフローチャートである。
【０３１７】
初めに、ステップＳ１２１において、パラメータ更新部２０４は、既知未知判定部２０１から供給された、既知の移動履歴データと、それに対応するノード系列データを取得する。以下では、説明を簡単にするため、１個の既知の移動履歴データと、それに対応するノード系列データが取得されたとして説明する。
【０３１８】
ステップＳ１２２において、パラメータ更新部２０４は、既存モデルの初期確率xhmm.piを更新する。
【０３１９】
ステップＳ１２２では、まず、初期確率xhmm.piとしてのM行１列の初期確率テーブルの、取得された状態ノード系列の先頭ノードに対応する初期確率xhmm.pi(i)に１が加算される。図４４Aでは、状態ノード系列の先頭ノードが状態ノードs１８である例として、xhmm.pi(18)に１が加算されている。
【０３２０】
そして、確率の条件を満たすため、図４４Bに示すように、初期確率テーブルの各行が、全要素の総和SUM_piで除算されることで規格化され、既存モデルの初期確率xhmm.piの更新が終了する。
【０３２１】
次に、ステップＳ１２３において、パラメータ更新部２０４は、既存モデルの時系列データ数xhmm.seq_cntを更新する。時系列データ数は一つ増加するだけであるので、現在のxhmm.seq_cntに１を加算したものが更新後の既存モデルの時系列データ数xhmm.seq_cntとされる。
【０３２２】
ステップＳ１２４において、パラメータ更新部２０４は、既存モデルの遷移確率xhmm.aと状態頻度xhmm.cnt_allを更新する。
【０３２３】
ステップＳ１２４では、まず、取得された状態ノード系列で発生している状態遷移に対応する遷移確率テーブルの各要素に、１が加算される。例えば、図４５の例では、状態ノードs１８から状態ノードs２への遷移と、状態ノードsMから状態ノードs２への遷移が、少なくとも発生し、xhmm.a(18,2)×xhmm.cnt_all(18)とxhmm.a(M,2)×xhmm.cnt_all(M)のそれぞれに、１が加算されている。
【０３２４】
また、取得された状態ノード系列の最後尾の状態ノードについては、自己遷移に対応する遷移確率テーブルの要素に、１が加算される。例えば、図４５では、状態ノード系列の最後尾の状態ノードがs２である例として、xhmm.a(2,2)×xhmm.cnt_all(2)に、１が加算されている。
【０３２５】
次に、パラメータ更新部２０４は、図４６に示すように、１を加算後の遷移確率テーブルに対し、行方向の和を演算することで、既存モデルの状態頻度xhmm.cnt_allを計算（更新）する。
【０３２６】
最後に、パラメータ更新部２０４は、図４７に示すように、１を加算後の遷移確率テーブルの各行を、更新後の既存モデルの状態頻度xhmm.cnt_all(i)で除算して、規格化する。以上の計算により、既存モデルの遷移確率テーブルが更新される。
【０３２７】
そして、処理はステップＳ１２５に進み、パラメータ更新部２０４は、既存モデルの確率分布の中心値xhmm.muおよび分散値xhmm.sigma2を更新する。
【０３２８】
一般に、既存モデルにおいて状態ノードsiがM個出現し、その平均値がμsiである場合において、M＋１番目の状態ノードsiと認識される新しいサンプルxM＋１が増えたときの更新前の平均値μsi（M）と更新後のμsi（M＋１）との間には、次の関係がある。
【０３２９】
【数１６】
2012008659.tif 000018
式（２３）および式（２４）において、右肩の括弧付きの文字は状態ノードsiの出現回数を表す。
【０３３０】
そこで、パラメータ更新部２０４は、図４８に示すように、M行D列の中心値テーブルの各行の要素に、上述したステップＳ１２４で状態頻度xhmm.cnt_all(i)を更新する前の、１つ前の状態頻度xhmmOLD.cnt_all(i)を乗算する（i=１，・・・，M）。従って、１つ前の状態頻度xhmmOLD.cnt_all(i)は、ステップＳ１２４の処理を行う前に、所定の場所に格納しておく必要がある。
【０３３１】
次に、パラメータ更新部２０４は、新しいサンプルxM＋１に対応する状態ノードに対応する中心値テーブルの行に、新しいサンプルxM＋１としての既知の移動履歴データ（３次元データのそれぞれ）を加算する。
【０３３２】
さらに、パラメータ更新部２０４は、M行D列の中心値テーブルの各行の要素を、上述したステップＳ１２４で更新した状態頻度xhmm.cnt_all(i)で除算する。以上で、既存モデルの確率分布の中心値xhmm.muの更新が終了する。
【０３３３】
一方、既存モデルにおいて状態ノードsiがM個出現し、その平均値がμsi、分散値がσsi２である場合において、M＋１番目の状態ノードsiと認識される新しいサンプルxM＋１が増えたときの更新前の平均値σsi２（M）と更新後のσsi２（M＋１）との間には、次の関係がある。
【０３３４】
【数１７】
2012008659.tif 000019
式（２５）および式（２６）において、右肩の括弧付きの文字は状態ノードsiの出現回数を表す。
【０３３５】
そこで、パラメータ更新部２０４は、M行D列の分散値テーブルの各行の要素に、既存モデルの確率分布の中心値xhmm.muを更新する前の、１つ前の中心値xhmm OLD.muの二乗を加算する（i=１，・・・，M）。従って、１つ前の中心値xhmm OLD.muも、上述の更新を行う前に、所定の場所に格納しておく必要がある。
【０３３６】
次に、パラメータ更新部２０４は、１つ前の中心値xhmm OLD.muの二乗加算後のM行D列の分散値テーブルの各行の要素に、１つ前の状態頻度xhmmOLD.cnt_all(i)を乗算する。
【０３３７】
図４９は、状態頻度xhmmOLD.cnt_all(i)を乗算後の分散値テーブルを示している。
【０３３８】
さらに、パラメータ更新部２０４は、新しいサンプルxM＋１に対応する状態ノードに対応する中心値テーブルの行に、新しいサンプルxM＋１としての既知の移動履歴データ（３次元データのそれぞれ）の二乗を加算する。
【０３３９】
最後に、パラメータ更新部２０４は、M行D列の中心値テーブルの各行の要素を、上述したステップＳ１２４で更新した状態頻度xhmm.cnt_all(i)で除算し、かつ、更新後の中心値xhmm.mu(i)の二乗を減算する。以上で、既存モデルの確率分布の分散値xhmm.sigma2の更新が終了する。
【０３４０】
そして、処理はステップＳ１２６に進み、パラメータ更新部２０４は、更新された既存モデルのパラメータを新規モデル結合部２０３と更新モデル整理部２０５に出力する。即ち、更新された既存モデルの初期確率xhmm.pi、時系列データ数xhmm.seq_cnt、遷移確率xhmm.a、状態頻度xhmm.cnt_all、並びに、確率分布の中心値xhmm.muおよび分散値xhmm.sigma2が出力される。以上で、パラメータ更新処理は終了する。
【０３４１】
[学習メインプロセス部２３全体の処理]
次に、図５０のフローチャートを参照して、学習メインプロセス部２３全体の学習メインプロセス処理について説明する。
【０３４２】
初めに、ステップＳ１４１において、学習メインプロセス部２３は、学習プリプロセス部２２（図１）から供給される移動履歴データと、ユーザ別モデルパラメータ記憶部１２（図１）から供給される、既存モデルのパラメータを取得する。移動履歴データは、既知未知判定部２０１が取得し、既存モデルのパラメータは、既知未知判定部２０１、新規モデル結合部２０３、およびパラメータ更新部２０４が取得する。
【０３４３】
ステップＳ１４２において、既知未知判定部２０１は、供給された移動履歴データが既知の経路の移動履歴データであるか否か判定する既知未知判定処理を行う。
【０３４４】
図２０乃至図２８を参照して説明したように、既知未知判定処理では、既存モデルの状態ノードに未知状態ノードを追加した未知状態追加モデルでビタビ推定を行い、既知未知の二状態モデルによるビタビ判定を行うことで、既知または未知の判定が行われる。
【０３４５】
既知未知判定処理において、供給された移動履歴データが既知であると判定された場合、供給された移動履歴データと、それに対応する状態ノードの時系列データであるノード系列データが、パラメータ更新部２０４に供給される。一方、既知未知判定処理において、供給された移動履歴データが未知であると判定された場合、供給された移動履歴データは新規モデル生成部２０２に供給される。また、未知の移動履歴データが既知の状態ノード（経路）と接続されている場合には、接続先の状態ノードも新規モデル生成部２０２に供給される。
【０３４６】
ステップＳ１４２で既知と判定された場合、処理はステップＳ１４３に進み、パラメータ更新部２０４は、既知の移動履歴データと、それに対応するノード系列データに基づいて、既存モデルのパラメータを更新するパラメータ更新処理を行う。即ち、図４３乃至図４９を参照して説明した処理が行われる。
【０３４７】
一方、ステップＳ１４２で未知と判定された場合、処理はステップＳ１４４に進み、新規モデル生成部２０２は、未知の移動履歴データに対応する新規モデルを生成する新規モデル生成処理を行う。換言すれば、新規モデル生成部２０２は、未知の移動履歴データを表現する新規モデルのパラメータを求める。新規モデル生成処理は、即ち、図２９乃至図３５を参照して説明した処理である。
【０３４８】
ステップＳ１４５において、新規モデル結合部２０３は、既存モデルと新規モデルとを結合し、学習済みの既存モデルに、未知の移動履歴データを取り込んで成長させたトポロジー更新モデルを生成するトポロジー更新処理を行う。即ち、新規モデル結合部２０３は、図３６乃至図４２を参照して説明した処理を行う。
【０３４９】
ステップＳ１４３またはＳ１４５の処理後、ステップＳ１４６において、更新モデル整理部２０５は、自己遷移のみで、他の状態ノードからの遷移が無い状態ノードを消去することで、パラメータ更新モデルまたはトポロジー更新モデルを整理する。更新モデル整理部２０５は、整理後の更新モデルのパラメータを、学習ポストプロセス部２４とユーザ別モデルパラメータ記憶部１２に供給して、処理を終了する。
【０３５０】
［目的地経由地検出部２５の処理］
次に、図５１を参照して、学習ブロック１１の目的地経由地検出部２５（図１）の処理について説明する。
【０３５１】
上述したように、学習メインプロセス部２３は、移動履歴データを分割およびホールドする処理が行われた後の（移動属性付き）移動履歴データを学習用データとして、ユーザ活動モデルのパラメータを学習する。そして、学習ポストプロセス部２４が、学習により求めたパラメータを用いて、移動履歴データに対応する状態系列データを生成する。
【０３５２】
図５１Ａは、図８下段に示した、学習プリプロセス部２２によって移動履歴データの分割およびホールドが行われた後の、移動属性付き移動履歴データ８３Ａおよび８３Ｂを示している。
【０３５３】
図５１Ｂは、図８下段に示した移動属性付き移動履歴データ８３Ａおよび８３Ｂに、対応する状態系列データを併せて示した図である。
【０３５４】
移動属性付き移動履歴データ８３Ａには、ｓ１，ｓ２，・・・，ｓｋ，・・・ｓｔの状態系列ノードが対応する。移動属性付き移動履歴データ８３Ｂには、ｓｔ＋１，ｓｔ＋２，・・・，ｓＴの状態系列ノードが対応する。
【０３５５】
目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、目的地の属性を付与する。図５１Ｂの例では、移動属性付き移動履歴データ８３Ａの状態ノードｓｔと、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴに対して、目的地の属性が付与される。状態ノードｓｔと状態ノードｓＴは、いずれも滞在状態が滞在閾値時間以上継続していた状態ノードである。このように、目的地経由地検出部２５によって、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードが、目的地に推定される。
【０３５６】
なお、図８を参照して説明した分割処理では、分割した移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”が、１つの”滞在状態”に縮減された。しかしながら、分割処理では、移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”のすべてを、消去するようにしてもよい。図５１Ａの例で説明すると、移動属性付き移動履歴データ８３Ａおよび８３Ｂそれぞれの最後の”滞在状態（ｕ）”の３次元データを省略するようにしてもよい。この場合には、目的地経由地検出部２５は、１まとまりの移動属性付き移動履歴データの最後の３次元データに対応する状態ノードに、目的地の属性を付与する。図５１Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｔの１つ前の状態ノードｓｔ−１、および、移動属性付き移動履歴データ８３Ｂの状態ノードｓＴの１つ前の状態ノードｓＴ−１を目的地とすればよい。
【０３５７】
目的地経由地検出部２５は、また、１まとまりの移動属性付き移動履歴データの途中にある”滞在状態（ｕ）”の３次元データに対応する状態ノードを検出し、経由地の属性を付与する。即ち、滞在状態の継続時間が滞在閾値時間未満である移動履歴データに対応する状態ノードが、経由地に推定される。図５１Ｂの例で説明すると、移動属性付き移動履歴データ８３Ａの状態ノードｓｋが、経由地に決定される。
【０３５８】
なお、目的地経由地検出部２５は、図５１Ｃに示すように、移動手段が変更されたとき、変更前の最後の状態ノードｓｈにも、経由地の属性を付与するようにしてもよい。
【０３５９】
［学習ブロック１１の処理］
図５２のフローチャートを参照して、学習ブロック１１全体の処理について説明する。
【０３６０】
初めに、ステップＳ２４１において、履歴データ蓄積部２１は、センサデバイスから供給される、移動履歴データを、学習用データとして蓄積する。
【０３６１】
ステップＳ２４２において、学習プリプロセス部２２は、図１８を参照して説明した、学習プリプロセス処理を実行する。即ち、履歴データ蓄積部２１に蓄積されている移動履歴データの接続および分割の処理、移動履歴データを構成する３次元データそれぞれに、”滞在状態”または”移動状態”の移動属性の付与、などを行う。
【０３６２】
ステップＳ２４３において、学習メインプロセス部２３は、図５０を参照して説明した、学習メインプロセス処理を実行する。即ち、学習メインプロセス部２３は、供給されるユーザの移動履歴データに対して、既知または未知を判定し、判定結果に応じてユーザ活動モデルとしての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]は、次式（２７）で表すことができる。
【数１８】
2012008659.tif 000020
ここで、δは、クロネッカー関数を表し、添え字のｉとｊが一致するときのみ１となり、それ以外は０となる関数である。
【０３９３】
したがって、例えば、図５４の状態s５の状態遷移確率aijが、自己遷移確率a５，５＝０．５，遷移確率a５，６＝０．２，遷移確率a５，１１＝０．３である場合、状態s５から状態s６または状態s１１に分岐する場合の遷移確率[a５，６]および遷移確率[a５，１１]は、それぞれ、０．４，０．６となる。
【０３９４】
探索された経路の状態siのノード番号ｉが、（ｙ１，ｙ２，・・・，ｙｎ）であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式（２８）で表すことができる。
【数１９】
2012008659.tif 000021
【０３９５】
なお、実際には、通過点での規格化された遷移確率[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１９が注目ノードに設定されたとき、図５５Dに示されるように、未探索リストから、状態s１９が削除される。
【０４０１】
以上のように、目的地経由地予測部４２によるツリー探索処理は、検出された分岐先を未探索リストの最上位に記録させることで、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される。
【０４０２】
なお、探索の深さが深くなる、換言すれば、現在地ノードを最上位として下位の階層が深くなることで、全てを探索することが難しいことも考えられる。そのような場合には、例えば、１）遷移確率の低い分岐先は探索しない、２）生起確率の低い経路は探索しない、３）探索する深さに制限を加える、４）探索する枝の数に制限を加える、などの条件を加えて、途中で探索を終了するようにしてもよい。
【０４０３】
図５６は、ツリー探索処理における探索結果リストの例を示している。
【０４０４】
深さ優先アルゴリズムによりツリー探索処理を行うことにより、探索結果リストには、選択確率の高い経路から順に登録される。
【０４０５】
図５６の例では、探索結果リストの１番目には、目的地ｇ１までの経路Ｒ１（ｒ１，ｒ２，ｒ３，ｒ４）が登録され、この経路Ｒ１が選択される確率はＰ１で、経路Ｒ１を使って目的地ｇ１までにかかる時間がＴ１である。探索結果リストの２番目には、目的地ｇ２までの経路Ｒ２（ｒ１，ｒ２，ｒ３，ｒ５）が登録され、この経路Ｒ２が選択される確率はＰ２で、経路Ｒ２を使って目的地ｇ２までにかかる時間がＴ２である。探索結果リストの３番目には、目的地ｇ３までの経路Ｒ３（ｒ１，ｒ２，ｒ６）が登録され、この経路Ｒ３が選択される確率はＰ３で、経路Ｒ３を使って目的地ｇ３までにかかる時間がＴ３である。
【０４０６】
探索結果リストの４番目には、経由地ｗ２までの経路Ｒ４（ｒ１，ｒ２，ｒ７）が登録され、この経路Ｒ４が選択される確率はＰ４で、経路Ｒ４を使って経由地ｗ２までにかかる時間がＴ４である。探索結果リストの５番目には、経由地ｗ１までの経路Ｒ５（ｒ１，ｒ８）が登録され、この経路Ｒ５が選択される確率はＰ５で、経路Ｒ５を使って経由地ｗ１までにかかる時間がＴ５である。
【０４０７】
探索結果リストの６番目には、目的地ｇ３までの経路Ｒ６（ｒ１，ｒ８，ｗ１，ｒ８，ｒ９）が登録され、この経路Ｒ６が選択される確率はＰ６で、経路Ｒ６を使って目的地ｇ３までにかかる時間がＴ６である。探索結果リストの７番目には、この経路Ｒ７が選択される確率はＰ７で、目的地ｇ２までの経路Ｒ７（ｒ１，ｒ１０，ｒ１１）が登録され、経路Ｒ７を使って目的地ｇ２までにかかる時間がＴ７である。
【０４０８】
目的地または経由地まで、各経路が選択される確率は、上述した式（１３）により計算される。さらに、目的地までの経路が複数存在する場合、その目的地までの複数の経路の選択確率の和が、目的地の到達確率となる。
【０４０９】
従って、図５６の例では、目的地ｇ２へ行くには、経路Ｒ２を利用する場合と、経路Ｒ７を利用する場合があり得るので、目的地ｇ２の到達確率は、は（Ｐ２＋Ｐ７）となる。同様に、目的地ｇ３へ行くには、経路Ｒ３を利用する場合と、経路Ｒ６を利用する場合があり得るので、目的地ｇ３の到達確率は、は（Ｐ３＋Ｐ６）となる。なお、目的地ｇ１の到達確率は、経路Ｒ１が選択される確率Ｐ１と同一である。
【０４１０】
［予測ポストプロセス部３４の処理］
次に、予測ポストプロセス部３４が行う処理について説明する。
【０４１１】
目的地または経由地まで、選択された経路で移動したときにかかる時間の求め方について説明する。
【０４１２】
例えば、現在時刻ｔ１の現在地が状態ｓｙ１であり、時刻（ｔ１，ｔ２，・・・，ｔｇ）における決定された経路が（ｓｙ１，ｓｙ２，・・・，ｓｙｇ）であるとする。換言すれば、決定された経路の状態siのノード番号ｉが（ｙ１，ｙ２，・・・，ｙｇ）であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号ｉで表わす場合もある。
【０４１３】
現在時刻ｔ１での現在地ｙ１は、現在地ノード推定部４１により確定しているので、現在時刻ｔ１の現在地がｙ１である確率Ｐｙ１（ｔ１）は、
Ｐｙ１（ｔ１）＝１である。また、現在時刻ｔ１にｙ１以外の他の状態にいる確率は０である。
【０４１４】
一方、所定の時刻ｔｎにノード番号ｙｎにいる確率Ｐｙｎ（ｔｎ）は、
【数２０】
2012008659.tif 000022
で表すことができる。式（２９）の右辺第一項は、もともとその位置ｙｎにいて、自己遷移した場合の確率を表し、右辺第二項は、１つ前の位置ｙｎ−１から位置ｙｎに遷移してきた場合の確率を表している。式（２９）では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【０４１５】
目的地ｙｇへ到達するときの時刻ｔｇの予測値<ｔｇ>は、「その直前の時刻ｔｇ−１に目的地ｙｇの１つ前の位置ｙｇ−１にいて、時刻ｔｇに目的地ｙｇに移動する確率」を用いて、
【数２１】
2012008659.tif 000023
と表すことができる。
【０４１６】
即ち、予測値<ｔｇ>は、現在時刻から、「その直前の時刻ｔｇ−１に状態ｓｙｇの１つ前の状態ｓｙｇ−１にいて、時刻ｔｇに状態ｓｙｇに移動するとき」までの時間の期待値で表される。
【０４１７】
以上より、所定の目的地または経由地まで、選択された経路で移動したときにかかる時間は、上述した式（３０）の予測値<ｔｇ>により求められる。
【０４１８】
図５６の例を使用して、目的地までの経路が探索された場合に、代表経路として選択する代表経路選択処理について説明する。
【０４１９】
図５６のような探索結果リストが得られた場合、探索結果リストには、選択確率が高いものから順に（上位に）登録されるので、選択確率が上位であり、目的地も異なる、探索結果リストの１番目乃至３番目が予測結果として出力される。即ち、経目的地ｇ１とその経路Ｒ１、目的地ｇ２とその経路Ｒ２、目的地ｇ３とその経路Ｒ３が、目的地とその代表経路として選択される。
【０４２０】
次に、探索結果リストの４番目および５番目は経由地までの経路であるためスキップされ、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６を代表経路とするかが検討される。この経路Ｒ６は、既に代表経路として選択されている、同一の目的地ｇ３の経路Ｒ３には含まれていない経由地ｗ１を利用するものとなっている。したがって、目的地ｇ３へ到達するための経路Ｒ６も、代表経路として選択される。
【０４２１】
次に、探索結果リストの７番目の、目的地ｇ２へ到達するための経路Ｒ７を代表経路とするかが検討される。この経路Ｒ７は、既に代表経路として選択されている、同一の目的地ｇ２と同じく、所定の経由地を経由しないものとなっている。したがって、目的地ｇ２へ到達するための経路Ｒ７は、代表経路として選択されない。
【０４２２】
このように、代表経路選択処理では、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路は、同一目的地であっても、予測結果として提示することができる。
【０４２３】
なお、探索結果リストの６番目の、目的地ｇ３へ到達するための経路Ｒ６は、［背景技術］に示した先願２の方法では、経由地ｗ１で探索が終了されていた。しかしながら、予測システム１によれば、経由地ｗ１で終了することなく、経由地ｗ１を利用して目的地ｇ３へ到達する経路まで探索することが可能となっている。
【０４２４】
予測システム１によれば、学習により得られた状態ノードに、目的地と経由地を区別して属性を付与することで、途中の経由地を目的地として予測することを防止することができる。また、同一目的地への経路が複数探索された場合、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路を提示することができる。
【０４２５】
図５７は、予測ポストプロセス部３４が行う代表経路選択処理のフローチャートである。
【０４２６】
初めに、ステップＳ３０１において、予測ポストプロセス部３４は、目的地経由地予測部４２で作成された探索結果リストから、経由地までの経路を除外し、目的地のみの探索結果リストである目的地リストを生成する。
【０４２７】
ステップＳ３０２において、予測ポストプロセス部３４は、目的地リストを目的地別に並び替えた目的地別目的地リストに変更する。このとき、予測ポストプロセス部３４は、同一の目的地内における順位を変えないように目的地別目的地リストを生成する。
【０４２８】
ステップＳ３０３において、予測ポストプロセス部３４は、目的地ごとの到達確率を算出する。目的地までの経路が１つしかない場合には、その経路の選択確率が到達確率となり、目的地まで複数の経路が存在する場合には、複数の選択確率（生起確率）の和が、その目的地の到達確率となる。
【０４２９】
ステップＳ３０４において、予測ポストプロセス部３４は、代表経路の選択に経由地を考慮するかを判定する。ステップＳ３０４で、経由地を考慮しないと判定された場合、処理はステップＳ３０５に進み、予測ポストプロセス部３４は、目的地別に、最上位の経路を、各目的地の代表経路として選択し、処理を終了する。その結果、目的地まで複数の経路が存在する場合には、選択確率の高い目的地までの経路が、各目的地の代表経路とされ、その所要時間が、目的地までの所要時間として提示される。なお、目的地が多数ある場合には、上位から、予め設定した個数の目的地のみを提示するようにさせることができる。
【０４３０】
一方、ステップＳ３０４で、経由地を考慮すると判定された場合、処理はステップＳ３０６に進み、予測ポストプロセス部３４は、目的地別目的地リストを、経由地なしの目的地別目的地リストと、経由地ありの目的地別目的地リストに分類する。
【０４３１】
そして、ステップＳ３０７において、予測ポストプロセス部３４は、経由地なしの目的地別目的地リストから、目的地別に、最上位の経路を代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地なしの経路が決定される。
【０４３２】
次に、ステップＳ３０８において、予測ポストプロセス部３４は、経由地ありの目的地別目的地リストを、さらに、経由地別に分類する。
【０４３３】
ステップＳ３０９において、予測ポストプロセス部３４は、経由地別の、経由地ありの目的地別目的地リストから、目的地別に、各経由地の最上位の経路を、代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地ありの経路が決定される。その結果、目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方が、各目的地の代表経路とされ、それぞれの所要時間が、目的地までの所要時間として提示される。
【０４３４】
以上により、代表経路選択処理は終了する。このように、目的地への経路が複数存在する場合、生起確率の上位を複数提示するよりも、経由地によって分類して提示する方が、ユーザが実際に感じる予測に近いものとすることができる。
【０４３５】
［予測ブロック１３全体の処理］
図５８のフローチャートを参照して、予測ブロック１３全体の処理について説明する。
【０４３６】
初めに、ステップＳ３２１において、バッファリング部３１は、予測処理のため、リアルタイムに取得される移動履歴データをバッファリングする。
【０４３７】
ステップＳ３２２において、予測プリプロセス部３２は、予測プリプロセス処理を実行する。具体的には、学習プリプロセス部２２が行う学習プリプロセス処理と同様の、移動履歴データの接続および分割の処理、移動履歴データの明らかな異常を除去する処理、および、欠落データを補完する処理を実行する。但し、移動履歴データを分割する際の基準となる滞在閾値時間は、学習プリプロセス処理と異なる時間であってもよい。
【０４３８】
ステップＳ３２３において、予測メインプロセス部３３は、学習ブロック１１の学習により得られたユーザ活動モデルのパラメータを、ユーザ別モデルパラメータ記憶部１２から取得する。このパラメータを取得する処理は、図３３の目的地を予測する処理とは別に、予め実行するようにしてもよい。
【０４３９】
ステップＳ３２４において、予測メインプロセス部３３の現在地ノード推定部４１は、学習ブロック１１の学習により得られたパラメータを用いたユーザ活動モデルにより、ユーザの現在地に対応する状態ノード（現在地ノード）を推定する。より具体的には、現在地ノード推定部４１は、学習ブロック１１の学習により得られたパラメータを用いたユーザ活動モデルにより、移動履歴データに対応するノード系列データを算出する。そして、現在地ノード推定部４１は、ノード系列データの最後の状態ノードを現在地ノードとする。ノード系列データの算出には、ビタビアルゴリズムが採用される。
【０４４０】
ステップＳ３２５において、予測メインプロセス部３３の目的地経由地予測部４２は、図５３を参照して説明した、現在地ノード以降のツリー探索処理を実行する。ツリー探索処理と同時に、目的地および経由地までの経路（ノード系列）の生起確率も、式（２８）により求められる。
【０４４１】
ステップＳ３２６において、予測ポストプロセス部３４は、図５７を参照して説明した、代表経路の選択処理を実行する。
【０４４２】
ステップＳ３２７において、予測ポストプロセス部３４は、上述した式（３０）により、選択された各代表経路の所要時間を算出する。
【０４４３】
ステップＳ３２８において、予測ポストプロセス部３４は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力して、処理を終了する。
【０４４４】
以上のように、予測ブロック１３の処理では、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られたパラメータで表現されるユーザ活動モデルとを用いて、ユーザの現在地から目的地までの経路が探索される。学習により得られた状態ノードに目的地と経由地の属性が付与されているので、経由地を目的地として予測することを防止することができる。
【０４４５】
また、学習により得られた状態ノードに目的地と経由地の属性が付与されているので、同一目的地への経路であっても、経由地なしの経路と、経由地ありの経路を代表経路として出力することができる。
【０４４６】
[データ処理結果の例]
図５９乃至図６３に、上述した本発明を適用した予測システム１の学習メインプロセス部２３で、あるユーザの移動履歴データを学習させたときの学習処理結果を示す。
【０４４７】
図５９は、本発明（学習メインプロセス部２３）によるモデル化と、従来のHMMによるモデル化の状態ノードの学習結果を比較した図である。
【０４４８】
図５９Aは、本発明によるモデル化、即ち、図３１に示したように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようにモデル化した学習モデルによる学習結果を示している。
【０４４９】
図５９Bは、従来のHMMによるモデル化した学習モデルによる学習結果である。
【０４５０】
図５９Aおよび図５９Bにおいて、楕円は、各状態ノードが表すデータの分布（正規分布）の等高線を表している。ここでは、楕円の中心が各状態ノードの緯度経度の平均値であり、また、楕円の大きさが各状態ノードの緯度経度の分散値に比例している。
【０４５１】
図５９Bの従来のモデル化では、状態ノードの分散は、サンプルの中心に収束する（下限に到達している）が、図５９Aの本発明のモデル化では、ノードの分散は、サンプルとサンプルの間を覆うように、長く伸びている。この結果、図５９Bの従来のモデル化では、全体の状態ノードをみても、サンプル付近しか覆っていない部分があるが、図５９Aの本発明のモデル化では、経路全体を覆っていることがわかる。
【０４５２】
図５９Aおよび図５９Bでは、分散のパラメータは、時刻、緯度、経度の各次元でそれぞれ用意されている。このような場合、移動履歴データは、長軸が、緯度、経度に平行な楕円で表される状態ノードでモデル化される。すると、移動方向が、緯度、経度のいずれかに平行な場合は、経路をモデル化して、経路以外の領域以外は覆わなくなる。しかし、移動方向が斜めの場合は、経路以外の余分な領域を多く覆うようになる。そこで、余分な領域をモデル化することを極力避けたい場合には、分散のパラメータに共分散を用いるようにすればよい。この場合、移動履歴データは、斜めの楕円による状態ノードでモデル化されるようになる。その結果、移動方向が斜めの場合でも、経路以外の余分な領域を覆わずにモデル化ができる。
【０４５３】
図６０は、１回目に学習させた移動経路とその学習結果を示している。移動履歴データは、ユーザが、自宅から、ある目的地に出かけた際に、１５行間隔でサンプリングした３次元データである。
【０４５４】
図６０左側の地図上には、予測システム１に学習させた移動履歴データが黒丸で示され、黒丸の周辺に位置する楕円が学習結果の状態ノードを示している。この学習結果を参照しても、状態ノードはサンプル間の経路をモデル化するように学習されていることが分かる。
【０４５５】
この移動履歴データは、学習メインプロセス部２３の１回目の学習に使用されたデータであるので、既知未知判定部２０１の既知未知判定処理では、未知の移動履歴データと判定されるはずである。
【０４５６】
図６０右側の上下に並んだ２図は、図６０左側の移動履歴データの既知未知判定結果を示している。上段の図は、飽和対数尤度を示し、下段の図は、ビタビ判定による既知未知判定結果を示している。既知未知判定結果は、未知に対応する”−１”が継続的に出力されており、正確に未知の経路と学習されていることを示している。
【０４５７】
図６１は、ユーザが図６０の移動経路を通って到達した目的地から、同一経路を通って帰ったときの帰路の移動履歴データを学習させたときの学習結果を示している。
【０４５８】
この場合、ユーザが移動した経路の各場所は、ユーザが知っている場所であるから、既知未知判定結果は、一見、既知とされるところである。しかし、行動予測を行なう上では、ユーザの意図が重要で、同じ場所でも行きか、帰りかのユーザの意図を正しく区別してモデル化を行う必要がある。従って、図６１の帰路の移動履歴データに対しては、既知未知判定において、未知と判定されなければならない。
【０４５９】
図６１右側の既知未知判定結果を参照すると、未知に対応する”−１”が継続的に出力されており、学習メインプロセス部２３の既知未知判定部２０１が未知の経路と正確に判定していることを示している。
【０４６０】
図６２は、ユーザが全く異なる経路を通って図６０と同一の目的地へ移動した場合の移動履歴データの学習結果を示している。
【０４６１】
図６２左側の地図上の、横方向の楕円の連なりが、図６０で示した経路の学習結果を、縦方向の大きめの楕円の連なりが、全く異なる経路による学習結果を示している。なお、地図の縮尺は、図６０と図６２で異なる。
【０４６２】
図６２右側の既知未知判定結果を参照すると、未知に対応する”−１”が継続的に出力されており、全く異なる経路の移動履歴データについて、学習メインプロセス部２３の既知未知判定部２０１が未知の経路と正確に判定していることを示している。
【０４６３】
図６３は、さらに別の移動経路を学習させたときの学習結果を示している。
【０４６４】
具体的には、図６３は、あるユーザの自宅から勤務地までの移動経路を、第１の経路を通る１回目の学習をさせた後、第２の経路を通る２回目の学習をさせたときの学習結果を示している。
【０４６５】
ここで、第１の経路と、第２の経路とは、自宅から、途中の経由地までの経路が、寄り道をせずに移動した場合と、所定の場所へ寄り道をして移動した場合の違いである。そして、途中の経由地から目的地である勤務地までの後半の移動経路は同一である。
【０４６６】
図６３右側の既知未知判定結果を参照すると、移動経路の前半部分には未知に対応する”−１”が出力されており、移動経路の後半部分には既知に対応する”１”が出力されている。これは、自宅から途中の経由地までの経路を「未知」と、途中の経由地から勤務地までの経路を「既知」と判定していることを示している。従って、学習メインプロセス部２３の既知未知判定部２０１が既知と未知の経路を正確に区別して学習できていることがわかる。
【０４６７】
また、図６３左側の地図上に表示されている状態ノードでは、モノクロ表示ではうまく区別できないが、１回目の学習データの経路を覆う状態ノードには、２回目の学習で新たに追加された状態ノードが含まれていない。一方、２回目の学習データの経路を覆う状態ノードは、全て２回目の学習で新たに追加された状態ノードとなっている。即ち、既知の経路の移動履歴データについては、トポロジーの変更がなく、既存モデルのパラメータの更新により学習し、未知の経路の移動履歴データについてのみ、新たな状態ノードが追加されている。従って、学習メインプロセス部２３の学習では、無駄に状態ノードを追加することなく、新たな移動履歴データを学習モデルに反映させ、過不足のない学習モデルのモデル化を行うことができる。換言すれば、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができる。
【０４６８】
［コンピュータの構成例］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【０４６９】
図６４は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【０４７０】
コンピュータにおいて、CPU（Central Processing Unit）３２１，ROM（Read Only Memory）３２２，RAM（Random Access Memory）３２３は、バス３２４により相互に接続されている。
【０４７１】
バス３２４には、さらに、入出力インタフェース３２５が接続されている。入出力インタフェース３２５には、入力部３２６、出力部３２７、記憶部３２８、通信部３２９、ドライブ３３０、およびGPSセンサ３３１が接続されている。
【０４７２】
入力部３２６は、キーボード、マウス、マイクロホンなどよりなる。出力部３２７は、ディスプレイ、スピーカなどよりなる。記憶部３２８は、ハードディスクや不揮発性のメモリなどよりなる。通信部３２９は、ネットワークインタフェースなどよりなる。ドライブ３３０は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体３３２を駆動する。上述のセンサデバイスとしてのGPSセンサ３３１は、現在地の位置（緯度および経度）のデータと、そのときの時刻からなる３次元データを出力する。
【０４７３】
以上のように構成されるコンピュータでは、CPU３２１が、例えば、記憶部３２８に記憶されているプログラムを、入出力インタフェース３２５及びバス３２４を介して、RAM３２３にロードして実行することにより、上述した一連の処理が行われる。
【０４７４】
コンピュータ（CPU３２１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体３３２に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０４７５】
コンピュータでは、プログラムは、リムーバブル記録媒体３３２をドライブ３３０に装着することにより、入出力インタフェース３２５を介して、記憶部３２８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部３２９で受信し、記憶部３２８にインストールすることができる。その他、プログラムは、ROM３２２や記憶部３２８に、あらかじめインストールしておくことができる。
【０４７６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０４７７】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【０４７８】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０４７９】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０４８０】
１  予測システム，  １１  学習ブロック，  １３  予測ブロック，  ２２  学習プリプロセス部，  ２３  学習メインプロセス部，  ２４  学習ポストプロセス部，  ２５  目的地経由地検出部，  ３２  予測プリプロセス部，  ３３  予測メインプロセス部，  ３４  予測ポストプロセス部，  ２０１  既知未知判定部，  ２０２  新規モデル生成部，  ２０３  新規モデル結合部，  ２０４  パラメータ更新部，  ２０５  モデル整理部，  ２２１  既存モデル構築部，  ２２２  未知状態ノード追加部，  ２２３  状態ノード推定部，  ２２４  サンプル別尤度計算部，  ２２５  既知未知モデル記憶部，  ２２６  既知未知判定部，  ２２７  既知未知ポスト処理部，  ２４３  新規モデル学習部，  ２４４  ノード系列判定部，  ２４５  パラメータ再計算部
【図１】
2012008659.tif 000024
【図２】
2012008659.tif 000025
【図３】
2012008659.tif 000026
【図４】
2012008659.tif 000027
【図５】
2012008659.tif 000028
【図６】
2012008659.tif 000029
【図７】
2012008659.tif 000030
【図８】
2012008659.tif 000031
【図９】
2012008659.tif 000032
【図１０】
2012008659.tif 000033
【図１１】
2012008659.tif 000034
【図１２】
2012008659.tif 000035
【図１３】
2012008659.tif 000036
【図１４】
2012008659.tif 000037
【図１５】
2012008659.tif 000038
【図１６】
2012008659.tif 000039
【図１７】
2012008659.tif 000040
【図１８】
2012008659.tif 000041
【図１９】
2012008659.tif 000042
【図２０】
2012008659.tif 000043
【図２１】
2012008659.tif 000044
【図２２】
2012008659.tif 000045
【図２３】
2012008659.tif 000046
【図２４】
2012008659.tif 000047
【図２５】
2012008659.tif 000048
【図２６】
2012008659.tif 000049
【図２７】
2012008659.tif 000050
【図２８】
2012008659.tif 000051
【図２９】
2012008659.tif 000052
【図３０】
2012008659.tif 000053
【図３１】
2012008659.tif 000054
【図３２】
2012008659.tif 000055
【図３３】
2012008659.tif 000056
【図３４】
2012008659.tif 000057
【図３５】
2012008659.tif 000058
【図３６】
2012008659.tif 000059
【図３７】
2012008659.tif 000060
【図３８】
2012008659.tif 000061
【図３９】
2012008659.tif 000062
【図４０】
2012008659.tif 000063
【図４１】
2012008659.tif 000064
【図４２】
2012008659.tif 000065
【図４３】
2012008659.tif 000066
【図４４】
2012008659.tif 000067
【図４５】
2012008659.tif 000068
【図４６】
2012008659.tif 000069
【図４７】
2012008659.tif 000070
【図４８】
2012008659.tif 000071
【図４９】
2012008659.tif 000072
【図５０】
2012008659.tif 000073
【図５１】
2012008659.tif 000074
【図５２】
2012008659.tif 000075
【図５３】
2012008659.tif 000076
【図５４】
2012008659.tif 000077
【図５５】
2012008659.tif 000078
【図５６】
2012008659.tif 000079
【図５７】
2012008659.tif 000080
【図５８】
2012008659.tif 000081
【図５９】
2012008659.tif 000082
【図６０】
2012008659.tif 000083
【図６１】
2012008659.tif 000084
【図６２】
2012008659.tif 000085
【図６３】
2012008659.tif 000086
【図６４】
2012008659.tif 000087