PythonでのDTW（動的時間伸縮法）実装ガイド：numpyフルスクラッチとライブラリの使い分け

DTW（動的時間伸縮法、Dynamic Time Warping）は、長さや進む速さが揃わない2つの時系列データの類似度を測るアルゴリズムです。波形が時間方向に伸び縮みしていても、対応する点どうしを柔軟に対応づけて距離を計算できます。本記事ではPythonでDTWを実装する2つの道筋——numpyによるフルスクラッチと、fastdtwやtslearnなどのライブラリ利用——を、DTW距離の計算過程・計算量の課題・ライブラリの選び方・応用と注意点まで一通り解説します。なお検索語「DTW」にはデトロイト都市圏空港（IATAコード:DTW）の意味もありますが、ここで扱うのは時系列解析のDTWです。

まとめ：PythonでのDTW実装の要点

• 仕組みを理解したいならnumpyでフルスクラッチ。累積コスト行列を動的計画法で埋め、最小経路（ワーピングパス）をたどればDTW距離が求まります。
• 実務で使うならライブラリ一択。手軽さならfastdtw、速度と窓制約ならdtaidistance、多変量や機械学習ならtslearn、音声ならlibrosaを選びます。
• fastdtwは計算量O(N)の近似で、厳密なDTWではありません。精度を重視する用途では厳密実装のライブラリを使います。
• 厳密DTWの計算量はO(NM)で系列が長いと重く、Sakoe-Chiba制約（窓）で実用的な速度に落とします。
• scipyにDTWそのものの関数はなく、局所距離（ユークリッド距離など）の計算に使います。

以下、概念→アルゴリズム→numpy実装→ライブラリ比較→応用と注意点の順に掘り下げます。

DTW（動的時間伸縮法）とは：ユークリッド距離との違い

DTWは、2つの時系列を時間軸方向に「伸縮」させながら、もっとも対応のとれる点どうしを結んで距離を測る手法です。同じ動作でもテンポが違う、同じ単語でも発話速度が違う——こうした時間方向のズレを吸収して類似度を測れる点が最大の特徴です。

単純なユークリッド距離は、2つの系列を同じ時刻どうしで一対一に比較します。そのため片方が少し前後にずれただけで距離が大きく出てしまい、長さの違う系列は比較すらできません。DTWは一対多の対応（1つの点が相手の複数点に対応してよい）を許すことで、この弱点を解消します。たとえば「ゆっくり手を振る」と「速く手を振る」が同じジェスチャだと判定できるのはDTWならではです。

時系列データの前処理や特徴量づくりの基礎はPython Pandasで何ができるのかでも触れており、DTWに渡す前のデータ整形に役立ちます。

DTW距離の計算アルゴリズム：動的計画法による累積コスト

DTWの核心は、2系列のすべての点の組み合わせについて距離を求め、その中から累積距離が最小になる経路を動的計画法で探すことです。計算は3ステップに分かれます。

局所コストと累積コスト行列の漸化式

まず2系列の各点ペア間の距離（局所コスト）を求めます。1次元なら差の絶対値、多次元ならユークリッド距離が一般的です。次に、左下から右上へ累積コスト行列 D を埋めていきます。セル D(i, j) は次の漸化式で決まります。

D(i, j) = 局所コスト(i, j) + min( D(i-1, j), D(i, j-1), D(i-1, j-1) )

つまり「真下・左・左下」の3方向のうち、これまでの累積コストが最小の経路を選んで現在の局所コストを足し込みます。最終セル D(n, m) の値が、2系列全体のDTW距離です。

ワーピングパスと制約条件

累積コスト行列を右上から左下へ逆たどり（バックトラック）すると、どの点とどの点が対応したかを示す経路＝ワーピングパスが得られます。このパスには3つの制約が課されます。境界条件（両端どうしを必ず対応させる）、単調性（時間が逆行しない）、連続性（対応を飛ばさず隣接セルのみ進む）です。これらにより、対応づけが時系列としての順序を壊さないことが保証されます。

PythonでDTWをnumpyからフルスクラッチ実装する

アルゴリズムを理解する近道は、ライブラリを使わずnumpyだけで書いてみることです。長さの違う2系列でも動きます。

numpyによるDTW距離の実装コード

import numpy as np

def dtw_distance(a, b):
    n, m = len(a), len(b)
    # 累積コスト行列を無限大で初期化（先頭だけ0）
    acc = np.full((n + 1, m + 1), np.inf)
    acc[0, 0] = 0.0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = abs(a[i - 1] - b[j - 1])   # 局所コスト
            acc[i, j] = cost + min(
                acc[i - 1, j],      # 真下（挿入）
                acc[i, j - 1],      # 左（削除）
                acc[i - 1, j - 1],  # 左下（一致）
            )
    return acc[n, m], acc

