algorithm
Ускорение динамического времени
Поиск…
Введение в динамическое деформирование времени
Dynamic Time Warping (DTW) - это алгоритм для измерения сходства между двумя временными последовательностями, которые могут варьироваться в зависимости от скорости. Например, сходство в ходьбе можно обнаружить с помощью DTW, даже если один человек идет быстрее, чем другой, или если в ходе наблюдения наблюдались ускорения и замедление. Его можно использовать для сопоставления с образцовой голосовой командой с другими командами, даже если человек говорит быстрее или медленнее, чем предварительно записанный образец голоса. DTW может применяться к временным последовательностям видео-, аудио- и графических данных - действительно, любые данные, которые могут быть преобразованы в линейную последовательность, могут быть проанализированы с помощью DTW.
В общем, DTW - это метод, который вычисляет оптимальное совпадение между двумя заданными последовательностями с определенными ограничениями. Но давайте придерживаться более простых моментов здесь. Предположим, у нас есть две голосовые последовательности Sample и Test , и мы хотим проверить, соответствуют ли эти две последовательности или нет. Здесь голосовая последовательность относится к преобразованному цифровому сигналу вашего голоса. Это может быть амплитуда или частота вашего голоса, который обозначает слова, которые вы говорите. Предположим:
Sample = {1, 2, 3, 5, 5, 5, 6}
Test = {1, 1, 2, 2, 3, 5}
Мы хотим найти оптимальное совпадение между этими двумя последовательностями.
Сначала мы определяем расстояние между двумя точками, d (x, y), где x и y представляют две точки. Позволять,
d(x, y) = |x - y| //absolute difference
Давайте создадим таблицу 2D-матрицы, используя эти две последовательности. Мы рассчитаем расстояния между каждой точкой образца с каждой точкой теста и найдем оптимальное совпадение между ними.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 1 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | | | | | | | |
+------+------+------+------+------+------+------+------+
Здесь таблица [i] [j] представляет оптимальное расстояние между двумя последовательностями, если мы рассмотрим последовательность до Sample [i] и Test [j] , учитывая все оптимальные расстояния, которые мы наблюдали ранее.
Для первой строки, если мы не принимаем значения из Sample , расстояние между этим и Test будет бесконечным . Поэтому мы помещаем бесконечность в первую строку. То же самое касается первого столбца. Если мы не будем принимать значения из теста , расстояние между этим и Sample также будет бесконечным. И расстояние между 0 и 0 будет просто 0 . Мы получаем,
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
Теперь для каждого шага мы рассмотрим расстояние между каждым интересующим вас пунктом и добавим его с минимальным расстоянием, которое мы обнаружили до сих пор. Это даст нам оптимальное расстояние двух последовательностей до этой позиции. Наша формула будет,
Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])
Для первого, d (1, 1) = 0 , таблица [0] [0] представляет собой минимум. Таким образом, значение таблицы [1] [1] будет равно 0 + 0 = 0 . Для второго d (1, 2) = 0 . Таблица [1] [1] представляет собой минимум. Значение будет: Таблица [1] [2] = 0 + 0 = 0 . Если мы продолжим этот путь, после окончания таблицы таблица будет выглядеть так:
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | 0 | 0 | 1 | 2 | 4 | 8 |
+------+------+------+------+------+------+------+------+
| 2 | inf | 1 | 1 | 0 | 0 | 1 | 4 |
+------+------+------+------+------+------+------+------+
| 3 | inf | 3 | 3 | 1 | 1 | 0 | 2 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 7 | 7 | 4 | 4 | 2 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 11 | 11 | 7 | 7 | 4 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 15 | 15 | 10 | 10 | 6 | 0 |
+------+------+------+------+------+------+------+------+
| 6 | inf | 20 | 20 | 14 | 14 | 9 | 1 |
+------+------+------+------+------+------+------+------+
Значение в таблице [7] [6] представляет собой максимальное расстояние между этими двумя заданными последовательностями. Здесь 1 представляет максимальное расстояние между образцом и тестом 1 .
Теперь, если мы отступим от последней точки, все пути назад к стартовой точке (0, 0) , мы получим длинную линию, которая перемещается горизонтально, вертикально и по диагонали. Наша процедура обратного отслеживания будет:
if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
i := i - 1
j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
i := i - 1
else
j := j - 1
end if
Мы продолжим это, пока не достигнем (0, 0) . Каждый ход имеет свое значение:
- Горизонтальное перемещение представляет собой удаление. Это означает, что наша тестовая последовательность ускорилась в течение этого интервала.
- Вертикальный ход представляет собой вставку. Это означает, что тестовая последовательность замедляется в течение этого интервала.
- Диагональный ход представляет собой совпадение. В течение этого периода тест и образец были такими же.
Наш псевдокод будет:
Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
Table[i][0] := infinity
end for
for i from 1 to m
Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
for j from 1 to m
Table[i][j] := d(Sample[i], Test[j])
+ minimum(Table[i-1][j-1], //match
Table[i][j-1], //insertion
Table[i-1][j]) //deletion
end for
end for
Return Table[n + 1][m + 1]
Мы также можем добавить ограничение локальности. То есть, мы требуем, чтобы если Sample[i]
соответствовал Test[j]
, то |i - j|
не больше w , параметр окна.
Сложность:
Сложность вычисления DTW равна O (m * n), где m и n представляют длину каждой последовательности. Более быстрые методы для вычисления DTW включают PrunedDTW, SparseDTW и FastDTW.
Приложения:
- Распознавание слов
- Анализ корреляции мощности