DEIM Forum 2016 G3-1

動的属性付き軌跡データの類似検索
大橋

英明†

清水

敏之††

吉川 正俊††† 京都大学大学院情報学研究科 〒 606 - 8501 京都府京都市左京区吉田本町†† 京都大学大学院情報学研究科 〒 606 - 8501 京都府京都市左京区吉田本町
E-mail: †ohashi@db.soc.i.kyoto-u.ac.jp, ††{tshimizu,yoshikawa}@i.kyoto-u.ac.jp
あらまし

近年，センシング技術の発達等によって膨大な移動軌跡データが収集されており，軌跡データに対する研究が数多く行われている．その中で，軌跡間の類似を求める手法は軌跡データのクラスタリングや頻出パターン抽出などの基盤手法となっている．しかし，単に観測点の座標をもとに類似を求めるだけでは，有用な結果を得ることができない場合がある．例えば，サッカー選手の動きを軌跡データとして捉え，ある選手の動きと類似した動きをする
選手を検索するような状況を想定する．検索結果を選手分析等に利用する場合，座標のみではなく，選手の移動速度
やボールとの位置関係など，動的に変化する属性値を考慮して類似を求める必要があると考えられる．そこで我々は，オブジェクトの動的な属性値を付与した軌跡データ（動的属性付き軌跡データ）に対して，柔軟な類似検索を行うための手法の枠組みと，高速化のためのアルゴリズムを提案し，その有効性を検討する．
キーワード

軌跡，類似検索1. は じ め に置関係」などが挙げられる．
内的属性を扱った研究 [2], [9] は以前から数多く行われてきた

近年，センシング技術の発達により，大量の移動軌跡データ

が，外的属性を扱った研究は，複数のデータを横断利用するこが収集されている．収集された軌跡データの例として，歩行とが重要視されてきた近年，注目されつつある [14]．なお，外者の移動データ [15]，ハリケーンのトラッキングデータ [8]，ス

的属性はデータ取得の観点から二種類に分類できると考えら

ポーツのデータ [5], [12] 等があり，それぞれ経路の推薦，傾向れる．一つ目は「軌跡と同時に記録され，観測点と紐づけられの分析，選手の行動分析等に活用され得る．軌跡データの増加

た属性」である．例えば，ハリケーンのトラッキングデータにに伴い，分析を実現するためのクラスタリング [8] や外れ値探

おける気圧や，歩行者の移動軌跡データにおける心拍数など

索 [7] などの手法が数多く提案されてきた．我々はこのようなが例にあたる．二つ目は「軌跡を他のデータと結びつけること

様々な分析手法の基盤となる軌跡の類似検索手法に焦点を当によって得られる属性」である．例えば，タクシーの移動軌跡

てる．

データにおける走行路の制限速度情報や，スポーツ選手の軌跡センサーで収集された移動軌跡データに対する類似検索手法

データにおけるボールとの位置関係などが例にあたる．前者はとして，移動軌跡データを位置情報に基づく二次元の時系列

タクシーの移動軌跡データと道路地図データを，後者は選手のデータとして捉え，軌跡間の類似関係を求めるような手法が考移動軌跡データとボールの位置データを結びつけることによっえられる．しかし，位置情報のみに基づく類似検索では有用なて取得できる．上記の二種類の属性は，属性値を取得する過程

結果が得られない場合がある．例えば，あるサッカー選手の動は異なるが，軌跡固有の情報から導出できないという事実を共きと類似した動きをする選手を検索するような状況を考える．

通して持つため，本研究では同等のものとして扱う．

この場合，単に座標のみではなく，選手の移動速度やボールと本研究では，内的属性，外的属性を考慮した拡張観測点間のの位置関係など，動的に変化する属性値を考慮して類似を求め距離を定義し，DTW(動的時間伸縮法) [1] を用いて，動的属性

なければ，選手分析に用いることができるような有用な結果はを考慮した類似度の算出を行う．軌跡データの中でも，スポー得られないと考えられる．

ツデータのようにオブジェクトごとの挙動の差が激しい軌跡

本研究は，軌跡の動的属性を考慮した類似軌跡検索手法の枠

データの類似を求める手法として，DTW の他に LCSS [11],組みを提案する．軌跡の動的属性とは時間経過に合わせて変化

EDR [3] などが提案されてきた．しかし，本研究では詳細な距する属性（座標を除く）のことを指す．動的属性の中には，軌離の差を考慮して軌跡の距離を定義することを考えており，カ跡固有の情報から導出できるものと軌跡以外の情報と軌跡デー

ウントベースの距離である LCSS や EDR ではなく，DTW をタの組み合わせから導出される属性が存在する．本研究では，用いることが適切であると考えた．

前者を内的属性，後者を外的属性と表現する．内的属性の例とまた，本研究の手法に特化した高速化のためのアルゴリズム

