0

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

私の質問:

  1. 私が信じているように、これはDTWの有効な実装ですか？

  2. numpy 配列の使用と再帰関係を維持しながら、これを行うより良い方法はありますか?

  3. クラスを使用しなければならなくなり、クラスのインスタンスを再利用したい場合 (新しいシーケンスを渡し、warp_matrix を再計算することによって)、warp_path に引数として何らかのダミー値を渡す必要があります。関数 - そうでなければ、lru_cache が誤って値を返すと思います。この問題を回避するよりエレガントな方法はありますか?

4

1 に答える 1

1

DTW を再帰関数と考えるのは簡単ですが、反復バージョンを実装することは可能です。通常、反復バージョンは 10 倍から 30 倍高速です。

エーモン

于 2013-05-10T04:59:44.907 に答える