説明

データ処理装置、データ処理方法、およびプログラム

【課題】未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにする。
【解決手段】学習メインプロセス部23は、学習用データとしての移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める。学習用データとしての移動履歴データが供給された場合、学習メインプロセス部23は、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、既知の場合は、既存モデルのパラメータの更新を行い、未知の場合は、新規モデルを生成し、既存モデルと結合した更新モデルを生成する。本発明は、例えば、移動履歴データから目的地を予測するデータ処理装置に適用できる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ処理装置、データ処理方法、およびプログラムに関し、特に、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにするデータ処理装置、データ処理方法、およびプログラムに関する。
【背景技術】
【0002】
近年、ユーザが身に着けられるセンサであるウェアラブルセンサから得られる時系列データを用いてユーザの状態をモデル化して学習し、学習により得られたモデルを用いてユーザの現在の状態を認識する研究が盛んである(例えば、特許文献1,2、非特許文献1)。
【0003】
本出願人は、未来の所望の時刻におけるユーザの活動状態の複数の可能性を確率的に予測する方法を、特願2009−180780号(以下、先願1という)として先に提案している。先願1の方法では、時系列データからユーザの活動状態を確率的状態遷移モデルとして学習し、学習した確率的状態遷移モデルを用いて現在の活動状態を認識し、「所定時間後」のユーザの活動状態を確率的に予測することができる。先願1では、「所定時間後」のユーザの活動状態の予測の一例として、ユーザの移動履歴の時系列データ(移動履歴データ)を学習した確率的状態遷移モデルを用いて、ユーザの現在の位置を認識し、所定時間後のユーザの行き先(場所)を予測する例が示されている。
【0004】
さらに、本出願人は、先願1を発展させ、「所定時間後」という現在時刻からの経過時間の指定がない場合であっても、複数の目的地への到達確率、経路、時間を予測する方法を、特願2009−208064号(以下、先願2という)として提案した。先願2の方法では、確率的状態遷移モデルを構成する状態ノードに、”移動状態”かまたは”滞在状態”の属性が付与された。そして、確率的状態遷移モデルを構成する状態ノードの中から、目的地の状態ノードとして”滞在状態”の状態ノードを見つけることで、目的地の候補を自動的に検出することができた。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2006−134080号公報
【特許文献2】特開2008−204040号公報
【非特許文献】
【0006】
【非特許文献1】“Life Patterns: structure from wearable sensors”,Brian Patrick Clarkson, Doctor Thesis, MIT, 2002
【発明の概要】
【発明が解決しようとする課題】
【0007】
ところで、学習データとして新たに取得された移動履歴データを用いて追加学習する場合、学習時間を短縮させるため、新たに取得された移動履歴データのみを学習する差分学習を行うのが一般的である。
【0008】
しかしながら、差分学習は、通常、同一のモデルのパラメータを変化させるものである。新たに取得された移動履歴データが既知の経路を再度移動したデータであれば、既存の確率的状態遷移モデルのパラメータを更新させればよい。しかし、取得された移動履歴データがこれまでの学習にない未知の経路を移動したデータであれば、新たな状態ノードを追加し、追加した状態ノードに学習させることが望ましいが、従来の差分学習では、ユーザの行動範囲のトポロジーを成長させることは難しい。
【0009】
本発明は、このような状況に鑑みてなされたものであり、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができるようにするものである。
【課題を解決するための手段】
【0010】
本発明の一側面のデータ処理装置は、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備え、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段と
を有し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる。
【0011】
本発明の一側面のデータ処理方法は、
ユーザの移動履歴データを処理するデータ処理装置の、
学習手段が、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求め、
目的地経由地推定手段が、求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
現在地推定手段が、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
探索手段が、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
算出手段が、探索された前記目的地への到達確率と所要時間を算出する
ステップを含み、
前記学習手段のステップでは、
既知未知判定手段が、前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、
パラメータ更新手段が、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新し、
新規モデル生成手段が、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求め、
新規モデル結合手段が、前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段のステップでは、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる。
【0012】
本発明の一側面のプログラムは、
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させ、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段
としての機能を含み、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
ためのプログラムである。
【0013】
本発明の一側面においては、学習手段において、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータが求められ、目的地経由地推定手段において、求められたパラメータを用いた確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードが推定され、現在地推定手段において、学習用データとは別の、現在から所定時間以内のユーザの移動履歴データが、学習により得られたパラメータを用いた確率モデルに入力され、ユーザの現在地に相当する現在地ノードが推定され、探索手段において、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られた確率モデルとを用いて、ユーザの現在地から目的地までの経路が探索され、算出手段において、探索された目的地への到達確率と所要時間が算出される。
学習手段では、既知未知判定手段において、確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかが判定され、パラメータ更新手段において、新たな学習用データが既知の経路の移動履歴データであると判定された場合、既に求めた確率モデルである既存モデルのパラメータが更新され、新規モデル生成手段において、新たな学習用データが未知の経路の移動履歴データであると判定された場合、未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータが求められ、新規モデル結合手段において、既存モデルのパラメータと、新規モデルのパラメータを合成することで、既存モデルと新規モデルを結合した更新モデルが生成され、目的地経由地推定手段、現在地推定手段、探索手段、および算出手段のステップでは、確率モデルが新たな学習用データにより更新された場合、更新後の確率モデルを用いた処理が行われる。
【発明の効果】
【0014】
本発明の一側面によれば、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができる。
【図面の簡単な説明】
【0015】
【図1】本発明を適用した予測システムの一実施の形態の構成例を示すブロック図である。
【図2】予測システムのハードウエア構成例を示すブロック図である。
【図3】移動履歴データの例を示す図である。
【図4】HMMの例を示す図である。
【図5】left-to-right型のHMMの例を示す図である。
【図6】スパース制約を与えたHMMの例を示す図である。
【図7】学習プリプロセス部の詳細構成例を示すブロック図である。
【図8】学習プリプロセス部の処理について説明する図である。
【図9】移動属性識別付与部の詳細構成例を示すブロック図である。
【図10】移動属性識別部の学習器の構成例を示すブロック図である。
【図11】行動状態をカテゴリごとに分類する場合の分類例を示す図である。
【図12】行動状態ラベリング部の処理例を説明する図である。
【図13】行動状態ラベリング部の処理例を説明する図である。
【図14】図10の行動状態学習部の構成例を示すブロック図である。
【図15】移動属性識別部の詳細構成例を示すブロック図である。
【図16】移動属性識別部の学習器のその他の構成例を示すブロック図である。
【図17】移動属性識別部のその他の構成例を示すブロック図である。
【図18】学習プリプロセス部の処理を説明するフローチャートである。
【図19】図1の学習メインプロセス部の詳細構成例を示すブロック図である。
【図20】既知未知判定部の詳細な構成例を示すブロック図である。
【図21】未知状態ノード追加部による未知状態追加モデルの構築処理を説明するフローチャートである。
【図22】未知状態追加モデルの初期確率テーブルを説明する図である。
【図23】未知状態追加モデルの遷移確率テーブルを説明する図である。
【図24】未知状態追加モデルの中心値テーブルを説明する図である。
【図25】未知状態追加モデルの分散値テーブルを説明する図である。
【図26】既知未知判定部の既知未知判定処理を説明する説明するフローチャートである。
【図27】既知未知判定処理を行った結果の例を示す図である。
【図28】既知未知判定処理を行った結果の例を示す図である。
【図29】新規モデル生成部の詳細な構成例を示すブロック図である。
【図30】通常のHMMによる学習モデルと、新規モデル学習部が行う学習モデルの違いについて説明する図である。
【図31】通常のHMMによる学習モデルと、新規モデル学習部が行う学習モデルの違いについて説明する図である。
【図32】新規モデル学習部の学習モデルをグラフィカルモデルで表した図である。
【図33】新規モデル学習部の新規モデル学習処理を説明するフローチャートである。
【図34】パラメータ再計算部のパラメータ再計算処理を説明するフローチャートである。
【図35】新規モデル生成部が行う新規モデル生成処理全体のフローチャートである。
【図36】新規モデル結合部によるトポロジー更新モデル生成処理を説明するフローチャートである。
【図37】トポロジー更新モデルの初期確率テーブルを説明する図である。
【図38】トポロジー更新モデルの遷移確率テーブルを説明する図である。
【図39】トポロジー更新モデルの遷移確率テーブルを説明する図である。
【図40】トポロジー更新モデルの遷移確率テーブルを説明する図である。
【図41】トポロジー更新モデルの中心値テーブルを説明する図である。
【図42】トポロジー更新モデルの分散値テーブルを説明する図である。
【図43】パラメータ更新部が行うパラメータ更新処理全体のフローチャートである。
【図44】既存モデルの初期確率テーブルを説明する図である。
【図45】既存モデルの遷移確率テーブルを説明する図である。
【図46】既存モデルの遷移確率テーブルを説明する図である。
【図47】既存モデルの遷移確率テーブルを説明する図である。
【図48】既存モデルの中心値テーブルを説明する図である。
【図49】既存モデルの分散値テーブルを説明する図である。
【図50】学習メインプロセス部全体の学習メインプロセス処理のフローチャートである。
【図51】目的地経由地検出部の処理について説明する図である。
【図52】学習ブロック全体の処理を説明するフローチャートである。
【図53】ツリー探索処理を説明するフローチャートである。
【図54】ツリー探索処理をさらに説明する図である。
【図55】ツリー探索処理をさらに説明する図である。
【図56】ツリー探索処理における探索結果リストの例を示す図である。
【図57】代表経路選択処理を説明するフローチャートである。
【図58】予測ブロック全体の処理を説明するフローチャートである。
【図59】図1の学習メインプロセス部の学習処理結果の例を示す図である。
【図60】図1の学習メインプロセス部の学習処理結果の例を示す図である。
【図61】図1の学習メインプロセス部の学習処理結果の例を示す図である。
【図62】図1の学習メインプロセス部の学習処理結果の例を示す図である。
【図63】図1の学習メインプロセス部の学習処理結果の例を示す図である。
【図64】本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための形態】
【0016】
[予測システムの構成例]
図1は、本発明を適用した予測システムの一実施の形態の構成例を示している。
【0017】
図1の予測システム1は、学習ブロック11、ユーザ別モデルパラメータ記憶部12、および予測ブロック13により構成される。
【0018】
学習ブロック11には、GPS (Global Positioning System)センサなどのセンサデバイス(不図示)において、所定の期間に取得された、所定の時刻におけるユーザの位置(緯度と経度)を示す時系列データが供給される。即ち、学習ブロック11には、一定時間間隔(たとえば、15秒間隔)で順次取得された位置(緯度および経度)のデータと、そのときの時刻の3次元からなる、ユーザの移動経路を示す時系列データ(以下、移動履歴データという。)が供給される。なお、時系列データを構成する、緯度、経度、および時刻の1組のデータを、適宜、3次元データともいう。
【0019】
学習ブロック11は、ユーザの移動履歴データを用いて、ユーザの活動モデル(ユーザの行動・活動パターンを表した状態モデル)を、確率的状態遷移モデルとして学習する学習処理を行う。
【0020】
学習に使用される確率的状態遷移モデルとしては、例えば、エルゴディックHMM(Hidden Markov Model)などの、隠れ状態を含む確率モデルを採用することができる。予測システム1では、確率的状態遷移モデルとして、エルゴディックHMMにスパース制約を与えたものを採用する。なお、スパース制約を与えたエルゴディックHMM、エルゴディックHMMのパラメータの算出方法等については、図4乃至図6を参照して後述する。
【0021】
ユーザ別モデルパラメータ記憶部12は、学習ブロック11の学習により得られた、ユーザの活動モデルを表すパラメータを記憶する。
【0022】
予測ブロック13は、学習ブロック11の学習により得られたユーザ活動モデルのパラメータをユーザ別モデルパラメータ記憶部12から取得する。そして、予測ブロック13は、新たに取得されたユーザの移動履歴データに対し、学習により得られたパラメータによるユーザ活動モデルを用いて、ユーザの現在地を推定し、さらに現在地からの移動の目的地を予測する。さらに、予測ブロック13は、予測した目的地までの到達確率、経路、および到達時間(所要時間)も算出する。なお、目的地は1つだけとは限らず、複数の目的地が予測されることもある。
【0023】
学習ブロック11および予測ブロック13の詳細について説明する。
【0024】
学習ブロック11は、履歴データ蓄積部21、学習プリプロセス部22、学習メインプロセス部23、学習ポストプロセス部24、および目的地経由地検出部25により構成される。
【0025】
履歴データ蓄積部21は、センサデバイスから供給される、ユーザの移動履歴データを、学習用データとして蓄積(記憶)する。履歴データ蓄積部21は、移動履歴データを、必要に応じて学習プリプロセス部22に供給する。
【0026】
学習プリプロセス部22は、センサデバイスから生じる課題を解決する。具体的には、学習プリプロセス部22は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。また、学習プリプロセス部22は、移動履歴データを構成する3次元データそれぞれに対し、同一場所に滞在(停止)している”滞在状態”か、または、移動している”移動状態”のいずれかの移動属性を付与する。移動属性付与後の移動履歴データが、学習メインプロセス部23と目的地経由地検出部25に供給される。
【0027】
学習メインプロセス部23は、ユーザの移動履歴をユーザ活動モデルとしてモデル化する。即ち、学習メインプロセス部23は、ユーザの移動履歴データをユーザ活動モデルにモデル化したときのパラメータを求める。学習により得られたユーザ活動モデルのパラメータは、学習ポストプロセス部24とユーザ別モデルパラメータ記憶部12に供給される。
【0028】
また、学習メインプロセス部23は、ユーザの移動履歴データをユーザ活動モデルとして学習した後、新たな学習用データとしての移動履歴データが供給された場合、現在のユーザ活動モデルのパラメータをユーザ別モデルパラメータ記憶部12から取得し、更新する。
【0029】
具体的には、最初に、学習メインプロセス部23は、新たな学習用データとしての移動履歴データが既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する。そして、新たな学習用データが既知の経路の移動履歴データであると判定された場合、学習メインプロセス部23は、既存のユーザ活動モデル(以下、単に、既存モデルと称する。)のパラメータを更新する。一方、新たな学習用データが未知の経路の移動履歴データである場合、学習メインプロセス部23は、未知の経路の移動履歴データに対応する新規モデルとしてのユーザ活動モデルのパラメータを求める。そして、学習メインプロセス部23は、既存モデルのパラメータと、新規モデルのパラメータを合成することで、既存モデルと新規モデルを結合した更新モデルを生成する。
【0030】
なお、以下において、既知の経路の移動履歴データにより更新されたユーザ活動モデルは、パラメータ更新モデルと称する。一方、未知の経路の移動履歴データによりパラメータが更新されたユーザ活動モデルは、未知の経路の拡張に応じてトポロジーも更新されることから、トポロジー更新モデルと称する。また、以下では、既知の経路の移動履歴データ、および、未知の経路の移動履歴データを、単に、既知の移動履歴データ、および、未知の移動履歴データとも称する。
【0031】
パラメータ更新モデルまたはトポロジー更新モデルのパラメータは、学習ポストプロセス部24とユーザ別モデルパラメータ記憶部12に供給され、後段では、更新後のユーザ活動モデルを用いて処理が行われる。
【0032】
学習ポストプロセス部24は、学習メインプロセス部23の学習により得られたユーザ活動モデルを用いて、移動履歴データを構成する各3次元データを、ユーザ活動モデルの状態ノードに変換する。即ち、学習ポストプロセス部24は、移動履歴データに対応する、ユーザ活動モデルの状態ノードの時系列データ(ノード系列データ)を生成する。学習ポストプロセス部24は、変換後のノード系列データを目的地経由地検出部25に供給する。
【0033】
目的地経由地検出部25は、学習プリプロセス部22から供給された移動属性付与後の移動履歴データと、学習ポストプロセス部24から供給されたノード系列データとを対応付ける。即ち、目的地経由地検出部25は、移動履歴データを構成する各3次元データに、ユーザ活動モデルの状態ノードを割り当てる。
【0034】
そして、目的地経由地検出部25は、ノード系列データの各状態ノードのうち、移動属性が”滞在状態”の3次元データに対応する状態ノードに、目的地または経由地の属性を付与する。これにより、ユーザの移動履歴内の所定の場所(に対応する状態ノード)が、目的地かまたは経由地に割り当てられる。目的地経由地検出部25により、状態ノードに付与された目的地、経由地の属性についての情報は、ユーザ別モデルパラメータ記憶部12に供給され、記憶される。
【0035】
予測ブロック13は、バッファリング部31、予測プリプロセス部32、予測メインプロセス部33、および、予測ポストプロセス部34により構成される。
【0036】
バッファリング部31は、予測処理のためのリアルタイムに取得される移動履歴データをバッファリングする(記憶する)。なお、予測処理のための移動履歴データとしては、学習処理時の移動履歴データよりも短い期間のデータ、例えば、100ステップ程度の移動履歴データがあれば十分である。バッファリング部31は、常に、所定期間分の最新の移動履歴データを記憶するようにし、新たなデータが取得されたとき、記憶されているデータのうち最も古いデータを消去する。
【0037】
予測プリプロセス部32は、学習プリプロセス部22と同様、センサデバイスから生じる課題を解決する。即ち、予測プリプロセス部32は、移動履歴データを整形するとともに、一時的なデータの欠落を補間処理等を行うことで補完する。
【0038】
予測メインプロセス部33は、現在地ノード推定部41と目的地経由地予測部42により構成される。予測メインプロセス部33には、ユーザ別モデルパラメータ記憶部12から、学習ブロック11の学習により得られた、ユーザ活動モデルを表すパラメータが供給される。
【0039】
現在地ノード推定部41は、予測プリプロセス部32から供給される移動履歴データと、学習ブロック11の学習により得られたユーザ活動モデルを用いて、ユーザの現在地に対応する状態ノード(現在地ノード)を推定する。状態ノードの推定には、ビタビ最尤推定や軟判定ビタビ推定を採用することができる。
【0040】
目的地経由地予測部42は、現在地ノード推定部41で推定された現在地ノードから遷移可能な複数の状態ノードでなるツリー構造において、目的地の状態ノード(目的地ノード)までのノード系列とその生起確率を算出する。なお、目的地の状態ノードへのノード系列(経路)には経由地のノードが含まれる場合もあるので、目的地経由地予測部42は、目的地と同時に経由地も予測する。
【0041】
予測ポストプロセス部34は、同一目的地までの複数の経路の選択確率(生起確率)の和を目的地への到達確率として求める。また、予測ポストプロセス部34は、目的地への経路のうち代表となる1以上の経路(以下、代表経路という。)を選択し、代表経路の所要時間を算出する。そして、予測ポストプロセス部34は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力する。なお、経路の生起確率の代わりに頻度、目的地への到達確率の代わりに到達頻度を、予測結果として出力してもよい。
【0042】
[予測システムのハードウエア構成例]
以上のように構成される予測システム1は、例えば、図2に示されるハードウエア構成を採用することができる。即ち、図2は、予測システム1のハードウエア構成例を示すブロック図である。
【0043】
図2において、予測システム1は、3台のモバイル端末51−1乃至51−3とサーバ52とにより構成されている。モバイル端末51−1乃至51−3は、同一機能を有する同型のモバイル端末51であるが、モバイル端末51−1乃至51−3では、それを所有するユーザが異なる。従って、図2では、3台のモバイル端末51−1乃至51−3のみが示されているが、実際には、ユーザ数に応じた数のモバイル端末51が存在する。
【0044】
モバイル端末51は、無線通信及びインターネット等のネットワークを介した通信により、サーバ52とデータの授受を行うことができる。サーバ52は、モバイル端末51から送信されてくるデータを受信し、受信したデータに対し所定の処理を行う。そして、サーバ52は、データ処理の処理結果を無線通信等によりモバイル端末51に送信する。
【0045】
従って、モバイル端末51とサーバ52は、無線または有線による通信を行う通信部を少なくとも有する。
【0046】
さらに、モバイル端末51が、図1の予測ブロック13を備え、サーバ52が、図1の学習ブロック11とユーザ別モデルパラメータ記憶部12を備える構成を採用することができる。
【0047】
この構成が採用される場合、例えば、学習処理において、モバイル端末51のセンサデバイスにより取得された移動履歴データがサーバ52に送信される。サーバ52は、受信した学習用の移動履歴データに基づき、ユーザ活動モデルを学習し、記憶する。そして、予測処理において、モバイル端末51が、学習により得られたユーザ活動モデルのパラメータを取得し、リアルタイムに取得される移動履歴データから、ユーザの現在地ノードを推定し、さらに、目的地ノードと、そこまでの到達確率、代表経路、および所要時間を算出する。そして、モバイル端末51は、予測結果を図示せぬ液晶ディスプレイ等の表示部に表示する。
【0048】
以上のようなモバイル端末51とサーバ52との間の役割分担は、それぞれのデータ処理装置としての処理能力や通信環境に応じて、適宜、決定することができる。
【0049】
学習処理は、処理に要する1回あたりの時間は非常に長いが、それほど頻繁に処理する必要はない。従って、一般的には、携行可能なモバイル端末51よりもサーバ52の方が処理能力が高いので、サーバ52に、一日に一回程度蓄積された移動履歴データに基づいて学習処理(パラメータの更新)を行わせるようにすることができる。
【0050】
一方、予測処理は、時々刻々とリアルタイムに更新される移動履歴データに対応させて迅速に処理し、表示することが望ましいので、モバイル端末51で処理を行う方が望ましい。通信環境がリッチであれば、サーバ52に予測処理も行わせ、予測結果のみをサーバ52から受信する方が、携行可能な小型化が要求されるモバイル端末51の負荷が軽減され、望ましい。
【0051】
また、モバイル端末51単独で、データ処理装置として学習処理および予測処理を高速に行うことが可能である場合には、図1の予測システム1の構成すべてをモバイル端末51が備えるようにすることも勿論可能である。
【0052】
[入力される移動履歴データの例]
図3は、予測システム1で取得された移動履歴データの例を示している。図3において、横軸は経度を表し、縦軸は緯度を表している。
【0053】
図3に示される移動履歴データは、実験者の1ヶ月半程度の期間に蓄積された移動履歴データを示している。図3に示されるように、移動履歴データは、主に、自宅周辺と、勤務先などの4か所の外出先を移動したデータとなっている。なお、この移動履歴データには、人工衛星を捕捉できず、位置が飛んでいるデータも含まれている。
【0054】
[エルゴディックHMMについて]
次に、予測システム1が、学習モデルとして採用するエルゴディックHMMについて説明する。
【0055】
図4は、HMMの例を示している。
【0056】
HMMは、状態ノードと状態ノード間遷移とを有する状態遷移モデルである。
【0057】
図4は、3状態のHMMの例を示している。
【0058】
図4において(以降の図においても同様)、丸印は、状態ノードを表し、矢印は、状態ノードの遷移を表す。なお、以下において、状態ノードは、単に、ノードまたは状態ともいう。
【0059】
また、図4において、si(図4では、i=1,2,3)は、状態を表し、aijは、状態siから状態sjへの状態遷移確率を表す。さらに、bj(x)は、状態sjへの状態遷移時に、観測値xが観測される出力確率密度関数を表し、πiは、状態siが初期状態である初期確率を表す。
【0060】
なお、出力確率密度関数bj(x)としては、例えば、正規確率分布等が用いられる。
【0061】
ここで、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の状態数を表す。
【0062】
HMMのパラメータλを推定する方法としては、Baum-Welchの最尤推定法が広く利用されている。Baum-Welchの最尤推定法は、EMアルゴリズム(EM(Expectation-Maximization) algorithm)に基づくパラメータの推定方法である。
【0063】
Baum-Welchの最尤推定法によれば、観測される時系列データx=x1,x2,・・・,xTに基づき、その時系列データが観測(生起)される確率である生起確率から求まる尤度を最大化するように、HMMのパラメータλの推定が行われる。ここで、xtは、時刻tに観測される信号(サンプル値)を表し、Tは、時系列データの長さ(サンプル数)を表す。
【0064】
Baum-Welchの最尤推定法については、例えば、“パターン認識と機械学習(下)”,C.M.ビショップ著,P. 333(英語原書:“Pattern Recognition and Machine Learning (Information Science and Statistics) ”,Christopher M. BishopSpringer, New York, 2006.)(以下、文献Aと称する)に記載されている。
【0065】
なお、Baum-Welchの最尤推定法は、尤度最大化に基づくパラメータ推定方法ではあるが、最適性を保証するものではなく、HMMの構造やパラメータλの初期値によっては、局所解(ローカルミニマム)に収束することがある。
【0066】
HMMは、音声認識で広く利用されているが、音声認識で利用されるHMMでは、一般に、状態の数や状態遷移の仕方等はあらかじめ決定される。
【0067】
図5は、音声認識で利用されるHMMの例を示している。
【0068】
図5のHMMは、left-to-right型と呼ばれる。
【0069】
図5では、状態数は3になっており、状態遷移は、自己遷移(状態siから状態siへの状態遷移)と、左から右隣の状態への状態遷移とのみを許す構造に制約されている。
【0070】
図5のHMMのように、状態遷移に制約があるHMMに対して、図4に示した、状態遷移に制約がないHMM、すなわち、任意の状態siから任意の状態sjへの状態遷移が可能なHMMは、エルゴディック(Ergodic)HMMと呼ばれる。
【0071】
エルゴディックHMMは、構造としては最も自由度の高いHMMであるが、状態数が多くなると、パラメータλの推定が困難となる。
【0072】
例えば、エルゴディックHMMの状態数が、1000である場合、状態遷移の数は、100万(=1000×1000)となる。
【0073】
したがって、この場合、パラメータλのうちの、例えば、状態遷移確率aijについては、100万個の状態遷移確率aijを推定することが必要となる。
【0074】
そこで、状態に対して設定する状態遷移には、例えば、スパース(Sparse)な構造であるという制約(スパース制約)をかけることができる。
【0075】
ここで、スパースな構造とは、任意の状態から任意の状態への状態遷移が可能なエルゴディックHMMのような密な状態遷移ではなく、ある状態から状態遷移することができる状態が非常に限定されている構造である。なお、ここでは、スパースな構造であっても、他の状態への状態遷移は、少なくとも1つ存在し、また、自己遷移は存在することとする。
【0076】
図6は、スパース制約を与えたHMMを示している。
【0077】
ここで、図6では、2つの状態を結ぶ双方向の矢印は、その2つの状態の一方から他方への状態遷移と、他方から一方への状態遷移とを表す。また、図6において、各状態は、自己遷移が可能であり、その自己遷移を表す矢印の図示は、省略されている。
【0078】
図6では、16個の状態が、2次元空間上に格子状に配置されている。すなわち、図6では、横方向に、4個の状態が配置され、縦方向にも、4個の状態が配置されている。
【0079】
いま、横方向に隣接する状態どうしの距離、及び、縦方向に隣接する状態どうしの距離を、いずれも1とすると、図6Aは、距離が1以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【0080】
また、図6Bは、距離が√2以下の状態への状態遷移は可能とし、他の状態への状態遷移はできないというスパース制約を与えたHMMを示している。
【0081】
図1の例では、予測システム1に、移動履歴データx=x1,x2,・・・,xTが供給され、学習ブロック11は、移動履歴データx=x1,x2,・・・,xTを用い、ユーザ活動モデルを表すHMMのパラメータλを推定する。
【0082】
即ち、ユーザの移動軌跡を表す各時刻の位置(緯度経度)のデータが、HMMの状態siのいずれかに対応する地図上の一点から、所定の分散値の広がりを持って正規分布した確率変数の観測データであると考える。学習ブロック11は、各状態siに対応する地図上の一点(中心値μi)とその分散値σi、および状態遷移確率aijを最適化する。
【0083】
なお、状態siの初期確率πiは、一様な値に設定することができる。例えば、M個の状態siそれぞれの初期確率πiが、1/Mに設定される。
【0084】
現在地ノード推定部41は、学習により得られたユーザ活動モデル(HMM)に対して、ビタビアルゴリズムを適用し、移動履歴データx=x1,x2,・・・,xTが観測される尤度を最も大にする状態遷移の過程(状態の系列)(パス)(以下、最尤パスともいう)を求める。これにより、ユーザの現在地に対応する状態siが認識される。
【0085】
ここで、ビタビアルゴリズムとは、各状態siを始点とする状態遷移のパスの中で、時刻tに、状態siから状態sjに状態遷移する状態遷移確率aijと、その状態遷移において、移動履歴データx=x1,x2,・・・,xTのうちの時刻tのサンプル値xtが観測される確率(出力確率密度関数bj(x)から求められる出力確率)とを、処理後時系列データxの長さTに亘って累積した値(生起確率)を最大にするパス(最尤パス)を決定するアルゴリズムである。ビタビアルゴリズムの詳細については上述の文献AのP.347に記載されている。
【0086】
[学習プリプロセス部22の構成例]
図7は、学習ブロック11の学習プリプロセス部22の詳細構成例を示すブロック図である。
【0087】
学習プリプロセス部22は、データ接続分割部71、データ異常除去部72、再サンプリング処理部73、移動属性識別付与部74、および滞在状態加工部75により構成される。
【0088】
データ接続分割部71は、移動履歴データの接続および分割の処理を行う。データ接続分割部71には、移動履歴データが、センサデバイスから、1日単位などの所定の単位でログファイルとして供給される。従って、本来、ある目的地への移動途中で連続すべき移動履歴データが、日付を跨いだために分割されて取得されることがある。データ接続分割部71は、そのような分割された移動履歴データを接続する。具体的には、データ接続分割部71は、1つのログファイル内の最後の3次元(緯度、経度、時刻)データと、そのログファイルの次に作成されたログファイル内の最初の3次元データの時間差が所定の時間内であれば、それらのファイル内の移動履歴データを接続する。
【0089】
また、例えば、GPSセンサは、トンネルや地下では人工衛星を捕捉することができないため、移動履歴データの取得間隔が長くなることがある。移動履歴データが長い時間欠落している場合には、ユーザがどこにいたかを推定することが難しくなる。そこで、データ接続分割部71は、取得された移動履歴データにおいて、前後の取得時刻の間隔が所定の時間間隔(以下、欠落閾値時間という。)以上ある場合に、その間隔の前後で移動履歴データを分割する。ここで、欠落閾値時間は、例えば、5分、10分、1時間などである。
【0090】
データ異常除去部72は、移動履歴データの明らかな異常を除去する処理を行う。例えば、ある時刻の位置のデータが、その前後の位置と100m以上も離れていて、跳躍している場合、その位置のデータは異常である。そこで、データ異常除去部72は、ある時刻の位置のデータが、その前後の両方の位置と所定の距離以上離れている場合、その3次元データを移動履歴データから除去する。
【0091】
再サンプリング処理部73は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを、線形補間等により補完する処理を行う。即ち、取得時刻の時間間隔が欠落閾値時間以上である場合には、データ接続分割部71により、移動履歴データが分割されるが、欠落閾値時間未満のデータの欠落は残っている。そこで、再サンプリング処理部73は、取得時刻の時間間隔が欠落閾値時間未満の欠落データを補完する。
【0092】
移動属性識別付与部74は、移動履歴の3次元データそれぞれが、同一場所に滞在(停止)している”滞在状態”か、または、移動している”移動状態”のいずれであるかの移動属性を識別し、付与する。これにより、移動履歴データの各3次元データに移動属性が付与された、移動属性付き移動履歴データが生成される。
【0093】
滞在状態加工部75は、移動属性識別付与部74から供給される移動属性付き移動履歴データに基づいて、移動属性が”滞在状態”の3次元データを加工する。より具体的には、滞在状態加工部75は、”滞在状態”の移動属性が所定時間(以下、滞在閾値時間という。)以上継続している場合、その前後で移動履歴データを分割する。また、滞在状態加工部75は、”滞在状態”の移動属性が滞在閾値時間未満で継続している場合には、その滞在閾値時間以内の所定時間続く、”滞在状態”の複数の3次元データの位置のデータをホールドする(同一位置のデータに修正する)。これにより、同一の目的地や経由地の移動履歴データに対して複数の”滞在状態”ノードが割り当てられることを防止することができる。換言すれば、同一の目的地や経由地を複数のノードで表現することを防止することができる。
【0094】
[学習プリプロセス部22の処理]
図8は、学習プリプロセス部22の学習プリプロセス処理を概念的に示したイメージ図である。
【0095】
図8上段に示される、再サンプリング処理部73によるデータ補完後の移動履歴データ81に対して、移動属性識別付与部74が、”滞在状態”または”移動状態”の移動属性を識別し、付与する。その結果、図8中段に示される、移動属性付き移動履歴データ82が生成される。
【0096】
図8中段の移動属性付き移動履歴データ82において、”m”および”m”は、”移動状態”の移動属性を表し、”u”は、”滞在状態”の移動属性を表す。なお、”m”と”m”は、同じ”移動状態”でも、移動手段(車、バス、電車、徒歩など)が異なる。
【0097】
そして、図8中段の、移動属性付き移動履歴データ82に対して、滞在状態加工部75により、移動履歴データを分割およびホールドする処理が実行され、図8下段の、移動属性付き移動履歴データ83(83Aおよび83B)が生成される。
【0098】
移動属性付き移動履歴データ83では、移動属性付き移動履歴データ82において2回目に発生した”移動状態”の箇所(3次元データ)で分割処理が行われ、移動属性付き移動履歴データ83Aと83Bに分割されている。
【0099】
分割処理では、最初に、移動属性付き移動履歴データ82の2回目に発生した”移動状態”までと、それ以降の複数の3次元データとで分割され、2つの移動属性付き移動履歴データ83Aおよび83Bとされる。次に、分割後の移動属性付き移動履歴データ83Aおよび83Bのうち、時間的に早い移動属性付き移動履歴データ83Aの最後の滞在閾値時間以上の複数の”移動状態”の3次元データが、1つの”滞在状態”の3次元データにまとめられる。これにより、不要な移動履歴データが削除されるので、学習時間を短縮することができる。
【0100】
なお、図8の例では、移動属性付き移動履歴データ82の3回目に発生した” 複数の移動状態”の3次元データも滞在閾値時間以上の”移動状態”が続くデータであり、同様の分割処理が行われている。しかし、分割後の後ろの3次元データが存在しないため、滞在閾値時間以上の複数の”移動状態”の3次元データが、1つの”滞在状態”の3次元データにまとめられるのみとなっている。
【0101】
一方、移動属性付き移動履歴データ83Aのうち、1回目の”移動状態”の移動履歴データでは、ホールド処理が実行されている。ホールド処理後は、3つの”移動状態”の3次元データ{(tk−1,xk−1,yk−1),(t,x,y),(tk+1,xk+1,yk+1)}が、{(tk−1,xk−1,yk−1),(t,xk−1,yk−1),(tk+1,xk−1,yk−1)}となっている。即ち、位置のデータが”移動状態”の最初の位置のデータに修正されている。なお、ホールド処理では、位置のデータは、”移動状態”の最初の位置のデータに変更するのではなく、位置の平均値、”移動状態”の期間の真ん中の時刻の位置のデータ等に変更してもよい。
【0102】
[移動属性識別付与部74の構成例]
図9は、移動属性識別付与部74の詳細構成例を示すブロック図である。
【0103】
移動属性識別付与部74は、移動速度演算部91、移動属性識別部92、および移動属性付与部93により構成される。
【0104】
移動速度演算部91は、供給される移動履歴データから移動速度を演算する。
【0105】
具体的には、一定の時間間隔でkステップ目(k個目)に得られるときの3次元データを、時刻t、経度y、緯度xと表すと、kステップ目のx方向の移動速度vxおよびy方向の移動速度vyは、次式(1)により計算することができる。
【0106】
【数1】

