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

一、DTW解决了什么在处理时间序列数据时我们最常碰到的难题就是“不同步”。比如语音识别同样是说“你好”有人语速快有人语速慢直接拿时间来对齐比对是完全不准的。股票走势同样的一波上涨行情A股票用了3天走完B股票因为利好消息发酵慢走了7天才走完。传统的欧氏距离Euclidean Distance是“死板”的它要求两个序列在时间轴上必须严格一一对应。而动态时间规整Dynamic Time Warping, DTW 就像是给两条曲线装上了“弹性关节”它允许非线性拉伸或压缩时间轴从而找到两者之间的最优对齐路径。二、DTW的核心原理动态规划DPDTW的本质是一个典型的动态规划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 路径必须满足的“潜规则”为了保证规整的物理意义这条路径不能乱连必须同时满足三个硬性条件边界条件Boundary Condition路径必须从(1,1)(1,1)(1,1)出发到(n,m)(n,m)(n,m)结束。连续性Continuity路径上的点必须是相邻的不能跳过任何一个点比如不能从(1,1)(1,1)(1,1)直接跳到(3,2)(3,2)(3,2)。单调性Monotonicity路径只能向右、向上或斜着走绝不能往回走不能出现时间倒流。三、MATLAB 代码实战下面是一份基于MATLAB的高效DTW实现代码包含了核心计算逻辑和规整路径的回溯Backtracking。3.1 核心算法计算DTW距离%% 动态时间规整 (DTW) 核心算法% seq1, seq2: 输入的两个时间序列 (列向量)% dist: 返回的最短规整距离function[dtw_dist,acc_cost_mat,path]my_dtw(seq1,seq2)% 获取序列长度nlength(seq1);mlength(seq2);% 第一步构建累积距离矩阵 (Accumulated Cost Matrix)% 初始化一个 (n1) x (m1) 的矩阵第一行第一列设为 inf防止非法移动acc_cost_matinf(n1,m1);acc_cost_mat(1,1)0;% 起点距离为0% 填充动态规划表fori1:nforj1:m% 当前的匹配代价 (通常使用绝对值距离或平方距离)costabs(seq1(i)-seq2(j));% 取三个方向的最小值左、上、左上prev_minmin([acc_cost_mat(i,j),...acc_cost_mat(i,j1),...acc_cost_mat(i1,j)]);% 更新当前累积距离acc_cost_mat(i1,j1)costprev_min;endend% 最终的DTW距离就是矩阵的右下角元素dtw_distacc_cost_mat(n1,m1);% 第二步回溯寻找最优路径 (Warping Path)path[];in;jm;while(i0j0)path[i,j;path];% 将当前点加入路径头部% 找出到达当前点的最小代价来源[~,idx]min([acc_cost_mat(i,j),...acc_cost_mat(i,j1),...acc_cost_mat(i1,j)]);% 根据最小值来源更新索引ifidx1ii-1;% 来自上方jj-1;elseifidx2ii-1;% 来自左上方elsejj-1;% 来自左方endendend3.2 实战演示绘制规整效果图%% DTW 实战演示clc;clear;close all;% 1. 生成两条不同步的测试序列x1:100;seq_asin(linspace(0,2*pi,100))0.05*randn(1,100);% 正常速度seq_bsin(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_warpedseq_b(warping_path(:,2));plot(seq_b_warped,r--,LineWidth,2);legend(序列 A,序列 B (规整后));title(时间规整后的对齐效果 (Aligned Sequences));xlabel(规整后索引);ylabel(幅值);grid on;sgtitle(动态时间规整 (DTW) 算法演示);参考代码 动态时间规整DTWwww.youwenfan.com/contentcsu/55229.html四、DTW的优缺点一览维度优势 (Pros)劣势 (Cons)适应能力能够完美处理非线性形变的时间序列非常灵活。相比简单的欧氏距离计算复杂度较高为O(N×M)O(N \times M)O(N×M)。鲁棒性对局部的时间伸缩、平移不敏感抗噪声能力较强。容易受到离群点 (Outliers)的影响导致路径发生不必要的扭曲。直观性规整路径可以直观展示两个序列的对应关系。如果两个序列毫无关联DTW依然会强行算出一条路径可能导致误判。