「おはよう」とゆっくり言っても、早口で言っても、同じ「おはよう」です。心電図の波形も、心拍数が上がれば波形は時間方向に縮み、落ち着けば伸びますが、健康な心臓の拍動パターンであることに変わりはありません。人間はこうした時間軸の伸び縮みを無意識に吸収して「同じ形だ」と認識できます。ところが、コンピュータで2つの時系列をそのまま点ごとに比較すると、わずかな時間ズレだけで「全然違う波形」と判定されてしまいます。
この問題を解決するのが DTW（Dynamic Time Warping・動的時間伸縮法） です。時間軸を柔軟に伸縮させながら2つの時系列の「形」を最適に重ね合わせ、その上で距離を測ります。もともとは1970年代の音声認識（発話速度の違いを吸収して単語を照合する）で生まれた手法ですが、現在では
- 時系列分類・類似検索 — 「この波形に一番似ている過去の波形はどれか」を探す（1-NN DTWは長年、時系列分類の最強ベースラインでした）
- ジェスチャ・行動認識 — 加速度センサの波形から動作を認識する（動作の速さは人によって違う）
- 異常検知・品質管理 — 正常パターンとの DTW 距離が大きい波形を異常とみなす
など、時系列を扱うあらゆる分野で使われる基本道具になっています。
本記事の内容
- ユークリッド距離の何が問題で、DTWは何を解決するのか
- 整合パス（ワーピングパス）の定式化と3つの制約
- 動的計画法による漸化式の導出と手計算例
- Sakoe-Chibaバンドによる高速化と、バンド幅のトレードオフ
- DTWの落とし穴 — 特異点問題と「三角不等式を満たさない」こと
上の図が本記事の主役です。青い時系列 X と赤い時系列 Y は「同じ2つの山」を持ちますが、山の位置が時間方向にズレています。DTW は灰色の対応線のように、1つ目の山は1つ目の山と、2つ目の山は2つ目の山と対応づけ、そのうえで値の差を合計します。この「形が一番合う対応を探してから距離を測る」という2段構えが DTW の本質です。
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- k近傍法（k-NN）をわかりやすく解説 — DTWの代表的な使い道である「1-NN分類」の枠組み
- 標準化と正規化の違い — 実務でDTWを使う前の必須前処理
ユークリッド距離の何が問題か
まず、DTWが解決しようとしている問題を具体的に見ましょう。長さ $N$ の2つの時系列 $\bm{x} = (x_0, x_1, \dots, x_{N-1})$ と $\bm{y} = (y_0, y_1, \dots, y_{N-1})$ があるとき、最も素朴な距離はユークリッド距離です:
$$ d_{\mathrm{euc}}(\bm{x}, \bm{y}) = \sqrt{\sum_{i=0}^{N-1} (x_i – y_i)^2} $$
この式は「時刻 $i$ の値どうしを比べる」という対応を暗黙のうちに固定しています。$x_0$ は $y_0$ と、$x_1$ は $y_1$ と…という具合です。この「同時刻対応」は、2つの時系列が完全に同期しているときには自然ですが、時間軸が少しでもズレていると破綻します。
左の図では、同時刻を結ぶ対応線が「Xの山」と「Yの谷（山が過ぎた後）」を比べてしまっており、値の絶対差の合計は 15.55 に達します。右のDTWでは、形が合う点どうし（山と山、谷と谷）を対応づけるため、同じコスト関数（絶対差の和）で測った距離は 1.37 — 実に約11分の1です。2つの波形の「形」は同じなのですから、DTWの答えのほうが直感に合います。
ここで大事なのは、ユークリッド距離が「悪い」わけではないことです。問題は対応のとり方を固定していることにあります。では、対応のとり方そのものを最適化の対象にしたらどうなるでしょうか。これがDTWの出発点です。
整合パス — 「対応のとり方」を数学の言葉にする
DTWでは、2つの時系列の点どうしの対応関係を整合パス（warping path・ワーピングパス）と呼ばれる列で表します。長さ $N$ の $\bm{x}$ と長さ $M$ の $\bm{y}$（長さが違ってもよいのがDTWの利点です）に対して、整合パスは添字ペアの列
$$ \pi = \big( (i_0, j_0), (i_1, j_1), \dots, (i_{K-1}, j_{K-1}) \big) $$
です。「$(i, j)$ がパスに含まれる」とは「$x_i$ と $y_j$ を対応づけて比べる」という意味です。ただし、どんな対応でも許すわけではありません。時系列としての意味を保つために、次の3つの制約を課します。
- 境界条件: $(i_0, j_0) = (0, 0)$ かつ $(i_{K-1}, j_{K-1}) = (N-1, M-1)$。つまり両系列の先頭どうし・末尾どうしは必ず対応させ、全体を丸ごと照合します。
- 単調性: $i_{k+1} \geq i_k$ かつ $j_{k+1} \geq j_k$。時間を逆戻りする対応（Xの後半をYの前半と比べるような対応）は禁止します。
- 連続性（ステップサイズ）: $(i_{k+1} – i_k, \; j_{k+1} – j_k) \in \{(1, 0), (0, 1), (1, 1)\}$。1歩で進めるのは「上・右・斜め右上」のいずれかで、点を飛ばすことはできません。すべての点が少なくとも1回は使われます。
整合パスは、横軸に $\bm{y}$ の添字 $j$、縦軸に $\bm{x}$ の添字 $i$ をとった格子上の経路として描けます。左の緑のパスは3制約をすべて満たす正しい整合パスです。中央のように時間を逆戻りするパス（単調性違反）や、右のように点を飛ばすパス（連続性違反）は許されません。
この制約のもとで、パスが水平（$j$ だけ進む）に進む区間は「$\bm{x}$ の1点が $\bm{y}$ の複数点に対応する」= その部分で $\bm{x}$ を引き伸ばしていることを、垂直に進む区間はその逆を意味します。斜めに進む区間は1対1対応、つまり伸縮なしです。「時間軸の伸縮」が「格子上の経路の形」に翻訳されたことになります。
対応のとり方を経路として表現できたので、次は「良い対応」を選ぶ基準、すなわち最適化問題を立てましょう。
DTW距離の定義 — コスト行列上の最短経路問題
整合パス $\pi$ に沿って値の差を合計したものを、そのパスのコストと呼びます。まず点どうしの差を並べた局所コスト行列を定義します:
$$ d(i, j) = |x_i – y_j| $$
（絶対差の代わりに二乗差 $(x_i – y_j)^2$ を使う流儀もあります。本記事では図と数値をすべて絶対差で統一します。）このうえで、DTW距離は「すべての許される整合パスの中で最小のコスト」として定義されます:
$$ \mathrm{DTW}(\bm{x}, \bm{y}) = \min_{\pi \in \mathcal{P}} \sum_{(i, j) \in \pi} d(i, j) $$
ここで $\mathcal{P}$ は3制約を満たす整合パス全体の集合です。この式は「時間軸の伸縮をどう選んでも埋められない、形そのものの差」を測っていると読めます。伸縮で吸収できるズレはすべて吸収し、残った差だけを数える — これがDTW距離の意味です。
左が局所コスト行列 $d(i,j)$ です。暗い（コストが小さい）場所は「値が近い点の組」で、2つの山の対応関係が暗い谷筋として浮かび上がっています。DTWは、この行列の左下 $(0,0)$ から右上 $(N-1, M-1)$ まで、暗い場所を縫うように進む最安経路を探す問題です。右は後述の動的計画法で計算した累積コスト行列 $D(i,j)$ で、赤い線が見つかった最適経路。右上のセルの値がそのままDTW距離 1.37 になります。
ところで、この最小化は簡単ではありません。整合パスの本数は $N$ とともに指数的に爆発します（$N = M$ のときのパス数はデラノイ数と呼ばれ、$N=60$ では $10^{44}$ 本を超えます）。全列挙は論外です。ここで登場するのが動的計画法（DP）です。
動的計画法による解法 — 漸化式の導出
動的計画法の考え方はこうです。「$(i, j)$ にたどり着く最安経路」を直接探す代わりに、もっと小さい部分問題の答えから組み立てる。
そのために、累積コスト $D(i, j)$ を「$(0,0)$ から $(i,j)$ までの、制約を満たす部分パスの最小コスト」と定義します。求めたいDTW距離は $D(N-1, M-1)$ です。
ここで連続性の制約を思い出してください。$(i, j)$ に1歩でたどり着ける直前のセルは
- $(i-1, j)$ — 垂直移動（$\bm{x}$ 側を1つ進める）
- $(i, j-1)$ — 水平移動（$\bm{y}$ 側を1つ進める）
- $(i-1, j-1)$ — 斜め移動（両方進める）
の3つしかありません。$(i,j)$ に至る最安経路は、この3つのどれかを経由します。そして経由地までの部分も最安でなければ全体も最安になりません（部分最適性）。したがって:
$$ D(i, j) = d(i, j) + \min \big\{ D(i-1, j), \; D(i, j-1), \; D(i-1, j-1) \big\} $$
これがDTWの漸化式です。初期条件は境界条件から $D(0, 0) = d(0, 0)$、行列の下端と左端は選択肢が1方向しかないので
$$ D(i, 0) = d(i, 0) + D(i-1, 0), \qquad D(0, j) = d(0, j) + D(0, j-1) $$
となります。あとはこの漸化式を左下から右上へ順に埋めていくだけで、指数本のパスを調べることなく、$O(NM)$ の計算量で厳密な最小値が求まります。
左が漸化式の図解です。各セルは3方向の「入口」のうち累積コストが最小のものを引き継ぎます。右は次節で手計算する小さな例の累積コスト行列で、赤字が最適経路です。
漸化式が手に入ったので、実際に小さな例で手を動かして、計算の流れを体に入れましょう。
手計算例 — 5×4の行列を埋めてみる
$\bm{x} = (1, 3, 4, 2)$、$\bm{y} = (1, 2, 4, 4, 2)$ でDTW距離を計算します。$\bm{y}$ のほうが1点長く、「値4」が2回続いている（＝$\bm{x}$ の「4」が引き伸ばされた形）ことに注目してください。
まず1行目（$i=0$、$x_0 = 1$）。左端は $D(0,0) = |1-1| = 0$、あとは左から累積するだけです:
$$ D(0, \cdot) = (0, \; 1, \; 4, \; 7, \; 8) $$
2行目（$i=1$、$x_1 = 3$）に進みます。たとえば $D(1,1)$ は、局所コスト $|3-2| = 1$ に、3つの入口 $D(0,0)=0$、$D(0,1)=1$、$D(1,0)=2$ の最小値 $0$ を足して $1$ です。同様に埋めると:
$$ D(1, \cdot) = (2, \; 1, \; 2, \; 3, \; 4) $$
3行目（$x_2 = 4$）では $\bm{y}$ の連続する「4」と出会います。$D(2,2) = |4-4| + \min\{1, 2, 3\} = 0 + 1 = 1$、続く $D(2,3) = |4-4| + \min\{2, 3, 1\} = 0 + 1 = 1$。水平移動（$\bm{x}$ の1点を $\bm{y}$ の2点に対応させる伸縮）がコスト0で効いているのがわかります:
$$ D(2, \cdot) = (5, \; 3, \; 1, \; 1, \; 3) $$
最終行（$x_3 = 2$）も同様に埋めると:
$$ D(3, \cdot) = (6, \; 3, \; 3, \; 3, \; 1) $$
右上の値が答えです: $\mathrm{DTW}(\bm{x}, \bm{y}) = 1$。
最適経路は、右上から「どの入口から来たか」を逆にたどれば復元できます。この例では
$$ (0,0) \to (1,1) \to (2,2) \to (2,3) \to (3,4) $$
で、対応は「$1 \leftrightarrow 1$、$3 \leftrightarrow 2$、$4 \leftrightarrow 4$、$4 \leftrightarrow 4$（伸縮）、$2 \leftrightarrow 2$」。コストの内訳は $0 + 1 + 0 + 0 + 0 = 1$ で、行列の右上の値と一致します。ズレの実体は「3と2の差」だけで、時間軸の伸縮（4が2回続く部分）はコストゼロで吸収されたことが読み取れます。
計算の中身が見えたところで、実装を確認しておきましょう。漸化式そのままなので、驚くほど短く書けます。
Pythonでの実装
漸化式を素直にコードにします。番兵（$\infty$ の行と列）を足すと境界処理が消えてすっきりします。
import numpy as np
def dtw(x, y):
"""DTW距離と累積コスト行列を返す（コストは絶対差）"""
n, m = len(x), len(y)
D = np.full((n + 1, m + 1), np.inf)
D[0, 0] = 0.0
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = abs(x[i - 1] - y[j - 1])
D[i, j] = cost + min(D[i - 1, j], # 垂直（xを伸ばす）
D[i, j - 1], # 水平（yを伸ばす）
D[i - 1, j - 1]) # 斜め（1対1）
return D[n, m], D[1:, 1:]
x = np.array([1.0, 3.0, 4.0, 2.0])
y = np.array([1.0, 2.0, 4.0, 4.0, 2.0])
dist, D = dtw(x, y)
print(dist) # => 1.0（手計算と一致）
コードの心臓部は3行の min だけです。手計算例と同じ入力で走らせると距離 1.0 が返り、先ほど埋めた行列と完全に一致します。なお、この素朴な実装は2重ループなので大きな系列では遅くなります。実務では dtaidistance や tslearn といった高速なC実装のライブラリを使うのが定石です。
実装が動いたら、次は最適経路そのものを眺めてみましょう。経路の形には「どこをどれだけ伸縮したか」という情報がそのまま入っています。
整合パスの読み方 — 経路の形が伸縮の地図になる
左は冒頭の2山デモ（$N = 60$）の最適整合パスです。対角線（点線）は「同時刻対応＝伸縮なし」を表すので、経路が対角線から離れている場所ほど強い伸縮が起きています。序盤は対角線の上側（$\bm{x}$ が先行）、後半で下側に回り込んでおり、Yの山がXより早く来て、その後遅れる、という時間構造が経路の形から読み取れます。右の対応線でも、経路が水平・垂直に進む区間で1つの点が複数の点と結ばれている（＝伸縮）ことが確認できます。なお経路長は76組で、系列長60より長いのは伸縮（1対多対応)のぶんだけ対応の組数が増えるためです。
DTWの中身は以上で出揃いました。ただし実務投入の前に、計算量と「DTW特有のクセ」を知っておく必要があります。まずは計算量から見ていきます。
Sakoe-Chibaバンド — 計算量と病的な整合への対策
DTWの計算量 $O(NM)$ は、ユークリッド距離の $O(N)$ と比べるとかなり重い処理です。系列長1,000どうしなら100万セル。1本ずつなら問題になりませんが、データベース内の何万本もの系列と比較する検索の場面では致命的です。
そこで実務では、整合パスが通ってよい領域を対角線の近くに制限します。代表が Sakoe-Chibaバンド で、対角線から幅 $w$ 以内のセル、つまり $|i – j| \leq w$ のセルしか計算しません。もう1つの古典が Itakura平行四辺形で、こちらは経路の傾きを（標準的には）1/2〜2倍に制限するため、許容領域が平行四辺形になります。
緑がバンド内（計算する領域）です。左のSakoe-Chibaバンド（$w = 8$）では、計算するセルは全体のわずか26.3%で、最適経路（赤）はバンド内に収まっています。計算量は $O(NM)$ から $O(NW)$ に落ちます。右のItakura平行四辺形は始点・終点付近ほど狭く、「出だしと終わりは大きくズレないはず」という事前知識を表現しています。
バンドには高速化以外にもう1つ重要な効果があります。極端な伸縮（後述の特異点のような病的整合）を物理的に禁止することです。「心拍の波形が3倍以上伸び縮みすることはない」といったドメイン知識をバンド幅に込められるわけです。
では、バンド幅はどう選べばよいのでしょうか。狭いほど速い一方、狭すぎると本来の対応がバンドの外に出てしまい、距離が不正確になります。
冒頭の2山デモでバンド幅 $w$ を動かした結果です。左図: $w = 0$（同時刻対応に固定）では距離15.55ですが、$w$ を広げると急激に下がり、$w = 8$ で制約なしのDTW距離1.37に到達します。それ以上広げても距離は変わりません。右図: 一方、計算セル数は $w$ にほぼ比例して増え続けます。つまりこのデータでは $w = 8$ が「正確さを損なわない最小の計算量」です。実際のズレ幅より少し広めのバンドを選ぶのが実務の指針で、時系列分類のベンチマークでは $w$ を交差検証で選ぶと系列長の10%前後に落ち着くことが多い、と報告されています。
計算量の問題はバンドでかなり緩和できます。しかし、DTWにはもっと本質的な「クセ」が2つあります。知らずに使うと痛い目を見るポイントなので、順に見ていきましょう。
落とし穴1: 特異点問題 — 伸縮が「値の差」まで吸収してしまう
DTWの強みは時間軸の伸縮を吸収することでした。しかしこの能力は、ときに吸収してはいけない差まで吸収してしまいます。
左図は、位相は完全に同じで振幅だけが1.0と1.6に違う2つの正弦波のDTW対応です。本来の「正しい」対応は同時刻対応（整合パスなら対角線）のはずです。ところがDTWは、山の頂上付近で1つの点に10個もの点を対応させる極端な伸縮を選びました。右図の整合パスにも、水平・垂直の長い区間がはっきり現れています。振幅の差を正面から受け止めるより、値が近い点に大量に張り付くほうがコストが安いためです。この病的な1対多対応を特異点（singularity）と呼びます。
特異点への対策は主に3つ知られています。
- バンド制約: 前節のSakoe-Chibaバンドで極端な伸縮を物理的に禁止する（最も手軽で効果的）
- 微分DTW（DDTW）: 値そのものではなく微分（傾き）の差をコストにする。「上り坂は上り坂と対応すべき」という考え方
- 重み付きDTW: 対角移動を優遇する（水平・垂直移動にペナルティを課す）ことで、むやみな伸縮を抑える
いずれも「伸縮の自由度を適度に絞る」という方向の対策です。DTWの自由度は諸刃の剣である、と覚えておいてください。
もう1つの落とし穴は、より数学的な性質です。DTWを「距離」と呼んできましたが、実は数学的な意味での距離ではありません。
落とし穴2: DTWは三角不等式を満たさない
距離関数（距離公理を満たす関数）には、非負性・対称性・同一性に加えて三角不等式 $d(A, C) \leq d(A, B) + d(B, C)$ が要求されます。「寄り道をすると遠くなることはあっても近くなることはない」という、距離らしさの核心です。DTWはこれを満たしません。しかも、わざとらしい反例ではなく、ごく小さな例で破れます。
3つの系列 $A = (0)$、$B = (2)$、$C = (2, 2, 2)$ を考えます（この反例は長さ3以下・値 $\{0,1,2\}$ の全系列の総当たりで見つけた、違反量が最大のものです）。
- $\mathrm{DTW}(A, B) = |0 – 2| = 2$
- $\mathrm{DTW}(B, C) = 0$ — Bの1点がCの3点すべてに対応（伸縮）し、値は同じなのでコスト0
- $\mathrm{DTW}(A, C) = |0-2| \times 3 = 6$ — Aの1点がCの3点に対応し、差2を3回支払う
よって $\mathrm{DTW}(A, C) = 6 > 2 + 0 = \mathrm{DTW}(A, B) + \mathrm{DTW}(B, C)$ となり、三角不等式が破れています。カラクリは伸縮の非対称性です。$B \to C$ では伸縮がコスト0で済んだのに、$A \to C$ では伸縮のせいで同じ差を3回も数えることになりました。
「数学的に美しくない」だけの話ではありません。実務上の重要な帰結が2つあります。
- 三角不等式を前提とする高速化が使えない。ベクトル検索などで使われる多くの索引構造（メトリック索引）は三角不等式による枝刈りに依存しており、DTWには適用できません。DTW検索には専用の下界（LB_Keoghなど）による枝刈りが必要になります（続編で詳しく扱います）。
- k-meansのようなアルゴリズムで平均が定義しにくい。DTW空間での「平均系列」は自明でなく、DBA（DTW Barycenter Averaging）という専用の反復アルゴリズムが使われます。
なお、細かい注意として、$\mathrm{DTW}(\bm{x}, \bm{y}) = 0$ でも $\bm{x} = \bm{y}$ とは限りません（上の $B$ と $C$ がまさにそうです）。DTWは正確には距離ではなく「非類似度」ですが、慣例に従い本記事でもDTW距離と呼びました。
最後に、実務でDTWを使う際の前処理と発展形を短くまとめて、全体を締めくくります。
実務での注意と発展
z正規化はほぼ必須です。 DTWが吸収するのは時間軸のズレだけで、値方向のオフセットやスケール差はまったく吸収しません（特異点の例で見たとおり、むしろ病的整合の原因になります）。系列ごとに平均0・標準偏差1へ揃える z正規化（標準化）を、DTW計算の前に必ず入れるのが定石です。
発展形も簡単に紹介しておきます。
- FastDTW: 粗い解像度で経路を求め、細かい解像度でその近傍だけ精緻化する近似法。線形時間をうたいますが、近似誤差が問題になるケースも報告されており、「バンド付き厳密DTW」で十分なことも多いです。
- soft-DTW: $\min$ を滑らかな $\mathrm{softmin}$ に置き換えて微分可能にしたDTW。ニューラルネットワークの損失関数として使えます（SoftCLT のような対照学習でもDTWベースの類似度が活躍します）。
- DBA: DTW対応のもとで系列集合の「平均形状」を求めるアルゴリズム。DTW + k-means型クラスタリングの部品です。
まとめ
本記事では、DTW（動的時間伸縮法）を基礎から解説しました。
- ユークリッド距離は「同時刻対応」を固定するため時間軸のズレに弱い。DTWは対応のとり方そのものを最適化する（デモでは同じコスト関数で距離が約11分の1になった）
- 対応は整合パスとして定式化され、境界・単調性・連続性の3制約を満たす
- 最小コストのパスは動的計画法の漸化式 $D(i,j) = d(i,j) + \min\{D(i{-}1,j), D(i,j{-}1), D(i{-}1,j{-}1)\}$ で $O(NM)$ で厳密に求まる
- Sakoe-Chibaバンドで計算量を $O(NW)$ に削減でき、病的な伸縮の抑制にもなる
- 落とし穴は特異点（値の差を伸縮で吸収する病的整合）と三角不等式の不成立。前者はバンドや微分DTWで対策し、後者は検索の高速化戦略に効いてくる
DTWの最大の活躍の場は「大量の時系列から似た波形を探す」類似検索です。しかし三角不等式が使えない以上、素朴に全件DTW計算をするしかないのでしょうか？ 実はLB_Keoghと呼ばれる下界を使った強力な枝刈りがあり、これが「1-NN DTW」を長年最強の時系列分類器たらしめた立役者です。続編で徹底的に解説します。
次のステップとして、以下の記事も参考にしてください。