【0107】
式(1)では、緯度経度のデータをそのまま利用しているが、緯度経度を距離に変換したり、速度を時速や分速で表すように変換するなどの処理は、必要に応じて適宜行うことができる。
【0108】
また、移動速度演算部91は、式(1)で得られる移動速度vxおよびvyからさらに、式(2)で表されるkステップ目の移動速度vと進行方向の変化θを求め、これを利用することができる。
【0109】
【数2】

【0110】
式(2)で表される移動速度vと進行方向の変化θを利用する方が、式(1)の移動速度vxおよびvyよりも以下の点で、特徴をうまく取り出すことができる。
【0111】
1.移動速度vxおよびvyのデータの分布は、緯度経度軸に対して偏りが生じるため、同じ移動手段(電車や徒歩など)であっても角度が異なった場合に識別できない可能性があるが、移動速度vであればそのような可能性が少ない。
2.移動速度の絶対的な大きさ(|v|)だけで学習すると、機器のノイズによって生じる|v|のため、徒歩と滞在を区別できない。進行方向の変化も考慮することで、ノイズの影響を軽減することができる。
3.移動している場合は進行方向の変化が少ないが、滞在している場合は進行方向が定まらないので、進行方向の変化を使うと移動と滞在の識別がしやすい。
【0112】
以上の理由から、本実施の形態では、移動速度演算部91は、移動速度のデータとして、式(2)で表される移動速度vと進行方向の変化θを求め、移動属性識別部92に供給する。
【0113】
移動速度演算部91は、移動速度vと進行方向の変化θの演算を行う前に、ノイズ成分を除去するため、移動平均によるフィルタリング処理(前処理)を行うことができる。
【0114】
なお、センサデバイスのなかには、移動速度を出力できるものも存在する。そのようなセンサデバイスが採用されている場合、移動速度演算部91を省略し、センサデバイスが出力する移動速度をそのまま利用することができる。以下では、進行方向の変化θを、進行方向θと略記する。
【0115】
移動属性識別部92は、供給される移動速度に基づいて移動属性を識別し、認識結果を移動属性付与部93に供給する。より具体的には、移動属性識別部92は、ユーザの行動状態(移動状態)を確率的状態遷移モデル(HMM)として学習し、学習により得られた確率的状態遷移モデルを用いて移動属性を識別する。移動属性としては、少なくとも”滞在状態”と”移動状態”が存在する必要がある。本実施の形態では、図11等を参照して後述するように、移動属性識別部92は、”移動状態”を、さらに徒歩、自転車、車など、複数の移動手段によって分類した移動属性を出力する。
【0116】
移動属性付与部93は、再サンプリング処理部73からの、移動履歴データを構成する3次元データそれぞれに対し、移動属性識別部92で認識された移動属性を付与し、移動属性付き移動履歴データを生成して、滞在状態加工部75に出力する。
【0117】
次に、図10乃至図17を参照して、移動属性識別部92で使用される、ユーザの行動状態を表した確率的状態遷移モデルのパラメータの求め方について説明する。
【0118】
[移動属性識別部92の学習器の第1の構成例]
図10は、カテゴリHMMにより、移動属性識別部92で使用される確率的状態遷移モデルのパラメータを学習する学習器100Aの構成例を示している。
【0119】
カテゴリHMMでは、学習する教師データが予めどのカテゴリ(クラス)に属するデータであるのかが既知であり、カテゴリごとにHMMのパラメータが学習される。
【0120】
学習器100Aは、移動速度データ記憶部101、行動状態ラベリング部102、および行動状態学習部103により構成される。
【0121】
移動速度データ記憶部101は、学習用データとしての移動速度の時系列データを記憶する。
【0122】
行動状態ラベリング部102は、移動速度データ記憶部101から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル(カテゴリ)として付与する。行動状態ラベリング部102は、移動速度のデータに行動状態が対応付けられたラベル済み移動速度データを行動状態学習部103に供給する。例えば、kステップ目の移動速度vと進行方向θに対して、行動状態を表すラベルMを付与したデータが行動状態学習部103に供給される。
【0123】
行動状態学習部103は、行動状態ラベリング部102から供給されるラベル済み移動速度データを、カテゴリごとに分類し、カテゴリ単位で、ユーザ活動モデル(HMM)のパラメータを学習する。学習の結果得られたカテゴリ毎のパラメータは移動属性識別部92に供給される。
【0124】
[行動状態の分類例]
図11は、行動状態をカテゴリごとに分類する場合の分類例を示している。
【0125】
図11に示されるように、まず、ユーザの行動状態は、滞在状態と移動状態に分類することができる。本実施の形態では、移動属性識別部92が認識するユーザの行動状態としては、上述したように、少なくとも滞在状態と移動状態が存在する必要があるので、この2つに分類することは必須である。
【0126】
さらに、移動状態は、移動手段によって、電車、車(バスなども含む)、自転車、徒歩に分類することができる。電車は、さらに、特急、快速、ローカルなどに分類することができ、車は、さらに、高速、一般道などに分類することができる。また、徒歩は、走る、普通、散歩などに分類することができる。
【0127】
本実施の形態では、ユーザの行動状態を、図11において斜線で示される“滞在”、“電車(快速)”、“電車(ローカル)”、“車(高速)”、“車(一般道)”、“自転車”、および“徒歩”に分類することとする。なお、“電車(特急)”は、学習用データが得られなかったため省略した。
【0128】
なお、カテゴリの分類の仕方が図11に示した例に限定されるものではないことは言うまでもない。また、移動手段による移動速度の変化はユーザによって大きく異なるものではないので、学習用データとしての移動速度の時系列データは、認識対象のユーザのものである必要はない。
【0129】
[行動状態ラベリング部102の処理例]
次に、図12および図13を参照して、行動状態ラベリング部102の処理例について説明する。
【0130】
図12は、行動状態ラベリング部102に供給される移動速度の時系列データの例を示している。
【0131】
図12では、行動状態ラベリング部102から供給される移動速度のデータ(v,θ)を、(t,v)および(t,θ)の形で示している。図12において、四角(■)のプロットは移動速度vを表し、丸(●)のプロットは進行方向θを表している。また、横軸は時間tを表し、右側の縦軸は進行方向θを、左側の縦軸は移動速度vを表す。
【0132】
図12の時間軸の下方に示されている“電車(ローカル)”、“徒歩”、“滞在”の文字は、説明のため付加したものである。図12の時系列データの最初は、ユーザが電車(ローカル)で移動中である場合の移動速度のデータであり、次が“徒歩”で移動中である場合、その次が“滞在”である場合の移動速度のデータとなっている。
【0133】
ユーザが“電車(ローカル)”で移動している場合、電車が駅で停車し、出発するとき加速し、再度減速して駅に停車することを繰り返すので、移動速度vのプロットが繰り返し上下に振れるという特徴が表れている。なお、電車が停止している場合でも移動速度が0になっていないのは、移動平均によるフィルタリング処理を行っているためである。
【0134】
また、ユーザが“徒歩”で移動している場合と“滞在”している場合は、最も区別しにくい状態であるが、移動平均によるフィルタリング処理により、移動速度vに明らかな違いが見られる。また、“滞在”では、進行方向θが瞬時に大きく変化する特徴がみられ、“徒歩”との差別化が容易であることがわかる。このように、移動平均によるフィルタリング処理、および、ユーザの移動を移動速度vと進行方向θで表すことにより、“徒歩”と“滞在”の区別が容易になっていることがわかる。
【0135】
なお、“電車(ローカル)”と“徒歩”の間の部分は、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分である。
【0136】
図13は、図12に示した時系列データに対して、ラベル付けを行う例を示している。
【0137】
例えば、行動状態ラベリング部102は、図12に示した移動速度のデータをディスプレイに表示する。そして、ユーザは、ディスプレイに表示された移動速度のデータのうち、ラベル付けをしたい部分を矩形の領域で囲む操作を、マウスなどにより行う。また、ユーザは、指定したデータに対して付与するラベルをキーボードなどから入力する。行動状態ラベリング部102は、ユーザによって指定された矩形領域に含まれる移動速度のデータに、入力されたラベルを付与することにより、ラベル付けを行う。
【0138】
図13では、“徒歩”に相当する部分の移動速度のデータを矩形の領域で指示した例が示されている。なお、このとき、フィルタリング処理のため、行動の切り替わり点がはっきりしない部分については、指示する領域に含めないようにすることができる。時系列データの長さは、行動の違いが時系列データに明確に出る長さから決める。例えば、20ステップ(15秒×20ステップ=300秒)程度とすることができる。
【0139】
[行動状態学習部103の構成例]
図14は、図10の行動状態学習部103の構成例を示すブロック図である。
【0140】
行動状態学習部103は、分類部121とHMM学習部122乃至122により構成される。
【0141】
分類部121は、行動状態ラベリング部102から供給されるラベル済み移動速度データのラベルを参照し、ラベルに対応するHMM学習部122乃至122のいずれかに供給する。即ち、行動状態学習部103では、ラベル(カテゴリ)ごとにHMM学習部122が用意されており、行動状態ラベリング部102から供給されるラベル済み移動速度データが、ラベルごとに分類されて、供給される。
【0142】
HMM学習部122乃至122それぞれは、供給されるラベル済み移動速度データを用いて、学習モデル(HMM)を学習する。そして、HMM学習部122乃至122それぞれは、学習により得られるHMMのパラメータλを、図9の移動属性識別部92に供給する。
【0143】
HMM学習部122は、ラベルが“滞在”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“徒歩”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“自転車”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“電車(ローカル)”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“車(一般道)”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“電車(快速)”である場合の、学習モデル(HMM)を学習する。HMM学習部122は、ラベルが“車(高速)”である場合の、学習モデル(HMM)を学習する。
【0144】
[移動属性識別部92の第1の構成例]
図15は、学習器100Aで学習されたパラメータを利用する場合の移動属性識別部92である、移動属性識別部92Aの構成例を示すブロック図である。
【0145】
移動属性識別部92Aは、尤度計算部141乃至141と尤度比較部142とにより構成されている。
【0146】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91(図9)から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“滞在”である尤度を計算する。
【0147】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“徒歩”である尤度を計算する。
【0148】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“自転車”である尤度を計算する。
【0149】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“電車(ローカル)”である尤度を計算する。
【0150】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“車(一般道)”である尤度を計算する。
【0151】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“電車(快速)”である尤度を計算する。
【0152】
尤度計算部141は、HMM学習部122の学習により得られたパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データに対する尤度を計算する。即ち、尤度計算部141は、行動状態が“車(高速)”である尤度を計算する。
【0153】
尤度比較部142は、尤度計算部141乃至141それぞれから供給される尤度を比較し、尤度の最も高い行動状態を選択し、移動属性として出力する。
【0154】
[移動属性識別部92の学習器の第2の構成例]
図16は、マルチストリームHMMにより、移動属性識別部92で使用されるユーザ活動モデルのパラメータを学習する学習器100Bの構成例を示している。
【0155】
学習器100Bは、移動速度データ記憶部101、行動状態ラベリング部161、および行動状態学習部162により構成される。
【0156】
行動状態ラベリング部161は、移動速度データ記憶部101から時系列に順次供給される移動速度のデータに対し、ユーザの行動状態をラベル(行動モード)として付与する。行動状態ラベリング部161は、移動速度の時系列データ(v,θ)と、それと関連付けられた行動モードMの時系列データを行動状態学習部162に供給する。
【0157】
行動状態学習部162は、マルチストリームHMMにより、ユーザの行動状態を学習する。
【0158】
ここで、マルチストリームHMMは、通常のHMMと同様な遷移確率を有する状態ノードから、複数の異なる確率法則に従うデータが出力されるようなHMMである。マルチストリームHMMでは、パラメータλのうち、出力確率密度関数bj(x)が時系列データごとに別々に用意される。マルチストリームHMMでは、異なる種類の時系列データ(ストリーム)を関連付けながら学習することができる。
【0159】
行動状態学習部162には、連続量である移動速度vと進行方向θの時系列データと、離散量である行動モードMの時系列データが供給される。行動状態学習部162は、各状態ノードから出力される移動速度の分布パラメータと、行動モードの確率を学習する。学習により得られたマルチストリームHMMによれば、例えば、移動速度の時系列データから、現在の状態ノードが求められる。そして、求められた状態ノードから、行動モードを認識することができる。
【0160】
カテゴリHMMを用いた第1の構成例では、HMMをカテゴリごとに7個用意する必要があるが、マルチストリームHMMでは1個のHMMで十分である。ただし、状態ノードの数は、第1の構成例において7個のカテゴリで使用された状態ノードの総数と同程度用意する必要がある。
【0161】
[移動属性識別部92の第2の構成例]
図17は、学習器100Bで学習されたパラメータを利用する場合の移動属性識別部92である、移動属性識別部92Bの構成例を示すブロック図である。
【0162】
移動属性識別部92Bは、状態ノード認識部181と行動モード認識部182により構成される。
【0163】
状態ノード認識部181は、学習器100Bで学習されたマルチストリームHMMのパラメータを用いて、移動速度演算部91から供給される移動速度の時系列データから、マルチストリームHMMの状態ノードを認識する。状態ノード認識部181は、認識された現在の状態ノードのノード番号を行動モード認識部182に供給する。
【0164】
行動モード認識部182は、状態ノード認識部181で認識された状態ノードで、最も確率の高い行動モードを、移動属性として出力する。
【0165】
[学習プリプロセス部22の処理]
図18は、学習プリプロセス部22による学習プリプロセス処理のフローチャートである。
【0166】
学習プリプロセス処理では、最初に、ステップS1において、データ接続分割部71が、移動履歴データの接続および分割の処理を行う。
【0167】
ステップS2において、データ異常除去部72が、移動履歴データの明らかな異常を除去する処理を行う。
【0168】
ステップS3において、再サンプリング処理部73が、取得時刻の時間間隔が滞在閾値時間未満の欠落データを、線形補間等により補完する処理を行う。
【0169】
ステップS4において、移動属性識別付与部74が、移動履歴の3次元データそれぞれに対し、”滞在状態”かまたは”移動状態”の移動属性を識別し、付与する。
【0170】
ステップS5において、滞在状態加工部75が、移動属性識別付与部74から供給される属性付き移動履歴データに基づいて、移動属性が”滞在状態”の3次元データを加工する。そして、滞在状態加工部75は、加工処理後の、移動属性付き移動履歴データを学習メインプロセス部23に出力して、処理を終了する。
【0171】
以上のように、学習プリプロセス部22では、移動履歴データが、必要に応じて分割等された後、移動属性が付与されることにより、移動属性付き移動履歴データとされて、学習メインプロセス部23に供給される。
【0172】
[学習メインプロセス部23の詳細構成例]
図19は、学習ブロック11の学習メインプロセス部23の詳細構成例を示すブロック図である。
【0173】
学習メインプロセス部23は、既知未知判定部201、新規モデル生成部202、新規モデル結合部203、パラメータ更新部204、および更新モデル整理部205により構成される。
【0174】
学習プリプロセス部22(図1)から供給される移動履歴データが、既知未知判定部201に供給される。また、少なくとも1回以上、学習メインプロセス部23による学習が既に行われている場合、ユーザ別モデルパラメータ記憶部12(図1)から、先の学習により得られたユーザ活動モデルのパラメータが、既存モデルのパラメータとして取得される。既存モデルのパラメータは、既知未知判定部201、新規モデル結合部203、およびパラメータ更新部204に供給される。
【0175】
既知未知判定部201は、学習プリプロセス部22から供給された移動履歴データが既知の経路の移動履歴データであるか否か判定する。なお、2回目以降の学習では、供給された移動履歴データの一部が未知の経路の移動履歴データで、残りの一部が既知の経路の移動履歴データとなっていることもある。既知未知判定部201は、既知と判定された移動履歴データについては、移動履歴データの各3次元データが既存モデルのどの状態ノードに相当するか推定する。そして、既知未知判定部201は、既知の移動履歴データと、それに対応するノード系列データをパラメータ更新部204に供給する。
【0176】
一方、既知未知判定部201は、供給された移動履歴データが未知の経路の移動履歴データであると判定した場合、未知の経路の移動履歴データを新規モデル生成部202に供給する。また、未知の経路の移動履歴データが既知の経路の移動履歴データと接続されている場合、既知未知判定部201は、未知の経路の移動履歴データの接続先となる、前後の既知の移動履歴データに対応する既存モデルの状態ノードを新規モデル生成部202に供給する。なお、未知の移動履歴データの後の既存モデルの状態ノードが存在しない場合、例えば、既知の経路から未知の経路を通って未知の目的地へ到達し、戻ってくるような場合には、前の既存モデルの状態ノードのみが新規モデル生成部202に供給される。
【0177】
1回目の学習では、学習プリプロセス部22から供給された移動履歴データすべてが未知の移動履歴データとして新規モデル生成部202に供給される。また、1回目の学習では、前後の既存モデルの状態ノードは存在しないので、新規モデル生成部202への供給はない。
【0178】
新規モデル生成部202は、既知未知判定部201から供給された未知の移動履歴データを用いてユーザ活動モデルを学習する。即ち、新規モデル生成部202は、未知の移動履歴データを確率的状態遷移モデルでモデル化したときのパラメータを求め、新規モデル結合部203に供給する。ここで学習されたユーザ活動モデルが、先の学習により得られている既存モデルとは別の、新規モデルとなる。なお、1回目の学習と2回目以降の学習は、学習対象の未知の移動履歴データのデータ量が異なるのみであり、同一の学習により、ユーザ活動モデルのパラメータを求めることができる。
【0179】
新規モデル生成部202は、学習により得られた新規モデルのパラメータを、新規モデル結合部203に供給する。また、新規モデル生成部202は、前後の既存モデルの状態ノードが既知未知判定部201から供給された場合には、その前後の既存モデルの状態ノードも、新規モデル結合部203に供給する。
【0180】
新規モデル結合部203は、2回目以降の学習において、未知の移動履歴データに基づいて、先の学習により得られている既存モデルを更新する。即ち、新規モデル結合部203は、未知の移動履歴データの前後の既存モデルの状態ノードに基づいて、既存モデルに、新規モデル生成部202からの新規モデルを結合し、更新後のユーザ活動モデルを生成する。新規モデル結合部203により更新されたユーザ活動モデルは、未知の移動履歴データに応じて状態ノードが追加されたトポロジー更新モデルである。
【0181】
なお、新規モデル結合部203において、新規モデル生成部202からの新規モデルと結合される既存モデルは、学習メインプロセス部23に供給された移動履歴データに既知の経路の移動履歴データが全く含まれていない場合には、ユーザ別モデルパラメータ記憶部12(図1)から取得された既存モデルとなる。一方、学習メインプロセス部23に供給された移動履歴データに既知の経路の移動履歴データが一部含まれている場合には、新規モデルと結合される既存モデルは、パラメータ更新部204で更新された既存モデルとなる。
【0182】
パラメータ更新部204は、既知の移動履歴データと、それに対応するノード系列データに基づいて、先の学習により得られている既存モデルを更新する。更新された既存モデルのパラメータは、新規モデル結合部203と更新モデル整理部205に出力される。パラメータ更新部204による更新では、上述したように状態ノードの追加はない。
【0183】
更新モデル整理部205は、新規モデル結合部203により更新されたトポロジー更新モデル、または、パラメータ更新部204により更新されたパラメータ更新モデルのなかで、自己遷移のみで、他の状態ノードからの遷移が無い状態ノードを消去し、更新モデルを整理する。整理後の更新モデルのパラメータが、学習(更新学習)により得られたユーザ活動モデルのパラメータとして、学習ポストプロセス部24とユーザ別モデルパラメータ記憶部12に供給される。
【0184】
次に、既知未知判定部201の詳細についてさらに説明する。
【0185】
[既知未知判定部201の詳細構成例]
図20は、既知未知判定部201の詳細な構成例を示すブロック図である。
【0186】
学習メインプロセス部23によって、少なくとも1回は学習処理が実行されている場合、既存モデルのパラメータがユーザ別モデルパラメータ記憶部12(図1)から既存モデル構築部221に供給される。既存モデル構築部221は、供給された既存モデルのパラメータに基づいて、既存モデルを構築し、未知状態ノード追加部222に供給する。
【0187】
なお、1回も学習処理が実行されていない状態においては、既存モデル構築部221には、既存モデルの初期パラメータが予め設定されている。既存モデルの初期パラメータは、ノード数が1で、その1個の状態ノードの遷移確率が自己遷移のみ、中心値が3次元データ(時刻、経度、緯度)の取り得る範囲外の値、分散値が分散最小値、ノード頻度が1に設定されている。少なくとも1回の学習処理が実行され、ユーザ別モデルパラメータ記憶部12(図1)から既存モデルのパラメータが供給されることで、既存モデルの初期パラメータが上書きされ、消去される。
【0188】
未知状態ノード追加部222は、既存モデル構築部221で構築された既存モデルに、未知の移動履歴データを引き受ける一つの状態ノード(以下、未知状態ノードと称する。)を追加する。これにより、既存モデルに1つの状態ノードが追加された学習モデル(以下、未知状態追加モデルと称する。)が構築され、状態ノード推定部223に供給される。
【0189】
状態ノード推定部223は、未知状態ノード追加部222から供給された未知状態追加モデルを用いたビタビアルゴリズムにより、供給された移動履歴データの各3次元データに対応する未知状態追加モデルの状態ノードを推定する。未知状態追加モデルには、未知の移動履歴データを引き受ける1つのノードが追加されているので、入力された移動履歴データが未知の移動履歴データであっても、ビタビ推定が破綻なく行われる。仮に、移動履歴データを引き受ける1つのノードが追加されていない場合には、未知の移動履歴データに対しては、対応する状態ノードが見つからず、ビタビ推定が破綻する。
【0190】
サンプル別尤度計算部224は、既知未知判定に用いる指標としての観測尤度の期待値を計算する。時刻tにおける観測尤度の期待値はL(t)で求められる。移動履歴データが既知の経路のデータである場合、観測尤度の期待値L(t)は大きくなり、移動履歴データが未知の経路のデータである場合、観測尤度の期待値L(t)は小さくなる。
【0191】
既知未知判定部226は、観測尤度の期待値L(t)の時系列データ(観測尤度系列データ)に対して、既知未知モデル記憶部225に記憶されている、既知未知の二状態モデルを用いたビタビ判定を行うことで、既知または未知の判定を行う。
【0192】
既知未知ポスト処理部227は、状態ノード推定部223が未知と推定した状態ノードで、既知未知判定部226が既知と判定したものを、未知に修正する。即ち、未知の判定は、状態ノード推定部223による推定結果が優先される。
【0193】
また、既知未知ポスト処理部227は、修正後の判定結果を参照して学習プリプロセス部22(図1)から供給される移動履歴データを、新規モデル生成部202またはパラメータ更新部204に出力する。即ち、既知未知ポスト処理部227は、判定結果が既知である移動履歴データを、それに対応するノード系列データとともにパラメータ更新部204(図19)に供給する。一方、既知未知ポスト処理部227は、判定結果が未知である移動履歴データを、新規モデル生成部202に供給する。未知の移動履歴データが既知の移動履歴データと接続されている場合には、既知未知ポスト処理部227は、未知の移動履歴データの接続先となる、前後の既知の移動履歴データに対応する既存モデルの状態ノードも新規モデル生成部202に供給する。
【0194】
[未知状態追加モデルの構築処理]
図21のフローチャートを参照して、未知状態ノード追加部222による未知状態追加モデルの構築処理について説明する。
【0195】
初めに、ステップS21において、未知状態ノード追加部222は、未知状態追加モデルの各状態ノードの初期確率を格納した、未知状態追加モデルの初期確率テーブルを生成する。
【0196】
初期確率テーブルは、図22に示すように、既存モデルのM個の状態ノードに未知の移動履歴データを引き受ける1個の状態ノードを追加した(M+1)行1列のテーブルで、各状態ノードの初期確率は、例えば、等確率の1/(M+1)に設定される。
【0197】
ステップS22において、未知状態ノード追加部222は、未知状態追加モデルの各状態ノードの遷移確率を格納した、未知状態追加モデルの遷移確率テーブルを生成する。
【0198】
遷移確率テーブルは、図23に示すように、(M+1)行(M+1)列のテーブルで構成される。遷移確率テーブルでは、第1行第1列乃至第M行第M列の既存モデルの各状態間の状態遷移確率aijに(1−eps)が乗算される。また、遷移確率テーブルの第(M+1)列の各要素には、一番下の(M+1)行を除いて、epsが設定され、第(M+1)行の各要素には、一番下の(M+1)行を除いて、epsが設定される。ここで、epsは、例えば、1.0E-8程度の、1より十分小さい所定の値であり、既存モデルの状態ノード間の遷移確率のどれよりも低い。この未知状態追加モデルでは、既存モデルの各状態ノードから未知状態ノードへの遷移確率がepsで、未知状態ノードから既存モデルの各状態ノードへの遷移確率もepsに設定されたことを表す。また、第(M+1)行第(M+1)列の要素は未知状態ノードの自己遷移確率を表し、(1−M×eps)である。図23の未知状態追加モデルでは、各行の総和が1となる。
【0199】
ステップS23において、未知状態ノード追加部222は、未知状態追加モデルの各状態ノードの観測確率の中心値μsi(d)を格納した、未知状態追加モデルの中心値テーブルを生成する。
【0200】
図24は、ステップS23で生成される未知状態追加モデルの中心値テーブルを示している。未知状態追加モデルの中心値テーブルの列数は、移動履歴データの次元数Dに対応し、行数は状態ノードの数に対応する。従って、本実施の形態では、未知状態追加モデルの中心値テーブルは、(M+1)行3列で構成される。そして、未知状態追加モデルの中心値テーブルは、既存モデルのM行D列の中心値テーブルに、第(M+1)行目として、未知状態ノードの中心値μsM+1(1)=E1,μsM+1(2)=E2,μsM+1(3)=E3の1行が追加された形となっている。
【0201】
ここで、E1,E2,E3それぞれには、任意の値を設定することができる。例えば、E1は、時刻の取り得る値(0時から24時)の中心値である「12」、E2およびE3は、緯度、経度の取り得る値(−180から180まで)の中心値である0とすることができる。また例えば、E1、E2、およびE3それぞれは、既存モデルのM個の中心値μs1(d)乃至μsM(d)の平均値とすることができる。
【0202】
ステップS24において、未知状態ノード追加部222は、未知状態追加モデルの各状態ノードの観測確率の分散値σsi(d)’2を格納した、未知状態追加モデルの分散値テーブルを生成する。
【0203】
図25は、ステップS24で生成される未知状態追加モデルの分散値テーブルを示している。未知状態追加モデルの分散値テーブルの列数は、移動履歴データの次元数Dに対応し、行数は状態ノードの数に対応する。従って、本実施の形態では、未知状態追加モデルの分散値テーブルは、(M+1)行3列で構成される。そして、未知状態追加モデルの分散値テーブルは、既存モデルのM行D列の分散値テーブルに、第(M+1)行目として、未知状態ノードの分散値σsM+1(1)=V1,σsM+1(2)=V2,σsM+1(3)=V3の1行が追加された形となっている。
【0204】
ここで、V1,V2,V3それぞれには、任意の値を設定することができるが大きい値であることが望ましい。例えば、V1は、0時から24時の取り得る範囲を網羅できるように、「12」の二乗より大きい値に設定する。V2およびV3は、−180から180までの緯度、経度の取り得る範囲を網羅できるように、180の二乗より大きい値に設定する。
【0205】
以上の処理により、未知状態追加モデルの各パラメータが設定され、未知状態追加モデルが構築される。
【0206】
[サンプル別尤度計算部224の観測尤度の計算]
次に、サンプル別尤度計算部224が行う観測尤度の計算について説明する。
【0207】
サンプル別尤度計算部224は、既知未知判定に用いる指標としての観測尤度の期待値L(t)を計算する。観測尤度の期待値L(t)は、次式(3)により計算することができる。
【数3】

