動的時間伸縮 DTW シミュレーター

速度や位相がずれた 2 つの時系列を、時間軸の伸縮を許した最適アラインメントで比較する Dynamic Time Warping（DTW）の動作を体験するツールです。系列長・Sakoe-Chiba 窓幅・距離計量・位相シフト・振幅倍率を変えると、DTW 距離・素朴な L2 距離・コスト行列セル数・メモリ削減率・スピードアップ比がリアルタイムで更新されます。

パラメータ設定

系列 1 長 N

参照時系列のサンプル数

系列 2 長 M

比較対象時系列のサンプル数

Sakoe-Chiba 窓幅

対角線からの最大逸脱幅（系列長に対する %）

距離計量

セル間距離 d(x,y) の定義

真の位相シフト

系列 2 が系列 1 から時間方向にずれる量

振幅倍率

系列 2 の振幅を系列 1 比でスケールする

計算結果

—

DTW 距離

—

単純 L2 距離

—

アラインメント長

—

制約セル数

—

メモリ削減 (%)

—

スピードアップ比

—

コスト行列と最適アラインメント経路

上下に 2 時系列（白＝系列 1、青＝系列 2）、右上にコスト行列のグリッド。青ラインが Sakoe-Chiba 窓制約下での最適経路、黄ハイライトが窓境界。

元時系列 vs アラインメント後

DTW 距離 vs 窓幅 (%)

理論・主要公式

$$D(i,j) = d(x_i, y_j) + \min\bigl\{D(i-1,j-1),\, D(i-1,j),\, D(i,j-1)\bigr\}$$

D = 累積コスト行列、d = 点対点距離。動的計画法でセル毎に更新し、最終セル D(N,M) が DTW 距離。

$$|i-j| \le w, \qquad w = \max\bigl(|N-M|,\ \lceil r\cdot\max(N,M)\rceil\bigr)$$

Sakoe-Chiba 窓制約。r は窓幅%、w 外のセルは計算しない。制約セル数は N·(2w+1) − w·(w+1) でメモリ・計算量を大幅に削減。

$$\text{Speedup} = \frac{N \cdot M}{N \cdot (2w+1) - w(w+1)}$$

素朴な全探索 N·M に対するスピードアップ比。窓を狭めるほど速くなるが、最適パスを外す危険が増える。

動的時間伸縮 (DTW) — 時系列パターンマッチング

🙋

「動的時間伸縮」って名前が物々しいですけど、要は何をするアルゴリズムなんですか？「同じ波形だけど速度が違う 2 つの時系列」を比較する、と聞いたんですが…。

🎓

そう、その理解でほぼ正解だよ。例えば同じ言葉を 1 秒で言った人と 1.3 秒でゆっくり言った人。波形を縦に並べて引き算すると、時間がずれているだけで距離は爆発する。でも DTW は「片方を伸ばしたり縮めたりして、最も一致する対応関係（アラインメント）」を動的計画法で探す。だから速度違いの同パターンを「同じもの」と判定できる。1978 年に NTT の Sakoe（迫江）と Chiba（千葉）が音声認識のために提案した、由緒正しい古典アルゴリズムなんだ。

🙋

なるほど、左で系列 1 長を 100、系列 2 長を 80 にしてみました。素朴な L2 距離が 101 もあるのに、DTW 距離は 1.2 になってます。これは「単に長さが違うだけのほぼ同じ波形」だと DTW は理解した、ということですか？

🎓

そのとおり。素朴な L2 は長さの差 20 ポイントに 5 のペナルティを掛けて 100 が乗ってる。でも DTW は時間軸を縮めて系列 1 の 100 点を系列 2 の 80 点にうまく対応付けるから、本質的な「波形の違い」だけが残る。あとは位相シフト 10% と振幅 100%（つまり等倍）の差で、コスト行列の最終セル D(N,M) が 1.2 になる。これが心電図比較・歩行解析・音声認識で DTW が今でも現役で使われ続けている理由だよ。

