QP-DTW: Upgrading Dynamic Time Warping to Handle Quasi Periodic Time Series Alignment = QP-DTW: Upgrading Dynamic Time Warping to Handle Quasi Periodic Time Series Alignment

다국어 초록 (Multilingual Abstract)

Dynamic time warping (DTW) is the main algorithms for time series alignment. However, it is unsuitable for quasi-periodic time series. In the current situation, except the recently published the shape exchange algorithm (SEA) method and its derivatives, no other technique is able to handle alignment of this type of very complex time series. In this work, we propose a novel algorithm that combines the advantages of the SEA and the DTW methods. Our main contribution consists in the elevation of the DTW power of alignment from the lowest level (Class A, non-periodic time series) to the highest level (Class C, multiple-periods time series containing different number of periods each), according to the recent classification of time series alignment methods proposed by Boucheham (Int J Mach Learn Cybern, vol. 4, no. 5, pp. 537-550, 2013). The new method (quasi-periodic dynamic time warping [QP-DTW]) was compared to both SEA and DTW methods on electrocardiogram (ECG) time series, selected from the Massachusetts Institute of Technology - Beth Israel Hospital (MIT-BIH) public database and from the PTB Diagnostic ECG Database. Results show that the proposed algorithm is more effective than DTW and SEA in terms of alignment accuracy on both qualitative and quantitative levels. Therefore, QP-DTW would potentially be more suitable for many applications related to time series (e.g., data mining, pattern recognition, search/retrieval, motif discovery, classification, etc.).

참고문헌 (Reference)

1 D. J. Berndt, "Using dynamic time warping to find patterns in time series" 359-370, 1994

2 S. Salvador, "Toward accurate dynamic time warping in linear time and space" 11 (11): 561-580, 2007

3 J. R. Annam, "Time series clustering and analysis of ECG heart-beats using dynamic time warping" 1-3, 2011

4 C. A. Ratanahatano, "Three myths about dynamic time warping data mining" 506-510, 2005

5 J. B. Kruskall, "The symmetric time warping algorithm: from continuous to discrete;Time Warps, String Edits and Macromolecules" Addison-Wesley 1983

6 L. Chen, "Similarity-based retrieval of time-series data using multi-scale histograms" University of Waterloo 2003

7 E. J. Keogh, "Scaling up dynamic time warping for datamining applications" 285-289, 2000

8 B. Boucheham, "Reduced data similarity-based matching for time series patterns alignment" 31 (31): 629-638, 2010

9 A. Bahri, "Recherche par similarite de sequences temporelles dans les bases de donnees: un etat de l'art"

10 N. Begum, "Rare time series motif discovery from unbounded streams" 8 (8): 149-160, 2014

11 M. Awad, "Prediction of time series using RBF neural networks: a new approach of clustering" 6 (6): 138-143, 2009

12 A. L. Goldberger, "PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals" 101 (101): e215-e220, 2000

13 B. Boucheham, "Matching of quasi-periodic time series patterns by exchange of block-sorting signatures" 29 (29): 501-514, 2008

14 T. Bozkaya, "Matching and indexing sequences of different lengths" 128-135, 1997

15 "MIT-BIH Arrhythmia Database"

16 E. Keogh, "LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures" 882-893, 2006

17 I. Boulnemour, "I-SEA: improved shape exchange algorithm for quasi-periodic time series alignment" 1-6, 2015

18 R. Agrawal, "Foundations of Data Organization and Algorithms" Springer 69-84, 1993

19 Muhammad Zeeshan Arshad, "Fault Detection in the Semiconductor Etch Process Using the Seasonal Autoregressive Integrated Moving Average Modeling" 한국정보처리학회 10 (10): 429-442, 2014

20 G. Zhang, "Electrocardiogram data mining based on frame classification by dynamic time warping matching" 12 (12): 701-707, 2009

21 B. Boucheham, "Efficient matching of very complex time series" 4 (4): 537-550, 2013

22 L. Ulanova, "Efficient long-term degradation profiling in time series for complex physical systems" 2167-2176, 2015

23 L. Junkui, "Early abandon to accelerate exact dynamic time warping" 6 (6): 144-152, 2009

24 E. J. D. S. Luz, "ECG-based heartbeat classification for arrhythmia detection: a survey" 127 : 144-164, 2016

25 F. Petitjean, "Dynamic time warping averaging of time series allows faster and more accurate classification" 470-479, 2014

26 H. Sakoe, "Dynamic programming algorithm optimization for spoken word recognition" 26 (26): 43-49, 1978

27 E. J. Keogh, "Derivative dynamic time warping" 1-11, 2001

28 K. Vimala, "Classification of cardiac vascular disease from ECG signals for enhancing modern health care scenario" 2 (2): 63-72, 2013

29 A. Vishwa, "Arrhythmic ECG signal classification using machine learning techniques" 1 (1): 163-167, 2011

30 H. Shatkay, "Approximate queries and representations for large data sequences" 536-545, 1996

31 N. Begum, "Accelerating dynamic time warping clustering with a novel admissible pruning strategy" 49-58, 2015

32 B. Boucheham, "Abnormality detection in electrocardiograms by time series alignment" 1 (1): 6-10, 2011

33 T. C. Fu, "A review on time series data mining" 24 (24): 164-181, 2011

34 A. Barbulescu, "A hybrid approach for modeling financial time series" 9 (9): 327-335, 2012