动态时间规整

动态时间规整 (DTW) 是一套有效的规则，在大多数情况下用于衡量时间序列之间的相似性，这些时间序列在时间和速度上可能存在差异。DTW 最初是在语音识别的背景下开发的，此后由于其在比较时间序列数据方面的鲁棒性，已广泛应用于生物信息学、数据挖掘和经济评估等领域。

在本文中，我们将探讨 DTW 是什么，它的工作机制、应用、优点、局限性以及它与其他相似性度量的区别。

什么是动态时间规整？

DTW 是一种算法，用于找到两个时间序列之间的最佳对齐。由于存在不同的时间扭曲，这些序列在速度、长度或对齐方式上可能存在差异。与欧几里得距离等传统距离度量不同，后者可以测量时间上对应点之间的差异，DTW 允许“扭曲”时间轴。这样，即使相似序列不同步，也可以对齐。

我们为什么需要 DTW？

我们需要动态时间规整 (DTW) 来分析速度或时间可能不同的时间序列数据。在许多现实情况中，事件不会在完全相同的时间或以相同的速度发生，这使得使用通用距离度量来衡量序列之间的相似性变得困难。

例如，考虑

• 语音识别：在比较以不同速度发音的同一短语的音频录音时，传统的距离度量将无法正确捕捉相似性，因为它们假定相似的声音在相同的时间发生。然而，DTW 会“扭曲”时间轴以匹配相似的声音，即使它们在每次录音中发生的时间不同。
• 手势和运动分析：在机器人技术和体育等领域，DTW 用于分析速度或风格可能不同的动作。例如，两个人可以以不同的速度执行相同的舞蹈动作。DTW 通过拉伸或压缩时间轴来对齐这些序列，以找到最相似的点，从而可以进行有意义的比较。
• 生物数据分析：DTW 用于比较 DNA、蛋白质序列或其他生物数据，其中模式可能相似但时间上不完全对齐。
• 金融分析：在股市数据中，价格趋势可能发生在不同的时间范围内。DTW 允许对齐这些趋势，即使一个股票的价格变化比另一个慢，也能识别出相似的模式。

在这些情况下，DTW 使我们能够处理非线性时间扭曲，提供一种灵活的相似性度量方法。这使得 DTW 在时间序列数据在时间和持续时间上存在差异的领域至关重要，使我们能够在不同背景下有效地比较模式。

DTW 的工作原理

动态时间规整 (DTW) 的工作原理是找到时间序列之间的最佳对齐，即使它们在速度或时间上存在差异。以下是 DTW 工作原理的分步说明：

1. 计算成本矩阵

为了比较序列，DTW 首先创建一个“成本矩阵”，其中每个单元格代表一个序列中的一个点与另一个序列中的一个点之间的差异。例如，给定序列 ? = (?1, ?2,...,) 和 ? = (?1,?2,...,??)，每个单元格的成本计算为平方差：(?i−?j)2。此矩阵捕获序列中所有点之间的成对差异。

2. 定义最佳规整路径

规整路径是矩阵中的一系列单元格，代表两个序列之间的最佳对齐，从而最小化总成本。该路径从左下角开始（对齐每个序列的开头），并在右上角结束（对齐两个序列的末尾）。

3. 动态规划

DTW 使用动态规划来寻找具有最低累积成本的路径，通过考虑三种可能的移动：对角线（对齐两个序列）、垂直（拉伸序列 X）或水平（拉伸序列 Y）。在每个单元格处，累积成本计算为

(i,j) = cost(i,j) + min(D(i - 1, j), D(i , j - 1), D(i - 1, j - 1))

此计算一直进行，直到填满矩阵，使 DTW 能够通过最小化沿该路径的总成本来识别最高效的路径。

4. 提取最佳路径

在计算完成本矩阵后，DTW 从矩阵的右上角回溯到左下角，以识别出确切的规整路径。这条路径显示了两个序列如何对齐，即使它们在速度或时间上存在差异。

5. 归一化

