前置き

本記事はfreeeデータに関わる人たち Advent Calendar 2019におけるDay 21のエントリーです。
同Advent CalendarのDay 2に引き続き2度目の登場ですが、今回は分析っぽいことを書きます。

目的

時系列データのクラスタリングなどを行う際に頻繁に用いられる距離尺度の一つに動的時間伸縮（DTW）があります。

DTWの定義を見て、言葉では何となく性質を理解した気になっているのですが、視覚的にちゃんと理解するべく、トイデータを使って可視化します。

距離尺度の簡単な説明

動的時間伸縮（Dynamic Time Warping）

英語版wikiやこの記事あたりが詳しいですが、要は以下の条件下で2つの時系列の各点の類似点を総当りで探索し、その距離が2つの系列間のDTW距離です。

• いずれの点も必ずもう一方の時系列における一つ以上の点にマッピングされる
• 端点同士はつなぐ
• 点のマッピングは交差してはならない

全探索的に比較して最適マッチを探すアルゴリズムのため、時系列方向の移動や伸縮に強い距離関数として知られています。
今回は可視化を通じ、この英語名がかっこいい距離尺度の長所を身を以て理解します。

ユークリッド距離

ここでは比較対象として、みんな大好きユークリッド距離を採用します。
各時間における値の距離を足し上げたものに対応し、以下のような定義で算出されます。

{\rm Euclidean}=\sum_i \left|{y_{1i}-y_{2i}}\right|

当然、各時間における値の距離しか見てないので、時系列方向にズレたデータの距離なんかは遠くなります。

検証対象データ

ここでは三角関数をベースに３種類のトイデータ群＋基準データを作成しました。
いずれも比較相手は $y=\cos(x)$ とします。

ちなみに、以下は目的に合致する関数系を適当に考えたので、パラメータ置くならもっとこうした方が良いでしょ、みたいなツッコミは甘んじて受けます。

時間方向に並行移動

系列の周期変化がズレた時間で起こっている場合。
数式で書いたら以下みたいなデータ（$a$がパラメータ）。

y = \cos(x+a\pi)

振動数の変化

時系列方向に対して同じ周期変化をするが、変化の速度が異なる。
数式で書いたら以下。

y = \cos(ax)

伸縮

全体で見ると波の数は一致しているが、特定時点を境に振動数の変化が大きく変わっている場合。
連続関数だが、導関数は不連続。

y = \left\{
  \begin{array}{ll}
    \cos\left(\frac{1}{a}x\right) & 0\lt x\lt 4a\pi \\
    \cos\left[\frac{1}{2-a}(x-4a\pi)\right] & 4a\pi \lt x \lt 8\pi
  \end{array}
\right.

基準データ

これより距離が遠ければ似てないとみなせそうな相手として、何の動きもしない$x$軸と平行な直線（$y=0$）を採用します。

比較結果

まず比較の基準となる距離として、$y=\cos(x)$と基準データ$y=0$の距離を算出します。
以降はこの値を基準とした類似度（基準値比）のパラメータに対する変化を観察します。

時間方向に平行移動

まずは平行移動させた場合を見てみます。

いずれの距離尺度にも山なりの挙動ですが、ユークリッド距離はパラメータがだいたい0.3-1.7の間では比較基準を超えているのに対し、DTWは最大でも基準値の半分程度の距離に収まっており、DTWはユークリッド距離に比べて「時間軸方向にズレていても同じ変化をしている場合は似ている」と判断できる尺度であることがよくわかります。

一方で、ユークリッド距離はきれいな弧を描いているのに対し、DTWはパラメータ１付近で挙動に乱れが見られます。
これはDTWのアルゴリズム上、データの端点における周期上の位置が揃っていない場合に類似点に不安定性が発生することに起因し、実際、DTWの類似点を可視化すると、該当パラメータ付近で類似点の切り替わりが観測できます。

DTWで時系列データの一部切り取ったものを扱う際は、どこで切り取ったかに気をつけたほうが良いかもしれません。

振動数の変化

次に、振動数を変化させた場合を見てみます。

ユークリッド距離はパラメータが1の近傍でのみ基準値を下回りますが、それ以外の部分では1.4付近でほぼ一定の値を取ります。
一方、DTWはパラメータが1を境に概ね単調に大きくなる谷型の形状であり、少なくとも0.5-2.5倍の間では基準値を上回ることはありませんでした。
DTWはデータに含まれる周期数が変化しても、ある程度の柔軟性を持って距離が測れるというのが確認できますね。

また、振動数を変化させた場合はいずれの距離尺度も小さく振動する傾向があります。
特にパラメータ1以降で距離尺度に依らず、いずれも同じ0.25程度の周期で振動していることから、アルゴリズム上の産物というよりは、このデータ自体の性質と思われます（深掘りはしてない）。

ちなみに上と同様にDTWの類似点を可視化すると、定期的に類似点の切り替わりが発生し、振動数の差が大きくなるにつれて節の数が増えていて、距離の増加に寄与しているのが分かります。

伸縮

最後に、三角関数を２周期ずつで分け、時間方向に伸び縮みさせた場合を見てみます。

ユークリッド距離は0.85を超えないと基準よりも距離が小さくなりませんが、DTWはかなり広い領域でほぼ0を取っています。
DTWのアルゴリズムが、2つの時系列の端点を類似点とし、残りを交差しないように類似点を探索することを考慮すると、「同じ周期数で、かつ端の周期位置が揃っている」場合には距離がほぼ0となることは理解できます。

また、DTWの類似点を可視化してみると、0.3まででは節がありますが、上記アルゴリズムを考慮すると、これは数値計算上出てきた局所最適と思われます（深掘りはしてない）。

まとめ

今回はトイデータを利用した可視化を通じ、DTWの性質をちょっと深めに理解できました。
データとその目的を鑑みながら、適した距離尺度を利用して分析したいものですね！