原文链接：http://tecdat.cn/?p=22945

动态时间扭曲算法何时、如何以及为什么可以有力地取代常见的欧几里得距离，以更好地对时间序列数据进行分类（点击文末“阅读原文”获取完整代码数据）。

时间序列分类的动态时间扭曲

使用机器学习算法对时间序列进行分类需要一定的熟悉程度。

时间序列分类（TSC）任务通常由监督算法解决，它旨在创建分类器，将输入时间序列映射到描述时间序列本身的一个或多个特征的离散变量（类）中。

可以在语音识别或手势和运动识别中找到时序分类任务的有趣示例。

图 — 移动识别示例

用于其他类型的数据（例如表格数据）的标准分类算法不能直接应用，因为它们将每个样本与其他样本分开处理。

对于时间序列，不能忽略数据的时间顺序，因此，不能考虑时间序列的每个样本而考虑其他样本，但必须保留时间顺序。

出于这个原因，在文献中，有几种类型的时间序列分类技术，将在下一段中简要解释。

时间序列分类方法

作为TSC不同类型方法的简要概述。

• 基于区间的方法：从不同的区间中提取时间序列的特征和信息，并将标准分类器应用于特征本身。算法的一个示例是时序森林分类器。
  
• 基于字典 的方法：将时间序列的特征转换为代表类的单词。标准分类器应用于提取单词的分布。算法的一个例子是模式袋。
  
• 基于频率的方法：在频谱水平上提取时间序列的特征，通过频率分析和连续的标准分类器。算法的一个示例是随机间隔频谱集成。
  
• 基于形状的方法：形状是代表类的时间序列的子序列。提取时间序列中k个最具特征的形状，然后使用标准分类器。算法的一个示例是 Shapelet 变换分类器。
  
• 集成方法：对于一般问题非常有竞争力，它们结合了几个估计器，例如HIVE-COTE算法。

基于距离的方法

在本文中，我们将重点介绍基于距离的方法。

它是一种将距离度量与分类器混合以确定类成员的非参数方法。分类器通常是 k 最近邻 （KNN）  算法，用于了解要标记的时间序列是否与训练数据集中的某些时间序列相似。根据邻域，最近的类或最近类的聚合与所分析的时间序列相关联。动态时间扭曲（DTW）是基于距离的方法的一个示例。

图  — 基于距离的方法

距离指标

在时间序列分类中，我们需要计算两个序列之间的距离，同时牢记每个序列内样本之间的时间关系和依赖性。选择正确的指标是这种方法的基础。

欧几里得距离

让我们开始考虑常见的欧几里得距离。

鉴于时间序列分类，欧几里得距离是不合适的，因为即使它保留了时间顺序，它也以逐点的方式测量距离。实际上，与两个时间序列的欧几里得距离的相似性是通过考虑它们的振幅来计算的，而与相移、时移和失真无关。

以图中的示例为例。我们有树时间序列：ts1、ts2 和 ts3。我们希望检测两条正弦曲线彼此相似，因为它们具有相同的形状和上下趋势，即使它们的相位和频率略有不同。但是，如果我们计算欧几里得指标，直线 ts3 的结果更接近 ts1。

图 — 要比较的时间序列示例

之所以出现这种现象，是因为欧几里得距离正在比较曲线的振幅，而不允许任何时间拉伸。

图 — 欧几里得匹配

动态时间扭曲

引入了动态时间扭曲以避免欧几里得距离的问题。

从历史上看，它是为语音识别而引入的。如图所示，以不同的速度重复相同的句子，有必要将时间序列与相同的单词相关联，从而管理不同的速度。

图 — DTW 的语音识别应用

DTW 允许您通过确定时间序列之间的最佳对齐方式并最大程度地减少时间失真和偏移的影响来衡量时间序列之间的相似性。

不同相的相似形状，及时匹配弹性翘曲。

图 — 动态时间扭曲匹配

算法

