尽管 DTW 已经被成功应用到很多领域中,DTW 依然存在缺点:有时 DTW 会在对齐时产生不自然的扭曲/翘曲。如下图 4 所示: A 中实线、虚线所展示的是两条合成信号(均值、方差都相同),B 中展示的是自然的“feature to feature”的对应,而 C 中展示的则是 DTW 的结果。不难发现,DTW 没能自然地将图形中的波峰与波峰相对应,反而产生了一个序列中的一个点对应另外一个序列中的多个点的情况,这种情况被称为“Singularities”。出现这种情况的原因是 DTW 算法试图通过扭曲 X 轴来解释 Y 轴上的变化。 为了解决“Singularities”问题,过去的研究提出了很多方案,大致可归为以下三类: 1-Windowing:归根结底,出现 singularities 就是因为两个时间序列上相隔很远的点仅因为值相同/相近容易被 warping 到一起。可以限制 DTW 在 warping 过程中的能选择的范围来解决 singularities,具体可以通过设置一个 warping window 来实现,故称之为 Windowing方法。数学上可写作:, 作为 window width 是一个正整数。图 3 中两虚线所夹范围即为经 window 限制后的范围,此时 warping path 就只能在此区域内。 2-Slope weighting:当传统 DTW 中的递归式改为下式时,即可实现 slope weighting。 不难发现,唯一的区别在于在 min 函数中的后两项前加了 X ,X 为一个正实数。当对 X 的值进行调整时,可以使得 warping path 的方向(slope)会有一定的调整。X 取较大值时,warping path 的选择会更多的朝向对角线方向。 3-Step patterns:改变传统 DTW 中的递归式为下式可以实现改变 warping path step。 将传统 DTW 中的递归式和上式分别可视化如下图 5 中 A、B 所示: A 所对应的即为传统 DTW 的递归式,下一步只能在距离矩阵中相邻的三个方格中选取,而 B 中所对应的就是改变了 step 后的递归式。相较于 A 中,B 中对于每一个第一步没有沿着对角线方向走的方格都再朝其所在方格的对角线方向移动一步,这样即可实现改变 step pattern。 总的来说,以上三类解决方案在一定程度上对解决 singularities 有一定帮助,然而,它们仍然存在以下缺点: (1)有可能错过正确的 warping path。以上三类方法都是在没有任何前提条件的情况下人为地对 warping path 进行限制和调整来减少翘曲,这很有可能会错过真正正确的 warping path。 (2)参数的选择没有明确的指导。在 Windowing 方法中 R 值的选取、Slope weighting 方法中 X 都是人为视具体场景主观调整、没有明确标准的。
5 Derivative Dynamic Time Warping (DDTW)
实际上,DTW 之所以造成“Singularities”,本质上是由于 DTW 算法本身所考虑的特征决定的:DTW 算法只考虑数据点在 Y 轴上的值。 例如:两个数据点 和 的值相同,但是 位于一个时间序列的上升趋势部分,而 位于一个时间序列的下降趋势部分。对于 DTW 而言,很容易将这两个点匹配在一起,因为它们的值相同。然而,从直觉上来说,我们很难把两个趋势相反的部分匹配在一起。为了避免 DTW 只考虑 Y 轴的值造成“Singularities”问题, DDTW 出现了。 DDTW 不考虑数据点的 Y 轴的值,而是考虑更高层次的特征——时序数据的“形状”。该方法通过计算时序数据的一阶导数来获取与“形状”相关的信息,所以被称为 Derivative DTW。 DDTW 本身的概念也很简单,对于传统 DTW 而言,距离矩阵中的元素即为两个点 和 之间的距离;然而对于 DDTW 而言,此时的“距离矩阵”中的元素不再是两点之间的距离,而是时序数据在两点处一阶导数的差值的平方。尽管有多种方法估计一阶导数,出于简便和拓展性,DDTW 中的一阶导数估计采用以下方法: 不难发现,在 点处一阶导数的估计就是通过该点和该点左边点的直线斜率与通过该点左边点和该点右边点的直线斜率的平均数。Keogh, E. J., & Pazzani, M. J. 提到,在只考虑两个数据点的情况下,这种估计方法面对 outliers 更为稳定。 需要注意的是,这种一阶导数的估计方法无法计算时序数据的第一个数据点和最后一个数据点的一阶导数,在实际操作时可以用第二个数据点和倒数第二个数据点的导数来替代。此外,对于高噪声的数据集可以在估计一阶导数之前先做 exponential smoothing。
6 Weighted Dynamic Time Warping (WDTW)
上文提到,经典的 DTW 算法在匹配两个时间序列上的点时仅考虑 Y 轴上的值,而不考虑所匹配的点在 X 轴上的差别,因此会造成时序数据匹配时的“Singularities”问题。 归根结底,“Singularities”问题在某种程度上就源于只考虑 Y 轴的值,第一个序列上的一个点可以跟第二个序列上的另一个很远(此处“远”指的是 X 轴的距离/序数)的点匹配起来,加上 DTW 中 warping path 的连续性、单调性条件,造成了时序数据对齐过程中的各种翘曲/扭曲。 DDTW 通过考虑“形状”利用估计时序数据的一阶导数来解决这个问题,而 WDTW 则采用了不同的思路。简单来说,WDTW 选择在计算两个序列上的两个点之间欧氏距离时加上一个 weight,而这个 weight 与两个点之间的 X 轴上的距离有关系。具体如下(p=2): 如上式,p=2 时为计算两个序列上的两个点 和 的欧氏距离。此处的 即为与两个点在 X 轴上的距离(phase difference)相关的 weight。WDTW 通过计算两点欧氏距离时添加一个 weight 的方法,为解决“Singularities”问题提供了新的思路:weighted DTW 本质上是一种 penalized-based DTW,当 的值较大(两个点在 X 轴上距离较大)时,通过赋予一个较大的 值,则可避免算法将两个距离较大的点匹配在一起。 针对 WDTW,Jeong, Y. S., Jeong, M. K., & Omitaomu, O. A. 等人还提出了一个 logistic weight function 来赋予权重,感兴趣的读者可自行查阅原文。值得一提的是,当 是一个常数的时候,此时的 WDTW 不会对于 X 轴上距离不同的点的惩罚是相同的,所以等同于传统的 DTW;当 的值极大时,此时的 WDTW 对于 X 轴上距离不同的点惩罚也极大,甚至第 i 个点和第 i-1 个点的匹配也不行,此时的 WDTW 即对应传统的欧氏距离。
Keogh, E., & Ratanamahatana, C. A. (2005). Exact indexing of dynamic time warping.Knowledge and information systems,7(3), 358-386. Keogh, E. J., & Pazzani, M. J. (2001, April). Derivative dynamic time warping. InProceedings of the 2001 SIAM international conference on data mining(pp. 1-11). Society for Industrial and Applied Mathematics. Jeong, Y. S., Jeong, M. K., & Omitaomu, O. A. (2011). Weighted dynamic time warping for time series classification.Pattern recognition,44(9), 2231-2240. 维基百科.