DTW 算法步骤详解 - 时间序列相似度测量

DTW 算法（Dynamic Time Warping）是一种用于测量两个时间序列之间的相似度的算法，其步骤如下：

1. 定义两个时间序列 X 和 Y，长度分别为 N 和 M。
2. 创建一个距离矩阵 D，其大小为 (N+1)×(M+1)，并初始化所有元素为正无穷大。
3. 初始化矩阵 D 的第一行和第一列，使得 D(0,0)=0，D(0,j)=正无穷大（0<=j<=M），D(i,0)=正无穷大（0<=i<=N）。
4. 对于每个矩阵元素 D(i,j)，计算其值为两个时间序列 X 和 Y 在位置 i 和 j 处的距离（如欧几里得距离、曼哈顿距离等）加上 D(i-1,j)、D(i,j-1) 和 D(i-1,j-1) 中的最小值。
5. 最终的 DTW 距离为矩阵 D(N,M) 的值。

注：在第 4 步中，可以将计算距离的方式改为使用动态时间权重，即在计算距离时，对比较相近的时间点赋予更高的权重，对相距较远的时间点赋予较低的权重。