0

我在 Python 中创建了一个简单的 Dynamic Time Warping 实现，但感觉有点像 hack。我实现了递归关系（或者，至少，我相信我做到了！），但是因为在我的例子中这涉及到一个 numpy 数组，我必须将它包装在一个类中才能让记忆工作（numpy 数组是可变的）。

DTW 的 Wiki 链接：动态时间规整

这是代码：

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_cache 将错误地返回值。有没有更优雅的方法来解决这个问题？

4

1 回答 1

1

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

埃蒙

于 2013-05-10T04:59:44.907 回答