ShapeDTW: Shape Dynamic Time Warping. (February 2018)

• Record Type: Journal Article
• Authors: Zhao, Jiaping; Itti, Laurent
• Is Part Of: Pattern recognition. Volume 74(2018:Feb.)
• Page Start: 171
• Page End: 184
• Publication Date: 2018-02
• Subjects: Dynamic Time Warping -- Sequence alignment -- Time series classification; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.09.020
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Developed an improved sequence alignment algorithm, named shapeDTW, which augments the traditional Dynamic Time Warping (DTW) by local temporal shape information. shapeDTW performs significantly better than DTW under the one nearest neighbor classifier for time series classification; to be concrete, it wins DTW on 64 (out of 84) UCR time series datasets. shapeDTW is essentially a DTW algorithm, therefore runs efficiently. Moreover, shapeDTW is insensitive to one design parameter. Abstract: Dynamic Time Warping (DTW) is an algorithm to align temporal sequences with possible local non-linear distortions, and has been widely applied to audio, video and graphics data alignments. DTW is essentially a point-to-point matching method under some boundary and temporal consistency constraints. Although DTW obtains a global optimal solution, it does not necessarily achieve locally sensible matchings. Concretely, two temporal points with entirely dissimilar local structures may be matched by DTW. To address this problem, we propose an improved alignment algorithm, named shape Dynamic Time Warping (shapeDTW), which enhances DTW by taking point-wise local structural information into consideration. shapeDTW is inherently a DTW algorithm, but additionally attempts to pair locally similar structures and to avoid matching points with distinct neighborhood structures. We apply shapeDTW to align audio signal pairs having ground-truth alignments, as well as artificially simulated pairs of aligned sequences, and obtain quantitatively much lower alignment errors than DTW and its two variants. When shapeDTW is used as a distance measure in a nearest neighbor classifier (NN-shapeDTW) to classify time series, it beats DTW on 64 out of 84 UCR time series datasets, with significantly improved classification accuracies. By using a properly designed local structure descriptor, shapeDTW improves accuracies by more than 10% on 18 datasets. To the best of our knowledge, shapeDTW is the first distance measure under the nearest neighbor classifier scheme to significantly outperform DTW, which had been widely recognized as the best distance measure to date. Our code is publicly accessible at: https://github.com/jiapingz/shapeDTW .