gggggraziegrazie

graizegrazieさんのやったこと、学んだことを記録する雑記帳です

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

2つの時間軸方向に変化するデータx, yの類似度を求めるためのアルゴリズムです。類似度はデータ間の距離で表現されます。データは時間方向に変化するため、時刻xにおけるx, yの値を{x_t, y_t}とすると、データ間の距離は{\sum|x_t - y_t|}となります。もしもx, yが同じデータを表していれば、理想的には時刻tにおけるx,とyの値は等しいはずなので、類似度は0となります。

[1]にありますが、元々この手法は音声認識に使われていたそうです。音声認識でXさん・Yさんがそれぞれ発した「あいうえお」を録音したとして、録音のタイミングや話者の話し方によっては、最初の「あ」が音声データ中の同じ時刻には記録されません。そのため、「あ」のタイミングが同時になるような調整処理が必要となります。加えて、XさんとYさんで尺やトーンが異なることが考えられるので、x,yのデータを総当たりで比較する必要があります。総当たりの比較の結果は、下記の様な行列で表現できます。
{
\begin{pmatrix}
\mid x_1 - y_1\mid & ... & \mid x_1 - y_M \mid \\
... & ... & ... \\
\mid x_N - y_1 \mid & ... & \mid x_N - y_M \mid
\end{pmatrix}
}
となります。類似度は{ min \sum \mid x_t - y_t \mid }と表せるので、つまり上記行列の左上から右下までで合計値が最も小さくなるパスを選ぶ問題として考えることが出来ます。