DTW vs DDTW

直感 #

同じ山道を歩いた 2 人の高度計の記録を比べるとします。1 人は海抜 20 m の町から、もう 1 人は海抜 0 m の海岸から出発しているので、値そのものを比べると全区間で 20 m の差が出続けます。DTW はこの 20 m を「違い」として距離に積み上げます。しかし「登り坂と下り坂のタイミングが同じか」を知りたいなら、比べるべきは高度ではなく傾きです。DDTW は各時点の傾き（1 つ前と 1 つ後の差分の平均）を先に計算し、その傾きの列どうしに DTW をかけるので、出発地点の高さ 20 m は距離に影響しません。

1. ライブラリ #

1
2
3
4
5
6
7
8
9

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from dtaidistance import dtw
from dtaidistance import dtw_visualisation as dtwvis

from utils import DDTW

np.random.seed(777)

何が起きているか（ステップで見る） #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。

見るポイント：DTW は時間を伸び縮みさせて形を合わせる。タイミングがずれた似た波形を「近い」と判定できる。

実験に使用する二つの波形をプロット #

振幅 12・オフセット +20 の sin 波と、振幅 10・オフセット 0 でノイズを乗せた sin 波を 30 点ずつ作ります。形はほぼ同じで高さが 20 違う、DDTW の効果が最も分かりやすい組み合わせです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

data1 = np.array([12.0 * np.sin(i / 2.1) + 20 for i in range(30)])
data2 = np.array([10.0 * np.sin(i / 2.0) + np.random.rand() for i in range(30)])

plt.figure(figsize=(12, 4))

# 波形をプロット
plt.plot(data1, label="data1", color="k")
plt.plot(data2, label="data2", color="r")
plt.legend()
plt.show()

DTW #

dtaidistance で累積コスト行列と最良経路を求め、2 本の系列と一緒に 1 枚の図にします。

1
2
3
4
5
6
7

d, paths = dtw.warping_paths(
    data1,
    data2,
    window=25,
)
best_path = dtw.best_path(paths)
dtwvis.plot_warpingpaths(data1, data2, paths, best_path)

(<Figure size 720x720 with 4 Axes>,
 [<AxesSubplot:>, <AxesSubplot:>, <AxesSubplot:>, <AxesSubplot:>])

DDTW #

同じ 2 本に自作の DDTW を当て、累積コスト行列を熱マップで描きます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

γ_mat, arrows, ddtw = DDTW(np.array(data1), np.array(data2))

sns.set(rc={"figure.figsize": (18, 15)})
sns.set(font="IPAexGothic")
ax = sns.heatmap(-1 * γ_mat, cmap="YlGnBu")
ax.set_title(f"DDTW = {ddtw}")
ax.invert_xaxis()
ax.invert_yaxis()
ax.set_xlabel("w2")
ax.set_ylabel("w2")
plt.show()

findfont: Font family ['IPAexGothic'] not found. Falling back to DejaVu Sans.
findfont: Font family ['IPAexGothic'] not found. Falling back to DejaVu Sans.

使いどころと落とし穴 #

形のタイミングだけを比べたい（心電図の波形、歩行のセンサー、売上の季節パターン）なら DDTW、値の水準そのものに意味がある（温度の異常検知、在庫量の比較）なら DTW を選びます。DDTW は差分を取るので、data2 に乗せた一様ノイズのような細かい揺れが傾きでは増幅されます。ノイズが多いデータでは移動平均や Savitzky–Golay フィルタで平滑化してから DDTW にかけます。同じ効果を手軽に得たいなら、DTW の前に各系列を z 正規化（平均 0・分散 1）する方法もあり、オフセットと振幅の差はこれでも消えますが、途中でベースラインが動く系列には DDTW の方が強いです。