論文

DBSJ Letters Vol.6, No.1

類似部分区間検索のためのタイム
ワーピング距離の下限値計算
A Query Adaptive Lower Bound Calculation for Subsequence Search underTime Warping Distance

1.

はじめに

近年，音声データ，株価データ，気温や磁気などの自然観測データ等，様々な分野において時系列データが大量に蓄積されるようになってきた．ここで時系列データとは，気温など経時変化する値を観測時間順に並べて得られる実数値のシーケンスである．蓄積されたデータを有効に活用するため，時系列データの分類やクラスタリングなどの研究が行なわれているが [1][2]，基本技術の一つとして重要なのが類似検索である．時系列デー

♥

♦

石川 雅弘
陳 漢雄 ♠大保 信夫 †吉川 昂伯
古瀬 一隆 ♣

Masahiro ISHIKAWA
Hanxiong CHEN
Nobuo OHBO

Takanori YOSHIKAWA
Kazutaka FURUSEなどの自然観測データ等，様々な分野で時系列データが大量に蓄積されるようになってきた．蓄積されたデータを活用するための基本技術の一つとして時系列データに対する類似検索の研究が行なわれているが，同程度の長さの時系列データを多数集めたデータベースを検索対象とし，問合わせとして与えられた時系列データに全長が類似したデータを検索するのが一般的である．しかし，例えば過去の株価の動きの中から最近数週間の値動きに類似した期間を検索するような，長大な時系列データから問合せ時系列に類似した部分区間を検索する研究は少ない．
本稿では，タイムワーピング距離に基づいた類似区間検索を効率的に行なうための，問合せに適応した下限距離計算法を提案し，実験によりその有効性を示す．

In recent years, huge amount of time-series datais accumulated in various domains. To utilize them,similarity search techniques are heavily studied.
However, in the most studies, target database consists of large amount of data whose length are almost the same and a query is a time-series data ofalmost the same length. We focus on the case where
the target database is a single very long time-series,
and the length of a query is much shorter than thatof the database. In this paper, we propose a queryadaptive lower-bound calculation for subsequence
search under time-warping distance, and show its
eﬃciency by experimental results.

♦♠♣ある．また，時系列データに対する類似検索の研究では，同程度の長さの時系列データを多数集めたデータベースを検索対象とし，問合せ時系列データと全長が類似したデータを検索するものが一般的であるが [7][5][8]，本稿で提案する手法が想定するのはデータベース時系列が問合せ時系列に比べ大幅に長い場合であり，検索されるのはデータベース時系列中問合せに類似した部分区間である．
本稿では，このような検索を効率的に行うための DTW 距離の下限値計算の手法を示し，実験によりその有効性を示す．

2.

2.1

動的タイムワーピング距離 (DTW 距離)DTW 距離の定義

時系列データには，観測間隔の違いや観測機器の故障によるデータの欠損などにより時間軸上のずれが生じる事があり，距離を求める際にはそれを考慮する必要がある．時間軸上のずれを吸収した距離として広く用いられているのが DTW 距離[3] である．長さ m と n の時系列データ x, y 間の DTW 距離
D(x, y) は下式で与えられる．
89>< D(x2: , y ) >=D(x, y) = D0 (x1 , y1 ) + minD(x , y 2: )>: D(x , y ) >
;
2:
2:(1)

D0 (x, y) = |x − y|(2)

ここで xi: は x の第 i 要素から始まる接尾辞となる部分時系列データであり，xi:j は第 i 要素から始まり第 j 要素で終わる部
分時系列データである．また，D0 (x, y) は引数の差の絶対値の単調増加関数ならば任意であり，例えば |x − y|2 が用いられる事もある．

2.2

DTW 距離の計算方法

yosikawa@dblab.is.tsukuba.ac.jp
正会員

テーブルが空の状態から計算を開始し，全ての要素の値が求め