【0208】
ここで、N(xt|μsi,σsi)は、状態ノードsiから観測データxtを観測する観測尤度を表す。観測データは(μsi,σsi)の正規分布に従う。また、δ(si,t)は、時刻tの観測データxtが状態ノードsiから出力された確率である。この確率δ(si,t)は、ビタビアルゴリズムを用いて算出されたものである。具体的には、確率δ(si,t)は、次の1)、2)の処理によって算出される。1)状態ノードsiに到達する一つ前の状態ノードsi-1のうち、ビタビ推定確率と観測尤度N(Xt|μsi,σsi)の積が最も大きい状態ノードが選択される。2)選択された一つ前の状態ノードsi-1のビタビ推定確率の観測尤度に比例するように、現在の状態ノードsiのビタビ推定確率が規格化される。1)は、現在までの移動履歴データを、モデルの遷移の制約を考慮しながらビタビアルゴリズムで最尤推定することを意味し、2)は、最尤推定で生き残った尤度を規格化することで、現在どの状態ノードにいるかの確率を算出していることを意味している。
【0209】
次式(3)により計算される観測尤度の期待値L(t)は、未知状態追加モデルが観測データを十分に説明できるのであれば大きくなる。一方、未知状態追加モデルが観測データを十分に説明できない場合と、観測データが未知状態ノードで説明される場合には、観測尤度の期待値L(t)は小さくなる。従って、観測尤度の期待値L(t)の大きさで、既知または未知の判定を行うことができる。なお、以下では、観測尤度の期待値L(t)を、単に、観測尤度L(t)と称する。
【0210】
[既知未知判定部226の既知未知判定処理]
次に、図26のフローチャートを参照して、サンプル別尤度計算部224で計算された観測尤度L(t)を用いて既知または未知の判定を行う、既知未知判定部226の既知未知判定処理について説明する。
【0211】
初めに、ステップS31において、既知未知判定部226は、ノード系列データに対応する観測尤度L(t)の時系列データを、サンプル別尤度計算部224から取得する。そして、既知未知判定部226は、観測尤度L(t)の時系列データのそれぞれを、対数尤度logL(t)に変換する。即ち、既知未知判定部226は、各時刻tの観測尤度L(t)の対数を計算する。
【0212】
ステップS32において、既知未知判定部226は、対数尤度logL(t)を飽和させた飽和対数尤度を求める処理を行う。具体的には、既知未知判定部226は、対数尤度logL(t)から、所定のオフセット(閾値)を減算して所定の値で除算した結果を、tanh関数に入力することで、対数尤度logL(t)を飽和させる。ステップS31およびS32の処理により、観測尤度L(t)が、−1から1までの範囲を取るパラメータに変換される。
【0213】
ステップS33において、既知未知判定部226は、既知と未知の二状態で構成されるHMMを用いてビタビ判定を行うことにより、飽和対数尤度に対し既知未知判定を行う。
【0214】
既知状態と未知状態の二状態で構成されるHMMは、次式(4)で表される。
【数4】

