dtw_distance

dtw_distance(x: ndarray, y: ndarray, window: float | None = None, itakura_max_slope: float | None = None, bounding_matrix: ndarray | None = None, **kwargs: Any) → float

计算两个时间序列之间的动态时间规整（DTW）距离。

最初在 [1] 中提出的 DTW 是一种弹性距离度量，即，它是在对齐（扭曲）两个时间序列以通过时间轴扭曲最好地匹配彼此之后计算的距离 [2]。

此函数仅计算以下情况的时间翘曲距离：* 序列，忽略时间索引 * 两个长度相等的时间序列 * 欧几里得成对距离

对于不等长的时序数据，使用 sktime.dists_kernels.DistFromAligner 配合时间弯曲对齐器，如 sktime.aligners.AlignerDTW。要使用任意的成对距离，使用 sktime.aligners.AlignerDTWfromDist。

在数学上，对于两个序列 :math:’mathbf{a}={a_1,a_2,ldots,a_m}’ 和 :math:’mathbf{b}={b_1,b_2,ldots, b_n}’（为简化假设长度相等），DTW首先计算序列 :math:’mathbf{a}’ 和 :math:’mathbf{b}’ 之间的成对距离矩阵 :math:’M( mathbf{a},mathbf{b})’，即 :math:’m times n’ 矩阵，其中 :math:’M_{i,j} = d(a_i, b_j)’，对于所选的距离度量 \(d: \mathbb{R}^h \times \mathbb{R}^h \rightarrow \mathbb{R}\)。在此估计器中，使用了平方欧几里得距离，即 \(d(x, y):= (x-y)^2\)。一个扭曲路径 .. math:: P=((i_1, j_1), (i_2, j_2), ldots, (i_s, j_s)) 是一个有序的索引元组 \(i_k \in \{1, \dots, m\}, j_k \in \{1, \dots, n\}\)，它定义了矩阵 :math:’M’ 的一个遍历路径。此实现假设扭曲路径满足以下条件：* 闭合路径：\(i_1 = j_1 = 1\); \(i_s = m, j_s = n\) * 单调路径：\(i_k \le i_{k+1}, j_k \le j_{k+1}\) 对于所有 \(k\) * 严格单调路径：\((i_k, j_k) \neq (i_{k+1}, j_{k+1})\) 对于所有 \(k\) 序列之间的DTW路径是通过 :math:’M’ 的最小化总距离的路径，在所有满足上述假设的有效路径中，给出序列。形式上：长度为 :math:’s’ 的扭曲路径 :math:’P’ 的距离为 .. math:: D_P(mathbf{a},mathbf{b}) = sum_{k=1}^s M_{i_k,j_k}。如果 :math:’mathcal{P}’ 是所有可能路径的集合，DTW路径 :math:’P^*’ 是其中距离最小的路径：.. math:: P^* = argmin_{Pin mathcal{P}} D_{P}(mathbf{a},mathbf{b})。两个序列 :math:’mathbf{a},mathbf{b}’ 之间的DTW距离是最小扭曲路径距离：.. math:: d_{dtw}(mathbf{a}, mathbf{b}) = min_{Pin mathcal{P}} D_{P}(mathbf{a},mathbf{b}) = D_{P^*}(mathbf{a},mathbf{b})。最优扭曲路径 $P^*$ 可以通过动态规划精确找到。这可能是一个耗时的操作，通常会对允许的扭曲量进行限制。这是通过 bounding_matrix 结构实现的，该结构通过掩码限制允许的扭曲。常见的边界策略包括Sakoe-Chiba带 [R93974dace1e5-3] 和Itakura平行四边形 [4_]。Sakoe-Chiba带创建了一个沿 :math:’M’ 对角线宽度相同的扭曲路径窗口。Itakura平行四边形允许在序列的开始或结束处比中间进行更少的扭曲。

如果函数被调用时传入的是多元时间序列，请注意矩阵 :math:’M’ 是使用多元平方欧几里得距离计算的，即 \(d(x, y):= (x-y)^2\) = sum_{i=1}^h (x_i - y_i)^2`。这有时被称为DTW的“依赖”版本，即DTW_D，参见 [R93974dace1e5-5]。

参数:

x: np.ndarray (1d 或 2d 数组)

第一个时间序列。

y: np.ndarray (1d 或 2d 数组)

第二个时间序列。

window: float, defaults = None

这是Sakoe-Chiba窗口的半径（如果使用Sakoe-Chiba下界）。值必须在0.和1.之间。

itakura_max_slope: float, 默认值 = None

Itakura 平行四边形的斜率梯度（如果使用 Itakura 平行四边形下界）。值必须在 0. 和 1. 之间。

bounding_matrix: np.ndarray (2d，大小为 mxn，其中 m 是 len(x)，n 是 len(y))，

defaults = None

自定义使用的边界矩阵。如果定义了，则忽略其他 lower_bounding 参数。矩阵应构造为，被认为在边界内的索引值应为 0，而边界矩阵外的索引值应为无穷大。

**kwargs: 任意

额外的关键字参数。

返回:

浮动

x 和 y 之间的 DTW 距离。

引发:

ValueError

如果 sakoe_chiba_window_radius 不是浮点数。如果 itakura_max_slope 不是浮点数。如果提供的 x 或 y 的值不是 numpy 数组。如果 x 或 y 的值有超过 2 个维度。如果提供了度量字符串，并且不是定义的有效字符串。如果提供了度量对象（类的实例）并且不继承自 NumbaDistance。如果解析的度量不是 no_python 编译的。如果无法确定度量类型。如果同时设置了 window 和 itakura_max_slope。

参考文献

[1]

H. Sakoe, S. Chiba, “Dynamic programming algorithm optimization for spoken word recognition,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 26(1), pp. 43–49, 1978.

[2]

Ratanamahatana C 和 Keogh E.: 关于动态时间规整数据的三个误区

mining 第五届 SIAM 国际数据挖掘会议论文集, 2005 .. [R93974dace1e5-3] Sakoe H. 和 Chiba S.: 用于口语识别的动态规划算法优化。IEEE 声学、语音和信号处理交易 26(1):43-49, 1978. .. [R93974dace1e5-4] Itakura F: 应用于语音识别的最小预测残差原理。IEEE 声学、语音和信号处理交易 23(1):67-72, 1975. .. [R93974dace1e5-5] Shokoohi-Yekta M 等: 将 DTW 推广到多维情况需要一种自适应方法。数据挖掘和知识发现, 31, 1-31 (2017).

示例

>>> import numpy as np
>>> from sktime.distances import dtw_distance
>>> x_1d = np.array([1, 2, 3, 4])  # 1d array
>>> y_1d = np.array([5, 6, 7, 8])  # 1d array
>>> dtw_distance(x_1d, y_1d)
58.0

>>> x_2d = np.array([[1, 2, 3, 4], [5, 6, 7, 8]])  # 2d array
>>> y_2d = np.array([[9, 10, 11, 12], [13, 14, 15, 16]])  # 2d array
>>> dtw_distance(x_2d, y_2d)
512.0