DEIM Forum 2017 G6-4

多変量拡張軌跡の時空間ペナルティを考慮した類似検索
大橋

英明†

清水

敏之††

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

近年，移動軌跡に関する研究分野において，単純な軌跡を用いた研究でなく，軌跡と外部情報を組み合わせた研究が注目を集めている．例えば，利用者の行動情報と軌跡を組み合わせることで新たな知識発見を試みた研究
や，気象情報，交通量，人の軌跡などを組み合わせることで空気の質の推定を行った研究がある．本研究は，外部情報として数値データの時系列を考え，観測時刻ごとに軌跡上の座標と時系列上の数値データを同時に得られる状況を想定し，軌跡と時系列集合を組み合わせたデータ (多変量拡張軌跡と呼ぶ) を扱う．多変量拡張軌跡の例として，歩行者の軌跡と心拍数の時系列，ハリケーンの軌跡と気圧・風速の時系列などが挙げられる．本研究は動的時間伸縮法(DTW) に基づいた距離尺度を利用した多変量拡張軌跡の類似検索に焦点を当て，ペナルティ関数によって軌跡対のワーピングパスを重視可能な距離尺度を提案する．また，ペナルティ関数を設定する際に利用者の入力が困難と考えられるパラメータの指標も合わせて提案する．
キーワード

軌跡，多変量時系列，類似検索

1. は じ め に昇することが報告されている [11]．さらに，Jeong らは Sakoe-

Chiba band を一般化したペナルティを組み込んだ WDTW [9]近年，センシング技術の発達により，膨大な移動軌跡データを提案している．本研究は，Jeong らが提案したペナルティをが収集されている．収集されたデータの例として，歩行者の移時間ペナルティと呼び，多変量拡張軌跡の距離尺度に応用する

動データ [22]，ハリケーンのトラッキングデータ [10]，スポー

ことを考えた．

ツのデータ [7] 等が挙げられる．また，これらを生の軌跡 (rawDTW を多変量時系列に適用した簡潔かつ代表的な手法とtrajectory) のまま解析するのではなく，データの横断利用がして，Shokoohi-Yekta らが提案した DTWI , DTWD がある

注目される昨今，外部情報と軌跡を組み合わせて解析すること(I は独立 (Independent) を表し，D は依存 (Dependent) を表で，新たな知見を得ようとする取り組みも盛んである [20]．例す) [13]．DTWI は各時系列対の DTW 距離の総和を多変量時

えば，位置情報を利用したアプリケーションから得られる利用

系列間の距離とする手法であり，各時系列対ワーピングパスは者の行動情報 (外部情報) と利用者の軌跡 (軌跡) を組み合わせ

異なったものとなり得る．DTWD は各時系列対の二点間の距たデータから頻出パターンを抽出した研究 [18] や，気象情報，

離の総和を用いて DTW 距離を求める手法であり，各時系列対交通量等 (外部情報) と人々の動き (軌跡) を組み合わせ，空気のワーピングパスは共通している．また，DTWI において，各の質を推定した研究 [21] がある．前者の研究は外部情報として時系列対の DTW 距離の総和を取る際に重み付き線形和を用いラベルの系列データを扱い，新たな知識発見を試みている．後る拡張や，DTWD において，各時系列対上の二点間の距離の者の研究は外部情報として空気の質に関わる多様なデータを扱総和を取る際に重み付き線形和を用いる拡張が考えられる．

い，推定に有効な特徴を設計している．本研究では，外部情報

本研究では，DTW に基づいて多変量拡張軌跡間の距離を算として数値データの時系列を考え，観測時刻ごとに軌跡上の座出する際，軌跡対および各時系列対のワーピングパスが大きく

標と時系列上の数値データを同時に得られる状況を想定する．

異なっていることは不適切であると考えた．例えば，ハリケー

この想定を満たす例として，歩行者の軌跡と心拍数の時系列，

ンの軌跡と気圧の時系列から構成される多変量拡張軌跡を想定

ハリケーンの軌跡と気圧・風速の時系列，サッカー選手の軌跡

し，多変量拡張軌跡間の距離を算出する場合，気圧はハリケーと選手とボールの位置関係を表す時系列等が挙げられる．本研ンの軌跡上の各地点で観測される情報であるため，軌跡対の究は軌跡と時系列集合を組み合わせた上記のようなデータを多ワーピングパスと気圧の時系列対のワーピングパスが大きく

変量拡張軌跡と呼ぶ．我々は，動的時間伸縮法 (DTW) [3] を用異なっているのは不自然である．この考えに基づくと，単純にいた距離尺度を利用した多変量拡張軌跡の類似検索に焦点を当DTWI を用いて多変量拡張軌跡間の距離を算出することは不適てる．多変量拡張軌跡の類似検索はクラスタリングや外れ値検切であると考えられる．また，DTWD では，ワーピングパス

索などの応用手法の基盤になると考えられる．

が共通しているが，共通のワーピングパスと軌跡対のワーピン

DTW は時系列の距離算出手法として優れた性能を持つ [15]．

グパスが大きく異なる場合がある．そこで，本研究は，軌跡対

また，時系列の伸縮のずれに制限をかける Sakoe-Chiba bandの二点間の距離が近いほどペナルティが小さくなるようなペナ[12] を用いた拡張によって，DTW を用いた 1-近傍法の精度が上ルティ関数を用いて DTWI を拡張した DTWP を提案する．

DTWP は，軌跡対の DTW 距離と，ペナルティが付与され2. 2 時系列の距離尺度に関する研究

