DTW определяет расстояние между временными рядами, учитывая сжатия и растяжения временной оси. Формально говоря, для рядов x = (x_1, ..., x_n) и y = (y_1, ..., y_m) рассматриваются монотонные пути pi в решётке {1, ..., n} * {1, ..., m}, начинающиеся в (1, 1) и заканчивающиеся в (n, m), и минимизируется суммарная стоимость(см фото).
DTW можно реализовать примерно так(dynamic programming btw):
def dtw(x, y):
n, m = len(x), len(y)
D = np.full((n + 1, m + 1), np.inf)
D[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], D[i, j - 1], D[i - 1, j - 1])
return D[n, m]
x = np.sin(np.linspace(0, 2 * np.pi, 100))
y = np.sin(np.linspace(0, 2 * np.pi, 80) + 0.3)
DTW не удовлетворяет неравенству треугольника и официально вообще не считается метрикой, что конечно ограничивает её применение во многих структурах и теоретически в TDA. Существуют исправленные версии, типа Lower Bound Keogh и soft-DTW Cuturi-Blondel, которые обеспечивают либо метрические свойства, либо дифференцируемость для использования в loss-функциях.
На практике, DTW применим к таким областям как speech recognition(разные говорящие, произносят слова с разной скоростью), в анализе мед данных(ЭКГ), а так же в анализе фин временных рядов.
#TDA101