On Enhancing the Accuracy of Nearest Neighbour Time Series Classifier Using Improved Shape Exchange Algorithm

Abstract

Several methods have been proposed for time series alignment and classification. In particular our previously published method I-SEA (Improved Shape Exchange Algorithm) has been proposed as a rival method to the SEA (Shape Exchange Algorithm) method for time series alignment. The aim of this work is to improve the accuracy of the SEA method for time series classification by proposing a 1NN-ISEA (1 Nearest Neighbor-Improved Shape Exchange Algorithm) classifier. Results of the proposed method show to be better as compared to those of the 1NN-SEA and the 1NN-ED classifiers (Euclidian Distance). All results have been obtained using the UCR (University of California at Riverside) time series Dataset, universally admitted as the first Benchmark in time series classification and clustering.

Keywords

• KNN
• SEA
• ISEA
• ED
• DTW
• Time Series

References

1. [Alkasassbeh 2015] Alkasassbeh, M., Altarawneh,G., Hassanat, A.B.: “On enhancing the performance of nearest neighbourclassifers using Hassanat distance metric”, Cana-dian Journal of Pure and Applied Sciences, 9 (1), pp 3291-3298 (2015).
2. [Amr, 2012] Amr, T.: “Survey on time-series data classification”, In TSDM journal (2012).
3. [Bagnall, 2015] A. Bagnall, J. Lines, J. Hills, and A. Bostrom,“Time-series classification-with cote: the collective of transformation-based ensembles”. IEEETransactions on Knowledge and Data Engineering, vol. 27, No.9, pp. 2522–2535, 2015.
4. [Berndt, 1994] Berndt, D. J., Clifford, J.: “Using dynamic time warping to find patterns in time series”, In AAI Workshop on Knowledge Discovery in Databases (KDD’94), pp. 359-370, Seattle, Washington (1994).
5. [Boucheham, 2008] Boucheham, B.: “Matching of quasi-periodic time series patterns by exchange of block-sorting signatures”. Pattern Recognition Letters (Elsevier). Vol. 29, pp. 501–514 (2008).
6. [Boucheham, 2011] Boucheham, B.: “Abnormality Detection in Electrocardiograms by Time Series Alignment”, Communications in Information Science and Management Engi-neering (CISME), Vol.1 No.3, pp. 7-11 (2011).
7. [Boucheham, 2013] Boucheham, B.: “Efficient matching of very complex time series”. In International Journal of Machine Learning and Cybernetics, Springer, Vol. 4, Issue 5, pp. 537-550 (2013).
8. [Boulnemour, 2015] Boulnemour, I., Boucheham, B.: “I-SEA: Improved shape exchange algorithm for quasi-periodic time series alignment”, In IEEE International Conference on Computer Vision and Image Analysis Applications (ICCVIA), Sousse, Tunisia, pp. 1-6 (2015).

