Искажение времени Edit Distance - Time Warp Edit Distance
Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
Искажение времени Edit Distance (TWED) - это мера расстояния для дискретных Временные ряды соответствие «эластичности» времени. По сравнению с другими показателями расстояния (например, DTW (Динамическое искажение времени ) или LCS (Самая длинная общая проблема подпоследовательности )) TWED - это метрика. Его вычислительная временная сложность составляет , но в некоторых конкретных ситуациях его можно значительно сократить, используя коридор для уменьшения пространства поиска. Сложность его памяти может быть уменьшена до . Впервые он был предложен в 2009 г. П.-Ф. Марто.
Определение
в то время как
В то время как рекурсияинициализируется как:
с
Реализации
Реализацию TWED-алгоритма на C или Matlab можно скачать с домашней страницы авторов.[1]
Реализация TWED на R была интегрирована в TraMineR, R-пакет для интеллектуального анализа данных, описания и визуализации последовательностей состояний или событий и, в более общем смысле, данных дискретных последовательностей.[2]
Кроме того, ОБРАЩЕННЫЙ - это ускоренная CUDA реализация TWED, в которой используется улучшенный алгоритм, разработанный Дж. Райтом (2020). Этот метод является линейным по памяти и широко распараллелен. cuTWED написан на CUDA C / C ++, поставляется с привязками python, а также включает привязки python для эталонной реализации C Марто.
Python
импорт тупой в качестве нпdef Dlp(А, B, п=2): Стоимость = нп.сумма(нп.мощность(нп.пресс(А - B), п)) возвращаться нп.мощность(Стоимость, 1 / п)def twed(А, timeSA, B, timeSB, ню, _lambda): # [расстояние, DP] = TWED (A, timeSA, B, timeSB, lambda, nu) # Вычислить расстояние редактирования временной деформации (TWED) для заданных временных рядов A и B # # A: = Временной ряд A (например, [10 2 30 4]) # timeSA: = Отметка времени временного ряда A (например, 1: 4) # B: = Временной ряд B # timeSB: = Отметка времени временного ряда B # lambda: = Штраф за операцию удаления # nu: = Параметр эластичности - nu> = 0 необходим для измерения расстояния # Ссылка : # Marteau, P .; Ф. (2009). «Расстояние редактирования искажения времени с регулировкой жесткости для согласования временных рядов». # IEEE Transactions по анализу шаблонов и машинному анализу. 31 (2): 306–318. arXiv: cs / 0703033 # http://people.irisa.fr/Pierre-Francois.Marteau/ # Проверяем входные аргументы если len(А) != len(timeSA): Распечатать(«Длина A не равна длительности timeSA») возвращаться Никто, Никто если len(B) != len(timeSB): Распечатать(«Длина B не равна длительности timeSB») возвращаться Никто, Никто если ню < 0: Распечатать("ню отрицательно") возвращаться Никто, Никто # Добавить отступ А = нп.множество([0] + список(А)) timeSA = нп.множество([0] + список(timeSA)) B = нп.множество([0] + список(B)) timeSB = нп.множество([0] + список(timeSB)) п = len(А) м = len(B) # Динамическое программирование DP = нп.нули((п, м)) # Инициализировать матрицу DP и установить первую строку и столбец на бесконечность DP[0, :] = нп.инф DP[:, 0] = нп.инф DP[0, 0] = 0 # Минимальные затраты на вычисление за я в классифицировать(1, п): за j в классифицировать(1, м): # Рассчитывать и экономить на различных операциях C = нп.те((3, 1)) * нп.инф # Удаление в A C[0] = ( DP[я - 1, j] + Dlp(А[я - 1], А[я]) + ню * (timeSA[я] - timeSA[я - 1]) + _lambda ) # Удаление в B C[1] = ( DP[я, j - 1] + Dlp(B[j - 1], B[j]) + ню * (timeSB[j] - timeSB[j - 1]) + _lambda ) # Сохранять точки данных в обоих временных рядах C[2] = ( DP[я - 1, j - 1] + Dlp(А[я], B[j]) + Dlp(А[я - 1], B[j - 1]) + ню * (пресс(timeSA[я] - timeSB[j]) + пресс(timeSA[я - 1] - timeSB[j - 1])) ) # Выберите операцию с минимальными затратами и обновите DP Matrix DP[я, j] = нп.мин(C) расстояние = DP[п - 1, м - 1] возвращаться расстояние, DP
Поиск с возвратом, чтобы найти наиболее экономичный путь:
def возврат(DP): # [best_path] = ОТСЛЕЖИВАНИЕ (DP) # Вычислить наиболее экономичный путь # DP: = DP матрица функции TWED Икс = нп.форма(DP) я = Икс[0] - 1 j = Икс[1] - 1 # Индексы путей сохраняются в обратном направлении # путь = np.ones ((i + j, 2)) * np.inf; лучший_путь = [] шаги = 0 пока я != 0 или же j != 0: лучший_путь.добавить((я - 1, j - 1)) C = нп.те((3, 1)) * нп.инф # Сохранять точки данных в обоих временных рядах C[0] = DP[я - 1, j - 1] # Удаление в A C[1] = DP[я - 1, j] # Удаление в B C[2] = DP[я, j - 1] # Найдите индекс по самой низкой цене idx = нп.аргмин(C) если idx == 0: # Сохранять точки данных в обоих временных рядах я = я - 1 j = j - 1 Элиф idx == 1: # Удаление в A я = я - 1 j = j еще: # Удаление в B я = я j = j - 1 шаги = шаги + 1 лучший_путь.добавить((я - 1, j - 1)) лучший_путь.обеспечить регресс() возвращаться лучший_путь[1:]
MATLAB
функция[расстояние, DP] =twed(A, timeSA, B, timeSB, лямбда, ню)% [расстояние, DP] = TWED (A, timeSA, B, timeSB, lambda, nu) % Расчет расстояния редактирования деформации времени (TWED) для заданных временных рядов A и B % % A: = Временной ряд A (например, [10 2 30 4]) % timeSA: = отметка времени временного ряда A (например, 1: 4) % B: = Временной ряд B % timeSB: = отметка времени временного ряда B % lambda: = Штраф за операцию удаления % nu: = Параметр эластичности - nu> = 0 необходим для измерения расстояния % % Автор кода: P.-F. Марто - http://people.irisa.fr/Pierre-Francois.Marteau/ % Проверить, есть ли входные аргументы если длина (A) ~ = длина (timeSA) предупреждение('Длина A не равна длительности timeSA') возвращатьсяконец если длина (B) ~ = длина (timeSB) предупреждение('Длина B не равна длине timeSB') возвращатьсяконец если nu <0 предупреждение('nu отрицательный') возвращатьсяконец % Добавить отступ А = [0 А]; timeSA = [0 timeSA]; B = [0 B]; timeSB = [0 timeSB]; % Динамическое программирование DP = нули(длина(А), длина(B)); % Инициализировать матрицу DP и установить первую строку и столбец на бесконечность DP(1, :) = инф; DP(:, 1) = инф; DP(1, 1) = 0; п = длина(timeSA); м = длина(timeSB); % Минимальная стоимость вычислений за я = 2: п за j = 2: м Стоимость = Dlp(А(я), B(j)); % Расчет и экономия затрат на различные операции C = те(3, 1) * инф; % Удаления в A C(1) = DP(я - 1, j) + Dlp(А(я - 1), А(я)) + ню * (timeSA(я) - timeSA(я - 1)) + лямбда; % Удаления в B C(2) = DP(я, j - 1) + Dlp(B(j - 1), B(j)) + ню * (timeSB(j) - timeSB(j - 1)) + лямбда; % Сохранить точки данных в обоих временных рядах C(3) = DP(я - 1, j - 1) + Dlp(А(я), B(j)) + Dlp(А(я - 1), B(j - 1)) + ... ню * (пресс(timeSA(я) - timeSB(j)) + пресс(timeSA(я - 1) - timeSB(j - 1))); % Выберите операцию с минимальными затратами и обновите DP Matrix DP(я, j) = мин(C); конецконец расстояние = DP(п, м); % Функция для вычисления евклидова расстояния функция[Стоимость] =Dlp(А, Б)Стоимость = sqrt(сумма((А - B) .^ 2, 2)); конецконец
Поиск с возвратом, чтобы найти наиболее экономичный путь:
функция[дорожка] =возврат(DP)% [путь] = ОТСЛЕЖИВАНИЕ (DP) % Вычислить наиболее экономичный путь % DP: = матрица DP функции TWED Икс = размер(DP); я = Икс(1); j = Икс(2); % Индексы путей сохраняются в обратном направлении дорожка = те(я + j, 2) * Inf; шаги = 1; пока (я ~= 1 || j ~= 1) дорожка(шаги, :) = [я; j]; C = те(3, 1) * инф; % Сохранить точки данных в обоих временных рядах C(1) = DP(я - 1, j - 1); % Удаления в A C(2) = DP(я - 1, j); % Удаления в B C(3) = DP(я, j - 1); % Найдите индекс с наименьшей стоимостью [~, idx] = мин(C); выключатель idx дело 1 % Сохранить точки данных в обоих временных рядах я = я - 1; j = j - 1; дело 2 % Удаления в A я = я - 1; j = j; дело 3 % Удаления в B я = я; j = j - 1; конец шаги = шаги + 1; конец путь (шаги, :) = [я j]; % Путь был рассчитан в обратном направлении. дорожка = дорожка(1:шаги, :); дорожка = дорожка(конец: - 1:1, :); конец
Рекомендации
- ^ Марто, П.-Ф. «Сайт на серверах IRISA». Получено 2016-09-11.
- ^ TraMineR. "Веб-сайт на серверах Женевского университета, Швейцария". Получено 2016-09-11.
- Marteau, P .; Ф. (2009). «Расстояние редактирования искажения времени с регулировкой жесткости для согласования временных рядов». IEEE Transactions по анализу шаблонов и машинному анализу. 31 (2): 306–318. arXiv:cs / 0703033. Дои:10.1109 / TPAMI.2008.76.