a = np.array([1, 2, 3, 4, 3, 2, 1])
b = np.array([1, 1, 2, 3, 4, 3, 2, 1])  # aより1点長く、少し後ろにずれた波形
distance, acc = dtw_distance(a, b)
print(distance)   # 0.0（時間方向のズレを吸収して同一波形と判定）

ユークリッド距離なら長さ違いで計算できず、ズレた分だけ距離が出ます。DTWはこの例で距離0、つまり「同じ形」と正しく判定します。

ワーピングパスの抽出と可視化

対応関係を見たいときは、累積コスト行列をバックトラックしてパスを取り出し、matplotlibで2波形を結ぶ線として描くと直感的です。

def warping_path(acc):
    i, j = acc.shape[0] - 1, acc.shape[1] - 1
    path = [(i - 1, j - 1)]
    while i > 1 or j > 1:
        step = np.argmin([acc[i-1, j-1], acc[i-1, j], acc[i, j-1]])
        if step == 0:
            i, j = i - 1, j - 1   # 左下
        elif step == 1:
            i = i - 1             # 真下
        else:
            j = j - 1             # 左
        path.append((i - 1, j - 1))
    return path[::-1]

描画の基礎はPythonのmatplotlibとはで確認できます。出力では2つの波形が上下に並び、対応点どうしを結ぶ線が両者を渡します。線が斜めに走るほど時間方向に大きく伸縮して対応づけられたことを意味します。累積コスト行列そのものをimshowでヒートマップ表示すると、左下から右上へ伸びる最小経路が暗い帯として浮かび上がり、ワーピングパスを視覚的に確認できます。

DTWライブラリの選び方：fastdtw・tslearn・dtaidistanceの比較

実務では自作せず、用途に合うライブラリを使います。代表的な選択肢の違いを整理します。

表の「速度」は実装方式に由来します。fastdtwは純PythonのO(N)近似、dtw-pythonはRのdtwパッケージ移植で多機能な反面ベンチマークではaeonやtslearnの約5倍遅いと報告されています。一方dtaidistanceはCythonとNumbaで実装されており、Numbaの概要と特徴で解説されるJITコンパイルとC実装が速度の源泉です。選び方の基準ははっきりしています。まず試すならfastdtw、本番で速度が要るならdtaidistance、機械学習や多変量時系列ならtslearn、音声・音楽信号ならlibrosaです。

fastdtwの実装と近似の注意点

fastdtwはSalvadorとChanが提案した近似アルゴリズムで、計算量をO(N)に抑えます。1次元の系列ならdist引数を省くだけで、既定の差の絶対値を局所コストとして距離を計算できます。

from fastdtw import fastdtw
import numpy as np

a = np.array([1, 2, 3, 4, 3, 2, 1])
b = np.array([1, 1, 2, 3, 4, 3, 2, 1])
distance, path = fastdtw(a, b)   # 1次元系列は dist 省略でOK（差の絶対値）
print(distance)   # 近似DTW距離（厳密値とは限らない）

各時点がベクトルになる多変量系列では、2次元配列にしてdist=euclideanのように距離関数を渡します。逆に1次元配列のままdist=euclidean（scipy.spatial.distance.euclidean）を渡すと、現行のscipyでは「Input vector should be 1-D」エラーになるため、1次元ではdistを省くかdist=2を指定します。

注意したいのは、fastdtwは名前のとおり近似であり厳密なDTWではない点です。複数ライブラリを比較した検証では、誤差は通常20%未満に収まる一方、精度・速度ともにdtaidistanceやtslearnの厳密実装に劣後する結果が報告されています。短い系列や厳密な距離が要る場面では、近似ではなく厳密実装を選ぶべきです。

DTWの課題：計算量とSakoe-Chiba制約による高速化

厳密DTWの弱点は計算量です。長さ N と M の系列を比べると累積コスト行列は N×M セルあり、計算量はO(NM)、両者がほぼ同じ長さならO(N²)になります。数千点規模の系列を多数比較すると、この二乗オーダーが現実的な壁になります。

高速化の王道がSakoe-Chiba bandです。ワーピングパスが対角線から大きく外れないよう、対角の上下に幅 w の帯を設けて探索範囲を制限します。これにより計算量はO(N·w)に下がり、同時に「時間方向のズレは現実的な範囲に限る」という事前知識を反映できます。tslearnやdtaidistanceでは窓パラメータで指定できます。

from dtaidistance import dtw
import numpy as np