为了比较特定序列对之间的相似性，DTW 可以通过路径长度来归一化沿路径的累积距离，这有助于使不同长度的序列之间的比较更加一致。

DTW 的示例用法

想象两个人以不同的速度走同一条路。传统的距离度量可能无法识别它们的相似性，因为事件发生在不同的时间。DTW 会拉伸或压缩一个序列相对于另一个序列，对齐它们路径上的相似部分，并在存在时间差异的情况下进行有意义的比较。

DTW 的应用

动态时间规整 (DTW) 在分析和比较时间序列数据的领域有多种应用，尤其是在事件的时间或速度可变的情况下。以下是一些关键应用：

1. 语音和音频识别

• 应用：DTW 最初是为语音识别而开发的，它能够对齐音频模式以识别单词，即使它们以不同的速度发音。
• 用例：通过将录制的语音与存储的模板进行比较，DTW 能够有效地匹配单词，而不管说话者的语速如何，从而提高了语音识别系统的准确性。

2. 手写和签名识别

• 应用：在手写识别中，DTW 可以匹配手写字符或单词，它们的长度、形状或书写速度可能各不相同。
• 用例：对于签名验证，DTW 会随时间对齐笔的轨迹，通过考虑一个人书写中的自然变化，可以更轻松地进行签名身份验证。

3. 生物信息学和基因组学

• 应用：在生物信息学中，DTW 比较 DNA、RNA 或蛋白质序列，这些序列在时间和长度上可能存在差异，从而能够在生物数据中进行模式匹配。
• 用例：DTW 有助于在不同生物或实验中识别相似的基因表达模式，即使序列长度不同或略有错位。

4. 手势和运动识别

• 应用：DTW 在各种应用中用于从时间序列数据识别手势，例如手语翻译、人机交互或体育表现分析。
• 用例：对于手语，DTW 会对齐手势中的运动模式，并考虑用户之间速度或风格的差异，从而实现准确的手势识别。

5. 金融和股市分析

• 应用：DTW 有助于分析金融时间序列数据，例如股票价格，其中模式可能跨越不同的时间范围。
• 用例：通过匹配历史和实时股票数据中的模式，DTW 可用于识别相似的趋势，例如价格波动，即使这些趋势随时间以不同的速度发生。

6. 健康监测和医疗数据分析

• 应用：DTW 用于分析医疗时间序列数据，例如心率、ECG 或 EEG 信号，这些信号可能因患者而异。
• 用例：DTW 通过将这些模式与已知模板对齐，有助于检测预示健康状况（如心律失常）的医疗数据模式，即使存在个体差异。

DTW 的优点

1. 对非线性扭曲具有鲁棒性：DTW 可以处理时间上的非线性变化，使其成为事件或运动可能以不同速度发生的应用程序的理想选择。
2. 灵活性：DTW 不需要序列具有相同的长度，这使得模式匹配更加灵活。
3. 直观的对齐：DTW 直观地对齐序列，使其成为具有缓慢移动或变化的序列的理想选择。

DTW 的局限性

1. 计算复杂度：DTW 的时间和空间复杂度为 (? × ?)，其中 ? 和 ? 是两个序列的长度。对于非常大的时间序列，这可能在计算上成本高昂。FastDTW 等优化可以提供帮助，但复杂性仍然是一个问题。
2. 对噪声敏感：当序列具有高水平噪声时，DTW 可能会产生次优对齐。为了获得更好的结果，可能需要进行一些预处理或平滑处理。
3. 可解释性差：DTW 找到的规整路径有时可能缺乏可解释性，尤其是在处理复杂数据时。它可能在不保留整体结构的情况下捕捉模式中的相似性。

DTW 与其他相似性度量

在分析时间序列数据时，动态时间规整 (DTW) 通常与其他相似性度量（如欧几里得距离和相关性）进行比较。以下是 DTW 的独到之处，以及何时可能比其他度量更有效。

1. DTW 与欧几里得距离

