Последующее сопоставление временных рядов

Я застрял с последующим сопоставлением временных рядов в MATLAB (я новичок в этом).

У меня есть два временных ряда: A (длины a) и B (длины b). Предположим, что а намного больше, чем b. Задача состоит в том, чтобы найти ближайшее окно из А в Б (согласно евклидовой метрике).

Для этого я создаю дополнительную матрицу C, в которой хранятся все подпоследовательности длины b из A, а затем использую pdist2(C, B). Очевидно, что он работает медленно и требует слишком много памяти.

Итак, у меня есть пара вопросов:

  1. Как получить C без циклов (фактически изменить форму A)?

  2. Каковы общие способы решения этой проблемы? (желательно в MATLAB, но возможны и другие среды)

Спасибо за вашу помощь!


machine-learning matlab time-series euclidean-distance
person Max    schedule 06.02.2015    source источник
comment
Было бы полезно, если бы вы могли опубликовать некоторые образцы данных.   -  person kkuilla    schedule 06.02.2015

Ответы (3)


arrow_upward
1
arrow_downward

Для первого вопроса вы можете попробовать

tmp = repmat(A,1,b);
C = reshape([tmp zeros(1,b)],a,b);
C = C(1:(a-b+1),:);

Кроме того, pdist2 очень медленный по сравнению с этим очень хорошим решением: ">Эффективное вычисление попарного квадрата евклидова расстояния в Matlab

person jolo    schedule 06.02.2015
comment
Спасибо! У меня есть значительное ускорение, изменяющее временные ряды, и я постараюсь избежать pdist2. P.S. Это должно быть tmp вместо B во второй строке - person Max; 06.02.2015
comment
Это хороший подход для создания всех смещенных версий сигнала, но мне потребовалось некоторое время, чтобы понять идею с добавленными нулями - может быть, вы могли бы добавить какое-то объяснение? - person mbschenkel; 07.02.2015
comment
Нули необходимы для получения правильных размеров матрицы после изменения формы. Поскольку я использую pdist2, мне нужно, чтобы все сигналы были одинаковой длины. На самом деле они все равно вырезаны. - person Max; 08.02.2015

arrow_upward
1
arrow_downward

Во второй части вашего вопроса типичным способом сравнения последовательностей является динамическое искажение времени (DTW). . Вы почти наверняка сможете использовать Google для реализации Matlab.

Базовая версия алгоритма DTW имеет сложность O(nm), но приближенные версии, которые обычно имеют сопоставимую производительность, имеют сложность ближе к O(max(n, m)).

person user1149913    schedule 06.02.2015
comment
Спасибо! Я не был знаком с DTW, но я попробую. - person Max; 06.02.2015

arrow_upward
0
arrow_downward

Я хотел бы предложить взаимную корреляцию (xcorr) в качестве подхода к этой проблеме. О том, как связаны взаимная корреляция и евклидово расстояние, см., например, во введении к этой статье. Он не инвариантен к масштабированию по времени или амплитуде и может быть чувствителен к шуму, но вопрос не подразумевает никаких подобных искажений.

Преимуществом кросс-корреляции является ее эффективная реализация в области преобразования. К сожалению, у меня на руках только старая версия Matlab без pdist2, так что засечь время не могу. Но подумайте

%// Parameters
a = 1e4;
b = 1e2;
noise = 0.1;

%// Create sample signals with some distortion
A = rand(1, a);
Offset_actual = 321
B = A(Offset_actual + [1:b]) + noise*rand(1, b);

%// Computation
CC = xcorr(A, B);
[m, i] = max(CC);
Offset_estimated = i - a
plot(CC)

который должен восстановить Offset_estimated == Offset_actual.

person mbschenkel    schedule 07.02.2015
comment
Спасибо! Сейчас это немного ошеломляет меня, но я попробую этот подход. - person Max; 08.02.2015