## Imen Boulnemour* and Bachir Boucheham*## |

PRD(X,Y) | PRD(X,X _{ rec } ) | PRD(Y,Y _{ rec } ) | Corr(X,Y) | Corr(X,X _{ rec } ) | Corr(Y,Y _{ rec } ) | |

SEA | - | 32.0207 | 50.3374 | - | 0.9566 | 0.9561 |

QP-DTW | - | 16.8858 | 21.6276 | - | 0.9906 | 0.9817 |

DTW | 68.0843 | - | - | 0.7582 | - | - |

The visual inspection of Fig. 10 and the numerical results reported in Table 1 show that despite all the problems previously cited, QP-DTW arrives to align these particularly very complex time series. We see also that SEA method doesn't do a good alignment because time series Y and its reconstruction are almost detached, only the QRSs have been correctly aligned. The DTW done a very bad alignment because, the second QRS of the time series Y haven’t been aligned with the QRSs of the time series X.

6.1. Comparison of Similar Traces from the MIT-BIH ECG DatabaseFig. 11 shows the case of two plots of the same record with 1,000 samples of the time series rec.113 for X and 1,200 samples of the same time series with a shift of 30 seconds for Y. Fig. 11(a) presents the original time series. They have some peaks of amplitudes with heights slightly difference due to low frequency noise. Fig. 11(b) shows the alignment performed by SEA. We see that the original and the reconstructed time series are detached because of the problem of low frequency noise. Fig. 11(c) shows that despite all the problems mentioned above, QP-DTW done an almost perfect reconstruction, to the point that it is difficult to distinguish between the original and the reconstructed time series. Fig. 11(d) shows the misalignment of X and Y done by DTW because of the problem of quasi periodicity and low frequency noise of the time series. The numerical results presented in Table 2 confirm this state with a very low error rate (PRD) and a very high correlation in favor of QP-DTW. In contrary they indicate a high error rate (PRD) for DTW and SEA, an average correlation for SEA and a low correlation for DTW.

Table 2.

ECG segments | DTW | SEA | QP-DTW | |||

PRD% | Corr | Mean PRD% | Mean Corr | Mean PRD% | Mean Corr | |

(215,215) | 51.97 | 0.8554 | 35.32 | 0.9680 | 23.82 | 0.9887 |

(113,113) | 40.48 | 0.9225 | 46.85 | 0.9689 | 14.55 | 0.9914 |

(104,104) | 34.48 | 0.9389 | 51.83 | 0.8734 | 20.51 | 0.9849 |

Fig. 12 shows the case of two plots of the same record with 1,000 samples of the time series rec.215 for X and 2000 samples of the same time series with a shift of 35 seconds for Y. Fig. 12(a) presents the original time series. The X signal has been taken at the beginning of the recording and the Y signal has been taken at the end of the recording to illustrate the phase shift problem. Fig. 12(b) shows the alignment performed by SEA. We see that SEA method fails in face of the problem of low frequency noise which is presented in the Y signal. Fig. 12(c) shows the alignment performed by QP-DTW. Fig. 12(d) presents the bad alignment done by DTW. We see that our method resolve efficiently the problems of phase shift and noise. The factors of similarity (Corr) and of dissimilarity (PRD) clearly indicate the superiority of our method in comparison with DTW and SEA. The correlation of QP-DTW is higher than those of DTW and SEA and its PRD is the lowest. It represents the half of the value of PRD of DTW.

Fig. 13 shows the case of two plots of the same record with 1,000 samples of the time series rec.104 and 2,000 samples of the same time series with a shift of 20 seconds for Y. Fig. 13(a) presents the original time series. Each series is composed of different number of periods which are phase shifted. The Y signal presents also the problem of noise. The alignment performed by the SEA method is presented in Fig. 13(b). We see that SEA fails facing the problems of different amplitude scales and phase shift. Fig. 13(c) presents the alignment done by QP-DTW. It shows that our method resolve all the problems previously cited. The alignment done by DTW is presented in Fig. 13(d). We see that DTW fails again facing the problems of phase shift and noise. The numerical results indicate a high correlation and a low PRD for QP-DTW, a very low correlation and a high PRD for SEA and an average PRD and correlation for DTW.

6.2 Comparison of Similar Traces of the PTB Diagnostic ECG DatabaseFig. 14 shows the case of two plots of the same record with 1,000 samples of the time series “s0287lrem” from the PTB Diagnostic ECG Database [ 18 ] for X and 1,200 samples of the same time series. The time series are phase shifted. The visual inspection and the numerical results indicate that the alignment done by QP-DTW is much better than the alignment done by SEA and DTW. Specifically, it can be noticed in this particular case that the SEA method deals weakly when we have one cycle in series X and two cycles in series Y, whereas the proposed QP-DTW deals much better with this complex case.