即ち、既知状態と未知状態の初期確率πはともに同確率(0.5)である。また、ユーザの移動履歴を考えた場合、既知状態と未知状態が頻繁に入れ替わることは考えにくく、既知の経路を移動している場合も未知の経路を移動している場合も切り替わった後はある程度連続して続くと考えられる。従って、遷移確率Aは、1より非常に小さいな所定の値をεとして、既知状態と未知状態のそれぞれで自己遷移する確率が大きくなるように設定される。観測確率としては、既知状態が1、未知状態が−1を中心に分布し、分散値として1が設定されている。
【0215】
図27と図28は、ある2つの観測尤度L(t)の時系列データに対して、図27の既知未知判定処理を行った結果を示している。
【0216】
図27および図28において、上段のグラフは、観測尤度L(t)の時系列データを対数尤度logL(t)に変換した結果を示し、中段のグラフは、対数尤度logL(t)を飽和させた飽和対数尤度を示し、下段のグラフは、既知未知判定結果を示している。既知未知判定結果は、”−1”が未知を表し、”1”が既知を表す。
【0217】
図27および図28を参照すると、仮に、対数尤度logL(t)を単純に所定の閾値と比較するようにした場合には、頻繁に既知と未知が入れ替わることがある。しかしながら、上述したように、ユーザの移動行動は通常ある意図をもってなされるため、既知状態と未知状態が頻繁に入れ替わることは考えにくい。
【0218】
そこで、既知状態と未知状態のそれぞれで自己遷移する確率が大きくなるように設定した二状態の隠れマルコフモデルにより判定することで、下段の既知未知判定結果が示すように、適切なタイミングで既知未知が切り替わるようにすることができる。飽和対数尤度の計算結果を見ると、図27では、短時間だけ既知状態が発生したり、図28では、チャタリングが発生したりしているが、既知未知判定結果は、安定した既知または未知の状態が得られている。従って、図27の既知未知判定処理により、観測尤度L(t)の時系列データに対して、安定した既知未知の判定ができている。
【0219】
なお、既知未知の判定の方法は、観測尤度L(t)の時系列データに基づいて、既知または未知の2値に弁別することができればよいので、上記の方法に限られない。例えば、観測尤度L(t)の時系列データに、ローパスフィルタを施し、既知または未知に2値化するような方法でもよい。
【0220】
また、上述のビタビ推定やローパスフィルタを使った既知未知判定では、状態ノード推定部223において未知と推定された状態ノードが既知と判定されることが稀にある。このような場合は、次の(1)か(2)のいずれかの方法を採用することができる。(1)状態ノードの推定結果(即ち、未知)を、上述の既知未知判定の判定結果よりも優先する。(2)未知の推定結果の状態ノードが出現する前または後の状態ノードの推定結果(即ち、既知)で置き換える。ここで、置き換える元となる状態ノードは、未知の推定結果の状態ノードが出現する前または後のいずれか一方に予め決定しておいてもよいし、前または後ろの状態ノードのうち、観測尤度の大きい方の状態ノードとするようにしてもよい。(1)では、推定結果を優先し、判定結果を未知に修正することになり、(2)では、判定結果を優先し、推定結果を既知に修正することになる。
【0221】
次に、新規モデル生成部202の詳細について説明する。
【0222】
[新規モデル生成部202の詳細構成例]
図29は、新規モデル生成部202の詳細な構成例を示すブロック図である。
【0223】
新規モデル生成部202は、新規モデル初期化部241、新規モデル制約部242、新規モデル学習部243、ノード系列判定部244、パラメータ再計算部245、および新規モデル整理部246により構成される。
【0224】
新規モデル生成部202には、既知未知判定部201から、未知の移動履歴データが供給される。また、未知の移動履歴データが既知の移動履歴データと接続されている場合には、未知の移動履歴データの前後の既存モデルの状態ノードも供給される。既知未知判定部201から供給される未知の移動履歴データと前後の既存モデルの状態ノードは、新規モデル生成部202の各部が必要に応じて取得することができる。
【0225】
新規モデル初期化部241は、供給された未知の移動履歴データのサンプル数と同数の状態ノード数のHMMを、新規モデルとして宣言する(メモリ確保して生成する)。
【0226】
新規モデル制約部242は、新規モデル初期化部241で宣言した新規モデルに、left-to-rightの制約を設定する。これは、一回の移動行動は、強い一方向性の制約があること、また、仮に移動方向に一方向性がなくても、時間は常に一方向性があることによる。
【0227】
新規モデル学習部243は、未知の移動履歴データを用いて新規モデルを学習する。即ち、新規モデル学習部243は、既知未知判定部201から供給された未知の移動履歴データを用いて、新規モデルを表すleft-to-rightの制約が与えられたHMMのパラメータを求める。
【0228】
ノード系列判定部244は、新規モデル学習部243の学習により得られた新規モデルを用いて、未知の移動履歴データの3次元データそれぞれを、新規モデルの状態ノードsiに変換したノード系列データを生成し、パラメータ再計算部245に供給する。具体的には、ノード系列判定部244は、新規モデル学習部243から供給されたパラメータに基づく新規モデルから、入力されたユーザの時刻、緯度、および経度に対応するユーザの現在の状態ノードsiを認識する処理を、未知の移動履歴データの最初のステップから最後のステップまで繰り返す。
【0229】
パラメータ再計算部245は、ノード系列判定部244から供給されるノード系列データを基に、移動履歴データのHMMのパラメータに対応するノード系列データのパラメータを計算する。即ち、パラメータ再計算部245は、未知の移動履歴データのHMMの初期確率πi、状態遷移確率aij、および観測確率(中心値μiと分散値σi)に対応する、ノード系列データの初期確率<πi>、状態遷移確率<aij>、および観測確率(中心値<μi>と分散値<σi>)を計算する。以下において、”< >”で囲まれた初期確率πi、状態遷移確率aij、および観測確率(中心値μiと分散値σi)は、ノード系列データで再計算されたパラメータを表す。
【0230】
また、パラメータ再計算部245は、各状態遷移の遷移頻度<trans_cntij>と各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>を計算しておく。
【0231】
ここで、遷移頻度<trans_cntij>は、状態ノードsiから状態ノードsjに遷移する頻度(カウント値)を表し、i=1乃至N,j=1乃至N(Nは、時系列データの最後のノード番号(=ノード数))である。状態頻度<cnt_alli>は、全てのノード系列データにおける状態ノードsiの総数であり、状態初期頻度<cnt_starti>は、ノード系列データの先頭が状態ノードsiである個数である。
【0232】
一般に、更新後の初期確率πi_update、状態遷移確率aij_update、および観測確率の中心値μi_updateと分散値σi_updateは、次のように表すことができる。
【数5】

