動的時間伸縮法 / DTW (Dynamic Time Warping)

時系列(音データ)の類似度を測りたいところで、DTWというのをよく見かけるので、どういうものなのか調べてみました。

参考は英文ウィキ:http://en.wikipedia.org/wiki/Dynamic_time_warping

DTWの計算では、二つの時系列(長さは異なってもいい)の各点の距離を総当たりに比較するため、まずは各点の「距離」を定義しておく必要があります。普通にユークリッド距離とかが一般的か。

ほかの時系列比較方法は、時系列の点を一対一で比較しますが、DTWは長さが異なる(たとえ同じ長さでも内部でパターンがずれてるかもしれない)ということに対応するため、

「一つの点はもう一つの時系列の、複数の隣接した点と比較してもよい」

という特別ルールを採用したといえます。ちなみに最初と最後の点はお互い揃える必要があります。

このルールでは、二つの時系列の間で多くのマッチングパターンができるので、その中で距離の総和が一番小さいものを求めて、DTWの結果とするわけですね。求め方は普通に動的計算法で、結構わかりやすいです。

実際には、時間的に離れすぎている点がマッチされることを避けたい場合があるので、時系列に窓をかけて制限をかけるというのが、ウィキの下のアルゴリズムがやってることです。

DTWは類似度計算に使われるほか、最小コストが得られるルート(マッチング)を使って二つの時系列を揃える(Alignment)という仕事もできます。