Data.DTW

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.

Documentation

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

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

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

fastDtw

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

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

Associated Types

type Item dataset :: *

Methods

ix :: dataset -> Int -> Item dataset

len :: dataset -> Int

Instances

DataSet [a]

DataSet (Seq a)

DataSet (Vector a)

Unbox a => DataSet (Vector a)

Storable a => DataSet (Vector a)

data Result a

Constructors

Result

Fields

cost :: a

path :: Path

Instances

Eq a => Eq (Result a)

Read a => Read (Result a)

Show a => Show (Result a)

type Path = [Index]

type Index = (Int, Int)