正会員 つくば国際大学産業情報学科 mi@tius.ac.jp
筑 波 大 学 大 学 院 シ ス テ ム 情 報 工 学 研 究 科
筑波大学大学院システム情報工学研究科

chx@cc.tsukuba.ac.jp
正会員

筑波大学大学院システム情報工学研究科

筑 波 大 学 大 学 院 シ ス テ ム 情 報 工 学 研 究 科

ohbo@cs.tsukuba.ac.jp

1るようになってきたが [4][5][6]，計算コストが高いという問題がDTW 距離は動的計画法を用いて求められる．その考え方
を二つの時系列データ x = x1 , x2 , x3 , x4  = 4, 3, 5, 3 とy = y1 , y2 , y3 , y4 , y5 , y6  = 3, 4, 3, 5, 5, 4 を例に説明する．
まず，二つの時系列データの長さに合わせて 4 × 6 のテーブ
ルを考える (図 1 参照)．行方向はxに，列方向はy に対応しており，最下行最左要素を a1,1 ，最上行最右要素を a6,4 とする．

furuse@cc.tsukuba.ac.jp†ワーピング (DTW: Dynamic Time Warping) 距離が用いられあり，効率的な検索のためには距離計算コストの削減が重要で音声データ，株価などの経済データ，あるいは気温や磁気変動♥

タの類似検索に用いる距離尺度に適したものとして動的タイムられた時点で計算が終了する．始めに a1,1 に D0 (x1 , y1 ) を格納し，a1,2 〜a1,4 には ai,j = a1,j−1 + D0 (x1 , yj ) を，a2,1 〜a6,1 には ai,j = ai−1,1 + D0 (xi , y1 ) を格納する．左，下，左下の三つの接する要素がすでに求められた他の各要素には，下式

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

論文

DBSJ Letters Vol.6, No.1

図4
図1

累積距離テーブル

Fig. 1 Accumulated Distance Table

いないが，その一つが解を与えている事が分かる．常にこの例のように解となるパスが残る保証はないが， 値の小さな要素だに従って求めた値を格納する．

89>>< ai−1,j=ai,j = D0 (xi , yj ) + minai,j−1>>: a;i−1,j−1

1 以下の要素のみを残した差分テーブル

Fig. 4 Diﬀerence Table with Smaller Values (less than two)

けに注目する事で可能なパスの数を削減し， 低コストで距離を(3)求められる可能性がある．
図 5 は，データベースd と問合せq による差分テーブルであり，4 以下の要素にのみ値を記入してある．以下では値の記入さ全ての要素を求めた時，最後に求められた最上最右要素 a6,4 の値が DTW 距離となる．a1,1 から a6.4 までを，右上に向かって辿るパス (ワーピングパス) は多数存在するが，図中網掛けで示したのは a6.4 から逆算して式 (3) 第二項で選択された要素を辿ったパスであり，DTW 距離を与える時のx とy の要素の対応を示している．この時の対応を図 2 に示す．a1,1 から a6,4 まで
図5マークされた要素を結ぶ事で得られる検索グラフ

Fig. 5 Search Graph built from Marked Elements
図2

ワーピングパスが与える要素の対応

Fig. 2 Element Correspondence by the Warping Path

辿るワーピングパスは他にも存在するが， DTW 距離とは，全ての可能なパスのうち (すなわち全ての可能な対応付けのうち)，a6,4 に最小の値を与えるパスから得られる距離のことである．

2.3

差分テーブルと DTW 距離れた要素をマークされた要素と呼ぶ．マークされた二つの要素

ti,j , tk,l 間に以下の条件が成り立つ場合に有向辺 ti,j , tk,l  を張る事で得られるグラフを検索グラフと呼ぶ．

1. i ≤ k かつ j ≤ l (ただし ti,j = tk,l )．
2. i ≤ u かつ j ≤ v かつ u ≤ k かつ v ≤ l なる tu,v が存在しない (ただし ti,j = tu,v かつ tu,v = tk,l )．

