More Web Proxy on the site http://driver.im/

Article

Fast time series classification using numerosity reduction

Authors:

Christian Shelton,

Chotirat Ann RatanamahatanaAuthors Info & Claims

ICML '06: Proceedings of the 23rd international conference on Machine learning

Pages 1033 - 1040

https://doi.org/10.1145/1143844.1143974

Published: 25 June 2006 Publication History

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.

References

[1]

Chen, L. & Kamel, M. S. (2005). Design of Multiple Classifier Systems for Time Series Data. Multiple Classifier Systems, pp. 216--225.]]

Digital Library

[2]

Chen, L., Özsu, M. T., & Oria, V. (2005). Using Multi-Scale Histograms to Answer Pattern Existence and Shape Match Queries. SSDBM '05.]]

Digital Library

[3]

Dasarathy, B. V. (1991). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, pp. 388--397.]]

[4]

Eads, D., Glocer, K., Perkins, S., & Theiler, J. (2005). Grammar-guided feature extraction for time series classification. NIPS '05.]]

[5]

Fu, A. W., Keogh, E., Lau, L. Y. H., & Ratanamahatana, C. A. (2005). Scaling and Time Warping in Time Series Querying. VLDB '05, pp. 649--660.]]

Digital Library

[6]

Geurts, P. (2002). Contributions to decision tree induction: bias/variance tradeoff and time series classification. Ph.D. thesis, University of Liege.]]

[7]

Grass, J. & Zilberstein, S. (1996). Anytime Algorithm Development Tools. Sigart Artificial Intellligence, Vol 7, ACM Press.]]

Digital Library

[8]

Han, J. & Kamber, M. (2000). Data Mining Concepts and Techniques. Morgan Kaufmann Publishers.]]

Digital Library

[9]

Hayashi, A., Mizuhara, Y., & Suematsu, N. (2005). Embedding Time Series Data for Classification. Machine Learning and Data Mining in Pattern Recognition, pp. 356--365.]]

Digital Library

[10]

Karydis, I., Nanopoulos, A., Papadopoulos, A., & Manolopoulos, Y. (2005). Music Retrieval in P2P Networks Under the Warping Distance, 7th International Conference on Enterprise Information Systems.]]

[11]

Keogh, E. (2002). Exact Indexing of Dynamic Time Warping. VLDB '02, pp. 406--417, Hong Kong, Aug 20--23.]]

[12]

Keogh, E. (2006). UCR Time Series Archive www.cs.ucr.edu/~eamonn/TSDMA/]]

[13]

Kim, S., Smyth, P., & Luther, S. (2004). Modeling waveform shapes with random effects segmental hidden Markov Models. Technical Report, UCI-ICS 04--05.]]

[14]

Lei, H. & Govindaraju, V. (2004). Regression Time Warping for Similarity Measure of Sequence. CIT'04, pp. 826--830.]]

Digital Library

[15]

Megalooikonomou, V., Wang, Q., Li, G., & Faloutsos, C. A. (2005). Multiresolution Symbolic Representation of Time Series. ICDE '05, pp. 668--679.]]

Digital Library

[16]

Megalooikonomou, V. (2006). Personal Communication.]]

[17]

Nanopoulos, A., Alcock, R., & Manolopoulos, Y. (2001). Feature-based Classification of Time-series Data. International Journal of Computer Research, pp. 49--61.]]

Digital Library

[18]

Pekalska, E., Duin, R. P. W., & Paclik, P. (2006). Prototype Selection for Dissimilarity-Based Classifiers. Pattern Recognition, 39:2, pp. 189--208.]]

Digital Library

[19]

Ratanamahatana, C. A. & Keogh, E. (2005). Three myths about Dynamic Time Warping Data Mining. SDM '05.]]

[20]

Rodríguez, J. J. & Alonso, C. J. (2004). Interval and dynamic time warping-based decision trees. In Proceedings of the 2004 ACM symposium on Applied computing (SAC), pp. 548--552.]]

Digital Library

[21]

Rodríguez, J. J., Alonso, C. J., & Boströöm, H. (2000). Learning First Order Logic Time Series Classifiers: Rules and Boosting. PKDD '00, pp. 299--308.]]

Digital Library

[22]

Sakoe, H. & Chiba, S. Dynamic programming algorithm optimization for spoken word recognition. (1978). IEEE Trans. Acoustics, Speech, and Signal Proc., Vol. ASSP-26.]]

[23]

Shou, Y., Mamoulis, N., & Cheung, D. W. (2005). Fast and exact warping of time series using adaptive segmental approximations. Machine Learning, Vol 28, pp. 231--267.]]

Digital Library

[24]

Wei, L., Keogh, E., Van Herle, H., & Mafra-Neto, A. (2005). Atomic Wedgie: Efficient Query Filtering for Streaming Time Series. ICDM '05, pp. 490--497.]]

Digital Library

[25]

Wilson, D. R. & Martinez, T. R. (1997). Instance Pruning Techniques. ICML '97, Morgan Kaufmann, pp. 403--411.]]

Digital Library

[26]

Wu, Y. & Chang, E. Y. (2004). Distance-function design and fusion for sequence data. CIKM '04, pp. 324--333.]]

Digital Library

[27]

Zhu, Y. & Shasha, D. (2003). Query by Humming: a Time Series Database Approach, SIGMOD '03.]]

Digital Library

Cited By

