英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

动态时序规整

动态时序规整（DTW）是一项著名的，在特定限制下，于两个给定的（时变）序列之间寻找最优排列的技术（图4.1）。直观来看，这些序列以非线性的方式进行规整来彼此相匹配。起初，DTW技术用于在自动语言识别中，比较不同的语言模式，参见[170]。在某些领域，例如数据挖掘和信息检索中，DTW曾被成功应用于自动处理时间形变和与时序数据相关的不同速度。

在这一章，我们将介绍和探讨经典DTW的主要观点（Sect.4.1）并且总结关于局部和全局参数的几个修改（Sect.4.2）。为了提高传统DTW的速度，我们在Sect.4.3描述了一种一般的多尺度的DTW方法。在Sect.4.4我们将展示DTW是如何被用来在一个长数据流中识别所有子序列的，这类似于给定的查询序列（Sect.4.4）。相关排列技术的讨论与参考文献可以在Sect.4.5找到。

图4.1. 两个时间相关序列的时间排列。对齐的点由箭头表示

4.1 经典DTW

DTW的目的是比较两个（时变）序列X := (x₁, x₂,...,x_N )的长度N isin; N和Y := (y₁, y₂,...,y_M) 的长度M isin; N。这些序列可以是离散信号（时间序列），或者更普遍的在等间距点采样的特征序列。下面，我们确定了一个特征空间，记作F。那么x_n, y_misin;F对于nisin;[1:n]和misin;[1:m]。为比较两种不同的特征x, y isin; F，需要一个局部成本测度，有时也称为局部距离测度，这定义为一个函数

通常，如果x和y彼此相似，那么c(x,y)很小（低成本），否则，c(x,y)很大（高成本）。对序列X和Y中的每一对元素的局部成本测度的估计，得到由C(n, m) := c(x_n, y_m)定义的

成本矩阵C isin; R^Ntimes;M，详见Fig. 4.2. 然后，目标是在X和Y中寻找一种有着最小整体成本的排列。直观来看，这样的最优排列方式沿着成本矩阵C的低成本“谷”运行，如图4.4所示。下一个定义形式化了排列的概念。

图4.2. 两个实数序列成本矩阵的X（纵轴）和Y（横轴）使用曼哈顿距离（差值绝对值）作为局部成本度量c。低成本区域用深色表示，高成本区域用浅色表示。

定义4.1. 一个(N,M)-规整路径（若N和M在下文中交代清晰，则可简称为规整路径），是一个对于 lisin; [1 : L]满足以下三个条件的包含p_l = (n_l, m_l) isin; [1 : N] times; [1 : M]的序列p= (p₁,...,p_L)。

(i)边界条件：p₁ = (1, 1) 且 p_L = (N,M).

(ii)单调性条件：n₁ le; n₂ le; ... le; n_L 且m₁ le; m₂ le; ... le; m_L.

(iii)步长条件：p_{l 1} minus; p_l isin; {(1, 0),(0, 1),(1, 1)} for lisin; [1 : L minus; 1].

需注意，步长条件暗示了单调性条件，但为了表述清晰，已明确引用。一个(N,M)-规整路径p = (p₁,...,p_L)通过将X中的元素x_nl赋值给Y中的元素y_ml来定义X = (x₁, x₂,...,x_N )和Y = (y₁, y₂,...,y_M)两序列的排列。边界条件将X和Y的第一个元素和最后一个元素彼此排列。换言之，此排列指的是X和Y的整个序列。单调性条件反映了对于可靠时序的需求：如果X中的一个元素在第二个元素之前，这也适用于Y中相应的元素，反之亦然。最后步长条件表达了一种连续性条件：X和Y所有元素都不可以被遗漏，并且在排列之中没有重复（意义是规整路径p上包含的的所有指数对是两两不同的）。图4.3说明了这三个条件。

在X和Y之间的规整路径p相对于局部成本度量c的总成本c_p(X, Y)定义为

此外，在X和Y之间的最优规整路径是一个在所有可能的规整路径中，总成本最小规整路径p^lowast;。然后定义X和Y之间的DTW距离DTW(X, Y)作为p^lowast;的总成本：