ここで差分テーブルと呼ぶテーブルを導入する．差分テーブ

間に非マーク要素を挟む場合，有向辺上の始点から終点に至る

ルとは，累積距離テーブルと同サイズのテーブルであり，そのパスの厳密な距離を求める事はできないが， その下限値は求め(i, j) 要素 ti,j の値は D0 (xi , yj ) である．図 3 に例を示す．解る事ができる．

3.2

有向辺の下限距離t2,1 から t3,3 に至るパスを考える．両要素により形成される矩形区間 (図 5 参照) でマークされているのは t2,1 と t3,,3 のみであり，それぞれの値は 1 と 2 であるため，パスがこの二つの要素を通る以上，最低でも値の合計は 3 である．ここで t2,1 から t3,3 に至るまでに取り得るパスは [t2,1 → t3,1 → t3,2 → t3,3 ]，図3

差分テーブルFig. 3 Diﬀerence Tableを与えるワーピングパスが与えられた時，パス上の要素の値を合計する事で DTW 距離を求める事ができる．図から，解を与えるパスは差分テーブル上では値の小さな要素上を通る傾向にある事が分かる．なぜなら，全ての可能なパスの中で値の合計が最小となるものが解を与えるからである．

3.

3.1

問合せに適応した DTW 距離の下限値
検索グラフ

図 4 は，図 3 の差分テーブルで値が 1 以下の要素のみを残し[t2,1 → t3,2 → t3,3 ]，[t2,1 → t2,2 → t3,3 ]，[t2,1 → t2,2 → t2,3 →t3,3 ] の 4 つである．どのパスでも q2 に対応する要素を必ず一つは通過する必要があり，かつそれだけで t3,3 に到達できる．
従って距離の下限値は 7(= 3 + 4) である．なぜなら，マーク要素の上限値は 4 であるため，非マーク要素の下限値は 4 だからである．このように，閾値以下の要素のみをマークする事でマーク要素間のパスの与える距離の下限値を求める事ができる．
このようにして求めた下限値は，類似区間検索などの際に一定距離を越える区間をフィルタアウトする事で検索効率改善に利用できる．
以下では，一つの有向辺の下限距離の求め方について，矩形の形状ごとに解説する．

たものである．この時 t1,1 と t6,4 を結ぶパスは二つしか残って2

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

論文
3.2.1

DBSJ Letters Vol.6, No.1

3.2.5

正方形の場合多段の場合二つのマーク要素をそれぞれ ta , tb とし，形成される矩形が最後に，有向辺を複数辿った場合の下限距離について説明す

正方形の場合の例を図 6 に示す．ここで要素 ta , tb の値をそれる．図 9 は，既に ta から tb に辿った後に，さらに tc へ辿るとぞれ a, b とする．また，閾値は各 qi 毎に異なる値とし，それぞころを表している．ta → tb 間，tb → tc 間の下限距離はそれぞれを εi で表す．

図 6 正方形の場合の下限距離計算

Fig. 6 Lower Bound (square case)

図9ta と tb を結ぶパスは，少なくとも q2 〜q4 のそれぞれに対応する要素を一つずつ通過する必要があり，かつそれだけで tbに達する事ができる．したがって，この有向辺の距離の下限はFig. 9 Lower Bound (Multiple Step)

れ既に L(ta , tb )，LB(tb , tc ) として求まっているとする．この時 ta → tc 間の下限距離 L(ta , tc ) は下式で与えられる．

(LB(ta , tb ) = ε2 + ε3 + ε4 である．

3.2.2

多段の場合の下限距離

縦長の長方形の場合

L(ta , tb ) + b + LB(tb , tc )LB(ta , tc )L(ta , tc ) = min

図 7 に示したのは，縦長の長方形になる例である．この時，)(5)