让我们考虑两个时间序列 X = （x₁， x₂， ...， xn） 和 Y = （y₁， y₂， ...， ym）， 在等距时间点采样，长度相等或不同。

我们的目标是找到对齐时间序列的最小距离。

图 — 要对齐的时间序列示例

定义局部成本矩阵，该矩阵将被最小化以找到最佳对齐方式。成本矩阵 C 定义为所有时间序列点的成对距离：

图 — 当地成本矩阵 C

目的是通过遵循成本最低的路线，在局部成本矩阵上找到对齐时间序列的翘曲路径。

翘曲路径 p 是局部成本矩阵上的点序列，因此是两个时间序列上的几个点序列：

必须满足一些条件：

• 边界条件：
  

翘曲路径的起点和终点必须是序列的第一个和最后一个点。

• 单调性条件：
  

以保留时间顺序。

• 步长条件：
  

以限制跳跃和时间偏移，同时对齐序列。

每个翘曲路径都有相关的成本：

• 与翘曲路径 p 相关的成本函数
  

图 — 翘曲路径示例（非最佳）

目的是找到最佳的翘曲路径：

DTW 通过递归实现解决，为此可以找到成本最低的翘曲路径：

图 — 最佳翘曲路径

找到最佳翘曲路径后，将计算出相关的最优成本，并将其用作 DTW 距离。

递归实现达到最优，但计算成本为 O（NM）， 其中 N 和 M 是两个时间序列的长度。

k-最近邻

回到对感兴趣的时间序列进行分类的原始问题，距离度量可以与k-最近邻（k-nn）算法耦合。这意味着您可以计算时间序列到训练数据集中所有其他时间序列的 DTW 距离。然后，如果您正在考虑使用 1-nn 方法，则可以将最近邻的类与时间序列相关联，或者，同样，您可以将 k 最近类中最常用的类与 k-nn 方法相关联。

通过这种方式，您已经达到了为时间序列分配类的目标，该方法考虑了时间序列的时移。

传统 DTW 的替代方法可加快速度

快速 DTW

提出了一种多级方法来加快FastDTW算法中的算法速度。

它需要不同的步骤：

• 粗化： 将时间序列缩小为较粗的时间序列。这通过对相邻点对求平均值来减小时间序列的大小。
  
• 投影： 找到最小距离的翘曲路径，用作更高分辨率翘曲路径的初始猜测。
  
• 优雅： 通过局部调整将翘曲路径从较低分辨率细化到较高分辨率。此步骤在投影路径的邻域中查找最佳翘曲路径，半径 r 参数控制邻域的大小。
  

图 — 快速 DTW

FastDTW允许快速分辨率，复杂度为O（Nr）， 具有良好的次优解决方案。

R语言实现

在这篇文章中，我们将学习如何找到两个数字序列数据的排列。

创建序列数据

首先，我们生成序列数据，并在一个图中将其可视化。

plot(a, type = "l")
lines(b, col = "blue")

点击标题查阅往期内容

Python用KShape对时间序列进行聚类和肘方法确定最优聚类数k可视化

01

02

03

04

计算规整方式

dtw()函数计算出一个最佳规整方式。

align(a, b)

返回以下项目。你可以参考str()函数来了解更多信息。

现在，我们可以绘制组合。

用双向的方法作图

动态时间规整结果的绘图：点比较

显示查询和参考时间序列以及它们的排列方式，进行可视化检查。

Plot(align)

用密度作图

显示叠加了规整路径的累积成本密度 。

该图是基于累积成本矩阵的。它将最优路径显示为全局成本密度图中的 "山脊"。

PlotDensity(align)

小结

总而言之, DTW是一种非常有用的计算序列最小距离的方法, 不论是在语音序列匹配, 股市交易曲线匹配, 还是DNA碱基序列匹配等等场景, 都有其大展身手的地方. 它的最大特点是在匹配时允许时间上的伸缩, 因此可以更好的在一堆序列集合中找到最佳匹配的序列.

1. Eamonn Keogh, Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, 2005.