Fig. 15 shows the case of two plots of the same record with 2,000 samples of the time series “s0273lrem” from the PTB Diagnostic ECG Database for X and 3,000 samples of the same time series for Y. The visual inspection of the Fig. 15 shows that QP-DTW has done a good alignment, contrary to DTW which fails completely and to SEA which shows some weakness. In Table 3, the numerical results confirm this fact.

Table 3.

ECG segments | DTW | SEA | QP-DTW | |||

PRD% | Corr | Mean PRD% | Mean Corr | Mean PRD% | Mean Corr | |

(s0287, s0287) | 43.18 | 0.9052 | 83.20 | 0.6433 | 27.97 | 0.9716 |

(s0273, s0273) | 47.27 | 0.8825 | 60.10 | 0.8117 | 26.91 | 0.9673 |

Fig. 16 shows the case of two plots from two different records with 2,000 samples of the time series rec.103 for X and 2,000 samples of the time series rec.123 for Y and a shift of 40 seconds for Y. The visual inspection of the figure shows that the original time series and the reconstructed time series by QP-DTW are detached. The numerical results in Table 4 indicate a very low correlation and a very high PRD in favor of QP-DTW. This proves that our method is perfectly capable of differentiating dissimilar time series.

Table 4.

ECG segments | DTW | SEA | QP-DTW | |||

PRD% | Corr | Mean PRD% | Mean Corr | Mean PRD% | Mean Corr | |

(103, 123) | 57.24 | 0.8472 | 51.67 | 0.9673 | 69.01 | 0.8953 |

(100, 112) | 80.25 | 0.7034 | 62.58 | 0.8709 | 88.38 | 0.5866 |

Fig. 17 shows two plots from two different records with 1,000 samples of the time series rec.100 for X and 2,000 samples of the time series rec.112 for Y and a shift of 50 seconds for Y. The visual inspection and the numerical results indicate that QP-DTW done the best misalignment.

Figs. 18 and 19 show respectively the changes in the correlation and in the PRD of the three methods in relation to the size of time series. Fig. 18 indicates that the correlation of QP-DTW is the best and that it is always close to 1. Fig. 19 indicates that the PRD of QP-DTW is always the lowest despite increasing data size.

In this work, we have proposed a novel alignment method for quasi-periodic time series. The proposed QP-DTW can be seen as an upgrade of the classical DTW that handles alignment of very complex time series, more effectively than the existing SEA method, quantitatively and qualitatively. Therefore, the proposed method would be a good alternative for time series applications, such as data mining, pattern recognition, search/retrieval, motif discovery and classification.

She received her B.S. and M.S. degrees in Computer Science from the University of Skikda in 2009 and 2011, respectively. She is now a PhD student in the Department of Computer Science of the same university. Her fields of interest are Data mining, pattern recognition, diagnosis, Time series, Optimization.

