dtw-1.0.0.0: (Fast) Dynamic Time Warping

Safe Haskell None Haskell2010

Data.DTW

Description

This module implements dynamic time warping as described here: http://en.wikipedia.org/w/index.php?title=Dynamic_time_warping

Additionally `fastDtw` is implemented as described in the paper: "FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space" by Stan Salvador and Philip Chan.

Please note that `fastDtw` is only an approximative solution. If you need the optimal solution and can bear with the heavily increased demand both in cpu and in memory you should use `dtwMemo` or `dtwMemoWindowed`.

## Example

````>>> ````-- create two sample datasets
````>>> ````let as = [ sin x | x <- [0,0.1..pi] ]
````>>> ````let bs = [ sin (x+0.1) | x <- [0,0.1..pi] ]
````>>> ````-- define a cost function between two datapoints
````>>> ````let dist x y = abs (x-y)
````>>> ````-- define a function that will half the size of a dataset (see below)
````>>> ````let shrink xs = case xs of (a:b:cs) -> (a+b)/2 : shrink cs; a:[] -> [a]; [] -> []
````>>> ````-- calculate the cost with fastDtw and dtwMemo for comparison
````>>> ````cost \$ fastDtw dist shrink 2 as bs :: Float
```0.19879311
`>>> ````cost \$ dtwMemo (\x y -> abs (x-y)) as bs :: Float
```0.19879311
```

## Some words on the shrink function

Care must be taken when choosing a shrink function. It's vital that the resolution is halfed, this is not exactly a problem with the algorithm but with the implementation. The lower resolution dataset should be an honest representation of the higher resolution dataset. For starters binning as in the example above should suffice.

Synopsis

# Documentation

dtwNaive :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> c Source

this is the naive implementation of dynamic time warping no caching what so ever is taking place this should not be used and is just used as a reference for the other implementations

dtwMemo :: (Ord c, Fractional c, DataSet a, DataSet b) => (Item a -> Item b -> c) -> a -> b -> Result c Source

this is the "standard" implementation of dynamic time warping O(N^2) is achieved by memoization of previous results

Arguments

 :: (Ord c, Fractional c, DataSet a) => (Item a -> Item a -> c) -> (a -> a) function that shrinks a dataset by a factor of two -> Int radius that the search window is expanded at each resolution level -> a first dataset -> a second dataset -> Result c result

this is the "fast" implementation of dynamic time warping as per the authors this methods calculates a good approximate result in O(N), depending on the usecase the windowsize should be tweaked

class DataSet dataset where Source

a generic dataset is basically just an indexing function | and an indicator of the dataset size

Associated Types

type Item dataset :: * Source

Methods

ix :: dataset -> Int -> Item dataset Source

len :: dataset -> Int Source

Instances

 DataSet [a] DataSet (Seq a) DataSet (Vector a) Unbox a => DataSet (Vector a) Storable a => DataSet (Vector a)

data Result a Source

Constructors

 Result Fieldscost :: a path :: Path

Instances

 Eq a => Eq (Result a) Read a => Read (Result a) Show a => Show (Result a)

type Path = [Index] Source

type Index = (Int, Int) Source