た各時系列対の DTW 距離を求め，それらの総和を多変量拡張

本研究は時系列の伸縮を考慮した距離算出手法の一つ，

軌跡間の距離とする．DTWP を算出するには DTWD よりも複DTW(動的時間伸縮法) を用いる．伸縮を考慮した手法は他

雑な計算が必要となるが，ペナルティ関数を適切に設定すれば，にも存在し，LCSS [14], EDR [4] などが挙げられる．これらのペナルティが付与された各時系列対のワーピングパスは軌跡対中で DTW は最も単純でありながら，優れた性能を持つことがのワーピングパスと似たものになり，各々のワーピングパスの示されている [15]．また近年，ラベル付き時系列データセット

ばらつきが抑えられる．DTWP では，時間ペナルティの考えの整備が進んだことにより [5]，単変量時系列データ分類する方を用いて，ペナルティ関数を実現した．本研究では，軌跡対・手法が数多く提案されている [1]．時系列の分類問題において，各時系列対の DTW 距離の和を取る際に，重み付き線形和を用

DTW を用いた 1-近傍法は古典的であるが有効な手法とされてい，さらに時間ペナルティを付与するような，DTWP を拡張

おり，ベースラインとしてしばしば利用されている．本研究はした手法を DTWWTP と呼び，多変量拡張軌跡の距離尺度とし

DTW よりも 1-近傍法の精度が良いとされる WDTW [9] を参て用いることを考えた．DTWP やその拡張である DTWWTP考にする．WDTW は DTW に対して時系列の伸縮のずれのペでは，ペナルティ関数を適切に設定するために，いくつかのパ

ナルティを付与した手法である (詳細は後述する)．本研究はこラメータを利用者が設定する必要があるが，対象データに対すのペナルティを一部拡張したものを時間ペナルティと呼ぶ．本

る洞察が不足している利用者にとってはこの設定が困難だと考研究は時間ペナルティを応用することで，DTWP における軌えられる．そこで，DTWP のペナルティ関数において特に入跡対のワーピングパスを重視するためのペナルティ関数を実現力が困難なパラメータの入力支援を目的として，パラメータのする．

指標も合わせて提案した．
本研究の貢献は以下の通りである．

•

多変量拡張軌跡に対して軌跡のワーピングパスを重視可能
な距離尺度を提案した•

2. 3 多変量時系列の類似を扱った研究
既存研究として，主成分分析を用いて抽出された特徴量を利用した研究 [16] や，マハラノビス距離と DTW を組み合わせた指標を多変量時系列間の距離とした研究 [17] などがある．多変量時系列は単変量時系列よりも複雑な構造を持つため，他にもペナルティ関数を設定する際に入力が困難なパラメータの多様な類似指標が提案されてきた [2], [8], [13]．本研究は軌跡対指標を提案したのワーピングパスに焦点を当てた距離尺度を提案した点で，多変量時系列の類似を扱った既存研究と異なっている．

本論文の構成を以下に示す．第 2 節では，関連研究の紹介を行う．第 3 節では，本研究の提案に必要な定義を行う．第 4

3. 各 種 定 義

節では，DTWP , DTWWTP を定式化し，第 5 節では，ペナル

本節では多変量拡張軌跡を定式化し，DTW および DTW

ティ関数を設定する際に入力が困難なパラメータの指標を提案に対する時間ペナルティに関して述べる．さらに，DTWI とする．第 6 節では，提案した距離尺度の有効性を検討するため

DTWD の定義を述べる．

に行った実験について述べる．第 7 節では，本稿のまとめを述3. 1 多変量拡張軌跡の定式化

べる．

我々は軌跡と時系列集合を組み合わせたデータを多変量拡張

2. 関 連 研 究軌跡と表現する．本研究では軌跡を以下のように表現する．

pi = ⟨pi (1), pi (2), . . . , pi (n)⟩2. 1 外部情報と軌跡を組み合わせた研究
ラベルの系列 (利用者の行動情報や地理情報等) と軌跡を組

i は軌跡の識別子を，n は軌跡の観測点の数を，pi (j) (j =み合わせたデータに対して，効率的な類似検索手法を提案した

1, 2, . . . , n) は軌跡上の j 番目の観測点の座標を表している．た研究 [19] や頻出パターンを抽出する研究 [18] 等がある．本研究だし，本研究ではすべての観測点は等時間間隔で観測されていはこれらの研究と異なり，数値データの時系列と軌跡を組み合ると仮定する．また，軌跡 pi と m 個の時系列から構成される

わせたデータを扱う．上記の研究が扱うラベルは比較の結果と時系列集合を組み合わせた多変量拡張軌跡を考える際，時系列

して二通りのパターン (一致するか，一致しないか) しか得ら集合中の l 番目の時系列を以下のように表現する．

れないが，本研究が扱う数値データは比較 (差の絶対値を用い

vli = ⟨vli (1), vli (2), . . . , vli (n)⟩た比較など) の結果として多様な値を取り得る．また，ラベルの系列に限らず様々なデータと軌跡を用いて特定のタスクに取り組んだ研究として，気象情報，交通量，人の軌跡などを利用し，空気の質を推定した研究 [21] や，地理情報やタクシーの軌跡から不動産の鑑定を行った研究 [6] がある．本研究はこれらの研究と異なり，(教師付きの) 特定のタスクに取り組むのではなく，多変量拡張軌跡の性質に基づいた汎用的な距離尺度を定式化する．

vli (j) (j = 1, 2, . . . , n) は l 番目の時系列中の j 番目の値を表している．以上より本研究は多変量拡張軌跡を以下のように表現
する．



