动态时间规整算法-音乐数据分析效果与应用

动态时间规整算法简称DTW算法，是一种可以计算两个不同长度的时间序列并找到最优匹配路径的匹配算法。这种方法可以判断两个时间序列的相似性，将待识别序列与模板库中的样本序列进行动态规划，其中一个时间序列可以通过拉伸、收缩与扭曲时间轴，达到两个时间序列时间长度一致的效果。该算法因有较强的适应性，鲁棒性较强，被广泛使用，在语音识别、数据挖掘、手势识别、机器人技术和医学上有较多应用。

图3-2是两个水平方向相似的时间序列，每条竖线将一个时间序列的点连接到另外一个时间序列上。这些竖线有相似的值，所以选取值差异较大的点，将对应的点连线称为经线路径。若图中的两个时间序列是相同的，那么所有的直线都是垂直的直线，因为没有斜线，所有的点都一一对应。DTW算法能在两个时间序列之间找到最优对齐路径。

图3-2　两个时间序列的规整路径

通常，为了确定两个时间序列的相似性，需要定义、计算和判别序列间的欧几里得距离，欧几里得距离是一个有效测量两点间真实距离的方法，特别适用于一些时间空间域。

给出两个时间序列X和Y，时间序列表示如下，长度为|x|和|y|。

X=x1，x2，…，xi，…，x|X|

（3-1）

Y=y1，y2，…，yi，…，y|Y|

（3-2）

规整路径为W：

W=w1，w2，…，wk，max（|X|，|Y|）≤k≤|X|+|Y|

（3-3）

当规整路径的长度为K时，规整路径的第k个元素是wk=（i，j）。i为时间序列X的序数，j是时间序列Y的序数。规整路径序列在每个时间序列的最开始都是wi=（1，1），并在两个时间序列的末尾结束。wk在规整路径上也有约束，i和j在路径上单调递增，图3-2中的路径上的线是不重叠的。用公式表示为：

wk=（i，j），wk+1=（i′，j′）；i＜i′，j＜j′

（3-4）

一条最优规整路径是其中一条最小距离的经线路径。任意一条经线路径的距离为：

Dist（W）的规整路径距离表示W和Dist（Wki，Wkj）两个数据点（一个来自X，一个来自Y）中的第k个元素之间的距离。

动态时间规划算法可以求出两个时间序列之间寻找最小距离的规整路径。此算法先解决子问题（时间序列的小部分），通过解决小问题，结合为大问题，直到为整个时间序列中找到最优解决方案。

一个二维的|X||Y|矩阵D，是由两个时间序列X=x1，……，xi和Y=y1，……，yj构成，需求出最小的D（i，j）。x轴代表了X序列的时间，y轴代表了Y序列的时间。图3-3展示了一个矩阵和最小距离变形路径，即从D（1，1）到D（|X|，|Y|）；其中|x|=16，|y|=16，经线路径为……W={（1，1），（2，1），（15，15），（16，16）}。如果经线路径经过矩阵的D（i，j），则时间序列X的第i点被对应到时间序列Y的j点上，一个时间序列上的单点可能映射到另一个时间序列上的几个点上，因为两个时间序列可能不等长。(www.xing528.com)

要找到最小距离的经线路径，先计算出矩阵中的每个小单元格中的欧式距离值，再使用经典的动态规划算法，从原点出发，沿着i和j轴逐个增加，或者保持不变，最优路径在矩阵的单元格D（i-1，j），D（i，j-1）和D（i-1，j-1）中进行选择，这样矩阵的当前单元值为：W={（1，1），（2，1），（15，15），（16，16）}

D（i，j）=Dist（i，j）+min[D（i，j−1），D（i−1，j），D（i−1，j−1）]

（3-6）

D（i，j）的经线路径必须经过这三个小单元格中的其中一个，如图3-4所示，图中的a，b对应公式（3-6）中的D，每个点代表一个单元格，三个点的对应公式（3-6）。

在一个时序内矩阵中填充一列是从下到上，从左到右，如图3-5所示。

图3-3　两个时间序列组成的最小距离偏差矩阵

图3-4　矩阵内i，j节点

图3-5　矩阵填充顺序

在整个矩阵填满后，可以从D（x，y）中找到一条经线路径，顺序是从前到后，即从D（x，y）到D（1，1）。通过计算单元格向左、向下和对角线的方向，选择这三个相邻的单元格的最小值，添加到D（i，j）中，并从这个单元格继续搜索。当到达D（1，1）时，搜索结束。

在|x，y|矩阵中的每个单元格填满后，才能找到一个最优解决方案。矩阵大小与时间序列大小一致，显然时间复杂度为O（N2）。在时间序列的区域中，如果约束较好，那么最优的经线路径预计将接近线性经线，并以相对直线的方式通过矩阵。对于许多实际应用而言，使用约束会比不受约束的DTW带来更好的分类精度。使用约束过后的DTW算法例子见图3-6。

图3-6　通过数据约束加速DTW

使用DTW算法需要满足以下两个条件：

（1）严格的约束限制—一个相对严格的近似线性规整路径。

（2）短时间序列—所有时间序列都足够短，可以快速执行DTW算法。

下面给出DTW的伪代码，即计算出公式（3-6）的距离值。

再给出在Excel表格中，计算公式3-6的方法：

INDIRECT表示引用相应的单元格，D4表示当前将计算的单元格，"C"&COLUMN（D4）-1表示D4的上一个单元格，就是D3，"R"&ROW（D4）-1表示D4的左边一个单元格，就是C4，"R"&ROW（D4）-1&"C"&COLUMN（D4）-1，）表示D4的左上一个单元格，就是C3，POWER表示乘方。