• 欧几里得距离：这是衡量两个时间序列之间距离最简单的方法。它计算两个序列中对应元素的直接、逐点差异。然而，欧几里得距离假定两个序列在时间上是同步的，这意味着对应事件同时发生。
• DTW：与欧几里得距离不同，DTW 允许“扭曲”时间轴，从而能够对齐速度或时间不同的序列。当一个序列中的事件发生在不同于另一个序列的时间时，这非常有用。例如，如果一个人比另一个人说一个词更快，DTW 仍然可以匹配模式，而欧几里得距离会出错。
• 何时使用 DTW：DTW 更适用于具有时间扭曲或非线性时间变化模式的序列。欧几里得距离适用于同步序列，或在不需要考虑时间差异的情况下比较整体形状。

2. DTW 与皮尔逊相关系数

• 皮尔逊相关系数：它衡量两个时间序列之间的线性关系，寻找所有点上的恒定偏移。当您想了解两个序列的整体趋势是否相似时，皮尔逊相关系数很有用，而不管它们的绝对值如何。但是，它也假定序列在时间上是同步的。
• DTW：DTW 不需要序列线性相关或同步，这使其更加灵活。DTW 可以在序列形状随时间变化的情况下捕捉相似性，而相关性仅衡量线性特征方面的相似程度。
• 何时使用 DTW：DTW 更适合比较时间可能变化但形状和模式比线性趋势更重要的序列。当您需要一种快速的趋势相似性度量而无需对齐序列时，皮尔逊相关系数更有用。

3. DTW 与互相关

• 互相关：互相关通过随时间移动一个序列来寻找最佳对齐，以测量序列之间的相似性。它通常用于信号处理，在信号处理中，了解序列之间的最佳延迟以对齐相似模式至关重要。
• DTW：虽然互相关可以找到最佳的时间延迟进行对齐，但它仍然假定是线性偏移，这意味着对齐后，一个序列中的每个点仍然直接对应于另一个序列中的一个点。而 DTW 允许非线性变化，这意味着一个序列的部分可以拉伸或压缩以以非均匀的方式与另一个序列对齐。
• 何时使用 DTW：当序列之间存在可变速度或非线性时间偏移时，首选 DTW。互相关对于具有恒定延迟偏移的序列非常强大，但在时间扭曲复杂时会变得受限。

4. DTW 与余弦相似度

• 余弦相似度：这种相似性度量评估两个序列之间的角度，专注于它们的形状而不是它们的幅度。它通常用于文本和向量相似性，但也适用于时间序列。余弦相似度对整体形状和方向敏感，但它不考虑时间上的对齐。
• DTW：DTW 的优势在于找到最佳对齐，即使时间不同。如果序列基本同步，并且形状相似性比精确时间更重要，则余弦相似度效果很好。
• 何时使用 DTW：当精确的对齐和时间很重要时，DTW 更优；而当真实的对齐不是那么重要时，余弦相似度是识别相似形状的快速有效选择。

5. DTW 与汉明距离

• 汉明距离：此度量计算相同长度序列之间不同点的数量。它通常用于分类序列或二元数据，但对于具有时间变化的连续时间序列不太有用。
• DTW：DTW 允许沿时间轴进行连续变化，处理汉明距离无法处理的变化。汉明距离对于具有严格对齐要求的序列非常强大，但对于具有时间变化的连续数据缺乏灵活性。
• 何时使用 DTW：DTW 更适合具有时间变化模式的连续时间序列，而汉明距离适用于离散或分类数据中的精确序列匹配。

结论

动态时间规整是衡量时间序列数据相似性的宝贵工具，尤其是在存在非线性时间扭曲的应用中。虽然 DTW 的计算量很大且对噪声敏感，但它仍然是排列和比较可变长度和速度的时间序列的少数方法之一。它在语音识别、生物信息学、手势分析和金融领域的应用证明了其多功能性，并且优化技术不断使 DTW 成为大型数据集的可行选择。

通过理解和利用 DTW，数据科学家和工程师可以解锁复杂时间序列数据中的洞察力，从而在各个领域实现更好的模式识别和预测分析。