9. [Boulnemour, 2016] Boulnemour, I., Boucheham, B., Benloucif, S.: “Improved dynamic time warping for abnormality detection in ECG time series,” In F. Ortuño and I. Rojas, Eds., Bioinformatics and Biomedical Engineering: 4th International Conference, IWBBIO 2016, Granada, Spain, April 20-22. 2016, Proceedings, Cham: Springer International Pub-lishing AG, pp. 242-253 (2016).
10. [Boulnemour, 2018] Boulnemour, I., Boucheham, B., “QP-DTW: upgrading dynamic time warping to handle quasi-periodic time series alignment”, Journal of Information Pro-cessing Systems, vol. 14, n°4, pp. 851-876 (2018).
11. [Chen, 2015] Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., Batista, G.: “The UCR time series classification archive” (2015), www.cs.ucr.edu/∼eamonn/time_series_data/.10
12. [Ding, 2008] Ding, H., Trajcevski, G., Scheuermann, P., Wang, X., Keogh, E “Querying and mining of time series data: experimental comparison of representations and distance measure”, In Proceedings of the VLDB Endowment, vol.1, n°2, pp. 1542–1552 (2008).
13. [Huerta, 2012] Huerta, R., Vembu, S., Muezzinoglu, M.K., Vergara, A.: “Dynamical SVM for Time Series Classification”, Pattern Recognition. DAGM/OAGM. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, vol. 7476, pp. 216-225, (2012).
14. [Graves, 2013] Graves, A., Mohamed, A., Hinton, G.: “Speech recognition with deep re-current neural networks”, In Proceedings of the IEEE International Conference on Acous-tics, Speech and Signal Processing (2013).
15. [Liu, 2019] Liu, C. L., Hsaio, W. H., Tu, Y. C.: “Time Series Classification With Multi-variate Convolutional Neural Network”, In Proceedings of the IEEE Transactions on In-dustrial Electronics, vol. 66, n° 6 (2019).
16. [Nguyen, 2017] Nguyen, T.L., Gsponer, S, Ifrim, G.: “Time series classification by se-quence learning in all-subsequence space”, In Proceedings of the 33th International Con-ference on Data Engineering, pp. 947–958. IEEE Press, San Diego (2017).
17. [Owsley, 1997] Owsley, L., Atlas, L., Bernard, G.: “Self-organizing feature maps and hid-den markov models for machine-tool monitoring”, In IEEE Transactions on Signal Pro-cessing vol. 45, n°11, pp. 2787–2798 (1997).
18. [Prasatha, 2017] Prasatha, V. B. S., Abu Alfeilat, H.A., Lasassmeh, O., Hassanat, A. B. A.: “Distance and Similarity Measures Effect on the Performance of K-Nearest Neighbor Classifier-A Review”, Journal Elsevier (2017).
19. [Sakoe, 1978] Sakoe, H, Chiba, S.: “Dynamic programming algorithm optimization for spoken word recognition”, In proceedings of the IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 26, n°1, pp. 43-49 (1978).
20. [Serfass , 2017] Serfass, D.: “Dynamic Biometric Recognition of Handwritten Digits Us-ing Symbolic Aggregate Approximation”, In Proceedings of the ACM SE'17, South East Conference, pp. 1-4 (2017).
21. [Schäfer, 2015] P. Schäfer, “The boss is concerned with time series classification in the presence of noise”, Data Mining and Knowledge Discovery, vol. 29, n° 6, pp. 1505–1530, 2015.
22. [Liao, 2005] T. W. Liao,“Clustering of time series data - a survey”, Pattern Recognition, vol. 38, n°11, pp. 1857-1874, 2005.
23. [Lines, 2016] J. Lines, S. Taylor, A. Bagnall, “HIVE-COTE: The Hierarchical Vote Col-lective of Transformation-based Ensembles for Time Series Classification”, In proceedings of the IEEE 16th International Conference on Data Mining (ICDM), 2016.
24. [Ravinder, 2010] K .Ravinder, “Comparison of hmm and dtw for isolated word recognition system of punjabi language”, Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, pp. 244–252, 2010.
25. [Smith, 2009] Smith, A.A.: “Classification and Alignment of Gene-Expression Time-Series Data”, Thèse de doctorat, Université de Wisconsin–Madison (2009).
26. [Singha, 2018] Singha, S., Pandey, S. K., Pawar, U., Janghel, R. R.: “Classification of ECG Arrhythmia using Recurrent Neural Networks”, In Proceedings Computer Science, ELsevier, vol. 132, pp. 1290-1297 (2018).
27. [Wettschereck, 1997] Wettschereck, D., Aha, D.W., Mohri, T./ “A review and empirical evaluation of feature weighting methods for a class of lazy learning algorithms”, Artificial Intelligence Review, Springer, vol. 11, issue 1-5, pp. 273-314 (1997).
28. [Ziat, 2017] Ziat, A.Y. : “Apprentissage de représentation pour la prédiction et la classifi-cation de séries temporelles”, Thèse de Doctorat en Réseau de neurones, Université Pierre et Marie Curie - Paris VI (2017).