search

slaypni / fastdtw

A Python implementation of FastDTW
MIT License
794 stars 123 forks source link

Add partial matching #59

Open trueroad opened 1 year ago

trueroad commented 1 year ago

Add partial matching

This pull request adds partial matching DTW like #27 . The difference between #27 and this is as follows.

Examples

>>> import numpy as np
>>> import fastdtw
>>> x = np.array([1, 2, 3, 4, 5], dtype='float')
>>> y = np.array([2, 3, 4], dtype='float')
>>> fastdtw.fastdtw(x, y)
(2.0, [(0, 0), (1, 0), (2, 1), (3, 2), (4, 2)])
>>> fastdtw.fastdtw(x, y, b_partial_start=True)
(1.0, [(1, 0), (2, 1), (3, 2), (4, 2)])
>>> fastdtw.fastdtw(x, y, b_partial_end=True)
(1.0, [(0, 0), (1, 0), (2, 1), (3, 2)])
>>> fastdtw.fastdtw(x, y, b_partial_start=True, b_partial_end=True)
(0.0, [(1, 0), (2, 1), (3, 2)])

I created this pull request with reference to SPRING [1][2].

SPRING is a streaming method for subsequence matching in data streams. It differs from regular DTW in that it calculates partial matching.

In SPRING, the starting point for partial matching is obtained by star-padding and STWM. This commit adds b_partial_start flag, and if it is True, __dtw() calculates the matching start point by the star-padding-like and the STWM-like behavior.

In SPRING, the ending point for the partial matching is obtained as the ending point of the optimal subsequence as the data streaming progresses. However, __dtw() does not handle data streams. This commit adds b_partial_end flag, and if it is True, __dtw() calculates the matching ending point as the point with the lowest DTW distance.

[1] Yasushi Sakurai, Christos Faloutsos, Masashi Yamamuro: Stream Monitoring under the Time Warping Distance, ICDE2007, https://doi.org/10.1109/ICDE.2007.368963

[2] Yasushi Sakurai, Christos Faloutsos, Masashi Yamamuro: Stream Processing under the Dynamic Time Warping Distance, DEWS2007, https://www.ieice.org/iss/de/DEWS/DEWS2007/pdf/l6-5.pdf