MULTIDIMENSIONAL SEQUENCE CLUSTERING WITH ADAPTIVE ITERATIVE DYNAMIC TIME WARPING

Authors

  • Sergii Mashtalir
  • Olena Mikhnova
  • Mykhailo Stolbovyi

DOI:

https://doi.org/10.47839/ijc.18.1.1273

Keywords:

segmentation, clustering, multidimensional sequence, video processing, adaptive iterative dynamic time warping, Kohonen self-organizing map.

Abstract

Multimedia sequence matching is an urgent problem nowadays for the field of artificial intelligence. Despite great progress in this field of computer science, huge data arrays require near to real time processing, which significantly limits applicable methods. In this paper, the authors make an attempt of time series approach modification and enhancement with orientation for non-stationary data of different length. The processing procedure is enriched by sequences alignment with iterative dynamic time warping which implies matching two temporal data segments. Computational complexity is reduced due to Kohonen self-organizing maps applied for the purpose of clustering. Mathematical presentation is given in scalar, vector and matrix forms in order to cover all the possible use cases. An example of video sequence processing with the novel approach is provided to show its efficiency. The proposed technique can also be successfully implemented for natural language and signal processing, bioinformatics and financial data analysis.

References

H. Chen, D. Chen, S. Lee, “Object based video similarity retrieval and its application to detecting anchorperson shots in news video,” Proceedings of the IEEE Fifth International Symposium on Multimedia Software Engineering, Taichung, Taiwan, December 10-12, 2003, pp. 172-179.

M. Tang, S. Pongpaichet, R. Jain, “Research challenges in developing multimedia systems for managing emergency situations,” Proceedings of the 2016 ACM Conference on Multimedia, Amsterdam, the Netherlands, October 15-19, 2016, pp. 938-947.

D. Reynolds, R.A. Messner, “Video copy detection utilizing the log-polar transformation,” International Journal of Computing, vol. 15, issue 1, pp. 8-13, 2016.

N.I. Korsunov, D.A. Toropchin, “The method of finding the spam images based on the hash of the key points of the image,” International Journal of Computing, vol. 15, issue 4, pp. 259-264, 2016.

A. Valente et. al. “When does picture naming take longer than word reading?,” in: S. Sulpizio, S. Kinoshita (Eds.), Bridging Reading Aloud and Speech Production, vol. 7, article 31, Frontiers, Lausanne, 2016, pp. 83-93.

D. Jurafsky, J.H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, 2-nd edition, Prentice Hall, New Jersey, 2008, 1032 p.

T. Tsai and S. Lee, “SimSearcher: A local similarity search engine for biological sequence databases,” Proceedings of the IEEE Fifth International Symposium on Multimedia Software Engineering, Taichung, Taiwan, December 10-12, 2003, pp. 305-312.

T.W. Liao, “Clustering of time series data,” Pattern Recognition, vol. 38, issue 11, pp. 1857-1874, 2005.

E.I. Keogh, S. Chu, D. Hart, M. Pazzani, “Segmenting time series: A survey and novel approach,” in: M. Last, A. Kandel, H. Bunke (Eds.), Data mining in time series databases, World Scientific Publ. Company, New Jersey, 2004, pp. 1-22.

C.C. Aggarwal, Data Mining: The Textbook, Springer, New York, 2015, 734 p.

C.C. Aggarwal, C.K. Reddy, Data Clustering: Algorithms and Applications, CRC Press, Boca Raton, 2014, 652 p.

S. Mashtalir, O. Mikhnova, “Detecting significant changes in image sequences,” in: A.E. Hassanien et. al. (Eds.), Multimedia Forensics and Security, Springer, Basel, 2017, pp. 161-191.

Zh. Hu, S.V. Mashtalir, O.K. Tyshchenko, M.I. Stolbovyi, “Clustering matrix sequences based on the iterative dynamic time deformation procedure”, International Journal of Intelligent Systems and Applications, vol. 10, no. 7, pp. 66-73, 2018.

J. Han, M. Kamber, J. Pei, Data Mining: Concepts and Techniques, 3-rd edition, Elsevier, Amsterdam, 2013, 703 p.

F. Iglesias, W. Kastner, “Analysis of similarity measures in times series clustering for the discovery of building energy patterns,” Energies, vol. 6, pp. 579-597, 2013.

C. Cassisi, P. Montalto, M.A. Aliotta, A. Pulvirenti, “Similarity measures and dimensionality reduction techniques for time series data mining,” in: A. Karahoca (Ed.), Advances in Data Mining Knowledge Discovery and Applications, Chapter 3, IntechOpen, London, 2012, pp. 71-96.

D. Berndt, J. Clifford, “Using dynamic time warping to find patterns in time series,” Workshop on KDD, vol. 10, no. 16, Seattle, USA, July 31 - August 01, 1994, pp. 359-370.

M. Müller, Information Retrieval for Music and Motion, Springer-Verlag, Berlin, 2007, 318 p.

N. Begum, L. Ulanova, J. Wang, E. Keogh, “Accelerating dynamic time warping clustering with a novel admissible pruning strategy”, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia, August 10-13, 2015, pp. 49-58.

S. Chu, E.I. Keogh, D. Hart, M. Pazzani, “Iterative deepening dynamic time warping for time series”, Proceedings of the 2-nd SIAM International Conference on Data Mining, Arlington, USA, April 11-13, 2002. pp. 195-212.

A. Zinke, D. Mayer, Iterative Multi Scale Dynamic Time Warping, Universität Bonn, Technical Report CG-2006-1, 2006, 11 p.

T. Kohonen, Self-Organizing Maps, Springer-Verlag, Berlin, 1995, 364 p.

T. Kohonen, “Essentials of the self-organizing map,” Neural Networks, vol. 37, Elsevier, pp. 52-65, 2013.

Downloads

Published

2019-03-31

How to Cite

Mashtalir, S., Mikhnova, O., & Stolbovyi, M. (2019). MULTIDIMENSIONAL SEQUENCE CLUSTERING WITH ADAPTIVE ITERATIVE DYNAMIC TIME WARPING. International Journal of Computing, 18(1), 53-59. https://doi.org/10.47839/ijc.18.1.1273

Issue

Section

Articles