pi





pi (1)

 i   i
 v1   v1 (1) 
et =  .  = ..
 ..  
.

 
i
i
vm (1)vmipi (2)...

pi (n)

v1i (2)
..
.

...
..
.

v1i (n)
..
.

i
vm
(2)

...

i
vm
(n)









3

0

4

3

3

2

1

(7)

3

0

4

3

3

2

1

(6)

2

1

3

2

2

1

2

(6)

2

1

3

2

2

1

2

(5)

3

0

4

3

3

2

1

(5)

3

0

4

3

3

2

1

(4)

1

2

2

1

1

0

3

(4)

1

2

2

1

1

0

3

(3)

1

2

2

1

1

0

3

(3)

1

2

2

1

1

0

3

(2)

1

4

0

1

1

2

5

(2)

1

4

0

1

1

2

5

(1)

1

2

2

1

1

0

3

(1)

1

2

2

1

1

0

3

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

3.0

g=0
g=0.05g=0.25g=3

2.5w(q, r)

(7)

2.0

1.5

1.0

図 1: DTW 概要．

0

20

40

60

d

80

100

図 2: Modified Logistic Weight Function.

ただし，m は時系列集合の大きさを表している．

3. 2 DTW

3.0

DTW について述べる．二つの時系列 a = ⟨a(1), a(2), . . . , a(na )⟩2.5と b = ⟨b(1), b(2), . . . , b(nb )⟩ を想定する．このとき，DTW は

2.0

1.5

以下のように定義できる．

1.0
20

DT W (a, b) = f (na , nb )f (q, r) = D(q, r) + min15 f (q − 1, r)



20

10
15
10

5
5

f (q, r − 1)

0




f (q − 1, r − 1)0図 3: 時間ペナルティ．

f (0, 0) = 0, f (q, 0) = f (r, 0) = ∞の場合ほぼ線形になり，g = 0.25 の場合 c を境に急激に値(q = 1, 2, . . . , na ; r = 1, 2, . . . , nb )が変わり，g = 3 の場合 c を境に値がほぼ二つに分かれる．

ただし，D(q, r) は a(q) と b(r) 間の距離を表している．図 1
は DTW の概要を表している．時系列対から導出される距離行列に対して，コストの総和がなるべく小さくなるよう赤色のパス (ワーピングパス) が選択され，パス上のコストの総和

wmax = 1, c = 50 のとき，g = 0, g = 0.05, g = 0.25, g = 3 のModified Logistic Weight Function は図 2 のようになる．
我々は式 2 に柔軟性を与えるため，下限を調整できるよう，
以下のように拡張した．

が DTW 距離となる．ただし，図 1 では各時刻における観測wt (q, r) = wtmin +値間の距離 (D(q, r)) を差の絶対値で算出している．このとき，DTW 距離は 1 + 2 + 0 + 1 + 1 + 2 + 1 + 1 = 9 となる．
3. 3 時間ペナルティ
Jeong ら [9] は DTW に時間の伸縮のずれに関するペナルティwtband
1 + exp(−gt (dt − ct ))(3)

dt は比較される点の観測時刻の差 |q − r| である．wtmin は取り得る値の下限を決定するパラメータ，wtband は取り得る値の幅を決定するパラメータ，gt は関数の形を決定するパラメータ，を導入した WDTW を提案している．本研究はこのペナルティct は関数の中心を決定するパラメータである．また，すべてのを時間ペナルティと呼ぶ．Jeong らは WDTW を定義する際，パラメータは 0 以上の値を取る．

先に述べた DTW の定義中の D(q, r) の代わりに，以下に示す

D′ (q, r) を用いている．

wtmin = 1, wtband = 2, gt = 3, ct = 10 のとき，長さ 20 の二つの多変量拡張軌跡間の時間ペナルティは図 3 のように表されD′ (q, r) = w(q, r) · D(q, r)(1)

る．時間ペナルティは単変量時系列に対して提案されたものであるが，次に述べる DTWI や DTWD に適用することも可能

w(q, r) は距離行列中の各要素に付与されるペナルティであり，である

Jeong らはロジスティック関数を拡張した以下の関数 (Modified

3. 4 DTWI と DTWD

Logistic Weight Function) を w(q, r) として用いている．

Shokoohi-Yekta らは DTW を用いて多変量時系列データのw(q, r) =wmax
1 + exp(−g(d − c))(2)

類似を求める手法を DTWI と DTWD の二つに分類している [13]．この二つの手法は DTW を用いた多変量時系列間の距d は比較される点の観測時刻の差 |q − r| である．また，wmax

離算出手法として，簡潔かつ代表的な手法と考えられる．以下，は取り得る値の上限を決定するパラメータ，g は関数の形を決DTWI と DTWD の概要を例を用いて簡単に説明する．

定するパラメータ，c は関数の中心を決定するパラメータであ

まず，DTWI について述べる．DTWI は各時系列対の DTWる．また，すべてのパラメータは 0 以上の値を取る．Jeong ら

距離の総和を多変量時系列間の距離とする手法である．DTWIの研究では g = 0(Constant weight), g = 0.05(Linear weight),

を多変量拡張軌跡に適用すると，軌跡対の DTW 距離と各時系

g = 0.25(Sigmoid weight), g = 3(Two distinct weights) の列対の DTW 距離の総和が多変量拡張軌跡間の距離となる (図みが扱われている．g = 0 の場合値が一定になり，g = 0.05

4)．各時系列対のワーピングパスは軌跡対のワーピングパスと

