Paradise Lost

駄人間にならないための日々の記録

DTW(dynamic time warping)を使って時系列データを分類してみた

時系列データを扱う練習として先生に教えていただいたDTW距離をまとめてみることにした。

DTW(Dynamic time warping)とは

動的時間伸縮法(Dynamic time warping、DTW)は初期の音声認識手法であるが、隠れマルコフモデルに基づく手法が一般化したため、使われなくなった。時間または早さの異なる2つの信号シーケンスの間の類似度を測るアルゴリズムである。
Wikipediaより

簡単に言えば二つの時系列データを似た部分同士を伸縮を許して比較する方法

f:id:centraleden:20150814182734p:plain
比較例

DTWのメリットとデメリット

メリット

  • 様々な時系列データに対して高精度
  • 長さの異なる時系列データを比較できる

デメリット

  • 計算量が多い

DTWの流れ

XとYという時系列データがあり、それぞれのデータ長がN, Mであるとする。

  1. N×Mの大きさのDTW距離を格納した類似度行列DTWを作る
  2. 動的計画法によりDTW[0][0]からDTW[N-1][M-1]までのコストを順番に求めていき、DTW[N-1][M-1]のコストが最小となるパスを求める
  3. 2で求めた行列のDTW[N-1][M-1]の値がXとYの距離となる

DTW行列の作り方

  1. N×Mの大きさの行列を作り、初期化する
  2. DTW行列の0列目の要素と0行目の要素の値を全て∞とし、DTW[0][0] = 0とする
  3. その他の部分は以下の式で求める
cost = root((A[i] - B[j]) ^ 2)
DTW[i][j] = cost + minimum(DTW[i-1][j], DTW[i][j-1], DTW[i-1][j-1])

この計算でDTW[N-1][M-1]までに通ったパスはワーピングパスと呼ばれ、比較する点の対を表す。以下にワーピングパスの例を示す。

f:id:centraleden:20150814191051p:plain
ワーピングパスの例

実験

クラス分類でこの距離尺度を試してみる

使用データセット

SVC2004のサンプルデータセットを使用した。 このデータセットは、あるユーザーの署名の時系列データと、他人が本人の真似をして書いた偽物の署名の時系列データがそれぞれ20個ずつあり、それらのデータが5人分用意されている。ユーザー毎に1から20までのデータが本物の署名データで21から40までが偽物の署名データとなっている。 含まれている特徴は以下の7個

  • X座標
  • Y座標
  • タイムスタンプ
  • ペンがペンタブについているかどうか
  • ペンの方向
  • ペンの高さ
  • 筆圧

評価方法

  • 1人40個×5人分=200個のデータを使用
  • サンプルデータの特徴のうちX座標とY座標のみ使用
  • 本物の署名10個と偽物の署名10個をそれぞれの平均データを取るために使用し、残りの180個で評価を行った(偽物の署名はそれぞれ別々の人が書いたため、平均を取る意味はない)
  • 分類するデータを本物の署名の平均データと偽物の署名の平均データとそれぞれ比較して近い方に分類した
  • ここではDTW行列を作ってパスを求めたまではいいが、そのパスで(i,j)というものがあった場合F[ i ]とG[ j ]をユークリッド距離で比較するというよくわからないことをしていた(しかも最終的にそっちを計算した平均を距離として使用していたため、DTW距離を計算したのに使用していない)

結果

結果は後で出します