In recent years, indexing, classification, clustering, and anomaly detection of time series data have become topics of great interest within the database/data mining community; within those data mining applications, the measurement of similarity between two time series is one of the most essential subroutines. The superiority of Dynamic Time Warping (DTW) similarity measure over Euclidean distance for these tasks has been well-demonstrated by many researchers. However, the greater accuracy of DTW comes at a price of forbiddingly higher CPU demands. The recent introduction of lower bounding function greatly helps address this problem, making DTW calculation tenable for larger datasets.; In spite of the great success of DTW in a variety of domains, there still are several persistent myths about it, causing great confusion in the literature. This work identifies and dispels these myths by empirical demonstration of the findings with a comprehensive set of experiments. Based on these findings, a novel framework, so called Ratanamahatana-Keogh Band ( R-K Band), is proposed, making DTW faster and more accurate by learning arbitrary constraints on the warping path of the DTW calculation. This proposed framework can conveniently replace the existing DTW distance measures, or can be incorporated into any other time series applications; the extensive empirical evaluations demonstrate significant improvement both in accuracy for classification problems, and in precision/recall for a relevance feedback system for time series retrieval. As an augmentation to this work, a bit-level dimensionality reduction technique, a clipped representation, is proposed and shown to improve the compression ratio by a wide margin, while being able to maintain or increase the tightness of its lower bound, allowing even faster nearest neighbor queries, especially in ones that require DTW distance measure.
展开▼