!"#
$%&'

()*
&'+,

!"#
$%

!"#

#$%

#$%
&'

!"#$%

!

$
!"#
$%

!"#

()*
+,'#
$%&'

%

()*-.
!"/#
$%

#$%

-./
01,*
&'+,

!"#

-./23

" ()4*
&'

!

$

#$%

!"#
$%

#$%
&'

#$%
&'

図 6: DTWP .

図 4: DTWI .
量拡張軌跡間の距離とする (図 6)．ペナルティ関数として，軌
!"#
$%&'

!"#

()*-.
!"/#
$%

跡対の二点間の距離が近いほどペナルティが小さくなるような関数を用いるため，DTWP における各時系列のワーピングパ
スは，軌跡対のワーピングパスを考慮したものとなり得る．すなわち，各時系列対のワーピングパスが軌跡のワーピングパス

()*
+,'#
$%&'

と類似したものとなり得る．また，軌跡の影響の大きさは利用者が調整することができ，影響を大きくした場合，DTWP が描く各時系列対の距離行列のワーピングパスは軌跡対のワーピ
図 5: DTWD .

異なった経路を取り得るため，DTWI は多変量拡張軌跡の距離尺度として不適切であると考えられる．
続いて，DTWD について述べる．DTWD は各時系列対の距離行列の総和を取って統合した後に DTW 距離を導出する手法である．DTWD を多変量拡張軌跡に適用すると，軌跡対の距離行列と各時系列対の距離行列を統合した距離行列から導出される DTW 距離が多変量拡張軌跡間の距離となる (図 5)．

ングパスに近づく．影響を小さくした場合，各時系列対の距離行列のワーピングパスは DTWI が描くワーピングパスに近づき，影響を完全に無くした場合，DTWI のワーピングパスと一致する．つまり，DTWP は DTWI を一般化した手法となっている．
本研究は，時間ペナルティを参考にし，以下のような関数を

DTWP におけるペナルティとして用いた．
ws (q, r) = wsmin +wsband
1 + exp(−gs (ds − cs ))(4)

DTWD は統合された距離行列に対して単一のワーピングパス

ds は比較される点間の距離である．本研究では ds としてユーを引くため，DTWI と異なり，軌跡対と各時系列対の間で異クリッド距離 ||pi1 (q) − pi2 (r)|| を用いる．wsmin は取り得るなったワーピングパスが取られることはない．しかし，図 5 の値の下限を決定するパラメータ，wsband は取り得る値の幅を決ように，軌跡対のワーピングパス (図 4 上部) から外れたパス

定するパラメータ，gs は関数の形を決定するパラメータ，cs はを共通のワーピングパスとして持つ可能性がある．

関数の中心を決定するパラメータである．また，すべてのパラ

また，DTWI において，各時系列対の DTW 距離の総和をメータは 0 以上の値を取る．図 7 に示す軌跡対を例に用いて取る際に重み付き線形和を用いる拡張や，DTWD において，各DTWP におけるペナルティの意義を直感的に述べる．ただし，

時系列対上の二点間の距離を取る際に重み付き線形和を用いる

どちらの軌跡も左下から右上の順番で観測されているものとす

拡張が考えられる．

る．このとき，wsmin = 1, wsband = 2, gs = 3, cs = 60 なら

4. DTWP : ペナルティ付き DTWI

ば，DTWP におけるペナルティは図 8 のように表され，二つの軌跡上の点が近いほど対応する要素に付与されるペナルティ

本章は初めに DTWP の定義を述べる．続いて，DTWP には小さくなり，遠いほど大きくなることを読み取れる．DTW

重みと時間ペナルティを付与した DTWWTP の概要を述べる．

はコストの総和が小さくなるようにパスを選択するため (図 1

本研究では DTWWTP を多変量拡張軌跡の距離尺度として用い参照)，ペナルティを各時系列対の距離行列に掛け合わせることる．さらに，DTWP のペナルティにおいて入力が困難なパラで，図 6 のような軌跡対のワーピングパスを重視したワーピン

メータの設定の指標を提案する．

グパスが選択され得る．また，軌跡対のワーピングパスを重視

4. 1 定義する方法として，単に軌跡対のワーピングパスを用いて他の時本研究は軌跡対のワーピングパスを明示的に重視できる

系列のワーピングパスを決める方法も考えられるが，この方法

DTWP を新たに提案する．DTWP は軌跡対の二点間の距離をの場合，時系列対の距離行列中の大きな値のセルを含むワーピ

もとに導出されるペナルティを用いて DTWI を拡張した距離ングパスが選択され得る．そのため，本研究は式 4 のようなペ尺度である．DTWP は，ペナルティを各時系列対の距離行列

ナルティを用いた手法がより頑健であると考えた．

に付与し，軌跡対の距離行列とペナルティが付与された時系列

DTWP は，各時系列対の距離行列に対して式 4 のペナルティ

対の距離行列をもとに DTW 距離を求め，それらの総和を多変を与える．すなわち，式 1 中の w(q, r) として ws (q, r) を用いる．このときの DTW 距離を W DT Ws (vli1 , vli2 ) と表現すると，

140

120

100

(7)

8

7

6

1

5

1

1

(7)

8

7

6

1

5

1

1

(7)

8

7

6

1

5

1

1

(6)

5

4

3

2

2

4

2

(6)

5

4

3

2

2

4

2

(6)

5

4

3

2

2

4

2

(5)

6

5

4

1

3

3

1

(5)

6

5

4

1

3

3

