在本节中,我们首先对 DTW 方法中如何应用翘曲约束以及如何在时间序列的签名表示中实现这些约束进行一些一般性观察。然后,我们研究了增强时间序列以实现更有效的签名特征表示的各种方法,最后我们提出了三种不同的选项来使用签名特征进行时间序列分类。
Notations and Definitions
对于图 3(a) 中的 DTW 情况,时间序列 X 和 Y 周围的绿色圆圈分别代表可以通过扭曲获得的时间序列集合。这些时间序列在 DTW 下被视为等效,并形成等效类。此外,一旦我们找到一个时间序列 Z,它都属于 X 和 Y 的翘曲等价类,我们就可以立即推断 X 和 Y 实际上共享相同的等价类。
然而,在实践中,我们可能不想将 X 与其整个 warping 等价类匹配,因此我们可能会对允许的 warping 数量施加一些限制。如果我们使用“硬”约束,例如最大 warping 窗口大小(数据点可以从其原始时间位置翘曲多远),那么受约束的 DTW 在不受约束的。
如图 3(a) 中的红色省略号所示。我们也可以选择应用“软”约束,其中翘曲惩罚随翘曲距离而变化(例如,如 Amerced DTW [18]),在这种情况下,我们不再定义等价关系,而是强制时间序列之间的接近性,这些时间序列可以以较低的成本相互扭曲(我们将在下一小节中重新讨论如何定义此成本)。图 3(a) 中的紫色“光晕”说明了当我们远离 X 和 Y 时翘曲“容易”的衰减。
对于图 3(b) 中的路径签名情况,路径签名本身直接表示整个 warping 等效类。对于任何可以从 X 扭曲的路径,它们在签名空间中与 X 共享完全相同的路径签名。因此,如果 X 不能被时间扭曲成 Y,那么它们必须具有不同的路径签名。虽然不能保证签名之间的距离直接反映了 X 和 Y 之间的时间扭曲距离,但正如我们稍后将看到的,我们至少可以凭经验验证签名空间中Sx,Sy之间的距离(或它的转换)与路径空间中的 DTW 距离密切相关。
我们现在可以看到,路径签名为弹性距离提供了一种替代弹性距离的方法,用于描述翘曲变换下的时间翘曲等效性或接近性。在接下来的章节中,我们将讨论如何选择合适的增强来约束翘曲,以及如何利用特征特征进行时间序列分类。
Constrained Time Warping
在本节中,我们研究了将约束应用于弹性距离测量(尤其是 DTW)的不同方式,如何使用路径签名实现类似的效果,以及如何使用路径签名更容易实现一些 warping 约束。正如我们在上一小节中看到的,翘曲约束可以是“硬”的,即对翘曲量有上限,也可以是“软”的,即更多的翘曲会产生更高的成本。例如,经典的 Sakoe 带 [41] 或 Itakura 平行四边形 [20] 是硬约束,而软约束在距离优化问题中可能表示为罚项:
现在,我们将注意力转向 warping 约束之间的另一种区别——全局 warp 约束与局部 warp 约束。大多数基于翘曲窗口的弹性距离约束都会对时间翘曲产生全局的绝对约束,如图 4 所示。在这里,我们使用局部 warping 来指代小连续间隔内的形状变形,并使用全局 warping 作为每个 warping 点行进的时间距离的量度。很明显,经典 DTW 算法和其他弹性距离测量中的翘曲窗口约束是绝对约束,它限制了允许数据点从其原始位置移动的距离。
图 4,但排除了像情况 B 这样的极端翘曲。然而,让我们也考虑一下情况 C,其中对于时间序列的每一部分,形状变形量都很小,但它的一个特征在时间上已经移动了很长的距离。从某种意义上说,总时间扭曲仍然“很小”,在某些用例中,我们可能希望对 C 型时间扭曲不同的序列进行分类,例如,两组相同运动类型的体育锻炼跟踪数据,但在动作之间任意停顿。因为情况 C 产生的绝对时间扭曲很大,所以具有全局约束(如约束窗口)的弹性距离无法捕获我们想要的相似性关系。
如果我们考虑软约束,那么全局 warp 约束的合理成本函数将是
这只是将每个点在 Warping 下行进的时间距离相加。同样,局部 warp 约束的成本函数为
这进一步通过曲线的“平坦度”来加权翘曲惩罚,其中曲线的“不有趣”部分(例如平坦区域)比具有有趣形状特征的部分更容易翘曲。
然而,直接扭曲成本惩罚并不是我们实现软局部约束的唯一方法。人们可能已经观察到,通过将时间维度附加到曲线本身可以很容易地恢复全局 warping 约束,因此 warping 成本 自动包含在两点之间的距离中。因此,时间增强等同于应用全局 warp 约束。我们可以对局部 warping 使用相同的增强技巧吗?
事实上,局部约束问题的一个直接解决方案是在 “shape descriptor” 特征向量中 “fossiliized” 局部数据点关系,然后对特征序列进行无约束的弹性距离比较。derivative DTW 或 shapeDTW [51] 等方法采用了这种方法。其他可能的局部形状描述符包括时间延迟嵌入、时间延迟 PCA (TD-PCA) 变换、小波变换等。事实上,可以证明在温和的假设下,导数 DTW 或 DTW 随时间延迟嵌入的作用等价于等式 (6) 中的成本函数(见附录)。图 5 提供了此概念的图示。
我们在这里的主要观察是,如果我们改用路径签名来描述时间扭曲相似性,这种增强技巧仍然适用。我们可以首先使用时间增强和/或局部形状描述符来转换原始时间序列,这会将时间序列提升为一个增强序列,该序列在小时间扭曲下轻微变形,在大扭曲下严重变形。假设签名转换是连续的,如果两个增强序列彼此非常接近,则它们的签名也应该彼此接近。
基于签名和基于 DTW 的弹性相似性比较之间的一个主要区别是,路径签名方法是一种自上而下的方法,而 DTW 是自下而上的方法。给定一个时间序列 X,它的最低阶签名项首先捕获 X 的一般、大规模形状,然后当我们添加更高阶的签名项时,可以解析更精细的局部细节。因此,对于路径签名,比局部小尺度模式更容易捕获大规模模式(例如图 5 中整个模式的位移)。然而,对于 DTW 来说,情况正好相反——对于小的 warping 窗口,我们只能在一个小的局部社区内匹配模式,而要匹配具有明显绝对 warp 的大尺度模式,我们需要大大扩展 warping 窗口,甚至求助于不受约束的 DTW 匹配。这种区别意味着存在弹性相似性问题,其中使用路径签名本质上比使用 DTW 更容易解决,反之亦然。