Алгоритм динамической трансформации временной шкалы

Алгоритм динамической трансформации временно́й шкалы (DTW-алгоритм, от англ. dynamic time warping) — алгоритм, позволяющий найти оптимальное соответствие между временными последовательностями. Впервые применен в распознавании речи, где использован для определения того, как два речевых сигнала представляют одну и ту же исходную произнесённую фразу. Впоследствии были найдены применения и в других областях.

Временные ряды — широко распространенный тип данных^{[уточнить]}, встречающийся, фактически, в любой научной области, и сравнение двух последовательностей является стандартной задачей. Для вычисления отклонения бывает достаточно простого измерения расстояния между компонентами двух последовательностей (евклидово расстояние). Однако часто две последовательности имеют приблизительно одинаковые общие формы, но эти формы не выровнены по оси X. Чтобы определить подобие между такими последовательностями, мы должны «деформировать» ось времени одной (или обеих) последовательности, чтобы достигнуть лучшего выравнивания.

Алгоритм

сопоставление евклидовой метрикой; сопоставление DTW алгоритмом

Измерение расстояния между двумя временными рядами нужно для того, чтобы определить их подобие и классификацию. Таким эффективным измерением является евклидова метрика. Для двух временных последовательностей это просто сумма квадратов расстояний от каждой n-ой точки одной последовательности до n-ой точки другой. Однако использование евклидова расстояния имеет существенный недостаток: если два временных ряда одинаковы, но один из них незначительно смещен во времени (вдоль оси времени), то евклидова метрика может посчитать, что ряды отличаются друг от друга. DTW-алгоритм был введён для того, чтобы преодолеть этот недостаток и предоставить наглядное измерение расстояния между рядами, не обращая внимание как на глобальные, так и на локальные сдвиги на временной шкале.

Классический алгоритм

Рассмотрим два временных ряда — $Q$ длины $n$ и $C$ длины $m$:

$Q=q_{1},q_{2},\ldots ,q_{i},\ldots ,q_{n};\qquad \qquad (1)$

$C=c_{1},c_{2},\ldots ,c_{j},\ldots ,c_{m}.\qquad \qquad (2)$

Первый этап алгоритма состоит в следующем. Мы строим матрицу $d$ порядка $n\times m$ (матрицу расстояний), в которой элемент $d_{i\;j}$ есть расстояние $d(q_{i},c_{j})$ между двумя точками $q_{i}$ и $c_{j}$. Обычно используется евклидово расстояние: $d(q_{i},c_{j})=(q_{i}-c_{j})^{2}\quad$, или $d(q_{i},c_{j})=|q_{i}-c_{j}|$. Каждый элемент $(i,j)$ матрицы соответствует выравниванию между точками $q_{i}$ и $c_{j}$.

GIF — анимация, показывающая построение матрицы трансформаций и выбор оптимального пути трансформации

На втором этапе строим матрицу трансформаций (деформаций)$D$, каждый элемент которой вычисляется исходя из следующего соотношения:

$D_{i\;j}=d_{i\;j}+min({D_{i-1\;j},D_{i-1\;j-1},D_{i\;j-1}}).\qquad (3)$

После заполнения матрицы трансформации, мы переходим к заключительному этапу, который заключается в том, чтобы построить некоторый оптимальный путь трансформации (деформации) и DTW расстояние (стоимость пути).
Путь трансформации $W$ — это набор смежных элементов матрицы, который устанавливает соответствие между $Q$ и $C$. Он представляет собой путь, который минимизирует общее расстояние между $Q$ и $C$. $k$-ый элемент пути $W$ определяется как $w_{k}=(i,j)_{k},\quad d(w_{k})=d(q_{i},c_{j})=(q_{i}-c_{j})^{2}$.
Таким образом:

$W=w_{1},w_{2},\ldots ,w_{k},\ldots ,w_{K};\qquad max(m,n)\leqslant K<m+n,$

где $K$ — длина пути.

Путь трансформации должен удовлетворять следующим ограничивающим условиям:

