Fast time series classification using numerosity reduction
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
Many algorithms have been proposed for the problem of time series classification. However, it is clear that one-nearest-neighbor with Dynamic Time Warping (DTW) distance is exceptionally difficult to beat. This approach has one weakness, however; it is computationally too demanding for many realtime applications. One way to mitigate this problem is to speed up the DTW calculations. Nonetheless, there is a limit to how much this can help. In this work, we propose an additional technique, numerosity reduction, to speed up one-nearest-neighbor DTW. While the idea of numerosity reduction for nearest-neighbor classifiers has a long history, we show here that we can leverage off an original observation about the relationship between dataset size and DTW constraints to produce an extremely compact dataset with little or no loss in accuracy. We test our ideas with a comprehensive set of experiments, and show that it can efficiently produce extremely fast accurate classifiers.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Dynamic Programming Algorithm Optimization for Spoken Word Recognition
Sakoe, H., & Chiba, S. (1978) · IEEE Transactions on Acoustics Speech and Signal Processing · doi:10.1109/tassp.1978.1163055 · Cited by 6,727
Nearest neighbor (NN) norms: NN pattern classification techniques
Dasarathy, B. V. (1991) · Medical Entomology and Zoology · Cited by 1,654
(2017) · Encyclopedia of Machine Learning and Data Mining · doi:10.1007/978-1-4899-7687-1_100318 · Cited by 1,037
Exact indexing of dynamic time warping
Keogh, E. (2002) · Cited by 594
Self-citationThree Myths about Dynamic Time Warping Data Mining
Ratanamahatana, C. A., & Keogh, E. (2005) · Proceedings of the 2005 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972757.50 · Cited by 393
Self-citationPrototype selection for dissimilarity-based classifiers
Pękalska, E., Duin, R. P. W., & Paclík, P. (2006) · Pattern Recognition · doi:10.1016/j.patcog.2005.06.012 · Cited by 302
Feature-based classification of time-series data
Νανόπουλος, Α., Alcock, R. J., & Manolopoulos, Y. (2001) · Cited by 259
Scaling and time warping in time series querying
Fu, A. W.-C., Keogh, E., Lau, L. Y. H., Ratanamahatana, C. A., & Wong, R. C.-W. (2008) · The VLDB Journal · doi:10.1007/s00778-006-0040-z · Cited by 219
Self-citationWilson, D. R., & Martinez, T. R. (1997) · Cited by 185
A Multiresolution Symbolic Representation of Time Series
Megalooikonomou, V., Wang, Q., Li, G., & Faloutsos, C. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2005.10 · Cited by 112
Interval and dynamic time warping-based decision trees
Rodríguez, J. J., & Alonso, C. J. (2004) · ACM Symposium on Applied Computing · doi:10.1145/967900.968015 · Cited by 87
Contributions to decision tree induction: bias/variance tradeoff and time series classification
Geurts, P. (2002) · ORBi (University of Liège) · Cited by 82
Embedding Time Series Data for Classification
Hayashi, A., Mizuhara, Y., & Suematsu, N. (2005) · Lecture notes in computer science · doi:10.1007/11510888_35 · Cited by 34
Modeling waveform shapes with random effects segmental hidden Markov models
Kim, S. Y., Smyth, P., & Luther, S. (2004) · Uncertainty in Artificial Intelligence · doi:10.5555/1036843.1036881 · Cited by 21
Using multi-scale histograms to answer pattern existence and shape match queries
Chen, L., Öszu, M. T., & Oria, V. (2005) · Cited by 19
Cited by
A review on time series data mining
Fu, T.-C. (2011) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2010.09.007 · Cited by 1,500
Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., & Keogh, E. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454226 · Cited by 1,354
Self-citationA global averaging method for dynamic time warping, with applications to clustering
Petitjean, F., Ketterlin, A., & Gançarski, P. (2011) · Pattern Recognition · doi:10.1016/j.patcog.2010.09.013 · Cited by 1,138
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
Time series shapelets: a new primitive for data mining
Ye, L., & Keogh, E. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557122 · Cited by 987
Self-citation
Metadata
- Authors
- Xi, X., Keogh, E., Shelton, C., Wei, L., & Ratanamahatana, C. A.
- Venue
- Proceedings of the 23rd international conference on Machine learning - ICML '06
- Publisher
- ACM Press
- Published
- 2006
- Pages
- 1033-1040
- OpenAlex
- W2039260438
- Cited by
- 591
- References
- 16
- FWCI
- 20.38
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.