PythonでDynamic Time Warping

DynamicTimeWarpingって何？

動的時間伸縮法と呼ばれる、時間や速度の異なる信号同士の類似度を求めるアルゴリズムです。
信号同士の類似度を求める際に、単純にユークリッド距離を求めようとすると、信号の長さが
異なると非常に厄介な事になります。

それに対し、DTWは時間伸縮技術を用いて信号同士の長さの差異をうまく丸め込んでくれます。

用途

長さの異なるベクトル同士の類似度を算出するアルゴリズムであり、主に音声認識等の信号解析に用いられています。

Pythonのコード

numpyを使うように直しました 2015年3月17日

def dtw(vec1, vec2):
    import numpy as np
    d = np.zeros([len(vec1)+1, len(vec2)+1])
    d[:] = np.inf
    d[0, 0] = 0
    for i in range(1, d.shape[0]):
        for j in range(1, d.shape[1]):
            cost = abs(vec1[i-1]-vec2[j-1])
            d[i, j] = cost + min(d[i-1, j], d[i, j-1], d[i-1, j-1])
    return d[-1][-1]

このようになります。
sig1とsig2にそれぞれ比較したい1次元の信号データを渡すとベクトル間の類似度を返します。

例えば以下の様な信号s, tを渡すと・・・

s = [1, 1, 1, 1, 1]
t = [1, 1, 2, 2, 1, 3, 3]
dtw(s, t)

6.0

s = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
t = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
dtw(s, t)

0

異なる信号の長さでも類似度を算出することが出来ました