🙋

右の「制約セル数」と「メモリ削減 54%」というのは何ですか？窓幅を 100% にすると 8000 セル全部使うのに、20% にすると 3680 セルで済むみたいです。

🎓

それが Sakoe-Chiba 窓の効果だ。本来の DTW は N·M = 100·80 = 8000 セル全部を埋める必要があるけど、現実の音声や心電図では対応関係は対角線からそんなに外れない。だから「対角線から幅 w 以内のセルしか計算しない」と決め打ちすれば、計算量とメモリが大幅に減る。窓 20% なら 3680 セル、メモリ 54% 削減、スピードアップは 8000/3680 = 2.17 倍。組込み機器や数千点の長系列だとこの差が効くんだ。

🙋

じゃあ窓を 1% とか極端に狭くしたほうがいいんですか？スピードアップが 50 倍くらい出そうですけど。

🎓

それが落とし穴で、窓が狭すぎると本来の最適パスを窓の外に追い出してしまい、距離が大きく出てしまう。下の verdict が窓 5% 未満で warn になるのはそのため。経験則として、音声認識なら 5〜10%、歩行や心拍なら 10〜20%、未知データなら 20〜30% から始める。窓幅は「許せる速度変動の上限」を決めるパラメータだと思うといい。あとは検証データで誤識別率を測りつつ詰めていくんだ。

🙋

距離計量にユークリッド・マンハッタン・コサインの 3 つがあるのは、何のためですか？

🎓

セル間距離 d(x,y) の定義を変えるためだね。1 次元のスカラー時系列（温度、株価、音圧）なら自乗誤差のユークリッドが標準。外れ値が多いノイジーなデータならマンハッタン（L1）のほうが頑健で、ピーク値に引っ張られにくい。音声認識のメル係数 MFCC のような多次元ベクトル列では、絶対値より「向き」を比べたいのでコサイン距離がよく使われる。DTW の動的計画法の骨格は同じで、d だけを差し替えるんだ。同じ系列でも計量を変えるとパスもコストも変わるから、ぜひ切り替えて感触をつかんで。

よくある質問

要素ごとの L2 距離は、2 つの時系列を同じインデックスで縦に並べて差を取るため、わずかな速度差や位相ずれで距離が一気に増えます。長さが違うと比較すらできません。DTW は動的計画法でコスト行列 D を埋め、時間軸の伸縮を許した最適パスを探します。これにより「同じ歩行パターンを速度違いで歩いた 2 系列」が小さな距離になり、長さの異なる音声や心電図でも比較できます。本ツールでは N=100、M=80 のデフォルトで素朴な L2 が 101.0、DTW 距離が 1.2 と桁違いの差が出ることが確認できます。

Sakoe-Chiba 窓は対角線から幅 w までしかパスが逸脱できないという制約で、計算量とメモリを大幅に削減します。窓を 100% にすると全セルを使い元の DTW と同じ、0% にすると対角線のみで素朴な L2 距離に近づきます。実務では 5〜20% が定番で、音声・歩行のような速度変動の許容範囲を経験的に決めます。窓幅が小さすぎると本来の最適パスを外し誤マッチを起こすので、検証データで誤識別率を見ながら調整してください。

1 次元スカラーの時系列（温度・株価・音圧）ではユークリッドかマンハッタンを使い、外れ値の影響を抑えたい場合はマンハッタン（L1）が頑健です。多次元ベクトル系列（メル係数 MFCC のような特徴量）では、絶対大きさよりも「向き」を見たいことが多く、コサイン距離がよく使われます。本ツールでは d(x,y) の定義だけを切り替えるので、同じ系列でも距離計量によって最適パスとコストが変化することを体感できます。

