-
Notifications
You must be signed in to change notification settings - Fork 33
DYNWARP
From Wikipedia:
In time series analysis, dynamic time warping (DTW) is one of the algorithms for measuring similarity between two temporal sequences, which may vary in speed.
In laymans terms, DTW tries to find the minimal error sequences of two input vectors whereas these two sequences may vary in speed. The output sequences normally do not share the same length as the input vectors since datapoints are normally repeated to reach maximum similarity.
Given two vectors x and y the base calculation searches for a path through a n x m matrix (m, n are the input vector lengths) where the elements at ij are calculated by the distance to between vector element xi and yj plus the previous calculation column. The distance function may be L2, Abs dist or Kullback Leibler distance calculation.
There also exists a faster implementation of the DTW algorithm that recursively calculates the DTW path through the matrix in 2 steps reducing the needed calculation O(n^2) to (n*log(n)).
The class also supports a maximum search depth to steere the maximum allowed temporal change.
type
TDynamicTimeWarpDistMethod = (dtwSquared, dtwAbsolute, dtwSymKullbackLeibler);
constructor Create(DistMethod : TDynamicTimeWarpDistMethod = dtwSquared);
Initialize the object with one of the distance measurements.
function DTW(t, r : TDoubleDynArray; var dist : double; MaxSearchWin : integer = 0) : TDoubleDynArray; overload;
function DTWCorr(t, r : TDoubleDynArray; MaxSearchWin : integer = 0) : double; overload;
function DTW(t, r : IMatrix; var dist : double; MaxSearchWin : integer = 0) : IMatrix; overload;
function DTWCorr(t, r : IMatrix; MaxSearchWin : integer = 0) : double; overload; // calculate the correlation coefficient between both warped vectors
Applies the standard O(n^2) DTW algorithm on the vectors t and r. The MaxSearchWin param defines the maximum search depth aka the maximum allowed temporal change (0 is complete). Note that the lower the value (but greater than 0) the faster the outcome is. The *corr functions calculated the DTW correlation coefficent between the two vectors. dist returns the calculated distance between the two vectors.
function FastDTW(x, y : IMatrix; var dist : double; Radius : integer = 1) : IMatrix; overload; // applies fastdtw
function FastDTWCorr(t, r : IMatrix; Radius : integer = 1) : double; overload; // calculate the correlation coefficient between both warped vectors
function FastDTWCorr(t, r : IMatrix; var dist : double; Radius : integer = 1) : double; overload;
Implements the fast O(n*log(n)) algorithm on the input vectors x, y (or t, r). Radius defines the maximum search radius like the MaxSearchWin param but since the size varies from each iteration it's a bit different than the "whole" algorithm.
The last results are stored in the properties W1 and W2.
There exists a SSE optimzed version of DTW. Set the class var UseSSE to true before instanciating the object to speed up the calculation. Note that this variable is set in the InitMathFunctions or InitSSEOptFunctions.
The example is take from the test application and shows how the DTW algorithm works on a "chirp" signal (varying frequency as function of time) and a sine:
procedure TestDTWChirp;
var x : TDoubleDynArray;
y : TDoubleDynArray;
counter : integer;
dtw : TDynamicTimeWarp;
xv, yV : IMatrix;
dist : double;
begin
SetLength(x, 1000);
SetLength(y, 400);
for counter := 0 to Length(x) - 1 do
x[counter] := cos(2*pi*sqr( (3*(counter + 1)/1000) ));
for counter := 0 to Length(y) - 1 do
y[counter] := cos(2*pi*9*(counter + 1)/400);
xv := TDoubleMatrix.Create(x, Length(x), 1);
yv := TDoubleMatrix.Create(y, Length(y), 1);
dtw := TDynamicTimeWarp.Create;
try
dtw.DTW(xv, yv, dist);
Writeln(Format('Distance: %.4f', [dist]));
finally
dtw.Free;
end;
end;