LB(ta , tc ) は，ta , tc 間にマーク要素がないと考えて求めた下限距離である．

4.

実験

4.1

類似区間検索の概要

検索グラフと下限距離による効率化を検証するために，類似図7

検索実験を行なった．行なった類似検索は，問合せ q と整数 k

縦長の長方形の場合の下限距離計算が与えられた時，一本の長大な時系列データから k 個の最も qFig. 7 Lower Bound (vertical case)ta から tb に達するには，少なくとも q2 〜q4 に対応する要素を一つずつ通過する必要があり，かつそれだけで tb に達する事もできる．よって下限距離は LB(ta , tb ) = ε2 + ε3 + ε4 である．

3.2.3

横長の長方形の場合

図 8 は横長の長方形の場合である．ta から tb に達するにに類似した部分区間を検索する k-最近傍検索である．検索処理の概要は以下の通りである．

1. マーク付け · · · 値の小さな差分要素をマークする．
2. 解候補の選択 · · · k 個の部分区間を解候補として選択し，qとそれらとの実 DTW 距離を計算する．
3. 検索グラフの探索 · · · 検索グラフを探索しながら区間の下限距離を求める．その時，k 番目の解候補の実距離よりも下限距離が大きな区間をフィルタアウトする事で候補となる区間を絞り込む．

4.2
図8横長の場合の下限距離計算

実験データ

実験には非周期性のランダムウォークデータと，周期性のFig. 8 Lower Bound (horizontal case)

Cylinder, Bell, Funnel[9] の合成データを用いた．図 10 に各は，少なくとも q2 , q3 に対応する要素を一つずつ通過する必データの例を示す．問合せは各データから切り取った部分時系要がある．tb に到達するにはさらに，横長の分だけ q1 〜q4 の2012108106846158どこかを余計に通過する必要がある．下限値を与えるのは，そ610205の中で最小閾値の要素を通過した時である．よって下限値は-2-4以上の三つのケースをまとめると， 一般に一つの有向辺の距縦幅と横幅である．

LB(ta , tb ) =3n−1i=2 εi
Pn−1i=2 εi + (m − n) min{εk }200300400500600700

800

900

1000

0-4-2-60100200300

400500600