πi_current、aij_current、並びにμi_current及びσi_currentは、既存のノード系列データの状態ノードsiの初期確率、状態遷移確率、並びに観測確率の中心値および分散値である。また、πi_new、aij_new、並びにμi_new及びσi_newは、追加分のノード系列データの状態ノードsiの初期確率、状態遷移確率、並びに観測確率の中心値および分散値である。ni_currentとni_newは、ノード系列データの状態ノードsiの既存部分のノード数と追加部分のノード数である。
【0233】
従って、パラメータ再計算部245が各状態遷移の遷移頻度<trans_cntij>と各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>を計算して記憶しておくことで、次の更新の計算が容易になる。
【0234】
なお、頻度を計算して記憶する代わりに、頻度を確率的にカウントして、非整数の成分を扱ってもよい。さらに、頻度の代わりに、頻度×平均値、頻度×分散値のようなパラメータを記憶してもよい。
【0235】
パラメータ再計算部245は、状態初期頻度<cnt_starti>とともに、ノード系列判定部244から供給されるノード系列データの総数であるノード系列データ数<seq_cnt>も計算しておく。
【0236】
新規モデル整理部246は、新規モデル初期化部241が宣言した新規モデルとしてのHMMの各状態ノードsiのなかで、使用されない状態ノードを消去することで、新規モデルを整理する。具体的には、新規モデル整理部246は、パラメータ再計算部245で計算された状態頻度<cnt_alli>が0の状態ノードsiを消去する。新規モデル整理部246により整理された後の新規モデル(のパラメータ)が、新規モデル結合部203に出力される。また、未知の移動履歴データの前後の既存モデルの状態ノードも既知未知判定部201から供給されていた場合には、それも、併せて新規モデル結合部203に出力される。
【0237】
[新規モデル学習部243の学習処理]
次に、図30乃至図33を参照して、新規モデル学習部243の学習処理について説明する。
【0238】
初めに、図30および図31を参照して、通常のHMMによる学習モデルと、新規モデル学習部243が行う学習モデルの違いについて説明する。
【0239】
ユーザの移動履歴をHMMのように離散状態でモデル化する場合、通常、移動経路を一定の時間間隔でサンプルしたデータをモデル化する。移動履歴のデータを取得する際に、省電力の要請などの理由からサンプリング間隔を細かくできず、十分なサンプルが得られない場合、サンプル数とノード数があまり変わらないか、ノード数に比べてサンプル数が少ない状況が起こり得る。このような状況で、観測されるデータが所定の位置の周囲に正規分布する状態ノードを仮定する場合、一つのサンプルを一つのノードでモデル化することがある。この場合、ノードの分散値は非常に小さい値(あるいは0)に収束し、サンプルの近傍はモデル化されないことになる。従って、サンプリングされたサンプル間の経路はモデル化されない。
【0240】
図30は、移動履歴を通常のHMMによりモデル化したときの概念図を示している。図30の直線(線分)はユーザの実際の移動経路を示し、バツ印(×)が移動履歴データとして取得されたサンプル、サンプルを囲む丸(○)がノードを示している。
【0241】
図30に示すように、近くにサンプルが得られなかった場所(領域)はモデル化されないので、例えば、電車のような速い移動速度で移動しているような場合、サンプルとサンプルの間の経路はモデル化されない。一方、徒歩のような遅い移動速度で移動している場合、一つのノードで複数のサンプルをモデル化する場合がある。このような場合には、移動履歴をノードで適切に表現できていないことがある。
【0242】
また、同一の移動経路を二回通過した場合に、ノードの分散値が非常に小さい値(あるいは0)に収束していると、二回目の通過した位置は、一回目の通過のときに表現されたノードでモデル化されず、異なるノードが割り当てられることがある。
【0243】
このような問題を回避するためには、ノードの分散値に下限を設定し、サンプルから所定の領域の経路を必ずモデル化するようにさせることが考えられる。
【0244】
しかし、分散値を大きくすると、異なる経路を同一の経路とみなす可能性も高くなる。例えば、平行に進む異なる経路を同一の経路とみなすおそれが生じる。さらに、分散値を大きくすると、移動速度の遅いときの移動履歴データを高い精度で再現することが難しくなる。逆に、分散値が小さくしすぎると、移動速度が速いときの移動履歴データを同一の経路と認識できなくなる。実際の移動履歴データのサンプルは、移動速度の違いで様々な距離感覚となるため、全てに適したノードの分散値の下限を決定するのは困難である。
【0245】
そこで、新規モデル学習部243は、図31に示すように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようなモデルを仮定することで、サンプルとサンプルの間の経路をモデル化する。新規モデル全体では、新規モデル学習部243は、各ノードが二つの連続するサンプルを順次つないだモデル化を行う。これにより、鎖で繋がれるように、経路全体の領域がもれなく新規モデルで表現することができる。
【0246】
また、サンプルとサンプルの間隔が長くても、二つのサンプル間を含むようにモデル化しているので、ノードの分散値は小さく設定することができる。逆に、サンプルとサンプルの間隔が短い場合も同様にモデル化できるため、スケールフリーなモデル化を実現することができる。
【0247】
なお、後述するように、新規モデル学習部243は、一つの状態ノードが連続する3つ以上のサンプルを反映するようにモデル化することも可能であり、一つの状態ノードがいくつのサンプルを反映するようにモデル化するかは、適宜、決定することができる。
【0248】
図32は、新規モデル学習部243の学習モデルをグラフィカルモデルで表したものである。
【0249】
図32Aの学習モデルは、現在のある状態ノードが、現在のデータと、一つ前(一つ後ろ)の2つのサンプルを観測するモデルである。図32Aでは、一つの状態ノードからの矢印が、下と右下にあるが、下と左下に向かう矢印のあるモデルでもよい。
【0250】
なお、本実施の形態では、図31に示したように、一つの状態ノードが二つの連続するサンプルを表現するモデルを採用するが、一つの状態ノードが3以上の連続するサンプルを表現するモデルを採用することもできる。図32Bのモデルは、一つの状態ノードが3つの連続するサンプルを表現するモデルのグラフィカルモデルである。
【0251】
[新規モデル学習部243の新規モデル学習処理]
次に、図33のフローチャートを参照して、新規モデル学習部243の新規モデル学習処理について説明する。
【0252】
初めに、ステップS51において、新規モデル学習部243は、未知の移動履歴データに対する各状態の尤度を計算する。具体的には、新規モデル学習部243は、ユーザ活動モデルを表すHMMの状態siへの遷移時に、移動履歴データの2つのサンプル、時刻tの位置のデータxtと時刻t+1の位置のデータxt+1が出力されると仮定した観測尤度P(xt,xt+1|si)を、次式(5)により計算する。
【0253】
【数6】

なお、時刻tは、時系列データの測定時刻ではなく、時系列データの順番(ステップ数)を表し、1からT(時系列データのサンプル数)までの値をとる。また、式(5)のxt(1)、xt(2)、xt(3)は、それぞれ移動履歴データxtの時刻、緯度、経度を表すものとする。さらに、式(5)のN()は、単一正規分布を表し、μsi(1)、σsi(1)は、時刻の単一正規分布の中心値および分散値を表す。また、μsi(2)、σsi(2)は、緯度の単一正規分布の中心値および分散値を表し、μsi(3)、σsi(3)は、経度の単一正規分布の中心値および分散値を表すものとする。
【0254】
観測尤度P(xt,xt+1|si)は、元の時系列データと、一つずれた時系列データの同時分布なので、それぞれの観測系列の分布の積となっている。
【0255】
なお、一つの状態ノードがW個以上の連続するサンプルを表現するモデルの観測尤度P(xt,・・・,xt+W|si)は、次式(6)で表すことができる。勿論、時系列データの次元数Dも3より大きい値に一般化することも可能である。
【数7】

【0256】
ステップS51では、全ての状態siと3次元データxtの組み合わせについて、式(5)による観測尤度P(xt,xt+1|si)が、新規モデル学習部243によって計算される。
【0257】
次に、ステップS52において、新規モデル学習部243は、各時刻tにおける全ての状態siのフォワード尤度αt(si)を計算する。即ち、新規モデル学習部243は、次の式(7)および式(8)により、時刻tにおける状態siのフォワード尤度αt(si)を時刻1から最終の時刻Tまで順番に計算する。
【0258】
【数8】

なお、式(7)のπsiは、状態siの初期確率を表す。また、式(8)のajiは、状態sjから状態siへの状態遷移確率を表す。なお、初期確率πsiおよび状態遷移確率ajiの初期値は、例えば、外部から与えられる。
【0259】
ステップS53において、新規モデル学習部243は、各時刻tにおける全ての状態siのバックワード尤度βt(si)を計算する。即ち、新規モデル学習部243は、次の式(9)および式(10)により、時刻tにおける状態siのバックワード尤度βt(si)を、最終の時刻Tから時刻1まで逆順に計算する。
【0260】
【数9】

式(9)では、時刻Tに各状態siである確率が全て等しいものとされている。
【0261】
このように、ステップS51乃至S53の処理により、移動履歴データに対する隠れマルコフモデルの各種の尤度が計算される。
【0262】
ステップS54において、新規モデル学習部243は、初期確率、状態遷移確率を更新する。即ち、新規モデル学習部243は、各状態siの初期確率πsi、各状態間の状態遷移確率aijを、次の式(11)および式(12)で求まる初期確率πsi’、状態遷移確率aij’にそれぞれ更新する。
【0263】
【数10】

式(11)および式(12)は、Baum-Welchの最尤推定法で一般的に用いられる式に、観測尤度P(xt,xt+1|si)を適用したものである。
【0264】
ステップS55において、新規モデル学習部243は、観測確率を更新する。即ち、新規モデル学習部243は、各状態siの観測確率(確率分布)の中心値μsi(d)、分散値σsi(d)2を、次の式(13)および式(14)で求まる中心値μsi(d)’、分散値σsi(d)’2にそれぞれ更新する。
【0265】
【数11】

式(13)および式(14)のdは、データの次元Dに対応し、1,2、または3のいずれかとなる。
【0266】
一つの状態ノードがW個以上の連続するサンプルを表現するモデルで、次元数がDである場合の観測確率の中心値μsi(d)’および分散値σsi(d)’2は、次の式(15)および式(16)で求めることができる。
【数12】

【0267】
式(13)および式(15)の中心値μsi(d)’、並びに、式(14)および式(16)の分散値σsi(d)’2は、尤度を最小化する式を解くことで、容易に算出することができる。
【0268】
ステップS56において、新規モデル学習部243は、パラメータの更新を終了するか否かを判定する。例えば、各尤度の増分が所定の値以下となり、パラメータの更新の収束条件を満たした場合、新規モデル学習部243は、パラメータの更新を終了すると判定する。あるいは、ステップS51乃至S55の処理を規定の回数繰り返し実行した場合、パラメータの更新を終了すると判定するとしてもよい。
【0269】
ステップS56で、パラメータの更新を終了しないと判定された場合、処理はステップS51に戻る。
【0270】
ステップS51では、新規モデル学習部243は、更新されたパラメータに基づいて、各状態の尤度が計算される。即ち、ステップS54およびS55の処理で更新された、各状態siの初期確率πsi’、中心値μsi(d)’および分散値σsi(d)’2、並びに、各状態間の状態遷移確率aij’を示すデータに基づいて、各状態の尤度が計算される。
【0271】
その後、同様にステップS52乃至S55の処理が実行される。これにより、状態siの系列の各種の尤度、すなわち、観測尤度P(xt,xt+1|si)、フォワード尤度αt(si)、バックワード尤度βt(si)が次第に増加し、最終的に最大になるように、HMMのパラメータの更新が行われる。そして、ステップS56において、再度、パラメータの更新を終了するか否かが判定される。
【0272】
ステップS56で、パラメータの更新を終了すると判定された場合、処理はステップS57に進む。
【0273】
ステップS57において、新規モデル学習部243は、最終的なパラメータをノード系列判定部244に出力する。即ち、新規モデル学習部243は、最終的に求められた、各状態siの初期確率πsi’、中心値μsi(d)’および分散値σsi(d)’2、並びに、各状態間の状態遷移確率aij’を示すデータをノード系列判定部244に出力して、処理を終了する。
【0274】
[パラメータ再計算部245のパラメータ再計算処理]
次に、図34のフローチャートを参照して、パラメータ再計算部245のパラメータ再計算処理について説明する。
【0275】
初めに、ステップS71において、パラメータ再計算部245は、ノード系列判定部244から供給される全てのノード系列データを対象として、各状態遷移の遷移頻度<trans_cntij>(i=1乃至N,j=1乃至N,Nは、時系列データの最後のノード番号(=ノード数))をカウントする。
【0276】
ステップS72において、パラメータ再計算部245は、ノード系列判定部244から供給される全てのノード系列データを対象として、各状態ノードsiの状態頻度<cnt_alli>、状態初期頻度<cnt_starti>、およびノード系列データ数<seq_cnt>をカウントする。
【0277】
ステップS73において、パラメータ再計算部245は、ノード系列データの初期確率<πi>’と状態遷移確率<aij>’を計算(更新)する。ノード系列データの初期確率<πi>’および状態遷移確率<aij>’は、次の式(17)および式(18)により計算することができる。
【数13】

【0278】
ステップS74において、パラメータ再計算部245は、ノード系列データの観測確率、即ち、各状態ノードsiの中心値<μj>’と分散値<σj>’を計算(更新)する。各状態ノードsiの中心値<μj>’と分散値<σj>’は、次の式(19)および式(20)により計算することができる。
【0279】
【数14】

式(19)及び式(20)において、xt_kは、移動履歴データの3次元データxtのうち、状態ノードsiに対応する3次元データを表す。従って、xt_kの個数は、状態ノードsiの状態頻度<cnt_alli>と等しくなる。
【0280】
なお、一つの状態ノードがW個以上の連続するサンプルを表現するモデルでは、各状態ノードsiの中心値<μj>’と分散値<σj>’は、次の式(21)および式(22)により計算することができる。
【数15】

【0281】
以上で、パラメータ再計算部245によるパラメータ再計算処理は終了する。
【0282】
なお、図32のグラフィカルモデルを用いていることが、図29の新規モデル学習部243(式(5),式(6)、式(13)乃至式(16))と、パラメータ再計算部245(式(19)乃至式(22))に反映されている。従って、例えば、処理を簡略化する要請があるならば、図29のパラメータ再計算部245のみに、図32のグラフィカルモデルを反映しただけの実施例でもよい。この場合、図29の新規モデル学習部243には、通常のバウムウエルチアルゴリズムによる学習を採用することができる。また、さらに簡略化するならば、通常のバウムウエルチアルゴリズムの代わりに、取得した移動履歴データに対して、前から順に番号を割り振って、これを状態ノードの番号とするような処理に変更してもよい。この場合、図7の移動属性識別付与部74で与えられた移動属性を見て、現在の移動履歴の3次元データの移動属性が滞在状態でなければ、一つ前の3次元データに割り振られた番号を1大きくした番号が、状態ノードの番号として割り振られる。一方、現在の移動履歴の3次元データの移動属性が滞在状態であれば、一つ前の3次元データに割り振られた番号と同じ番号が状態ノードの番号として割り振られる。
【0283】
[新規モデル生成部202の新規モデル生成処理]
図35は、新規モデル生成部202が行う新規モデル生成処理全体のフローチャートである。
【0284】
初めに、ステップS91において、新規モデル初期化部241は、既知未知判定部201から供給された未知の移動履歴データを取得し、それに対応する新規モデルを生成する。即ち、新規モデル初期化部241は、取得した未知の移動履歴データのサンプル数と同数の状態ノード数のHMMを生成する。
【0285】
ステップS92において、新規モデル制約部242は、新規モデル初期化部241で生成したHMMにleft-to-rightの制約を設定する。
【0286】
ステップS93において、新規モデル学習部243は、未知の移動履歴データを用いて新規モデルを学習する。即ち、ステップS93では、新規モデルは、図31に示したように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようなモデルとして、図33を参照して説明した新規モデル学習処理が実行される。
【0287】
ステップS94において、ノード系列判定部244は、ステップS93の新規モデル学習処理により得られた新規モデルを用いて、未知の移動履歴データに対応するノード系列データを生成し、パラメータ再計算部245に供給する。
【0288】
ステップS95において、パラメータ再計算部245は、ノード系列判定部244から供給されるノード系列データを基に、移動履歴データのHMMのパラメータに対応するノード系列データのパラメータを計算する。より具体的には、パラメータ再計算部245は、ノード系列データの初期確率<πi>’、状態遷移確率<aij>’、および各状態ノードsiの中心値<μj>’と分散値<σj>’を計算する。また、パラメータ再計算部245は、各状態ノードsiの状態頻度<cnt_alli>と状態初期頻度<cnt_starti>も計算する。
【0289】
ステップS96において、新規モデル整理部246は、生成した新規モデルとしてのHMMの各状態ノードsiのなかで、使用されない状態ノードを消去することで、新規モデルを整理する。そして、新規モデル整理部246は、整理後の新規モデルのパラメータと、未知の移動履歴データの前後の既存モデルの状態ノードも既知未知判定部201から供給されていた場合には、それも、新規モデル結合部203に出力して、処理を終了する。
【0290】
[新規モデル結合部203のトポロジー更新モデル生成処理]
次に、先の学習により得られている既存モデルと、未知の移動履歴データにより生成された新規モデルを結合し、トポロジー更新モデルを生成する新規モデル結合部203のトポロジー更新モデル生成処理について説明する。
【0291】
まず、説明の前提として、以下の変数を定義する。
【0292】
既存モデル :xhmm
新規モデル :yhmm
トポロジー更新モデル:zhmm
【0293】
既存モデル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行1列のテーブル(初期確率テーブル)となる。
各状態ノードの遷移確率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行1列のテーブル(状態頻度テーブル)となる。
【0294】
図36のフローチャートを参照して、新規モデル結合部203によるトポロジー更新モデル生成処理について説明する。
【0295】
初めに、ステップS101において、新規モデル結合部203は、トポロジー更新モデルの初期確率zhmm.piを計算する。
【0296】
ステップS101では、まず、新規モデル結合部203は、既存モデルがM個、新規モデルがN個の状態ノードからなるので、図37Aに示すように、初期確率zhmm.piとしての(M+N)行1列の初期確率テーブルを生成する。
【0297】
そして、新規モデル結合部203は、トポロジー更新モデルの初期確率テーブルの第1行乃至第M行の第m行に(m=1,2,・・,M)は、図37Aに示すように、既存モデルの初期確率xhmm.pi(m)に、既存モデルの時系列データ数xhmm.seq_cntを乗算した値を設定する。また、トポロジー更新モデルの初期確率テーブルの第(M+1)行乃至第(M+N)行の第(M+n)行(n=1,2,・・・,N)には、新規モデルの初期確率yhmm.pi(n)に、新規モデルの時系列データ数yhmm.seq_cntを乗算した値を設定する。
【0298】
そして、図37Bに示されるように、トポロジー更新モデルの初期確率テーブルの各行が、初期確率テーブルの全要素の総和SUM_piで除算されることで規格化され、トポロジー更新モデルの初期確率テーブルzhmm.piの生成が終了する。
【0299】
次に、ステップS102において、新規モデル結合部203は、トポロジー更新モデルの時系列データ数zhmm.seq_cntを計算する。具体的には、新規モデル結合部203は、既存モデルの時系列データ数xhmm.seq_cntと、新規モデルの時系列データ数yhmm.seq_cntの和を計算し、トポロジー更新モデルの時系列データ数zhmm.seq_cntとする。
【0300】
ステップS103において、新規モデル結合部203は、トポロジー更新モデルの遷移確率zhmm.aと状態頻度zhmm.cnt_allを計算する。
【0301】
ステップS103では、まず、新規モデル結合部203は、既存モデルがM個、新規モデルがN個の状態ノードからなるので、図38に示すように、(M+N)行(M+N)列の遷移確率テーブルを生成する。なお、遷移確率テーブルの第1行第1列から第M行M列を左上領域、第(M+1)行第(M+1)列から第(M+N)行(M+N)列を右下領域、第1行第(M+1)列から第M行(M+N)列を右上領域、第(M+1)行第1列から第(M+N)行M列を左下領域という。
【0302】
そして、新規モデル結合部203は、生成した遷移確率テーブルの左上領域の各要素に、既存モデルの状態ノードsmの遷移確率xhmm.a(m,j)に、既存モデルの状態ノードsmの状態頻度xhmm.cnt_all(m)を乗算した値を設定する(j=1,・・・,M)。
【0303】
また、新規モデル結合部203は、生成した遷移確率テーブルの右下領域の各要素に、新規モデルの状態ノードsmの遷移確率yhmm.a(m,j)に、新規モデルの状態ノードsmの状態頻度yhmm.cnt_all(m)を乗算した値を設定する(j=1,・・・,M)。
【0304】
なお、図38では、紙面の制約上、xhmm.a(m,j)×xhmm.cnt_all(m)、yhmm.a(m,j)×yhmm.cnt_all(m)と、同一行についてはまとめて図示している。
【0305】
さらに、新規モデル結合部203は、生成した遷移確率テーブルの右上領域の各要素については、基本的に”0”を代入する。ただし、未知の移動履歴データの前の既存モデルの状態ノードが、新規モデル生成部202から供給され、新規モデルが既存モデルのノード系列データの後に接続される場合、その接続先の状態ノードに対応する要素のみ、”1”が代入される。具体的には、接続先の状態ノードがsである場合、第i行第(M+1)列の要素に、”1”が設定される。
【0306】
同様に、新規モデル結合部203は、生成した遷移確率テーブルの左下領域の各要素については、基本的に”0”を代入する。ただし、未知の移動履歴データの後の既存モデルの状態ノードが、新規モデル生成部202から供給され、新規モデルの後に既存モデルのノード系列データが接続される場合、その接続先の状態ノードに対応する要素のみ、”1”が代入される。具体的には、接続先の状態ノードがsである場合、第(M+N)行第j列の要素に、”1”が設定される。
【0307】
次に、新規モデル結合部203は、図39に示すように、生成した遷移確率テーブルの左上領域と右下領域について、行方向の和を演算することにより、トポロジー更新モデルの状態頻度zhmm.cnt_allを計算する。図39の状態頻度テーブルは、(M+N)行1列のテーブルによりなる。
【0308】
最後に、新規モデル結合部203は、図40に示すように、図38の遷移確率テーブルの左上領域と右下領域の各行を、トポロジー更新モデルの状態頻度テーブルの各行zhmm.cnt_all(i)で除算して、規格化する。以上で、トポロジー更新モデルの遷移確率テーブルの生成が終了する。
【0309】
そして、処理はステップS104に進み、新規モデル結合部203は、トポロジー更新モデルの確率分布の中心値zhmm.muおよび分散値zhmm.sigma2を計算する。
【0310】
ステップS104では、既存モデルがM個、新規モデルがN個の状態ノードからなるので、トポロジー更新モデルの中心値zhmm.muに対応する中心値テーブルは、(M+N)行D列で構成される。
【0311】
図41に示すように、(M+N)行D列の中心値テーブルの第1行から第M行の各行には、既存モデルの中心値xhmm.mu(i,1),xhmm.mu(i,2),xhmm.mu(i,3)が代入される(i=1,・・・,M)。また、(M+N)行D列の中心値テーブルの第(M+1)行から第(M+N)行の各行には、新規モデルの中心値yhmm.mu(i,1),yhmm.mu(i,2),yhmm.mu(i,3)が代入される(i=1,・・・,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)は、移動履歴データの経度の中心値である。
【0312】
同様に、トポロジー更新モデルの確率分布の分散値zhmm.sigma2に対応する分散値テーブルも、(M+N)行D列で構成される。
【0313】
図42に示すように、(M+N)行D列の分散値テーブルの第1行から第M行の各行には、既存モデルの分散値xhmm.sigma2(i,1),xhmm.sigma2(i,2),xhmm.sigma2(i,3)が代入される(i=1,・・・,M)。また、(M+N)行D列の分散値テーブルの第(M+1)行から第(M+N)行の各行には、新規モデルの分散値yhmm.sigma2(i,1),yhmm.sigma2(i,2),yhmm.sigma2(i,3)が代入される(i=1,・・・,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)は、移動履歴データの経度の分散値である。
【0314】
そして、処理はステップS105に進み、新規モデル結合部203は、トポロジー更新モデルのパラメータを更新モデル整理部205に出力する。即ち、トポロジー更新モデルの初期確率zhmm.pi、時系列データ数zhmm.seq_cnt、遷移確率zhmm.a、状態頻度zhmm.cnt_all、並びに、確率分布の中心値zhmm.muおよび分散値zhmm.sigma2が更新モデル整理部205に出力される。以上で、トポロジー更新モデル生成処理は終了する。
【0315】
[パラメータ更新部204のパラメータ更新処理]
次に、パラメータ更新部204によるパラメータ更新処理について説明する。
【0316】
図43は、パラメータ更新部204が行うパラメータ更新処理全体のフローチャートである。
【0317】
初めに、ステップS121において、パラメータ更新部204は、既知未知判定部201から供給された、既知の移動履歴データと、それに対応するノード系列データを取得する。以下では、説明を簡単にするため、1個の既知の移動履歴データと、それに対応するノード系列データが取得されたとして説明する。
【0318】
ステップS122において、パラメータ更新部204は、既存モデルの初期確率xhmm.piを更新する。
【0319】
ステップS122では、まず、初期確率xhmm.piとしてのM行1列の初期確率テーブルの、取得された状態ノード系列の先頭ノードに対応する初期確率xhmm.pi(i)に1が加算される。図44Aでは、状態ノード系列の先頭ノードが状態ノードs18である例として、xhmm.pi(18)に1が加算されている。
【0320】
そして、確率の条件を満たすため、図44Bに示すように、初期確率テーブルの各行が、全要素の総和SUM_piで除算されることで規格化され、既存モデルの初期確率xhmm.piの更新が終了する。
【0321】
次に、ステップS123において、パラメータ更新部204は、既存モデルの時系列データ数xhmm.seq_cntを更新する。時系列データ数は一つ増加するだけであるので、現在のxhmm.seq_cntに1を加算したものが更新後の既存モデルの時系列データ数xhmm.seq_cntとされる。
【0322】
ステップS124において、パラメータ更新部204は、既存モデルの遷移確率xhmm.aと状態頻度xhmm.cnt_allを更新する。
【0323】
ステップS124では、まず、取得された状態ノード系列で発生している状態遷移に対応する遷移確率テーブルの各要素に、1が加算される。例えば、図45の例では、状態ノードs18から状態ノードsへの遷移と、状態ノードsMから状態ノードsへの遷移が、少なくとも発生し、xhmm.a(18,2)×xhmm.cnt_all(18)とxhmm.a(M,2)×xhmm.cnt_all(M)のそれぞれに、1が加算されている。
【0324】
また、取得された状態ノード系列の最後尾の状態ノードについては、自己遷移に対応する遷移確率テーブルの要素に、1が加算される。例えば、図45では、状態ノード系列の最後尾の状態ノードがsである例として、xhmm.a(2,2)×xhmm.cnt_all(2)に、1が加算されている。
【0325】
次に、パラメータ更新部204は、図46に示すように、1を加算後の遷移確率テーブルに対し、行方向の和を演算することで、既存モデルの状態頻度xhmm.cnt_allを計算(更新)する。
【0326】
最後に、パラメータ更新部204は、図47に示すように、1を加算後の遷移確率テーブルの各行を、更新後の既存モデルの状態頻度xhmm.cnt_all(i)で除算して、規格化する。以上の計算により、既存モデルの遷移確率テーブルが更新される。
【0327】
そして、処理はステップS125に進み、パラメータ更新部204は、既存モデルの確率分布の中心値xhmm.muおよび分散値xhmm.sigma2を更新する。
【0328】
一般に、既存モデルにおいて状態ノードsiがM個出現し、その平均値がμsiである場合において、M+1番目の状態ノードsiと認識される新しいサンプルxM+1が増えたときの更新前の平均値μsi(M)と更新後のμsi(M+1)との間には、次の関係がある。
【0329】
【数16】

