python - Python中的动态时间规整，如何记下可变矩阵

我在Python中创建了一个简单的动态时间规整实现，但是感觉有点不合常规。我实现了递归关系（或者，至少，我相信我做到了！），但是因为在我的情况下，这涉及到一个numpy数组，所以我不得不将其包装在一个类中以使备忘录起作用（numpy数组是可变的）。

指向DTW的Wiki链接：Dynamic Time Warping

这是代码：

class DynamicTimeWarp(object):
  def __init__(self, seq1, seq2):
    self.warp_matrix = self.time_warp_matrix(seq1, seq2)

  def time_warp_matrix(self, seq1, seq2):
    output = np.zeros((len(seq1), len(seq2)), dtype=np.float64)
    for i in range(len(seq1)):
      for j in range(len(seq2)):
        output[i][j] = np.sqrt((seq1[i] - seq2[j]) ** 2)
    return output·

  @lru_cache(maxsize=100)
  def warp_path(self, i=None, j=None):
    if (i is None) and (j is None):
      i, j = self.warp_matrix.shape
      i   -= 1
      j   -= 1

    distance = self.warp_matrix[i, j]
    path = ((i, j),)
    if i == j == 0:
      return distance, path

    potential = []

    if i - 1 >= 0:
      potential.append(self.warp_path(i-1, j))

    if j - 1 >= 0:
      potential.append(self.warp_path(i, j-1))

    if (j - 1 >= 0) and (i - 1 >=0):
      potential.append(self.warp_path(i-1, j-1))

    if len(potential) > 0:
      new_dist, new_path = min(potential, key = lambda x: x[0])
      distance          += new_dist
      path               = new_path + path

    return distance, path

我的问题：


我相信这是DTW的有效实现吗？
有没有更好的方法来做到这一点，同时保持使用numpy数组
和复发关系？
如果最终不得不使用一个类，然后希望重用该类的实例（通过向其传递新序列，并重新计算warp_matrix），则必须将某种虚拟值作为参数传递给warp_path功能-否则我想lru_cache将错误地返回值。解决这个问题是否有更优雅的方法？

最佳答案

虽然很容易将DTW视为递归函数，但可以实现迭代版本。迭代版本通常快10到30倍。

伊蒙