Making the dynamic time warping distance warping-invariant. (October 2019)

• Record Type: Journal Article
• Authors: Jain, Brijnesh J.
• Is Part Of: Pattern recognition. Volume 94(2019:Oct.)
• Page Start: 35
• Page End: 52
• Publication Date: 2019-10
• Subjects: Time series -- Dynamic time warping -- Semi-metric -- Nearest-neighbor rule; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.05.016
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: The dtw-distance is not warping-invariant. Lack of warping-invariance contributes to inconsistencies and peculiarities. Converts dtw-distance into a warping-invariant semi-metric. Proposed semi-metric is more efficient than dtw-distance. Error-rates of nn-classifiers in semi-metric and dtw-space are practically equivalent. Abstract: The literature postulates that the dynamic time warping (dtw) distance can cope with temporal variations but stores and processes time series in a form as if the dtw-distance cannot cope with such variations. To address this inconsistency, we first show that the dtw-distance is not warping-invariant—despite its name and contrary to its characterization in some publications. The lack of warping-invariance contributes to the inconsistency mentioned above and to a strange behavior. To eliminate these peculiarities, we convert the dtw-distance to a warping-invariant semi-metric, called time-warp-invariant (twi) distance. Empirical results suggest that the error rates of the twi and dtw nearest-neighbor classifier are practically equivalent in a Bayesian sense. However, the twi-distance requires less storage and computation time than the dtw-distance for a broad range of problems. These results challenge the current practice of applying the dtw-distance in nearest-neighbor classification and suggest the proposed twi-distance as a more efficient and consistent option.