動的時間伸縮法（DTW Dynamic Time Warping）における累積距離行列の成分の一般化

# はじめに
動的時間伸縮法（DTW: Dynamic Time Warping）とは2つの波形データの類似度を測定する手法です。

本記事ではDTWにおける累積距離行列の成分を、一般化された1つの数式で算出できる方法をまとめてみました。

なお、DTWを実装する方法については次の記事で解説していますので、ご確認ください。

https://qiita.com/skm_bnn/items/8060882a65f3980e6300

https://qiita.com/skm_bnn/items/2db6509939561cb8d5dd

# アルゴリズム
## 通常のDTW
通常のDTWのアルゴリズムについて簡単に解説します。詳細は次のページでまとめていますので気になる方はご確認ください。

https://qiita.com/skm_bnn/items/233458acff5654406582

まず、2つの波形 $Q, S$ 間のDTW距離を計算するにあたり、累積距離行列は次のようになります。

|$Q$ \ $S$||$s_{1}$|$s_{2}$|$\cdots$|$s_{j}$|$\cdots$|$s_{m}$|
|---|---|---|---|---|---|---|---|
||
|$q_{1}$||$d_{11}$|$d_{12}$||$d_{1j}$||$d_{1m}$|
|$q_{2}$||$d_{21}$|$d_{22}$||$d_{2j}$||$d_{2m}$|
|$\cdots$||||||||
|$q_{i}$||$d_{i1}$|$d_{i2}$||$d_{ij}$||$d_{im}$|
|$\cdots$||||||||
|$q_{n}$||$d_{n1}$|$d_{n2}$||$d_{nj}$||$d_{nm}$|

そして、行列の成分$d_{ij}$は次の式で求めることができます。

```math
d_{ij} = \left\{
\begin{align}
|q_{1} - s_{1}| &                                                 & (i = 1, j = 1)      \qquad\\
|q_{1} - s_{j}| & + d_{1(j-1)}                                    & (i = 1, j \gt 1)    \qquad\\
|q_{i} - s_{1}| & + d_{(i-1)1}                                    & (i > 1, j = 1)      \qquad\\
|q_{i} - s_{j}| & + min(d_{(i-1)(j-1)}, d_{(i-1)j}, d_{i(j-1)})   & (i > 1, j \gt 1)    \qquad
\end{align}
\right.
```


## 一般化されたDTW
本記事では、累積距離行列の初期化処理を変更することで、$d_{ij}$を場合分けせずに前述の式$(4)$のみで表します。

1. まず、累積距離行列における全行の先頭要素として $\infty$ を追加することで、式$(3)$を式$(4)$で表せます。

|$Q$ \ $S$|||$s_{1}$|$s_{2}$|$\cdots$|$s_{j}$|$\cdots$|$s_{m}$|
|---|---|---|---|---|---|---|---|---|
||
|$q_{1}$||$\infty$|$d_{11}$|$d_{12}$||$d_{1j}$||$d_{1m}$|
|$q_{2}$||$\infty$|$d_{21}$|$d_{22}$||$d_{2j}$||$d_{2m}$|
|$\cdots$|||||||||
|$q_{i}$||$\infty$|$d_{i1}$|$d_{i2}$||$d_{ij}$||$d_{im}$|
|$\cdots$|||||||||
|$q_{n}$||$\infty$|$d_{n1}$|$d_{n2}$||$d_{nj}$||$d_{nm}$|

次に、全列の先頭要素として $\infty$ を追加することで、さらに式$(2)$を式$(4)$ で表せます。

|$Q$ \ $S$|||$s_{1}$|$s_{2}$|$\cdots$|$s_{j}$|$\cdots$|$s_{m}$|
|---|---|---|---|---|---|---|---|---|
||
||||$\infty$|$\infty$||$\infty$||$\infty$|
|$q_{1}$||$\infty$|$d_{11}$|$d_{12}$||$d_{1j}$||$d_{1m}$|
|$q_{2}$||$\infty$|$d_{21}$|$d_{22}$||$d_{2j}$||$d_{2m}$|
|$\cdots$|||||||||
|$q_{i}$||$\infty$|$d_{i1}$|$d_{i2}$||$d_{ij}$||$d_{im}$|
|$\cdots$|||||||||
|$q_{n}$||$\infty$|$d_{n1}$|$d_{n2}$||$d_{nj}$||$d_{nm}$|

最後に、左上の成分を $0$ とすることで、式$(1)$を式$(4)$で表せます。

|$Q$ \ $S$|||$s_{1}$|$s_{2}$|$\cdots$|$s_{j}$|$\cdots$|$s_{m}$|
|---|---|---|---|---|---|---|---|---|
||
|||0|$\infty$|$\infty$||$\infty$||$\infty$|
|$q_{1}$||$\infty$|$d_{11}$|$d_{12}$||$d_{1j}$||$d_{1m}$|
|$q_{2}$||$\infty$|$d_{21}$|$d_{22}$||$d_{2j}$||$d_{2m}$|
|$\cdots$|||||||||
|$q_{i}$||$\infty$|$d_{i1}$|$d_{i2}$||$d_{ij}$||$d_{im}$|
|$\cdots$|||||||||
|$q_{n}$||$\infty$|$d_{n1}$|$d_{n2}$||$d_{nj}$||$d_{nm}$|


# 実装
次にPythonで一般化されたDTWのサンプルコードを示します。累積距離行列```D```の初期化が特殊なだけで、他は通常のDTWと同様です。

```python: 一般化されたDTWのサンプルコード
import math

def dtw(Q, S):
  # 累積距離行列の初期化
  D = []

  for i in range(len(Q) + 1):
    D.append([])

    # 全成分を無限大で埋める
    for j in range(len(S) + 1):
      D[i].append(math.inf)

  # 左上の成分のみ0とする
  D[0][0] = 0

  # 累積距離行列を求める
  for i in range(len(Q)):
    for j in range(len(S)):
      D[i+1][j+1] = abs(Q[i] - S[j]) + min(D[i][j], D[i][j+1], D[i+1][j])

  # 初期化のときに追加した無駄な要素を削除する
  del(D[0])
  
  for r in D:
    del(r[0])

  return D
```


# 参考

https://www.youtube.com/watch?v=7sWtbayTUA0&ab_channel=K_DM

https://data-analysis-stats.jp/%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92/dtwdynamic-time-warping%E5%8B%95%E7%9A%84%E6%99%82%E9%96%93%E4%BC%B8%E7%B8%AE%E6%B3%95/

https://magazine.techacademy.jp/magazine/31149