Mao YLi JQi ZYuan JXu XJin XDu X(2024)Research on Outlier Detection Methods for Dam Monitoring Data Based on Post-Data ClassificationBuildings10.3390/buildings1409275814:9(2758)Online publication date: 3-Sep-2024
https://doi.org/10.3390/buildings14092758
Rubaiyat ALi SYin XShifat-E-Rabbi MZhuang YRohde G(2024)End-to-End Signal Classification in Signed Cumulative Distribution Transform SpaceIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.337245546:9(5936-5950)Online publication date: Sep-2024
https://doi.org/10.1109/TPAMI.2024.3372455
Buza K(2024)Activity Recognition Based on Accelerometer Data with Enhanced ROCKET Algorithm2024 IEEE 18th International Symposium on Applied Computational Intelligence and Informatics (SACI)10.1109/SACI60582.2024.10619836(000321-000326)Online publication date: 23-May-2024
https://doi.org/10.1109/SACI60582.2024.10619836
Show More Cited By

Index Terms

Fast time series classification using numerosity reduction
1. Computing methodologies
  1. Machine learning
2. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Time series analysis

Recommendations

Scalable time series classification

Time series classification tries to mimic the human understanding of similarity. When it comes to long or larger time series datasets, state-of-the-art classifiers reach their limits because of unreasonably high training or testing times. One ...
FastEE: Fast Ensembles of Elastic Distances for time series classification
Abstract
In recent years, many new ensemble-based time series classification (TSC) algorithms have been proposed. Each of them is significantly more accurate than their predecessors. The Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-...
Applying General-Purpose Data Reduction Techniques for Fast Time Series Classification
Proceedings of the 23rd International Conference on Artificial Neural Networks and Machine Learning ICANN 2013 - Volume 8131

The one-nearest neighbour classifier is a widely-used time series classification method. However, its efficiency depends on the size of the training set as well as on data dimensionality. Although many speed-up methods for fast time series ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '06: Proceedings of the 23rd international conference on Machine learning

June 2006

1154 pages

ISBN:1595933832

DOI:10.1145/1143844

Program Chairs:
William Cohen,
Andrew Moore

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

ICML '06 Paper Acceptance Rate 140 of 548 submissions, 26%;

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

350
Total Citations
View Citations
2,518
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)5

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mao YLi JQi ZYuan JXu XJin XDu X(2024)Research on Outlier Detection Methods for Dam Monitoring Data Based on Post-Data ClassificationBuildings10.3390/buildings1409275814:9(2758)Online publication date: 3-Sep-2024
https://doi.org/10.3390/buildings14092758
Rubaiyat ALi SYin XShifat-E-Rabbi MZhuang YRohde G(2024)End-to-End Signal Classification in Signed Cumulative Distribution Transform SpaceIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.337245546:9(5936-5950)Online publication date: Sep-2024
https://doi.org/10.1109/TPAMI.2024.3372455
Buza K(2024)Activity Recognition Based on Accelerometer Data with Enhanced ROCKET Algorithm2024 IEEE 18th International Symposium on Applied Computational Intelligence and Informatics (SACI)10.1109/SACI60582.2024.10619836(000321-000326)Online publication date: 23-May-2024
https://doi.org/10.1109/SACI60582.2024.10619836
Khadiche MBoucheham BBougueroua S(2024)Ramer-Douglas-Peucker Dynamic Time Warping (RDP-DTW): A Novel Data Reduction Based Dynamic Time Warping method for Time Series Classification2024 International Conference on Advances in Electrical and Communication Technologies (ICAECOT)10.1109/ICAECOT62402.2024.10828578(1-5)Online publication date: 1-Oct-2024
https://doi.org/10.1109/ICAECOT62402.2024.10828578
Li HRajbahadur GLin DBezemer CJiang Z(2024)Keeping Deep Learning Models in Check: A History-Based Approach to Mitigate OverfittingIEEE Access10.1109/ACCESS.2024.340254312(70676-70689)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3402543
Namoano BLatsou CErkoyuncu J(2024)Multi-channel anomaly detection using graphical modelsJournal of Intelligent Manufacturing10.1007/s10845-024-02447-7Online publication date: 13-Jul-2024
https://doi.org/10.1007/s10845-024-02447-7
Ozyegen OMalik GCevik MIoi KEl Mokhtari K(2024)A unified framework for financial commentary predictionInformation Technology and Management10.1007/s10799-024-00439-wOnline publication date: 5-Sep-2024
https://doi.org/10.1007/s10799-024-00439-w
Xu HWang KSun WChen MLi HZhao H(2024)DDTM: A Distance-Based Data Transformation Method for Time Series ClassificationArtificial Intelligence and Robotics10.1007/978-981-99-9109-9_10(94-111)Online publication date: 4-Jan-2024
https://doi.org/10.1007/978-981-99-9109-9_10
Buza KAntal M(2024)ROCKET with Dynamic Convolution for Time Series ClassificationAdvances in Computational Collective Intelligence10.1007/978-3-031-70248-8_21(271-282)Online publication date: 8-Sep-2024
https://doi.org/10.1007/978-3-031-70248-8_21
Pocock CPorter CAgius M(2024)Co-producing Gesture-Based AT - A Case StudyDesign for Equality and Justice10.1007/978-3-031-61698-3_28(277-282)Online publication date: 9-Jul-2024
https://doi.org/10.1007/978-3-031-61698-3_28
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten