MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: dynamic time warping algorithm

  • To: mathgroup at smc.vnet.net
  • Subject: [mg43057] Re: [mg42867] dynamic time warping algorithm
  • From: Rob Pratt <rpratt at email.unc.edu>
  • Date: Sun, 10 Aug 2003 01:46:47 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

On Thu, 31 Jul 2003, Sujai wrote:

> i came across an algorithm for dynamic time warping in this article:
> http://citeseer.nj.nec.com/keogh00scaling.html
>
> we are trying to use the algorithm to calculate the distance between two
> sequences (of letters, for eg: AAAAABBCCCCCCCCDDD and AABBBBBBCDDDDDD).
>
> i understand the algorithm but have never used the dynamic programming
> technique described in the article.
>
> would anyone here know how this could be implemented in mathematica or
> if there is a resource where this has been done before? i have no idea
> where to even begin.
>
> thanks in advance,
>
> - sujai


The following should get you started.  The key idea is the use of
f[x_] := f[x] = some function of x
to store values of a function once they are computed.

(* Convert the given strings to lists of numbers 1, 2, 3, 4. *)
rules = {A->1, B->2, C->3, D->4};
q = ToExpression[Characters[ToString[AAAAABBCCCCCCCCDDD]]]/.rules;
c = ToExpression[Characters[ToString[AABBBBBBCDDDDDD]]]/.rules;

d[x_,y_] := d[x,y] = Abs[x-y];
(* I'm assuming this is the appropriate distance function, but you can use
whatever you want. *)

(* boundary conditions *)
g[1, 1] = d[q[[1]], c[[1]]];

g[1, j_] := g[1, j] = d[q[[1]], c[[j]]] + g[1, j - 1]

g[i_, 1] := g[i, 1] = d[q[[i]], c[[1]]] + g[i - 1, 1]

(* main recursion: equation (5) in the article *)
g[i_, j_] := g[i, j] =
d[q[[i]], c[[j]]] + Min[g[i - 1, j - 1], g[i - 1, j], g[i, j - 1]]

In the notation of the article, n = Length[q] = 18 and m = Length[c] = 15.
So the distance between the two sequences is g[n,m] = g[18,15], which
turns out to be 0.

You can use Outer[d,q,c] to see the distance matrix and
Outer[g,Range[n],Range[m]] to see the cumulative distance matrix.

left corner to the bottom right corner consisting entirely of zeros.  (In
the article, the vertical axis is reversed so that the warping path goes
from bottom left corner to top right corner.)

Note that your sequences can be preprocessed by the following
distance-preserving transformation: replace all runs by a single element.
In other words, your q and c both become {1, 2, 3, 4}, from which it is
even more obvious that the distance between them is zero.  This
transformation can be accomplished using Map[First,Split[q]].

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/


  • Prev by Date: Re: Re: Need a better Integrate
  • Next by Date: Re: Re: Need a better Integrate
  • Previous by thread: Re: Writing graphics to another notebook?
  • Next by thread: Re: Re: dynamic time warping algorithm