Total views : 339

Efficient Dynamic Time Warping for Time Series Classification

Affiliations

  • Research and Development Center, Bharathiar University, Coimbatore - 641046, Tamil Nadu, India
  • Department of CSE, VIIT Visakhapatnam, Gajuwaka - 530046, Andhra Pradesh, India
  • Department of Computer Science, Central University of Kerala, Padannakkad, Nileshwar - 671314, Kerala, India

Abstract


Background/Objective: Dynamic Time Warping (DTW), a similarity measure works in O(n2) complexity. Cause of this it will be used for small datasets only. Methods/Statistical Analysis: In this work, we introduced Efficient DTW (EDTW), which works in linear time. It uses two level approaches. In the first level data reduction is performed, and in the second level warping distance and path are calculated. Findings: While calculating the values of distance matrix, values along the warping path only considered and calculated. For time series of length n, maximum n values of distance matrix are calculated. So it works in linear time. Improvements/Applications: We applied this distance measure to UCR Time Series archive and calculated error rate of 1NN classification. Most of the cases it is matching, some cases it is better, and some other cases error rate is high.

Keywords

Dynamic Time Warping, Efficient DTW, 1NN Classification, Time Series Classification, UCR Time Series Data Sets.

Full Text:

 |  (PDF views: 438)

References


  • Ratanamahatana CA, Keogh E. Everything you know about dynamic time warping is wrong. International Conference on Knowledge Discovery and Data Mining (KDD); Seattle, WA. 2004 Aug. p. 22–5.
  • Muller M. Information Retrieval for Music and Motion. Springer; 2007.
  • Lia H, Chen X. Unifying time reference f smart card data using dynamic time warping. Procedia Engineering. 2016; 137:513–22.
  • Kumar V. A survey on time series data mining. IJIRCCE. 2014; 2(5):170–9.
  • Gupta L, Molfese D, Tammana R, Simos P. Non-linear alignment and averaging for estimating the evoked potential. IEEE Transactions on Biomedical Engineering. 1996; 43(4):346–56.
  • Keogh E, Pazzani M. Scaling up dynamic time warping for data mining applications. Proceedings of the 6th ACM SIGKDD; Boston, Massachusetts. 2000. p. 285–9.
  • Niennattrakul V, Ratanamahatana C A. Learning DTW Global constraint for time series classification. SIGKDD. 2009 Feb; 1–8.
  • Santosh VC. Spoken digits recognition using weighted MFCC and improved features for dynamic time warping. IJCA. 2012 Feb; 40(3):975–8887.
  • Forman G. An extensive empirical study of feature selection metrics for text classification. J Mach Learn. 2003 Mar; 1289–305.
  • Kim S, Park S, Chu W. An index-based approach for similarity search supporting time warping in large sequence databases. Proceedings of 17th International Conference on Data Engineering; Heidelberg, Germany. 2001. p. 607–14.
  • Stan S, Philip C. Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space, Intelligent Data Analysis archive. 2007 Oct; 11(5).
  • Arun KP. Data Mining Technique. University press; 2001.
  • Muller M. Dynamic Time Warping. Information Retrival for Music and Motion. 2007; 69–84.
  • Yanping C, Keogh E, Bing H, Nurjahan B, Anthony B, Abdullah M, Gustavo B. The UCR Time Series Classification Archive. 2015.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.