式(23)および式(24)において、右肩の括弧付きの文字は状態ノードsiの出現回数を表す。
【0330】
そこで、パラメータ更新部204は、図48に示すように、M行D列の中心値テーブルの各行の要素に、上述したステップS124で状態頻度xhmm.cnt_all(i)を更新する前の、1つ前の状態頻度xhmmOLD.cnt_all(i)を乗算する(i=1,・・・,M)。従って、1つ前の状態頻度xhmmOLD.cnt_all(i)は、ステップS124の処理を行う前に、所定の場所に格納しておく必要がある。
【0331】
次に、パラメータ更新部204は、新しいサンプルxM+1に対応する状態ノードに対応する中心値テーブルの行に、新しいサンプルxM+1としての既知の移動履歴データ(3次元データのそれぞれ)を加算する。
【0332】
さらに、パラメータ更新部204は、M行D列の中心値テーブルの各行の要素を、上述したステップS124で更新した状態頻度xhmm.cnt_all(i)で除算する。以上で、既存モデルの確率分布の中心値xhmm.muの更新が終了する。
【0333】
一方、既存モデルにおいて状態ノードsiがM個出現し、その平均値がμsi、分散値がσsiである場合において、M+1番目の状態ノードsiと認識される新しいサンプルxM+1が増えたときの更新前の平均値σsi2(M)と更新後のσsi2(M+1)との間には、次の関係がある。
【0334】
【数17】

式(25)および式(26)において、右肩の括弧付きの文字は状態ノードsiの出現回数を表す。
【0335】
そこで、パラメータ更新部204は、M行D列の分散値テーブルの各行の要素に、既存モデルの確率分布の中心値xhmm.muを更新する前の、1つ前の中心値xhmm OLD.muの二乗を加算する(i=1,・・・,M)。従って、1つ前の中心値xhmm OLD.muも、上述の更新を行う前に、所定の場所に格納しておく必要がある。
【0336】
次に、パラメータ更新部204は、1つ前の中心値xhmm OLD.muの二乗加算後のM行D列の分散値テーブルの各行の要素に、1つ前の状態頻度xhmmOLD.cnt_all(i)を乗算する。
【0337】
図49は、状態頻度xhmmOLD.cnt_all(i)を乗算後の分散値テーブルを示している。
【0338】
さらに、パラメータ更新部204は、新しいサンプルxM+1に対応する状態ノードに対応する中心値テーブルの行に、新しいサンプルxM+1としての既知の移動履歴データ(3次元データのそれぞれ)の二乗を加算する。
【0339】
最後に、パラメータ更新部204は、M行D列の中心値テーブルの各行の要素を、上述したステップS124で更新した状態頻度xhmm.cnt_all(i)で除算し、かつ、更新後の中心値xhmm.mu(i)の二乗を減算する。以上で、既存モデルの確率分布の分散値xhmm.sigma2の更新が終了する。
【0340】
そして、処理はステップS126に進み、パラメータ更新部204は、更新された既存モデルのパラメータを新規モデル結合部203と更新モデル整理部205に出力する。即ち、更新された既存モデルの初期確率xhmm.pi、時系列データ数xhmm.seq_cnt、遷移確率xhmm.a、状態頻度xhmm.cnt_all、並びに、確率分布の中心値xhmm.muおよび分散値xhmm.sigma2が出力される。以上で、パラメータ更新処理は終了する。
【0341】
[学習メインプロセス部23全体の処理]
次に、図50のフローチャートを参照して、学習メインプロセス部23全体の学習メインプロセス処理について説明する。
【0342】
初めに、ステップS141において、学習メインプロセス部23は、学習プリプロセス部22(図1)から供給される移動履歴データと、ユーザ別モデルパラメータ記憶部12(図1)から供給される、既存モデルのパラメータを取得する。移動履歴データは、既知未知判定部201が取得し、既存モデルのパラメータは、既知未知判定部201、新規モデル結合部203、およびパラメータ更新部204が取得する。
【0343】
ステップS142において、既知未知判定部201は、供給された移動履歴データが既知の経路の移動履歴データであるか否か判定する既知未知判定処理を行う。
【0344】
図20乃至図28を参照して説明したように、既知未知判定処理では、既存モデルの状態ノードに未知状態ノードを追加した未知状態追加モデルでビタビ推定を行い、既知未知の二状態モデルによるビタビ判定を行うことで、既知または未知の判定が行われる。
【0345】
既知未知判定処理において、供給された移動履歴データが既知であると判定された場合、供給された移動履歴データと、それに対応する状態ノードの時系列データであるノード系列データが、パラメータ更新部204に供給される。一方、既知未知判定処理において、供給された移動履歴データが未知であると判定された場合、供給された移動履歴データは新規モデル生成部202に供給される。また、未知の移動履歴データが既知の状態ノード(経路)と接続されている場合には、接続先の状態ノードも新規モデル生成部202に供給される。
【0346】
ステップS142で既知と判定された場合、処理はステップS143に進み、パラメータ更新部204は、既知の移動履歴データと、それに対応するノード系列データに基づいて、既存モデルのパラメータを更新するパラメータ更新処理を行う。即ち、図43乃至図49を参照して説明した処理が行われる。
【0347】
一方、ステップS142で未知と判定された場合、処理はステップS144に進み、新規モデル生成部202は、未知の移動履歴データに対応する新規モデルを生成する新規モデル生成処理を行う。換言すれば、新規モデル生成部202は、未知の移動履歴データを表現する新規モデルのパラメータを求める。新規モデル生成処理は、即ち、図29乃至図35を参照して説明した処理である。
【0348】
ステップS145において、新規モデル結合部203は、既存モデルと新規モデルとを結合し、学習済みの既存モデルに、未知の移動履歴データを取り込んで成長させたトポロジー更新モデルを生成するトポロジー更新処理を行う。即ち、新規モデル結合部203は、図36乃至図42を参照して説明した処理を行う。
【0349】
ステップS143またはS145の処理後、ステップS146において、更新モデル整理部205は、自己遷移のみで、他の状態ノードからの遷移が無い状態ノードを消去することで、パラメータ更新モデルまたはトポロジー更新モデルを整理する。更新モデル整理部205は、整理後の更新モデルのパラメータを、学習ポストプロセス部24とユーザ別モデルパラメータ記憶部12に供給して、処理を終了する。
【0350】
[目的地経由地検出部25の処理]
次に、図51を参照して、学習ブロック11の目的地経由地検出部25(図1)の処理について説明する。
【0351】
上述したように、学習メインプロセス部23は、移動履歴データを分割およびホールドする処理が行われた後の(移動属性付き)移動履歴データを学習用データとして、ユーザ活動モデルのパラメータを学習する。そして、学習ポストプロセス部24が、学習により求めたパラメータを用いて、移動履歴データに対応する状態系列データを生成する。
【0352】
図51Aは、図8下段に示した、学習プリプロセス部22によって移動履歴データの分割およびホールドが行われた後の、移動属性付き移動履歴データ83Aおよび83Bを示している。
【0353】
図51Bは、図8下段に示した移動属性付き移動履歴データ83Aおよび83Bに、対応する状態系列データを併せて示した図である。
【0354】
移動属性付き移動履歴データ83Aには、s,s,・・・,s,・・・sの状態系列ノードが対応する。移動属性付き移動履歴データ83Bには、st+1,st+2,・・・,sの状態系列ノードが対応する。
【0355】
目的地経由地検出部25は、1まとまりの移動属性付き移動履歴データの最後の”滞在状態(u)”の3次元データに対応する状態ノードを検出し、目的地の属性を付与する。図51Bの例では、移動属性付き移動履歴データ83Aの状態ノードsと、移動属性付き移動履歴データ83Bの状態ノードsに対して、目的地の属性が付与される。状態ノードsと状態ノードsは、いずれも滞在状態が滞在閾値時間以上継続していた状態ノードである。このように、目的地経由地検出部25によって、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードが、目的地に推定される。
【0356】
なお、図8を参照して説明した分割処理では、分割した移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”が、1つの”滞在状態”に縮減された。しかしながら、分割処理では、移動履歴データの最後の滞在閾値時間以上の複数の”移動状態”のすべてを、消去するようにしてもよい。図51Aの例で説明すると、移動属性付き移動履歴データ83Aおよび83Bそれぞれの最後の”滞在状態(u)”の3次元データを省略するようにしてもよい。この場合には、目的地経由地検出部25は、1まとまりの移動属性付き移動履歴データの最後の3次元データに対応する状態ノードに、目的地の属性を付与する。図51Bの例で説明すると、移動属性付き移動履歴データ83Aの状態ノードsの1つ前の状態ノードst−1、および、移動属性付き移動履歴データ83Bの状態ノードsの1つ前の状態ノードsT−1を目的地とすればよい。
【0357】
目的地経由地検出部25は、また、1まとまりの移動属性付き移動履歴データの途中にある”滞在状態(u)”の3次元データに対応する状態ノードを検出し、経由地の属性を付与する。即ち、滞在状態の継続時間が滞在閾値時間未満である移動履歴データに対応する状態ノードが、経由地に推定される。図51Bの例で説明すると、移動属性付き移動履歴データ83Aの状態ノードsが、経由地に決定される。
【0358】
なお、目的地経由地検出部25は、図51Cに示すように、移動手段が変更されたとき、変更前の最後の状態ノードsにも、経由地の属性を付与するようにしてもよい。
【0359】
[学習ブロック11の処理]
図52のフローチャートを参照して、学習ブロック11全体の処理について説明する。
【0360】
初めに、ステップS241において、履歴データ蓄積部21は、センサデバイスから供給される、移動履歴データを、学習用データとして蓄積する。
【0361】
ステップS242において、学習プリプロセス部22は、図18を参照して説明した、学習プリプロセス処理を実行する。即ち、履歴データ蓄積部21に蓄積されている移動履歴データの接続および分割の処理、移動履歴データを構成する3次元データそれぞれに、”滞在状態”または”移動状態”の移動属性の付与、などを行う。
【0362】
ステップS243において、学習メインプロセス部23は、図50を参照して説明した、学習メインプロセス処理を実行する。即ち、学習メインプロセス部23は、供給されるユーザの移動履歴データに対して、既知または未知を判定し、判定結果に応じてユーザ活動モデルとしてのHMMのパラメータを更新する。未知の移動履歴データが供給された場合には、移動範囲の拡張に合わせてトポロジーを成長させたHMMのパラメータが求められる。学習メインプロセス処理により得られたユーザ活動モデルのパラメータは、学習ポストプロセス部24とユーザ別モデルパラメータ記憶部12に供給され、ユーザ別モデルパラメータ記憶部12で記憶される。
【0363】
ステップS244において、学習ポストプロセス部24は、学習により得られたパラメータで表現されるユーザ活動モデルにより、移動履歴データに対応するノード系列データを生成する。
【0364】
ステップS245において、目的地経由地検出部25は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、目的地の属性を付与する。より具体的には、目的地経由地検出部25は、滞在状態が滞在閾値時間以上継続する移動履歴データに対応する状態ノードに、目的地の属性を付与する。
【0365】
ステップS246において、目的地経由地検出部25は、移動属性付き移動履歴データに対応する状態系列ノードの所定の状態ノードに、経由地の属性を付与する。より具体的には、目的地経由地検出部25は、滞在状態の継続時間が滞在閾値時間未満である移動履歴データに対応する状態ノードに、経由地の属性を付与する。
【0366】
ステップS247において、目的地経由地検出部25は、状態ノードに付与された目的地、経由地の属性についての情報を、ユーザ別モデルパラメータ記憶部12に記憶させ、処理を終了する。
【0367】
[予測メインプロセス部33の処理]
次に、予測ブロック13が行う処理について説明する。
【0368】
初めに、予測メインプロセス部33による、現在地ノード以降のツリー探索処理について説明する。
【0369】
現在地ノード以降のツリー探索処理は、予測メインプロセス部33の現在地ノード推定部41が推定した現在地ノードから、到達可能な目的地ノードと、そこまでの経路を求める処理である。到達可能な目的地ノードは、現在地ノードから遷移可能なノードで構成されるツリー構造の中に存在する。従って、ツリーを構成する状態ノードのなかから、目的地ノードを探索することで、目的地を予測することができる。また、現在地ノード以降のツリー探索処理において、経由地の属性が付与された状態ノード(以下、経由地ノードという。)が検出された場合には、経由地までの経路も記憶される。
【0370】
学習により得られたHMMの各状態siは、地図上の所定の点(位置)を表し、状態siと状態sjが結ばれているとき、状態siから状態sjを移動する経路を表していると考えることができる。
【0371】
この場合、状態siに対応する各点は、端点、通過点、分岐点、ループのいずれかに分類することができる。端点とは、自己遷移以外の確率が極めて小さく(自己遷移以外の確率が所定の値以下であり)、次に移動可能な点がない点である。通過点とは、自己遷移以外に有意な遷移が一つある、換言すれば、次に移動可能な点が一つある点である。分岐点とは、自己遷移以外に有意な遷移が二つ以上ある、換言すれば、次に移動可能な点が二つ以上ある点である。ループとは、これまで通過した経路上のどれかと一致する点である。
【0372】
目的地への経路を探索する場合、異なる経路がある場合には、それぞれの経路について必要時間等の情報を提示することが望まれる。そこで、可能な経路を過不足なく探索するために、次の条件を設定する。
(1)一度分岐した経路は再度合流した場合でも、別の経路とみなす。
(2)探索中の経路が分岐点に達した場合に、未探索リストを作成し、未探索リストの分岐先の探索を行う。
(3)経路内に端点またはループが現れた場合、その経路の探索を終了する。なお、現在の点から、1つ前の点に経路を逆戻りする場合はループに含む。
【0373】
図53は、予測メインプロセス部33の目的地経由地予測部42による、現在地ノード以降のツリー探索処理のフローチャートである。
【0374】
図53の処理では、最初に、ステップS261において、目的地経由地予測部42は、予測メインプロセス部33の現在地ノード推定部41により推定された現在地ノードを取得し、注目するノードである注目ノードに設定する。
【0375】
ステップS262において、目的地経由地予測部42は、注目ノードに遷移先があるかを判定する。ステップS262で、注目ノードに遷移先がないと判定された場合、処理は後述するステップS271に進む。
【0376】
一方、ステップS262で、注目ノードに遷移先があると判定された場合、処理はステップS263に進み、目的地経由地予測部42は、遷移先が目的地ノードであるかを判定する。
【0377】
ステップS263で、遷移先が目的地ノードであると判定された場合、処理はステップS264に進み、目的地経由地予測部42は、これまでの経路(状態ノード系列)を内部メモリの探索結果リストに記憶する。ステップS264の後、処理はステップS271に進む。
【0378】
一方、ステップS263で、遷移先が目的地ノードではないと判定された場合、処理はステップS265に進み、目的地経由地予測部42は、遷移先が経由地ノードであるかを判定する。
【0379】
ステップS265で、遷移先が経由地ノードであると判定された場合、処理はステップS265に進み、目的地経由地予測部42は、これまでの経路(状態ノード系列)を内部メモリの探索結果リストに記憶する。
【0380】
目的地までの代表経路、到達確率、および所要時間を予測結果として出力するためには、探索結果リストには、遷移先が目的地であるときの経路のみを記憶すればよい。しかしながら、遷移先が経由地であるときの経路も記憶することにより、経由地までの経路、確率、および時間が必要になったときに即座に求めることができる。
【0381】
ステップS265で遷移先が経由地ノードではないと判定された場合、または、ステップS266の後、処理はステップS267に進み、目的地経由地予測部42は、遷移先が分岐点かを判定する。
【0382】
ステップS267で、遷移先が分岐点であると判定された場合、処理はステップS268に進み、目的地経由地予測部42は、分岐先の2つの状態ノードを内部メモリの未探索リストに記憶する(追加する)。ステップS268の後、処理はステップS271に進む。なお、分岐先が探索中の経路のいずれかの状態ノードである場合はループとなるので、目的地経由地予測部42は、その分岐先の状態ノードについては未探索リストに記憶させない。
【0383】
ステップS267で、遷移先が分岐点ではないと判定された場合、処理はステップS269に進み、目的地経由地予測部42は、遷移先が端点であるかを判定する。ステップS269で、遷移先が端点であると判定された場合、処理はステップS271に進む。
【0384】
一方、ステップS269で、遷移先が端点ではないと判定された場合、処理はステップS270に進み、目的地経由地予測部42は、遷移先の状態ノードを注目ノードに設定し、処理をステップS262に戻す。即ち、遷移先が、目的地ノード、経由地ノード、分岐点、および端点のいずれでもない場合には、探索対象の状態ノードが、遷移先の次の状態ノードに進められる。
【0385】
ステップS264,S268、またはS269の処理の後、処理がステップS271に進められた場合、目的地経由地予測部42は、未探索リストに登録されている状態ノードがあるか、即ち、未探索の分岐先があるかを判定する。
【0386】
ステップS271で、未探索の分岐先があると判定された場合、処理はステップS272に進み、目的地経由地予測部42は、未探索リストの最上位の分岐先の状態ノードを、注目ノードに設定し、注目ノードまでの経路を読み出す。そして、処理がステップS262に戻される。
【0387】
一方、ステップS271で、未探索の分岐先がないと判定された場合、ツリー探索処理は終了する。
【0388】
以上のように、ツリー探索処理では、ユーザの現在地ノードから遷移可能な状態ノードでなるツリー構造において、現在地ノードを出発点として、目的地ノード若しくは遷移先のない終端ノード(端点)になるまで全ての状態ノードを探索する処理が行われる。そして、ユーザの現在地から目的地までの経路が、現在地ノードからの状態ノード系列として、探索結果リストに記憶される。なお、ツリー探索処理は、探索回数が終了条件としての所定の回数を満たすまで探索するようにしてもよい。
【0389】
[ツリー探索処理の例]
図54を参照して、目的地経由地予測部42のツリー探索処理についてさらに説明する。
【0390】
図54の例において、状態sが現在地である場合、次のような3通りの経路が少なくとも探索されることになる。1つめの経路は、状態sから状態s,状態s等を経由して状態s10までの経路(以下、経路Aともいう。)である。2つめの経路は、状態sから状態s,状態s11,状態s14,状態s23等を経由して状態s29までの経路(以下、経路Bともいう。)である。3つめの経路は、状態sから状態s,状態s11,状態s19,状態s23等を経由して状態s29までの経路(以下、経路Cともいう。)である。
【0391】
目的地経由地予測部42は、探索された各経路が選択される確率(経路の選択確率)を計算する。経路の選択確率は、経路を構成する状態間の遷移確率を順次乗算することで求められる。ただし、次の状態に遷移する場合のみを考慮し、その場所に滞留する場合は考慮する必要がないので、学習により求められた各状態の状態遷移確率aijから、自己遷移確率を除いて規格化された遷移確率[aij]を用いて、経路の選択確率が求められる。
【0392】
自己遷移確率を除いて規格化された遷移確率[aij]は、次式(27)で表すことができる。
【数18】

