动态时间规整（Dynamic Time Warping, DTW）算法的原理与时间序列对齐过程
1. 问题引入与算法目标
动态时间规整是一种用于度量两个长度可能不同的时间序列之间相似性的经典算法。
它的核心思想是：通过非线性地弯曲或拉伸时间轴，找到两个序列之间最佳的对齐匹配路径，从而最小化它们的累积距离。
- 为什么要用DTW？
直接比较两个时间序列的逐点距离（如欧氏距离）通常不合理。例如，语音识别中同一个单词的发音快慢不同，导致序列长度和局部特征在时间轴上发生了偏移。DTW能“弹性”地对齐它们。 - 应用场景：语音识别、手势识别、生物信息学（DNA序列对齐）、金融时间序列匹配等。
2. 基本概念与符号定义
设有两个时间序列：
- \(X = (x_1, x_2, ..., x_m)\)，长度为 \(m\)
- \(Y = (y_1, y_2, ..., y_n)\)，长度为 \(n\)
我们需要计算它们之间的“最佳对齐”下的累积距离。
3. 算法详细步骤
步骤1：构建距离矩阵
首先计算两个序列所有点对之间的局部距离，形成一个 \(m \times n\) 的矩阵 \(D\)：
\[D(i, j) = d(x_i, y_j) \]
其中 \(d(\cdot, \cdot)\) 通常是欧氏距离：
\[d(x_i, y_j) = (x_i - y_j)^2 \quad \text{或} \quad |x_i - y_j| \]
这个矩阵的每个格子 \((i,j)\) 表示序列 \(X\) 的第 \(i\) 点与序列 \(Y\) 的第 \(j\) 点的不匹配程度。
步骤2：定义累积距离矩阵（动态规划表）
构建另一个矩阵 \(\text{cost}(i, j)\)，表示从起点 \((1,1)\) 到点 \((i,j)\) 的最小累积距离。
初始化：
\[\text{cost}(1,1) = D(1,1) \]
步骤3：确定路径约束条件（规整窗口与步态）
对齐路径必须满足以下约束，以保证合理的对齐：
- 边界条件：路径必须从 \((1,1)\) 开始，到 \((m,n)\) 结束。
- 单调性：路径只能向右、向上或右上方向移动，保证时间顺序不会倒退。
- 连续性：路径必须连续，不能跳过任何点。
常见的步态模式（允许的移动方向）有三种：
- 从 \((i-1, j)\) 水平移动（X序列前进，Y序列不动）
- 从 \((i, j-1)\) 垂直移动（Y序列前进，X序列不动）
- 从 \((i-1, j-1)\) 对角线移动（两序列同时前进）
步骤4：动态规划递推
对于每个格子 \((i,j)\)，计算：
\[\text{cost}(i,j) = D(i,j) + \min \begin{cases} \text{cost}(i-1, j) \\ \text{cost}(i, j-1) \\ \text{cost}(i-1, j-1) \end{cases} \]
这个递推式表示：到达 \((i,j)\) 的最优累积距离 = 当前位置的局部距离 + 到达前一个最佳位置的最小累积距离。
步骤5：回溯寻找最优路径
从终点 \((m,n)\) 开始，根据累积距离矩阵反向回溯，选择使累积距离最小的前驱格子，直到起点 \((1,1)\)。
回溯得到的路径 \(P = [(1,1), ..., (m,n)]\) 就是最优规整路径。
步骤6：计算DTW距离
最终的DTW距离就是累积距离矩阵终点的值：
\[\text{DTW}(X, Y) = \text{cost}(m, n) \]
这个值越小，说明两个序列越相似。
4. 举例说明
假设：
\(X = [1, 3, 4, 9]\)
\(Y = [1, 2, 3, 4, 5]\)
- 计算距离矩阵 \(D\)（以绝对差为例）：
1 2 3 4 5 1 0 1 2 3 4 3 2 1 0 1 2 4 3 2 1 0 1 9 8 7 6 5 4 - 递推计算累积距离矩阵 \(\text{cost}\)（只展示最终矩阵）：
1 2 3 4 5 1 0 1 3 6 10 3 2 1 1 2 4 4 5 3 2 1 2 9 13 10 8 6 5 - 回溯路径（箭头表示前驱来源）：
- 终点 (4,5) 值 5，前驱是 (3,4)（因为 5 = 4 + 1，1来自 (3,4)）
- (3,4) 值 1，前驱是 (2,3)（1 = 0 + 1）
- (2,3) 值 1，前驱是 (1,2)（1 = 1 + 0）
- (1,2) 值 1，前驱是 (1,1)
最优路径：\((1,1) \rightarrow (1,2) \rightarrow (2,3) \rightarrow (3,4) \rightarrow (4,5)\)
- DTW距离 = 5。
5. 优化与变种
- 约束窗口：限制路径只能在距离对角线一定宽度范围内移动，减少计算量（如 Sakoe-Chiba Band、Itakura Parallelogram）。
- 步态权重：对不同移动方向赋予不同权重，控制拉伸惩罚。
- 导数DTW：使用序列的一阶导数代替原始值，对幅度不敏感，更关注形状。
- 快速算法：使用下界函数（如 LB_Keogh）提前排除不匹配序列，加速大规模检索。
6. 总结
DTW的核心是通过动态规划找到最小累积距离的对齐路径，解决了时间序列长度不一致和局部变形的问题。其计算复杂度为 \(O(mn)\)，但通过约束窗口可降低。它是时间序列相似性度量和分类（如最近邻分类器）中的基础工具。