衡量时间序列之间的距离:动态时间扭曲
分享：
|
杰西卡梁 商业分析学科 悉尼大学 |
|
罗伯特詹姆斯 财政纪律 悉尼大学 |
许多重要现象都被记录为时间序列数据，例如，音频信号，心跳监视器的心电图信号，金融资产的回报，甚至从遥远的恒星发出的光的强度。在许多应用中，测量不同时间序列样本之间的相似性(距离)是很有意义的。例如，语音识别系统将一个语音单词的音频信号与一个模板信号数据库进行比较。另一个例子是心跳监测系统，它将实时模式与已知心脏状况的心电图模式数据库进行比较。
在测量时间序列序列之间的相似性时，重要的是考虑对准路径，即两次序列中观察之间的映射。欧几里德距离是两个向量之间的广泛使用的相似性，其根据定义，在任何两个时间序列样本中的相应观察之间强制执行锁定步骤一对一的映射。然而，当沿着时轴的轻微错位（例如由于仪器测量误差）之间存在两个时间序列时，通过欧几里德距离测量的两个时间序列之间的相似性可以严重扭曲。因此，如果未首先纠正未对准，则时间序列数据挖掘任务（如分类和群集）将分解。图1展示了属于同一类明星的两个星光曲线，但在时间内未对准1。图1的第二面板示出了两次序列之间的锁定步骤欧几里德对准路径。由于我们知道这两个时间序列属于同一类星，很明显，欧几里德距离不提供这些未对准时间序列的直观相似性。
图1:同一颗恒星的两条星光曲线的欧几里得和DTW比对。 |
为了在这些情况下准确测量相似性，我们必须考虑两个给定的时间序列样本之间的潜在未对准。动态时间翘曲（DTW）为这种未对准问题提供了一个可能的解决方案。DTW缩小或拉伸一个时间序列的区域，以便最适合另一个。换句话说，DTW允许在观察结果之间进行非线性对准，因此不正常到错位数据。图1的第三面板绘制了DTW构造的对准路径。使用此对齐路径，图1的最终面板绘制了同步时间序列。现在清楚的是星光曲线属于同一类恒星。
为了构造DTW对齐路径，我们首先建立一个代价矩阵，该代价矩阵包含两个时间序列中观测值之间所有可能的成对欧氏距离的穷举组合。相邻的对齐路径可以通过这个代价矩阵来跟踪，在任意给定的对齐路径下，两个时间序列之间的距离是路径上的距离之和。DTW的目标是构建成本最小的对齐路径。通过使用递归方程找到这条最小代价路径，该方程将当前观测的累积代价定义为当前代价加上与前一个观测相对应的相邻单元的最小代价。通常，我们计算的最佳对齐路径受一个约束，即翘曲窗口宽度约束，该约束限制翘曲路径位于成本矩阵主对角线附近的区域。直观地说，这种约束通过禁止一个观察结果与其他时间序列中的许多观察结果相匹配的情况来确保现实的对齐，这种情况被称为病理扭曲。
图2与先前绘制的两个星光曲线的DTW对准路径（实心白线）一起绘制成本矩阵的示例。沿成本矩阵的对角线的虚线对应于欧几里德对准路径。因此，欧几里德对准路径是DTW对准路径的特殊情况。当DTW对准路径高于（下方）对角线（缩小）时间序列x匹配时间序列y。因此，DTW通常被称为弹性距离测量。成本矩阵表明DTW对准路径是阻力最小的路径。成本矩阵对角线周围的虚线表示翘曲窗口宽度约束设置为时间序列长度的20％的值。在实践中，可以使用交叉验证选择在该约束中使用的最佳值[1]。
图2:两条星光曲线的代价矩阵和DTW对齐路径 |
DTW中最多增长的应用之一是最近邻居算法中的距离测量。对于给定的查询时间序列，用于从参考时间序列的数据库找到最佳匹配。然而，使用DTW距离的最近邻南搜索的计算成本是相当大的。在实践中，K-Collect邻居DTW算法应始终使用较低限制和早期的放弃技术来减少所需的DTW计算的数量。下限是计算比DTW距离更快的函数，而是非常近似于两个时间序列之间的实际DTW距离。下限用于有效地修剪最近的邻居候选者，并以计算复杂性的级联顺序实现。文献中开发的三个最常见的下界是[7,3]和[4]。还可以指定早期的放弃条件，如果沿着最佳对准路径的累积距离，可以停止电流DTW计算，使得参考序列不能是最接近的邻居[7]。这些技术允许DTW应用于真正的大规模数据集。除了最近的邻居应用外，还可以使用DTW [6]来执行时间序列聚类。 For example, STRAVA has demonstrated how DTW averaging techniques in the domain of time series clustering can fix sequences of location data that have been misaligned by GPS sensor noise. It is also possible to generalize DTW for use with multivariate time series sequences [8].
动态时间扭曲已被证明在大量应用程序域中执行得非常好，特别是考虑到它的相对简单性[1]时。因此，DTW在过去的二十年中已经成为最重要的时间序列数据挖掘技术之一。时间序列分类的最新趋势已转向使用k -最近邻DTW作为关键算法的集成模型[见5)。此外，[2]最近将DTW表述为一个经典的最优控制问题。这为进一步研究通过扩展优化公式分析信号的新方法开辟了道路。
总之，DTW是一种多功能工具，跨越许多科学领域的成功。可以通过应用DTW以富有想象力的新方式来解决许多令人兴奋的时间序列数据挖掘问题。
1星光曲线数据可在https://www.cs.ucr.edu/%7eeamonn/time_series_data_2018/
参考：
- Dau, H. A.， Silva, D. F.， Petitjean, F.， Forestier, G.， Bagnall, A.， Mueen, A.和Keogh, E.(2018)。为时间序列数据挖掘应用优化动态时间扭曲的窗口宽度。数据挖掘和知识发现，32(4): 1074 - 1120。
- Deriso，D.和Boyd，S。（2019）。动态时间翘曲的一般优化框架。Arxiv预印迹arxiv：1905.12893。
- Keogh E.和Ratanamahatana C. A.(2005)。动态时间扭曲的精确索引。知识和信息系统，7（3）：358-386。
- Lemire，D。（2009）。更快地检索双通过动态时翘曲的下限。模式识别42(9): 2169 - 2180。
- 线，J.，Taylor，S.和Bagnall，A.（2018）。随着Hive-Cote的时间序列分类：基于转换的合奏的分层投票集体。ACM交易来自数据的知识发现，12（5）。
- Petitjean，F.，Ketterlin，A.和Gançarski，P.（2011）。用于动态时间扭曲的全局平均方法，应用程序到群集。模式识别，44（3）：678-693。
- Rakthanmanon, T.， Campana, B.， Mueen, A.， Batista, G.， Westover, B.， Zhu, Q.， Zakaria, J.， and Keogh, E.(2013)。大数据时间序列寻址:在动态时间扭曲下挖掘万亿时间序列子序列。美国计算机学会《从数据中发现知识汇》，7（3）：1-31。
- Shokoohi-yekta，M.，Hu，B.，Jin，H.，Wang，J。和Keogh，E。（2017）。将DTW概括为多维案例需要自适应方法。数据挖掘和知识发现,(1): 31日至31日。