論文――――――――――――――――――――――――――――――――――――

ＡｄａｐｔｉｖｅＷａｒｐｉｎｇ

Ｔｉｍｅ

Adaptive Time Warping

大桃 諭♥
古瀬 一隆♦陳 漢雄♦
大保 信夫♠DBSJ Letters Vol.2, No.2

に対してデータマイニングを行うには，時系列データの類似度を計算することが必要となる．
現在，ユークリッド距離が類似度として最もよく使用されている．しかし，ユークリッド距離には時間軸における小さな歪みにも影響を受けやすいという欠点がある．そして，この欠点を解決する技法に，タイムワーピング（Time Warping:TW）がある．TWでは，一方の時系列の1つの点と他方の時系列の連続する複数の点を対応させることによって，時間軸に伸縮性を持たせて歪みの影響を抑えることができる（図1）．

Satoshi OOMOMO Hanxiong CHEN
Kazutaka FURUSE Nobuo OHBO
図 1
大規模な時系列データベースに対する高速な類似検索が重要な課題となっている．これまでにユークリッド距離に基づく類似検索技法が多く提案されているが，最近の研究によって，タイムワーピングによって得られた距離が時系列データの類似検索において有効であることが実証されてきた．しかし，タイムワーピングの計算時間は非常に長く，しかも距離公理の三角不等式が成り立たないため，伝統的な索引技法の適用は困難である．この問題を解決するために，時系列を固定長に区切って圧縮する手法が提案されているが，本論文では，時系列を可変長に区切って圧縮する手法を提案する．
そして，本論文で提案する手法が有効であることを実験によって実証する．
Recently, time series produced and treated in many
fields, and fast similarity search in large time series
databases becomes important. For this subject, similarity
search techniques based on Euclidean distance arestraightforward. However, recent studies have shown thattime warping distance is more robust distance insimilarity search for time series. Difficulty is that time
warping
distance
iscomputationallyexpensive.
Traditional indexing techniques are powerless because it
violates the triangle inequality. To overcome this problem,compression is considered to be effective and sometechniques which divide time series into fix length forcompressing have been proposed. In this paper we
propose an adaptive compressing technique. Prefer to fix
length division, our approach divides a time series
according to its characters hence obtains higher effectwhile keeping lower information lost in compression. The
effectiveness has been confirmed in out experimentalresults.

1. 序論

Fig.1

ユークリッド距離とタイムワーピング距離

Euclidean distance and Time Warping distance

これまでの研究によってTWの有効性は実証されているが，計算時間が非常に長いという欠点がある．そこで，計算時間を短くするための様々な手法が提案されている．その中の1つに，時系列を圧縮する手法がある．そして，圧縮する手法の1つに，時系列を固定長に区切って圧縮するPiecewise
Dynamic Time Warping（PDTW）という手法がある．
PDTWを行うことによって，正確性の低下を抑えつつ高速化できることが実証されているが，全ての時系列を固定長で区切って圧縮するよりも，時系列の変動の度合に応じて可変長で区切って圧縮した方が，圧縮によって生じる誤差を抑えつつ高速化できると考えられる．そこで，本論文では，時系列を変動の度合に応じて可変長に区切って圧縮するAdaptiveTime Warping（ATW）の手法を提案する．

2. タイムワーピングと固定長圧縮
2.1

タイムワーピング

この章では，タイムワーピング（TW）のアルゴリズムを簡単に述べる[1]．
長さn,mの2つの時系列X=x1,…,xi,…,xn，Y=y1,…,yj,…,ymに対して，まずは，以下の式で定義される2つの点xi,yj間の距離d(xi,yj)を(i,j)要素の値とするn×m行列を作成する．

d ( xi , y j ) = (xi − y j )2(1)

次に，ワーピングパスW=w1,w2,…,wk,…,wKを求める．ワーピングパスは，以下の3つの条件を満たす行列の要素の順列で表現される．ワーピングパスの例を図2に示す。
•[境界条件] w1=(1,1),wK=(n,m)とする．
•[連続性] wk=(a,b),wk‑1=(a',b')とすると，a‑a'≦1かつb‑b'≦1となる．
•[単調性] wk=(a,b),wk‑1=(a',b')とすると，a‑a'≧0
かつb‑b'≧0となる．

