時系列データにおける距離尺度の評価と分析 Survey and Analysis of

時系列データにおける距離尺度の評価と分析
Survey and Analysis of Distance Measures for Time Series
認知支援システム学講座 0312011160 吉田将
指導教員：Basabi Chakraborty，David Ramamonjisoa
1.
はじめに
現在，手書き文字データ，株価データなど，時系列
データとして扱うことができる情報が数多く存在する．
ここで時系列データとは，座標や株価の情報と共に観
測された時間の情報を持つデータである．時系列デー
タに対してデータマイニング，検索，クラスタリング，
クラス分類などの処理を行う場合，時間的な変化を観
測している点から，非時系列データの処理とは異なる
距離尺度が必要となる．また，時系列データのクラス
タリングやクラス分類では距離尺度によって結果が大
きく異なるため，距離尺度は時系列データ処理におい
て最も重要な部分の一つであると考えられる．
本稿では，既存の距離尺度を使用したクラス分類を
行い，正答率により距離尺度の比較を行う．さらに，
距離尺度の比較によって発見された問題点の改良手法
と，実験結果について述べる．
2. 既存の距離尺度
2.1. ユークリッド距離
ユークリッド距離は計算方法が単純であり，計算量
も少ない事から，最も一般的に使用される距離尺度で
ある．𝑥，𝑦を比較する時系列データとし，𝑥の i 番目の
データを𝑥𝑖 とすると，以下の式で計算される．
𝑀
𝐷(𝑥, 𝑦) = ∑ √(𝑥𝑖 − 𝑦𝑖 )2
𝑖=1
ここで M は𝑥，𝑦 の時系列データの長さである．ユー
クリッド距離の問題点は，長さの異なる時系列データ
の比較を行うことができない点や，時間軸方向にずれ
がある時系列データ同士の距離の計算を正しく行う事
ができない点である．
2.2. フーリエ変換距離
フーリエ変換距離はユークリッド距離を拡張した距
離尺度であり，時系列データをフーリエ変換により周
波数成分に分解し，同じ周波数成分の大きさを比較す
る．フーリエ変換後のデータに対してユークリッド距
離と同様の式で距離の計算を行う．この距離尺度を使
用すると，ユークリッド変換とほぼ同じ結果が得られ
るが，時系列データに高周波ノイズが含まれている場
合などに高周波ノイズを除いて比較を行う事が可能で
あるという評価点がある 1)．
2.4. 動的タイムワーピング距離(DTW:
Dynamic Time Warping)
DTW 距離はユークリッド距離における問題点であ
る長さの異なる時系列データの比較を可能とし，最適
な点同士の比較を行うことで時間軸方向のずれにも対
応した距離尺度であり，ユークリッド距離と共に一般
的に使用されている．
DTW 距離は M×N の大きさの類似度行列を作り，
動的計画法により𝑥，𝑦内の比較する点の組を示すワ
ーピングパスを発見し，距離を計算する．ここで M，
N は時系列データ𝑥，𝑦の長さを表す．具体的には以下
の手順で計算を行う．
1.
M×N の大きさの類似度行列 D を作る
2.
初期処理として𝐷0,0 = 0とし，それ以外の類似
度行列の値に∞を代入する
3.
以下の式により i = 1, 2, …, M，j = 1, 2, …, N
の全ての組み合わせの𝐷𝑖,𝑗 を計算する
𝐷𝑖,𝑗 = 𝑓(𝑥𝑖 , 𝑦𝑗 ) + min(𝐷𝑖,𝑗−1 , 𝐷𝑖−1,𝑗 , 𝐷𝑖−1,𝑗−1 )
𝑓(𝑥𝑖 , 𝑦𝑗 ) = √(𝑥𝑖 − 𝑦𝑗 )2
これにより得られた類似度行列における𝐷𝑀−1,𝑁−1 の
値が時系列データ𝑥，𝑦の距離となる．
DTW 距離の問題点は，O(N×M)となるため計算量
が膨大である事や，ノイズに弱い事である．
2.5. EDR 距離(Edit distance on real
sequences)
EDR 距離は DTW 距離に Edit distance の考え方を
取り入れた距離尺度である．EDR 距離では DTW 距離
の𝑓(𝑥𝑖 , 𝑦𝑗 )の部分を以下の式により計算する．
𝑚(𝑥𝑖 , 𝑦𝑗 ) = 𝛩(𝜖 − 𝑓(𝑥𝑖 , 𝑦𝑗 ))
𝛩( )はヘヴィサイドの階段関数であり，𝛩(𝑧)において
z ≧ 0 であれば 1 を返し，z < 0 であれば 0 を返す．
ϵは
閾値を示しており，𝑚(𝑥𝑖 , 𝑦𝑖 )は，𝑥𝑖 と𝑦𝑗 の距離が閾値よ
りも大きければペナルティとして𝐷𝑖−1,𝑗−1 に 1 を加え
た値を𝐷𝑖,𝑗 に代入する．EDR 距離は DTW 距離より優
れた結果が得られる事があるが，適切な ϵの値を設定
するのが難しい点や，DTW 距離と同程度の計算量で
ある点が問題点である．
2.3. 自己回帰係数距離
3. 実験
3.1. 実験概要
自己回帰係数距離は自己回帰モデルの係数が時系列
データの特徴を表しているという考えから生まれた距
離尺度である 2)．時系列データから自己回帰係数を求
め，自己回帰係数をユークリッド距離の式に当てはめ
る事で距離の計算を行う．自己回帰係数距離の問題点
は，比較に用いる自己回帰係数の数を設定する必要が
ある点や，データによっては自己回帰モデルによるデ
ータの表現が難しい点である．
これまでに挙げた 5 つの距離尺度を用いて様々な時
系列データセットに対してクラス分類を行い，その正
答率により距離尺度を比較する．クラス分類の方法と
して最も単純な 1-NN 法を用いる．
また，多くの種類の時系列データを使用し，クラス分
類を行うことで，様々な種類の時系列データに対する
柔軟性について比較する．ここでは，距離尺度の計算
において重要な計算量についての比較も行う．
3.2. 実験データセット
4.2. データ削減手法
UCR(University of California, Riverside) time
series repository で公開されている 43 種類の時系列
データセットを使用する 3)．
連続してデータの値が上昇，または下降する点の間
となる点はデータの特徴としての意味が小さいと考え，
その点を削除する．この手法を使用すると，時系列デ
ータ毎の長さが統一されなくなるため，通常のユーク
リッド距離による距離計算はできなくなる．
図 1 は時系列データのデータ削減例である．左のグ
ラフが削減前のデータであり，円で囲われた点を削除
することで右のグラフのデータとなる．
3.3. パラメータ設定
自己回帰係数距離における自己回帰係数の数は，1
から 10 までの数で実験を行い，最も良い結果を得られ
た係数の数とする．
EDR 距離における閾値は，教師データ同士のユーク
リッド距離による比較を行い，全ての比較点の平均距
離とする．
3.4. 実験結果・考察
表 1 は 43 種類のデータセットに対してユークリッド
距離，自己回帰係数距離，DTW 距離を使用したクラ
ス分類の正答率の中から，クラス数が下位と上位のデ
ータセットを 3 つずつ取り出した結果である．自己回
帰係数距離において，クラス数が増加するほど他の距
離尺度と比較してもクラス分類の正答率が大幅に低下
することがわかる．
表 1 クラス数が下位と上位のデータセットを 3 つ
ずつ取り出したクラス分類結果
クラス
数
データセット名
ユークリッド
距離
DTW
距離
自己回帰
係数距離
ECG200
2
0.89
0.79
0.79
ECGFiveDays
2
0.79
0.74
0.79
Gun_Point
2
0.95
0.79
0.88
WordsSynonyms
25
0.63
0.21
0.67
Adiac
37
0.60
0.29
0.59
50words
50
0.67
0.21
0.71
次に距離尺度の柔軟性について比較する．ここでは，
43 種類の時系列データに対してクラス分類を行い，正
答率の平均を見ることで比較を行う．表 2 はそれぞれ
の距離尺度の平均正答率と計算量である．
表 2 それぞれの距離尺度の平均正答率と計算量
ユークリッド
距離
平均
正答率
計算量
0.76
O(𝑀)
フーリエ
変換距離
自己回帰
係数距離
0.73
0.53
2
2
O(𝑀 )
O(𝑀 )
DTW
距離
EDR
距離
0.79
0.75
2
O(𝑀 ) O(𝑀2 )
これを見ると，柔軟性の点では，DTW 距離が最も
優れていると言える．しかし，計算量を併せて見ると，
ユークリッド距離が最も優れていると言える．そこで，
DTW 距離の前処理でデータの長さを削減する事で速
度が速く，高い成果を得られると考え，追加実験を行
った．
4.
追加実験
4.1. 実験概要
前処理で時系列データの長さを削減し，DTW 距離
による距離計算を行い，計算量，クラス分類の正答率
について従来の DTW 距離と比較を行う．
図 1 時系列データの削減例
4.3. 実験結果・考察
表 3 は従来の DTW 距離とデータ削減後の DTW 距
離を使用したクラス分類の平均正答率と平均計算量で
ある．データの削減により，正答率が僅かに減少した
が，計算量を 15％以下に削減する事が出来た．また，
いくつかのデータセットにおいて，ユークリッド距離
よりも少ない計算量で距離を計算することが出来た．
表 3 従来の DTW 距離とデータ削減後の DTW 距離
を使用したクラス分類の結果
従来の DTW 距離
データ削減後の DTW 距離
平均正答率
0.79
0.76
平均計算量
294707
43497
5.
おわりに
本稿では，既存の距離尺度を使用したクラス分類を
行い，正答率を比較することで距離尺度の比較を行っ
た．その結果，柔軟性に関しては DTW 距離が最も優
れている事がわかった．また，DTW 距離の問題点で
ある計算量についても，提案手法により改良すること
が出来た．
今後は距離尺度の精度を下げることなく，計算量を
減らすことが出来るようなアルゴリズムの改良や，新
たなアルゴリズムの開発を課題として研究を行う．
参考文献
1) Serrá, J., Arcos, J.L.: An empirical
evaluation of similarity measures for time
series classification. Knowledge-Based
Systems , Vol.67, pp. 305-314, 2014.
2) T. Warren Liao: Clustering of time series
data-a survey, Pattern Recognition, Vol.38
No.11, pp.1857-1874, 2005.
3) Keogh, E., Zhu, Q., Hu, B., Hao. Y., Xi, X.,
Wei, L. & Ratanamahatana, C. A.: (2011).
The UCR Time Series
Classification/Clustering Homepage:
www.cs.ucr.edu/~eamonn/time_series_data
/.

Download Report