ここで、δは、クロネッカー関数を表し、添え字のiとjが一致するときのみ1となり、それ以外は0となる関数である。
【0393】
したがって、例えば、図54の状態sの状態遷移確率aijが、自己遷移確率a5,5=0.5,遷移確率a5,6=0.2,遷移確率a5,11=0.3である場合、状態sから状態sまたは状態s11に分岐する場合の遷移確率[a5,6]および遷移確率[a5,11]は、それぞれ、0.4,0.6となる。
【0394】
探索された経路の状態siのノード番号iが、(y,y,・・・,y)であるとき、この経路の選択確率は、規格化された遷移確率[aij]を用いて、次式(28)で表すことができる。
【数19】

【0395】
なお、実際には、通過点での規格化された遷移確率[aij]は1であるので、経路の選択確率は、分岐する際の規格化された遷移確率[aij]を順次乗算すれば足りる。従って、目的地経由地予測部42は、図53のツリー探索処理を実行しながら、同時に、選択された経路の選択確率を式(28)により計算することができる。
【0396】
図54の例では、経路Aの選択確率は、0.4である。また、経路Bの選択確率は、0.24=0.6×0.4である。経路Cの選択確率は、0.36=0.6×0.6である。そして、計算された経路の選択確率の総和は1=0.4+0.24+0.36であり、過不足ない探索を実現することができることがわかる。
【0397】
図54の例では、現在地の状態sから注目ノードが順次進められ、状態sが注目ノードであるとき、遷移先の状態sが分岐点であるため、図53のステップS268が実行され、図55Aに示されるように、分岐先の状態s11と状態sが未探索リストに記憶される。ここで、状態s11と状態sでは、状態s11の選択確率が高いため、状態s11が未探索リストの上位に記憶される。
【0398】
そして、図53のステップS271およびS272が実行され、未探索リストの上位に記憶されている、状態s11が注目ノードに設定され、状態s11以降の経路が探索される。状態s11が注目ノードに設定されたとき、図55Bに示されるように、未探索リストから、状態s11が削除される。
【0399】
そして、状態s11を注目ノードとして探索が進められると、状態s14と状態s19の分岐先が検出されるので、図53のステップS268が実行され、状態s14と状態s19が未探索リストに記憶される。このとき、状態s14と状態s19は、現在の未探索リストの最上位に記憶され、また、状態s14と状態s19では、状態s19の選択確率が高いため、状態s19が状態s14より上位に記憶される。従って、未探索リストは、図55Cに示されるようになる。
【0400】
以下同様に、図53のステップS271およびS272が実行され、未探索リストの上位に記憶されている、状態s19が注目ノードに設定され、状態s19以降の経路が探索される。状態s19が注目ノードに設定されたとき、図55Dに示されるように、未探索リストから、状態s19が削除される。
【0401】
以上のように、目的地経由地予測部42によるツリー探索処理は、検出された分岐先を未探索リストの最上位に記録させることで、分岐先の経路のうち、より選択確率の高い方を先に探索する深さ優先アルゴリズムにより処理が実行される。
【0402】
なお、探索の深さが深くなる、換言すれば、現在地ノードを最上位として下位の階層が深くなることで、全てを探索することが難しいことも考えられる。そのような場合には、例えば、1)遷移確率の低い分岐先は探索しない、2)生起確率の低い経路は探索しない、3)探索する深さに制限を加える、4)探索する枝の数に制限を加える、などの条件を加えて、途中で探索を終了するようにしてもよい。
【0403】
図56は、ツリー探索処理における探索結果リストの例を示している。
【0404】
深さ優先アルゴリズムによりツリー探索処理を行うことにより、探索結果リストには、選択確率の高い経路から順に登録される。
【0405】
図56の例では、探索結果リストの1番目には、目的地gまでの経路R(r,r,r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って目的地gまでにかかる時間がTである。探索結果リストの2番目には、目的地gまでの経路R(r,r,r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って目的地gまでにかかる時間がTである。探索結果リストの3番目には、目的地gまでの経路R(r,r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って目的地gまでにかかる時間がTである。
【0406】
探索結果リストの4番目には、経由地wまでの経路R(r,r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って経由地wまでにかかる時間がTである。探索結果リストの5番目には、経由地wまでの経路R(r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って経由地wまでにかかる時間がTである。
【0407】
探索結果リストの6番目には、目的地gまでの経路R(r,r,w,r,r)が登録され、この経路Rが選択される確率はPで、経路Rを使って目的地gまでにかかる時間がTである。探索結果リストの7番目には、この経路Rが選択される確率はPで、目的地gまでの経路R(r,r10,r11)が登録され、経路Rを使って目的地gまでにかかる時間がTである。
【0408】
目的地または経由地まで、各経路が選択される確率は、上述した式(13)により計算される。さらに、目的地までの経路が複数存在する場合、その目的地までの複数の経路の選択確率の和が、目的地の到達確率となる。
【0409】
従って、図56の例では、目的地gへ行くには、経路Rを利用する場合と、経路Rを利用する場合があり得るので、目的地gの到達確率は、は(P+P)となる。同様に、目的地gへ行くには、経路Rを利用する場合と、経路Rを利用する場合があり得るので、目的地gの到達確率は、は(P+P)となる。なお、目的地gの到達確率は、経路Rが選択される確率Pと同一である。
【0410】
[予測ポストプロセス部34の処理]
次に、予測ポストプロセス部34が行う処理について説明する。
【0411】
目的地または経由地まで、選択された経路で移動したときにかかる時間の求め方について説明する。
【0412】
例えば、現在時刻tの現在地が状態sy1であり、時刻(t,t,・・・,t)における決定された経路が(sy1,sy2,・・・,syg)であるとする。換言すれば、決定された経路の状態siのノード番号iが(y,y,・・・,y)であるとする。以下、簡単のため、位置に相当する状態siを、単に、そのノード番号iで表わす場合もある。
【0413】
現在時刻tでの現在地yは、現在地ノード推定部41により確定しているので、現在時刻tの現在地がyである確率Py1(t)は、
y1(t)=1である。また、現在時刻tにy以外の他の状態にいる確率は0である。
【0414】
一方、所定の時刻tにノード番号yにいる確率Pyn(t)は、
【数20】

で表すことができる。式(29)の右辺第一項は、もともとその位置yにいて、自己遷移した場合の確率を表し、右辺第二項は、1つ前の位置yn−1から位置yに遷移してきた場合の確率を表している。式(29)では、経路の選択確率の計算とは異なり、学習により得られた状態遷移確率aijがそのまま利用される。
【0415】
目的地yへ到達するときの時刻tの予測値<t>は、「その直前の時刻tg−1に目的地yの1つ前の位置yg−1にいて、時刻tに目的地yに移動する確率」を用いて、
【数21】

と表すことができる。
【0416】
即ち、予測値<t>は、現在時刻から、「その直前の時刻tg−1に状態sygの1つ前の状態syg−1にいて、時刻tに状態sygに移動するとき」までの時間の期待値で表される。
【0417】
以上より、所定の目的地または経由地まで、選択された経路で移動したときにかかる時間は、上述した式(30)の予測値<t>により求められる。
【0418】
図56の例を使用して、目的地までの経路が探索された場合に、代表経路として選択する代表経路選択処理について説明する。
【0419】
図56のような探索結果リストが得られた場合、探索結果リストには、選択確率が高いものから順に(上位に)登録されるので、選択確率が上位であり、目的地も異なる、探索結果リストの1番目乃至3番目が予測結果として出力される。即ち、経目的地gとその経路R、目的地gとその経路R、目的地gとその経路Rが、目的地とその代表経路として選択される。
【0420】
次に、探索結果リストの4番目および5番目は経由地までの経路であるためスキップされ、探索結果リストの6番目の、目的地gへ到達するための経路Rを代表経路とするかが検討される。この経路Rは、既に代表経路として選択されている、同一の目的地gの経路Rには含まれていない経由地wを利用するものとなっている。したがって、目的地gへ到達するための経路Rも、代表経路として選択される。
【0421】
次に、探索結果リストの7番目の、目的地gへ到達するための経路Rを代表経路とするかが検討される。この経路Rは、既に代表経路として選択されている、同一の目的地gと同じく、所定の経由地を経由しないものとなっている。したがって、目的地gへ到達するための経路Rは、代表経路として選択されない。
【0422】
このように、代表経路選択処理では、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路は、同一目的地であっても、予測結果として提示することができる。
【0423】
なお、探索結果リストの6番目の、目的地gへ到達するための経路Rは、[背景技術]に示した先願2の方法では、経由地wで探索が終了されていた。しかしながら、予測システム1によれば、経由地wで終了することなく、経由地wを利用して目的地gへ到達する経路まで探索することが可能となっている。
【0424】
予測システム1によれば、学習により得られた状態ノードに、目的地と経由地を区別して属性を付与することで、途中の経由地を目的地として予測することを防止することができる。また、同一目的地への経路が複数探索された場合、ほぼ同一の経路を通る、似たような経路は提示せず、ユーザにとって有益と考えられる、異なる経由地を通る経路を提示することができる。
【0425】
図57は、予測ポストプロセス部34が行う代表経路選択処理のフローチャートである。
【0426】
初めに、ステップS301において、予測ポストプロセス部34は、目的地経由地予測部42で作成された探索結果リストから、経由地までの経路を除外し、目的地のみの探索結果リストである目的地リストを生成する。
【0427】
ステップS302において、予測ポストプロセス部34は、目的地リストを目的地別に並び替えた目的地別目的地リストに変更する。このとき、予測ポストプロセス部34は、同一の目的地内における順位を変えないように目的地別目的地リストを生成する。
【0428】
ステップS303において、予測ポストプロセス部34は、目的地ごとの到達確率を算出する。目的地までの経路が1つしかない場合には、その経路の選択確率が到達確率となり、目的地まで複数の経路が存在する場合には、複数の選択確率(生起確率)の和が、その目的地の到達確率となる。
【0429】
ステップS304において、予測ポストプロセス部34は、代表経路の選択に経由地を考慮するかを判定する。ステップS304で、経由地を考慮しないと判定された場合、処理はステップS305に進み、予測ポストプロセス部34は、目的地別に、最上位の経路を、各目的地の代表経路として選択し、処理を終了する。その結果、目的地まで複数の経路が存在する場合には、選択確率の高い目的地までの経路が、各目的地の代表経路とされ、その所要時間が、目的地までの所要時間として提示される。なお、目的地が多数ある場合には、上位から、予め設定した個数の目的地のみを提示するようにさせることができる。
【0430】
一方、ステップS304で、経由地を考慮すると判定された場合、処理はステップS306に進み、予測ポストプロセス部34は、目的地別目的地リストを、経由地なしの目的地別目的地リストと、経由地ありの目的地別目的地リストに分類する。
【0431】
そして、ステップS307において、予測ポストプロセス部34は、経由地なしの目的地別目的地リストから、目的地別に、最上位の経路を代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地なしの経路が決定される。
【0432】
次に、ステップS308において、予測ポストプロセス部34は、経由地ありの目的地別目的地リストを、さらに、経由地別に分類する。
【0433】
ステップS309において、予測ポストプロセス部34は、経由地別の、経由地ありの目的地別目的地リストから、目的地別に、各経由地の最上位の経路を、代表経路として選択する。これにより、代表経路としての、目的地ごとの経由地ありの経路が決定される。その結果、目的地までの経路として、経由地なしの経路と経由地ありの経路が存在する場合には、その両方が、各目的地の代表経路とされ、それぞれの所要時間が、目的地までの所要時間として提示される。
【0434】
以上により、代表経路選択処理は終了する。このように、目的地への経路が複数存在する場合、生起確率の上位を複数提示するよりも、経由地によって分類して提示する方が、ユーザが実際に感じる予測に近いものとすることができる。
【0435】
[予測ブロック13全体の処理]
図58のフローチャートを参照して、予測ブロック13全体の処理について説明する。
【0436】
初めに、ステップS321において、バッファリング部31は、予測処理のため、リアルタイムに取得される移動履歴データをバッファリングする。
【0437】
ステップS322において、予測プリプロセス部32は、予測プリプロセス処理を実行する。具体的には、学習プリプロセス部22が行う学習プリプロセス処理と同様の、移動履歴データの接続および分割の処理、移動履歴データの明らかな異常を除去する処理、および、欠落データを補完する処理を実行する。但し、移動履歴データを分割する際の基準となる滞在閾値時間は、学習プリプロセス処理と異なる時間であってもよい。
【0438】
ステップS323において、予測メインプロセス部33は、学習ブロック11の学習により得られたユーザ活動モデルのパラメータを、ユーザ別モデルパラメータ記憶部12から取得する。このパラメータを取得する処理は、図33の目的地を予測する処理とは別に、予め実行するようにしてもよい。
【0439】
ステップS324において、予測メインプロセス部33の現在地ノード推定部41は、学習ブロック11の学習により得られたパラメータを用いたユーザ活動モデルにより、ユーザの現在地に対応する状態ノード(現在地ノード)を推定する。より具体的には、現在地ノード推定部41は、学習ブロック11の学習により得られたパラメータを用いたユーザ活動モデルにより、移動履歴データに対応するノード系列データを算出する。そして、現在地ノード推定部41は、ノード系列データの最後の状態ノードを現在地ノードとする。ノード系列データの算出には、ビタビアルゴリズムが採用される。
【0440】
ステップS325において、予測メインプロセス部33の目的地経由地予測部42は、図53を参照して説明した、現在地ノード以降のツリー探索処理を実行する。ツリー探索処理と同時に、目的地および経由地までの経路(ノード系列)の生起確率も、式(28)により求められる。
【0441】
ステップS326において、予測ポストプロセス部34は、図57を参照して説明した、代表経路の選択処理を実行する。
【0442】
ステップS327において、予測ポストプロセス部34は、上述した式(30)により、選択された各代表経路の所要時間を算出する。
【0443】
ステップS328において、予測ポストプロセス部34は、予測した目的地までの代表経路、到達確率、および所要時間を予測結果として出力して、処理を終了する。
【0444】
以上のように、予測ブロック13の処理では、推定された目的地ノードおよび経由地ノード並びに現在地ノードについての情報と、学習により得られたパラメータで表現されるユーザ活動モデルとを用いて、ユーザの現在地から目的地までの経路が探索される。学習により得られた状態ノードに目的地と経由地の属性が付与されているので、経由地を目的地として予測することを防止することができる。
【0445】
また、学習により得られた状態ノードに目的地と経由地の属性が付与されているので、同一目的地への経路であっても、経由地なしの経路と、経由地ありの経路を代表経路として出力することができる。
【0446】
[データ処理結果の例]
図59乃至図63に、上述した本発明を適用した予測システム1の学習メインプロセス部23で、あるユーザの移動履歴データを学習させたときの学習処理結果を示す。
【0447】
図59は、本発明(学習メインプロセス部23)によるモデル化と、従来のHMMによるモデル化の状態ノードの学習結果を比較した図である。
【0448】
図59Aは、本発明によるモデル化、即ち、図31に示したように、一つの状態ノードが連続するサンプル二つ分を必ず反映するようにモデル化した学習モデルによる学習結果を示している。
【0449】
図59Bは、従来のHMMによるモデル化した学習モデルによる学習結果である。
【0450】
図59Aおよび図59Bにおいて、楕円は、各状態ノードが表すデータの分布(正規分布)の等高線を表している。ここでは、楕円の中心が各状態ノードの緯度経度の平均値であり、また、楕円の大きさが各状態ノードの緯度経度の分散値に比例している。
【0451】
図59Bの従来のモデル化では、状態ノードの分散は、サンプルの中心に収束する(下限に到達している)が、図59Aの本発明のモデル化では、ノードの分散は、サンプルとサンプルの間を覆うように、長く伸びている。この結果、図59Bの従来のモデル化では、全体の状態ノードをみても、サンプル付近しか覆っていない部分があるが、図59Aの本発明のモデル化では、経路全体を覆っていることがわかる。
【0452】
図59Aおよび図59Bでは、分散のパラメータは、時刻、緯度、経度の各次元でそれぞれ用意されている。このような場合、移動履歴データは、長軸が、緯度、経度に平行な楕円で表される状態ノードでモデル化される。すると、移動方向が、緯度、経度のいずれかに平行な場合は、経路をモデル化して、経路以外の領域以外は覆わなくなる。しかし、移動方向が斜めの場合は、経路以外の余分な領域を多く覆うようになる。そこで、余分な領域をモデル化することを極力避けたい場合には、分散のパラメータに共分散を用いるようにすればよい。この場合、移動履歴データは、斜めの楕円による状態ノードでモデル化されるようになる。その結果、移動方向が斜めの場合でも、経路以外の余分な領域を覆わずにモデル化ができる。
【0453】
図60は、1回目に学習させた移動経路とその学習結果を示している。移動履歴データは、ユーザが、自宅から、ある目的地に出かけた際に、15行間隔でサンプリングした3次元データである。
【0454】
図60左側の地図上には、予測システム1に学習させた移動履歴データが黒丸で示され、黒丸の周辺に位置する楕円が学習結果の状態ノードを示している。この学習結果を参照しても、状態ノードはサンプル間の経路をモデル化するように学習されていることが分かる。
【0455】
この移動履歴データは、学習メインプロセス部23の1回目の学習に使用されたデータであるので、既知未知判定部201の既知未知判定処理では、未知の移動履歴データと判定されるはずである。
【0456】
図60右側の上下に並んだ2図は、図60左側の移動履歴データの既知未知判定結果を示している。上段の図は、飽和対数尤度を示し、下段の図は、ビタビ判定による既知未知判定結果を示している。既知未知判定結果は、未知に対応する”−1”が継続的に出力されており、正確に未知の経路と学習されていることを示している。
【0457】
図61は、ユーザが図60の移動経路を通って到達した目的地から、同一経路を通って帰ったときの帰路の移動履歴データを学習させたときの学習結果を示している。
【0458】
この場合、ユーザが移動した経路の各場所は、ユーザが知っている場所であるから、既知未知判定結果は、一見、既知とされるところである。しかし、行動予測を行なう上では、ユーザの意図が重要で、同じ場所でも行きか、帰りかのユーザの意図を正しく区別してモデル化を行う必要がある。従って、図61の帰路の移動履歴データに対しては、既知未知判定において、未知と判定されなければならない。
【0459】
図61右側の既知未知判定結果を参照すると、未知に対応する”−1”が継続的に出力されており、学習メインプロセス部23の既知未知判定部201が未知の経路と正確に判定していることを示している。
【0460】
図62は、ユーザが全く異なる経路を通って図60と同一の目的地へ移動した場合の移動履歴データの学習結果を示している。
【0461】
図62左側の地図上の、横方向の楕円の連なりが、図60で示した経路の学習結果を、縦方向の大きめの楕円の連なりが、全く異なる経路による学習結果を示している。なお、地図の縮尺は、図60と図62で異なる。
【0462】
図62右側の既知未知判定結果を参照すると、未知に対応する”−1”が継続的に出力されており、全く異なる経路の移動履歴データについて、学習メインプロセス部23の既知未知判定部201が未知の経路と正確に判定していることを示している。
【0463】
図63は、さらに別の移動経路を学習させたときの学習結果を示している。
【0464】
具体的には、図63は、あるユーザの自宅から勤務地までの移動経路を、第1の経路を通る1回目の学習をさせた後、第2の経路を通る2回目の学習をさせたときの学習結果を示している。
【0465】
ここで、第1の経路と、第2の経路とは、自宅から、途中の経由地までの経路が、寄り道をせずに移動した場合と、所定の場所へ寄り道をして移動した場合の違いである。そして、途中の経由地から目的地である勤務地までの後半の移動経路は同一である。
【0466】
図63右側の既知未知判定結果を参照すると、移動経路の前半部分には未知に対応する”−1”が出力されており、移動経路の後半部分には既知に対応する”1”が出力されている。これは、自宅から途中の経由地までの経路を「未知」と、途中の経由地から勤務地までの経路を「既知」と判定していることを示している。従って、学習メインプロセス部23の既知未知判定部201が既知と未知の経路を正確に区別して学習できていることがわかる。
【0467】
また、図63左側の地図上に表示されている状態ノードでは、モノクロ表示ではうまく区別できないが、1回目の学習データの経路を覆う状態ノードには、2回目の学習で新たに追加された状態ノードが含まれていない。一方、2回目の学習データの経路を覆う状態ノードは、全て2回目の学習で新たに追加された状態ノードとなっている。即ち、既知の経路の移動履歴データについては、トポロジーの変更がなく、既存モデルのパラメータの更新により学習し、未知の経路の移動履歴データについてのみ、新たな状態ノードが追加されている。従って、学習メインプロセス部23の学習では、無駄に状態ノードを追加することなく、新たな移動履歴データを学習モデルに反映させ、過不足のない学習モデルのモデル化を行うことができる。換言すれば、未知の経路の移動履歴データが得られたときの差分学習をより簡単に行うことができる。
【0468】
[コンピュータの構成例]
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【0469】
図64は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。
【0470】
コンピュータにおいて、CPU(Central Processing Unit)321,ROM(Read Only Memory)322,RAM(Random Access Memory)323は、バス324により相互に接続されている。
【0471】
バス324には、さらに、入出力インタフェース325が接続されている。入出力インタフェース325には、入力部326、出力部327、記憶部328、通信部329、ドライブ330、およびGPSセンサ331が接続されている。
【0472】
入力部326は、キーボード、マウス、マイクロホンなどよりなる。出力部327は、ディスプレイ、スピーカなどよりなる。記憶部328は、ハードディスクや不揮発性のメモリなどよりなる。通信部329は、ネットワークインタフェースなどよりなる。ドライブ330は、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブル記録媒体332を駆動する。上述のセンサデバイスとしてのGPSセンサ331は、現在地の位置(緯度および経度)のデータと、そのときの時刻からなる3次元データを出力する。
【0473】
以上のように構成されるコンピュータでは、CPU321が、例えば、記憶部328に記憶されているプログラムを、入出力インタフェース325及びバス324を介して、RAM323にロードして実行することにより、上述した一連の処理が行われる。
【0474】
コンピュータ(CPU321)が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブル記録媒体332に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【0475】
コンピュータでは、プログラムは、リムーバブル記録媒体332をドライブ330に装着することにより、入出力インタフェース325を介して、記憶部328にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部329で受信し、記憶部328にインストールすることができる。その他、プログラムは、ROM322や記憶部328に、あらかじめインストールしておくことができる。
【0476】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【0477】
なお、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる場合はもちろん、必ずしも時系列的に処理されなくとも、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで実行されてもよい。
【0478】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【0479】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【0480】
1 予測システム, 11 学習ブロック, 13 予測ブロック, 22 学習プリプロセス部, 23 学習メインプロセス部, 24 学習ポストプロセス部, 25 目的地経由地検出部, 32 予測プリプロセス部, 33 予測メインプロセス部, 34 予測ポストプロセス部, 201 既知未知判定部, 202 新規モデル生成部, 203 新規モデル結合部, 204 パラメータ更新部, 205 モデル整理部, 221 既存モデル構築部, 222 未知状態ノード追加部, 223 状態ノード推定部, 224 サンプル別尤度計算部, 225 既知未知モデル記憶部, 226 既知未知判定部, 227 既知未知ポスト処理部, 243 新規モデル学習部, 244 ノード系列判定部, 245 パラメータ再計算部

【特許請求の範囲】
【請求項1】
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段と
を備え、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段と
を有し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
データ処理装置。
【請求項2】
前記新規モデル生成手段は、前記確率モデルとして、一つの状態ノードが前記ユーザの移動履歴データの少なくとも2つの連続するサンプルを反映するモデルを採用する
請求項1に記載のデータ処理装置。
【請求項3】
前記一つの状態ノードが前記ユーザの移動履歴データの少なくとも2つの連続するサンプルを反映するモデルは、一つの状態ノードへの遷移時に、前記ユーザの移動履歴データの少なくとも2つの連続するサンプルを同時に出力するモデルである
請求項2に記載のデータ処理装置。
【請求項4】
前記一つの状態ノードが前記ユーザの移動履歴データの少なくとも2つの連続するサンプルを反映するモデルは、さらに、left-to-rightの制約を設定したモデルである
請求項3に記載のデータ処理装置。
【請求項5】
前記新規モデル生成手段は、Baum-Welchの最尤推定法により、前記確率モデルのパラメータを求める
請求項1に記載のデータ処理装置。
【請求項6】
前記新規モデル生成手段は、前記Baum-Welchの最尤推定法により、前記未知の経路の移動履歴データに対応する前記新規モデルのパラメータを求め、前記未知の経路の移動履歴データを前記新規モデルの状態ノードに変換したノード系列データを生成し、各状態ノードの状態頻度と遷移頻度を計算して、前記未知の経路の移動履歴データの前記新規モデルのパラメータに対応する前記ノード系列データのパラメータを求める
請求項5に記載のデータ処理装置。
【請求項7】
前記既知未知判定手段は、前記新たな学習用データが既知の経路の移動履歴データであると判定した場合、前記既知の経路の移動履歴データを前記既存モデルの状態ノードに変換したノード系列データを生成し、
前記パラメータ更新手段は、前記既知の経路の移動履歴データを前記既存モデルの状態ノードに変換したノード系列データから、各状態ノードの状態頻度と遷移頻度を更新し、前記既存モデルのパラメータとしての前記ノード系列データのパラメータを更新する
請求項6に記載のデータ処理装置。
【請求項8】
前記既知未知判定手段は、前記既存モデルに未知の経路の移動履歴データを引き受ける一つの状態ノードを追加した未知状態追加モデルにより、前記新たな学習用データとしての移動履歴データに対応する状態ノードを認識し、前記新たな学習用データとしての移動履歴データに対応する前記未知状態追加モデルのノード系列データの観測尤度を求め、求められた観測尤度の大きさから、既知または未知の判定を行う
請求項6に記載のデータ処理装置。
【請求項9】
前記既存モデルに追加される、未知の経路の移動履歴データを引き受ける一つの状態ノードの、前記既知モデルの各状態ノードとの間の遷移確率は、既知モデルの状態ノード間の遷移確率のどれよりも低く、分散値は、移動履歴データの取り得る範囲を網羅する値である
請求項8に記載のデータ処理装置。
【請求項10】
前記既知未知判定手段は、前記未知状態追加モデルのノード系列データの観測尤度に対し、既知と未知の二状態で構成され、自己遷移する確率が大きいHMMを用いてビタビ判定を行うことにより、既知または未知の判定を行う
請求項8に記載のデータ処理装置。
【請求項11】
前記既知未知判定手段は、前記未知の経路の移動履歴データが前記既知の経路の移動履歴データと接続されている場合、その接続先の前記既知の経路の移動履歴データに対応する状態ノードも出力し、
前記新規モデル結合手段は、前記既存モデルがM個、前記新規モデルがN個の状態ノードからなる場合、前記更新モデルの遷移確率を定義する(M+N)行(M+N)列の遷移確率テーブルを生成し、
生成した前記遷移確率テーブルの第1行第1列から第M行M列の左上領域の各要素が、前記既存モデルの状態ノードの遷移確率に対応し、
生成した前記遷移確率テーブルの第(M+1)行第(M+1)列から第(M+N)行(M+N)列の右下領域の各要素が、前記新規モデルの状態ノードの遷移確率に対応し、
生成した前記遷移確率テーブルの第1行第(M+1)列から第M行(M+N)列の右上領域の各要素が、前記新規モデルが前記既存モデルのノード系列データの後に接続されるときの接続先の状態ノードに対応し、
生成した前記遷移確率テーブルの第(M+1)行第1列から第(M+N)行M列の左下領域の各要素が、前記新規モデルの後に前記既存モデルのノード系列データが接続されるときの接続先の状態ノードに対応する
請求項1に記載のデータ処理装置。
【請求項12】
前記移動履歴データを構成する各3次元データに対し、少なくとも滞在状態または移動状態を識別する移動属性識別手段をさらに備え、
前記目的地経由地推定手段は、前記滞在状態が所定の閾値時間以上継続する前記移動履歴データに対応する前記状態ノードを前記目的地ノードに推定し、前記滞在状態の継続時間が前記所定の閾値時間未満である前記移動履歴データに対応する前記状態ノードを前記経由地ノードに推定する
請求項1に記載のデータ処理装置。
【請求項13】
ユーザの移動履歴データを処理するデータ処理装置の、
学習手段が、学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求め、
目的地経由地推定手段が、求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定し、
現在地推定手段が、前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定し、
探索手段が、推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索し、
算出手段が、探索された前記目的地への到達確率と所要時間を算出する
ステップを含み、
前記学習手段のステップでは、
既知未知判定手段が、前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定し、
パラメータ更新手段が、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新し、
新規モデル生成手段が、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求め、
新規モデル結合手段が、前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成し、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段のステップでは、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
データ処理方法。
【請求項14】
コンピュータを、
学習用データとして取得されるユーザの移動履歴データを、ユーザの活動を表す確率モデルとして表したときの確率モデルのパラメータを求める学習手段と、
前記学習手段により求められた前記パラメータを用いた前記確率モデルの状態ノードのうち、移動の目的地および経由地に相当する目的地ノードおよび経由地ノードを推定する目的地経由地推定手段と、
前記学習用データとは別の、現在から所定時間以内の前記ユーザの移動履歴データを、学習により得られた前記パラメータを用いた前記確率モデルに入力し、前記ユーザの現在地に相当する現在地ノードを推定する現在地推定手段と、
推定された前記目的地ノードおよび経由地ノード並びに前記現在地ノードについての情報と、学習により得られた前記確率モデルとを用いて、ユーザの現在地から目的地までの経路を探索する探索手段と、
探索された前記目的地への到達確率と所要時間を算出する算出手段
として機能させ、
前記学習手段は、
前記確率モデルのパラメータを一旦求めた後、新たな学習用データとしての移動履歴データが供給された場合、前記新たな学習用データが、既知の経路の移動履歴データであるか、または、未知の経路の移動履歴データであるかを判定する既知未知判定手段と、
前記既知未知判定手段において、前記新たな学習用データが前記既知の経路の移動履歴データであると判定された場合、既に求めた前記確率モデルである既存モデルのパラメータを更新するパラメータ更新手段と、
前記既知未知判定手段において、前記新たな学習用データが前記未知の経路の移動履歴データであると判定された場合、前記未知の経路の移動履歴データに対応する新規モデルとしての確率モデルのパラメータを求める新規モデル生成手段と、
前記既存モデルのパラメータと、前記新規モデルのパラメータを合成することで、前記既存モデルと前記新規モデルを結合した更新モデルを生成する新規モデル結合手段
としての機能を含み、
前記目的地経由地推定手段、前記現在地推定手段、前記前記探索手段、および前記算出手段では、前記確率モデルが前記新たな学習用データにより更新された場合、更新後の前記確率モデルを用いた処理が行われる
ためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate

【図38】
image rotate

【図39】
image rotate

【図40】
image rotate

【図41】
image rotate

【図42】
image rotate

【図43】
image rotate

【図44】
image rotate

【図45】
image rotate

【図46】
image rotate

【図47】
image rotate

【図48】
image rotate

【図49】
image rotate

【図50】
image rotate

【図51】
image rotate

【図52】
image rotate

【図53】
image rotate

【図54】
image rotate

【図55】
image rotate

【図56】
image rotate

【図57】
image rotate

【図58】
image rotate

【図59】
image rotate

【図60】
image rotate

【図61】
image rotate

【図62】
image rotate

【図63】
image rotate

【図64】
image rotate


【公開番号】特開2012−8659(P2012−8659A)
【公開日】平成24年1月12日(2012.1.12)
【国際特許分類】
【出願番号】特願2010−141946(P2010−141946)
【出願日】平成22年6月22日(2010.6.22)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】