【DTWとは】動的時間伸縮法で2つの時系列データの類似度を調べる

機械学習

2020.03.30

DTW（Dynamic Time Warping：動的時間伸縮法）で2つの時系列データの類似度を調べる方法をまとめました。

DTW（Dynamic Time Warping）とは、2つの時系列データの類似度を調べることができるアルゴリズムです。
2つの時系列データの各サンプル値間の距離（コスト）を総渡りで計算していき、距離（コスト）が最小となる関係性（経路）を見つます。よって

●サンプル数が異なる時系列データ同士の比較が可能
●時間や位相軸が異なっていても、波形が似ていれば類似度が高くなる

という優れた利点があります。つまり、周期や動きが似ているが、サンプル数が異なる時系列データ同士を比較できます。

【アルゴリズム】類似度の算出（計算例つき）

アルゴリズムを計算例つきで解説します。

● 2つの時系列データ（X, Y）を用意します。ます。

x = [1, 2, 3]
y = [2, 3, 4]

● 各サンプル点に対して総当たりで距離を計算し、要素がデータ点同士の距離となる行列D（m × n）を作成します。

D =
[[1. 4. 9.]
 [0. 1. 4.]
 [1. 0. 1.]]

● D[0][0] からD[m][n]までに通るパスのうち、行列の要素の合計が最小となるパスを探索します。
コストパスの要素の合計がDTW距離となります。

D(0, 0) -> D(1, 0)  -> D(2, 1)  -> D(2, 2)が最短経路。
よって、1 + 0 + 0 + 1 = 2がDTW距離（類似度）。