はじめに
動的時間伸縮法（DTW: Dynamic Time Warping）とは2つの波形データの類似度を測定する手法です。
DTW は各波形データのデータポイントの距離を総当たりで求めることで、最短となるパス（最適な波形データ間の対応関係）を探索して、DTW 距離（波形間の累積的な距離）を算出します。
すなわち、DTW によって得られる距離は、2つの波形データの非類似度（似てない度合い）を表すので、この値が小さいほど2つの波形データは似ている形状とされます。
ウェアラブルデバイスにおいてはジェスチャ認識の処理で利用されることがあります。
実装については、次の記事で解説しています。
- ライブラリを利用した実装の解説
- ライブラリを利用しない実装の解説
アルゴリズム
一般形
数式を用いた一般的な表現で、DTW の計算手順を解説します。
もし、分かりづらい場合は 具体例 にお進みください。
-
2つの波形 $Q, S$ を用意します
$$
Q = [q_{1}, q_{2}, \cdots, q_{n}], S = [s_{1}, s_{2}, \cdots, s_{m}]
$$- $n$: 波形 $Q$ のデータポイント数
- $m$: 波形 $S$ のデータポイント数
- $q_i (i = 1, \cdots, n)$: 波形 $Q$ のデータポイント
- $s_i (i = 1, \cdots, m)$: 波形 $S$ のデータポイント
-
$q_i$ を行ラベル、$s_j$ を列ラベルとする表（累積距離行列）を作成します
$Q$ \ $S$ $s_{1}$ $s_{2}$ $\cdots$ $s_{j}$ $\cdots$ $s_{m}$ $q_{1}$ $d_{1,1}$ $d_{1,2}$ $d_{1,j}$ $d_{1,m}$ $q_{2}$ $d_{2,1}$ $d_{2,2}$ $d_{2,j}$ $d_{2,m}$ $\cdots$ $q_{i}$ $d_{i,1}$ $d_{i,2}$ $d_{i,j}$ $d_{i,m}$ $\cdots$ $q_{n}$ $d_{n,1}$ $d_{n,2}$ $d_{n,j}$ $d_{n,m}$ - $d_{i,j}$: $q_i, s_j$ 間の累積的な距離（次の手順から算出していきます）
-
累積距離行列の1行目 $[d_{1,1}, d_{1,2}, \cdots, d_{1,m}]$ を次の式で求めます
d_{1, j} = \left\{ \begin{array}{ll} |q_{1} - s_{1}| & (j = 1)\\ |q_{1} - s_{j}| + d_{1(j-1)} & (j \gt 1) \end{array} \right. -
累積距離行列の2行目以降 $[d_{i,1}, d_{i,2}, \cdots, d_{i,m}] (1 \lt i \le n)$ を次の式で求めます
d_{i, j} = \left\{ \begin{array}{ll} |q_{i} - s_{1}| + d_{(i-1), 1} & (j = 1)\\ |q_{i} - s_{j}| + min(d_{(i-1), (j-1)}, d_{(i-1), j}, d_{i, (j-1)}) & (j \gt 1) \end{array} \right. -
$d_{n,m}$ が DTW 距離となります
$$dist_{DTW} = d_{n,m}$$
具体例
次の波形データ $Q, S$ の DTW 距離を算出していきます。
$$
Q = [3, 4, 3, 3, 2, 3], S = [1, 6, 4, 4, 1, 5]
$$
-
累積距離行列を作成します
$Q$ \ $S$ 1 6 4 4 1 5 3 $d_{1,1}$ $d_{1,2}$ $d_{1,3}$ $d_{1,4}$ $d_{1,5}$ $d_{1,6}$ 4 $d_{2,1}$ $d_{2,2}$ $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$ -
累積距離行列の1行目 $[d_{1,1}, d_{1,2}, \cdots, d_{1,6}]$ を求めていきます
-
累積距離行列の一番左上にある $d_{1, 1}$ を求めます
$d_{1, 1}$ は1行目の行ラベルである $q_1 = 3$ と 1列目の列ラベルである $s_1 = 1$ の差の絶対値です
$$
d_{1, 1} = |q_{1} - s_{1}| = |3 - 1| = 2
$$$Q$ \ $S$ 1 6 4 4 1 5 3 2 $d_{1,2}$ $d_{1,3}$ $d_{1,4}$ $d_{1,5}$ $d_{1,6}$ 4 $d_{2,1}$ $d_{2,2}$ $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$ -
$d_{1, 2}$ を求めます
$d_{1, 2}$ は1行目の行ラベルである $q_1 = 3$ と 2列目の列ラベルである $s_2 = 6$ の差の絶対値に、$d_{1, 2}$ の左にある $d_{1, 1}$ を足した値です
$$
d_{1, 2} = |q_{1} - s_{2}| + d_{1, 1} = |3 - 6| + 2= 5
$$$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 $d_{1,3}$ $d_{1,4}$ $d_{1,5}$ $d_{1,6}$ 4 $d_{2,1}$ $d_{2,2}$ $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$ -
$d_{1, 2}$ と同様に、$d_{1, 3}$ から $d_{1, 6}$ まで求めます
$d_{1, j}$ は1行目の行ラベルである $q_1 = 3$ と $j$ 列目の列ラベルである $s_j$ の差の絶対値に、$d_{1, j}$ の左にある $d_{1, j-1}$ を足した値です
$$
d_{1, j} = |q_{1} - s_{j}| + d_{1, j-1} \qquad (j = 3, 4, 5, 6)
$$$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 6 7 9 11 4 $d_{2,1}$ $d_{2,2}$ $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$
-
-
累積距離行列の2行目 $[d_{2,1}, d_{2,2}, \cdots, d_{2,m}]$ を求めていきます
-
$d_{2, 1}$ を求めていきます
$d_{2, 1}$ は2行目の行ラベルである $q_2 = 4$ と 1列目の列ラベルである $s_1 = 1$ の差の絶対値に、
$d_{2, 1}$ の上にある $d_{1, 1}$ を足した値ですd_{2, 1} = |q_{2} - s_{1}| + d_{1, 1} = |4 - 1| + 2 = 5$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 6 7 9 11 4 5 $d_{2,2}$ $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$ -
$d_{2, 2}$ を求めます
まず、2行目の行ラベルである $q_2 = 4$ と 2列目の列ラベルである $s_2 = 6$ の差の絶対値を計算します
|q_{2} - s_{2}| = |4 - 6| = 2次に、$d_{2, 2}$ の左上にある $d_{1, 1}$と上にある $d_{1, 2}$、左にある $d_{2, 1}$のうち最小な値を選択します
min(d_{1, 1}, d_{1, 2}, d_{2, 1}) = min(2, 5, 5) = 2$d_{2, 2}$ は上記で得られた $|q_{2} - s_{2}|$ と $min(d_{1, 1}, d_{1, 2}, d_{2, 1})$ の和です
d_{2, 2} = |q_{2} - s_{2}| + min(d_{1, 1}, d_{1, 2}, d_{2, 1}) = 2 + 2 = 4$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 6 7 9 11 4 5 4 $d_{2,3}$ $d_{2,4}$ $d_{2,5}$ $d_{2,6}$ 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$ -
$d_{2, 2}$ と同様に、$d_{2, 3}$ から $d_{2, 6}$ まで求めます
$d_{2, j}$ は2行目の行ラベルである $q_2 = 4$ と $j$ 列目の列ラベルである $s_j$ の差の絶対値に、$d_{2, j}$ の左上にある $d_{1, j-1}$ と上にある $d_{1, j}$、左にある $d_{2, j-1}$ のうち最小な値を足した値です
d_{2, j} = |q_{2} - s_{j}| + min(d_{1, (j-1)}, d_{1. j}, d_{2, (j-1)})$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 6 7 9 11 4 5 4 4 4 7 8 3 $d_{3,1}$ $d_{3,2}$ $d_{3,3}$ $d_{3,4}$ $d_{3,5}$ $d_{3,6}$ 3 $d_{4,1}$ $d_{4,2}$ $d_{4,3}$ $d_{4,4}$ $d_{4,5}$ $d_{4,6}$ 2 $d_{5,1}$ $d_{5,2}$ $d_{5,3}$ $d_{5,4}$ $d_{5,5}$ $d_{5,6}$ 3 $d_{6,1}$ $d_{6,2}$ $d_{6,3}$ $d_{6,4}$ $d_{6,5}$ $d_{6,6}$
-
-
累積距離行列の2行目と同様に、3行目以降 $[d_{i,1}, d_{i,2}, \cdots, d_{i,m}] (1 \lt i \le n)$ を求めます
是非、練習として計算してみてください
答え
$Q$ \ $S$ 1 6 4 4 1 5 3 2 5 6 7 9 11 4 5 4 4 4 7 8 3 7 7 5 5 6 8 3 9 10 6 6 7 8 2 10 13 8 8 7 10 3 12 13 9 9 9 9 -
$d_{n,m}$ が DTW 距離となります
答え
$$dist_{DTW} = d_{n,m} = 9$$
参考