He received the Doctor of Science (Ph.D.) and the HDR (post-doctoral degree for research supervision), respectively in 2005 and 2009, both in Computer Science from Mentouri University of Constantine, Algeria. He is a full professor of Computer Science at the Department of Informatics, University of Skikda, Algeria and a member of the LRES research laboratory within the same university. His main areas of interest and expertise include pattern recognition, computer vision, image processing and retrieval, time series and signals processing and retrieval, data reduction and compression. Prof. Boucheham authored/co-authored several papers in various high impact international journals and conferences and serves as reviewer for many international journals (https://publons.com/author/489776/bachir-boucheham#profile).

- 1 R. Agrawal, C. Faloutsos, A. Swami, "Efficient similarity search in sequence databases,"
*in Foundations of Data Organization and Algorithms. Heidelberg: Springer1993,*, pp. 69-84. doi:[[[10.1007/3-540-57301-1_5]]] - 2 A. Barbulescu, E. Bautu, "A hybrid approach for modeling financial time series,"
*The International Arab Journal of Information Technology, 2012*, vol. 9, no. 4, pp. 327-335. custom:[[[http://ccis2k.org/iajit/PDF/vol.9,no.4/2806-5.pdf]]] - 3 M. Awad, H. Pomares, I. R. Ruiz, O. Salameh, M. Hamdon, "Prediction of time series using RBF neural networks: a new approach of clustering,"
*The International Arab Journal of Information Technology, 2009*, vol. 6, no. 2, pp. 138-143. custom:[[[http://www.ccis2k.org/iajit/PDF/vol.6,no.2/5PTSURNNNAC138.pdf]]] - 4 M. Z. Arshad, J. M. Nawaz, S. J. Hong, "Fault detection in the semiconductor etch process using the seasonal autoregressive integrated moving average modeling,"
*Journal of Information Processing System, 2014*, vol. 10, no. 3, pp. 429-442. doi:[[[10.3745/JIPS.04.0004]]] - 5 L. Ulanova, T. Yan, H. Chen, G. Jiang, E. Keogh, K. Zhang, "Efficient long-term degradation profiling in time series for complex physical systems," in
*Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, Sydney, Australia, 2015;pp. 2167-2176. custom:[[[http://www.cs.ucr.edu/~eamonn/Aging_KDD2015_camera-ready.pdf]]] - 6 A. Vishwa, A. Sharma, "Arrhythmic ECG signal classification using machine learning techniques,"
*International Journal of Computer ScienceInformation Technology, Security, , 2011*, vol. 1, no. 2, pp. 163-167. custom:[[[-]]] - 7 K. Vimala, D. V. Kalaivani, "Classification of cardiac vascular disease from ECG signals for enhancing modern health care scenario,"
*Health Informatics-An International Journal (HIIJ), 2013*, vol. 2, no. 4, pp. 63-72. doi:[[[10.5121/hiij.2013.2405]]] - 8 E. J. D. S. Luz, W. R. Schwartz, G. Camara-Chavez, D. Menotti, "ECG-based heartbeat classification for arrhythmia detection: a survey,"
*Computer Methods and Programs in Biomedicine, 2016*, vol. 127, pp. 144-164. doi:[[[10.1016/j.cmpb.2015.12.008]]] - 9 B. Boucheham, "Matching of quasi-periodic time series patterns by exchange of block-sorting signatures,"
*Pattern Recognition Letters, 2008*, vol. 29, no. 4, pp. 501-514. doi:[[[10.1016/j.patrec.2007.11.004]]] - 10 B. Boucheham, "Abnormality detection in electrocardiograms by time series alignment,"
*Communications in Information Science and Management Engineering, 2011*, vol. 1, no. 3, pp. 6-10. custom:[[[http://www.academicpub.org/cisme/paperInfo.aspx?PaperID=13058]]] - 11 N. Begum, E. Keogh, "Rare time series motif discovery from unbounded streams," in
*Proceedings of the VLDB Endowment*, 2014;vol. 8, no. 2, pp. 149-160. doi:[[[10.14778/2735471.2735476]]] - 12 T. C. Fu, "A review on time series data mining,"
*Engineering Applications of Artificial Intelligence, 2011*, vol. 24, no. 1, pp. 164-181. doi:[[[10.1016/j.engappai.2010.09.007]]] - 13 H. Sakoe, S. Chiba, "Dynamic programming algorithm optimization for spoken word recognition,"
*IEEE Transactions on AcousticsSpeech, and Signal Processing, , 1978*, vol. 26, no. 1, pp. 43-49. doi:[[[10.1016/b978-0-08-051584-7.50016-4]]] - 14 B. Boucheham, "Efficient matching of very complex time series,"
*International Journal of Machine Learning and Cybernetics, 2013*, vol. 4, no. 5, pp. 537-550. doi:[[[10.1007/s13042-012-0117-5]]] - 15 E. Keogh, L. Wei, X. Xi, S. H. Lee, M. Vlachos, "LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures," in
*Proceedings of the 32nd International Conference on Very Large Data Bases*, Seoul, Korea, 2006;pp. 882-893. custom:[[[http://www.cs.ucr.edu/~eamonn/VLDB2006_Expanded.pdf]]] - 16 C. A. Ratanahatano, E. Keogh, "Three myths about dynamic time warping data mining," in
*Proceedings of the 2005 SIAM International Conference on Data Mining*, Newport Beach, CA, 2005;pp. 506-510. doi:[[[10.1137/1.9781611972757.50]]] - 17
*MIT-BIH Arrhythmia Database (Online). Available:*, http://www.physionet.org/physiobank/database/mitdb/ - 18 A. L. Goldberger, L. A. Amaral, L. Glass, J. M. Hausdorff, P. C. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C. K. Peng, H. E. Stanley, "PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals,"
*Circulation, 2000*, vol. 101, no. 23, pp. e215-e220. custom:[[[https://www.ncbi.nlm.nih.gov/pubmed/10851218]]] - 19 D. J. Berndt, J. Clifford, "Using dynamic time warping to find patterns in time series," in
*Proceedings of AAAI-94 Workshop on Knowledge Discovery Database (KDD)*, 1994;pp. 359-370. custom:[[[https://www.aaai.org/Papers/Workshops/1994/WS-94-03/WS94-03-031.pdf]]] - 20 E. J. Keogh, M. J. Pazzani, "Scaling up dynamic time warping for datamining applications," in
*Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, Boston, MA, 2000;pp. 285-289. doi:[[[10.1145/347090.347153]]] - 21 L. Chen, M. T. Ozsu, "Similarity-based retrieval of time-series data using multi-scale histograms,"
*University of WaterlooWaterloo, Canada, Technical Report No. CS-2003-31, 2003*. custom:[[[https://www.semanticscholar.org/paper/Similarity-based-Retrieval-of-Time-Series-Data-Chen-%C3%96zsu/f96a6e69d1ccbd30b59974ce1b03ac472197a723]]] - 22 H. Shatkay, S. B. Zdonik, "Approximate queries and representations for large data sequences," in
*Proceedings of the 12th International Conference on Data Engineering*, New Orleans, LA, 1996;pp. 536-545. doi:[[[10.1109/ICDE.1996.492204]]] - 23 T. Bozkaya, N. Yazdani, M. Ozsoyoglu, "Matching and indexing sequences of different lengths," in
*Proceedings of the 6th International Conference on Information and Knowledge Management*, Las Vegas, NV, 1997;pp. 128-135. doi:[[[10.1145/266714.266880]]] - 24 J. R. Annam, S. S. Mittapalli, R. S. Bapi, "Time series clustering and analysis of ECG heart-beats using dynamic time warping," in
*Proceedings of 2011 Annual IEEE India Conference (INDICON)*, Hyderabad, India, 2011;pp. 1-3. doi:[[[10.1109/INDCON.2011.6139394]]] - 25 N. Begum, L. Ulanova, J. Wang, E. Keogh, "Accelerating dynamic time warping clustering with a novel admissible pruning strategy," in
*Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, Sydney, Australia, 2015;pp. 49-58. doi:[[[10.1145/2783258.2783286]]] - 26 F. Petitjean, G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen, E. Keogh, "Dynamic time warping averaging of time series allows faster and more accurate classification," in
*Proceedings of 2014 IEEE International Conference on Data Mining (ICDM)*, Shenzhen, China, 2014;pp. 470-479. doi:[[[10.1109/ICDM.2014.27]]] - 27 G. Zhang, W. Kinsner, B. Huang, "Electrocardiogram data mining based on frame classification by dynamic time warping matching,"
*Computer Methods in Biomechanics and Biomedical Engineering, 2009*, vol. 12, no. 6, pp. 701-707. doi:[[[10.1080/10255840902882158]]] - 28 B. Boucheham, "Reduced data similarity-based matching for time series patterns alignment,"
*Pattern Recognition Letters, 2010*, vol. 31, no. 7, pp. 629-638. doi:[[[10.1016/j.patrec.2009.11.019]]] - 29 E. J. Keogh, M. J. Pazzani, "Derivative dynamic time warping," in
*Proceedings of the 2001 SIAM International Conference on Data Mining*, Chicago, IL, 2001;pp. 1-11. custom:[[[https://www.ics.uci.edu/~pazzani/Publications/sdm01.pdf]]] - 30 J. B. Kruskall, M. Liberman, "The symmetric time warping algorithm: from continuous to discrete,"
*in Time WarpsString Edits and Macromolecules. Reading, MA: Addison-Wesley, 1983*. custom:[[[-]]] - 31 I. Boulnemour, B. Boucheham, "I-SEA: improved shape exchange algorithm for quasi-periodic time series alignment," in
*Proceedings of 2015 International Conference on Computer Vision and Image Analysis Applications (ICCVIA)*, Sousse, Tunisia, 2015;pp. 1-6. doi:[[[10.1109/ICCVIA.2015.7351884]]] - 32 A. Bahri, Y., Naija, G. Jomier, M. Manouvrier, "Recherche par similarité de séquences temporelles dans les bases de données: un état de l'art,"
*LAMSADEUniversité Paris Dauphine, France, 2014*. custom:[[[-]]] - 33 L. Junkui, W. Yuanzhen, "Early abandon to accelerate exact dynamic time warping,"
*International Arab Journal of Information Technology, 2009*, vol. 6, no. 2, pp. 144-152. custom:[[[http://iajit.org/PDF/vol.6,no.2/6EAAEDTW144.pdf]]] - 34 S. Salvador, P. Chan, "Toward accurate dynamic time warping in linear time and space,"
*Intelligent Data Analysis, 2007*, vol. 11, no. 5, pp. 561-580. doi:[[[10.3233/ida-2007-11508]]]