して，隣接する二点の座標のみから大まかに算出できる「進行を提案した．このアルゴリズムの有効性を示すため，ハリケー

方向」などが挙げられる．外的属性の例として，サッカー選手

ンの実データと人工的に作成したデータを対象に実験を行った．

の移動軌跡データを想定すると，ボールの位置情報と選手の移その結果，アルゴリズムを用いなかった場合と比べて，3〜17

動軌跡データの組み合わせから導出できる「選手とボールの位倍の速度向上が見れらた．

本論文の構成を以下に示す．第 2 節では，軌跡に関する関連研究の紹介を行う．第 3 節では，本研究の問題設定の詳細な説

3. 問 題 設 定

明を行い，第 4 節では，検索を高速化するためのアルゴリズム

本研究は，動的属性付き軌跡集合が与えられた際に，その中を提案する．第 5 節では，提案手法とそのアルゴリズムの有効から問合せとして一つの軌跡を選択し，その軌跡と最も類似し性を検討するために行った実験について述べる．第 6 節では，た軌跡を出力するような問題を扱う．なお，軌跡間の類似の基

本稿のまとめを述べる．

準は利用者の意図によって異なると考えられる．例えば，サッ

2. 関 連 研 究
本節では，内的属性を扱った既存研究，外的属性を扱った既存研究，軌跡の距離を扱った既存研究を紹介する．

カーの軌跡データに対して，ある利用者が過去の試合のデータを用いて選手分析をする状況を想定する．この時，ある選手の動きに対して，ドリブルの動きが類似した他選手の動きを得た
いというニーズや，ポジションの取り方が類似した他選手の動2. 1 内的属性を扱った研究

きを得たいというニーズが想定される．前者の場合は，選手のPelekis らの研究 [9] は軌跡の時空間情報，速さの情報，進

進行方向や速度に重きをおくべきだと考えられ，後者の場合

行方向の情報を考慮した類似検索手法を提案している．また，は，他選手やボールとの位置関係に重きをおくべきだと考えら

Buchin らの研究 [2] は軌跡を特徴付ける基準を用いて，軌跡をれる．このように，利用者の意図によって類似の基準は変化す

分割する枠組みを提案している．基準として，location, head-

る．よって本研究では，様々なニーズに対応できるように，軌ing, speed, velocity, curvature, sinuosity, curviness と呼ばれ跡の入力に加えて，各動的属性に対する重みの入力も利用者にる独自の指標を提案しており，これらの指標は全て軌跡固有の委ねることを想定している．

情報のみから算出される．以上二つの研究は内的属性のみを

以下，本研究で取り扱う問題について詳細な定式化を行う．

扱っている研究である．

3. 1 動的属性付き軌跡

2. 2 外的属性を扱った研究

ある軌跡の識別子を i (i = 1, 2, . . . , n)，軌跡の観測点の数

Zheng らの研究 [13] は，軌跡データと地図データを結びつを n, 軌跡の中で j 番目に観測された点の座標を pi (j) (j =けることによって，各観測点にラベルを付与した軌跡 (activity

1, 2, . . . , n) とする．軌跡は時系列に並べられた観測点のリスト

trajectory) を生成し，これに対する検索手法を提案している．

で表現されるため，識別子 i を持つ軌跡 pi は以下のように定義

本田らの研究 [16] は位置情報を伴う車両走行センサデータからできる．

車両走行の特徴を抽出し，要約・表現する手法を提案している．
以上二つの研究は外的属性のみを扱っている研究である．

2. 3 軌跡の距離を扱った研究

pi =< pi (1), pi (2), . . . , pi (n) >(1)

ただし本研究では，すべての観測点は等時間間隔で観測され軌跡間の距離を表す指標として，DTW [1], LCSS [11], EDRていると仮定する．続いて，動的属性について具体例を交えて[3] などが挙げられる．DTW はもともと信号解析に使われてい説明する．軌跡の動的属性とは時間経過に合わせて変化する属た技術であったが，Berndt ら [1] によって時系列データマイニ

性（座標を除く）を指す．本研究では，動的属性を内的属性とングに取り入れられた．DTW はマイニングの手法として有用

外的属性に分別して考える．

である一方，コストが非常に高いことで知られており，コスト

内的属性とは，軌跡の情報のみから導出できる属性のことを減らすための研究が数多く行われている [4], [6], [10]．LCSSを表す．Buchin らの研究 [2] では，heading, speed, curvature,

は Vlachos ら [11] によって提案された手法である．最長共通部

sinuosity など多様な属性が独自に定義され，用いられていた．

分列の考え方を取り入れており，DTW よりもノイズに強いと

