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

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

## 一、DTW解决了什么？

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

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

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

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

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

### 2.1 数学表达

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

– 序列 $X = \{x_1, x_2, …, x_n\}$
– 序列 $Y = \{y_1, y_2, …, y_m\}$

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

路径的累积距离（Cost）计算公式为：
$$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}$$
*(注：$dist$ 通常是曼哈顿距离 $|x_i – y_j|$ 或欧氏距离)*

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

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

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

## 三、MATLAB 代码实战

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

### 3.1 核心算法：计算DTW距离

“`matlab
%% 动态时间规整 (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

% 填充动态规划表
for i = 1:n
for j = 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;
end
end

% 最终的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)]);

% 根据最小值来源更新索引
if idx == 1
i = i – 1; % 来自上方
j = j – 1;
elseif idx == 2
i = i – 1; % 来自左上方
else
j = j – 1; % 来自左方
end
end
end
“`

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

“`matlab
%% 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的优缺点一览