(57)【要約】【課題】計算量を抑えて、時空間データを分析することができるようにする。【解決手段】時空間データマイニング装置2000は、測位データについて、移動体が観測された地点を含む地理空間エリアを特定する地理空間エリア群データ生成部12と、測位データが時空間データに追加され、追加された測位データについて特定された地理空間エリアが分析対象となっている地理空間エリアの集合に含まれないと判定されたとき、特定された地理空間エリアを分析対象となっている地理空間エリアの集合に追加する分析対象地理空間エリア群データ生成部2111と、を含んで構成されている。【選択図】図１
2018112774.tif 000002
【特許請求の範囲】
【請求項１】
地理空間を複数の地理空間エリアに分割した地理情報空間上において、移動体に備え付けられた測位装置によって得られる位置情報と、前記測位装置により位置情報が計測された時刻との組からなる一連の測位データから構成される時空間データを分析する時空間データマイニング装置において、
前記測位データについて、前記測位データの位置情報より、前記移動体が観測された地点を含む地理空間エリアを特定する地理空間エリア群データ生成手段と、
前記測位データが前記時空間データに追加されたとき、前記測位データについて特定された地理空間エリアが分析対象となっている地理空間エリアの集合に含まれるか否かを判定する分析対象地理空間エリア判定手段と、
前記追加された測位データについて特定された地理空間エリアが分析対象となっている地理空間エリアの集合に含まれないと判定されたとき、前記特定された地理空間エリアを分析対象となっている地理空間エリアの集合に追加する分析対象地理空間エリア群データ生成手段と、
を有することを特徴とする時空間データマイニング装置。
【請求項２】
決められた時間帯で、指定された移動体が、移動元として指定された分析対象の地理空間エリアから移動先として指定された分析対象の地理空間エリアへ移動したイベントの発生回数を示す移動総数を求める移動総数計数手段と、
測位データＰが前記時空間データに追加されたとき、前記測位データＰと同一の移動体の時空間データに対して前記測位データＰの直前に記録された測位データＱを特定する直前測位データ特定手段と、
前記測位データＰの前記移動体に対し、前記測位データＱについて特定される地理空間エリアと前記測位データＰについて特定される地理空間エリアとが同一の場合、前記測位データＱの計測時刻までに同一の地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算し、
前記測位データＱについて特定される地理空間エリアＡiと前記測位データＰについて特定される地理空間エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアＡjがすでに分析対象となっている場合、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算すると共に、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡjへ移動した移動総数に、１を加算し、
前記測位データＱについて特定される地理空間エリアＡiと前記測位データＰについて特定される地理空間エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアＡjが分析対象となっていない場合、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算すると共に、前記地理空間エリアＡiから前記地理空間エリアＡjへ移動した移動総数を、１に設定し、前記地理空間エリアＡi以外の前記地理空間エリアの各々から前記地理空間エリアＡjへ移動した移動総数を、０に設定するユーザ毎移動イベント数データ生成手段と、
分析対象となっている地理空間エリアの組み合わせの各々について、一方の地理空間エリアから他方の地理空間エリアへの個々の移動体の移動総数を、全ての移動体において加算して全移動総数を求める移動イベント数データ生成手段と、
分析対象となっている地理空間エリアの組み合わせの各々について、一方の地理空間エリアから分析対象となっている地理空間エリアの各々への全移動総数を加算した値を求め、一方の地理空間エリアから他方の地理空間エリアへの全移動総数を、前記求めた全移動総数の加算値で割った値を、一方の地理空間エリアから他方の地理空間エリアへ移動する確率として算出し、前記算出された確率を要素とする推移行列データを生成する推移行列データ生成手段と、
前記推移行列データを指定回数掛け合わせたものを用いて、分析対象となっている地理空間エリアの各々に、指定された移動体が移動する確率を算出するユーザ移動地理空間エリア出力手段と、
全ての移動体についての時空間データの測位データについて特定された地理空間エリアから求められる、分析対象となっている各地理空間エリアに存在する移動体数と、分析対象となっている全ての地理空間エリアにおける移動体数の総数を求め、分析対象となっている各地理空間エリアについて、前記移動体数を前記移動体数の総数で割った値を、前記分析対象となっている地理空間エリアに移動体が存在する比率として算出する分析対象地理空間エリア滞在ユーザ数生成手段と、
前記算出された比率からなるベクトルに、前記推移行列データを指定回数掛け合わせたものを掛け合わせることにより、将来時刻における、分析対象となっている地理空間エリアの各々に移動体が存在する比率を算出する予測分析対象地理空間エリア滞在率データ生成手段と、
を更に有する請求項１記載の時空間データマイニング装置。
【請求項３】
木状に構成された論理エリアであって、親論理エリアは、１つ以上の子論理エリアから構成され、子論理エリアに対応する全ての地理空間エリアにおいて地理的に重なる部分はなく、子論理エリアの集合により構成される地理空間エリア群は親論理エリアの地理空間エリア群と一致し、再下位層にある論理エリアである葉論理エリアは１つの地理空間エリアと同一視できる、論理エリアのトポロジーを構成する論理エリアトポロジーデータ生成手段と、
分析対象となる論理エリア数の最大値を設定する分析対象最大論理エリア数データ生成手段と、
指定された論理エリアに対する子論理エリアを求める子論理エリア算出手段と、
指定された論理エリアに対する親論理エリアを求める親論理エリア算出手段と、を更に含み、
前記分析対象地理空間エリア判定手段は、前記測位データが前記時空間データに追加されたとき、追加された測位データの座標情報から前記測位データが観測された地点を含む地理空間エリアAPを特定し、前記地理空間エリアAPに対応する葉論理エリアを求め、前記葉論理エリアが、分析対象となっている葉論理エリアの集合に含まれるか否かを判定し、
前記分析対象地理空間エリア群データ生成手段は、前記追加された測位データについて特定された葉論理エリアが前記分析対象となっている葉論理エリアの集合に含まれないと判定されたとき、前記葉論理エリアを前記分析対象となっている葉論理エリアの集合に追加し、
前記時空間データマイニング装置は、
前記追加された測位データについて特定された葉論理エリアに対する親論理エリアを求め、統合候補となっている論理エリアの集合に前記親論理エリアを追加する測位データ追加処理手段と、
指定された論理エリアの価値を算出する論理エリア価値計算手段と、
統合候補となっている論理エリアの集合のうち、最小の論理エリアの価値を持つ論理エリアＧを求め、前記論理エリアＧの子の論理エリア群{child(Ｇ)}を求め、前記子の論理エリア群{child(Ｇ)}が、分析対象となっている論理エリアの集合に含まれている場合は、前記子の論理エリア群{child(Ｇ)}を前記分析対象となっている論理エリアの集合から削除し、前記分析対象となっている論理エリアの集合に、前記最小の論理エリアの価値を持つ論理エリアＧを追加し、前記統合候補となっている論理エリアの集合から前記最小の論理エリアの価値を持つ論理エリアＧを削除し、前記最小の論理エリアの価値を持つ論理エリアＧの親論理エリアpar(Ｇ)を、前記統合候補となっている論理エリアの集合に追加する論理エリア統合処理手段と、
前記分析対象となっている論理エリアの集合のうち、最大の論理エリアの価値を持つ論理エリアＧを求め、前記分析対象となっている論理エリアの集合から前記最大の論理エリア価値を持つ論理エリアＧを削除し、前記最大の論理エリア価値を持つ論理エリアＧの子の論理エリア群{child(Ｇ)}を求め、前記子の論理エリア群{child(Ｇ)}に含まれる各子論理エリアにおいて、前記論理エリアのトポロジーを使って、該当する地理空間エリアを求め、前記時空間データを使って、前記地理空間エリアに測位データが観測されているかを調べ、前記測位データが存在する場合、前記子論理エリアを、前記分析対象となっている論理エリアの集合に追加する論理エリア分割処理手段と、
前記測位データが前記時空間データに追加されたとき、
前記分析対象となっている論理エリアの集合の要素は、前記分析対象となる論理エリア数の最大値以下であり、かつ、前記統合候補となっている論理エリアの集合内の論理エリアで最小の論理エリアの価値ρmin(C)が、前記分析対象となっている論理エリアの集合内の論理エリアで最大の論理エリアの価値ρmax(F)より大きいと判定されるまで、前記論理エリア統合処理手段による処理、及び前記論理エリア分割処理手段による処理を繰り返させる論理エリア構成最適判定手段と、を更に有する請求項１記載の時空間データマイニング装置。
【請求項４】
決められた時間帯で、指定された移動体が、移動元として指定された分析対象の葉論理エリアから移動先として指定された分析対象の葉論理エリアへ移動したイベントの発生回数を示す移動総数を求める移動総数計数手段と、
測位データＰが前記時空間データに追加されたとき、前記測位データＰと同一の移動体の時空間データに対して前記測位データＰの直前に記録された測位データＱを特定する直前測位データ特定手段と、
前記測位データＰの前記移動体に対し、前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアが同一の場合、前記測位データＱの計測時刻までに同一の葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算し、
前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアＡiと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjがすでに分析対象となっている場合、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算すると共に、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡjへ移動した移動総数に、１を加算し、
前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアＡiと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが分析対象となっていない場合、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算すると共に、前記葉論理エリアＡiから前記葉論理エリアＡjへ移動した移動総数を、１に設定し、前記葉論理エリアＡi以外の前記葉論理エリアの各々から前記葉論理エリアＡjへ移動した移動総数を、０に設定するユーザ毎葉論理エリア移動イベント数データ生成手段と、
指定された論理エリアを起点とした枝において、葉論理エリアの集合を求める枝上葉論理エリア算出手段と、
前記移動体の各々に対し、分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアについて求められる葉論理エリアの集合の何れかの葉論理エリアから、他方の論理エリアについて求められる葉論理エリアの集合の何れかの葉論理エリアへの移動総数を、一方の論理エリアから他方の論理エリアへの移動総数として設定するユーザ毎論理エリア移動イベント数データ生成手段と、
前記分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアから他方の論理エリアへの個々の移動体の移動総数を、全ての移動体において加算して全移動総数を求める論理エリア移動イベント数データ生成手段と、
前記分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアから分析対象となっている論理エリアの各々への全移動総数を加算した値を求め、一方の論理エリアから他方の論理エリアへの全移動総数を、前記求めた全移動総数の加算値で割った値を、一方の論理エリアから他方の論理エリアへ移動する確率として算出し、前記算出された確率を要素とする推移行列データを生成する推移行列データ生成手段と、
前記推移行列データを指定回数掛け合わせたものを用いて、前記分析対象となっている論理エリアの各々に、指定された移動体が移動する確率を算出するユーザ移動地理空間エリア出力手段と、
全ての移動体についての時空間データの測位データについて特定された論理エリアから求められる、前記分析対象となっている各論理エリアに存在する移動体数と、前記分析対象となっている全ての論理エリアにおける移動体数の総数を求め、前記分析対象となっている各論理エリアについて、前記移動体数を前記移動体数の総数で割った値を、前記分析対象となっている論理エリアに移動体が存在する比率として算出する分析対象論理エリア滞在ユーザ数生成手段と、
前記算出された比率からなるベクトルに、前記推移行列データを指定回数掛け合わせたものを掛け合わせることにより、将来時刻における、分析対象となっている論理エリアの各々に移動体が存在する比率を算出する予測論理エリア滞在率データ生成手段と、
を更に有する請求項３記載の時空間データマイニング装置。
【請求項５】
前記論理エリア価値計算手段は、指定された論理エリアの価値として、前記論理エリアで発生した測位データ数を算出する請求項３又は４記載の時空間データマイニング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動体の位置情報とその計測時刻のデータから構成される時空間データから有益な情報を分析する時空間データマイニング装置に関する。
【背景技術】
【０００２】
＜時空間データ＞
近年、携帯電話やスマートフォーンなどの通信端末に内蔵されているGPS（Global Positioning System）の情報や、通信端末と電波のやり取りを行っている通信キャリアの基地局もしくはWi-Fiの位置情報を使って、通信端末の位置をリアルタイムに計測することが可能となった（例えば、非特許文献７参照）。ある物体の位置をリアルタイムに計測し適切な座標に変換する機能を有する装置を、測位装置とよぶ。人、動物、荷物のような移動体に測位装置を保持させることにより、移動体の位置を容易に計測することができる。
【０００３】
測位装置によって得られる移動体の座標値と、それを計測した時刻を対応付けたデータを測位データと呼ぶ。例えば、時刻tに計測された移動体の2次元の位置を(x, y)とすると、(x, y, t)は測位データとなる。
【０００４】
特定の移動体の一連の測位データの集合を時空間データ(spatial trajectpry)と呼ぶ（非特許文献1参照）。nuを移動体の総数し、移動体の識別子を
2018112774.tif 000003
とする。この時、
2018112774.tif 000004
番目に計測した測位データを(xu,i, yu,i, tu,i) とすると、移動体uの時空間データDuは
2018112774.tif 000005
として与えられる。ここで、nusは移動体uにおける測位データの総数である。
【０００５】
＜時空間データマイニングの例＞
今まで、時空間データから隠された有益な知識を発見する試みがなされている。例えば、移動体を歩行者（以下、ユーザ）とし、すべてのユーザの時空間データを用いて、あるユーザの行き先を予測する試みがなされている（例えば、非特許文献２参照）。
【０００６】
＜マルコフ連鎖を使った移動エリア予測＞
時空間データを使った移動予測方式としてマルコフ連鎖を用いた方式が提案されている（非特許文献２、非特許文献３）。
【０００７】
次に、非特許文献３において記載されているように地理空間を複数の地理空間エリアに分割し、マルコフ連鎖を使って、指定された将来時刻において、あるユーザが指定された地理空間エリアに移動する確率を予測する方式、及び指定された将来時刻において、ユーザの地理空間エリア毎の滞在率を予測する方式を紹介する。
【０００８】
＜原理＞
図２５に示すように、地理空間100を地理空間エリア101A1、・ ・ ・、地理空間エリア102Ai、・ ・ ・、地理空間エリア103Aj、・ ・ ・、地理空間エリア104AnAから構成されるnA個の地理空間エリアに分割した例を考える。ユーザ111とユーザ112 が地理空間100内を移動するものとし、そのときのそれぞれの移動軌跡を121、122に示している。ユーザ111が、ある時刻mΔT（m = 0, 1, 2, ・ ・ ・ ,）に地理空間エリア102Aiに存在し、そのユーザが時刻(m+1)ΔTに地理空間エリア103Ajへ移動する事象である移動イベント131 の発生確率を
2018112774.tif 000006
とする。ここで、ΔT は状態推移を観測するための周期である。なお、あるユーザが時刻mΔTから時刻(m+1)ΔTまで地理空間エリア102Aiに滞在した場合も、地理空間エリア102Aiから地理空間エリア102Aiへ移動したとみなす。
【０００９】
マルコフ連鎖の用語では(i, j)要素が
2018112774.tif 000007
である行列PAを推移行列と呼ぶ（非特許文献４）。時刻tにおいて、地理空間エリア102Aiに滞在しているユーザ数を
2018112774.tif 000008
とする。時刻tにおいて、地理空間エリア102Aiに滞在しているユーザの比率を
2018112774.tif 000009
とすると、
2018112774.tif 000010
は、
【００１０】
【数１】
2018112774.tif 000011
（１）
【００１１】
として与えられる。
【００１２】
ベクトル
2018112774.tif 000012
とすると、
【００１３】
【数２】
2018112774.tif 000013
（２）
2018112774.tif 000014
（３）
2018112774.tif 000015
（４）
2018112774.tif 000016
（５）
【００１４】
が成立することが知られている（非特許文献４）。
【００１５】
上記（２）〜（５）式内の推移行列
2018112774.tif 000017
の（i,j)成分は、時刻tにユーザが地理空間エリアAiに滞在していた時、未来時刻t + m'ΔT にユーザが地理空間エリアAj に移動する確率を意味する。
【００１６】
ベクトル
2018112774.tif 000018
は、未来時刻t+m'ΔTにユーザが地理空間エリア
2018112774.tif 000019
に存在する確率である。以上より、推移行列PAとベクトルπA(t) が既知であれば、将来時刻においてユーザの地理空間エリア間の移動確率とユーザのエリア毎の滞在率を予測することができることがわかる。
【００１７】
＜ユーザの地理空間移動イベント
2018112774.tif 000020
の算出＞
図２６に示すように、ユーザuが時刻mΔTに地理空間エリア102Aｉにいたとき、時刻(m+1)ΔT に地理空間エリアAjへ移動したイベント132 をEui,j(m)と表記する。そのユーザu の時空間データDuから、地理空間移動イベントEui,j(m)を見つけ出すアルゴリズムを次に説明する。
【００１８】
＜地理空間移動イベント
2018112774.tif 000021
算出アルゴリズム＞
１．ユーザuの時空間データを特定し、それをDuとする。
【００１９】
２．
2018112774.tif 000022
を満たすpを、時空間データDuより求める。pは時空間データDuでのp番目測位データである。
【００２０】
３．
2018112774.tif 000023
を満たすqを、Duより求める。q は時空間データDuでのq番目測位データである。
【００２１】
４．p番目測位データ
2018112774.tif 000024
の位置情報（xu,p, yu,p）から地理空間エリアを特定し、それをAiとする。
【００２２】
５．q番目測位データ
2018112774.tif 000025
の位置情報（xu,q, yu,q）から地理空間エリアを特定し、それをAj とする。
【００２３】
６．ユーザuの時空間データのｐ番目測位データから得られる地理空間エリアAiからq番目測位データから得られる地理空間エリアAjへ移動したイベントを地理空間移動イベント
2018112774.tif 000026
とする。
【００２４】
ユーザuによる地理空間エリアAiから地理空間エリアAjへの移動イベントの発生回数の算出時刻tまでに、ユーザuが地理空間エリアAiから地理空間エリアAjへ移動したイベントの発生回数を
2018112774.tif 000027
とする。
【００２５】
2018112774.tif 000028
は次のアルゴリズムにより算出することができる。
【００２６】
＜
2018112774.tif 000029
算出アルゴリズム＞
１．時刻t以下で直近のmtΔTを求める。
【００２７】
mtは
【００２８】
【数３】
2018112774.tif 000030
（６）
【００２９】
として与えられる。
2018112774.tif 000031
はaの切り下げを意味する。
【００３０】
２．離散時刻0、ΔT 、・ ・ ・ 、mtΔTにおいて以下の処理を行う。
【００３１】
（ａ）上述した地理空間移動イベント
2018112774.tif 000032
算出アルゴリズム(m = 0, 1, ・ ・ ・ ,mt)を実行する。
【００３２】
（ｂ）上記のアルゴリズムの実行結果より、ユーザuが地理空間エリアAiから地理空間エリアAjへの移動イベントが得られるごとに、ユーザuの地理空間エリアAiから地理空間エリアAjへの移動イベント数を加算していく。
【００３３】
最終的に得られた数を、ユーザuの地理空間エリアAiから地理空間エリアAjへの移動イベント数
2018112774.tif 000033
とする。
【００３４】
すべてのユーザによる地理空間エリアAiから地理空間エリアAjへの移動イベントの発生回数の算出時刻tまでに、すべてのユーザが地理空間エリアAiから地理空間エリアAjへ移動したイベントの発生回数を
2018112774.tif 000034
とする。
【００３５】
2018112774.tif 000035
は、次式で与えられる。
【００３６】
【数４】
2018112774.tif 000036
（７）
【００３７】
すべてのユーザによる地理空間エリアAiから他の地理空間エリアへの移動イベントの発生回数の算出時刻tまでに、すべてのユーザが地理空間エリアAiから他の地理空間エリア（Aiも含む）へ移動したイベントの発生回数を
2018112774.tif 000037
とする。
2018112774.tif 000038
は、次式で与えられる。
【００３８】
【数５】
2018112774.tif 000039
(８）
【００３９】
推移行列PAの算出時刻tにおける推移行列PAの(i, j)要素
2018112774.tif 000040
の推定値は
【００４０】
【数６】
2018112774.tif 000041
（９）
【００４１】
として与えられる。
【００４２】
＜実装方式＞
時空間データを使って、ユーザが現在時刻に滞在している地理空間エリアから将来時刻に指定された地理空間エリアに移動する確率および将来時刻におけるユーザの各地理空間エリアでの滞在率を予測する装置を説明する。
【００４３】
図２７にこの予測サービスを実現するための時空間データマイニング装置の構成例を示す。時空間データマイニング装置１は、ユーザ111、ユーザ112の時空間データから、あるユーザが将来時刻に指定された地理空間エリアに移動する確率や将来時刻におけるユーザの各地理空間エリアでの滞在率をオペレータ２に提供する。
【００４４】
ユーザ111とユーザ112には、それぞれ測位装置141と測位装置142が装着されている。測位装置141と測位装置142を通して得られるユーザ111とユーザ112の測位データは、通信ネットワーク46上の基地局48に集められ、時空間データマイニング装置１に送られる。
【００４５】
時空間データマイニング装置１は、地理空間エリア群データ管理部10、ユーザ移動地理空間エリア予測部30、地理空間エリア滞在率予測部50から構成される。
【００４６】
地理空間エリア群データ管理部10は、地理空間エリア群データ22を生成する地理空間エリア群データ生成部12と、測位データから時空間データ21を生成する時空間データ生成部11から構成される。
【００４７】
＜地理空間エリア群データ22の構成例＞
地理空間エリアの表現モデルには様々なモデルがある（非特許文献5参照）。ここでは、図２８に示すような地理空間を8(=nA)個のグリッド（小さい正方形）により分割したモデルを考える。各地理空間エリアは辺の長さ211γと基点位置座標212（αi, βi), i =1, 2, ・ ・ ・ ,nAを定めることにより、地理空間内のすべての地理空間エリアを規定することができる。
【００４８】
地理空間エリア群データ22の構成例を図２９に示す。地理空間エリア群データ22は、各地理空間エリアの辺の長さ211γを格納するレジスターとnA個の組（地理空間エリア識別子213、基点位置座標212）を含むテーブルから構成される。
【００４９】
＜地理空間エリア群データ生成部12の処理＞
地理空間エリア群データ生成部12は、オペレータ2の指示により地理空間エリア群データ22を作成する。
【００５０】
＜時空間データ21の構成例＞
時空間データ21の構成例を図３０に示す。時空間データ21は、ユーザ数nu個の組（ユーザ識別子201、測位データの集合202）から構成される。例えば、ユーザuの時空間データ203Duは、ユーザuの測位データ204の集合から構成される。
【００５１】
＜時空間データ生成部11の処理＞
時空間データ生成部11は、通信ネットワーク46を経て測位データを受信した場合、以下の処理を行う。
【００５２】
１．通信ネットワーク46を介して受信した測位データのユーザを識別する。
【００５３】
２．時空間データ21において、そのユーザ識別子をもつ時空間データ203を探索し、その時空間データ203に受信した測位データを追加する。
【００５４】
＜ユーザ移動地理空間エリア予測部30の構成例＞
図３１にユーザ移動地理空間エリア予測部30内の処理部とデータを示す。
【００５５】
ユーザ移動地理空間エリア予測部30はユーザ毎移動イベント数データ41を生成するユーザ毎移動イベント数データ生成部31と、移動イベント数データ42を生成する移動イベント数データ生成部32と、推移行列データ43を生成する推移行列データ生成部33と、将来時刻において指定されたユーザが指定された地理空間に移動する確率をオペレータ2に出力するユーザ移動地理空間エリア出力部34から構成される。
【００５６】
＜ユーザ毎移動イベント数データ41の構成例＞
ユーザ毎移動イベント数データ41の構成例を図３２に示す。ユーザ毎移動イベント数データ41は、nu個からなるユーザ識別子がｕの移動イベント数データ411から構成される。ユーザ識別子がｕの移動イベント数データ411は移動先地理空間エリア412を意味するnA個の行、移動元地理空間エリア413を意味するnA個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素414は、現在時刻までにユーザ識別子がuであるユーザにおいて、地理空間エリア識別子がAiである地理空間エリアから地理空間エリア識別子がAj である地理空間エリアへの移動イベントの総発生回数である。
【００５７】
＜ユーザ毎移動イベント数データ生成部31の処理＞
ユーザ毎移動イベント数データ生成部31は、すべてのユーザに対して以下の処理を行い、ユーザ毎移動イベント数データ41を更新する。
【００５８】
1. 現在時刻tを求める。
【００５９】
2. ユーザ識別子u(=1, 2, ・ ・ ・ , nu)において、すべての地理空間エリアの組
2018112774.tif 000042
2018112774.tif 000043
において、以下の処理を行う。
【００６０】
（ａ）
2018112774.tif 000044
算出アルゴリズムを実行する。
【００６１】
（ｂ）上記により得られた値をユーザ毎移動イベント数データ41の(i, j)番目要素414に格納する。
【００６２】
＜移動イベント数データ42の構成例＞
移動イベント数データ42の構成例を図３３に示す。移動イベント数データ42は移動先地理空間エリア421を意味するnA個の行、移動元地理空間エリア422を意味するnA個の列から構成されるテーブルである。そのテーブルの(i, j) 番目要素423は、現在時刻までに、すべてのユーザにおいて地理空間エリア識別子がAiである地理空間エリアから地理空間エリア識別子がAjである地理空間エリアへの移動イベントの総発生回数である。
【００６３】
＜移動イベント数データ生成部32の処理＞
移動イベント数データ生成部32は、次の手順を使って移動イベント数データ42を更新する。
【００６４】
1. 現在の時刻tを求める。
【００６５】
2. すべての地理空間エリアの組(Ai,Aj), i = 1, 2,・・・, nA, j = 1, 2,・・・, nAにおいて、以下の処理を行う。
【００６６】
（ａ）ユーザ毎移動イベント数データ41と（７）式を使って現在時刻までのすべてのユーザにおける地理空間エリア識別子がAiである地理空間エリアから地理空間エリア識別子がAjである地理空間エリアへの移動イベントの発生回数を求める。
【００６７】
（ｂ）上記により得られた値を移動イベント数データ42の(i, j) 番目要素423に格納する。
【００６８】
＜推移行列データ43の構成例＞
推移行列データ43の構成例を図３４に示す。推移行列データ43は移動先地理空間エリア431を意味するnA個の行、移動元地理空間エリア432を意味するnA個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素433であるpijは、現在時刻までのすべてのユーザにおける地理空間エリア識別子がAiである地理空間エリアから地理空間エリア識別子がAjである地理空間エリアへ移動する確率である。
【００６９】
＜推移行列データ生成部33の処理＞
推移行列データ生成部33は、次の手順を使って推移行列データ43を更新する。
【００７０】
1.現在の時刻tを求める。
【００７１】
2.すべての地理空間エリアの組(Ai,Aj), i =1, 2,・・・,nA, j=1, 2,・・・, nAにおいて、以下の処理を行う。
【００７２】
（ａ）移動イベント数データ42と（８）式を使って、現在時刻tまでのすべてのユーザにおいて、地理空間エリア識別子がAiであるエリアから他の地理空間エリアへ移動したイベントの発生回数を求める。
【００７３】
（ｂ）移動イベント数データ42、上記により得られた値および（９）式を使って、現在時刻tまでのすべてのユーザにおいて、地理空間エリア識別子がAiである地理空間エリアから地理空間エリア識別子がAjである地理空間エリアへ移動する確率を求める。
【００７４】
（ｃ）上記により得られた値を推移行列データ43の(i, j)番目要素433に格納する。
【００７５】
ユーザ移動地理空間エリア出力部34のオペレータ2より、現時点で地理空間エリアAiに滞在しているユーザが、kΔT後に地理空間エリアAjに移動する確率の出力を依頼されたとき、以下の処理を行う。
【００７６】
１．推移行列データ43の{PA}を使って、その行列のk乗すなわち{PA}kを求める。
【００７７】
２．上記で得られた{PA}kの(i,j)成分の値をオペレータ2に通知する。
【００７８】
＜地理空間エリア滞在率予測部50の構成例＞
図３５に示すように、地理空間エリア滞在率予測部50は、地理空間エリア滞在ユーザ数データ61を生成する地理空間エリア滞在ユーザ数データ生成部51と、予測地理空間エリア滞在率データ62を生成する予測地理空間エリア滞在率データ生成部52と、オペレータ2に将来時刻での各地理空間エリアでのユーザ滞在率を通知する地理空間エリア滞在率出力部53から構成される。
【００７９】
＜地理空間エリア滞在ユーザ数データ61の構成例＞
地理空間エリア滞在ユーザ数データ61の構成例を図３６に示す。地理空間エリア滞在ユーザ数データ61は、組(地理空間エリア識別子、滞在ユーザ数、滞在ユーザ比率)のnA個の要素からなるテーブルである。i番目要素231は、現在時刻において地理空間エリア識別子がAiである地理空間エリアに滞在しているユーザ数であり、i番目要素232は、現在時刻において地理空間エリア識別子がAiである地理空間エリアに滞在しているユーザの比率である。
【００８０】
＜地理空間エリア滞在ユーザ数データ生成部51の処理＞
地理空間エリア滞在ユーザ数データ生成部51は、次の手順を使って地理空間エリア滞在ユーザ数データ61を更新する。
【００８１】
すべての地理空間エリア
2018112774.tif 000045
において、以下の手順を行う。
【００８２】
１．時空間データ21から、現在時刻において地理空間エリア識別子がAiである地理空間エリアに滞在しているユーザ数（（１）式での
2018112774.tif 000046
に対応する）を求める。
【００８３】
２．上記により得られた値を地理空間エリア滞在ユーザ数データ61のi番目要素231に格納する。
【００８４】
３．（１） 式を使って、現在時刻において地理空間エリア識別子がAiである地理空間エリアに滞在しているユーザの比率（（１）式での
2018112774.tif 000047
に対応する）を求める。
【００８５】
４．上記により得られた値を地理空間エリア滞在ユーザ数データ61のi番目要素232に格納する。
【００８６】
＜予測地理空間エリア滞在率データ62の構成例＞
予測地理空間エリア滞在率データ62の構成例を図３７に示す。予測地理空間エリア滞在率データ62はnA個の行、m'個の列から構成されるテーブルである。そのテーブルの(i, j) 番目要素241は、未来時刻t+iΔTにおいて地理空間エリアAjにユーザが滞在している確率である。この確率は（４）式でのベクトル
2018112774.tif 000048
のj番目成分に対応する。
【００８７】
＜予測地理空間エリア滞在率データ生成部52の処理＞
予測地理空間エリア滞在率データ生成部52は次の手順を使って予測地理空間エリア滞在率データ62を更新する。
【００８８】
未来時刻
2018112774.tif 000049
とすべての地理空間エリア
2018112774.tif 000050
において、以下の手順を行う。
【００８９】
１．推移行列データ43と、地理空間エリア滞在ユーザ数データ61の滞在ユーザ比率の列と、上記（２）式〜（５）式とを使って未来時刻t + iΔTにおいて地理空間エリアAjにユーザが滞在している確率241を求める。
【００９０】
２．上記により得られた値を予測地理空間エリア滞在率データ62の未来時刻がiΔT後で地理空間エリア識別子がAjである要素に格納する。
【００９１】
＜地理空間エリア滞在率出力部53の処理＞
地理空間エリア滞在率出力部53は、予測地理空間エリア滞在率データ62を加工してオペレータに情報を提供する。
【先行技術文献】
【非特許文献】
【００９２】
【非特許文献１】Y,Zheng, "Trajectory Data Mining: An Overview",ACM Transaction on Intelligent Systems and Technology, Vol.6,No.3,pp.29-41,2015年
【非特許文献２】浅原彰規， 佐藤暁子， 丸山貴志子“混合自己回帰隠れマルコフモデルによる歩行者行き先予測” 情報処理学会論文誌,Vol.53,No.1,pp.342-351,2012年．
【非特許文献３】G.J.G. Upton,B,Fingleton, "Spatial Data Analysis by Example, Volume 2, Categorical and Directional Data", John Wiley & Sons, p.182,1989年
【非特許文献４】森村英典、高橋幸雄“マルコフ解析” 日科技連出版社、1979年.
【非特許文献５】張長平“地理情報システムを用いた空間データ分析”古今書院、2009年.
【非特許文献６】野崎昭弘“アルゴリズムの最近の動向：4. 行列積の漸近的計算量”情報処理  24（４），ｐｐ.363-366，1983年.
【非特許文献７】横山隆治、楳田良輝“リアル行動ターゲティング” 日経BP社、2015年.
【発明の概要】
【発明が解決しようとする課題】
【００９３】
従来方式では、前述したように、地理空間を事前に設定された大きさの地理空間エリアで分割し、各地理空間エリアの大きさは不変であることと、分析対象となる地理空間エリアは地理空間内のすべての地理空間エリアであることとを仮定している。
【００９４】
図３８に正方形状の地理空間500上で観測された測位データの例を示す。図３８では、各地理空間エリアはグリッド（小さな正方形）であり、地理空間内の地理空間エリア数はnAであると仮定している。分析対象となる地理空間エリアの集合は、測位データ501の分布に依存することなく、地理空間内のすべての地理空間エリアの集合となる。
【００９５】
このような状況のもとでの課題を次に示す。
【００９６】
＜課題Ｐ１＞
以下の理由により、分析対象とする地理空間エリアの集合を必要最小限に抑える必要がある。
【００９７】
ある地理空間エリアから、ある地理空間エリアへのユーザの移動確率を意味する推移行列PAと、ある地理空間エリアでのユーザの滞在率を意味する状態確率πA (t)が与えられた時、m’ΔT後の時刻でのユーザの地理空間エリアでの滞在率を意味するπA(t+m'ΔT)を予測する場合、{PA}m’の演算が必要となる（（５）式参照）。もし、分析対象となる地理空間エリアの集合が地理空間と等しい場合、推移行列PAの大きさ（行の数）は地理空間エリアの数nAと等しくなる。
【００９８】
行列積の演算量は、大きさの３乗に比例することが知られている（非特許文献６）。よって、{PA}m’の演算は、
2018112774.tif 000051
の計算量を必要とする。
【００９９】
従来の装置では、測位データの有無にかかわらず、すべての地理空間エリアが計算対象となってしまう。そのため、ユーザの地理空間エリアの移動確率を求めるにあたって、nAの３乗のオーダーの計算量を必要とする。一方、地理的な移動予測誤差を小さくするために地理空間エリアの大きさを小さくすると、数nAはますます大きくなってしまう。結果的に、計算量はさらに増大する。したがって計算量を減らすためには分析対象となる地理空間エリア数を増大させないことが必要となる。
【０１００】
すべての地理空間エリアを分析対象とすると、測位データが存在しない地理空間エリアが多数発生する。このような地理空間エリアを表現する推移行列は、疎行列（成分のほとんどが零である行列）となる。疎行列の演算では、無駄が多いと知られている。よって、できる限り疎行列とならないように、測位データが存在する地理空間エリアを分析対象とし、分析対象の地理空間エリア数を抑える工夫を必要とする。
【０１０１】
＜課題Ｐ２＞
オペレータの満足度を向上させるためには、オペレータが処理を依頼してからその応答を得るまでの時間を一定時間に抑える必要がある。したがって、分析対象の地理空間エリアの数nAが、計算許容エリア数（閾値nth）を超えたとき、分析対象となっている複数の地理空間エリアを統合する必要がある（図３８での統合地理空間エリア503参照）。
【０１０２】
無作為に２つの地理空間エリアを統合する場合、その組み合わせは
2018112774.tif 000052
通りとなる。よって、nA(nA-1)/2個の候補から適切なエリアを選択する処理を必要とするため、n A 2のオーダーの計算量を必要とする。したがって、統合対象となる地理空間エリアを効率よく選択することを必要とする。
【０１０３】
本発明は、上記の課題を解決するためになされたものであり、計算量を抑えて、時空間データを分析することができる時空間データマイニング装置を提供することを目的とする。
【課題を解決するための手段】
【０１０４】
上記課題Ｐ１を解決するために、本発明に係る時空間データマイニング装置は、地理空間を複数の地理空間エリアに分割した地理情報空間上において、移動体に備え付けられた測位装置によって得られる位置情報と、前記測位装置により位置情報が計測された時刻との組からなる一連の測位データから構成される時空間データを分析する時空間データマイニング装置において、前記測位データについて、前記測位データの位置情報より、前記移動体が観測された地点を含む地理空間エリアを特定する地理空間エリア群データ生成手段と、前記測位データが前記時空間データに追加されたとき、前記測位データについて特定された地理空間エリアが分析対象となっている地理空間エリアの集合に含まれるか否かを判定する分析対象地理空間エリア判定手段と、前記追加された測位データについて特定された地理空間エリアが分析対象となっている地理空間エリアの集合に含まれないと判定されたとき、前記特定された地理空間エリアを分析対象となっている地理空間エリアの集合に追加する分析対象地理空間エリア群データ生成手段と、を含んで構成されている。
【０１０５】
また、移動体が未来時刻に滞在する地理空間エリアを予測するために、本発明に係る時空間データマイニング装置は、決められた時間帯で、指定された移動体が、移動元として指定された分析対象の地理空間エリアから移動先として指定された分析対象の地理空間エリアへ移動したイベントの発生回数を示す移動総数を求める移動総数計数手段と、測位データＰが前記時空間データに追加されたとき、前記測位データＰと同一の移動体の時空間データに対して前記測位データＰの直前に記録された測位データＱを特定する直前測位データ特定手段と、前記測位データＰの前記移動体に対し、前記測位データＱについて特定される地理空間エリアと前記測位データＰについて特定される地理空間エリアとが同一の場合、前記測位データＱの計測時刻までに同一の地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算し、前記測位データＱについて特定される地理空間エリアＡiと前記測位データＰについて特定される地理空間エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアＡjがすでに分析対象となっている場合、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算すると共に、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡjへ移動した移動総数に、１を加算し、前記測位データＱについて特定される地理空間エリアＡiと前記測位データＰについて特定される地理空間エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアＡjが分析対象となっていない場合、前記測位データＱの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記地理空間エリアＡiから前記地理空間エリアＡiへ移動した移動総数を加算すると共に、前記地理空間エリアＡiから前記地理空間エリアＡjへ移動した移動総数を、１に設定し、前記地理空間エリアＡi以外の前記地理空間エリアの各々から前記地理空間エリアＡjへ移動した移動総数を、０に設定するユーザ毎移動イベント数データ生成手段と、分析対象となっている地理空間エリアの組み合わせの各々について、一方の地理空間エリアから他方の地理空間エリアへの個々の移動体の移動総数を、全ての移動体において加算して全移動総数を求める移動イベント数データ生成手段と、分析対象となっている地理空間エリアの組み合わせの各々について、一方の地理空間エリアから分析対象となっている地理空間エリアの各々への全移動総数を加算した値を求め、一方の地理空間エリアから他方の地理空間エリアへの全移動総数を、前記求めた全移動総数の加算値で割った値を、一方の地理空間エリアから他方の地理空間エリアへ移動する確率として算出し、前記算出された確率を要素とする推移行列データを生成する推移行列データ生成手段と、前記推移行列データを指定回数掛け合わせたものを用いて、分析対象となっている地理空間エリアの各々に、指定された移動体が移動する確率を算出するユーザ移動地理空間エリア出力手段と、全ての移動体についての時空間データの測位データについて特定された地理空間エリアから求められる、分析対象となっている各地理空間エリアに存在する移動体数と、分析対象となっている全ての地理空間エリアにおける移動体数の総数を求め、分析対象となっている各地理空間エリアについて、前記移動体数を前記移動体数の総数で割った値を、前記分析対象となっている地理空間エリアに移動体が存在する比率として算出する分析対象地理空間エリア滞在ユーザ数生成手段と、前記算出された比率からなるベクトルに、前記推移行列データを指定回数掛け合わせたものを掛け合わせることにより、将来時刻における、分析対象となっている地理空間エリアの各々に移動体が存在する比率を算出する予測分析対象地理空間エリア滞在率データ生成手段と、を更に有することができる。
【０１０６】
また、上記課題Ｐ２を解決するために、測位データが存在する論理エリアのみを分析対象とするように、本発明に係る時空間データマイニング装置は、木状に構成された論理エリアであって、親論理エリアは、１つ以上の子論理エリアから構成され、子論理エリアに対応する全ての地理空間エリアにおいて地理的に重なる部分はなく、子論理エリアの集合により構成される地理空間エリア群は親論理エリアの地理空間エリア群と一致し、再下位層にある論理エリアである葉論理エリアは１つの地理空間エリアと同一視できる、論理エリアのトポロジーを構成する論理エリアトポロジーデータ生成手段と、分析対象となる論理エリア数の最大値を設定する分析対象最大論理エリア数データ生成手段と、指定された論理エリアに対する子論理エリアを求める子論理エリア算出手段と、指定された論理エリアに対する親論理エリアを求める親論理エリア算出手段と、を更に含み、前記分析対象地理空間エリア判定手段は、前記測位データが前記時空間データに追加されたとき、追加された測位データの座標情報から前記測位データが観測された地点を含む地理空間エリアAPを特定し、前記地理空間エリアAPに対応する葉論理エリアを求め、前記葉論理エリアが、分析対象となっている葉論理エリアの集合に含まれるか否かを判定し、前記分析対象地理空間エリア群データ生成手段は、前記追加された測位データについて特定された葉論理エリアが前記分析対象となっている葉論理エリアの集合に含まれないと判定されたとき、前記葉論理エリアを前記分析対象となっている葉論理エリアの集合に追加し、前記時空間データマイニング装置は、前記追加された測位データについて特定された葉論理エリアに対する親論理エリアを求め、統合候補となっている論理エリアの集合に前記親論理エリアを追加する測位データ追加処理手段と、指定された論理エリアの価値を算出する論理エリア価値計算手段と、統合候補となっている論理エリアの集合のうち、最小の論理エリアの価値を持つ論理エリアＧを求め、前記論理エリアＧの子の論理エリア群{child(Ｇ)}を求め、前記子の論理エリア群{child(Ｇ)}が、分析対象となっている論理エリアの集合に含まれている場合は、前記子の論理エリア群{child(Ｇ)}を前記分析対象となっている論理エリアの集合から削除し、前記分析対象となっている論理エリアの集合に、前記最小の論理エリアの価値を持つ論理エリアＧを追加し、前記統合候補となっている論理エリアの集合から前記最小の論理エリアの価値を持つ論理エリアＧを削除し、前記最小の論理エリアの価値を持つ論理エリアＧの親論理エリアpar(Ｇ)を、前記統合候補となっている論理エリアの集合に追加する論理エリア統合処理手段と、前記分析対象となっている論理エリアの集合のうち、最大の論理エリアの価値を持つ論理エリアＧを求め、前記分析対象となっている論理エリアの集合から前記最大の論理エリア価値を持つ論理エリアＧを削除し、前記最大の論理エリア価値を持つ論理エリアＧの子の論理エリア群{child(Ｇ)}を求め、前記子の論理エリア群{child(Ｇ)}に含まれる各子論理エリアにおいて、前記論理エリアのトポロジーを使って、該当する地理空間エリアを求め、前記時空間データを使って、前記地理空間エリアに測位データが観測されているかを調べ、前記測位データが存在する場合、前記子論理エリアを、前記分析対象となっている論理エリアの集合に追加する論理エリア分割処理手段と、前記測位データが前記時空間データに追加されたとき、前記分析対象となっている論理エリアの集合の要素は、前記分析対象となる論理エリア数の最大値以下であり、かつ、前記統合候補となっている論理エリアの集合内の論理エリアで最小の論理エリアの価値ρmin(C)が、前記分析対象となっている論理エリアの集合内の論理エリアで最大の論理エリアの価値ρmax(F)より大きいと判定されるまで、前記論理エリア統合処理手段による処理、及び前記論理エリア分割処理手段による処理を繰り返させる論理エリア構成最適判定手段と、を更に有することができる。
【０１０７】
また、移動体が未来時刻に滞在する地理空間エリアを予測するために、本発明に係る時空間データマイニング装置は、決められた時間帯で、指定された移動体が、移動元として指定された分析対象の葉論理エリアから移動先として指定された分析対象の葉論理エリアへ移動したイベントの発生回数を示す移動総数を求める移動総数計数手段と、測位データＰが前記時空間データに追加されたとき、前記測位データＰと同一の移動体の時空間データに対して前記測位データＰの直前に記録された測位データＱを特定する直前測位データ特定手段と、前記測位データＰの前記移動体に対し、前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアが同一の場合、前記測位データＱの計測時刻までに同一の葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算し、前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアＡiと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjがすでに分析対象となっている場合、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算すると共に、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡjへ移動した移動総数に、１を加算し、前記測位データＱについて特定される地理空間エリアに対応する葉論理エリアＡiと前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが異なり、かつ、前記測位データＰについて特定される地理空間エリアに対応する葉論理エリアＡjが分析対象となっていない場合、前記測位データＱの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数に、前記測位データＱの計測時刻から前記測位データＰの計測時刻までに前記葉論理エリアＡiから前記葉論理エリアＡiへ移動した移動総数を加算すると共に、前記葉論理エリアＡiから前記葉論理エリアＡjへ移動した移動総数を、１に設定し、前記葉論理エリアＡi以外の前記葉論理エリアの各々から前記葉論理エリアＡjへ移動した移動総数を、０に設定するユーザ毎葉論理エリア移動イベント数データ生成手段と、指定された論理エリアを起点とした枝において、葉論理エリアの集合を求める枝上葉論理エリア算出手段と、前記移動体の各々に対し、分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアについて求められる葉論理エリアの集合の何れかの葉論理エリアから、他方の論理エリアについて求められる葉論理エリアの集合の何れかの葉論理エリアへの移動総数を、一方の論理エリアから他方の論理エリアへの移動総数として設定するユーザ毎論理エリア移動イベント数データ生成手段と、前記分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアから他方の論理エリアへの個々の移動体の移動総数を、全ての移動体において加算して全移動総数を求める論理エリア移動イベント数データ生成手段と、前記分析対象となっている論理エリアの組み合わせの各々について、一方の論理エリアから分析対象となっている論理エリアの各々への全移動総数を加算した値を求め、一方の論理エリアから他方の論理エリアへの全移動総数を、前記求めた全移動総数の加算値で割った値を、一方の論理エリアから他方の論理エリアへ移動する確率として算出し、前記算出された確率を要素とする推移行列データを生成する推移行列データ生成手段と、前記推移行列データを指定回数掛け合わせたものを用いて、前記分析対象となっている論理エリアの各々に、指定された移動体が移動する確率を算出するユーザ移動地理空間エリア出力手段と、全ての移動体についての時空間データの測位データについて特定された論理エリアから求められる、前記分析対象となっている各論理エリアに存在する移動体数と、前記分析対象となっている全ての論理エリアにおける移動体数の総数を求め、前記分析対象となっている各論理エリアについて、前記移動体数を前記移動体数の総数で割った値を、前記分析対象となっている論理エリアに移動体が存在する比率として算出する分析対象論理エリア滞在ユーザ数生成手段と、前記算出された比率からなるベクトルに、前記推移行列データを指定回数掛け合わせたものを掛け合わせることにより、将来時刻における、分析対象となっている論理エリアの各々に移動体が存在する比率を算出する予測論理エリア滞在率データ生成手段と、を更に有することができる。
【０１０８】
また、論理エリア価値計算手段は、指定された論理エリアの価値として、前記論理エリアで発生した測位データ数を算出することができる。
【発明の効果】
【０１０９】
以上説明したように、本発明の時空間データマイニング装置によれば、計算量を抑えて、時空間データを分析することができる、という効果が得られる。
【図面の簡単な説明】
【０１１０】
【図１】本発明の第１の実施の形態における時空間データマイニング装置のブロック図である。
【図２】分析対象地理空間エリア群データの構成の例を示す図である。
【図３】本発明の第１の実施の形態に係るユーザ移動地理空間エリア予測部の構成例を示す図である。
【図４】ユーザ毎移動イベント数データの構成例を示す図である。
【図５】測位データの場合分けの例を示す図である。
【図６】移動イベント数データの構成例を示す図である。
【図７】推移行列データの構成例を示す図である。
【図８】本発明の第１の実施の形態に係る地理空間エリア滞在率予測部の構成例を示す図である。
【図９】分析対象地理空間エリア滞在ユーザ数の構成例を示す図である。
【図１０】予測分析対象地理空間エリア滞在率データの構成例を示す図である。
【図１１】本発明の第２の実施の形態に係る時空間データマイニングのブロック図である。
【図１２】本発明の第２の実施の形態に係る分析対象論理空間エリア群データ管理部の構成例を示す図である。
【図１３】論理エリアトポロジーデータの構成例を示す図である。
【図１４】分析対象論理エリア群データの構成例を示す図である。
【図１５】分析対象葉エリア群データの構成例を示す図である。
【図１６】統合候補論理エリア群データの構成例を示す図である。
【図１７】本発明の第２の実施の形態に係るユーザ移動地理空間エリア予測部の構成例を示す図である。
【図１８】ユーザ毎葉論理エリア移動イベント数データの構成例を示す図である。
【図１９】ユーザ毎論理エリア移動イベント数データの構成例を示す図である。
【図２０】論理エリア移動イベント数データの構成例を示す図である。
【図２１】推移行列データの構成例を示す図である。
【図２２】本発明の第２の実施の形態に係る地理空間エリア滞在率予測部の構成例を示す図である。
【図２３】分析対象論理エリア滞在ユーザ数データの構成例を示す図である。
【図２４】予測論理エリア滞在率データの構成例を示す図である。
【図２５】地理空間を地理空間エリアに分割した例を示す図である。
【図２６】地理空間移動イベントを説明するための図である。
【図２７】従来技術における時空間データマイニング装置のブロック図である。
【図２８】地理空間エリアの表現モデルを示す図である。
【図２９】地理空間エリア群データの構成例を示す図である。
【図３０】時空間データの構成例を示す図である。
【図３１】従来技術におけるユーザ移動地理空間エリア予測部の構成例を示す図である。
【図３２】ユーザ毎移動イベント数データの構成例を示す図である。
【図３３】移動イベント数データの構成例を示す図である。
【図３４】推移行列データの構成例を示す図である。
【図３５】従来技術における地理空間エリア滞在率予測部の構成例を示す図である。
【図３６】地理空間エリア滞在ユーザ数データの構成例を示す図である。
【図３７】予測地理空間エリア滞在率データの構成例を示す図である。
【図３８】地理空間上で観測された測位データの例を示す図である。
【発明を実施するための形態】
【０１１１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【０１１２】
＜本発明の第１の実施の形態に係る時空間データマイニング装置の構成＞
次に、本発明の第１の実施の形態に係る時空間データマイニング装置の構成について説明する。図１に示すように、本発明の第１の実施の形態に係る時空間データマイニング装置2000は、ＣＰＵと、ＲＡＭと、プログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。時空間データマイニング装置2000は、移動体に備え付けられた測位装置によって得られる位置情報と、測位装置により位置情報が計測された時刻との組からなる一連の測位データから構成される時空間データを分析する装置である。この時空間データマイニング装置2000は、機能的には図１に示すように、分析対象地理空間エリア群データ管理部2100、ユーザ移動地理空間エリア予測部2200、及び地理空間エリア滞在率予測部2300から構成される。なお、従来技術として説明した時空間データマイニング装置１と同様の構成となる部分については同一符号を付して説明を省略する。
【０１１３】
＜分析対象地理空間エリア群データ管理部2100＞
＜分析対象地理空間エリア群データ管理部2100の構成例＞
分析対象地理空間エリア群データ管理部2100は上記図２７で示した従来の地理空間エリア群データ管理部10での時空間データ生成部11、時空間データ21、地理空間エリア群データ生成部12、及び地理空間エリア群データ22と、新たに追加された分析対象地理空間エリア群データ生成部2111及び分析対象地理空間エリア群データ2121とから構成されている。
【０１１４】
＜分析対象地理空間エリア群データ2121の構成例＞
分析対象地理空間エリア群データ2121の構成の例を図２に示す。分析対象地理空間エリア数の値をnBとすると、分析対象地理空間エリア群データ2121にはnB個の組（分析対象となっている地理空間エリアの識別子2131、分析対象地理空間エリアに対応する地理空間エリアの識別子2132）から構成されている。
【０１１５】
＜分析対象地理空間エリア群データ生成部2111の処理＞
分析対象地理空間エリア群データ生成部2111は、次の手順を使って分析対象地理空間エリア群データ2121を更新する。測位データPが時空間データ21に追加された時、以下の分析対象地理空間エリア増加アルゴリズムを行う。
【０１１６】
［分析対象地理空間エリア増加アルゴリズム］
１．追加された測位データP(= (x, y, t))の座標情報(x, y)からその測位データが観測された地点を含む地理空間エリアを特定し、その地理空間エリアをAPとする（請求項１の地理空間エリア群データ生成手段に相当する）。
【０１１７】
２．その地理空間エリアAPの識別子が、分析対象地理空間エリア群データ2121での地理空間エリア識別子2132の集合内の要素と合致するかを調べ（請求項1の分析対象地理空間エリア判定手段に相当する）、その結果に応じて以下の処理を行う（請求項１の分析対象地理空間エリア群データ生成手段に相当する）。
【０１１８】
地理空間エリアAPの識別子が地理空間エリア識別子2132の集合内の要素と合致しない場合、以下の（ａ）〜（ｃ）の処理を行う。
【０１１９】
（ａ）nBを一つ加算する（nB←nB +1）。
【０１２０】
（ｂ）分析対象地理空間エリア群データ2121での分析対象地理空間エリア識別子2132の集合に要素BnBを追加する。
【０１２１】
（ｃ）分析対象地理空間エリア群データ2121での分析対象地理空間エリア識別子2131がBnBに対応する地理空間エリア識別子をAPの識別子とする。
【０１２２】
地理空間エリアAPの識別子が地理空間エリア識別子2132の集合内の要素と合致する場合何もしない。
【０１２３】
＜ユーザ移動地理空間エリア予測部2200＞
＜ユーザ移動地理空間エリア予測部2200の構成例＞
図３に、第１の実施の形態に係るユーザ移動地理空間エリア予測部2200の構成例を示す。上記図３１で示した従来のユーザ移動地理空間エリア予測部30でのユーザ毎移動イベント数データ生成部31をユーザ毎移動イベント数データ生成部2231に、移動イベント数データ生成部32を移動イベント数データ生成部2232に、推移行列データ生成部33を推移行列データ生成部2233に、ユーザ移動地理空間エリア出力部34をユーザ移動地理空間エリア出力部2234に、ユーザ毎移動イベント数データ41をユーザ毎移動イベント数データ2241に、移動イベント数データを移動イベント数データ42に、推移行列データ43を推移行列データ2243に、置き換えている。
【０１２４】
＜ユーザ毎移動イベント数データ2241の構成例＞
第１の実施の形態に係るユーザ毎移動イベント数データ2241の構成例を図４に示す。ユーザ毎移動イベント数データ2241は、nu個のユーザ識別子uの各々に対する移動イベント数データ2211から構成される。ユーザ識別子uの移動イベント数データ2211は移動先分析対象地理空間エリアを意味するnB個の行、移動元分析対象地理空間エリアを意味するnB個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素2214は、現在時刻までの、ユーザ識別子uであるユーザが分析対象地理空間エリア識別子がBiである地理空間エリアから分析対象地理空間エリア識別子がBjである地理空間エリアへの移動イベントの総発生回数である。
【０１２５】
＜ユーザ毎移動イベント数データ生成部2231の処理＞
ユーザ毎移動イベント数データ生成部2231は、以下の
2018112774.tif 000053
【０１２６】
算出アルゴリズムを使ってユーザ毎移動イベント数データ2241を更新する。このアルゴリズムにより、ユーザuにおいて、時間帯(s,t)における分析対象地理空間エリアBiから分析対象地理空間エリアBjへの移動回数を求めることができる。
2018112774.tif 000054
算出アルゴリズムは、請求項2の移動総数計数手段に相当する。
【０１２７】
［
2018112774.tif 000055
算出アルゴリズム］
１．分析対象地理空間エリア群データ2121を使って、分析対象地理空間エリアBiに対応する地理空間エリアAｉ*を求める。
【０１２８】
２.分析対象地理空間エリア群データ2121を使って、分析対象地理空間エリアBjに対応する地理空間エリアAｊ*を求める。
【０１２９】
３．時刻s以上で直近のmsΔTを求める。
【０１３０】
msは
【０１３１】
【数７】
2018112774.tif 000056
（１０）
【０１３２】
として与えられる。
2018112774.tif 000057
はaの切り上げを意味する。
【０１３３】
４．時刻t以下で直近のmtΔTを求める。
【０１３４】
mtは
【０１３５】
【数８】
2018112774.tif 000058
（１１）
【０１３６】
として与えられる。
【０１３７】
５．離散時刻msΔT 、(ms+1)ΔT ，・・・，mtΔTにおいて以下の（ａ）、（ｂ）の処理を行う。
【０１３８】
（ａ）上記で述べた地理空間移動イベント
2018112774.tif 000059
算出アルゴリズム(m = ms,ms+1,・・・,mt)を実行する。
【０１３９】
（ｂ）ユーザuの地理空間エリアAｉ*からAｊ*への移動イベントが得られるごとにユーザuの地理空間エリアAｉ*からAｊ*への移動イベント数を加算していく。
【０１４０】
最終的に得られるユーザuの地理空間エリアAｉ*からAｊ*への移動イベント数を
2018112774.tif 000060
とする。
【０１４１】
次に、
2018112774.tif 000061
算出アルゴリズムを使った、ユーザ毎移動イベント数データ2241の更新処理を説明する（請求項2の直前測位データ特定手段、及びユーザ毎移動イベント数データ生成手段に相当する）。
【０１４２】
時空間データ21に追加された測位データをPとし、そのユーザをuとする。ユーザuの時空間データ２１において測位データPを追加する前の最後に記録されている測位データをQとする。測位データPを次のＣａｓｅＩ〜ＣａｓｅIIのように分類して、ユーザ毎移動イベント数データ2241を更新する。
【０１４３】
（ＣａｓｅＩ）測位データPは、測位データPを時空間データ21に追加する前の分析対象地理空間エリア群以外の地理空間エリアにて観測された場合
【０１４４】
（ＣａｓｅII）測位データPは、測位データPを時空間データ21に追加する前の分析対象地理空間エリア群上の地理空間エリアにて観測された場合
【０１４５】
ＣａｓｅIIは、更に、次のＣａｓｅII−ａ、ＣａｓｅII−ｂに分類される。
【０１４６】
（ＣａｓｅII−ａ）測位データPが観測された地理空間エリアは測位データQが観測された地理空間エリアと同じ場合（つまり、ユーザuが同一地理空間エリアに滞在していた場合）
【０１４７】
（ＣａｓｅII−ｂ）測位データPが観測された地理空間エリアは測位データQが観測された地理空間エリアと異なる場合（つまり、ユーザuがすでに分析対象となっている他の地理空間エリアに移動した場合。）
【０１４８】
＜測位データPの場合分けの例＞
図５に測位データPの場合分けの例を示す。ユーザ１の測位データPが追加される前の分析対象地理空間エリア群2501は三つの地理空間エリアから構成され、分析対象地理空間エリア群データ2121において、分析対象地理空間エリア識別子2131の集合を{B1,B2,B3}、それに対応する地理空間エリア識別子2132の集合を{A2,A6,A7}とする。
【０１４９】
（ＣａｓｅＩの例）
ユーザ１の時空間データD1において、測位データPが追加される前の測位データQ2502は地理空間エリアA6(=B2)において、観測されたものとする。測位データPが地理空間エリアA4において観測された場合、分析対象地理空間エリア群以外の地理空間で観測されたため、ＣａｓｅＩとなる（図５での2503参照）。
【０１５０】
（ＣａｓｅII-ａの例）
測位データPが地理空間エリアA6において観測された場合、測位データPが観測された地理空間エリアは、分析対象地理空間エリア群であって、測位データQと同一エリアであるため、ＣａｓｅII-ａとなる（図５での2504参照）。
【０１５１】
（ＣａｓｅII-ｂの例）
測位データPが地理空間エリアA2において観測された場合、測位データPが観測された地理空間エリアは、分析対象地理空間エリア群であって、測位データQが観測されたエリアとは異なるエリアであるため、ＣａｓｅII-ｂとなる（図５での2505参照）。
【０１５２】
前述の場合分けに応じて以下の処理を行う。
【０１５３】
１．現在の時刻tを求める。
【０１５４】
２．分析対象地理空間エリア群データ2121の要素数をnBとする。
【０１５５】
３．追加された測位データPのユーザuを特定する。
【０１５６】
４．時空間データ21のユーザuの時空間データ203Duにおいて測位データPが保存される前の最後に保存された測位データＱを探索する。
【０１５７】
５．測位データＱの記録時刻をsとする。
【０１５８】
６．測位データＱの座標情報が観測された地点を含む地理空間エリアを特定し、その地理空間エリアを
2018112774.tif 000062
とする。
【０１５９】
７．分析対象地理空間エリア群データ2121での地理空間エリア識別子2132の集合においてAQに等しい要素を見つけ、それをAiとする。
【０１６０】
８．地理空間エリアAPの種別により以下の処理を行う。
【０１６１】
ＣａｓｅＩの場合（測位データPが観測された地理空間エリアは、Pを記録する前の分析対象地理空間エリア群の要素でない場合）、（ａ）〜（ｃ）の処理を行う。
【０１６２】
（ａ）ユーザ毎移動イベント数データ2241の(i, i)番目の要素の値を次の値で更新する。
【０１６３】
【数９】
2018112774.tif 000063
（１２）
【０１６４】
ただし、
2018112774.tif 000064
は、時刻ｓから時刻ｔまでの期間にユーザが滞在していることを表しており、例えば、時刻ｓから時刻ｔまでの期間における観測周期数である。
【０１６５】
（ｂ）ユーザ毎移動イベント数データ2241にnB行とnB列の要素を追加する。
【０１６６】
（ｃ）追加された要素において、要素(i, nB)の値を１とし、それ以外の要素の値を０とする。
【０１６７】
なお、他のユーザのユーザ毎移動イベント数データ2241については、変更されない。
【０１６８】
ＣａｓｅIIの場合（測位データPが観測された地理空間エリアは、Pを記録する前の分析対象地理空間エリア群の要素である場合）、分析対象地理空間エリア群データ2121の地理空間エリア識別子2131の集合において、APに等しい要素を見つけ、それを
2018112774.tif 000065
とする。
【０１６９】
ユーザu が同一エリア
2018112774.tif 000066
に滞在していた場合（つまり、
2018112774.tif 000067
の場合）、ユーザ毎移動イベント数データ2241の(i, i)番目の要素の値を次の値で更新する。
【０１７０】
【数１０】
2018112774.tif 000068
（１３）
【０１７１】
ユーザuがすでに分析対象となっている他の地理空間エリアに移動した場合（つまり、
2018112774.tif 000069
の場合）、ユーザ毎移動イベント数データ2241の(i, j)番目の要素の値を次の値で更新する。
【０１７２】
【数１１】
2018112774.tif 000070
（１４）
【０１７３】
次に、図５で説明した例をもとにユーザ毎移動イベント数データ2241の更新を説明する。
【０１７４】
ＣａｓｅＩの場合（測位データPはPを記録する前の分析対象地理空間エリアで観測されていない場合：図５での2503参照）、ユーザ１の測位データPが観測された地理空間エリアA4は分析対象地理空間エリア群に属さないため、ユーザ１のユーザ毎移動イベント数データである行列
2018112774.tif 000071
は
【０１７５】
【数１２】
2018112774.tif 000072
（１５）
【０１７６】
となる。上式より、行列
2018112774.tif 000073
の(2, 2)番目要素の値が増加する可能性があるとともに、4列目と4行目の要素が追加され、(1, 4)番目の要素には1が入りそれ以外には0が入ることがわかる。
【０１７７】
ユーザ１が同一エリアに滞在し続けた場合（図５での2504参照）、ユーザ１の測位データPは、引き続き地理空間エリアA6(=B2)にて観測されている、つまりユーザ１は地理空間エリアA6に滞在しているので、行列
2018112774.tif 000074
は
【０１７８】
【数１３】
2018112774.tif 000075
（１６）
【０１７９】
となり、(2, 2)番目要素の値が増加する可能性がある。
【０１８０】
ユーザ1が他の分析対象となっている地理空間エリアに移動した場合（図５での2505参照）、ユーザ１の測位データPは、分析対象である地理空間エリアA2(= B1)にて観測されているので、行列
2018112774.tif 000076
は、
【０１８１】
【数１４】
2018112774.tif 000077
（１７）
【０１８２】
となり、(2, 2) 番目要素の値が増加する可能性があるとともに(2,1)番目の要素には、時刻sの時の値に1が加算される。
【０１８３】
＜移動イベント数データ2242の構成例＞
移動イベント数データ2242の構成例を図６に示す。移動イベント数データ2242は移動先分析対象地理空間エリア2221を意味するnB個の行、移動元分析対象地理空間エリア2222を意味するnB個の列から構成されるテーブルである。そのテーブルの(i, j) 番目要素2223は、現在時刻までの、すべてのユーザにおける分析対象地理空間エリア識別子がBiである地理空間エリアから分析対象地理空間エリア識別子がBjである地理空間エリアへの移動イベントの総発生回数である。
【０１８４】
＜移動イベント数データ生成部2232の処理＞
移動イベント数データ生成部2232は、次の手順を使って移動イベント数データ2242を更新する（請求項2の移動イベント数データ生成手段に相当する）。
【０１８５】
１. 現在の時刻tを求める。
【０１８６】
２．すべての分析対象地理空間エリアの組
2018112774.tif 000078
において、以下の処理を行う。
【０１８７】
（ａ）ユーザ毎移動イベント数データ2241内のデータと
【０１８８】
【数１５】
2018112774.tif 000079
（１８）
【０１８９】
より、現在時刻までの、すべてのユーザにおける分析対象地理空間エリア識別子がBiである地理空間エリアから分析対象地理空間エリア識別子がBjである地理空間エリアへの移動イベントの発生回数を求める。
【０１９０】
（ｂ）上記により得られた値ei,j(0, t)を移動イベント数データ2242の(i, j) 番目要素2223に格納する。
【０１９１】
＜推移行列データ2243の構成例＞
推移行列データ2243の構成例を図７に示す。推移行列データ2243は移動先分析対象地理空間エリア2331を意味するnB個の行、移動元分析対象地理空間エリア2332を意味するnB個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素2333は、現在時刻までのすべてのユーザにおける分析対象地理空間エリア識別子がBiである地理空間エリアから分析対象地理空間エリア識別子がBjである地理空間エリアへ移動する確率である。
【０１９２】
＜推移行列データ生成部2233の処理＞
推移行列データ生成部2233は、次の手順を使って推移行列データ2243を更新する（請求項2の推移行列データ生成手段に相当する）。
【０１９３】
１．現在の時刻t を求める。
【０１９４】
２．すべての分析対象地理空間エリアの組
2018112774.tif 000080
において、以下の処理を行う。
【０１９５】
（ａ）移動イベント数データ2242と
【０１９６】
【数１６】
2018112774.tif 000081
（１９）
【０１９７】
を使って、現在時刻tまでの、すべてのユーザにおける分析対象地理空間エリア識別子がBiである地理空間エリアから分析対象地理空間エリア識別子がBjである地理空間エリアへ移動する確率を意味する
2018112774.tif 000082
を求める。
【０１９８】
（ｂ）上記により得られた値を推移行列データ2243の(i, j)番目要素2433に格納する。
【０１９９】
＜ユーザ移動地理空間エリア出力部2234の処理＞
オペレータ2より、現時点で地理空間エリアAiにいたユーザがkΔ後に地理空間エリアAjに移動する確率の出力を依頼されたとき以下の処理を行う（請求項2でのユーザ移動地理空間エリア出力手段に相当する）。
【０２００】
１．分析対象地理空間エリア群データ2121を使って、地理空間エリア識別子がAiである地理空間エリアに対応する分析対象地理空間エリア識別子Bｉ’を求める。
【０２０１】
２．同様に、地理空間エリア識別子がAjである地理空間エリアに対応する分析対象地理空間エリア識別子Bｊ’を求める。
【０２０２】
３．推移行列データ2243である{PB}を使って、その行列のk乗すなわち{PB}kを求める。
【０２０３】
４．上記で得られた{PB}kの(i',j')成分の値をオペレータ２に通知する。
【０２０４】
＜地理空間エリア滞在率予測部2300＞
＜地理空間エリア滞在率予測部2300の構成例＞
図８に第１の実施の形態に係る地理空間エリア滞在率予測部2300の構成例を示す。地理空間エリア滞在率予測部2300は、分析対象地理空間エリア滞在ユーザ数データ2361を生成する分析対象地理空間エリア滞在ユーザ数データ生成部2351に、予測分析対象地理空間エリア滞在率データ2362を生成する予測分析対象地理空間エリア滞在率データ生成部2352と、オペレータ2に将来時刻での各地理空間エリアでのユーザ滞在率を通知する地理空間エリア滞在率出力部2253から構成される。
【０２０５】
＜分析対象地理空間エリア滞在ユーザ数データ2361の構成例＞
分析対象地理空間エリア滞在ユーザ数データ2361の構成例を図９に示す。分析対象地理空間エリア滞在ユーザ数データ2361は、組（分析地理空間エリア識別子、滞在ユーザ数、滞在ユーザ比率）のnB 個の要素からなるテーブルである。i番目要素2341は、現在時刻において分析対象地理空間エリア識別子がBiである分析対象地理空間エリアに滞在しているユーザ数であり、i番目要素2342は、現在時刻において分析対象地理空間エリア識別子がBiである分析対象地理空間エリアに滞在しているユーザの比率である。
【０２０６】
＜分析対象地理空間エリア滞在ユーザ数データ生成部2351の処理＞
分析対象地理空間エリア滞在ユーザ数データ生成部2351は、次の手順を使って分析対象地理空間エリア滞在ユーザ数データ2361を更新する（請求項2での分析対象地理空間エリア滞在ユーザ数生成手段に対応する）。
【０２０７】
すべての分析対象地理空間エリアBi,i=1, 2,・・・, nBにおいて、以下の手順を行う。
【０２０８】
１．分析対象地理空間エリア群データ2121を使って、分析対象地理空間エリアBiに対応する地理空間エリア識別子A*を求める。
【０２０９】
２．時空間データ21から現在時刻において地理空間エリア識別子がA*である地理空間エリアに滞在しているユーザ数
2018112774.tif 000083
に対応する）を求める。
【０２１０】
３．上記により得られた値を分析対象地理空間エリア滞在ユーザ数データ2361のi番目要素2342に格納する。
【０２１１】
４．時刻tにおいて、分析対象地理空間エリアBi に対応する地理空間エリアに滞在しているユーザの比率を
2018112774.tif 000084
とすると、
2018112774.tif 000085
は、
【０２１２】
【数１７】
2018112774.tif 000086
（２０）
【０２１３】
として与えられる。
【０２１４】
上式を使って、現在時刻において分析対象地理空間エリアBiである地理空間エリアに滞在しているユーザの比率（上式の
2018112774.tif 000087
に対応する）を求める。
【０２１５】
５．上記により得られた値を分析対象地理空間エリア滞在ユーザ数データ2361のi番目要素に格納する。
【０２１６】
＜予測分析対象地理空間エリア滞在率データ2362の構成例＞
予測分析対象地理空間エリア滞在率データ2362の構成例を図１０に示す。予測分析対象地理空間エリア滞在率データ2362はnB個の行、m’個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素2341は、未来時刻t + iΔT において分析対象地理空間エリアBjに対応する地理空間エリアにユーザが滞在している確率である。
【０２１７】
＜予測分析対象地理空間エリア滞在率データ生成部2352の処理＞
予測分析対象地理空間エリア滞在率データ生成部2352は次の手順を使って予測分析対象地理空間エリア滞在率データ2362を更新する（請求項2での予測分析対象地理空間エリア滞在率データ生成手段に相当する）。
【０２１８】
未来時刻
2018112774.tif 000088
とすべての分析対象エリア
2018112774.tif 000089
において、以下の手順を行う。
【０２１９】
１．以下の式のPBに対応する推移行列データ2243と、以下の式のπB(t)に対応する分析対象地理空間エリア滞在ユーザ数データ2361での滞在ユーザ比率の列と、以下の式を使って未来時刻t+ iΔTにおいて分析対象地理空間エリアBjにユーザが滞在している確率2341を求める。
【０２２０】
【数１８】
2018112774.tif 000090
（２１）
2018112774.tif 000091
（２２）
2018112774.tif 000092
2018112774.tif 000093
（２３）
2018112774.tif 000094
2018112774.tif 000095
（２４）
【０２２１】
２．上記により得られた値を予測分析対象地理空間エリア滞在率データ2362の(i, j)要素に格納する。
【０２２２】
＜地理空間エリア滞在率出力部2253の処理＞
地理空間エリア滞在率出力部2253は、予測分析対象地理空間エリア滞在率データ2362と分析対象地理空間エリア群データ2121を使ってオペレータ2に情報を提供する。
【０２２３】
＜本発明の第１の実施の形態に係る時空間データマイニング装置の作用＞
次に、本発明の第１の実施の形態に係る時空間データマイニング装置2000の作用について説明する。
【０２２４】
まず、地理空間エリア群データ生成部12は、オペレータ2の指示により地理空間エリア群データ22を作成する。
【０２２５】
そして、ユーザ111、112に装着されている測位装置141、142から、ユーザ111、112の測位データが、通信ネットワーク46上の基地局48に集められ、時空間データマイニング装置2000に送られる。
【０２２６】
時空間データ生成部11は、通信ネットワーク46を経て測位データを受信した場合、受信した測位データのユーザを識別し、時空間データ21において、そのユーザ識別子をもつ時空間データ203を探索し、その時空間データ203に受信した測位データを追加する。
【０２２７】
そして、分析対象地理空間エリア群データ生成部2111は、測位データPが時空間データ21に追加された時、上述した分析対象地理空間エリア増加アルゴリズムを行って、分析対象地理空間エリア群データ2121を更新する。
【０２２８】
また、オペレータ２により、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率の出力が依頼された場合、ユーザ毎移動イベント数データ生成部2231は、上述した
2018112774.tif 000096
算出アルゴリズムを使ってユーザ毎移動イベント数データ2241を更新する。
【０２２９】
そして、移動イベント数データ生成部2232は、ユーザ毎移動イベント数データ2241を用いて、移動イベント数データ2242を更新する。
【０２３０】
そして、推移行列データ生成部2233は、移動イベント数データ2242を用いて、推移行列データ2243を更新する。
【０２３１】
そして、ユーザ移動地理空間エリア出力部2234は、分析対象地理空間エリア群データ2121と、推移行列データ2243とを用いて、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率を算出し、オペレータ２に通知する。
【０２３２】
また、オペレータ２により、未来時刻における各地理空間エリアのユーザの滞在率の出力が依頼された場合、分析対象地理空間エリア滞在ユーザ数データ生成部2351は、時空間データ21を用いて、分析対象地理空間エリア滞在ユーザ数データ2361を更新する。
【０２３３】
そして、予測分析対象地理空間エリア滞在率データ生成部2352は、推移行列データ2243と、分析対象地理空間エリア滞在ユーザ数データ2361での滞在ユーザ比率の列とを用いて、未来時刻t+ jΔTにおいて各分析対象地理空間エリアにユーザが滞在している確率2341を求め、予測分析対象地理空間エリア滞在率データ2362を更新する。
【０２３４】
そして、地理空間エリア滞在率出力部2253は、予測分析対象地理空間エリア滞在率データ2362と分析対象地理空間エリア群データ2121を使ってオペレータ2に情報を提供する。
【０２３５】
以上説明したように、本発明の第１の実施の形態に係る時空間データマイニング装置によれば、計算量を抑えて、時空間データを分析して、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率や、未来時刻における各地理空間エリアのユーザの滞在率を予測することができる。
【０２３６】
＜本発明の第２の実施の形態に係る時空間データマイニング装置の構成＞
次に、本発明の第２の実施の形態に係る時空間データマイニング装置の構成について説明する。図１１に示すように、本発明の第２の実施の形態に係る時空間データマイニング装置3001は、ＣＰＵと、ＲＡＭと、プログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。時空間データマイニング装置3001は、移動体に備え付けられた測位装置によって得られる位置情報と、測位装置により位置情報が計測された時刻との組からなる一連の測位データから構成される時空間データを分析する装置である。この時空間データマイニング装置3001は、機能的には図１１に示すように、分析対象論理空間エリア群データ管理部3100、ユーザ移動地理空間エリア予測部3200、及び地理空間エリア滞在率予測部3300から構成される。すなわち、第１の実施の形態に係る時空間データマイニング装置2000での分析対象地理空間エリア群データ管理部2100を分析対象論理空間エリア群データ管理部3100に、ユーザ移動地理空間エリア予測部2200をユーザ移動地理空間エリア予測部3200に、地理空間エリア滞在率予測部2300を地理空間エリア滞在率予測部3300に置き換えている。なお、従来技術として説明した時空間データマイニング装置１、及び第１の実施の形態に係る時空間データマイニング装置2000と同様の構成となる部分については同一符号を付して説明を省略する。
【０２３７】
＜分析対象論理空間エリア群データ管理部3100＞
＜分析対象論理空間エリア群データ管理部3100の構成例＞
分析対象論理空間エリア群データ管理部3100を図１２に示す。分析対象論理空間エリア群データ管理部3100では、従来の時空間データ生成部11、時空間データ21、地理空間エリア群データ生成部12、地理空間エリア群データ22に、分析対象論理エリア群データ3121、論理エリアトポロジーデータ3122、分析対象葉エリア群データ3123、統合候補論理エリア群データ3124、分析対象最大論理エリア数データ3032、分析対象論理エリア群データ生成部3111、論理エリアトポロジーデータ生成部3112、分析対象最大論理エリア数データ生成部3131、測位データ追加処理部3141、論理エリア価値計算部3151、論理エリア統合処理部3152、論理エリア分割処理部3153、論理エリア構成最適判定部3154、子論理エリア算出部3113、及び親論理エリア算出部3114が加えられている。
【０２３８】
＜論理エリアトポロジーデータ3122の構成例＞
上記図２８で示した地理空間上のエリア構成での論理エリアトポロジーデータ3122の構成例を図１３に示す。論理エリアトポロジーデータ3122は、ツリー状のデータから構成される。図１３の例では論理エリアトポロジーデータ3122は3階層からなり、最上位層の論理エリア群4101、第2層の論理エリア群4102、最下位層の論理エリア群4103から構成されている。論理エリアのトポロジーにおいて、最下位に位置する論理エリアを葉論理エリアと呼ぶ。
【０２３９】
後に説明する論理エリア統合・分割アルゴリズムを正しく動作させるために、次に示す親の論理エリアと子の論理エリア間の条件（論理エリアトポロジー構成条件）を設ける。
【０２４０】
［論理エリアトポロジー構成条件］
・親論理エリアは1つ以上の子の論理エリアから構成される。
・すべての子の論理エリアに対応するすべての地理空間エリアにおいて地理的に重なる部分はない。
・子の論理エリアの集合により構成される地理空間エリア群は親論理エリアの地理空間エリア群と完全に一致する。
・１つの葉論理エリアには、１つの地理空間と同一視できる。
【０２４１】
＜論理エリアトポロジーデータ生成部3112の処理＞
論理エリアトポロジーデータ生成部3112はオペレータ2の指示に従い、論理エリアトポロジー構成条件を満たすように論理エリアトポロジーデータ3122を構成する（請求項3での論理エリアトポロジーデータ生成手段に相当する）。
【０２４２】
＜分析対象最大論理エリア数データ生成部3131の処理＞
分析対象最大論理エリア数データ生成部3131はオペレータ2の指示に従い、分析対象の論理エリア数の最大値を分析対象最大論理エリア数データ3032に設定する（請求項3での分析対象最大論理エリア数データ生成手段に相当する）。
【０２４３】
＜分析対象論理エリア群データ3121の構成例＞
分析対象論理エリア群データ3121の構成例を図１４に示す。
【０２４４】
分析対象最大論理エリア数データ3032に格納されている値（分析対象最大論理エリア数データ）をnFとすると、分析対象論理エリア群データ3121にはnF個の組（分析対象となっている論理エリア識別子4121、分析対象となっている論理エリアに対応する論理エリアトポロジーデータ3122上の論理エリア識別子4122）から構成されている。
【０２４５】
＜分析対象葉エリア群データ3123の構成例＞
分析対象葉エリア群データ3123の構成例を図１５に示す。分析対象葉論理エリアの数をnLとすると、分析対象葉エリア群データ3123にはnL個の組（分析対象となっている葉論理エリアの識別子4131、分析対象となっている葉論理エリアに対応する地理空間エリア識別子4132）から構成されている。
【０２４６】
＜統合候補論理エリア群データ3124の構成例＞
統合候補論理エリア群データ3124の構成例を図１６に示す。
【０２４７】
統合候補論理エリアは、後に述べるように統合候補となる論理エリアである。
【０２４８】
＜子論理エリア算出部3113の処理＞
論理エリアトポロジーデータ3122を使って、指定された論理エリアの識別子に対する子論理エリアの識別子を返す（請求項3での子論理エリア算出手段に相当する）。
【０２４９】
＜親論理エリア算出部3114の処理＞
論理エリアトポロジーデータ3122を使って、指定された論理エリアの識別子に対する親論理エリアの識別子を返す（請求項３での親論理エリア算出手段に相当する）。
【０２５０】
＜測位データ追加処理部3141の処理＞
測位データPが時空間データ21に追加された時、測位データ追加処理部3141は以下の分析対象葉論理エリア増加アルゴリズムを行う。
【０２５１】
［分析対象葉論理エリア増加アルゴリズム］
１．追加された測位データP(= (x, y, t))の座標情報(x, y) からその測位データが観測された地点を含む地理空間エリアを特定し、その地理空間エリアをAPとする。
【０２５２】
２．その地理空間エリアAPの識別子が、分析対象葉エリア群データ3123での分析対象葉地理空間エリア識別子の集合内の要素と合致するかを調べ、その結果に応じて以下の処理を行う。
【０２５３】
地理空間エリアAPの識別子が分析対象葉地理空間エリア識別子の集合内の要素と合致しない場合（地理空間エリアAPに対応する葉論理エリアが、分析対象となっている葉論理エリアの集合の要素でない場合）、以下の（ａ）、（ｂ）の処理を行う。
【０２５４】
（ａ）以下の手順を行って、地理空間エリアAPに対応する葉論理エリアを分析対象となっている葉論理エリアの集合に追加する。
【０２５５】
i. 論理エリアトポロジーデータ3122を使って、地理空間エリアAPに対応する葉論理エリアGを求める。
【０２５６】
ii.分析対象葉エリア群データ3123の大きさであるｎLを1つ増加させる。
【０２５７】
iii.分析対象葉エリア群データ3123において、分析対象葉論理エリア識別子4131の集合に要素
2018112774.tif 000097
を追加する。
【０２５８】
iv.分析対象葉エリア群データ3123において、分析対象葉論理エリア識別子4131が
2018112774.tif 000098
に対応する地理空間エリア識別子をAPの識別子とする。
【０２５９】
v.分析対象論理エリア群データ3121の大きさであるｎLを1つ増加させる。
【０２６０】
vi.分析対象論理エリア群データ3121において、分析対象となっている論理エリアの識別子4121の集合に要素
2018112774.tif 000099
を追加する。
【０２６１】
vii.分析対象論理エリア群データ3121において、分析対象論理エリア識別子4121が
2018112774.tif 000100
に対応する論理エリア識別子4122をGとする。
【０２６２】
（ｂ）以下の手順を行って、地理空間エリアAPに対応する葉論理エリアの親論理エリアを求め、それを統合候補である論理エリアの集合に追加する。
【０２６３】
i.親論理エリア算出部3133を使って、葉論理エリアGの親論理エリアpar(Ｇ)を求める。
【０２６４】
ii.親論理エリアpar(Ｇ)が統合候補論理エリア群データ3124内の要素でない場合、par(Ｇ)を統合候補論理エリア群データ3124に追加する。
【０２６５】
一方、地理空間エリアAPの識別子が分析対象葉地理空間エリア識別子の集合内の要素と合致する場合、何もしない。
【０２６６】
＜論理エリア価値計算部3151の処理＞
論理エリア価値計算部3151は、決められた式に従って論理エリアの価値を計算する（請求項３での論理エリア価値計算手段に相当する）。
【０２６７】
例えば、以下の手順を使って指定された論理エリアにおいて発生した測位データ数を論理エリアの価値とする。
【０２６８】
１.論理エリアトポロジーデータ3122を使って、指定された論理エリアに対応する葉論理エリア群を求める。
【０２６９】
２．分析対象葉エリア群データ3123を使って、葉論理エリア群に対応する地理空間エリア群を求める。
【０２７０】
３．時空間データ21を使って、地理空間エリア群において観測された測位データの総数を求める。
【０２７１】
＜論理エリア統合処理部3152の処理＞
論理エリア統合処理部3152は以下の処理を行う（請求項3での論理エリア統合処理手段に相当する）。
【０２７２】
１．以下の手順を行って、適切な論理エリアの統合により、分析対象となる論理エリアの集合を構成する。
【０２７３】
（ａ）統合候補論理エリア群データ3124内のすべての論理エリアにおいて、論理エリア価値計算部3151を使って、論理エリアの価値を求める。
【０２７４】
（ｂ）統合候補論理エリア群データ3124内のすべての論理エリアにおいて、最小の論理エリアの価値を持つ論理エリアＧを求める。
【０２７５】
（ｃ）論理エリアＧの子の論理エリア群{child(Ｇ)}を、子論理エリア算出部3113を使って求める。
【０２７６】
（ｄ）{child(Ｇ)}が、分析対象論理エリア群データ3121に含まれている場合は、その{child(Ｇ)}を分析対象論理エリア群データ3121から削除する。
【０２７７】
（ｅ）分析対象論理エリア群データ3121に論理エリアＧを追加する。
【０２７８】
２．以下の手順を行って、統合候補の論理エリア集合を構成する。
【０２７９】
（ａ）統合候補論理エリア群データ3124から論理エリアＧを削除する。
【０２８０】
（ｂ）論理エリアＧの親論理エリアpar(Ｇ)を、親論理エリア算出部3114を使って求め、統合候補論理エリア群データ3124に親論理エリアpar(Ｇ)を追加する。
【０２８１】
＜論理エリア分割処理部3153の処理＞
論理エリア分割処理部3153は以下の処理を行う（請求項3での論理エリア分割処理手段に対応する）。
【０２８２】
１．分析対象論理エリア群データ3121内のすべての論理エリアで論理エリア価値計算部3151を使って、最大の論理エリア価値を持つ論理エリアＧを求める。
【０２８３】
２．分析対象論理エリア群データ3121からＧを削除する。
【０２８４】
３．Ｇの子の論理エリア群{child(Ｇ)}を、子論理エリア算出部3113を使って求める。
【０２８５】
４．各子論理エリアにおいて、論理エリアトポロジーデータ3122を使って、該当する地理空間エリアを求め、時空間データ21を使って、その地理空間エリアに測位データが観測されているかを調べ、測位データが存在する場合、その論理エリアを分析対象論理エリア群データ3121に追加する。
【０２８６】
＜論理エリア構成最適判定部3154の処理＞
論理エリア構成最適判定部3154は以下の2つを同時に満たすかを判定する（請求項3での論理エリア構成最適判定手段に対応する）。
【０２８７】
・分析対象論理エリア群データ3121の要素数（すなわちnF）は、分析対象最大論理エリア数データ3032の値であるnth以下である。
【０２８８】
・統合候補論理エリア群データ3124内の論理エリアで最小の論理エリアの価値を
2018112774.tif 000101
とし、分析対象論理エリア群データ3121の論理エリアで最大の論理エリアの価値を
2018112774.tif 000102
とする。この時、
【０２８９】
【数１９】
2018112774.tif 000103
（２５）
【０２９０】
を満たすことである。
【０２９１】
＜分析対象論理エリア群データ生成部3111の処理＞
測位データPが時空間データ21に追加された時、分析対象論理エリア群データ3121の要素数nFがnth以下となるまで、論理エリア構成最適判定部3154を使って、上記（２５）式を満たすように論理エリア分割処理部3153を使って、分析対象となる論理エリアを求める請求項3での論理エリア構成最適判定手段に対応する）。
【０２９２】
＜ユーザ移動地理空間エリア予測部3200＞
＜ユーザ移動地理空間エリア予測部3200の構成例＞
図１７に、第２の実施の形態に係るユーザ移動地理空間エリア予測部3200の構成例を示す。上記図３で示した第１の実施の形態に係るユーザ移動地理空間エリア予測部2200においてユーザ毎移動イベント数データ生成部2231をユーザ毎論理エリア移動イベント数データ生成部3231に、移動イベント数データ生成部2232を論理エリア移動イベント数データ生成部3232に、推移行列データ生成部2233を推移行列データ生成部3233に、ユーザ移動地理空間エリア出力部2234をユーザ移動地理空間エリア出力部3234に、ユーザ毎移動イベント数データ2241をユーザ毎論理エリア移動イベント数データ3241に、移動イベント数データ2242を論理エリア移動イベント数データ3242に、推移行列データ2243を推移行列データ3243に、置き換えている。
【０２９３】
さらに、ユーザ毎葉論理エリア移動イベント数データ3240と、それを生成するユーザ毎葉論理エリア移動イベント数データ生成部3230と、論理エリアが与えられたとき、論理エリアトポロジーデータ3122を使ってそれを基点として枝における葉論理エリアの集合を算出する枝上葉論理エリア算出部3235とを追加している。
【０２９４】
＜ユーザ毎葉論理エリア移動イベント数データ3240の構成例＞
ユーザ毎葉論理エリア移動イベント数データの構成例を図１８に示す。ユーザ毎葉論理エリア移動イベント数データ3240は、nu個の葉論理エリア移動イベント数データ4211から構成される。ユーザ識別子がｕの葉論理エリア移動イベント数データ4211は移動先分析対象葉論理エリア4212を意味するnL個の行、移動元分析対象葉論理エリア4213を意味するnL個の列から構成されるテーブルである。そのテーブルの(i,j)番目要素4214は、現在時刻までにユーザ識別子uであるユーザが分析対象葉論理エリア識別子がGLiであるエリアから分析対象葉論理エリア識別子がGLjであるエリアへの移動イベントの総発生回数である。
【０２９５】
＜ユーザ毎葉論理エリア移動イベント数データ生成部3230の処理＞
ユーザ毎葉論理エリア移動イベント数データ生成部3230は、
【０２９６】
2018112774.tif 000104
算出アルゴリズムを使ってユーザ毎葉論理エリア移動イベント数データ3240を更新する。このアルゴリズムにより、ユーザuにおいて、時間帯(s, t)における分析対象となっている葉論理エリアGLiから分析対象となっている葉論理エリアGLjへの移動回数を求めることができる。
2018112774.tif 000105
算出アルゴリズムは請求項4での移動総数計数手段に相当する。
【０２９７】
［
2018112774.tif 000106
算出アルゴリズム］
【０２９８】
１．分析対象葉エリア群データ3123を使って、分析対象葉論理エリアGLiに対応する地理空間エリアA**iを求める。
【０２９９】
２．分析対象葉エリア群データ3123を使って、分析対象葉論理エリアGLjに対応する地理空間エリアA**jを求める。
【０３００】
３．時刻s以上で直近のmsΔTを求める。
【０３０１】
msは
【０３０２】
【数２０】
2018112774.tif 000107
（２６）
【０３０３】
として与えられる。
2018112774.tif 000108
はaの切り上げを意味する。
【０３０４】
４．時刻t以下で直近のmtΔTを求める。
【０３０５】
mtは
【０３０６】
【数２１】
2018112774.tif 000109
（２７）
【０３０７】
として与えられる。
2018112774.tif 000110
はaの切り下げを意味する。
【０３０８】
５.離散時刻
2018112774.tif 000111
において以下の処理を行う。
【０３０９】
（ａ）地理空間移動イベント
2018112774.tif 000112
算出アルゴリズム(m=ms,ms+1,・・・,mt)を実行する。
【０３１０】
（ｂ）地理空間移動イベント
2018112774.tif 000113
算出アルゴリズムによりユーザuの地理空間エリアA**iからA**jへの移動イベントが得られるごとにユーザuの地理空間エリアA**iからA**jへの移動イベント数を加算していく。
【０３１１】
最終的に得られるユーザuの地理空間エリアA**iからA**への移動イベント数を
2018112774.tif 000114
とする。
【０３１２】
＜ユーザ毎葉論理エリア移動イベント数データ生成部3230の処理＞
【０３１３】
ユーザ毎葉論理エリア移動イベント数データ生成部3230は、測位データPが時空間データ21に追加されたとき、以下の処理を行う（請求項4の直前測位データ特定手段、ユーザ毎葉論理エリア移動イベント数データ生成手段に相当する）。
【０３１４】
1. 現在の時刻tを求める。
【０３１５】
２．分析対象葉エリア群データ3123の要素数をnLとする。
【０３１６】
３．追加された測位データPのユーザuを特定する。
【０３１７】
４．時空間データ21のユーザuの時空間データ203Duにおいて測位データPが保存される前の最後に保存された測位データＱを探索する。
【０３１８】
５．測位データＱの記録時刻をsとする。
【０３１９】
６．測位データＱの座標情報が観測された地点を含む地理空間エリアを特定し、その地理空間エリアを
2018112774.tif 000115
とする。
【０３２０】
７．分析対象葉エリア群データ3123での分析対象葉地理空間エリア識別子4132の集合において
2018112774.tif 000116
に等しい要素を見つけ、それを
2018112774.tif 000117
とする。
【０３２１】
８．地理空間エリアAPの種別により以下の処理を行う。
【０３２２】
・ＣａｓｅＩ（測位データPはPを記録する前の分析対象葉論理エリア上ではない場合）では、以下の（ａ）〜（ｃ）の処理を行う。
【０３２３】
（ａ）ユーザ毎葉論理エリア移動イベント数データ3240の(i, i)番目の要素の値を次の値で更新する。
【０３２４】
【数２２】
2018112774.tif 000118
（２８）
【０３２５】
（ｂ）ユーザ毎葉論理エリア移動イベント数データ3240のnL行とnL列の要素を追加する。
【０３２６】
（ｃ）追加された要素において、要素(i, nL)の値を１とし、それ以外の要素の値を0とする。
【０３２７】
・ＣａｓｅII（測位データPはPを記録する前の分析対象葉論理エリアにある場合）では、分析対象葉エリア群データ3123での分析対象葉地理空間エリア識別子4132の集合においてAPに等しい要素を見つけ、それを
2018112774.tif 000119
とする。
【０３２８】
そして、ユーザuが同一地理空間エリア
2018112774.tif 000120
に滞在していた場合（つまり、
2018112774.tif 000121
の場合）、ユーザ毎葉論理エリア移動イベント数データ3240の(i, i)番目の要素の値を次の値で更新する。
【０３２９】
【数２３】
2018112774.tif 000122
（２９）
【０３３０】
ユーザuがすでに分析対象となっている他の地理空間エリアに移動した場合（つまり、
2018112774.tif 000123
の場合）、ユーザ毎葉論理エリア移動イベント数データ3240の(i, i)番目の要素の値を次の値で更新する。
【０３３１】
【数２４】
2018112774.tif 000124
（３０）
【０３３２】
ユーザ毎葉論理エリア移動イベント数データ3240の(i, j)番目の要素の値を次の値で更新する。
【０３３３】
【数２５】
2018112774.tif 000125
（３１）
【０３３４】
＜枝上葉論理エリア算出部3235の処理＞
論理エリアトポロジーデータ3122を使って、指定された論理エリアの識別子に対する論理エリアを起点とした枝上にある各葉論理エリアの識別子を返す（請求項4での枝上葉論理エリア算出手段に相当する）。
【０３３５】
＜ユーザ毎論理エリア移動イベント数データ3241の構成例＞
第２の実施の形態に係るユーザ毎論理エリア移動イベント数データ3241の構成例を図１９に示す。ユーザ毎論理エリア移動イベント数データ3241は、nu個のユーザ識別子がｕの論理エリア移動イベント数データ4221から構成される。ユーザ識別子がuの論理エリア移動イベント数データ4221は移動先分析対象論理エリア4222を意味するnF個の行、移動元分析対象論理エリアを意味するnF個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素4222は、現在時刻までの、ユーザuにおける分析対象論理エリア識別子がGFiである分析対象論理エリアから分析対象論理エリア識別子がGFjである分析対象論理エリアへの移動イベントの総発生回数である。
【０３３６】
＜ユーザ毎論理エリア移動イベント数データ生成部3231の処理＞
ユーザ毎論理エリア移動イベント数データ生成部3231は、ユーザ毎葉論理エリア移動イベント数データ3240が更新されると、以下の処理を行いユーザ毎論理エリア移動イベント数データ3241を更新する（請求項4でのユーザ毎論理エリア移動イベント数データ生成手段に相当する）。
【０３３７】
１．分析対象論理エリア群データ3121内の論理エリア
2018112774.tif 000126
において、枝上葉論理エリア算出部3235を使って、論理エリアGFiを基点とする枝における葉論理エリアの集合
2018112774.tif 000127
を求める。
【０３３８】
２．分析対象論理エリア群データ3121内の論理エリア
2018112774.tif 000128
において、枝上葉論理エリア算出部3235を使って、論理エリアGFjを基点とする枝における葉論理エリアの集合
2018112774.tif 000129
を求める。
【０３３９】
３．ユーザ毎葉論理エリア移動イベント数データ3240を使って、葉論理エリア群
2018112774.tif 000130
の何れかの葉論理エリアから、葉論理エリア群
2018112774.tif 000131
の何れかの葉論理エリアへ移動したイベントの発生回数を求める。
【０３４０】
４．上記の値を
2018112774.tif 000132
として、ユーザ毎葉論理エリア移動イベント数データ3240の(i, j)要素に格納する。
【０３４１】
＜論理エリア移動イベント数データ3242の構成例＞
論理エリア移動イベント数データ3242の構成例を図２０に示す。論理エリア移動イベント数データ3242は、移動先分析対象論理エリア4412を意味するnF個の行、移動元分析対象論理エリア4413を意味するnF個の列から構成されるテーブルである。そのテーブルの(i, j) 番目要素4414は、現在時刻までにすべてのユーザにおいて分析対象論理エリア識別子がGFiである分析対象論理エリアから分析対象論理エリア識別子がGFjである分析対象論理エリアへの移動イベントの総発生回数である。
【０３４２】
＜論理エリア移動イベント数データ生成部3232の処理＞
論理エリア移動イベント数データ生成部3232は、次の手順を使って論理エリア移動イベント数データ3242を更新する（請求項4での論理エリア移動イベント数データ生成手段に相当する）。
【０３４３】
１．現在の時刻tを求める。
【０３４４】
２．すべての分析対象論理エリアの組
2018112774.tif 000133
において、以下の処理を行う。
【０３４５】
（ａ）ユーザ毎論理エリア移動イベント数データ3241内のデータと
【０３４６】
【数２６】
2018112774.tif 000134
（３２）
【０３４７】
より、現在時刻までの、すべてのユーザにおける分析対象論理エリア識別子がGFiである論理エリアから分析対象論理エリア識別子がGFjである論理エリアへの移動イベントの発生回数を求める。
【０３４８】
（ｂ）上記により得られた値
2018112774.tif 000135
を論理エリア移動イベント数データ3242の(i, j)番目要素とする。
【０３４９】
＜推移行列データ3243の構成例＞
推移行列データ3243の構成例を図２１に示す。推移行列データ3243は、移動先分析対象論理エリア4231を意味するnF個の行、移動元分析対象論理エリア4232を意味するnF個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素4233は、分析対象論理エリア識別子がGFiである分析対象論理エリアから分析対象論理エリア識別子がGFjである分析対象論理エリアへ移動する確率である。
【０３５０】
＜推移行列データ生成部3233の処理＞
推移行列データ生成部3233は、次の手順を使って推移行列データ3243を更新する（請求項4での推移行列データ生成手段に相当する）。
【０３５１】
１．現在の時刻tを求める。
【０３５２】
２．すべての分析対象論理エリアの組
2018112774.tif 000136
において、以下の処理を行う。
【０３５３】
（ａ）論理エリア移動イベント数データ3242と
【０３５４】
【数２７】
2018112774.tif 000137
（３３）
【０３５５】
を使って、現在時刻tまでの、すべてのユーザにおける分析対象論理エリアGFiから分析対象論理エリアGFjへ移動する確率
2018112774.tif 000138
を求める。
【０３５６】
（ｂ）上記により得られた値を推移行列データ3243の(i, j) 番目要素4233に格納する。
【０３５７】
＜ユーザ移動地理空間エリア出力部3234の処理＞
オペレータ2より、現時点で地理空間エリアAiにいたユーザがkΔ後に地理空間エリアAjに移動する確率の出力を依頼されたとき以下の処理を行う。
【０３５８】
１．分析対象葉エリア群データ3123を使って、地理空間エリア識別子がAiである地理空間エリアに対応する分析対象葉エリア識別子Bi’を求める。
【０３５９】
２．論理エリアトポロジーデータ3122と分析対象論理エリア群データ3121を使って、分析対象葉エリア識別子Bi’を含む分析対象論理エリア識別子Gｉ'' を求める。
【０３６０】
３．同様に、地理空間エリア識別子がAjである地理空間エリアに対応する分析対象論理エリア識別子Gｊ''を求める。
【０３６１】
４．推移行列データ3243である{PG}を使って、その行列のk乗すなわち{PG}kを求める。
【０３６２】
５．上記で得られた{PG}kの（ｉ''，ｊ''）成分の値をオペレータ２ に通知する。
【０３６３】
＜地理空間エリア滞在率予測部3300＞
＜地理空間エリア滞在率予測部3300の構成例＞
図２２に、第２の実施の形態に係る地理空間エリア滞在率予測部3300の構成例を示す。地理空間エリア滞在率予測部3300は、分析対象論理エリア滞在ユーザ数データ3361を生成する分析対象論理エリア滞在ユーザ数データ生成部3351と、予測分析対象論理エリア滞在率データ3362を生成する予測分析対象論理エリア滞在率データ生成部3352と、オペレータ2に将来時刻での各地理空間エリアでのユーザ滞在率を通知する地理空間エリア滞在率出力部3353とから構成される。
【０３６４】
＜分析対象論理エリア滞在ユーザ数データ3361の構成例＞
分析対象論理エリア滞在ユーザ数データ3361の構成例を図２３に示す。分析対象論理エリア滞在ユーザ数データ3361は、組（分析対象論理エリア識別子、滞在ユーザ数、滞在ユーザ比率）のnF個の要素からなるテーブルである。i番目要素4241は、現在時刻において分析対象論理エリア識別子がGFiである論理エリアに滞在しているユーザ数であり、i 番目要素4342は、現在時刻において分析対象論理エリア識別子がGFiである論理エリアに滞在しているユーザの比率である。
【０３６５】
＜分析対象論理エリア滞在ユーザ数データ生成部3351の処理＞
分析対象論理エリア滞在ユーザ数データ生成部3351は、次の手順を使って分析対象論理エリア滞在ユーザ数データ3361を更新する（請求項4での分析対象論理エリア滞在ユーザ数生成手段に相当する）。
【０３６６】
すべての分析対象論理エリア
2018112774.tif 000139
において、以下の手順を行う。
【０３６７】
１．論理エリアトポロジーデータ3122を使って、論理エリアGFiに対応する地理空間エリア群
2018112774.tif 000140
を求める。
【０３６８】
２．時空間データ21から現在時刻において
2018112774.tif 000141
のすべての地理空間エリアでの滞在人数の総和を求め、その総和をsFiとする。
【０３６９】
３．sFiを分析対象論理エリア滞在ユーザ数データ3361のi番目要素4321に格納する。
【０３７０】
４．以下の式を使って、現在時刻において
2018112774.tif 000142
のすべての地理空間エリアに滞在しているユーザの比率πFiを求める。
【０３７１】
【数２８】
2018112774.tif 000143
（３４）
【０３７２】
５．上記により得られた値πFiを分析対象論理エリア滞在ユーザ数データ3361のi番目要素4321に格納する。
【０３７３】
＜予測分析対象論理エリア滞在率データ3362の構成例＞
予測分析対象論理エリア滞在率データ3362の構成例を図２４に示す。
【０３７４】
予測分析対象論理エリア滞在率データ3362はnF個の行、m’個の列から構成されるテーブルである。そのテーブルの(i, j)番目要素は、未来時刻t+iΔT において分析対象論理エリアGFjにユーザが滞在している確率4341である。
【０３７５】
＜予測分析対象論理エリア滞在率データ生成部3352の処理＞
予測分析対象論理エリア滞在率データ生成部3352は次の手順を使って予測分析対象論理エリア滞在率データ3362を更新する（請求項4での予測論理エリア滞在率データ生成手段に相当する）。
【０３７６】
未来時刻
2018112774.tif 000144
とすべての分析対象論理エリア
2018112774.tif 000145
において、以下の手順を行う。
【０３７７】
１．以下の式のPFに対応する推移行列データ3243と、以下の式のπF (t)に対応する分析対象論理エリア滞在ユーザ数データ3361での滞在ユーザ比率の列と以下の式を使って未来時刻t + iΔT において分析対象論理エリアGjにユーザが滞在している確率4341を求める。
【０３７８】
【数２９】
2018112774.tif 000146
（３５）
2018112774.tif 000147
（３６）
2018112774.tif 000148
2018112774.tif 000149
（３７）
2018112774.tif 000150
2018112774.tif 000151
（３８）
【０３７９】
２．上記により得られた値を予測分析対象論理エリア滞在率データ3362の(i, j)要素に格納する。
【０３８０】
＜地理空間エリア滞在率出力部3353の処理＞
地理空間エリア滞在率出力部3353は、予測分析対象論理エリア滞在率データ3362と論理エリアトポロジーデータ3122を使ってオペレータ2 に情報を提供する。
【０３８１】
＜本発明の第２の実施の形態に係る時空間データマイニング装置の作用＞
次に、本発明の第２の実施の形態に係る時空間データマイニング装置3001の作用について説明する。
【０３８２】
まず、地理空間エリア群データ生成部12は、オペレータ2の指示により地理空間エリア群データ22を作成する。また、論理エリアトポロジーデータ生成部3112は、オペレータ2の指示に従い、論理エリアトポロジー構成条件を満たすように論理エリアトポロジーデータ3122を構成する。
【０３８３】
分析対象最大論理エリア数データ生成部3131はオペレータ2の指示に従い、分析対象の論理エリア数の最大値を分析対象最大論理エリア数データ3032に設定する。
【０３８４】
そして、ユーザ111、112に装着されている測位装置141、142から、ユーザ111、112の測位データが、通信ネットワーク46上の基地局48に集められ、時空間データマイニング装置3001に送られる。
【０３８５】
時空間データ生成部11は、通信ネットワーク46を経て測位データを受信した場合、受信した測位データのユーザを識別し、時空間データ21において、そのユーザ識別子をもつ時空間データ203を探索し、その時空間データ203に受信した測位データを追加する。
【０３８６】
そして、測位データ追加処理部3141は、測位データPが時空間データ21に追加された時、上述した分析対象葉論理エリア増加アルゴリズムを行って、分析対象葉エリア群データ3123、分析対象論理エリア群データ3121、及び統合候補論理エリア群データ3124を更新する。
【０３８７】
そして、論理エリア構成最適判定部3154によって上記（１５）式に示す条件を満たすまで、論理エリア統合処理部3152の処理と、論理エリア分割処理部3153の処理とを繰り返す。
【０３８８】
また、ユーザ毎葉論理エリア移動イベント数データ生成部3230は、測位データPが時空間データ21に追加されたとき、
2018112774.tif 000152
算出アルゴリズムを使ってユーザ毎葉論理エリア移動イベント数データ3240を更新する。
【０３８９】
また、オペレータ２により、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率の出力が依頼された場合、論理エリア移動イベント数データ生成部3232は、ユーザ毎論理エリア移動イベント数データ3241を用いて、論理エリア移動イベント数データ3242を更新する。
【０３９０】
そして、推移行列データ生成部3233は、論理エリア移動イベント数データ3242を用いて、推移行列データ3243を更新する。
【０３９１】
そして、ユーザ移動地理空間エリア出力部2234は、分析対象葉エリア群データ3123と、論理エリアトポロジーデータ3122と、分析対象論理エリア群データ3121と、推移行列データ2243とを用いて、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率を算出し、オペレータ２に通知する。
【０３９２】
また、オペレータ２により、未来時刻における各地理空間エリアのユーザの滞在率の出力が依頼された場合、分析対象論理エリア滞在ユーザ数データ生成部3351は、論理エリアトポロジーデータ3122と時空間データ21を用いて、分析対象論理エリア滞在ユーザ数データ3361を更新する。
【０３９３】
そして、予測分析対象論理エリア滞在率データ生成部3352は、推移行列データ3243と、分析対象論理エリア滞在ユーザ数データ3361での滞在ユーザ比率の列とを用いて、未来時刻t + jΔT において分析対象論理エリアGjにユーザが滞在している確率4341を求め、予測分析対象論理エリア滞在率データ3362を更新する。
【０３９４】
そして、地理空間エリア滞在率出力部3353は、予測分析対象論理エリア滞在率データ3362と論理エリアトポロジーデータ3122を使ってオペレータ2 に情報を提供する。
【０３９５】
以上説明したように、本発明の第２の実施の形態に係る時空間データマイニング装置によれば、計算量を抑えて、時空間データを分析して、現在時刻においてある地理空間エリアにいたユーザが未来時刻にある地理空間エリアに移動する確率や、未来時刻における各地理空間エリアのユーザの滞在率を予測することができる。
【０３９６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０３９７】
例えば、移動体として、歩行者（ユーザ）を対象とした場合を例に説明したが、これに限定されるものではなく、歩行者以外の移動物、例えば車両を対象としてもよい。
【０３９８】
また、上述の時空間データマイニング装置2000、3001は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０３９９】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０４００】
11     時空間データ生成部
12     地理空間エリア群データ生成部
21     時空間データ
22     地理空間エリア群データ
46     通信ネットワーク
48     基地局
111,112       ユーザ
141,142       測位装置
2000   時空間データマイニング装置
2100   分析対象地理空間エリア群データ管理部
2111   分析対象地理空間エリア群データ生成部
2121   分析対象地理空間エリア群データ
2200   ユーザ移動地理空間エリア予測部
2211   移動イベント数データ
2231   ユーザ毎移動イベント数データ生成部
2232   移動イベント数データ生成部
2233   推移行列データ生成部
2234   ユーザ移動地理空間エリア出力部
2241   ユーザ毎移動イベント数データ
2242   移動イベント数データ
2243   推移行列データ
2253   地理空間エリア滞在率出力部
2300   地理空間エリア滞在率予測部
2351   分析対象地理空間エリア滞在ユーザ数データ生成部
2352   予測分析対象地理空間エリア滞在率データ生成部
2361   分析対象地理空間エリア滞在ユーザ数データ
2362   予測分析対象地理空間エリア滞在率データ
3001   時空間データマイニング装置
3032   分析対象最大論理エリア数データ
3100   分析対象論理空間エリア群データ管理部
3111   分析対象論理エリア群データ生成部
3112   論理エリアトポロジーデータ生成部
3113   子論理エリア算出部
3114   親論理エリア算出部
3121   分析対象論理エリア群データ
3122   論理エリアトポロジーデータ
3123   分析対象葉エリア群データ
3124   統合候補論理エリア群データ
3131   分析対象最大論理エリア数データ生成部
3133   親論理エリア算出部
3141   測位データ追加処理部
3151   論理エリア価値計算部
3152   論理エリア統合処理部
3153   論理エリア分割処理部
3154   論理エリア構成最適判定部
3200   ユーザ移動地理空間エリア予測部
3230   ユーザ毎葉論理エリア移動イベント数データ生成部
3231   ユーザ毎論理エリア移動イベント数データ生成部
3232   論理エリア移動イベント数データ生成部
3233   推移行列データ生成部
3234   ユーザ移動地理空間エリア出力部
3235   枝上葉論理エリア算出部
3240   ユーザ毎葉論理エリア移動イベント数データ
3241   ユーザ毎論理エリア移動イベント数データ
3242   論理エリア移動イベント数データ
3243   推移行列データ
3300   地理空間エリア滞在率予測部
3351   分析対象論理エリア滞在ユーザ数データ生成部
3352   予測分析対象論理エリア滞在率データ生成部
3353   地理空間エリア滞在率出力部
3361   分析対象論理エリア滞在ユーザ数データ
3362   予測分析対象論理エリア滞在率データ
【図１】
2018112774.tif 000153
【図２】
2018112774.tif 000154
【図３】
2018112774.tif 000155
【図４】
2018112774.tif 000156
【図５】
2018112774.tif 000157
【図６】
2018112774.tif 000158
【図７】
2018112774.tif 000159
【図８】
2018112774.tif 000160
【図９】
2018112774.tif 000161
【図１０】
2018112774.tif 000162
【図１１】
2018112774.tif 000163
【図１２】
2018112774.tif 000164
【図１３】
2018112774.tif 000165
【図１４】
2018112774.tif 000166
【図１５】
2018112774.tif 000167
【図１６】
2018112774.tif 000168
【図１７】
2018112774.tif 000169
【図１８】
2018112774.tif 000170
【図１９】
2018112774.tif 000171
【図２０】
2018112774.tif 000172
【図２１】
2018112774.tif 000173
【図２２】
2018112774.tif 000174
【図２３】
2018112774.tif 000175
【図２４】
2018112774.tif 000176
【図２５】
2018112774.tif 000177
【図２６】
2018112774.tif 000178
【図２７】
2018112774.tif 000179
【図２８】
2018112774.tif 000180
【図２９】
2018112774.tif 000181
【図３０】
2018112774.tif 000182
【図３１】
2018112774.tif 000183
【図３２】
2018112774.tif 000184
【図３３】
2018112774.tif 000185
【図３４】
2018112774.tif 000186
【図３５】
2018112774.tif 000187
【図３６】
2018112774.tif 000188
【図３７】
2018112774.tif 000189
【図３８】
2018112774.tif 000190