本研究では，特に「速さ」と「進行方向」を扱う．これら二ついう性質を持つ．EDR は Chen ら [3] によって提案された手法の属性は多様な軌跡において扱われ得る属性であると考えらである．編集距離の考え方を取り入れており，LCSS よりも精れるため，また導出が比較的容易であるため，本研究で取り扱度が高くノイズにも強い手法とされている．ただし，LCSS とうことにした．速さを示す属性値は，観測点が等時間間隔で観EDR は二点間に定義された尺度がある閾値以上の場合に距離測されているという仮定より，隣接する二点間のユークリッド

が 1 増加するような距離関数を定義している．つまり，LCSS

距離を用いて近似できると考える．よって，隣接する二点間のと EDR は DTW と異なり詳細な距離の差を考慮できない．例

ユークリッド距離を速さを示す属性値として扱う．また，進行

えば，軌跡データに対して LCSS や EDR を単純に適用した場

方向を示す属性値も隣接する二点の座標から近似的に求めるこ合，ある二点間のユークリッド距離が閾値よりわずかに大きとができる．本研究では，これらの隣接する二点のうち，観測い場合と非常に大きい場合を同じものとして扱ってしまう．こ

時刻が早い方の観測点に対して内的属性を付与する．

れは，様々な尺度を用いて詳細な距離を測る本研究にとって不外的属性とは，外部の情報と軌跡の組み合わせから導出され適当な性質であるため，本研究では DTW を利用する．また，る属性のことを表す．例えば，ハリケーンの軌跡を考える場合，

Lee らの研究 [8] は，セグメント間の距離を複数の尺度を合成

ハリケーンの中心気圧や最大風速などが外的属性に相当する．

することによって導出している．Lee らは複数の尺度を合成す

また，サッカー選手の軌跡を考える場合，他選手やボールとのる際に線形結合を用いているが，本研究も座標，内的属性，外位置関係などが外的属性に相当する．前者は「軌跡と同時に記的属性という複数の尺度を合成する際に線形結合を用いる．

録され，観測点と紐づけられた属性」であり，属性値を得るた

めの処理を必要としないが，後者は「軌跡を他のデータと結びつけることによって得られる属性」であり，属性値を得るための処理を必要とする．ただし，本研究では外的属性がどのように付与されたかは考慮せず，あらかじめ与えられるものとする．
また，外的属性値も，内的属性値と同じく，各観測点に付与される．
以上を踏まえて，座標，内的属性値，外的属性値の組を拡張観測点と呼ぶことにする．

epi (j) = (pi (j), ivi (j), evi (j))(2)

ivi (j) は内的属性値，evi (j) は外的属性値を表す．動的属性
付き軌跡は時系列に並べられた拡張観測点のリストとして表
図 1: DTW

現可能であり，本研究ではそのリストを拡張軌跡と呼ぶことにする．

epi =< epi (1), epi (2), . . . , epi (n) >(3)

なお，上述の例では，内的属性と外的属性が各々1 種類だけ存在するように定義されているが，複数属性への拡張も容易にの計算はコストが高いため，重みの入力ごとに DTW を逐一計算すると，計算に時間を要すると考えられる．そこで，我々は重みを用いた検索を行う本研究の問題設定に特化した，検索速度向上のためのアルゴリズムを提案する．

4. 2 DTW について行うことができると考えている．

アルゴリズムの説明を行う前に，DTW の概要を述べる．

3. 2 拡張観測点間の距離
本研究は，拡張観測点間の距離を定義し，DTW を用いるこ

長さ k の時系列データ P =< p(1), p(2), . . . , p(k) > と長さとによって，拡張軌跡間の距離を計算する．二つの拡張観測点

l の時系列データ Q =< q(1), q(2) . . . , q(l) > が存在した時，間の距離は以下の式によって求めることができると考えた．

DTW 距離は以下のように定義できる．ただし，i = 1, 2, . . . , k,

EDist(epi (k), epj (l)) = wS · dS + wI · dI + wE · dE

j = 1, 2, . . . , l である．また，p(i) と q(j) 間の距離を D(i, j) で
(4)

dS = DistS (pi (k), pj (l))(5)

dI = DistI (ivi (k), ivj (l))(6)

dE = DistE (evi (k), evj (l))(7)

wS , wI , wE は 重 み を ，DistS は 座 標 に 関 す る 距 離 を 求め る 関 数 ，DistI は 内 的 属 性 に 関 す る 距 離 を 求 め る 関 数 ，表現する．

DT W (P, Q) = f (k, l)f (i, j) = D(i, j) + min f (i − 1, j)f (i, j − 1)
 f (i − 1, j − 1)

f (0, 0) = 0, f (i, 0) = f (0, j) = ∞DistE は外的属性に関する距離を求める関数を表す．また，
wS >= 0, wI >= 0, wE >= 0, wS + wI + wE = 1 とする．重みのるデータ間の距離を定義することができる．図 1 は二つの軌

