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()
_images/time_series.png
>>> 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()
_images/dtw.png

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.