Введение
Алгоритм измерения сходства между двумя временными последовательностями, которые могут различаться по скорости. В анализе временных рядов динамическое программирование временных искажений (DTW) — это алгоритм для измерения сходства между двумя временными последовательностями, которые могут различаться по скорости. Например, с помощью DTW можно обнаружить сходство в походке, даже если один человек идет быстрее другого, или если в процессе наблюдения присутствуют ускорения и замедления. DTW применяется к временным последовательностям видео-, аудио- и графических данных — фактически, любые данные, которые можно преобразовать в одномерную последовательность, могут быть проанализированы с помощью DTW. Хорошо известным применением является автоматическое распознавание речи для учета различной скорости речи. Другие области применения включают распознавание диктора и распознавание подписи в режиме онлайн. Его также можно использовать в приложениях частичного сопоставления форм. В общем, DTW — это метод, который вычисляет оптимальное соответствие между двумя заданными последовательностями (например, временными рядами) с определенными ограничениями и правилами:
In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences, which may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walking faster than the other, or if there were accelerations and decelerations during the course of an observation. DTW has been applied to temporal sequences of video, audio, and graphics data — indeed, any data that can be turned into a one dimensional sequence can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds. Other applications include speaker recognition and online signature recognition. It can also be used in partial shape matching applications. In general, DTW is a method that calculates an optimal match between two given sequences (e. g. time series) with certain restriction and rules:
Every index from the first sequence must be matched with one or more indices from the other sequence, and vice versa
The first index from the first sequence must be matched with the first index from the other sequence (but it does not have to be its only match)
The last index from the first sequence must be matched with the last index from the other sequence (but it does not have to be its only match)
The mapping of the indices from the first sequence to indices from the other sequence must be monotonically increasing, and vice versa, i. e. if are indices from the first sequence, then there must not be two indices in the other sequence, such that index is matched with index and index is matched with index , and vice versa
We can plot each match between the sequences and as a path in a matrix from to , such that each step is one of In this formulation, we see that the number of possible matches is the Delannoy number. The optimal match is the match that satisfies all the restrictions and the rules and that has the minimal cost, where the cost is computed as the sum of absolute differences, for each matched pair of indices, between their values. The sequences are "warped" non linearly in the time dimension to determine a measure of their similarity independent of certain non linear variations in the time dimension. This sequence alignment method is often used in time series classification. Although DTW measures a distance like quantity between two given sequences, it doesn't guarantee the triangle inequality to hold. In addition to a similarity measure between the two sequences, a so called "warping path" is produced. By warping according to this path the two signals may be aligned in time. The signal with an original set of points X(original), Y(original) is transformed to X(warped), Y(warped). This finds applications in genetic sequence and audio synchronisation. In a related technique sequences of varying speed may be averaged using this technique see the average sequence section. This is conceptually very similar to the Needleman–Wunsch algorithm.
Каждый индекс из первой последовательности должен быть сопоставлен с одним или несколькими индексами из другой последовательности, и наоборот.
Первый индекс из первой последовательности должен быть сопоставлен с первым индексом из другой последовательности (но не обязательно только с ним).
Последний индекс из первой последовательности должен быть сопоставлен с последним индексом из другой последовательности (но не обязательно только с ним).
Сопоставление индексов из первой последовательности с индексами из другой последовательности должно быть монотонно возрастающим, и наоборот, то есть, если и — индексы из первой последовательности, то не должно быть двух индексов и в другой последовательности, таких что индекс сопоставлен с индексом , а индекс сопоставлен с индексом , и наоборот.
In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences, which may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walking faster than the other, or if there were accelerations and decelerations during the course of an observation. DTW has been applied to temporal sequences of video, audio, and graphics data — indeed, any data that can be turned into a one dimensional sequence can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds. Other applications include speaker recognition and online signature recognition. It can also be used in partial shape matching applications. In general, DTW is a method that calculates an optimal match between two given sequences (e. g. time series) with certain restriction and rules:
Every index from the first sequence must be matched with one or more indices from the other sequence, and vice versa
The first index from the first sequence must be matched with the first index from the other sequence (but it does not have to be its only match)
The last index from the first sequence must be matched with the last index from the other sequence (but it does not have to be its only match)
The mapping of the indices from the first sequence to indices from the other sequence must be monotonically increasing, and vice versa, i. e. if are indices from the first sequence, then there must not be two indices in the other sequence, such that index is matched with index and index is matched with index , and vice versa
We can plot each match between the sequences and as a path in a matrix from to , such that each step is one of In this formulation, we see that the number of possible matches is the Delannoy number. The optimal match is the match that satisfies all the restrictions and the rules and that has the minimal cost, where the cost is computed as the sum of absolute differences, for each matched pair of indices, between their values. The sequences are "warped" non linearly in the time dimension to determine a measure of their similarity independent of certain non linear variations in the time dimension. This sequence alignment method is often used in time series classification. Although DTW measures a distance like quantity between two given sequences, it doesn't guarantee the triangle inequality to hold. In addition to a similarity measure between the two sequences, a so called "warping path" is produced. By warping according to this path the two signals may be aligned in time. The signal with an original set of points X(original), Y(original) is transformed to X(warped), Y(warped). This finds applications in genetic sequence and audio synchronisation. In a related technique sequences of varying speed may be averaged using this technique see the average sequence section. This is conceptually very similar to the Needleman–Wunsch algorithm.
Мы можем представить каждое соответствие между последовательностями и как путь в матрице от до , где каждый шаг — один из . В этой формулировке мы видим, что количество возможных соответствий — это число Деланнуа. Оптимальное соответствие — это соответствие, которое удовлетворяет всем ограничениям и правилам и имеет минимальную стоимость, где стоимость вычисляется как сумма абсолютных разностей между значениями для каждой сопоставленной пары индексов. Последовательности "искажаются" нелинейно во временном измерении, чтобы определить меру их сходства, не зависящую от определенных нелинейных изменений во временном измерении. Этот метод выравнивания последовательностей часто используется в классификации временных рядов. Хотя DTW измеряет величину, подобную расстоянию, между двумя заданными последовательностями, он не гарантирует, что неравенство треугольника будет выполняться. В дополнение к мере сходства между двумя последовательностями генерируется так называемый "путь искажения". Искажая последовательности в соответствии с этим путем, два сигнала можно выровнять по времени. Сигнал с исходным набором точек X(original), Y(original) преобразуется в X(warped), Y(warped). Это находит применение в генетических последовательностях и синхронизации аудио. В связанной технике последовательности с изменяющейся скоростью можно усреднять, используя этот метод (см. раздел "Средняя последовательность"). Это концептуально очень похоже на алгоритм Нидлмана — Вунша.
In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences, which may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walking faster than the other, or if there were accelerations and decelerations during the course of an observation. DTW has been applied to temporal sequences of video, audio, and graphics data — indeed, any data that can be turned into a one dimensional sequence can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds. Other applications include speaker recognition and online signature recognition. It can also be used in partial shape matching applications. In general, DTW is a method that calculates an optimal match between two given sequences (e. g. time series) with certain restriction and rules:
Every index from the first sequence must be matched with one or more indices from the other sequence, and vice versa
The first index from the first sequence must be matched with the first index from the other sequence (but it does not have to be its only match)
The last index from the first sequence must be matched with the last index from the other sequence (but it does not have to be its only match)
The mapping of the indices from the first sequence to indices from the other sequence must be monotonically increasing, and vice versa, i. e. if are indices from the first sequence, then there must not be two indices in the other sequence, such that index is matched with index and index is matched with index , and vice versa
We can plot each match between the sequences and as a path in a matrix from to , such that each step is one of In this formulation, we see that the number of possible matches is the Delannoy number. The optimal match is the match that satisfies all the restrictions and the rules and that has the minimal cost, where the cost is computed as the sum of absolute differences, for each matched pair of indices, between their values. The sequences are "warped" non linearly in the time dimension to determine a measure of their similarity independent of certain non linear variations in the time dimension. This sequence alignment method is often used in time series classification. Although DTW measures a distance like quantity between two given sequences, it doesn't guarantee the triangle inequality to hold. In addition to a similarity measure between the two sequences, a so called "warping path" is produced. By warping according to this path the two signals may be aligned in time. The signal with an original set of points X(original), Y(original) is transformed to X(warped), Y(warped). This finds applications in genetic sequence and audio synchronisation. In a related technique sequences of varying speed may be averaged using this technique see the average sequence section. This is conceptually very similar to the Needleman–Wunsch algorithm.
Свойства деформации
Алгоритм DTW обеспечивает дискретное сопоставление существующих элементов одной последовательности с другой. Иными словами, он не допускает масштабирования временной шкалы сегментов внутри последовательности. Другие методы позволяют осуществлять непрерывную варьировку. Например, корреляционно-оптимизированная варьировка (COW) разбивает последовательность на однородные сегменты, которые масштабируются по времени с использованием линейной интерполяции для достижения наилучшего соответствия. Масштабирование сегментов может приводить к потенциальному созданию новых элементов за счет сжатия или растяжения сегментов по времени, что обеспечивает более чувствительную варьировку по сравнению с дискретным сопоставлением исходных элементов, выполняемым алгоритмом DTW.
Сложность
Временная сложность алгоритма DTW составляет , где и — длины двух входных последовательностей. 50-летнее квадратичное ограничение по времени было преодолено в 2016 году: алгоритм, предложенный Голдом и Шариром, позволяет вычислить DTW за время и объем памяти для двух входных последовательностей длины . Этот алгоритм также может быть адаптирован для последовательностей различной длины. Несмотря на это улучшение, было показано, что сильно субквадратичное время работы вида для некоторого не может существовать, если не окажется ложной гипотеза о сильном экспоненциальном времени. В то время как алгоритм динамического программирования для DTW требует памяти в наивной реализации, использование алгоритма Хиршберга позволяет уменьшить потребление памяти до .
This algorithm can also be adapted to sequences of different lengths. Despite this improvement, it was shown that a strongly subquadratic running time of the form for some cannot exist unless the Strong exponential time hypothesis fails. While the dynamic programming algorithm for DTW requires space in a naive implementation, the space consumption can be reduced to using Hirschberg's algorithm.
Быстрый вычисление
Быстрые методы вычисления DTW включают в себя методы с ранним отказом и обрезкой (Early Abandoned и Pruned DTW), PrunedDTW, SparseDTW, FastDTW и MultiscaleDTW. Общая задача – поиск похожих временных рядов – может быть ускорена за счет использования нижних границ, таких как LB Keogh, LB Improved, LB Enhanced, LB Webb или LB Petitjean. После проведения данного обзора была разработана нижняя граница LB Enhanced, которая всегда строже, чем LB Keogh, и при этом более эффективна в вычислениях. DTW является точным методом усреднения двух последовательностей. Для более чем двух последовательностей задача связана с задачей множественного выравнивания и требует применения эвристических методов. В настоящее время DBA является стандартным методом для согласованного усреднения набора последовательностей с использованием DTW. COMASA эффективно рандомизирует поиск средней последовательности, используя DBA в качестве процесса локальной оптимизации.
Обучение под наблюдением
Классификатор ближайших соседей может достигать передовых результатов при использовании динамического программирования времени в качестве метрики расстояния.
Динамическое деформация времени
Amerced Dynamic Time Warping (ADTW) — это вариант алгоритма DTW, разработанный для более эффективного контроля допустимости выравниваний, которые он допускает. Ограничивающие окна, используемые в классическом DTW, создают ступенчатую зависимость: любое искажение пути разрешено внутри окна, но запрещено за его пределами. В отличие от этого, ADTW применяет аддитивную штрафную функцию, которая начисляется каждый раз, когда путь искажается. Любая степень искажения разрешена, но каждое искажающее действие влечет за собой прямой штраф. ADTW значительно превосходит DTW с использованием окон при применении в качестве классификатора ближайших соседей на наборе эталонных задач классификации временных рядов. В отличие от независимого выравнивания нескольких пар с помощью DTW, GTW учитывает как точность выравнивания каждой пары последовательностей (как и DTW), так и степень их сходства (на основе структуры данных или заданную пользователем). Это может привести к повышению качества выравнивания, если между парами существует сходство.
Функции расстояния
DTW чувствителен к функции расстояния, используемой для оценки соответствия между парами значений в двух последовательностях. Изначальное определение DTW, применяемое в классификации временных рядов, получило широкое распространение. Недавние исследования показали, что оптимизация этой меры расстояния может быть полезна для повышения эффективности DTW. В частности, настройка γ в семействе функций расстояния вида позволяет DTW уделять больше внимания эффектам малой амплитуды при малых значениях γ и эффектам большой амплитуды при больших значениях γ.
Обработка недостающих значений
DTW не может обрабатывать пропущенные значения во временных рядах. Простые методы предварительной обработки, такие как удаление или интерполяция пропущенных значений, не дают хорошей оценки расстояния DTW. DTW AROW (DTW с дополнительными ограничениями на искажение) является обобщением DTW для обработки пропущенных значений. Гладкость и монотонность функций искажения времени могут быть достигнуты, например, путем интегрирования радиальной базисной функции, изменяющейся во времени, что делает их одномерным диффеоморфизмом. Оптимальные нелинейные функции искажения времени вычисляются путем минимизации меры расстояния от набора функций до их искаженного среднего значения. К функциям искажения могут быть добавлены штрафы за шероховатость, например, путем ограничения величины их кривизны. Полученные функции искажения гладкие, что облегчает дальнейшую обработку. Этот подход успешно применяется для анализа закономерностей и изменчивости речевых движений. Другой связанный подход – скрытая марковская модель (HMM), и было показано, что алгоритм Витерби, используемый для поиска наиболее вероятного пути в HMM, эквивалентен стохастическому DTW. DTW и связанные с ним методы искажения обычно используются в качестве этапов предварительной или последующей обработки при анализе данных. Если обе наблюдаемые последовательности содержат случайные колебания в их значениях, форме наблюдаемых последовательностей и случайное временное рассогласование, искажение может переобучиться на шум, приводя к смещенным результатам. Одновременная формулировка модели со случайными колебаниями как значений (вертикальных), так и параметризации времени (горизонтальных) является примером нелинейной модели смешанных эффектов. В анализе движений человека было показано, что одновременное нелинейное моделирование смешанных эффектов дает лучшие результаты по сравнению с DTW.
Программное обеспечение с открытым исходным кодом
Библиотека Tempo C++ с привязками Python реализует алгоритмы Early Abandoned и Pruned DTW, а также Early Abandoned и Pruned ADTW и нижние границы DTW – LB Keogh, LB Enhanced и LB Webb. Библиотека UltraFastMPSearch Java реализует алгоритм UltraFastWWSearch для быстрой настройки окна деформации. Библиотека lbimproved C++ реализует алгоритмы быстрого поиска ближайших соседей под лицензией GNU General Public License (GPL). Она также предоставляет реализацию динамического искажения времени (DTW) на C++ и различные нижние границы. Библиотека FastDTW является Java-реализацией DTW и предоставляет реализацию FastDTW, обеспечивающую оптимальное или почти оптимальное выравнивание со временной и пространственной сложностью O(N), в отличие от O(N²) для стандартного алгоритма DTW. FastDTW использует многоуровневый подход, рекурсивно проецирующий решение из более грубого разрешения и уточняющий спроецированное решение. FastDTW fork (Java) опубликован в Maven Central. Пакет time series classification (Java) предназначен для классификации временных рядов с использованием DTW в Weka. Пакет DTW предоставляет пакеты для Python (dtw python) и R (dtw) с широким охватом семейства алгоритмов DTW, включая различные правила рекурсии (также называемые шаблонами шагов), ограничения и сопоставление подстрок. Библиотека mlpy Python реализует DTW. Библиотека pydtw Python реализует меры DTW с манхэттенской и евклидовой метриками, включая нижние границы LB Keogh. Библиотека cudadtw C++/CUDA реализует выравнивание подпоследовательностей DTW с евклидовой метрикой и z-нормализованным евклидовым расстоянием, аналогично популярному UCR Suite на ускорителях с поддержкой CUDA. Библиотека машинного обучения JavaML реализует DTW. Библиотека ndtw C# реализует DTW с различными опциями. Sketch a Char использует Greedy DTW (реализованный на JavaScript) в составе программы классификатора символов LaTeX. MatchBox использует DTW для сопоставления мел-частотных кепстральных коэффициентов аудиосигналов. Усреднение последовательностей: Java-реализация DBA под лицензией GPL. DP-сопоставление – алгоритм сопоставления шаблонов, основанный на динамическом программировании (DP), использующий эффект нормализации времени, при котором колебания по оси времени моделируются нелинейной функцией временного искажения. Рассматривая любые два речевых образца, можно устранить их временные различия, искажая ось времени одного из них для достижения максимального совпадения с другим. Более того, если функция искажения может принимать любое значение, можно различать слова, принадлежащие к разным категориям. Поэтому, для повышения различия между словами, принадлежащими к разным категориям, были введены ограничения на наклон функции искажения.
Анализ корреляционной мощности
Нестабильные часы используются для противодействия наивному анализу мощности. Для нейтрализации этой защиты применяются различные методы, в том числе динамическое выравнивание по времени.
Финансы и эконометрия
Динамическое выравнивание по времени используется в финансах и эконометрике для оценки качества прогнозирования по отношению к реальным данным.