Dynamic Time Warping (DTW)¶
Standard DTW¶
- mlpy.dtw_std(x, y, dist_only=True)¶
Standard DTW as described in [Muller07], using the Euclidean distance (absolute value of the difference) or squared Euclidean distance (as in [Keogh01]) as local cost measure.
Parameters : - x : 1d array_like object (N)
first sequence
- y : 1d array_like object (M)
second sequence
- dist_only : bool
compute only the distance
- squared : bool
squared Euclidean distance
Returns : - dist : float
unnormalized minimum-distance warp path between sequences
- cost : 2d numpy array (N,M) [if dist_only=False]
accumulated cost matrix
- path : tuple of two 1d numpy array (path_x, path_y) [if dist_only=False]
warp path
[Muller07] (1, 2) M Muller. Information Retrieval for Music and Motion. Springer, 2007. [Keogh01] E J Keogh, M J Pazzani. Derivative Dynamic Time Warping. In First SIAM International Conference on Data Mining, 2001.
Example
Reproducing the Fig. 2 example in [Salvador04].
>>> import mlpy
>>> import matplotlib.pyplot as plt
>>> import matplotlib.cm as cm
>>> x = [0,0,0,0,1,1,2,2,3,2,1,1,0,0,0,0]
>>> y = [0,0,1,1,2,2,3,3,3,3,2,2,1,1,0,0]
>>> dist, cost, path = mlpy.dtw_std(x, y, dist_only=False)
>>> dist
0.0
>>> fig = plt.figure(1)
>>> ax = fig.add_subplot(111)
>>> plot1 = plt.imshow(cost.T, origin='lower', cmap=cm.gray, interpolation='nearest')
>>> plot2 = plt.plot(path[0], path[1], 'w')
>>> xlim = ax.set_xlim((-0.5, cost.shape[0]-0.5))
>>> ylim = ax.set_ylim((-0.5, cost.shape[1]-0.5))
>>> plt.show()
| [Salvador04] | S Salvador and P Chan. FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. 3rd Wkshp. on Mining Temporal and Sequential Data, ACM KDD ‘04, 2004. |
Subsequence DTW¶
- mlpy.dtw_subsequence(x, y)¶
Subsequence DTW as described in [Muller07], assuming that the length of y is much larger than the length of x and using the Manhattan distance (absolute value of the difference) as local cost measure.
Returns the subsequence of y that are close to x with respect to the minimum DTW distance.
Parameters : - x : 1d array_like object (N)
first sequence
- y : 1d array_like object (M)
second sequence
Returns : - dist : float
unnormalized minimum-distance warp path between x and the subsequence of y
- cost : 2d numpy array (N,M) [if dist_only=False]
complete accumulated cost matrix
- path : tuple of two 1d numpy array (path_x, path_y)
warp path