【视频】时间序列分类方法：动态时间规整算法DTW和R语言实现

动态时间扭曲算法何时、如何以及为什么可以有力地取代常见的欧几里得距离，以更好地对时间序列数据进行分类

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

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

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

图 — 移动识别示例

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

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

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

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

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

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

图 — 基于距离的方法

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

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

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

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

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

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

图 — 欧几里得匹配

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

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

图 — DTW 的语音识别应用

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

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

图 — 动态时间扭曲匹配

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

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

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

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

图 — 当地成本矩阵 C

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

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

必须满足一些条件：

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

以保留时间顺序。

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

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

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

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

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

图 — 最佳翘曲路径

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

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

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

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

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

它需要不同的步骤：

图 — 快速 DTW

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

动态时间规整（DTW,Dynamic time warping,动态时间归整/规整/弯曲）是一种衡量两个序列之间最佳排列的算法。线性序列数据如时间序列、音频、视频都可以用这种方法进行分析。DTW通过局部拉伸和压缩，找出两个数字序列数据的最佳匹配，同时也可以计算这些序列之间的距离。

动态时间规整算法，故名思议，就是把两个代表同一个类型的事物的不同长度序列进行时间上的“对齐”。比如DTW最常用的地方，语音识别中，同一个字母，由不同人发音，长短肯定不一样，把声音记录下来以后，它的信号肯定是很相似的，只是在时间上不太对整齐而已。所以我们需要用一个函数拉长或者缩短其中一个信号，使得它们之间的误差达到最小。

因此，动态时间规整要解决的问题就是：找到一条最优的规整路径 W = {\varpi _1},{\varpi _2}...{\varpi _k} W=ϖ1​,ϖ2​...ϖk​，其中 {w_k} = (i,j) wk​=(i,j)，即认为时间序列1的第i个点和时间序列2的第j个点是类似的。全部类似点的距离之和做为规整路径距离，用规整路径距离来衡量两个时间序列的类似性。规整路径距离越小，类似度越高。

下面我们来总结一下DTW动态时间规整算法的简单的步骤：

   画出下表：

【注】如果不回溯路径，直接在第3步的时候将左上角三个节点到下一个节点最短的点作为最优路径节点，就是贪婪算法了。DTW是先计算起点到终点的最小值，然后从这个最小值回溯回去看看这个最小值都经过了哪些节点。

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

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

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

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

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

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

用密度作图

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

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

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

最受欢迎的见解

1.在python中使用lstm和pytorch进行时间序列预测

2.python中利用长短期记忆模型lstm进行时间序列预测分析

3.使用r语言进行时间序列（arima，指数平滑）分析

4.r语言多元copula-garch-模型时间序列预测

5.r语言copulas和金融时间序列案例

6.使用r语言随机波动模型sv处理时间序列中的随机波动

7.r语言时间序列tar阈值自回归模型

8.r语言k-shape时间序列聚类方法对股票价格时间序列聚类

9.python3用arima模型进行时间序列预测