Re: Re: dynamic time warping algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg43080] Re: [mg43057] Re: [mg42867] dynamic time warping algorithm
- From: Dr Bob <drbob at bigfoot.com>
- Date: Mon, 11 Aug 2003 02:15:58 -0400 (EDT)
- References: <200308100546.BAA26284@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
> (* 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; I'd use ToCharacterCode["aAZz"] - 64 or ToCharacterCode@ToUpperCase["aAZz"] - 64 Bobby On Sun, 10 Aug 2003 01:46:47 -0400 (EDT), Rob Pratt <rpratt at email.unc.edu> wrote: > 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/ > > -- majort at cox-internet.com Bobby R. Treat
- References:
- Re: dynamic time warping algorithm
- From: Rob Pratt <rpratt@email.unc.edu>
- Re: dynamic time warping algorithm