700800Cylinder
図 10離の下限値は下式で与えられる．ここで n, m はそれぞれ矩形の(P100Randomwalk

一般の場合

-2000

3.2.4

22-5LB(ta , tb ) = ε2 + ε3 + mink∈1..4 {εk } である．

44900

1000

-40100200300

400500

600

700

800

900

1000

Bell0100

200

300

400

500

600

700800Funnel

合成データの例

Fig. 10 Example of Synthetic Dataset

列とし，各データに対して 10-最近傍検索を 20 回行ない，その平均で評価した．

(n ≥ m)(n < m)比 較 対 象 と し た の は ，問 合 せq と デ ー タ ベ ー ス の 接 尾 辞(4)

d1: , d2: , d3: との DTW 距離を累積距離テーブルを用いて順次計算する方法である．D(q, di: ) を計算する際には di:k なる

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

9001000

論文

DBSJ Letters Vol.6, No.1

部分区間との距離も求まるため，全ての部分区間をチェックする事ができる．ただし，di: の末尾まで計算するのは無駄が大きいため，累積距離テーブルを埋める際に k 番目の候補解の最大距離よりも大きな値しか求まらなくなった時点で計算を打ち切った．

4.3

実験結果

図 11 は，データ長に対する実行時間の変化を示したものである．時間軸は対数目盛である．Cylinder, Bell, Funnel の三つのデータセットについては，それらの平均を cbf として示した．

rw はランダムウォークデータである．マーク要素数は，ランダ

図 11

データベース長に対する検索時間の変化

Fig. 11 Database Length vs. Elapsed Timeムウォークデータで全体の 5%，cbf データで 100% である．また正解の再現率は 100% である．
グラフからデータベース長に関わらず提案手法の速度が比較手法を大幅に上回っている事がわかる．データベース長が100,000 の時には，ランダムウォークデータでは約 800 倍の，cbf データでは約 70 倍の速度向上がみられた．両データ共，データベースが長くなるに従い速度向上の比率が高まる事も確認できる．

5.

まとめと今後の課題

長大な時系列データを対象とし，問合せ時系列データに類似する部分区間を効率的に検索するために利用できる，タイムワーピング距離の下限値計算手法を示した．また，二種の合成データによる類似部分区間検索の実験により，提案手法の有効性を示した．
現在，提案した下限距離を用いてより高速に類似区間を検索するための，検索グラフの効率的な探索手法の考案と実験を進めている．また，過去に蓄積された時系列データを効率的に扱
うには二次記憶上に格納したデータへの I/O コストも考慮に入れる必要があるため，そのための索引手法も検討中である．
距離尺度そのものについては，現在は広く利用されている

DTW 距離 を採用しているが，外れ値などへの対応がより柔軟な距離尺度として最長共有部分列に基づく距離への対応も考えたい．

[文献][1] Chotirat Ratanamahatana and Eamonn Keogh, “Making Time-Series Classification More Accurate Using
Learned”, In proc. of 4th SIAM International Conference on Data Mining, 2004.
[2] Li Junkui, Wang Yuanzhen and Li Xinping, ”LB HUST:

4A Symmetrical Boundary Distance for Clustering TimeSeries”, In proc. of the 9th International Conference ofInformation Technology, 2006.
[3] Joseph B. Kruskal and Mark Liberman, “The Symmetric Time-Warping Problem: From Continuous to Discrete”, Time Warps, String Edits, and Macromolecules:
The Theory and Practice of Sequence Comparison, pp.
125-161 Addison-Wesley, 1983
[4] Eamonn Keogh and Michael Pazzani, “Scaling up Dynamic Time Warping for Datamining Applications”, Inproc. of 6th ACM SIGKDD Knowledge Discovery andData Mining, 2000.
[5] Eamonn Keogh, “Exact Indexing of Dynamic TimeWarping”, In proc. of 28th International Conference onVLDB, 2002.
[6] Sang-Wook Kim, Sanghyun Park, et al., “An IndexBased Approach for Similarity Search Supporting Time
Warping in Large Sequence Databases”, In proc. of 17thICDE, 2001.
[7] Yasushi Sakurai, Masatoshi Yoshikawa and Christos
Faloutsos ”FTW: Fast Similarity Search under the Time
Warping Distance”, In proc. of ACM PODS Conference
2005, pp.326-336, 2005.
[8] 大桃諭, 陳漢雄, 古瀬一隆, 大保信夫, 「タイムワーピングに基づく時系列データの類似検索：次元縮小による効率化」,
DBSJ Letters Vol.4, No.1, pp.1-4[9] Hansheng Lei, Venu Govindaraju ”Regression Time
Warping for Similarity Measure of Sequence”, In proceedings of the Fourth International Conference on
Computer and Information Technology, 2004

石川 雅弘 Masahiro ISHIKAWA
2001 年 筑波大学大学院博士課程工学研究科了．現在つくば国際大学産業情報学科講師．データベースシステムに関する研究に従事．博士 (工学)．日本データベース学会正会員．

吉川 昂伯 Takanori YOSHIKAWA

2005 年 筑波大学情報学類卒業．現在同大大学院システム情報工学研究科在学中．

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

古瀬 一隆 Kazutaka FURUSE

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

大保 信夫 Nobuo OHBO

1968 年 東京大学理学部卒．1970 年 同大大学院修士課程了．同年同大理学部助手．1980 年 筑波大学電子・情報工学系講師．

1995 年 同大電子・情報工学系教授．現在に至る．データベースシステムに関する研究に従事．理博．

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