拓端tecdat|R语言DTW(Dynamic Time Warping) 动态时间规整算法分析序列数据和可视化

原文链接：/?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是先计算起点到终点的最小值，然后从这个最小值回溯回去看看这个最小值都经过了哪些节点。