时间序列中的动态时间规整 (dtw)

动态时间规整 (DTW) 是一种用于测量时间序列之间相似度的算法，即使它们的速度或持续时间可能不同。与欧几里得距离等首选距离度量不同，DTW 可以通过允许灵活地对齐序列来适应时间失真。它被广泛用于语音识别、生物信息学、金融以及需要时间序列模式匹配的各种领域。

DTW 的工作原理

动态时间规整 (DTW) 是一种动态规划算法，它可以在两个时间序列之间找到最优的对齐方式，即使它们的速度或持续时间不同。与需要一对一比较的欧几里得距离不同，DTW 允许拉伸和压缩时间轴以获得最佳匹配。这使其在语音识别、手写分析和经济时间序列分析等应用中非常有用。

步骤 1：计算距离矩阵

DTW 的第一步是计算两个时间序列之间的距离矩阵。此矩阵上的每个元素代表序列中相应元素之间的距离（通常是绝对值或差值的平方）。例如，考虑时间序列

序列 A = [1, 2, 3, 4]

序列 B = [1, 1.5, 2.5, 3.5, 4]

将创建一个矩阵，其中单元格 (i, j) 的值为序列 A 的第 i 个元素与序列 B 的第 j 个元素之间的距离。这为在允许对齐偏移的同时衡量相似性提供了基础。

步骤 2：构建累积成本矩阵

一旦构建了距离矩阵，DTW 就会构建一个累积成本矩阵来确定对齐序列的最佳路径。此矩阵上每个位置 (i, j) 的成本计算如下：

C(i, j) = D(i, j) + min(C(i − 1, j), C(i, j − 1), C(i − 1, j − 1))

此公式确保对齐路径沿着矩阵中的最低成本方向前进。min() 函数中的三个项允许算法考虑来自左侧、底部或对角线方向的移动，这考虑了序列中的时间失真。

步骤 3：找到最优规整路径

一旦累积成本矩阵被填充，算法就会从最后一个单元格（右下角）回溯到第一个单元格（左上角），从而确定最佳规整路径。这条路径代表了两个序列必须如何对齐才能最小化它们的总距离。与直接的一对一映射不同，规整路径可以将序列 A 中的一个点映射到序列 B 中的多个点，反之亦然，从而实现灵活的对齐。

例如，如果序列 A 以恒定速度前进，但序列 B 波动，DTW 将会拉伸和压缩序列的元素，使它们尽可能相似。这确保了相应的模式正确对齐，即使它们在每个序列中以不同的速度出现。

步骤 4：计算 DTW 距离

最终的 DTW 距离是矩阵右下角的累积值。此成本代表了最优对齐的总成本。较小的 DTW 距离表示序列更相似，而较大的 DTW 距离表示不相似度更高。

DTW 的关键特性

动态时间规整 (DTW) 是一种用于对齐时间序列数据的通用算法，尤其适用于序列在速度或持续时间上存在差异的情况。为了确保有意义且准确的对齐，DTW 遵循几个关键属性。

1. 边界条件

规整路径必须从每个时间序列的第一个点开始，并在最后一个点结束。这确保了考虑了整个序列，并且不会遗漏时间序列的任何部分。

示例：如果我们有两个时间序列 A 和 B，规整路径将始终从 (A1, B1) 开始，并在 (An, Bm) 结束，其中 n 和 m 是序列的长度。

2. 连续性

规整路径在矩阵中逐渐前进，这意味着每一步都必须移动到相邻的单元格。这可以防止对齐中的跳跃，并确保一个序列中的每个点在另一个序列中都有一个对应的匹配。

成本矩阵中的允许移动

• 对角线移动 (i-1, j-1)：对齐两个序列的当前点。
• 垂直移动 (i-1, j)：保持序列 B 不变，拉伸序列 A。
• 水平移动 (i, j-1)：保持序列 A 不变，拉伸序列 B。

此属性确保所有点都以逻辑的、逐步的方式进行匹配。

3. 单调性

对齐路径必须随时间向前移动，这意味着两个序列中的索引只能增加。不允许向后移动，这确保了有效的时间顺序。

示例

如果我们有一条规整路径，例如 (A2, B3) → (A3, B4)，我们不能回溯到 (A1, B2)。

这可以防止不合逻辑的对齐，即时间事件被颠倒。

4. 规整约束（窗口化）

为了提高效率，DTW 可以应用约束来限制序列的拉伸程度。一种常见技术是 Sakoe-Chiba 带，它将规整限制在成本矩阵对角线周围的一个固定窗口内。

5. 斜率约束（步长条件）

DTW 限制一个序列在一个方向上拉伸的频率，以防止过度规整。一种常见的约束是防止连续出现过多的水平或垂直移动，以确保更均衡的对齐。

示例

如果一个序列被过度拉伸而另一个序列保持不变，则对齐可能会变得不可靠。斜率约束有助于保持合理的规整路径。

6. 全局最优性

DTW 通过最小化总规整成本来找到最优的对齐方式。选择的对齐路径是两条序列之间累积距离最低的路径。

如何实现？

通过使用动态规划，DTW 计算成本矩阵中的最优路径，从而确保在给定约束条件下的最优对齐。

DTW 的关键属性，包括边界条件、连续性、单调性、规整约束、斜率约束和全局最优性，确保了时间序列的对齐是准确且有意义的。通过遵循这些原则，DTW 为比较具有灵活时间变化的序列提供了一个强大的工具。