近年，時系列データは科学，医療，経済，工学などの様々な分野で扱われるようになり，それぞれの分野でデータマイニングが行われるようになっている．そして，時系列データ♥

学生会員 筑波大学大学院システム情報工学研究科
oomomo@dblab.is.tsukuba.ac.jp♦
正会員 筑波大学電子・情報工学系 {chx,furuse}@dblab.is.tsukuba.ac.jp♠
筑波大学電子・情報工学系 ohbo@dblab.is.tsukuba.ac.jp

1

図 2
Fig.2

ワーピングパスの例

An example of warping path

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2

上記の条件を満たすワーピングパスの中からワーピングコストが最小のパスを見つけて，距離を以下の式から求める．
KTW ( X , Y ) = min  ∑k =1 wk  K(3)

コストが最小のパスを求めるには以下の再帰式を利用する．

γ (i − 1, j − 1)

γ (i, j ) = d ( xi , y j ) + min γ (i − 1, j ) γ (i, j − 1) 



(4)

この再帰式を利用すると，式(3)は以下のように表される．

TW ( X , Y ) = γ (n, m) K(5)

図 4
Fig.4

nN
ix i = ∑ Nj = n (i −1) +1 x jNn(6)Variable length compression of time series

計算時間が O(n)で時系列 X=x1,…,xn を X=x1,…,xN に可変長圧縮を行うアルゴリズムを以下に示す．このアルゴリズムに現れる τは閾値であり，これについては後で説明する．
1.
2.

2.2 固定長圧縮を利用したタイムワーピング
この章では，時系列を固定長に区切って圧縮した後にタイムワーピングを適用する手法（PDTW）の概要を述べる[2]．
まずは，長さがnの時系列X=x1,…,xnを，長さNに圧縮する．
圧縮後の時系列を，X=x1,…,xNとすると，Xのi番目の点xiの値は以下のように定義される．

時系列の可変長圧縮

3.

s=1, N=1
find minimum e(s≦e<n) such thatmax {x s , L , x e } − min {x s , L , x e } ≤ τ
max {x s , L , x e + 1 } − min {x s , L , x e + 1 } > τ
if e dose not exist, go to 5.
calculate frame value xN.v and length xN.l.
x N .v = ∑ i = s x ie(e − s + 1 )x N .l = e − s + 1
4.
5.

s=e+1, N=N+1, and go to 2.
calculate last frame value xN.v and length xN.l.
x N .v = ∑ i = s x in

実際に時系列を圧縮した様子を図3に示す．

(n − s + 1 )x N .l = n − s + 1

図 3
Fig.3

時系列の固定長圧縮

Fixed length compression of time series

圧縮の程度を指定するパラメータとして，以下のように定義される圧縮率cを用いる．

c=n N

このアルゴリズムに従って， τ=4 として時系列をフレーム分けする様子を図 5 に示す．点 A から点 B までの部分時系列の最大値と最小値の差は 3 であり，τ以下の値となっているが，点 B の次の点である点 C まで進むと差は 6 になり，閾値より大きくなる．よって，点 A から点 B までが 1 つのフレームとなり，点 C が次のフレームの開始点になる．これを時系列の最後まで繰り返すと，フレーム分けは終了する．

(7)

時系列を圧縮した後は，TWをそのまま適用する．

3. 可変長圧縮を利用したタイムワーピング
第2.2章で述べたPDTWは，時系列を固定長に区切って圧縮しているが，変動の度合に応じて可変長に区切って圧縮した方が，圧縮による誤差を小さくできると考えられる．そこで，時系列を可変長に区切って圧縮する方法を第3.1章で，圧縮後にTWを適用する方法を第3.2章で述べる．

3.1

時系列の可変長圧縮まず初めに，可変長圧縮の流れを示す．
1. 時系列の区切り箇所を決定して複数の部分時系列に分ける．この部分時系列のことをフレームと呼ぶ．
2. 1 つのフレームを 1 つの点に圧縮することによって時系列全体を圧縮する．フレームの値は，そのフレーム内の点の値の平均値とする．
可変長圧縮を行う上で重要なことは，短い計算時間で，圧縮によって生じる誤差を一定以下に抑えつつ，フレームの数をなるべく少なくすることである．圧縮による誤差が小さい
ほど，TW を適用して得られる距離が圧縮前の距離に近似し，フレームの数が少ないほど，TW を適用したときの計算時間が短くなる．時系列を可変長圧縮した例を図 4 に示す．

