DDTW微分动态时间规整算法作者：郑培微分动态时间规整（DDTW）是对动态时间规整（DTW）的改进。为了缓解经典DTW算法带来的“奇点”问题，本文将从以下几个方面介绍DDTW算法。1.算法背景时间序列是几乎所有科学学科中无处不在的数据形式。时间序列的一个常见处理任务是将一个序列与另一个序列进行比较，以比较两个时间序列的相似性。在某些领域中，使用非常简单的距离度量就足够了，例如欧氏距离。然而，在大多数情况下，两个序列的整体构图形状大致相同，只是形状没有在x轴上对齐。（图1）为了找到这些序列之间的相似性，或者作为对它们进行平均之前的预处理步骤，我们必须“扭曲”一个（或两个）序列的时间轴以便更好地对齐。动态时间扭曲(DTW)是一种有效实现这种扭曲的技术。例如，如图A所示，实线和虚线是同一个词“pen”的两个语音波形（在y轴上分开画以便于观察）。可以看出它们整体的波形形状非常相似，只是在时间轴上没有对齐。假设一个序列中的第i个点与另一个序列中的第i个点对齐会产生“悲观差异”（pessimisticdissimilarity）。在图B中，DTW可以找到两个波形对齐的点，从而正确计算出它们之间的距离。(图1)因此，DTW显示出强大的能力，除了在数据挖掘中的应用(Keogh&Pazzani2000,Yiet.al.1998,Berndt&Clifford1994)，DTW也被用于手势识别(Gavrila&Davis1995))、机器人技术（Schmillet.al1999）、语音处理（Rabiner&Juang1993）、制造（Gollmer&Posten1995）和制药业（Caianiet.al1998）。2.经典动态时间规整算法假设我们有两个时间序列Q和C，长度分别为n和m，其中：为了对齐这两个序列，我们需要构造一个nxm的矩阵网格，矩阵元素(i,j)表示两点qi和cj之间的距离d(qi,cj)（即序列Q的每个点与C的每个点之间的相似度，距离越小，相似度越高。不管这里的顺序如何），一般使用欧几里得距离。每个矩阵元素(i,j)表示点qi和cj的对齐。使用此矩阵，我们能够计算两个时间序列之间的距离并显示扭曲路径(W)。由于“扭曲”时间轴的方式有很多种，我们可以得到很多条正则路径（W的公式如下），但我们的目标是找到最短的正则路径来判断两个时间序列“距离”的关系"是相似的，但是如何快速找到这条路径呢？我们发现动态规划（DynamicProgramming）可以为我们提供很大的便利。动态规划算法可以归结为通过这个网格中的几个网格点寻找一条路径，路径经过的网格点就是两个序列计算的对齐点。w的第i个元素定义了w=(i,j)的两个时间序列的映射。此外，正则化路径通常受到以下约束。1）边界条件：定义规则路径必须在矩阵的对角线元素开始和结束；2）连续性：这将规则路径中允许的步骤限制为相邻单元格（包括对角相邻单元格）；3)单调性：这迫使W中的点在时间上单调地进行。结合连续性和单调性约束，每个网格点的路径只有三个方向。例如路径已经过了格点(i,j)，那么下一个通过的格点只能是以下三种情况之一：(i+1,j),(i,j+1)或(i+1,j+1).综上所述，我们可以通过比较满足上述条件的所有正则路径来找到最短正则路径，但是DP为我们提供了一种更好的计算最短路径的方法。我们首先定义一个累积距离γ，累积距离γ(i,j)为当前网格点距离d(i,j)，即点qi和cj之间的欧式距离以及能到达该点的最小相邻元素点累积距离之和：通过动态规划算法，我们可以比较简单的得到最短的累积距离。3、动态时间规划的“奇异性”问题DTW算法最重要的特点是通过“扭曲”X轴来解释Y轴变量，从而达到对齐时间序列的目的。但是简单地通过Y轴上的变量值扭曲X轴可能会导致“不直观”的对齐，其中一个时间序列上的单个点映射到另一个时间序列的一部分。我们将这种不需要的行为称为“奇点”。已经提出了许多特别的方法来缓解这个奇点问题，所有这些方法的共同点是它们基本上限制了可能的“失真”。然而，它们产生的缺点是它们可能会阻止发现“正确的”“失真”。因此，我们引入DerivativeDTW来改善此类问题。4.导数动态时间扭曲算法上文提到，DTW算法根据Y轴变量的值粗略地（wildly）扭曲X轴，这样在Y轴变量时容易造成奇异性问题略有变化，如下图所示。时间序列最正确的对齐应该是特征之间的对应关系（featuretofeature），所以我们考虑在比DTW更高层次的特征选择，按照形状对齐。4.1、DDTW算法详解那么如何获取形状的信息，我们知道一阶导数可以反映斜率，而斜率是我们判断时间序列形状的一个指标，所以我们获取形状的信息通过考虑序列的一阶导数，所以我们的算法称为DerivativeDynamicTimeWarping(DDTW)。如前所述，我们构建了一个n×m矩阵，其中矩阵的(ith,jth)元素包含两点qi和cj之间的距离d(qi,cj)。DTW算法根据欧式距离计算两个时间序列对应点之间的距离，DDTW用qi和cj的估计导数差的平方代替DTW算法的距离公式。这里我们不考虑繁琐而精确的一阶导数计算公式，而是使用简单的导数估计方法来增加方法的泛化性。估计的导数公式如下：正如你所看到的，估计只是通过该点及其左邻域的直线的斜率与通过左右邻域的直线的斜率的平均值。值得注意的是，与仅使用两个数据点相比，此公式对异常值更稳健。还值得注意的是，该公式不包括第一个和最后一个点，而是使用第二个和倒数第二个点。下面是一个简单的例子。5.实验与结果为了验证DDTW对于奇点问题的改进，作者设计了两个实验从正反两方面进行论证。5.1Spuriouswarping作者选取了三组形状、噪声和自相关差异较大的数据集进行实验。这些序列高度相关但不相同，特别是它们包含小的（局部）差异。为了方便比较两种算法的区别，我们采用比较简单的K值（正则路径的长度）进行计算。K的取值范围为max(m,n)
