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

はじめに

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

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

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

アルゴリズム

通常のDTW

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

まず、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}$は次の式で求めることができます。

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と同様です。

一般化された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

参考