最適な数値は利用者の意図ごとに異なると考えられる．なお，跡上の観測点を DTW の定義に従い，破線を用いて対応付け定式化の段階では，内的属性と外的属性にそれぞれ一つずつ重た図である．この時，対応付けられた観測点間の距離の総和がみを与えているが，内的属性を複数同時に扱う場合（速さと進DTW 距離となる．本研究では，上式に現れる D(i, j) として

行方向の二種類の属性を同時に扱うなど）や外的属性を複数同

式 (4) を用いることによって，二つの拡張軌跡 epi , epj の距離時に扱う場合（他選手との位置関係とボールとの位置関係の二を導出する．

種類の属性を同時に扱うなど）については，扱われる属性それ
ぞれに対して重みを付与することで対応できると考えている．

4. アルゴリズム
4. 1 目的

本研究は，利用者の意図に沿った柔軟な検索を実現するため，
重みの入力を利用者に委ねることを想定している．しかし，重DTW は動的計画法に基づいた計算手法であり，長さの異な

4. 3 提 案 手 法
基本的な考え方は下界 (lower bound) を利用した検索対象の絞り込みである．座標，内的属性，外的属性に関する DTW 距離を，拡張軌跡間の距離を求めるときに用いた重みを使って線形結合した値を，拡張軌跡の類似検索における下界として用いることができる．まずは，例を参照しながらこの事実が成立することを確認する．

みを利用者入力とすると，重みが与えられるまで拡張観測点

図 2 は 軌 跡 i と 軌 跡 j の 座 標 に 関 す る 距 離 ，内 的 属 性

間の距離 (式 (4)) が一意に定まらないため，過去に収集されたに 関 す る 距 離 ，拡 張 観 測 点 に 関 す る 距 離 の 行 列 と DTW

データ集合を用いて類似検索を行うような状況であっても，事を 実 行 を し た 際 の ワ ー ピ ン グ パ ス を 示 し て い る ．た だ し ，

前に DTW 距離を求めておくことができない．しかし，DTW(wS , wI , wE ) = (0.5, 0.5, 0) として拡張観測点間の距離 (式QN = qN (1), qN (2), . . . , qN (l) 間の DTW 距離を求める時，
ワーピングパスの要素 W PN (m) は (m = 1, 2, . . . , n)，DTWの定義によって対応付けられる二つの観測点の観測番号の組となる．

W PN (m) = (i, j)(8)

ただし，i = 1, 2, . . . , k, j = 1, 2, . . . , l とする．
(a) 座標に関する距離行列(b) 内的属性に関する距離行列

pN (i) と qN (j) 間の距離を DN (i, j) で表現する．以下，ワー
ピングパスを引数にとり，そのワーピングパスを用いて距離行
列から総コストを求める関数を定義する．

W DistN 1 (W PN 2 ) =m=n∑

DN 1 (W PN 2 (m))

(9)

m=1

ただし，N 1, N 2 には ep, p, iv, ev のいずれかが代入される．
(c) 拡張観測点に関する距離行列

図 2: ワーピングパス

W DistN 1 は拡張観測点 (ep)，座標 (p)，内的属性 (iv)，外的属性 (ev) のいずれかに関する距離行列から総コストを求める関数を表す．このとき，W PN 1 は N 1 の距離行列の中で最小となるように選択されたパスであるため，以下の不等式が成立する．

(4)) を求めている．この時，各々のワーピングパスから，座標に関する距離に基づく DTW 距離 (15)，内的属性に関する距離に基づく DTW 距離 (22)，拡張観測点に関する距離に基づ
く DTW 距離 (20) が導出され，20 >= 0.5 · 15 + 0.5 · 22 + 0 であるため，確かに先ほどの事実が成立している．
図 2(a) と図 2(b) に示されたワーピングパスは座標に関する
距離と内的属性に関する距離の総和が最小となるように選択されたパスである．ゆえに，図 2(c) のパスを用いて，図 2(a)と図 2(b) の距離行列から導出される総コスト (17 と 23) は，各々の DTW 距離 (15 と 22) 以上の大きさになる．また，図2(c) のパスを用いた場合の各々の総コスト (17 と 23) を，重みW DistN 1 (W PN 2 ) >= W DistN 1 (W PN 1 )(10)

式 (10) より，以下の不等式が成立する．

W Distp (W Pep ) >= W Distp (W Pp )W Distiv (W Pep ) >= W Distiv (W Piv )W Distev (W Pep ) >= W Distev (W Pev )よって，補題 1 が成立する．
次に定理の証明を行う．

(wS , wI ) = (0.5, 0.5) を用いて合成した値 (20) が拡張観測点間定 理 1. 二 つ の 拡 張 軌 跡 epi , epj と 座 標 ，内 的 属 性 ，外 的の DTW 距離 (20) と一致するのは自明である．よって，拡張属 性 の 各々に 対 応 す る 重 み wS , wI , wE が 与 え ら れ た と き ，観測点間の距離に基づく DTW 距離は座標に関する距離に基づ

