Python中的动态时间扭曲，如何记忆可变矩阵

Question

我在Python中创建了一个动态时间扭曲的简单实现，但感觉有点像是一个黑客。我实现了递归关系（至少，我相信我做到了！），但因为在我的例子中，这涉及一个numpy数组，所以我必须将它包装在一个类中才能使memoriation工作（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

我的问题：

1. 我相信这是DTW的有效实现吗？

2. 有没有更好的方法在保持numpy数组的使用的同时做到这一点 递归关系呢？

3. 如果我最终不得不使用一个类，然后希望重用该类的一个实例（通过向它传递新的序列，并重新计算warp_matrix），我将不得不将某种类型的伪值作为参数传递给warp_path函数，否则我认为lru峎u缓存将错误地返回值。有没有更优雅的方法来解决这个问题？

Answer 1

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

亚蒙