2

図 5Fig.5

時系列のフレーム分け

Division of time series into frames

次に，閾値 τ の決定方法について説明する．まずは，圧縮の程度をユーザが直接指定できるパラメータとして，許容振幅率 ρというものを定義する．この ρ から，閾値 τ は以下の式で決定される．

τ = ρ ⋅ (max{x1 ,L , x n } − min{x1 , L, x n })(8)

これによって，時系列の取り得る値の範囲に関係なく，0 から 1 の値で圧縮の程度を指定できるようになる．

3.2

可変長圧縮された時系列に対する TW の適用

時系列を可変長圧縮した後は，TW を適用して距離を計算することになる．しかし，フレームの長さが一定でないために，そのまま TW を適用することはできない．そこで，フレームの長さを考慮に入れて TW を適用する方法を述べる．
長 さ N,M の 2 つ の 圧 縮 時 系 列 X=x1,…,xi,…,xN ，
Y=y1,…,yj,…,yM に対して，まずは，第 2.1 章で述べた方法
で，コストが最小となるワーピングパスを求める．次に，こ日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2のワーピングパスから距離を求めるのだが，その方法について述べる前にワーピングパスについて詳しく考えてみる．
第 2.1 章で述べた方法でワーピングパスを求めると，図 6の P1 に示すような 1 対 1 の関係と，P2 や P3 に示すような 1 対 多 の関係は存在するが，P4 に示すような 多対 多 の関係は存在しない．この証明に関しては省略する．

図 6

ＡＴＷにおける時系列の対応関係

Fig.6

Relations of time series in ATW

図 8Fig.8

そして，可変長圧縮された時系列におけるワーピングパスでは， 1 対 多 の関係をさらに 2 つのパターンに分けることができる．図 6 の P2 のような 1 の方のフレームの長さが 多 の方のフレームの長さの和よりも短いパターンと，P3 のような 1 の方が 多 の方の和よりも長いパターンである．可変長圧縮された時系列におけるワーピングパスは
P1, P2, P3 の 3 つのパターンで構成されているので，図 7 に示すようにワーピングパスを g1,…,gn にグループ分けして，パターン別のグループの値 gh.v と大きさ gh.l を求める．

図 7

ワーピングパスのグループ分け

Fig.7•Grouping of warping path

[パターン P1] グループ gh における関係が{xi}と{yj}の 1 対 1 であるとすると，{g h .v = d ( x i , y j ) ⋅ max x i .l , y j .l{g h .l = max x i .l , y j .l
•}}

(9)
(10)

[パターン P2] グループ gh における関係が{xi}と{yj,…,yk}の 1 対 多 であり，フレームの長さが x i .l ≤ ∑ k y .l であるとすると，
s= js(g h .v = ∑s = j d ( x i , y s ) ⋅ y s .lk)k

パターン毎の計算式から得られた n 個のグループ g1,…,gnの値と大きさから，ATW 距離を以下のように定義する．

∑ATW ( X , Y ) =g h .v =∑s= jg h .l = x i .lh =1g h .v∑

nh =1g h .l(15)

