smile.math.distance

Class DynamicTimeWarping<T>

java.lang.Object

smile.math.distance.DynamicTimeWarping<T>

All Implemented Interfaces:

java.io.Serializable, Distance<T[]>

public class DynamicTimeWarping<T>
extends java.lang.Object
implements Distance<T[]>, java.io.Serializable

Dynamic time warping is an algorithm for measuring similarity between two sequences which may vary in time or speed. DTW has been applied to video, audio, and graphics - indeed, any data which can be turned into a linear representation can be analyzed with DTW. A well known application has been automatic speech recognition, to cope with different speaking speeds.

In general, DTW is a method that allows a computer to find an optimal match between two given sequences (e.g. time series) with certain restrictions. The sequences are "warped" non-linearly in the time dimension to determine a measure of their similarity independent of certain non-linear variations in the time dimension. This sequence alignment method is often used in the context of hidden Markov models.

One example of the restrictions imposed on the matching of the sequences is on the monotonicity of the mapping in the time dimension. Continuity is less important in DTW than in other pattern matching algorithms; DTW is an algorithm particularly suited to matching sequences with missing information, provided there are long enough segments for matching to occur.

The optimization process is performed using dynamic programming, hence the name.

The extension of the problem for two-dimensional "series" like images (planar warping) is NP-complete, while the problem for one-dimensional signals like time series can be solved in polynomial time.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
DynamicTimeWarping(Distance<T> distance) Constructor.
DynamicTimeWarping(Distance<T> distance, double radius) Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.

Method Summary

Modifier and Type	Method and Description
static double	d(double[] x1, double[] x2) Dynamic time warping without path constraints.
static double	d(double[] x1, double[] x2, int radius) Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.
static double	d(float[] x1, float[] x2) Dynamic time warping without path constraints.
static double	d(float[] x1, float[] x2, int radius) Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.
static double	d(int[] x1, int[] x2) Dynamic time warping without path constraints.
static double	d(int[] x1, int[] x2, int radius) Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.
double	d(T[] x1, T[] x2) Returns the distance measure between two objects.
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

DynamicTimeWarping

public DynamicTimeWarping(Distance<T> distance)

Constructor. Dynamic time warping without path constraints.

DynamicTimeWarping

public DynamicTimeWarping(Distance<T> distance,
                          double radius)

Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.

Parameters:

radius - the window width of Sakoe-Chiba band in terms of percentage of sequence length.

Method Detail

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

d

public double d(T[] x1,
                T[] x2)

Description copied from interface: Distance

Returns the distance measure between two objects.

Specified by:

d in interface Distance<T[]>

d

public static double d(int[] x1,
                       int[] x2)

Dynamic time warping without path constraints.

d

public static double d(int[] x1,
                       int[] x2,
                       int radius)

Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.

Parameters:

radius - the window width of Sakoe-Chiba band.

d

public static double d(float[] x1,
                       float[] x2)

Dynamic time warping without path constraints.

d

public static double d(float[] x1,
                       float[] x2,
                       int radius)

Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.

Parameters:

radius - the window width of Sakoe-Chiba band.

d

public static double d(double[] x1,
                       double[] x2)

Dynamic time warping without path constraints.

d

public static double d(double[] x1,
                       double[] x2,
                       int radius)

Dynamic time warping with Sakoe-Chiba band, which primarily to prevent unreasonable warping and also improve computational cost.

Parameters:

radius - the window width of Sakoe-Chiba band.