Последващо съпоставяне на времеви редове

Бях заседнал с последващо съпоставяне на времеви серии в MATLAB (нов съм в него).

Имам два времеви реда: A (с дължина a) и B (с дължина b). Да приемем, че a е много по-голямо от b. Задачата е да се намери най-близкият прозорец от A до 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

За част 2 от вашия въпрос, типичен начин за сравняване на последователности е чрез Dynamic Time Warping (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