我们继续讨论关于DTW距离的几个问题。首先需明确，即使可能有几个最低总成本的规整路径，DTW距离也是被明确定义的。其次，我们可以轻易发现，如果局部成本c是对称的，那么DTW距离也是对称的。但是，DTW的距离通常是不正定的，即使对于c也是如此。例如，当c(x₁, x₁) = c(x₂, x₂) = 0时，得到序列X:= (x₁, x₂)和Y:= (x₁, x₁, x₂, x₂, x₂)的DTW(X, Y) = 0。此外，即使在c是度量的情况下，DTW距离一般也不满足三角形不等式。下面的例子说明了这一事实。

例子4.2. 令F: ={alpha;、beta;、gamma;}为一个三个特性组成的特征空间。对于x, yisin;F，如果x = y，令c(x, y):= 0；如果x ne; y，令c(x, y):= 1，我们以此来定义一个成本测度c: Ftimes;F→{0,1}。需注意，c定义了F上的一个度量，并且特别满足三角形不等式。现在考虑X: =(alpha;,beta;,gamma;),Y: =(alpha;,beta;,beta;,gamma;)和Z: =(alpha;,gamma;,gamma;)。然后很容易检查DTW(X, Y) = 0, DTW(X, Z) = 1, DTW(Y,Z) = 2。因此，DTW(Y,Z) gt; DTW(X, Y ) DTW(X, Z)，换言之，DTW距离不满足三角不等式。最后需注意，路径p¹ = ((1, 1), (2, 2),(3, 2),(4, 3)), p² = ((1, 1),(2, 1),(3, 2),(4, 3)),p³ = ((1, 1), (2, 2), (3, 3),(4, 3))为总成本Y与Z之间不同的最优规整路径。这表明，最优规整路径通常不是唯一的。

可以通过测试X和Y之中所有可能规整路径来确定一个最优规整路径。然而，这样的过程会导致计算复杂度以N和M的指数增长。现在我们将介绍一种基于动态规划的O(NM)算法。为此，我们定义对于isin; [1 : N]的前缀序列X(1:n) := (x1,...xn)和对于m isin; [1 : M]的前缀序列Y (1:m) := (y1,...ym)，并且令

D(n, m)的值定义了一个ntimes;m矩阵D，也称为累计成本矩阵。显然，D(N,M) = DTW(X, Y)。接下来，一个代表了成本矩阵C或者累积成本矩阵D的一个矩阵项的元组（n,m）将会被称为一个单元格。下一个定理展示了如何有效地计算D。

定理4.3. 累积成本矩阵D满足以下特征：对于n isin; [1 : N]，有D(n, 1) =sum;c(xk, y1)，对于m isin; [1 : M]，有D(1, m) = sum;c(x1, yk)，并且对于1lt; n le; N 和 1 lt; m le; M

特别是，DTW(X, Y) = D(N,M)可以用O(NM)运算来计算。

证明. 令m=1，n isin; [1 : N]。那么在Y(1:1)和X(1:n)之间只有一条可能的弯曲路径，且总成本为sum;c(xk, y1)。这证明了D(n, 1)的公式。同理可得D(1, m)的公式。现在，设n gt; 1、m gt; 1，设q = (q1，hellip;,qL-1,qL)为X(1:n)和Y (1:m)的最优规整路径。接着，边界条件意味qL = (n, m)。令(a, b) := qLminus;1，步长条件意味着(a, b) isin; {(n minus; 1, m minus; 1),(n minus; 1, m),(n, m minus; 1)}。并且由此可见，(q1，hellip;，qLminus;1)必为X(1: a)和Y (1: b)的最优规整路径（否则，q对于X(1:n)和Y (1:m)就不是最优的）。由于D(n, m) = c(q1，hellip;，qLminus;1)（X(1: a)， Y (1: b)） c(xn, ym)，q的最优性意味着声明(4.5)。

