Fast time series classification using numerosity reduction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast time series classification using numerosity reduction

Full text

Pdf (637 KB)

Source

ACM International Conference Proceeding Series; Vol. 148 archive
Proceedings of the 23rd international conference on Machine learning table of contents

Pittsburgh, Pennsylvania

Pages: 1033 - 1040

Year of Publication: 2006

ISBN:1-59593-383-2

Authors

Xiaopeng Xi	University of California, Riverside, CA
Eamonn Keogh	University of California, Riverside, CA
Christian Shelton	University of California, Riverside, CA
Li Wei	University of California, Riverside, CA
Chotirat Ann Ratanamahatana	Chulalongkorn University, Bangkok, Thailand

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 90, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1143844.1143974 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Chen, L. & Kamel, M. S. (2005). Design of Multiple Classifier Systems for Time Series Data. Multiple Classifier Systems, pp. 216--225.
	2	Lei Chen , M. Tamer Öszu , Vincent Oria, Using multi-scale histograms to answer pattern existence and shape match queries, Proceedings of the 17th international conference on Scientific and statistical database management, p.217-226, June 27-29, 2005, Santa Barbara, CA
	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	Ada Wai-chee Fu , Eamonn Keogh , Leo Yung Hang Lau , Chotirat Ann Ratanamahatana, Scaling and time warping in time series querying, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	6	Geurts, P. (2002). Contributions to decision tree induction: bias/variance tradeoff and time series classification. Ph.D. thesis, University of Liege.
	7	Joshua Grass , Shlomo Zilberstein, Anytime algorithm development tools, ACM SIGART Bulletin, v.7 n.2, p.20-27, April 1996 [doi>10.1145/242587.242592]
	8	Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
	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.
	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	Hansheng Lei , Venu Govindaraju, Regression Time Warping for Similarity Measure of Sequence, Proceedings of the The Fourth International Conference on Computer and Information Technology (CIT'04), p.826-830, September 14-16, 2004
	15	Vasileios Megalooikonomou , Qiang Wang , Guo Li , Christos Faloutsos, A Multiresolution Symbolic Representation of Time Series, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.668-679, April 05-08, 2005 [doi>10.1109/ICDE.2005.10]
	16	Megalooikonomou, V. (2006). Personal Communication.
	17	Alex Nanopoulos , Rob Alcock , Yannis Manolopoulos, Feature-based classification of time-series data, Information processing and technology, Nova Science Publishers, Inc., Commack, NY, 2001
	18	Pekalska, E., Duin, R. P. W., & Paclik, P. (2006). Prototype Selection for Dissimilarity-Based Classifiers. Pattern Recognition, 39:2, pp. 189--208.
	19	Ratanamahatana, C. A. & Keogh, E. (2005). Three myths about Dynamic Time Warping Data Mining. SDM '05.
	20	Juan J. Rodríguez , Carlos J. Alonso, Interval and dynamic time warping-based decision trees, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968015]
	21	Juan J. Rodríguez , Carlos Alonso González , Henrik Boström, Learning First Order Logic Time Series Classifiers: Rules and Boosting, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.299-308, September 13-16, 2000
	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	Yutao Shou , Nikos Mamoulis , David W. Cheung, Fast and Exact Warping of Time Series Using Adaptive Segmental Approximations, Machine Learning, v.58 n.2-3, p.231-267, February 2005 [doi>10.1007/s10994-005-5828-3]
	24	Li Wei , Eamonn Keogh , Helga Van Herle , Agenor Mafra-Neto, Atomic Wedgie: Efficient Query Filtering for Streaming Times Series, Proceedings of the Fifth IEEE International Conference on Data Mining, p.490-497, November 27-30, 2005 [doi>10.1109/ICDM.2005.28]
	25	D. Randall Wilson , Tony R. Martinez, Instance Pruning Techniques, Proceedings of the Fourteenth International Conference on Machine Learning, p.403-411, July 08-12, 1997
	26	Yi Wu , Edward Y. Chang, Distance-function design and fusion for sequence data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031238]
	27	Zhu, Y. & Shasha, D. (2003). Query by Humming: a Time Series Database Approach, SIGMOD '03.

CITED BY 13

	Bachir Boucheham, Matching of quasi-periodic time series patterns by exchange of block-sorting signatures, Pattern Recognition Letters, v.29 n.4, p.501-514, March, 2008
	Jae-Gil Lee , Jiawei Han , Xiaolei Li , Hector Gonzalez, TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Khandoker Tarik-Ul Islam , Kamrul Hasan , Young-Koo Lee , Sungyoung Lee, Enhanced 1-NN time series classification using badness of records, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea
	Xiang Bai , Xingwei Yang , Longin Jan Latecki, Detection and recognition of contour parts based on shape similarity, Pattern Recognition, v.41 n.7, p.2189-2199, July, 2008
	Wanpracha Art Chaovalitwongse , Ya-Ju Fan , Rajesh C. Sachdeo, Support feature machine for classification of abnormal brain activity, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Hui Ding , Goce Trajcevski , Peter Scheuermann , Xiaoyue Wang , Eamonn Keogh, Querying and mining of time series data: experimental comparison of representations and distance measures, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Ankur Jain , Daniel Nikovski, Incremental exemplar learning schemes for classification on embedded devices, Machine Learning, v.72 n.3, p.189-203, September 2008
	Jin Shieh , Eamonn Keogh, iSAX: indexing and mining terabyte sized time series, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Vincent S. Tseng , Chao-Hui Lee, Effective temporal data classification by integrating sequential pattern mining and probabilistic induction, Expert Systems with Applications: An International Journal, v.36 n.5, p.9524-9532, July, 2009
	Omar U. Florez , SeungJin Lim, Discovery of time series in video data through distribution of spatiotemporal gradients, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Dragomir Yankov , Eamonn Keogh , Umaa Rebbapragada, Disk aware discord discovery: finding unusual time series in terabyte sized datasets, Knowledge and Information Systems, v.17 n.2, p.241-262, November 2008
	Jin Shieh , Eamonn Keogh, iSAX: disk-aware mining and indexing of massive time series datasets, Data Mining and Knowledge Discovery, v.19 n.1, p.24-57, August 2009
	Lexiang Ye , Eamonn Keogh, Time series shapelets: a new primitive for data mining, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France