Dynamic Time Warping

发表于 | 分类于

Dynamic Time Warping

Dynamic Time Warping 的目标是比较两个依赖于时间的序列 $X:=(x_1, x_2, \cdots, x_N), Y:=(y_1, y_2,\cdots, y_M)$，这些序列可以是离散信号（时间序列），或者更一般地，是在等距时间点采样的特征序列。记 $\mathcal{F}$为特征空间，则 $x_n, y_m\in\mathcal{F},n\in[1:N],m\in[1:M]$。为了比较两个不同的特征 $x,y\in\mathcal{F}$，需要引入一个局部花费度量（local cost measure），有时也称为局部距离度量（local distance measure），其定义为

$$c:\mathcal{F}\times\mathcal{F}\to\mathbb{R}_{\ge0}$$

通常情况下，如果 $x$ 与 $y$ 相似，$c(x,y)$ 会比较小，否则会很大。通过计算序列 $X$ 和 $Y$ 的每个元素形成的数对的局部花费度量，可以得到花费矩阵 $C\in\mathbb{R}^{N\times M}$，定义为 $C(n,m):=c(x_n,y_m)$。那么我们的目标是寻找 $X$ 与 $Y$ 之间拥有最小整体花费的alignment。

定义 一个 $(N,M)-warping path$ 是一个序列 $p=(p_1,p_2,\cdots,p_L)$，其中 $p_l=(n_l,m_l)\in[1:N]\times[1:M],l\in[1:L]$ 满足下面三个条件：

  1. 边界条件：$p_1=(1,1),\ p_L={N,M}$
  2. 单调条件：$n_1\le n_2\le\cdots\le n_L,\ m_1\le m_2\le\cdots\le m_L$
  3. 步长条件：$p_{i+1}-p_i\in{(1,0),(0,1),(1,1)},\ l\in[1:L-1]$

设局部花费度量为 $c$，$X$ 和 $Y$ 之间的warping path $p$ 的总花费 $c_p(X,Y)$ 可定义为
$$c_p(X,Y):=\sum_{l=1}^{L}c(x_{nl},y_{ml})$$
此外，$X$ 和 $Y$ 之间的最优 warping path 是所有可能的warping paths中具有最小总花费的warping path $p^$。$X$ 和 $Y$ 之间的DTW距离 $DTW(X,Y)$ 定义为
$$DTW(X,Y):=c_{p^}(X,Y)=\min{c_p(X,Y)|p is an (N,M)-warping path}$$

remark:

  1. 在局部话费度量 $c$ 是对称的情况下，DTW距离是对称的。但DTW距离一般是非正定的，即使 $c$ 正定。
  2. DTW距离一般不满足三角不等式性。

例 令 $\mathcal{F}={\alpha,\beta,\gamma}$ 是由三个特征组成的特征空间，定义花费度量 $c:\mathcal{F}\times\mathcal{F}\to{0,1}$ 为
$$c{x,y}=\begin{cases}
0 & if x=y \
1 & if x \neq y\end{cases},x,y\in\mathcal{F}$$
注意 $c$ 是定义在 $\mathcal{F}$ 上的度量函数，满足三角不等式性。
现在考虑 $X=(\alpha,\beta,\gamma),Y=(\alpha,\beta,\beta,\gamma),Z=(\alpha,\gamma,\gamma)$。容易算得：$DTW(X,Y)=0, DTW(X,Z)=1,DTW(Y,Z)=2$。因此 $DTW(Y,Z)\ge DTW(X,Y)+DTW(X,Z)$，不满足三角不等式性。注意到 $p^1=((1,1),(2,2),(3,2),(4,3)),p^2=((1,1),(2,1),(3,2),(4,3)),p^3=((1,1),(2,2),(3,3),(4,3))$ 是 $Y$ 和 $Z$ 之间的不同的最优 warping paths，这说明optimal warping path 一般不唯一。

为了寻找最优路径 $p^*$，一种可以尝试的方法是检测 $X$ 和 $Y$ 之间的每一条可能的 warping path，这种方法的计算复杂度会随着 $N$ 和 $M$ 的增长呈指数增长，下面介绍一种复杂度为 $O(NM)$ 的动态规划算法。

未完。。。