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/
- Follow-Ups:
- Re: Re: dynamic time warping algorithm
- From: Dr Bob <drbob@bigfoot.com>
- Re: Re: dynamic time warping algorithm