DT W (epi , epj ) >= wS · DT W (pi , pj ) + wI · DT W (ivi , ivj ) +く DTW 距離と内的属性に関する距離に基づく DTW 距離を

wE · DT W (evi , evj ) が成立する．

合成した値よりも大きくなる．以下，厳密な証明を行う．まずは次の補題を証明する．

証明. 補題 1 より，次の式が成立する．

補題 1. 拡張観測点に関する距離行列を用いて DTW 距離を求DT W (epi , epj )める際のワーピングパスを W Pep とする．W Pep を用いて，座= W Distep (W Pep )標，内的属性値，外的属性値の距離行列からコストを導出する= wS · W Distp (W Pep ) + wI · W Distiv (W Pep )と，それらのコストは距離行列から導出される DTW 距離よりも大きくなる．
証明. DTW 距離を求める際のワーピングパスを以下のリスト
で表す．

W PN =< W PN (1), W PN (2), . . . , W PN (n) >N には ep, p, iv, ev のいずれかが代入される．W PN は拡+ wE · W Distev (W Pep )>= wS · W Distp (W Pp ) + wI · W Distiv (W Piv )+ wE · W Distev (W Pev )= wS · DT W (pi , pj ) + wI · DT W (ivi , ivj )+ wE · DT W (evi , evj )よって，定理 1 が成立する．

張 観 測 点 (ep)，座 標 (p)，内 的 属 性 (iv)，外 的 属 性 (ev) のい ず れ か に 関 す る 距 離 行 列 を 用 い て DTW 距 離 を 導 出 す

定理 1 を利用したアルゴリズム 1 について述べる．

る 際 の ワ ー ピ ン グ パ ス が 表 さ れ る ．長 さ k の 時 系 列 デ ー

まず前処理として，各々の尺度に関する DTW 距離を計算す

タ PN = pN (1), pN (2), . . . , pN (k) と長さ l の時系列データ

る (PREPROCESS PHASE)．この計算は重みを与えられるよりも前に実行することができる．また，入力軌跡を与えられるの情報を持つ．本実験では，6 時間ごとに記録された値が欠損以前であっても，すべての軌跡の組み合わせに対して DTW 距

していない軌跡データ 450 件を用いる．また，風速と気圧を外離を導出しておくことで前処理を完了できる．次に，前処理で的属性として扱う．

求められた DTW 距離を利用して類似検索を行う (SEARCH

また，上記のハリケーンデータにならって，軌跡の識別子，

PHASE)．重みと DTW 距離から下界 (lb) を算出し，下界が，タイムスタンプ，x 座標，y 座標，二つの外的属性を属性とし以前に算出された中で最も短い距離の値 (distmin ) よりも小けて持つようなデータを生成し，それらを人工の軌跡データとしれば，拡張軌跡間の真の距離 (true dist) を計算し，大きけれた．軌跡は 1000 件で，それぞれの軌跡の長さは範囲 (30:70) かば，その計算手順を省略する．これにより，検索候補を大きくらランダムに決定した．x 座標，y 座標，二つの外的属性は文絞り込むことができる．

献 [10] を参考にして，以下のようなランダムウォークモデルかなお，アルゴリズム 1 では，座標に関する距離，一つの内的属性に関する距離，一つの外的属性に関する距離という合計三つの尺度を扱っているが，内的属性を複数同時に扱う場合や外ら生成した．

v(i) = v(i − 1) + dif (i)的属性を複数同時に扱う場合についても，対応する重みを用意

ただし，軌跡の先頭 (v(0)) の x 座標と y 座標は範囲 (-5:5) かすることによって，同様のアルゴリズムを用いることができる．

らランダムに生成された小数，二つの外的属性は範囲 (-5:5) からランダムに生成された整数を用いている．また，直前のデー

Algorithm 1 FastExtendedTrajectorySimilaritySearch
INPUT: extended trajectory q
INPUT: {c1 , c2 , . . . , cn } ∈ C of candidate extended trajectories
INPUT: wS , wI , wE

タとの差分 (dif (i)) として，x 座標，y 座標は範囲 (-1:1) からランダムに生成された小数，二つの外的属性は範囲 (-5:5) からランダムに生成された整数を用いている．人工データをハリ

OUTPUT: the index of nearest extended trajectory regarding q

ケーンデータの形に合わせるため，x 座標と y 座標が小数，二1: ▷PREPROCESS PHASE

つの外的属性が整数となるように生成した．

2: for i ← 1 to |C| do

5. 1. 2 座標

D.p[i] ← DT W (q.p, ci .p)

式 (1) では一般化のため，座標を pi (j) として表現していた

4:

D.iv[i] ← DT W (q.iv, ci .iv)
D.ev[i] ← DT W (q.ev, ci .ev)