1

(5)

6

5

4

1

3

3

1

(4)

5

4

3

2

2

4

2

(4)

5

4

3

2

2

4

2

(4)

5

4

3

2

2

4

2
3

(3)

4

3

2

3

1

5

3

(3)

4

3

2

3

1

5

3

(3)

4

3

2

3

1

5

(2)

0

1

2

7

3

9

7

(2)

0

1

2

7

3

9

7

(2)

0

1

2

7

3

9

(1)

2

1

0

5

1

7

5

(1)

2

1

0

5

1

7

5

(1)

2

1

0

5

1

7

5

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

7

80

cs = 160

cs = 2cs = 4

図 9: 軌跡対の距離行列と cs の関係．

40

20

0

0

20

40

60

80

100

120

140

DT WW T P (eti1 , eti2 )
図 7: 軌跡対．

= Wp · W DT Wt (pi1 , pi2 ) +

(6)
m
∑

Wvl · W DT Wst (vli1 , vli2 )l=1

ただし，Wp , Wv1 , . . . , Wvm はそれぞれの距離を足し合わせる
3.0

際に用いられる重みである．これらの重みは利用者入力を想定

2.5

している．

2.0

1.5

5. パラメータに対する指標

1.0
20

15

本研究はペナルティ関数が持つパラメータの中で特に設定が

20

10
15

困難な cs に焦点を当て，類似検索において cs を設定するため

10

5
5
0

の指標を提案する．以下，cs の設定が困難な理由を説明する．

0

図 8: DTWP のペナルティ．

cs は DTWP のペナルティ関数の中心を決定する変数であるため，gs が 0 より大きい場合，軌跡対の距離行列の中で cs より

DTWP は以下のように定義される．
DT WP (eti1 , eti2 )大きな要素に対応したペナルティは大きくなり，cs より小さな(5)= DT W (pi1 , pi2 ) +m∑

W DT Ws (vli1 , vli2 )

l=1

要素に対応したペナルティは小さくなる．図 9 は軌跡対の距離行列に対して，cs 以下の値のセルを青く塗りつぶした図である．図 9 に示した軌跡対の距離行列を用いる場合，cs を大部分

DTWP におけるペナルティのパラメータについて補足する．

の軌跡の観測点間の距離よりも小さくすると，すなわち cs = 1

パラメータ gs が 0 のとき (Constant weight)，ペナルティの値にすると，時系列対の距離行列に与えられるペナルティ全体がはすべて等しくなるため，DTWP のワーピングパスは DTWI

大きくなってしまう．一方で，cs を大部分の軌跡の観測点間のと同じワーピングパスを取る (図 4)．すなわち，軌跡が時系距離よりも大きくすると，すなわち cs = 4 にすると，時系列列に与える影響がなくなる．一方，パラメータ gs が 3 のとき

対の距離行列に与えられるペナルティ全体が小さくなってしま(Two distinct weights)，ペナルティの値は cs を境に急激に変う．よって，各時系列対の距離行列のワーピングパスが軌跡対化するため，cs が適切に定められかつペナルティ関数の上限値の距離行列のワーピングパスに近付くようなペナルティを与えが十分に大きければ，各時系列対の距離行列のワーピングパス

たければ (図 6 参照)，cs を適度な大きさにする必要があると考は軌跡のワーピングパスに近づく．すなわち，軌跡が時系列にえられる．しかし，どの cs が適切なのか，対象データに対する与える影響が大きくなる．パラメータ cs はペナルティ関数の知見が不足している状況では判断が難しい．

中心を決定する変数であり，どのような値を入力するかで結果

そこで，本研究は利用者に cs を直接設定させるのではなく，は変化する．5 節では類似検索における cs の指標を提案する．

直感的に意味を捉えやすい指標 kc を設定させ，kc から導出さ

4. 2 DTWWTP

c
れるパラメータ ckmin
を cs の代わりに利用するという枠組みを本研究は，軌跡対・各時系列対の DTW 距離の和を取る際c考えた．ckminを定義するため，以下の条件 (A) を導入する．

に，重み付き線形和を用い，加えて時間ペナルティを付与し，

DTWP を拡張した手法を DTWWTP と呼び，多変量時系列(A) ある軌跡対 (pi1 , pi2 ) の距離行列において，cs 以下のセルのみでワーピングパスを引くことが可能である間の距離尺度として用いる．DTWWTP では軌跡対の距離行列に対して時間ペナルティ(式 3) のみを付与する．すなわち，

1 ,i2
本研究は条件 (A) を満たす最小の cs を ciminと表現する．ま式 1 中の w(q, r) として wt (q, r) を用いる．このときの DTW

ずは，図 9 に示した軌跡対の距離行列を例に用いて説明する．

距離を W DT Wt (p , p ) と表現する．また，各時系列対の

図 9 において，cs = 1 のとき，左下端から青く塗りつぶされた距離行列に対しては時間ペナルティと式 4 のペナルティを掛

セルのみを辿って (右，上，右上のいずれかの方向に進むことけ合わせたペナルティを与える．すなわち，式 1 中の w(q, r)を繰り返して)，右上端まで到達することはできない．すなわ

として ws (q, r) · wt (q, r) を用いる．このときの DTW 距離をち，条件 (A) が満たされない．図 9 の場合，cs = 2 になって

W DT Wst (vli1 , vli2 ) と表現する．以上より，DTWWTP は以下

1 ,i2
初めて条件 (A) が満たされる．よって，cimin= 2 となる．長のように定義される．

