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)

Input

  • derivative - [bool] Derivative DTW (DDTW).
  • startbc - [bool] (0, 0) boundary condition
  • steppattern - [string] step pattern (‘symmetric’, ‘asymmetric’, ‘quasisymmetric’)
  • wincond - [string] window condition (‘nowindow’, ‘sakoechiba’)
  • 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)

Input

  • x - [1D numpy array float / list] first time series
  • y - [1D numpy array float / list] second time series

Output

  • d - [float] normalized distance
  • self.px - [1D numpy array int] optimal warping path (for x time series) (for onlydist=False)
  • self.py - [1D numpy array int] optimal warping path (for y time series) (for onlydist=False)
  • self.cost - [2D numpy array float] cost matrix (for onlydist=False)

Example:

>>> 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.

Table Of Contents

Previous topic

Imputing

Next topic

Clustering

This Page