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

距离指标

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

---

---

欧几里得距离

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

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

 图 — 欧几里得匹配

动态时间扭曲

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

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

 图 — 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动态时间规整算法的简单的步骤：

1. 首先肯定是已知两个或者多个序列，但是都是两个两个的比较，所以我们假设有两个序列A={a1,a2,a3,…,am}  B={b1,b2,b3,….,bn}，维度m>n
2. 然后用欧式距离计算出每序列的每两点之间的距离，D(ai,bj) 其中1≤i≤m，1≤j≤n

   画出下表：

3.  接下来就是根据上图将最短路径找出来。从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)的最短距离。
4. 接下来从最终的最短距离往回找到那条最佳的输出路径， 从D(a1,b1)到D(am,bn)。他们的总和就是就是所需要的DTW距离

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

R语言实现

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

创建序列数据

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

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

计算规整方式

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.