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

动静工夫规整（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.