• Граничные условия: начало пути $w_{1}=(1,1)$, его конец — $w_{K}=(n,m)$. Это ограничение гарантирует, что путь трансформации содержит все точки обоих временных рядов.
• Непрерывность (условие на длину шага): любые два смежных элемента пути $W$, $w_{k}=(w_{i},w_{j})$ и $w_{k+1}=(w_{i+1},w_{j+1})$, удовлетворяют следующим неравенствам: $w_{i}-w_{i+1}\leqslant 1$, $w_{j}-w_{j+1}\leqslant 1$. Это ограничение гарантирует, что путь трансформации передвигается на один шаг за один раз. То есть оба индекса $i$ и $j$ могут увеличиться только на 1 на каждом шаге пути.
• Монотонность: любые два смежных элемента пути $W$, $w_{k}=(w_{i},w_{j})$ и $w_{k-1}=(w_{i-1},w_{j-1})$, удовлетворяют следующим неравенствам: $w_{i}-w_{i-1}\geqslant 0$, $w_{j}-w_{j-1}\geqslant 0$. Это ограничение гарантирует, что путь трансформации не будет возвращаться назад к пройденной точке. То есть оба индекса $i$ и $j$ либо остаются неизменными, либо увеличиваются (но никогда не уменьшаются).

Хотя существует большое количество путей трансформации, удовлетворяющих всем вышеуказанным условиям, однако нас интересуют только тот путь, который минимизирует DTW расстояние (стоимость пути).

DTW расстояние (стоимость пути) между двумя последовательностями рассчитывается на основе оптимального пути трансформации с помощью формулы:

$DTW(Q,C)=min\left\{{\frac {\sum \limits _{k=1}^{K}{d(w_{k})}}{K}}\right\}.\qquad (4)$

$K$ в знаменателе используется для учёта того, что пути трансформации могут быть различной длины.

Пространственная и временная сложность алгоритма — квадратичная, $O(nm)$, так как DTW алгоритм должен изучить каждую клетку матрицы трансформации.

Недостатки алгоритма

Хотя алгоритм успешно используется во многих областях, он может выдавать неправильные результаты. Алгоритм может попытаться объяснить непостоянство оси $y$ с помощью трансформации оси $x$. Это может привести к выравниванию, при котором одной точке первой последовательности ставится в соответствие большая подгруппа точек второй последовательности.

Другая проблема заключается в том, что алгоритм может не найти очевидное выравнивание двух рядов вследствие того, что особая точка (пик, впадина, плато, точка перегиба) одного ряда расположена немного выше или ниже соответствующей ей особой точки другого ряда.

Разновидности DTW алгоритма

Различные доработки DTW алгоритма предназначены для ускорения его вычислений, а также для того, чтобы лучше контролировать возможные маршруты путей трансформации.

Общие (глобальные) ограничения

Один из распространенных вариантов DTW алгоритма — наложение общих (глобальных) ограничивающих условий на допустимые пути деформации. Пусть $R\subseteq [1:n]\times [1:m]$ — подмножество, задающее область глобального ограничения. Теперь путём трансформации является путь, который содержится в области $R$. Оптимальный путь трансформации — путь, принадлежащий $R$, и минимизирующий стоимость пути среди всех путей трансформации из $R$.

Быстрый DTW-алгоритм

Этот алгоритм обладает линейной пространственной и временной сложностью. Быстрый DTW алгоритм использует многоуровневый подход с тремя ключевыми операциями:

1. Уменьшение детализации — уменьшаем размер временного ряда с помощью усреднения смежных пар точек. Полученный временной ряд — это ряд, имеющий в два раза меньше точек, чем исходный. Мы проводим эту операцию несколько раз, чтобы получить много различных разрешений временного ряда.
2. Планирование — берем путь трансформации при низкой детализации и определяем через какие клетки будет проходить путь трансформации при следующей детализации (на порядок выше предыдущей). Так как разрешение увеличивается в два раза, одной точке, принадлежащей пути трансформации в низком разрешении, будут соответствовать, по крайней мере, четыре точки в большем разрешении. Затем этот планируемый путь используется в качестве эвристического правила в процессе обработки, чтобы найти путь в высоком разрешении.
3. Обработка — поиск оптимального пути деформации в окрестности спланированного пути.

Разреженный DTW-алгоритм

Основная идея данного метода состоит в том, чтобы динамически использовать наличие подобия и/или сопоставления данных для двух временных последовательностей. Данный алгоритм имеет три особых преимущества:

1. Матрица трансформации представляется с помощью разреженных матриц, что приводит к уменьшению средней пространственной сложности по сравнению с другими методами.
2. Разреженный DTW алгоритм всегда выдает оптимальный путь трансформации.
3. Так как алгоритм выдает оптимальное выравнивание, то он может быть легко использован в сочетании с другими методами.

Области применения

• распознавание речи
• интеллектуальный анализ данных
• распознавание жестов
• робототехника
• медицина
• биоинформатика
• верификация подписи