动态时间规整（DTW）算法介绍

导读：通常我们比较两个序列的相似性，可以通过直接点对点计算距离的方式实现。但是当两个序列长度不相等时，原有的方法就变得不适用，比如两个人对同一个词语发音不同，导致阅读同一词语的时长不同，因此就要对序列进行延伸或压缩才能比较两段语音是否阅读的是同一个词语。本期介绍的DTW就是解决这类问题的常用算法。

1

基本概念

动态时间规整（Dynamic Time Warping，DTW）是按照距离最近原则，构建两个长度不同的序列元素的对应关系，评估两个序列的相似性。在构建两个序列元素对应关系时，需要对序列进行延伸或压缩。以下图为例，两条黑色实线代表两个语音序列，虚线代表两个序列元素的对应关系，可以看出存在某一元素与多个元素存在对应关系，如果换成一个个离散的点表示的话，就是对该点进行了拉伸处理。

DTW算法最早用于语音识别问题，如：语言学习跟读软件中，检测发音是否标准，后来也在传感器动作识别、生物信息比对等方面有所应用。

2

计算过程

DTW的计算过程主要分为构建累积距离矩阵和寻找最短路径两部分，类似于动态规划的过程。现在假设x序列为{3，4，5}，y序列为{1,4,2,6}，相似度计算采用欧式距离，即d=abs（a-b），我们以此为例介绍DTW算法的计算过程。

step 1 : 构建累积距离矩阵

首先我们形成一个3*4的网格，其中行对应X序列，列对应Y序列，每个网格内元素代表对应点的累积距离。

从左下角开始计算，左下角取值直接套用距离计算公式：3-1=2。然后网格第一列从下往上开始，除了要计算对应点的距离外，还需加上下方相邻网格的距离，进而实现距离的累积。同理，网格第一行从左至右，除了计算对应点距离之外，还需加上左方相邻网格的距离。

其余的网格，除要计算对应点的距离外，还需找到左下方三个点的最小值进行相加。

以此类推，得到最终的累积距离矩阵。

step 2 : 寻找最短路径

从右上角开始，寻找左下方三个点中距离最小的点，以此类推，通过回溯的方式找到最短路径，得到最短距离。注意，从右上角开始至少找到最短路径的便捷方法，路径的起点依旧为左下角的点。

在寻找最短路径的时候，有三个限制条件：

• 边界条件：起点和终点分别为左下角和右上角。比如：语速不同，读一个词语的开始和结束应该相同。
• 连续性：只能和相邻的点匹配，不能跨过某个点进行匹配。
• 单调性：路径上的点随着时间单调进行，不能往左回退。

因此每个点的下一步路径，只有可能存在于右上方的三个点当中。

3

Python实现

选假设x为参照序列，比较y、z哪一个序列与x最为相似。

import numpy as np
x = np.array([2, 0, 1, 1, 2, 4, 2, 1, 2, 0]).reshape(-1, 1)
y = np.array([1, 1, 2, 4, 2, 1, 2, 0]).reshape(-1, 1)
z = np.array([3, 2, 2, 4, 2, 1]).reshape(-1, 1)

from dtw import dtw
euclidean_norm = lambda x, y: np.abs(x - y)#指定距离计算公式
#得到累积距离，两两距离，dp矩阵，最佳路径
d1, cost_matrix1, acc_cost_matrix1, path1 = dtw(x, y, dist=euclidean_norm) 
d2, cost_matrix2, acc_cost_matrix2, path2 = dtw(x, z, dist=euclidean_norm) 
print("d1=",d1,"d2=",d2)

import matplotlib.pyplot as plt
#轨迹线打印
plt.imshow(acc_cost_matrix1.T, origin='lower', cmap='gray', interpolation='nearest')
plt.plot(path1[0], path1[1], 'w')
plt.show()

根据计算结果，y与x的距离比z与x的距离更近，因此y相对与x更为相似。具体距离及轨迹线图如下：

参考内容：

1.http://t.zoukankan.com/wangleBlogs-p-10444892.html

2.https://blog.csdn.net/gdp12315_gu/article/details/55667483

3.https://blog.csdn.net/weixin_39910711/article/details/108178110

4.Eamonn J. Keogh, Derivative Dynamic Time Warping

5.DTW（动态时间规整）算法原理与应用