a = np.array([1.0, 2, 3, 4, 3, 2, 1])
b = np.array([1.0, 1, 2, 3, 4, 3, 2, 1])
distance = dtw.distance(a, b, window=2)   # Sakoe-Chiba band: 帯幅2に制限
print(distance)

もう一方の古典的制約がItakura parallelogram（平行四辺形状に探索範囲を絞る）で、tslearnでは制約の種類としてSakoe-ChibaとItakuraのどちらも指定できます。前処理も精度に効きます。スケールの異なる系列はz-score正規化で揃え、ノイズが大きい場合は移動平均などで平滑化してからDTWにかけると、無関係な点どうしの誤対応を減らせます。

DTWの応用分野と、使うべきでない場面

主な応用分野

DTWは「速さの違う同じパターン」を見つけたいあらゆる場面で使われます。代表例は次のとおりです。

• 音声・話者認識：発話速度が違っても同じ単語を照合する。DTWが広まった原点の分野です。
• ジェスチャ・動作認識：ウェアラブル端末の加速度センサ波形から、テンポの違う同じ動作を識別する。
• 金融時系列：似たチャートパターンの探索。長さや時間軸の異なる値動きの形を比較できます。
• ヘルスケア・センサ：心拍や歩行波形など、個人差で周期が揺れる生体信号の照合。

時系列予測そのものを行いたい場合は、DTWよりProphet（Facebook開発の時系列予測ライブラリ）のような予測特化のツールが適します。DTWはあくまで「形の類似度」を測る手法です。

DTWが向かない場面

DTWは万能ではありません。次の条件では採用を見送るべきです。第一に、絶対的な時刻のズレ自体が意味を持つデータ。たとえば「何時に発生したか」が重要なログ照合では、時間を伸縮させて合わせるDTWは逆効果になります。第二に、数万点を超える長大な系列を大量に総当たりするケース。窓制約を入れてもO(N·w)が積み上がり、特徴量に圧縮してユークリッド距離やコサイン類似度で済ませたほうが速いことが多いです。第三に、振幅の絶対値の差を区別したい場合。DTWは形のズレに寛容な反面、正規化すると振幅差を吸収してしまうため、大きさそのものを比較したいなら不向きです。DTWは「時間方向の伸縮を許して形を比べたい」ときに限って強い、という割り切りが実務では有効です。

よくある質問（FAQ）

DTWとユークリッド距離は何が違いますか？

ユークリッド距離は2系列を同じ時刻どうしで一対一に比較するため、波形が前後にずれたり長さが違ったりすると正しく類似度を測れません。DTWは時間軸を伸縮させて対応点を柔軟に選ぶため、テンポや長さの違う「同じ形」を同一と判定できます。逆に、時刻のズレ自体に意味があるデータではユークリッド距離のほうが適切です。

fastdtw・dtw-python・tslearnのどれを使うべきですか？

手軽さ優先で近似でよいならfastdtw、厳密な距離と豊富な可視化機能が要るならdtw-python、機械学習や多変量時系列に組み込むならtslearnです。速度を最重視するならdtaidistanceが有力です。fastdtwは近似のため、厳密性が必要な場面では厳密実装のライブラリを選んでください。

scipyにDTWの関数はありますか？

scipy本体にDTWそのものの関数はありません。scipy.spatial.distance.euclideanのような距離関数を、DTWの局所コスト計算部分に渡して使うのが一般的な役割です。DTW全体を計算したい場合は、fastdtw・tslearn・dtaidistanceなどDTW専用ライブラリを利用します。

DTWの「DTW」はデトロイト空港のことですか？

文脈によります。時系列解析・機械学習の文脈ではDynamic Time Warping（動的時間伸縮法）を指します。一方、航空・旅行の文脈ではデトロイト・メトロポリタン・ウェイン郡空港のIATAコードもDTWです。本記事は前者、Pythonで実装するアルゴリズムとしてのDTWを扱っています。

DTW距離は系列の長さで正規化すべきですか？

長さの異なる系列どうしを比較する場合は、ワーピングパスの長さで割って正規化すると、系列が長いほど距離が大きく出る偏りを抑えられます。ただし正規化は振幅の絶対差も薄めるため、大きさそのものを比較したい用途では生のDTW距離を使う、と目的に応じて使い分けます。

関連記事

• Prophetとは｜Facebook（Meta）が開発した時系列予測ライブラリの仕組みと使い方
• Python Pandasで何ができるのか？具体的な機能と用途を解説
• Matplotlibとは？Pythonでグラフを描く使い方を入門から実践まで解説
• Numbaの概要と特徴：Pythonのパフォーマンスを劇的に向上させるツール
• 機械学習とは？初心者向けに基本概念と仕組みをわかりやすく解説