Алгоритм динамической трансформации временной шкалы
 |
Этот перевод статьи с другого языка требует улучшения (см. Проверка переводов). Вы можете помочь улучшить перевод. Оригинал можно найти слева в списке языков.
Статья, целиком являющаяся машинным переводом, может быть удалена на основании критерия быстрого удаления С2. |
Алгоритм динамической трансформации временно́й шкалы (DTW-алгоритм, от англ. dynamic time warping) — алгоритм, позволяющий найти оптимальное соответствие между временными последовательностями. Впервые применен в распознавании речи, где использован для определения того, как два речевых сигнала представляют одну и ту же исходную произнесённую фразу. Впоследствии были найдены применения и в других областях[1].
Временные ряды — широко распространенный тип данных[уточнить], встречающийся, фактически, в любой научной области, и сравнение двух последовательностей является стандартной задачей. Для вычисления отклонения бывает достаточно простого измерения расстояния между компонентами двух последовательностей (евклидово расстояние). Однако часто две последовательности имеют приблизительно одинаковые общие формы, но эти формы не выровнены по оси X. Чтобы определить подобие между такими последовательностями, мы должны «деформировать» ось времени одной (или обеих) последовательности, чтобы достигнуть лучшего выравнивания.[2]
Содержание
Алгоритм
Измерение расстояния между двумя временными рядами нужно для того, чтобы определить их подобие и классификацию. Таким эффективным измерением является евклидова метрика. Для двух временных последовательностей это просто сумма квадратов расстояний от каждой n-ой точки одной последовательности до n-ой точки другой. Однако использование евклидова расстояния имеет существенный недостаток: если два временных ряда одинаковы, но один из них незначительно смещен во времени (вдоль оси времени), то евклидова метрика может посчитать, что ряды отличаются друг от друга. DTW-алгоритм был введён для того, чтобы преодолеть этот недостаток и предоставить наглядное измерение расстояния между рядами, не обращая внимание как на глобальные, так и на локальные сдвиги на временной шкале.[3]
Классический алгоритм
Рассмотрим два временных ряда <math>Q</math> длины <math>n</math> и <math>C</math> длины <math>m</math>[4]:
- <math>
Q = q_{1}, q_{2},\ldots, q_{i}, \ldots, q_{n}; \qquad \qquad (1)</math>
- <math>
C = c_{1}, c_{2},\ldots, c_{j}, \ldots, c_{m}. \qquad \qquad (2)</math>
Первый этап алгоритма состоит в следующем. Мы строим матрицу <math>d</math> порядка <math>n\times m</math> (матрицу расстояний), в которой элемент <math>d_{i\;j}</math> есть расстояние <math>d(q_{i},c_{j})</math> между двумя точками <math>q_{i}</math> и <math>c_{j}</math>. Обычно используется евклидово расстояние: <math>d(q_{i},c_{j}) = (q_i - c_j)^2 \quad </math>, или <math>d(q_{i},c_{j}) = |q_i - c_j|</math>. Каждый элемент <math>(i, j)</math> матрицы соответствует выравниванию между точками <math>q_{i}</math> и <math>c_{j}</math>.
На втором этапе строим матрицу трансформаций (деформаций)<math>D</math>, каждый элемент которой вычисляется исходя из следующего соотношения:
- <math>
D_{i\;j} = d_{i\;j} + min({D_{i-1\;j},D_{i-1\;j-1},D_{i\;j-1}}). \qquad (3)</math>
После заполнения матрицы трансформации, мы переходим к заключительному этапу, который заключается в том, чтобы построить некоторый оптимальный путь трансформации (деформации) и DTW расстояние (стоимость пути).
Путь трансформации <math>W</math> — это набор смежных элементов матрицы, который устанавливает соответствие между <math>Q</math> и <math>C</math>. Он представляет собой путь, который минимизирует общее расстояние между <math>Q</math> и <math>C</math>. <math>k</math>-ый элемент пути <math>W</math> определяется как <math>w_{k} = (i,j)_{k}, \quad d(w_{k}) = d(q_{i},c_{j}) = (q_i - c_j)^2</math>.
Таким образом:
- <math>
W = w_{1}, w_{2},\ldots, w_{k}, \ldots, w_{K}; \qquad max(m,n)\leqslant K < m+n,</math> где <math>K</math> — длина пути.
Путь трансформации должен удовлетворять следующим ограничивающим условиям:
- Граничные условия: начало пути <math>w_{1} = (1,1)</math>, его конец — <math>w_{K} = (n,m)</math>. Это ограничение гарантирует, что путь трансформации содержит все точки обоих временных рядов.
- Непрерывность (условие на длину шага): любые два смежных элемента пути <math>W</math>, <math>w_{k} = (w_{i},w_{j})</math> и <math>w_{k+1} = (w_{i+1},w_{j+1})</math>, удовлетворяют следующим неравенствам: <math>w_{i} - w_{i+1} \leqslant 1</math>, <math>w_{j} - w_{j+1} \leqslant 1</math>. Это ограничение гарантирует, что путь трансформации передвигается на один шаг за один раз. То есть оба индекса <math>i</math> и <math>j</math> могут увеличиться только на 1 на каждом шаге пути.
- Монотонность: любые два смежных элемента пути <math>W</math>, <math>w_{k} = (w_{i},w_{j})</math> и <math>w_{k-1} = (w_{i-1},w_{j-1})</math>, удовлетворяют следующим неравенствам: <math>w_{i} - w_{i-1} \geqslant 0</math>, <math>w_{j} - w_{j-1} \geqslant 0</math>. Это ограничение гарантирует, что путь трансформации не будет возвращаться назад к пройденной точке. То есть оба индекса <math>i</math> и <math>j</math> либо остаются неизменными, либо увеличиваются (но никогда не уменьшаются).
Хотя существует большое количество путей трансформации, удовлетворяющих всем вышеуказанным условиям, однако нас интересуют только тот путь, который минимизирует DTW расстояние (стоимость пути).
DTW расстояние (стоимость пути) между двумя последовательностями рассчитывается на основе оптимального пути трансформации с помощью формулы:
- <math> DTW(Q,C) = min\left\{\frac {\sum\limits^{K}_{k=1} {d(w_{k})}} {K}\right\}. \qquad (4)</math>
<math>K</math> в знаменателе используется для учёта того, что пути трансформации могут быть различной длины.
Пространственная и временная сложность алгоритма — квадратичная, <math>O(nm)</math>, так как DTW алгоритм должен изучить каждую клетку матрицы трансформации.
Недостатки алгоритма
Хотя алгоритм успешно используется во многих областях, он может выдавать неправильные результаты. Алгоритм может попытаться объяснить непостоянство оси <math>y</math> с помощью трансформации оси <math>x</math>. Это может привести к выравниванию, при котором одной точке первой последовательности ставится в соответствие большая подгруппа точек второй последовательности.
Другая проблема заключается в том, что алгоритм может не найти очевидное выравнивание двух рядов вследствие того, что особая точка (пик, впадина, плато, точка перегиба) одного ряда расположена немного выше или ниже соответствующей ей особой точки другого ряда[5].
Разновидности DTW алгоритма
Различные доработки DTW алгоритма предназначены для ускорения его вычислений, а также для того, чтобы лучше контролировать возможные маршруты путей трансформации.
Общие (глобальные) ограничения
Один из распространенных вариантов DTW алгоритма — наложение общих (глобальных) ограничивающих условий на допустимые пути деформации[6]. Пусть <math> R \subseteq [1 : n] \times [1 : m] </math> — подмножество, задающее область глобального ограничения. Теперь путём трансформации является путь, который содержится в области <math>R</math>. Оптимальный путь трансформации — путь, принадлежащий <math>R</math>, и минимизирующий стоимость пути среди всех путей трансформации из <math>R</math>.
Быстрый DTW-алгоритм
Этот алгоритм обладает линейной пространственной и временной сложностью. Быстрый DTW алгоритм использует многоуровневый подход с тремя ключевыми операциями[7]:
- Уменьшение детализации — уменьшаем размер временного ряда с помощью усреднения смежных пар точек. Полученный временной ряд — это ряд, имеющий в два раза меньше точек, чем исходный. Мы проводим эту операцию несколько раз, чтобы получить много различных разрешений временного ряда.
- Планирование — берем путь трансформации при низкой детализации и определяем через какие клетки будет проходить путь трансформации при следующей детализации (на порядок выше предыдущей). Так как разрешение увеличивается в два раза, одной точке, принадлежащей пути трансформации в низком разрешении, будут соответствовать, по крайней мере, четыре точки в большем разрешении. Затем этот планируемый путь используется в качестве эвристического правила в процессе обработки, чтобы найти путь в высоком разрешении.
- Обработка — поиск оптимального пути деформации в окрестности спланированного пути.
Разреженный DTW-алгоритм
Основная идея данного метода состоит в том, чтобы динамически использовать наличие подобия и/или сопоставления данных для двух временных последовательностей. Данный алгоритм имеет три особых преимущества[8]:
- Матрица трансформации представляется с помощью разреженных матриц, что приводит к уменьшению средней пространственной сложности по сравнению с другими методами.
- Разреженный DTW алгоритм всегда выдает оптимальный путь трансформации.
- Так как алгоритм выдает оптимальное выравнивание, то он может быть легко использован в сочетании с другими методами.
Области применения
- распознавание речи
- интеллектуальный анализ данных
- распознавание жестов
- робототехника
- медицина
- биоинформатика
- верификация подписи
Напишите отзыв о статье "Алгоритм динамической трансформации временной шкалы"
Примечания
- ↑ [arxiv.org/pdf/1201.2969v1.pdf Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up Dynamic Time Warping] (англ.)
- ↑ [www.cs.rutgers.edu/~pazzani/Publications/sdm01.pdf Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Section 1] (англ.)
- ↑ [gi.cebitec.uni-bielefeld.de/teaching/2007summer/jclub/papers/Salvador2004.pdf Stan Salvador and Philip Chan Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space] (англ.)
- ↑ [www.cs.rutgers.edu/~pazzani/Publications/sdm01.pdf Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Section 2] (англ.)
- ↑ [www.cs.rutgers.edu/~pazzani/Publications/sdm01.pdf Eamonn J. Keogh, Michael J. Pazzani Derivative Dynamic Time Warping, Section 1, page 2] (англ.)
- ↑ [www2.hawaii.edu/~senin/assets/papers/DTW-review2008draft.pdf DTW Algorithm Review. Section 3.3] (англ.)
- ↑ [gi.cebitec.uni-bielefeld.de/teaching/2007summer/jclub/papers/Salvador2004.pdf Stan Salvador and Philip ChanFast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space] (англ.)
- ↑ [arxiv.org/pdf/1201.2969v1.pdf Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri Sparse DTW: A novel approach to speed up, Section 1.1] (англ.)
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Алгоритм динамической трансформации временной шкалы
– Ей богу, Безухов, в кафтане, с каким то старым мальчиком! Ей богу, – говорила Наташа, – смотрите, смотрите!– Да нет, это не он. Можно ли, такие глупости.
– Мама, – кричала Наташа, – я вам голову дам на отсечение, что это он! Я вас уверяю. Постой, постой! – кричала она кучеру; но кучер не мог остановиться, потому что из Мещанской выехали еще подводы и экипажи, и на Ростовых кричали, чтоб они трогались и не задерживали других.
Действительно, хотя уже гораздо дальше, чем прежде, все Ростовы увидали Пьера или человека, необыкновенно похожего на Пьера, в кучерском кафтане, шедшего по улице с нагнутой головой и серьезным лицом, подле маленького безбородого старичка, имевшего вид лакея. Старичок этот заметил высунувшееся на него лицо из кареты и, почтительно дотронувшись до локтя Пьера, что то сказал ему, указывая на карету. Пьер долго не мог понять того, что он говорил; так он, видимо, погружен был в свои мысли. Наконец, когда он понял его, посмотрел по указанию и, узнав Наташу, в ту же секунду отдаваясь первому впечатлению, быстро направился к карете. Но, пройдя шагов десять, он, видимо, вспомнив что то, остановился.
Высунувшееся из кареты лицо Наташи сияло насмешливою ласкою.
– Петр Кирилыч, идите же! Ведь мы узнали! Это удивительно! – кричала она, протягивая ему руку. – Как это вы? Зачем вы так?
Пьер взял протянутую руку и на ходу (так как карета. продолжала двигаться) неловко поцеловал ее.
– Что с вами, граф? – спросила удивленным и соболезнующим голосом графиня.
– Что? Что? Зачем? Не спрашивайте у меня, – сказал Пьер и оглянулся на Наташу, сияющий, радостный взгляд которой (он чувствовал это, не глядя на нее) обдавал его своей прелестью.
– Что же вы, или в Москве остаетесь? – Пьер помолчал.
– В Москве? – сказал он вопросительно. – Да, в Москве. Прощайте.
– Ах, желала бы я быть мужчиной, я бы непременно осталась с вами. Ах, как это хорошо! – сказала Наташа. – Мама, позвольте, я останусь. – Пьер рассеянно посмотрел на Наташу и что то хотел сказать, но графиня перебила его:
– Вы были на сражении, мы слышали?
– Да, я был, – отвечал Пьер. – Завтра будет опять сражение… – начал было он, но Наташа перебила его:
– Да что же с вами, граф? Вы на себя не похожи…
– Ах, не спрашивайте, не спрашивайте меня, я ничего сам не знаю. Завтра… Да нет! Прощайте, прощайте, – проговорил он, – ужасное время! – И, отстав от кареты, он отошел на тротуар.
Наташа долго еще высовывалась из окна, сияя на него ласковой и немного насмешливой, радостной улыбкой.
Пьер, со времени исчезновения своего из дома, ужа второй день жил на пустой квартире покойного Баздеева. Вот как это случилось.
Проснувшись на другой день после своего возвращения в Москву и свидания с графом Растопчиным, Пьер долго не мог понять того, где он находился и чего от него хотели. Когда ему, между именами прочих лиц, дожидавшихся его в приемной, доложили, что его дожидается еще француз, привезший письмо от графини Елены Васильевны, на него нашло вдруг то чувство спутанности и безнадежности, которому он способен был поддаваться. Ему вдруг представилось, что все теперь кончено, все смешалось, все разрушилось, что нет ни правого, ни виноватого, что впереди ничего не будет и что выхода из этого положения нет никакого. Он, неестественно улыбаясь и что то бормоча, то садился на диван в беспомощной позе, то вставал, подходил к двери и заглядывал в щелку в приемную, то, махая руками, возвращался назад я брался за книгу. Дворецкий в другой раз пришел доложить Пьеру, что француз, привезший от графини письмо, очень желает видеть его хоть на минутку и что приходили от вдовы И. А. Баздеева просить принять книги, так как сама г жа Баздеева уехала в деревню.
– Ах, да, сейчас, подожди… Или нет… да нет, поди скажи, что сейчас приду, – сказал Пьер дворецкому.
Но как только вышел дворецкий, Пьер взял шляпу, лежавшую на столе, и вышел в заднюю дверь из кабинета. В коридоре никого не было. Пьер прошел во всю длину коридора до лестницы и, морщась и растирая лоб обеими руками, спустился до первой площадки. Швейцар стоял у парадной двери. С площадки, на которую спустился Пьер, другая лестница вела к заднему ходу. Пьер пошел по ней и вышел во двор. Никто не видал его. Но на улице, как только он вышел в ворота, кучера, стоявшие с экипажами, и дворник увидали барина и сняли перед ним шапки. Почувствовав на себя устремленные взгляды, Пьер поступил как страус, который прячет голову в куст, с тем чтобы его не видали; он опустил голову и, прибавив шагу, пошел по улице.
Из всех дел, предстоявших Пьеру в это утро, дело разборки книг и бумаг Иосифа Алексеевича показалось ему самым нужным.
Он взял первого попавшегося ему извозчика и велел ему ехать на Патриаршие пруды, где был дом вдовы Баздеева.
Беспрестанно оглядываясь на со всех сторон двигавшиеся обозы выезжавших из Москвы и оправляясь своим тучным телом, чтобы не соскользнуть с дребезжащих старых дрожек, Пьер, испытывая радостное чувство, подобное тому, которое испытывает мальчик, убежавший из школы, разговорился с извозчиком.
Извозчик рассказал ему, что нынешний день разбирают в Кремле оружие, и что на завтрашний народ выгоняют весь за Трехгорную заставу, и что там будет большое сражение.
Приехав на Патриаршие пруды, Пьер отыскал дом Баздеева, в котором он давно не бывал. Он подошел к калитке. Герасим, тот самый желтый безбородый старичок, которого Пьер видел пять лет тому назад в Торжке с Иосифом Алексеевичем, вышел на его стук.
– Дома? – спросил Пьер.
– По обстоятельствам нынешним, Софья Даниловна с детьми уехали в торжковскую деревню, ваше сиятельство.
– Я все таки войду, мне надо книги разобрать, – сказал Пьер.
– Пожалуйте, милости просим, братец покойника, – царство небесное! – Макар Алексеевич остались, да, как изволите знать, они в слабости, – сказал старый слуга.
Макар Алексеевич был, как знал Пьер, полусумасшедший, пивший запоем брат Иосифа Алексеевича.
– Да, да, знаю. Пойдем, пойдем… – сказал Пьер и вошел в дом. Высокий плешивый старый человек в халате, с красным носом, в калошах на босу ногу, стоял в передней; увидав Пьера, он сердито пробормотал что то и ушел в коридор.
– Большого ума были, а теперь, как изволите видеть, ослабели, – сказал Герасим. – В кабинет угодно? – Пьер кивнул головой. – Кабинет как был запечатан, так и остался. Софья Даниловна приказывали, ежели от вас придут, то отпустить книги.
Пьер вошел в тот самый мрачный кабинет, в который он еще при жизни благодетеля входил с таким трепетом. Кабинет этот, теперь запыленный и нетронутый со времени кончины Иосифа Алексеевича, был еще мрачнее.
Герасим открыл один ставень и на цыпочках вышел из комнаты. Пьер обошел кабинет, подошел к шкафу, в котором лежали рукописи, и достал одну из важнейших когда то святынь ордена. Это были подлинные шотландские акты с примечаниями и объяснениями благодетеля. Он сел за письменный запыленный стол и положил перед собой рукописи, раскрывал, закрывал их и, наконец, отодвинув их от себя, облокотившись головой на руки, задумался.
Несколько раз Герасим осторожно заглядывал в кабинет и видел, что Пьер сидел в том же положении. Прошло более двух часов. Герасим позволил себе пошуметь в дверях, чтоб обратить на себя внимание Пьера. Пьер не слышал его.
– Извозчика отпустить прикажете?
– Ах, да, – очнувшись, сказал Пьер, поспешно вставая. – Послушай, – сказал он, взяв Герасима за пуговицу сюртука и сверху вниз блестящими, влажными восторженными глазами глядя на старичка. – Послушай, ты знаешь, что завтра будет сражение?..
– Сказывали, – отвечал Герасим.
– Я прошу тебя никому не говорить, кто я. И сделай, что я скажу…
– Слушаюсь, – сказал Герасим. – Кушать прикажете?
– Нет, но мне другое нужно. Мне нужно крестьянское платье и пистолет, – сказал Пьер, неожиданно покраснев.
– Слушаю с, – подумав, сказал Герасим.
Весь остаток этого дня Пьер провел один в кабинете благодетеля, беспокойно шагая из одного угла в другой, как слышал Герасим, и что то сам с собой разговаривая, и ночевал на приготовленной ему тут же постели.
Герасим с привычкой слуги, видавшего много странных вещей на своем веку, принял переселение Пьера без удивления и, казалось, был доволен тем, что ему было кому услуживать. Он в тот же вечер, не спрашивая даже и самого себя, для чего это было нужно, достал Пьеру кафтан и шапку и обещал на другой день приобрести требуемый пистолет. Макар Алексеевич в этот вечер два раза, шлепая своими калошами, подходил к двери и останавливался, заискивающе глядя на Пьера. Но как только Пьер оборачивался к нему, он стыдливо и сердито запахивал свой халат и поспешно удалялся. В то время как Пьер в кучерском кафтане, приобретенном и выпаренном для него Герасимом, ходил с ним покупать пистолет у Сухаревой башни, он встретил Ростовых.