DTW 的应用

动态时间规整 (DTW) 被广泛应用于各种需要时间序列数据对齐、比较或模式识别的领域。其处理不同长度和速度序列的灵活性使其成为多种应用的理想选择。以下是 DTW 应用的一些关键领域：

语音识别

DTW 在语音识别系统中被广泛用于比较口语单词或短语。由于人们说话的速度可能不同或停顿不同，DTW 可以有效地对齐这些语音模式以识别相似的单词。通过规整时间轴，DTW 确保在时间变化的情况下也能准确地匹配单词。

示例：DTW 可以通过调整时间尺度来匹配快速说出的单词和较慢说出的单词，以对齐关键的语音元素。

手写识别

在手写识别系统中，DTW 有助于比较长度、速度或风格不同的手写文本风格。通过对齐笔画或笔的运动，DTW 提高了字符和单词识别的准确性。

示例：DTW 可以对以不同速度书写的手写样本进行对齐，以识别相同的字符。

时间序列预测和分析

DTW 用于将历史时间序列数据与新模式进行比较，以检测趋势、异常或预测未来值。其对齐不同长度序列的能力使其非常适合金融市场分析、能源消耗趋势和天气模式预测。

示例：在金融领域，DTW 可以比较不同时期的股票价格走势，以识别历史趋势。

生物信息学与基因组学

在生物信息学中，DTW 被应用于对齐基因序列、蛋白质结构和生物标志物。由于生物数据通常在长度和结构上存在差异，DTW 可以有效地对齐这些序列以进行更深入的分析。

示例：DTW 有助于对齐可能存在插入、缺失或突变的 DNA 序列。

五、手势和运动识别

DTW 在运动跟踪和手势识别中是一个有价值的工具。它被用于游戏、医疗保健和体育分析等应用中的身体动作对齐。通过将运动数据与预定义的模式进行比较，DTW 可以识别特定的手势或动作。

示例：在健康应用中，DTW 可以将用户的运动动作与参考运动模式进行匹配，以评估表现。

音乐和音频分析

DTW 被应用于音乐检索、节拍跟踪和音频相似度检测。它对齐同一首歌曲的不同版本，从而确保同步，即使在速度或节奏上存在差异。

示例：DTW 可以将现场演唱会录音与录音室版本进行对齐，以比较旋律或检测时间错误。

签名验证

DTW 被用于生物识别系统，以比较手写签名进行身份验证。通过对齐签名过程的动态特征，如速度和压力，DTW 提高了签名验证的准确性。

示例：银行和安全系统经常使用 DTW 来检测伪造签名。

医疗保健和医学分析

DTW 被应用于分析医学时间序列数据，如心电图 (ECG) 和脑电图 (EEG) 信号。它有助于识别心律、大脑活动或其他生命体征中的异常。

示例：DTW 可以将患者的心跳模式与正常模式进行比较，以检测心律失常或其他心脏疾病。

动态时间规整 (DTW) 的优点和局限性

DTW 的优点

灵活的对齐

DTW 可以对齐具有不同长度、速度或采样率的时间序列数据。与欧几里得距离不同，DTW 会拉伸或压缩序列，以识别有意义的相似性，即使模式出现在不同的时间。

对时间失真具有鲁棒性

DTW 可以有效地处理时间变化，使其成为语音信号、股票价格或生物序列等速度波动的理想数据。

对噪声数据有效

即使数据包含噪声、小的失真或缺失值，DTW 仍然可以提供准确的对齐。通过专注于最小化累积距离，DTW 在不完善的情况下保持鲁棒性。

跨领域通用

DTW 广泛应用于语音识别、手势跟踪、生物信息学和金融分析等各个领域，使其成为时间序列分析的通用工具。

全局最优性

DTW 通过最小化累积距离来确保在序列之间找到最优的对齐路径，从而在复杂的数据场景中确保可靠的结果。

DTW 的局限性

计算复杂性

DTW 的时间复杂度为 O(m × n)，其中 m 和 n 是两个序列的长度。这使得它在计算上非常昂贵，尤其是对于长时序数据。

内存密集

由于 DTW 需要构建和存储完整的距离矩阵，因此需要大量的内存资源，这对于大型数据集可能效率不高。

对异常值敏感

尽管 DTW 可以处理一些噪声，但极端异常值可能会扭曲对齐路径，导致不正确的匹配。通常需要进行适当的数据预处理或异常值消除。

对齐偏差

如果不加以约束，DTW 也可能产生过度的规整，导致不切实际的对齐。诸如窗口化约束（例如，Sakoe-Chiba 带）之类的技术可以降低这种风险。

可解释性差

虽然 DTW 可以有效地找到最优对齐路径，但解释结果可能很困难。从规整路径中识别有意义的模式通常需要进一步的分析。

实时应用的缩放问题

由于其计算需求，DTW 可能难以满足实时处理任务，除非采用 FastDTW 等优化策略。

结论

动态时间规整是时间序列分析的强大方法，它能够在大规模具有不同时间特征的数据集中进行准确的模式识别。尽管计算复杂，DTW 仍然是多个领域的宝贵工具。FastDTW 和受限 DTW 等优化策略有助于缓解其计算上的缺点，使其能够用于实时应用。