原文链接：http://tecdat.cn/?p=30169
原文出处：拓端数据部落公众号
时间序列分类的动态时间扭曲
动态时间扭曲算法何时、如何以及为什么可以有力地取代常见的欧几里得距离，以更好地对时间序列数据进行分类
使用机器学习算法对时间序列进行分类需要一定的熟悉程度。
时间序列分类（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）， 具有良好的次优解决方案。
动态时间规整（DTW,Dynamic time warping,动态时间归整/规整/弯曲）是一种衡量两个序列之间最佳排列的算法。线性序列数据如时间序列、音频、视频都可以用这种方法进行分析。DTW通过局部拉伸和压缩，找出两个数字序列数据的最佳匹配，同时也可以计算这些序列之间的距离。
DTW是干什么的？
动态时间规整算法，故名思议，就是把两个代表同一个类型的事物的不同长度序列进行时间上的“对齐”。比如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动态时间规整算法的简单的步骤：
- 首先肯定是已知两个或者多个序列，但是都是两个两个的比较，所以我们假设有两个序列A={a1,a2,a3,...,am} B={b1,b2,b3,....,bn}，维度m>n
- 然后用欧式距离计算出每序列的每两点之间的距离，D(ai,bj) 其中1≤i≤m，1≤j≤n
画出下表：
- 接下来就是根据上图将最短路径找出来。从D(a1,a2)沿着某条路径到达D(am,bn)。找路径满足：假如当前节点是D(ai,bj)，那么下一个节点必须是在D(i 1,j)，D(i,j 1)，D(i 1,j 1)之间选择，并且路径必须是最短的。计算的时候是按照动态规划的思想计算，也就是说在计算到达第(i,j)个节点的最短路径时候，考虑的是左上角也即第(i-1,j)、(i-1,j-1)、(i,j-1)这三个点到(i,j)的最短距离。
- 接下来从最终的最短距离往回找到那条最佳的输出路径， 从D(a1,b1)到D(am,bn)。他们的总和就是就是所需要的DTW距离
【注】如果不回溯路径，直接在第3步的时候将左上角三个节点到下一个节点最短的点作为最优路径节点，就是贪婪算法了。DTW是先计算起点到终点的最小值，然后从这个最小值回溯回去看看这个最小值都经过了哪些节点。
R语言实现
在这篇文章中，我们将学习如何找到两个数字序列数据的排列。
创建序列数据
首先，我们生成序列数据，并在一个图中将其可视化。
代码语言：javascript复制plot(a, type = "l")
lines(b, col = "blue")
计算规整方式
dtw()函数计算出一个最佳规整方式。
代码语言：javascript复制align(a, b)返回以下项目。你可以参考str()函数来了解更多信息。
现在，我们可以绘制组合。
用双向的方法作图
动态时间规整结果的绘图：点比较
显示查询和参考时间序列以及它们的排列方式，进行可视化检查。
代码语言：javascript复制Plot(align)
用密度作图
显示叠加了规整路径的累积成本密度 。
该图是基于累积成本矩阵的。它将最优路径显示为全局成本密度图中的 "山脊"。
代码语言：javascript复制PlotDensity(align)
小结
总而言之, DTW是一种非常有用的计算序列最小距离的方法, 不论是在语音序列匹配, 股市交易曲线匹配, 还是DNA碱基序列匹配等等场景, 都有其大展身手的地方. 它的最大特点是在匹配时允许时间上的伸缩, 因此可以更好的在一堆序列集合中找到最佳匹配的序列.
- Eamonn Keogh, Chotirat Ann Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems, 2005.
最受欢迎的见解
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模型进行时间序列预测
