### Navigation

- index
- modules |
- next |
- previous |
- mlpy 2.2.0 documentation »

# Distance Computations

## Dynamic Time Warping

Features:

> - Naive and Derivative [Keogh01] DTW
> - Symmetric, Asymmetric, Quasi-Symmetric implementation with Slope Constraint Condition P=0 [Sakoe78]
> - Sakoe-Chiba window condition [Sakoe78] option
> - Linear space-complexity implementation option

class `mlpy.``Dtw`(derivative=False, startbc=True, steppattern='symmetric0', wincond='nowindow', r=0.0, onlydist=True)

  Dynamic Time Warping.

  Example:

      >>> import numpy as np
      >>> import mlpy
      >>> x = np.array([1,1,2,2,3,3,4,4,4,4,3,3,2,2,1,1])
      >>> y = np.array([1,1,1,1,1,1,1,1,1,1,2,2,3,3,4,3,2,2,1,2,3,4])
      >>> mydtw = mlpy.Dtw(onlydist=False)
      >>> mydtw.compute(x, y)
      0.36842105263157893
      >>> mydtw.px
      array([ 0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  2,  3,  4,  5,  6,  7,  8,
              9, 10, 11, 12, 12, 12, 13, 14, 15], dtype=int32)
      >>> mydtw.py
      array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 14, 14,
             14, 15, 15, 16, 17, 18, 19, 20, 21], dtype=int32)

  Parameters :

  derivative : bool

    derivative DTW (DDTW)

  startbc : bool

    forces x=0 and y=0 boundary condition

  steppattern : string (‘symmetric’, ‘asymmetric’, ‘quasisymmetric’)

    step pattern

  wincond : string (‘nowindow’, ‘sakoechiba’)

    window condition

  r : float

    sakoe-chiba window length

  onlydist : bool

    linear space-complexity implementation. Only the current and previous columns are kept in memory.

  New in version 2.0.7.

  `compute`(x, y)

    Parameters :

    x : 1d ndarray or list

      first time series

    y : 1d ndarray or list

      second time series

    Returns :

    d : float

      normalized distance

    Attributes :

    Dtw.px : 1d ndarray int32

      optimal warping path (for x time series) (if onlydist=False)

    Dtw.py : 1d ndarray int32

      optimal warping path (for y time series) (if onlydist=False)

    Dtw.cost : 2dndarray float

      cost matrix (if onlydist=False)

Extended example (requires matplotlib module):

    >>> import numpy as np
    >>> import matplotlib.pyplot as plt
    >>> import mlpy
    >>> x = np.array([1,1,2,2,3,3,4,4,4,4,3,3,2,2,1,1])
    >>> y = np.array([1,1,1,1,1,1,1,1,1,1,2,2,3,3,4,3,2,2,1,2,3,4])
    >>> plt.figure(1)
    >>> plt.subplot(211)
    >>> plt.plot(x)
    >>> plt.subplot(212)
    >>> plt.plot(y)
    >>> plt.show()

    >>> mydtw = mlpy.Dtw()
    >>> d = mydtw.compute(x, y)
    >>> plt.figure(2)
    >>> plt.imshow(mydtw.cost.T, interpolation='nearest', origin='lower')
    >>> plt.plot(mydtw.px, mydtw.py, 'r')
    >>> plt.show()

## Minkowski Distance

class `mlpy.``Minkowski`(p)

  Computes the Minkowski distance between two vectors `x` and `y`.

  {||x-y||}_p = (\sum{|x_i - y_i|^p})^{1/p}.

  Initialize Minkowski class.

  Parameters :

  p : float

    The norm of the difference {||x-y||}_p

  New in version 2.0.8.

  `compute`(x, y)

    Compute Minkowski distance

    Parameters :

    x : ndarray

      An 1-dimensional vector.

    y : ndarray

      An 1-dimensional vector.

    Returns :

    d : float

      The Minkowski distance between vectors `x` and `y`

[Senin08] | Pavel Senin. Dynamic Time Warping Algorithm Review

[Keogh01] | Eamonn J. Keogh and Michael J. Pazzani. Derivative Dynamic Time Warping. First SIAM International Conference on Data Mining (SDM 2001), 2001.

[Sakoe78] | (1, 2) Hiroaki Sakoe and Seibi Chiba. Dynamic Programming Algorithm Optimization for Spoken Word Recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing. Volume 26, 1978.

### Navigation

- index
- modules |
- next |
- previous |
- mlpy 2.2.0 documentation »