动态时间规整（DTW）：跨越时间维度的相似性度量

一、DTW解决了什么？

在处理时间序列数据时，我们最常碰到的难题就是“不同步”。比如：

• 语音识别：同样是说“你好”，有人语速快，有人语速慢，直接拿时间来对齐比对是完全不准的。
• 股票走势：同样的一波上涨行情，A股票用了3天走完，B股票因为利好消息发酵慢，走了7天才走完。

传统的欧氏距离（Euclidean Distance）是“死板”的，它要求两个序列在时间轴上必须严格一一对应。而动态时间规整（Dynamic Time Warping, DTW） 就像是给两条曲线装上了“弹性关节”，它允许非线性拉伸或压缩时间轴，从而找到两者之间的最优对齐路径。

二、DTW的核心原理：动态规划（DP）

DTW的本质是一个典型的动态规划（Dynamic Programming）问题。它的核心思想是：为了把两条序列对齐，我不要求你每一步都迈得一样大，但我要把总成本降到最低。

2.1 数学表达

假设我们有两条时间序列：

• 序列X={x1,x2,...,xn}X = \{x_1, x_2, ..., x_n\}X={x1​,x2​,...,xn​}
• 序列Y={y1,y2,...,ym}Y = \{y_1, y_2, ..., y_m\}Y={y1​,y2​,...,ym​}

我们在它们之间寻找一条规整路径WWW，这条路径由一系列点(i,j)(i, j)(i,j)组成，代表XXX的第iii个元素与YYY的第jjj个元素进行了对齐。

路径的累积距离（Cost）计算公式为：
DTW(i,j)=dist(xi,yj)+min⁡{DTW(i−1,j)DTW(i,j−1)DTW(i−1,j−1)DTW(i, j) = dist(x_i, y_j) + \min \begin{cases} DTW(i-1, j) \\ DTW(i, j-1) \\ DTW(i-1, j-1) \end{cases}DTW(i,j)=dist(xi​,yj​)+min⎩⎨⎧​DTW(i−1,j)DTW(i,j−1)DTW(i−1,j−1)​
(注：distdistdist通常是曼哈顿距离∣xi−yj∣|x_i - y_j|∣xi​−yj​∣或欧氏距离)

2.2 路径必须满足的“潜规则”

为了保证规整的物理意义，这条路径不能乱连，必须同时满足三个硬性条件：

1. 边界条件（Boundary Condition）：路径必须从(1,1)(1,1)(1,1)出发，到(n,m)(n,m)(n,m)结束。
2. 连续性（Continuity）：路径上的点必须是相邻的，不能跳过任何一个点（比如不能从(1,1)(1,1)(1,1)直接跳到(3,2)(3,2)(3,2)）。
3. 单调性（Monotonicity）：路径只能向右、向上或斜着走，绝不能往回走（不能出现时间倒流）。

三、MATLAB 代码实战

下面是一份基于MATLAB的高效DTW实现代码，包含了核心计算逻辑和规整路径的回溯（Backtracking）。

3.1 核心算法：计算DTW距离

%% 动态时间规整 (DTW) 核心算法% seq1, seq2: 输入的两个时间序列 (列向量)% dist: 返回的最短规整距离function[dtw_dist,acc_cost_mat,path]=my_dtw(seq1,seq2)% 获取序列长度n=length(seq1);m=length(seq2);% 第一步：构建累积距离矩阵 (Accumulated Cost Matrix)% 初始化一个 (n+1) x (m+1) 的矩阵，第一行第一列设为 inf，防止非法移动acc_cost_mat=inf(n+1,m+1);acc_cost_mat(1,1)=0;% 起点距离为0% 填充动态规划表fori=1:nforj=1:m% 当前的匹配代价 (通常使用绝对值距离或平方距离)cost=abs(seq1(i)-seq2(j));% 取三个方向的最小值：左、上、左上prev_min=min([acc_cost_mat(i,j),...acc_cost_mat(i,j+1),...acc_cost_mat(i+1,j)]);% 更新当前累积距离acc_cost_mat(i+1,j+1)=cost+prev_min;endend% 最终的DTW距离就是矩阵的右下角元素dtw_dist=acc_cost_mat(n+1,m+1);% 第二步：回溯寻找最优路径 (Warping Path)path=[];i=n;j=m;while(i>0&&j>0)path=[i,j;path];% 将当前点加入路径头部% 找出到达当前点的最小代价来源[~,idx]=min([acc_cost_mat(i,j),...acc_cost_mat(i,j+1),...acc_cost_mat(i+1,j)]);% 根据最小值来源更新索引ifidx==1i=i-1;% 来自上方j=j-1;elseifidx==2i=i-1;% 来自左上方elsej=j-1;% 来自左方endendend

3.2 实战演示：绘制规整效果图

%% DTW 实战演示clc;clear;close all;% 1. 生成两条不同步的测试序列x=1:100;seq_a=sin(linspace(0,2*pi,100))+0.05*randn(1,100);% 正常速度seq_b=sin(linspace(0,2*pi,80))+0.05*randn(1,80);% 速度更快% 2. 执行DTW计算[dtw_distance,acc_cost,warping_path]=my_dtw(seq_a',seq_b');fprintf('两条序列的DTW距离为: %.4f\n',dtw_distance);% 3. 可视化结果figure('Position',[100,100,1400,500]);% 子图1：原始序列对比subplot(1,3,1);plot(seq_a,'b-','LineWidth',2);hold on;plot(seq_b,'r--','LineWidth',2);legend('序列 A (慢)','序列 B (快)');title('原始时间序列 (Raw Sequences)');xlabel('时间点');ylabel('幅值');grid on;% 子图2：累积代价矩阵热图subplot(1,3,2);imagesc(acc_cost);colormap(jet);colorbar;hold on;% 绘制最优规整路径plot(warping_path(:,2),warping_path(:,1),'w-','LineWidth',2);plot(warping_path(:,2),warping_path(:,1),'ko','MarkerSize',4);title('累积代价矩阵与规整路径 (Accumulated Cost Matrix)');xlabel('序列 B 索引');ylabel('序列 A 索引');axis xy;% 保证坐标方向正确% 子图3：规整后的对齐效果subplot(1,3,3);plot(seq_a,'b-','LineWidth',2);hold on;% 提取规整后的序列 B (按照路径索引重新排列)seq_b_warped=seq_b(warping_path(:,2));plot(seq_b_warped,'r--','LineWidth',2);legend('序列 A','序列 B (规整后)');title('时间规整后的对齐效果 (Aligned Sequences)');xlabel('规整后索引');ylabel('幅值');grid on;sgtitle('动态时间规整 (DTW) 算法演示');

参考代码 动态时间规整（DTW）www.youwenfan.com/contentcsu/55229.html

四、DTW的优缺点一览