古典的な DTW は O(N·M) で N,M が数千を超えると計算量・メモリとも厳しくなります。FastDTW は粗い解像度で大まかなパスを求め、それを徐々に詳細化することで O(N) を実現します。PrunedDTW は最小コストの上界を使って明らかに最適でないセルを枝刈りします。UCR-DTW はクエリ検索向けに正規化と早期打切りを徹底した実装です。N が数千〜数万なら FastDTW、データベース照合なら UCR-DTW、組込みなら Sakoe-Chiba 窓 + ピボット計算を素直に書く、が目安です。

実世界での応用

音声認識・話者照合：DTW のオリジナル用途であり、DARPA 音声認識プロジェクトで標準アルゴリズムとなりました。入力音声の MFCC 系列と辞書テンプレートを DTW で照合し、最小距離の単語を選びます。HMM や深層学習の登場後も、子供向け学習機・組込み音声コマンドのような少語彙・低リソース用途では DTW が依然として主流です。

心電図・脈波解析：患者の心拍は呼吸や体動で速度が揺らぐため、同じ不整脈パターンでも素朴な距離では検出できません。テンプレート心拍と被験者心拍を DTW で照合することで、心房細動・PVC（期外収縮）などの異常を高精度に拾えます。ホルター心電図の長時間記録から特定パターンを検索する場面でも標準です。

歩行解析・モーションキャプチャ：同じ被験者でも歩幅・速度が日によって違うため、加速度センサや IMU の時系列を直接比較するのは困難です。DTW で速度差を吸収すると、リハビリ前後の歩容変化、転倒予兆、特定運動パターンの認識が可能になります。スマートウォッチの転倒検出にも応用されています。

株価・センサー異常検知：金融時系列のチャートパターン認識（ヘッドアンドショルダー等）、製造装置の振動診断（モーター異音検出）、HVAC のエネルギー消費パターン比較など、「同じパターンが少し速度違いで現れる」場面はあらゆる産業に存在します。Numpy/Pandas + 軽量な DTW ライブラリで実装でき、教師なしで動かせるのが強みです。

よくある誤解と注意点

まず最大の落とし穴は、「DTW を使えば何でも比較できる」という誤解です。DTW は時間方向の伸縮を許しますが、振幅の差はそのままコストに乗ります。本ツールで「振幅倍率」を 50% や 200% にすると DTW 距離が増えるのはそのためです。実務では DTW にかける前に Z-score 正規化（平均 0、標準偏差 1）を必ず行うのが鉄則で、これを怠ると振幅違いの同パターンが誤って遠いと判定されます。UCR-DTW の論文でも、正規化なしの DTW 比較は「ベンチマークの不正」とまで言われています。

次に、「窓幅を広くするほど精度が上がる」という誤解。窓を広げると確かに本来の最適パスを外す危険は減りますが、同時にノイズによる「不自然な伸縮」（パスが対角から大きく外れて偽の対応関係を作る）も許してしまいます。Ratanamahatana らの大規模実験では、UCR データセットの多くで窓 5〜10% が最適で、それ以上広げても精度が頭打ちもしくは低下することが示されています。窓は狭めから始めて、検証データで誤識別率を見ながら徐々に広げるのが定石です。

最後に、「DTW 距離は本物の距離（メトリック）である」という誤解。DTW 距離は非負・対称性は満たしますが、三角不等式は満たしません（d(A,C) > d(A,B) + d(B,C) になりうる）。このため、kNN 検索で距離不等式に基づく高速化（メトリック木、VP-tree など）が使えません。最近傍検索を高速化したい場合は、LB_Keogh のような「下界（lower bound）」で候補を絞り込んでから DTW を計算する、という 2 段構えが標準テクニックです。本ツールでも実装上は LB_Keogh 相当の前処理が前提と考えてください。

動的時間伸縮 DTW シミュレーター

動的時間伸縮 (DTW) — 時系列パターンマッチング

よくある質問

実世界での応用

よくある誤解と注意点

使い方ガイド

具体的な計算例

実務での注意点