さ n1 の軌跡 pi1 = ⟨pi1 (1), pi1 (2), . . . , pi1 (ni1 )⟩ と長さ n2 のi1

i2

軌跡 pi2 = ⟨pi2 (1), pi2 (2), . . . , pi2 (ni2 )⟩ に対して，以下に示す

て用いる．

1 ,i2
式から ciminを求めることができる．ただし，ここでは pi1 (q)i2Det (eti1 (q), eti2 (r))

と p (r) 間の距離を D(q, r) で表現する．
1 ,i2
cimin
= h(ni1 , ni2 )(h(q, r) = max D(q, r), min= Wp · Dp (pi1 (q), pi2 (r)) + f (q − 1, r)m∑

Wvl · Dvl (vli1 (q), vli2 (r))l=1)

f (q, r − 1)
 f (q − 1, r − 1)

(q = 2, . . . , ni1 ; r = 2, . . . , ni2 )ただし，座標間の距離を Dp (pi1 (q), pi2 (r))，各時系列上の数
値間の距離を Dvl (vli1 (q), vli2 (r))，軌跡と各時系列の重みをWp , Wv1 , . . . , Wvm としている．本研究は DTWWD に時間ペ
ナルティを付与した距離を DTWWTD と表現する．

6. 2 実験データについて

本研究は，入力軌跡と kc 件の候補軌跡間の任意の距離行列がc(A) を満たすような最小の cs を ckminと表現する．本研究は，直感的に意味を捉えやすい指標 kc を利用者入力として，kc かcら導出されるパラメータ ckminを用いる枠組みにより，適切なc値の判断が難しい cs の設定を支援できると考えた．ckmin
を求めるアルゴリズムを次に示す．

本研究はハリケーンのデータ用いて類似検索を行い，空間ペナルティが与える影響に関する考察を行った．ハリケーンの軌跡データとして，Unisys Weather（注 1） の大西洋上のハリケーン
トラックデータを用いた．本実験では，6 時間ごとに記録された値が欠損していない軌跡データ 451 件を用いる．このトラックデータは軌跡の識別子，タイムスタンプ，緯度，経度，風速，

Algorithm 1 Minimum Warping Threshold Search

気圧の情報を持つ．ただし，風速と気圧は非常に相関が高いた

INPUT: kc

め，本実験では緯度，経度から構成される軌跡に対して風速のINPUT:▷ the number of candidates which satisfy (A)query trajectory pq

時系列データのみを付与した多変量拡張軌跡を扱う．

INPUT: candidate trajectories p1 , . . . , pNc
OUTPUT: ckmin

1: for i ← 1 to kc do
2:

P Q.push(cq,imin )3: end for
4: for i ← kc + 1 to N do
5:

if cq,imin < P Q.top then6:

P Q.pop()

7:

P Q.push(cq,i
min )

8:

end if

データの前処理について述べる．本研究は緯度，経度，風速のデータを各々平均 0, 分散 1 となるように正規化した．また，異なる長さの時系列間の DTW 距離よりも，長さが等しくなる
ように補間された時系列間の DTW 距離のほうが正確であるという知見が既存研究で示されている [11] ため，451 件すべての多変量拡張軌跡の長さが 50 となるよう補間した．
続いて，軌跡間の距離と各時系列間の距離について述べる．
すべての距離のスケールを揃えなければ，パラメータの入力意
図と出力結果が食い違う可能性があるため，本研究では座標間