定理4.3简化了矩阵D的递归计算。通过额外的行和列来延伸矩阵D并且形式上令对于n isin; [1 : N]有D(n, 0) := infin;，对于m isin; [1 : M]有D(0, m) := infin;，且D(0, 0) := 0来简化初始化。那么(4.5)的递归对于nisin;[1:n]和misin;[1:m]也是成立的。此外，需注意，D可以按列方式计算，其中第m列的计算只需要第(m - 1)列的值。这意味着，如果只对值DTW(X, Y) = D(N,M)感兴趣，那么存储需求就是O(N)。类似地，可以以行方式进行，从而得到O(M)。但是，注意这两种情况下的运行时间都是O(N M)。此外，要计算出最优规整路径plowast;，需要整个(Ntimes;M)矩阵D。下面的练习将演示以下算法OptimalWarpingPath如何完成此任务。

※算法：OptimalWarpingPath

输入：累计成本矩阵D
输出：最优规整路径p

过程：计算最佳路径plowast;= (p1，hellip;，pL)的顺序与以pL = (N,M)开始的索引相反。假设pl=(n,m)已经被计算。在(n, m) =(1,1)的情况下，必有l= 1，这样就做完了。否则：

这里我们取字典上最小的对，以防“argmin”不是唯一的。

图4.4显示了图4.2中各序列的最佳整经路径p(白线)。需注意，plowast;只涉及成本较低的C单元（cf,图4.4a）。得到的累计成本矩阵D如图4.4b所示。

图4.4. (a)成本矩阵C，如图4.2所示；(b)具有最优规整路径p（白线）的累积成本矩阵D

4.2 DTW的变化

为了加快DTW的计算速度以及更好地控制规整路径的可能路径，提出了各种修改方案。在本节中，我们将讨论其中的一些变体，并参考[170]了解更多细节。

4.2.1步长条件

回想一下，定义4.1中的步长条件(iii)代表了一种局部连续性条件，它保证了序列X = (x1, x2，hellip;，xN)中的每个元素被赋值给Y = (y1, y2，hellip;，yM)的一个元素，反之亦然。然而，这种条件的一个缺点是，一个序列的单个元素可能被分配给另一个序列的多个连续元素，从而导致规整路径中的垂直和水平段，见图4.6。直观地说，规整路径可能会卡在某个位置上，相对于一个序列，对应于一个很大程度的局部减速（或者，相反地，相对于第二序列，一个很大程度的局部加速）。为了避免这种退化，可以修改步长条件来约束允许的规整路径的斜率。在第一个例子中，我们用对于lisin; [1 : L]有pl 1-plisin; {(2, 1),(1, 2),(1, 1)}这个条件替换了定义4.1中的步长条件(iii)。见图4.5b。这导致了规整路径在1/2和2范围内具有局部斜率。由此产生的累计成本矩阵D可以通过递归计算出来，对于nisin; [2 : N]和m isin; [2 : N]有：

我们将初值设为：对于n isin; [1 : N]有D(0, 0) := 0, D(1, 1) := c(x1, y1), D(n, 0) := infin;；对于 n isin; [2 : N]有D(n, 1) := infin;；对于m isin; [1 : M]有D(0, m) := infin;；对于m isin; [2 : M]有D(1, m) :=infin;。需注意，对于修改过的步长条件，当且仅当N和M之间的长度最多相差两倍时，两个序列X和Y之间会存在一条规整路径。此外，注意不是所有的元素X都需要赋值给Y的某个元素，反之亦然。如图4.6b所示：在这里，x1分配给y1, x3分配给y2，但是x2没有分配给Y的任何元素(即，x2被省略，且完全不产生任何成本)。

图4.5c给出了步长条件的第二个示例，该示例避免了这种遗漏，同时对规整路径的斜率施加了约束。对于(n, m) isin; [1 : N]X[1 : M]{(1,1)}，所得到的累计成本矩阵D的递归式为：

这里初值设定为：对于n isin; [minus;2 : N]有D(1, 1) := c(x1, y1), D(n, minus;2) := D(n, minus;1) := D(n, 0)

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[239447]，资料为PDF文档或Word文档，PDF文档可免费转换为Word