Package smile.math.distance

Class DynamicTimeWarping<T>

java.lang.Object
smile.math.distance.DynamicTimeWarping<T>
Type Parameters:
T - the input type of distance function.
All Implemented Interfaces:
Serializable, ToDoubleBiFunction<T[],T[]>, Distance<T[]>
public class DynamicTimeWarping<T> extends Object implements Distance<T[]>
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:

  • Constructor Summary

    Constructors
    Constructor
    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
    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.
    String
    toString()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    Methods inherited from interface smile.math.distance.Distance

    apply, applyAsDouble, D, D

  • Constructor Details

    • DynamicTimeWarping

      public DynamicTimeWarping(Distance<T> distance)
      Constructor. Dynamic time warping without path constraints.
      Parameters:
      distance - the distance function.

    • 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:
      distance - the distance function.
      radius - the window width of Sakoe-Chiba band in terms of percentage of sequence length.

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class 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>
      Parameters:
      x1 - an object.
      x2 - an object.
      Returns:
      the distance.

    • d

      public static double d(int[] x1, int[] x2)
      Dynamic time warping without path constraints.
      Parameters:
      x1 - a vector.
      x2 - a vector.
      Returns:
      the distance.

    • 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:
      x1 - a vector.
      x2 - a vector.
      radius - the window width of Sakoe-Chiba band.
      Returns:
      the distance.

    • d

      public static double d(float[] x1, float[] x2)
      Dynamic time warping without path constraints.
      Parameters:
      x1 - a vector.
      x2 - a vector.
      Returns:
      the distance.

    • 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:
      x1 - a vector.
      x2 - a vector.
      radius - the window width of Sakoe-Chiba band.
      Returns:
      the distance.

    • d

      public static double d(double[] x1, double[] x2)
      Dynamic time warping without path constraints.
      Parameters:
      x1 - a vector.
      x2 - a vector.
      Returns:
      the distance.

    • 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:
      x1 - a vector.
      x2 - a vector.
      radius - the window width of Sakoe-Chiba band.
      Returns:
      the distance.