9: end forの距離，時系列間の距離として以下の式を用いた．
√
i1
i2
i1 (q)−y i2 (r))22
Dp (pi1 (q), pi2 (r)) = (x (q)−x (r)) +(y2

10: return P Q.top

アルゴリズム 1 は kc とクエリ軌跡 pq , 候補軌跡 p1 , . . . , pNcを入力とし，ckmin
を出力とする．まずはじめに，クエリ軌跡とkc 個の候補軌跡間の cq,imin を計算し，優先度付きキュー P Q に格納する．続いて，それ以外の候補軌跡についても同様に cq,iminを計算し，もし P Q の中で最も大きな値よりも小さければ，そDv1 (v1i1 (q), v1i2 (r)) = |v1i1 (q) − v1i2 (r)|ただし，xi1 (q), xi2 (r) は正規化された緯度，y i1 (q), y i2 (r) は正規化された経度，v1i1 (q), v1i2 (r) は正規化された風速を表している．厳密なスケールの調整は今後の課題とする．

6. 3 ペナルティについての値を P Q から除外し，代わりに cq,imin を格納する．そして最時間ペナルティ・空間ペナルティの設定に必要なパラメータ

後に，P Q の中で最も大きな値を出力として返す．

は以下の通りである．

6. 実

験

本節では，ハリケーンの実データを用いて，DTWP の有効性を検討する．具体的には，DTWD にを拡張した DTWWTDとの比較を行う．

6. 1 DTWWTD について
DTWD (図 5) は各距離行列中で同じ位置に存在する要素の単純な和を取り，距離行列を統合していたが，他にも重み付き線形和やマハラノビス距離を用いる方法 [17] などが考えられる．本研究は重み付き線形和を用いて距離行列を統合した場合の DTW 距離を DTWWD と表現する．DTWWD は DTW の定義において，以下に示す Det (eti1 (q), eti2 (r)) を D(q, r) とし•

wtmin , wsmin (ペナルティの下限)•

wtband , wsband (ペナルティの幅)•

ct , cs (ペナルティの中心を決定する変数)•

gt , gs (ペナルティの形を決定する変数)
本実験は wtmin = 1, wtband = 2, wsmin = 1, wsband = 2 とする．また，W DT Wt (pi1 , pi2 ) 算出の際に，式 1 中の w(q, r)
として wt (q, r) · wt (q, r) を用い，W DT Wst (v1i1 , v1i2 ) 算出の際
（注 1）：http://weather.unisys.com/hurricane/(a) Wp = 1, Wv1 = 1, DTWWTD(b) Wp = 3, Wv1 = 1, DTWWTD(c) Wp = 1, Wv1 = 1, DTWWTP , gs = 0(d) Wp = 3, Wv1 = 1, DTWWTP , gs = 0(e) Wp = 1, Wv1 = 1, DTWWTP , gs = 3(f) Wp = 3, Wv1 = 1, DTWWTP , gs = 3

図 10: 実験結果．

に，wt (q, r) · ws (q, r) を用いる．これにより，軌跡間の距離といた場合の出力結果である．図 10d は Wp = 3, Wv1 = 1, gs = 0

時系列間の距離に付与されるペナルティの上限はどちらも 9，とし，DTWWTP を用いた場合の出力結果である．ただし，図下限はどちらも 1 となり，ペナルティによって軌跡間の距離と10c と図 10d で用いられた距離尺度 (DTWWTP , gs = 0) は

時系列間の距離のスケールが大きく変わることはないと考えら

DTWI に重み (Wp , Wv1 ) を加えた距離尺度と等価である．図れる．

10e は Wp = 1, Wv1 = 1, gs = 3 とし，DTWWTP を用いた場c
本実験では kc = 50 としたときの ckmin
を cs として用いる．

合の出力結果である．図 10f は Wp = 3, Wv1 = 1, gs = 3 とし，また，二つの多変量拡張軌跡の平均長の 10%の値を ct として

DTWWTP を用いた場合の出力結果である．ただし，各図の上用いる．この値を ct として選んだ理由を以下に述べる．時間ペ段がハリケーンの軌跡を，下段がハリケーンの風速の時系列を，

ナルティは時系列の伸縮のずれに制限を設ける手法の一つであ一番左の列が入力としたハリケーン ANDREW を表している．

る Sakoe-chiba band [12] の拡張と捉えることができる．よっ

図 10a，図 10c，図 10e は重みが全て共通 (Wp = 1, Wv1 = 1)て，Sakoe-chiba band の最適な band 幅がデータセットによっしており，一部の結果は重複しているが，順序は異なっている．

て異なるという事実 [11] と同様に，ct の最適な値はデータセッ

例えば，ハリケーン KATARINA はすべての出力結果に含まれトによって異なると考えられる．しかし実際は，正解ラベルのているが，図 10c では 1 番目，図 10a，図 10e では 4 番目に出存在しないデータセットにおいて ct の最適な値を求めることは現している．KATARINA と ANDREW は出現位置が大幅に異困難である．そこで，既存研究 [11] 中の「10%を超える band

なるが，部分的に類似した軌跡を辿る，また，ANDREW の風幅が有効なデータセットの作成ができなかった」という知見を速の時系列は他のハリケーンと比べて，KATARINA の風速の根拠とし，二つの多変量拡張軌跡の平均長の 10%の値を cs と時系列に類似している．よって，軌跡対と時系列対の DTW 距して用いる．本実験では gt = 3 とし，重み，距離尺度，gs を

離はともに近いが，時系列対ワーピングパスと時系列対のワー変えたときの類似検索の出力結果を考察する．

ピングパスは大きく異なっていると考えられる．以上より，軌

6. 4 実験結果・考察

跡対のワーピングパスと時系列対のワーピングパスの関係を考1992 年にアメリカ合衆国で大きな被害をもたらしたハリケー

慮しない DTWWTP (gs = 0) では 1 番目の出力になったが，軌ン ANDREW を入力とし，重み，距離尺度，gs を変化させた

跡対のワーピングパスと時系列対のワーピングパスが一致する

ときの出力結果を図 10 に示す．図 10a は Wp = 1, Wv1 = 1

DTWWTD や時系列対のワーピングパスが軌跡対のワーピングとし，DTWWTD を用いた場合の出力結果である．図 10b はパスに近づくようなペナルティを付与する DTWWTP (gs = 3)

Wp = 3, Wv1 = 1 とし，DTWWTD を用いた場合の出力結果ででは 4 番目の出力になったと考えられる．図 10b，図 10d，図ある．図 10c は Wp = 1, Wv1 = 1, gs = 0 とし，DTWWTP を用

10f でも同様に重みは全て共通 (Wp = 3, Wv1 = 1) しており，

一部の結果は重複しているが，順序が異なっている．ただし，
図 10a，図 10c，図 10e と比べ，時系列の類似が重視されていないことを見て取れる．

[7]

ところで，DTWWTD では Wp を大きくするほど，統合後の距離行列の各要素の値は，軌跡の距離行列の各要素の値に比例した値を取りうる (図 5 参照)．よって，統合後の距離行列[8]のワーピングパスは軌跡の距離行列のワーピングパスに近づくと考えられる．すなわち，多変量軌跡対のワーピングパスが元の軌跡対のワーピングパスに近づくと考えられる．しかし，

DTWWTD は DTWWTP と異なり，軌跡対のワーピングパスの[9]みを重視する手法ではない．ワーピングパスを重視しようとして Wp を大きくすると，軌跡の類似そのものも重視されてしまう．図 10 において，DTWWTD を用いて軌跡対のワーピング[10]

パスを重視しようとしたときの出力 (図 10b) と，DTWWTP を用いて軌跡対のワーピングパスを重視しようとしたときの出力(図 10e) を比較する．このとき，DTWWTD を用いた出力結果[11]の中に，軌跡は類似しているが風速の値が大きく異なったハリ
ケーン (ISAAC) が含まれていることを確認できる．以上より，[12]

DTWWTD を用いて軌跡対のワーピングパスのみを重視することは困難であると考えられるため，軌跡対のワーピングパスのみを重視したい場合は DTWWTP を用いるのが適当であると考

[13]

えられる．

7. お わ り に[14]

本研究は多変量拡張軌跡に対して，軌跡対のワーピングパスを重視するペナルティ関数を用いた距離尺度を提案した．また，
ペナルティ関数を設定する際に利用者の設定が困難と考えられ[15]

るパラメータに対する指標も合わせて提案した．本稿では，実験において，提案した距離尺度をハリケーンの類似検索に適用した際の実例を示すにとどまったが，今後は提案した距離尺度[16]がどのような状況で有効なのか定量的な評価を行いたい．

文

献[1] Anthony Bagnall, Aaron Bostrom, James Large, and Jason Lines. The great time series classification bake oﬀ: A
review and experimental evaluation of recently proposed algorithms. 2016.
[2] ZoltáN Bankó and JáNos Abonyi. Correlation based dynamic time warping of multivariate time series. Expert Systems with Applications, Vol. 39, No. 17, pp. 12814–12823,
2012.
[3] Donald J Berndt and James Cliﬀord. Using dynamic time
warping to find patterns in time series. In Proc. ACM KDD
workshop, pp. 359–370, 1994.
[4] Lei Chen, M Tamer Özsu, and Vincent Oria. Robust andfast similarity search for moving object trajectories. In Proc.
ACM SIGMOD International Conference on Managementof Data, pp. 491–502, 2005.
[5] Yanping Chen, Eamonn Keogh, Bing Hu, Nurjahan Begum,
Anthony Bagnall, Abdullah Mueen, and Gustavo Batista.
The ucr time series classification archive. www.cs.ucr.edu/
eamonn/time series data/, July 2015.
[6] Yanjie Fu, Hui Xiong, Yong Ge, Zijun Yao, Yu Zheng, andZhi-Hua Zhou. Exploiting geographic dependencies for realestate appraisal: a mutual perspective of ranking and clus-

[17]

[18]

[19]

[20]

[21]

[22]

tering. In Proc. ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, pp. 1047–1056,
2014.
Joachim Gudmundsson and Thomas Wolle. Towards automated football analysis: Algorithms and data structures. In
Proc. Australasian Conference on Mathematics and Computers in Sport, 2010.
Shen-Shyang Ho, Peng Dai, and Frank Rudzicz. Manifold
learning for multivariate variable-length sequences with anapplication to similarity search. IEEE transactions on neural networks and learning systems, Vol. 27, No. 6, pp. 1333–
1344, 2016.
Young-Seon Jeong, Myong K Jeong, and Olufemi A Omitaomu. Weighted dynamic time warping for time series classification. Pattern Recognition, Vol. 44, No. 9, pp. 2231–
2240, 2011.
Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In Proc.
ACM SIGMOD International Conference on Managementof Data, pp. 593–604, 2007.
Chotirat Ann Ratanamahatana and Eamonn Keogh. Everything you know about dynamic time warping is wrong.
In Proc. ACM KDD workshop, 2004.
Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE
Trans. Acoustics, speech, and signal processing, Vol. 26,
No. 1, pp. 43–49, 1978.
Mohammad Shokoohi-Yekta, Bing Hu, Hongxia Jin, Jun
Wang, and Eamonn Keogh. Generalizing dtw to the multidimensional case requires an adaptive approach. Data Mining and Knowledge Discovery, pp. 1–31, 2016.
Michail Vlachos, George Kollios, and Dimitrios Gunopulos.
Discovering similar multidimensional trajectories. In Proc.
IEEE International Conference on Data Engineering, pp.
673–684, 2002.
Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, and Eamonn Keogh. Experimental comparison of representation methods and distancemeasures for time series data. Data Mining and Knowledge
Discovery, Vol. 26, No. 2, pp. 275–309, 2013.
Kiyoung Yang and Cyrus Shahabi. A pca-based similarity measure for multivariate time series. In Proc. the 2nd
ACM international workshop on Multimedia databases, pp.
65–74, 2004.
Wei Yu and Michael Gertz. Constraint-based learning of
distance functions for object trajectories. In Proc. International Conference on Scientific and Statistical Database
Management, pp. 627–645, 2009.
Chao Zhang, Jiawei Han, Lidan Shou, Jiajun Lu, andThomas La Porta. Splitter: Mining fine-grained sequential
patterns in semantic trajectories. PVLDB, Vol. 7, No. 9,
pp. 769–780, 2014.
Kai Zheng, Shuo Shang, Nicholas Jing Yuan, and Yi Yang.
Towards eﬃcient search for activity trajectories. In Proc.
IEEE International Conference on Data Engineering, pp.
230–241, 2013.
Yu Zheng. Trajectory data mining: an overview. ACM
Transactions on Intelligent Systems and Technology, Vol. 6,
No. 3, p. 29, 2015.
Yu Zheng, Furui Liu, and Hsun-Ping Hsieh. U-Air: When
urban air quality inference meets big data. In Proc. ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1436–1444, 2013.
Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. Mining interesting locations and travel sequences from gps trajectories. In Proc. International World Wide Web Conference, pp. 791–800, 2009.