この章では，以下の 4 種類の手法の比較実験を行った結果について述べる．
•[Euclidean] ユークリッド距離•[TW] 圧縮を行わずに TW を適用•[PDTW] 固定長で圧縮してから TW を適用•[ATW] 可変長で圧縮してから TW を適用
実験には，合成データセットと実データセットを使用した．
合成データセットには，論文[2]で使用されている CBF データセットを用いた．CBF データセットには，Cylinder，Bell，Funnel の 3 種類のクラスが存在する（図 9）．実データセッ
ト に は ， Keogh,E.&Folias,T.(2002).The UCR Time Series
Data Mining Archive (http://www.cs.ucr.edu/ eamonn/TSDMA/index.html)の時系列を使用した．これらの時系列の中から，異なる特徴を持つ 7 種類の時系列をクラスとして選択した．この 7 種類の時系列を平均値が 0，最小値と最大値の差が 1 となるように正規化した後，一定の大きさに分割して，それらを集めてデータセットとした．このデータセットに含まれる 7 種類のクラスのデータを図 10 に示す．

(12)

図 9

ＣＢＦデータFig.9

CBF data

図 10

実データs∑ (d ( x , y ) ⋅ y .l ) (13)y .lkx i .lkn4. 実験結果

[パターン P3] グループ gh における関係が{xi}と{yj,…,yk}の 1 対 多 であり，フレームの長さが x i .l > ∑ k y .l であるとすると，
s= jss= jiss(14)

これらの式は，圧縮前の時系列に対して TW を適用すると図 8のようになるという考えから得られたものである．

3

Application of TW to original time series(11)g h .l = ∑s = j y s .l•

圧縮前の時系列に対するＴＷの適用

Fig.10

Examples of real data

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――
この 2 つのデータセットを用いた分類実験の内容は以下の通りである．まず，それぞれのクラスからランダムに 1 つデータを選んで基準データとする．次に，残りの全てのデータを最も類似度の高い基準データのクラスに分類する．分類が終わったら，全てのデータの中で正しく分類されたデータの割合と要した時間を求める．これを繰り返して平均の結果を求める．
このように実験を行った結果を表 1，2 と図 11，12 に示す．
図 11，12 のグラフは，PDTW と ATW に関してパラメータを変えて得られた結果を，横軸を実行時間，縦軸を正解率として線で結んだものである．このグラフから，今回提案した手法の ATW が，PDTW よりも優れた性能を持っているということができる．
parameter
EuclideanTW
PDTW

2480.1
0.2
0.4

ATWtime(ms)3.4
1086.3
270.1
67.8
18.2
366.9
106.3
8.5

correct(%)
64.97
83.30
77.28
74.56
68.14
80.26
75.95
80.54

表 1

ＣＢＦデータセットを使用した実験の結果

Table 1Result of experiments with CBF dataset
parameter

Euclidean
TWPDTW

2480.1
0.20.4ATW

表 2time(ms)70100020
26090
6140
1600
8320
3810
1740

correct(%)
26.19
80.95
79.05
66.19
59.05
82.86
81.90
67.62

実データセットを使用した実験の結果

Table 2

Result of experiments with real dataset

DBSJ Letters Vol.2, No.2

図 12Fig.12

実データセットを用いた実験結果

Result of experiments using real dataset

5. 結論
本研究では，時系列の類似度を定義する上でユークリッド距離よりも優れているタイムワーピング（TW）に対して，可変長圧縮の手法を用いることによって，欠点であった計算の遅さを改善することを試みた．実験によって，今回提案した手法（ATW）は，すでに提案されている固定長圧縮の手法（PDTW）よりも優れた性能を持っていることが実証された．
今後の課題としては，パラメータと実行時間と正解率の関係について考察して，適切なパラメータの自動設定を行う手法の提案ができれば良いと考えている．この他にも，今回提案した手法を応用して，時系列の類似検索においてフィルタリングを行う手法についても考案している．

[文献］[1] Joseph B. Kruskall, and Mark Liberman, ``The
Symmetric Time-Warping Problem: From Continuous toDiscrete,''TimeWarps,
StringEdits,andMacromolecules: The Theory and Practice of Sequence
Comparison, pp.125--161, Addison-Wesley, 1983.
[2] Keogh,E. and Pazzani,M. ``Scaling up Dynamic Time
Warping for Datamining Applications,'' Proc. of the 6th
ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, pp.285-289, Boston, MA,USA, August.2000

大桃 諭

Satoshi OOMOMO

2003 年筑波大学情報学類卒業．現在，同大大学院博士課程システム情報工学研究科在学中．データベースシステムに関する研究に従事．日本データベース学会学生会員．

陳 漢雄

Hanxiong CHEN

1993 年筑波大学大学院博士課程工学研究科了．現在，同大電子・情報工学系講師．データベースシステムに関する研究に従事．工博．日本データベース学会正会員．

古瀬 一隆
図 11Fig.11

ＣＢＦデータセットを用いた実験結果

Result of experiments using CBF dataset

Kazutaka FURUSE

1993 年筑波大学大学院博士課程工学研究科了．現在，同大電子・情報工学系講師．データベースシステムに関する研究に従事．工博．日本データベース学会正会員．

大保 信夫

Nobuo OHBO

1968 年東京大学理学部卒．1970 年同大大学院修士課程了．
同年同大理学部助手．1980 年筑波大学電子・情報工学系講師．
1995 年同大電子・情報工学系教授．現在に至る．データベー
スシステムに関する研究に従事．理博．

4日本データベース学会 Letters Vol.2, No.2