Paper Info
Title
Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy
Abstract
Clustering time series is a useful operation in its own right, and an important subroutine in many higher-level data mining analyses, including data editing for classifiers, summarization, and outlier detection. While it has been noted that the general superiority of Dynamic Time Warping (DTW) over Euclidean Distance for similarity search diminishes as we consider ever larger datasets, as we shall show, the same is not true for clustering. Thus, clustering time series under DTW remains a computationally challenging task. In this work, we address this lethargy in two ways. We propose a novel pruning strategy that exploits both upper and lower bounds to prune off a large fraction of the expensive distance calculations. This pruning strategy is admissible; giving us provably identical results to the brute force algorithm, but is at least an order of magnitude faster. For datasets where even this level of speedup is inadequate, we show that we can use a simple heuristic to order the unavoidable calculations in a most-useful-first ordering, thus casting the clustering as an anytime algorithm. We demonstrate the utility of our ideas with both single and multidimensional case studies in the domains of astronomy, speech physiology, medicine and entomology.
Year
DOI
Venue
2015
10.1145/2783258.2783286
ACM Knowledge Discovery and Data Mining
Keywords
Field
DocType
Clustering,Time Series,Anytime Algorithms
Data mining,CURE data clustering algorithm,Dynamic time warping,Computer science,Artificial intelligence,Cluster analysis,Canopy clustering algorithm,Clustering high-dimensional data,Data stream clustering,Correlation clustering,Algorithm,Constrained clustering,Machine learning
Conference
Citations 
PageRank 
References 
26
0.95
22
Authors
4
Name
Order
Citations
PageRank
Nurjahan Begum1562.24
Liudmila Ulanova2876.23
Jun Wang314415.26
Eamonn J. Keogh411859645.93