が，ハリケーンおよび人工データはオブジェクトの位置を二次

5:3:

6: end for
7: ▷SEARCH PHASE

元上の座標として表現できるため，pi (j) は (xi (j), yi (j)) と表すことができる．また，本実験では座標に関する距離を二次元

8: distmin = ∞のユークリッド距離とする．よって，座標に関する距離は以下

9: for i ← 1 to |C| doの式で算出した．

10:lb ← lower bound(D[i], W ) ▷ calculate LB from D and W

11:

if lb < distmin then

座標に関する距離√= (xk (l) − xi (j))2 + (yk (l) − yi (j))212:

true dist ← DT W (q.ep, ci .ep)13:

if true dist < distmin then14:

distmin ← true dist

5. 1. 3 内的属性値

15:

index ← i

ハリケーンデータと人工データの両方において，内的属性と

16:
17:

end if

して「速さ (speed)」と「進行方向 (direction)」を用いる．拡

end if

張軌跡上で隣接する二点間の座標の距離を速さの属性値として

18: end for扱う．よって，速さの属性値は以下の式で算出できる．

19: return index

5. 実

(11)

験

5. 1 実験データについて

ivi (j).speed√= (xi (j + 1) − xi (j))2 + (yi (j + 1) − yi (j))2(12)

次に進行方向の属性値について定義する．拡張軌跡上で隣接ハリケーンの実データと人工的に生成したデータを用いて提する二点のうち，観測時刻が早い方の観測点を始点，遅い方の案アルゴリズムの有効性を示す．始めにそれぞれのデータの概観測点を終点と呼ぶ．x 軸と並行かつ始点を端点に持ち，x 軸要を説明し，続けてデータに適合した座標，内的属性値，外的正方向に伸びる半直線と，始点・終点を結ぶ線分がなす角度を

属性値の扱い方と距離を求める関数について議論する．

進行方向の属性値として扱う．進行方向の属性値は以下の式で5. 1. 1 データの概要
ハリケーンの軌跡データとして，Unisys Weather（注 1） の大西洋上のハリケーントラックデータを用いた．このトラックデー
タは軌跡の識別子，タイムスタンプ，緯度，経度，風速，気圧（注 1）：http://weather.unisys.com/hurricane/

算出できる．

ivi (j).direction

(13)



θ






 θ+π
=

θ−π



π


2


 π
−2

(xi (j + 1) > xi (j))

表 1: 実験結果（ハリケーンデータ）(xi (j + 1) < xi (j), yi (j + 1)>=yi (j))Tightness(xi (j + 1) < xi (j), yi (j + 1) < yi (j))(xi (j + 1) = xi (j), yi (j + 1) > yi (j))(xi (j + 1) = xi (j), yi (j + 1) < yi (j))

ただし，

(

)
yi (j + 1) − yi (j)θ = arctanxi (j + 1) − xi (j)ππ(値域は − < arctan(x) < )
2
2

(14)

ところで，式 (3) が 1<
=j <=n の範囲で成立するように記述しLB を用いたPruning
Power 実行時間 (s) 実行時間 (s)

1

0.807

0.884

14.88

1.94

2

0.800

0.951

10.98

0.77

3

0.827

0.960

17.49

1.21

4

0.810

0.924

14.20

1.75

5

0.868

0.960

8.84

0.57

6

0.815

0.860

15.8

3.08

7

0.738

0.833

13.54

2.64

8

0.811

0.958

14.70

0.84

9

0.770

0.902

11.67

1.34

10

0.798

0.951

10.89

0.67

ていたが，速さや進行方向を考慮する時，軌跡終端の観測点の表 2: 実験結果（人工データ）

内的属性値を定義できない．よって，実験を行う際は，終端のTightness

観測点の速さと進行方向として直前の速さと進行方向の値を用

LB を用いたPruning
Power 実行時間 (s) 実行時間 (s)いた．また，隣接する二点が一致している場合も直前の値と同

1

0.699

0.824

68.92

12.42

じ値を用いた．

2

0.704

0.897

75.27

8.02

3

0.790

0.918

64.73

5.58

4

0.655

0.755

72.37

17.38

続いて，内的属性に関する距離を考える．速さに関する距離と進行方向に関する距離は，それぞれの属性値の差で表現でき

5

0.679

0.822

80.59

15.02

るものと考えた．また，速さに関する距離を重視する検索者も

6

0.528

0.630

68.56

24.14

いれば，進行方向に関する距離を重視する検索者もいると考え

7

0.701

0.822

79.60

14.52

られるので，それぞれに重み付けが必要である．

8

0.756

0.930

79.90

6.10

9

0.723

0.887

66.73

7.75

10

0.795

0.887

65.65

7.62

以上より，本研究では内的属性に関する距離を以下の式で扱う．
内的属性に関する距離= winame · |ivi (j).iname − ivk (l).iname|

