移動軌跡データモデルと
領域に基づく問合せ処理
† 日本電信電話株式会社
NTT コミュニケーション科学基礎研究所
‡ ATR 情報メディア研究所
○ 柳沢 豊† ,赤埴 淳一† ,小暮 潔‡
発表概要
• 移動軌跡データのモデリングに関する発表
– 研究の背景,目的
前半の発表
– 移動軌跡データとは
– 図形間の関係記述に基づくアプローチ
– リンクを用いた検索の効率化
– 形状の類似度に基づくアプローチ
– 重心を用いた線分の形状の近似方法
後半の発表
– まとめ
背景(1)
• GPSを始めとする,廉価で高精度の一取
得デバイスが開発されている.
– ナビゲーションシステム,位置依存情報サー
ビスなどへの応用が進んでいる.
位置依存情報
地域情報
ナビゲーション
背景(2)
• デバイスの普及に伴い,膨大な移動軌跡
データが日々取得され蓄積されている.
– データ分析により,ユーザの行動傾向の取得
や状況予測などに応用する動きが広がる.
課題
移動軌跡データをどのように分析するか?
移動軌跡データ
• 測定された位置座標と測定された時刻の
組の列として表される.
Y
tn
= (t1, x1, y1), (t2, x2, y2) … (tn, xn, yn)
分析のアプローチ
t1
t2
・ 位相幾何学的なアプローチ
・ 形状に基づくアプローチ
X
図形間の関係記述に基づく
アプローチ
• 移動軌跡データを連続な有向線分とみなし,空
間上の他の図形との関係記述によって,データ
の特徴付けを行う方法.
Z
Y
移動軌跡データ例
空間上にプロットしただけでは
移動軌跡データに意味づけが
しにくい.
X
図形間の関係記述に基づく
アプローチ
• 移動軌跡データを連続な有向線分とみなし,空
間上の他の図形との関係記述によって,データ
の特徴付けを行う方法.
Y
移動軌跡データを地図などと
重ね合わせ,地図に含まれる
領域(地形)データなどを使うと
特徴づけが行いやすい.
X
本研究でのアプローチ
• 移動軌跡と領域の関係を使って特徴づけを行う.
正門
大岡山駅エリア
大岡山駅エリア
正門
東工大エリア
本館
本館
東工大エリア
どのように記述すればよいか?
領域と線分の関係
• 閉領域と連続な線分との関係は,2x3行列
で表すことができる[Egenhöfer90,94].
境界: ∂R
閉領域
内部: R°
R
外部: R-
∂L
L°
∂R
R°
連続な線分
両端: ∂L
L
R-
関係記述行列
内部: L°
Φか¬Φが入る
領域と線分の関係
• 閉領域と連続な線分との関係は,2x3行列
で表すことができる[Egenhöfer90,94].
関係の例
R
L
線分の一端が領域内にあり,
もう一端は領域外にある.
∂L
L°
Φ
Φ
R°
¬Φ
¬Φ
R-
¬Φ
¬Φ
∂R
関係記述行列 T0
本研究での拡張
• 始点を∂0 L,終点を∂1 L と書いて区別することで,
有向線分を扱えるようにする.
– 閉領域との関係は 3x3 行列として表せる.
拡張部分
関係の例
T(R,L)
R
∂1 L
∂0L
L
線分の始点が領域内にあり,
終点が領域外にある.
∂0L
∂1L
L°
Φ
Φ
¬Φ
R°
Φ
¬Φ
¬Φ
R-
¬Φ
Φ
¬Φ
∂R
関係記述行列
可能な行列式は全26通り存在する.
26通りの関係
26通りの関係
いずれかの関係に分類できる.
線分の分割
• 線分を2つに分割すると,分割されたそれぞれの
線分と閉領域について関係を再定義できる.
L1
L
R
分解
T(R,L)
∂0L
∂1L
L°
∂R
Φ
Φ
¬Φ
R°
Φ
¬Φ
¬Φ
R-
¬Φ
Φ
¬Φ
L2
R
T = T1 ● T2
∂ 1 L1 = ∂ 0 L2
T1
∂0L1 ∂1L1 L1°
∂R
Φ ¬Φ Φ
Φ
Φ
R° Φ
R- ¬Φ
Φ
¬Φ
T2
∂0L2 ∂1L2 L2°
∂R ¬ Φ Φ
Φ
R° Φ ¬ Φ ¬ Φ
R- Φ
Φ
Φ
7つの基本的な関係
• いかなる閉領域 R と有向線分 L の関係も,
線分の分割を使えば,必ず次の7つの関係
の組み合わせで記述できる.
E1
E5
E2
E6
E3
E7
E4
複数の領域との関係
• 各領域 R1, .., Rn と,分割された各線分 L1,
…, Lm との関係記述の列として表す.
R1
R2
R3
L
R1
R2
R1から出発し,R2 を通過して
R3 に到着する移動軌跡 L
R3
L を各 R の境界上および
各境界の中心部分で分割
複数の領域との関係
• 各領域 R1, .., Rn と,分割された各線分 L1,
…, Lm との関係記述の列として表す.
R1
R2
R3
分割した各 Li について,
各 Rj との関係を記述し
それらを列挙する.
T(R1,R2,R3,L) = [E6●E2, E1●E5●E6●E2, E1●E2]
いかなる関係も分割により E1..E7 の組み合わせで記述できる.
Path
• 問い合わせに最も頻繁に使われる関係は,
領域 R1, .., Rn までを順番に通る関係.
R1
R2
L
R1
R2
これを Epath と記述することにする.
T(R1, R2, L) = Epath
R3
領域が増えた場合でも・・・
L
R1
R2
L1
R3
L2
T(R1, R2, R3, L) =
[T(R1, R2, L1), T(R2, R3, L2)] =
[Epath, Epath ]
Path を用いた関係記述例
T(大岡山, 正門, 東工大, 本館, 東工大, L ) = [Epath, Epath, Epath, Epath]
正門
大岡山駅エリア
大岡山駅エリア
正門
東工大エリア
本館
本館
東工大エリア
Path 検索
• データベースに含まれる移動軌跡の中から,
条件を満たす「部分」だけを取り出す.
R1
R2
R3
T(R1, R2, R3, L) = [Epath,Epath]
Path 検索のためのインデックス
1
2
3
4
1
2
3
4
I
II
III
IV
V
I
II
III
IV
V
1) 空間を適当な大きさの
グリッドに仕切っておく.
2) 入力された移動軌跡データが
通るグリッドの順序を記録しておく.
インデックスとして
使用する.
1,IV
2,IV
3,IV
3,III
3,II
2,II
3,III
4,III
インデックスを使った検索(1)
1
2
I
II
III
IV
V
3
4
R1 R2
3) 与えられたクエリ中にある
領域が含まれるグリッドを
特定する.
1
2
I
II
III
IV
V
3
4
R1 R2
4) 3,III を通る各移動軌跡データについて,
リンクをたどり,4,III に直に達するデータ
だけを見つける.
1,IV
2,IV
3,IV
3,III
3,II
2,II
3,III
4,III
例: T(R1, R2, L) = [Epath ] の場合
3,III
と
4,III
インデックスを使った検索(2)
1
2
3
4
I
II
III
IV
V
条件を満たすものだけが答えとして
取り出される.
注) 答の軌跡は,オリジナルのデータの
一部分(条件を満たす部分)が返される.
3) 最後に各 R について,実際
に条件を満たしているかどう
かを調べる.
条件: T(R1, R2, L) = [Epath ]
`
R
Rが複数のグリッドにまたがる
場合は,またがるグリッド全て
についてリンクをたどって調べる.
検索実験
[移動軌跡データ]
点1000個 x 1000 本
シミュレーションにて作成
平均長は 50km 程度
20000
18000
リンク不使用(領域数3)
16000
リンク不使用(領域数2)
Time (ms)
14000
12000
10000
8000
リンク使用(領域数3)
[グリッド] 1辺5km で20x20
リンク使用(領域数2)
[ハードウェアなど:]
Windows2000 / PenIII800MHz
6000
4000
R1
2000
0
Distance = 2
R2
20
18
16
14
12
10
8
Distance between each region
6
4
2
距離が近いほど効果が大
まとめ
• 移動軌跡データ(有向線分)と閉領域と
の関係を記述する方法を提案した.
• 指定された Path を探すためのインデック
ス作成方法を提案した.
• 今後の予定
– 表現力の拡大,実データへの適用
– Path 以外の関係にも適用できる
インデックスの開発
移動軌跡データに対する
類似度検索手法
日本電信電話株式会社
NTT コミュニケーション科学基礎研究所
柳沢 豊,赤埴 淳一,佐藤 哲司
形状の類似性による
アプローチ(1)
• 地図などの外部図形データを用いず,各
移動軌跡データを分類する.
スーパー内の顧客の動き
・ 顧客に共通する動きは?
・ 似た動きをする顧客間の
特徴は?
・ 自分と同じような動きを
する他の客は?
出口
入口
形状の類似性による
アプローチ(2)
• 地図などの外部図形データを用いず,各
移動軌跡データを分類する.
– モーションキャプチャデータの解析
– 都市デザインのための動線分析
2次元空間上での
移動軌跡データに拡張
• 2つの移動軌跡データ間の距離を元に類
似度を定義できる.
– 時系列データの類似度の定義[Keogh01]を拡張
v = (x, y) とする.
L
Y
v1
D (vi, v’i) = ( xi  x'i )  ( yi  y 'i )
2
L’
v’1
2
n
D ( L,L’ ) =
2
D
(
v
,
v
'
)
 i i
i 1
総当りで距離を計算する必要がある.
v7
v’7
X
計算量大
従来の空間インデックス
• 2つの図形間の「最短距離」を探すことに
重点が置かれている[chon02他].
– 最小被覆図形(MBR)などを利用する方法.
MBR を利用して木を作っておく.
従来の空間インデックス
• 2つの図形間の「最短距離」を探すことに
重点が置かれている[chon02他].
– 最小被覆図形(MBR)などを利用する方法.
P
点Pの近傍εを含む
MBRを再帰的に探す.
点Pの近傍εを含むMBRには点Pから距離εにある線分が
必ず含まれる.(近傍検索の高速化が可能)
従来の空間インデックス
• 2つの図形間の「最短距離」を探すことに
重点が置かれている[chon02他].
– 最小被覆図形(MBR)などを利用する方法.
P
形状の類似度については考慮されていない.
本研究でのアプローチ
• 形状情報を近似的な数値を使って表し,こ
れに対してインデックスを付与する.
– 近似値として重心座標を使用する.
– 空間インデックス(R-Treeなど)と組み合わせる.
v1
Y
L
Y
v’1
重心間の距離を
2つの線分の類似度の
近似値として使用
L’
v7
v’7
それぞれの
重心を計算
X
X
重心を用いる理由
• 時系列データ間の形状比較を高速化する手法の
応用(PAA: Piecewise Aggregate Approximate)
[Keogh01].
– 時系列データN個ずつの平均値(重心)間の距離は,元データ間
の距離と等しいか小さくなる.
w
連続する N 個のデータの
平均値(重心)
C1
C0
t
重心を用いる理由
• 重心間の距離は,オリジナルデータ間の距離
(類似度)の下限値として使える.
– 比較するデータの個数を減らす方法として使える.
D( C0, C1)
w
≦
D( C0, C1)
D( C0, C1)
D( C0, C1)
C1
C0
t
t7 t
2次元データへの適用(1)
• PAA (重心)と MBR を使ったインデックスを
組み合わせることで,効率を高める.
– いくつのデータの重心を取るかは予め決めておく.
Y
v8
L
N=4 の場合
Y
L
v5 から v8 までの重心
v1
v1 から v4 までの重心
X
2次元データへの適用(3)
• 各重心に対し,MBRを利用して木を作成する.
– 形状情報を含む空間インデックスができる.
Y
インデックス
A
L
A
C
B
B
X
C
検索方法
• ある移動軌跡データ QL と類似度が ε 以下の移
動軌跡データを検索する場合.
– L の長さが N の場合.
1) L の重心を求める.
N=4の場合
Y
Y
4つの値の平均値を求め,
プロットする.
QL
VQ
X
X
検索方法
• 木を使って,重心間の距離がε以下になるような
点を探す.
– その後,元データ同士を比較して実際に距離がε以下
であるかどうかを調べる.
Y
インデックス
A
A
これらが該当した!
C
B
VQ
B
X
VQから半径εの円
C
実験結果
N=Length の移動軌跡に最も近い軌跡を探すときの所要時間比較
インデックスを使用した場合
インデックスを使用しない場合
20000
20000
18000
18000
16000
16000
14000
14000
12000
Time
10000
(msec)
8000
12000
Time
10000
(msec)
8000
6000
6000
4000
Points
2000
32000
0
4
8000
8
16
Length
32
64
128
256
4000
Points
2000
32000
0
4
8000
8
16
2000
Length
32
64
128
256
2000
比較する移動軌跡の長さが増すと,
本手法の効果がより高くなることが分かった.
まとめ
• 移動軌跡データの形状の特徴値として重心
を用いる方法について述べた.
– 「似ている」形状の移動軌跡を効率よく探せる
ようになった.
• 今後の予定
– 線分の拡大,縮小,回転などが生じた場合にも
対応できる類似度の計算方法の検討
– 実データへの適用
関連研究
• Topological Invariants for Lines [Clementini98]
– 複数の有向線分間の関係の記述方法を提案
• A Spatiotemporal Query Processor Based
on Simplicial Representation [Horinokuchi98]
– 軌跡に対する点ベースの近傍検索方式を提案
• Query Processing for Moving Objects with
Space-Time Grid Storage Model [Chon02]
– 点ベースの近傍検索のための,グリッドを
使ったインデックスを提案
ダウンロード

移動軌跡データ - NTTコミュニケーション科学基礎研究所