進行方向，二つの外的属性の計五つの属性に関する距離を扱う．

(15)

ただし，iname は内的属性を表し，winame は内的属性値に掛け合わせる重みを表す．

た五つの重みをランダムに組み合わせたデータ 10 件を入力として用いる．なお，重みの総和は 1 となるように生成した．提案したアルゴリズムが有効であることを示すため，文献 [6] を

5. 1. 4 外的属性値
まず，ハリケーンの外的属性について説明する．本実験では外的属性として，ハリケーンの気圧と風速を用いる．これらのデータは「軌跡と同時に記録され，観測点と紐づけられた属性」
であり，特殊な前処理を必要としない．どちらの属性の距離も属性値の差で表すことができると考えた．また，内的属性に関する距離と同じく，検索者によって重視する属性は異なるため，重み付けが必要である．人工データの外的属性もハリケーン
データの外的属性の形に合わせて生成したため，同様に扱う．
外的属性に関する距離を考える．内的属性と同じく，各属性の距離はそれぞれの属性値の差で表現でき，また，重視する属
性は利用者によって異なる．
以上より，外的属性に関する距離は以下の式で定義できる．

参考に以下の三つの指標を用いて評価を行った．
（ 1 ） 下界の大きさ (T ightness)（ 2 ） 枝刈りされた軌跡の数 (P runingP ower)（ 3 ） 類似検索の実行速度
ハリケーンデータを用いた実験結果を表 1 に，人工データを用いた実験結果を表 2 に示した．ただし，下界と DTW 距離を算出する過程で発生する計算機由来の誤差によって，下界の値
が DTW 距離よりも大きくなるという事態を避けるため，本実験では下界を本来の値よりも小さな値に，DTW 距離を本来の値よりも大きな値に修正している．

Intel Core i7 3.60GHz，16GB メ モ リ の PC を 用 い て ，Ubuntu 14.04.3 上で，Python3.4.3 を用いて提案手法を実装した．また，事前に算出した DTW 距離を格納するために，

postgres9.3.10 を利用した．

外的属性に関する距離= wename · |evi (j).ename − evk (l).ename|

また，一つの軌跡の識別子と五つの属性に関する距離に対応し(16)

ただし，ename は外的属性を表し，wename は外的属性値に掛け合わせる重みを表す．

5. 2. 1 下界の大きさ
下界は元の値に近ければ近いほど有効に働く．よって，下界の値を本来の DTW 距離の値で割った値 (T ightness) は評価
指標として有用である．

5. 2 性 能 評 価
本実験では、観測点間に定義される距離として，座標，速さ，T ightness =下界の値
本来の DT W 距離(17)

10 件の入力に対して，入力軌跡とそれ以外の軌跡の組み合えられる．例えば，サッカーの選手の軌跡を入力とした際に，わせについて T ightness を求め，平均を取った値を表 1 と表

試合全体での動きが漠然と類似した選手よりも，ある一部の動2 に示した．ハリケーンデータは 0.738〜0.868，人工データは

きが強く類似した選手の方が分析対象として有用であると考え0.528〜0.795 となっている．ハリケーンデータの T ightness がられる．よって，軌跡の一部分を扱えるように拡張することは人工データの T ightness と比べて大きい理由は，ハリケーン

有用であると考えられる．

データに座標や外的属性の変化の傾向が類似しているものが多

最後に「前処理の高速化」について述べる．提案したアルゴく含まれるからだと考えられる．下界は線形和によって算出でリズムの中で，あらかじめ各属性に対する DTW 距離を求める

きるため，高速に計算することができる．それにもかかわらず，という前処理を行っている．入力軌跡の長さを k, 検索対象の下界の値は元の DTW 距離の約 7,8 割の値となっており，下界軌跡の長さの平均を l, 属性の数を m，軌跡の数を n とした時，が有効に働いていると考えられる．

前処理の計算量は Θ(klmn2 ) となり，軌跡の数が増えた際，計

5. 2. 2 枝刈りされた軌跡の数

算量が爆発的に増加してしまう．実利用に耐えうるようにする

下界によって枝刈りされた軌跡が多ければ多いほど，実行速ためには，前処理計算の効率化を検討しなければならないと考度は速くなる．よって，枝刈りされた軌跡の数を元の軌跡の数えられる．

で割った値 (P runingP ower) は評価指標として有用である．

P runingP ower =枝刈りされた軌跡の数
元の軌跡の数(18)

10 件の入力に対する PruningPower を表 1 と表 2 に示した．
ハリケーンデータは全軌跡データの約 83%〜96%を，人工デー
タは約 63%〜約 93%を枝刈りしており，提案アルゴリズムが効
果的に作用していると考えられる．また，T ightness が大きいものほど P runingP ower が大きくなるという傾向が見られた．

5. 2. 3 類似検索の実行速度
最後に，実行速度について述べる．10 件の入力に対する通常の実行速度と下界を用いた場合の実行速度を表 1 と表 2 に示す．ハリケーンデータは約 5.1 倍〜17 倍，人工データは約 2.8
倍〜13 倍の速度向上が見られた．ハリケーンデータにおいて枝刈りされた軌跡の数が人工データと比べて多かったため，ハリケーンデータにおける実行速度が人工データにおける実行速度と比べて大きく向上していると考えられる．

6. お わ り に
我々は動的属性を考慮した軌跡の類似検索のための枠組みを提案した．この枠組みによって，軌跡が持つ様々な属性（内的属性，外的属性）を利用した柔軟な検索が可能となった．加えて、検索速度を向上させるためのアルゴリズムを示し，実験によってそのアルゴリズムの有効性を示した．
今後の拡張の方向性として，大きく三つの方向性が考えられる．
（ 1 ） 距離関数の改良（ 2 ） 部分軌跡を考慮した検索（ 3 ） 前処理の高速化
まずは「距離関数の改良」について述べる．本研究では，拡張観測点間の距離を線形和の形で表現したが，データによってはその形が不適当な場合もあると考えられる．また，実世界での利用を想定した時に，重みの入力が利用者にとって不明瞭でコストの高い作業となり得るため，これを解決するためにも改良を行う必要がある．
続けて「部分軌跡を考慮した検索」について説明する．本研
究では，軌跡全体を類似検索の対象としていたが，部分軌跡を扱わなければ有用な結果が得られない場合がしばしばあると考文

献[1] Donald J Berndt and James Cliﬀord. Using dynamic time
warping to find patterns in time series. In KDD workshop,
Vol. 10, pp. 359–370, 1994.
[2] Maike Buchin, Anne Driemel, Marc van Kreveld, and Vera
Sacristán. An algorithmic framework for segmenting trajectories based on spatio-temporal criteria. In Proceedingsof the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 202–211,
2010.
[3] Lei Chen, M Tamer Özsu, and Vincent Oria. Robust andfast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 491–502, 2005.
[4] Xudong Gong, Yan Xiong, Wenchao Huang, Lei Chen, Qiwei Lu, and Yiqing Hu. Fast similarity search of multidimensional time series via segment rotation. In Proceedings of the Database Systems for Advanced Applications,pp. 108–124, 2015.
[5] Joachim Gudmundsson and Thomas Wolle. Towards automated football analysis: Algorithms and data structures. In
Proceedings of the 10th Australasian conference on Mathematics and Computers in Sport, 2010.
[6] Eamonn Keogh and Chotirat Ann Ratanamahatana. Exact
indexing of dynamic time warping. Knowledge and information systems, Vol. 7, No. 3, pp. 358–386, 2005.
[7] Jae-Gil Lee, Jiawei Han, and Xiaolei Li. Trajectory outlier
detection: A partition-and-detect framework. In Proceedings of the 24th International Conference on Data Engineering, pp. 140–149, 2008.
[8] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pp. 593–604, 2007.
[9] Nikos Pelekis, Ioannis Kopanakis, Gerasimos Marketos,
Irene Ntoutsi, Gennady Andrienko, and Yannis Theodoridis. Similarity search in trajectory databases. In Proceedings of the 14th International Symposium on Temporal Representation and Reasoning, pp. 129–140, 2007.
[10] Yasushi Sakurai, Masatoshi Yoshikawa, and Christos
Faloutsos. Ftw: fast similarity search under the time warping distance. In Proceedings of the 24th ACM SIGMODSIGACT-SIGART symposium on Principles of databasesystems, pp. 326–337, 2005.
[11] Michail Vlachos, George Kollios, and Dimitrios Gunopulos. Discovering similar multidimensional trajectories. In
Proceedings of the 18th International Conference on Data
Engineering, pp. 673–684, 2002.

[12] Chikashi Yajima, Yoshihiro Nakanishi, and Katsumi
Tanaka. Querying video data by spatio-temporal relationships of moving object traces. In Visual and Multimedia
Information Management, pp. 357–371. Springer, 2002.
[13] Kai Zheng, Shuo Shang, Nicholas Jing Yuan, and Yi Yang.
Towards eﬃcient search for activity trajectories. In Proceedings of the 29th International Conference on Data Engineering, pp. 230–241, 2013.
[14] Yu Zheng.
Trajectory data mining:
an overview.
ACM Transactions on Intelligent Systems and Technology(TIST), Vol. 6, No. 3, p. 29, 2015.
[15] Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. Mining interesting locations and travel sequences from gps trajectories. In Proceedings of the 18th international conference on World wide web, pp. 791–800, 2009.
[16] 本田崇人, 松原靖子, 根山亮, 櫻井保志. 車両走行センサデータ
からの自動パターン検出. 第 8 回 Web とデータベースに関するフォーラム論文集, 2015.