Clustering matrix sequences based on the iterative dynamic time deformation procedure

Автор: Zhengbing Hu, Sergii V. Mashtalir, Oleksii K. Tyshchenko, Mykhailo I. Stolbovyi

Журнал: International Journal of Intelligent Systems and Applications @ijisa

Статья в выпуске: 7 vol.10, 2018 года.

Бесплатный доступ

The techniques of Dynamic Time Warping (DTW) have shown a great efficiency for clustering time series. On the other hand, it may lead to sufficiently high computational loads when it comes to processing long data sequences. For this reason, it may be appropriate to develop an iterative DTW procedure to be capable of shrinking time sequences. And later on, a clustering approach is proposed for the previously reduced data (by means of the iterative DTW). Experimental modeling tests were performed for proving its efficiency.

Time Series, Segmentation, Clustering, Video Stream, Proximity Measure, Dynamic Time Warping

Короткий адрес: https://sciup.org/15016509

IDR: 15016509   |   DOI: 10.5815/ijisa.2018.07.07

Список литературы Clustering matrix sequences based on the iterative dynamic time deformation procedure

  • D.P. Acharjya and V. Santhi, Bio-inspired computing for image and video processing. Boca Raton: CRC Press, 2018.
  • H. Zhang, “Content-Based Video Analysis. Retrieval and Browsing”, In: Feng D.D., Siu W.C., Zhang H.J. (eds) Multimedia Information Retrieval and Management. Signals and Communication Technology. Springer, Berlin, Heidelberg, pp. 27-56, 2003.
  • V.S. Wold Eide, F. Eliassen, O.-C. Granmo, and O. Lysne, “Supporting timeliness and accuracy in distributed real-time content-based video analysis”, Proc. of the eleventh ACM international conference on Multimedia, pp. 21-32, 2003.
  • B. Huurnink, C.G.M. Snoek, M. de Rijke, and A.W.M. Smeulders, “Content-Based Analysis Improves Audiovisual Archive Retrieval”, IEEE Transactions on Multimedia, vol. 14, no. 4, pp. 1166-1178, 2012.
  • R. Nisbet, G. Miner, and K. Yale, Handbook of Statistical Analysis and Data Mining Applications, Second Edition. Elsevier, 2018.
  • A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
  • L. Kaufman and P.J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis. N.Y.: John Wiley & Sons, Inc., 1990.
  • R. Xu and D. Wunsch, Clustering. Wiley-IEEE Press, 2008.
  • G. Gan, C. Ma, and J. Wu, Data Clustering: Theory, Algorithms, and Applications. Philadelphia: SIAM, 2007.
  • J. Abonyi and B. Feil, Cluster Analysis for Data Mining and System Identification. Basel: Birkhäuser, 2007.
  • C.C. Aggarwal and C.K. Reddy, Data Clustering: Algorithms and Applications. Boca Raton: CRC Press, 2014.
  • Zh. Hu, Ye.V. Bodyanskiy, O.K. Tyshchenko, “A deep cascade neuro-fuzzy system for high-dimensional online fuzzy clustering”,Proceedings of the 2016 IEEE 1st International Conference on Data Stream Mining and Processing (DSMP 2016), Lviv, Ukraine, pp. 318-322, 2016.
  • S. Babichev, V. Lytvynenko, M. Korobchynskyi, M. Taif, “Objective clustering inductive technology of gene expression sequences features”, Commun. Comput. Inf. Sci., No.716, pp.359-372, 2016.
  • Zh. Hu, Ye.V. Bodyanskiy, O.K. Tyshchenko, “A cascade deep neuro-fuzzy system for high-dimensional online possibilistic fuzzy clustering”, Proceedings of the 11th International Scientific and Technical Conference on Computer Sciences and Information Technologies, CSIT 2016, Lviv, Ukraine, pp. 119-122, 2016.
  • Ye.V. Bodyanskiy, O.K. Tyshchenko, D.S. Kopaliani, “An Evolving Connectionist System for Data Stream Fuzzy Clustering and Its Online Learning”, Neurocomputing, vol. 262, pp.41-56, 2017.
  • Ye.V. Bodyanskiy, A.K. Tyshchenko, A.A. Deineko, “An evolving radial basis neural network with adaptive learning of its parameters and architecture”, Automatic Control and Computer Sciences, vol. 49, iss. 5, pp. 255-260, 2015.
  • Zh. Hu, Ye.V. Bodyanskiy, O.K. Tyshchenko, O.O. Boiko, “A neuro-fuzzy Kohonen network for data stream possibilistic clustering and its online self-learning procedure”, Applied Soft Computing Journal, vol. 68, pp. 710-718, 2018.
  • S. Babichev, V. Lytvynenko, A. Gozhyj, M. Korobchynskyi, and M. Voronenko, “A Fuzzy Model for Gene Expression Profiles Reducing Based on the Complex Use of Statistical Criteria and Shannon Entropy”, In: Hu Z., Petoukhov S., Dychka I., He M. (eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing. Springer, Cham, vol.754, pp.545-554, 2019. DOI: https://doi.org/10.1007/978-3-319-91008-6_55.
  • J. Abonyi, B. Feil, S. Nemett, and P. Arva, “Fuzzy Clustering Based Segmentation of Time-Series”, Advances in Intelligent Data Analysis V (IDA 2003). Lecture Notes in Computer Science, vol. 2810, pp. 275–285, 2003.
  • T.W. Liao, “Clustering of time series data”, Pattern Recognition, vol.38, no.11, pp. 1857-1874, 2005.
  • J. Han and M. Kamber, Data Mining: Concepts and Techniques. San Francisco: Morgan Kaufmann, 2006.
  • D.L. Olson and D. Dursun, Advanced Data Mining Techniques. Berlin: Springer, 2008.
  • C.C. Aggarwal, Data Mining. Cham: Springer, Int. Publ. Switzerland, 2015.
  • M.M. Deza and E. Deza, Encyclopedia of Distances. Dordrecht, Heidelberg, London, New York: Springer, 2009.
  • X. Wang, A. Mueen, H. Ding, G. Trajcevski, P. Scheuermann, and E. Keogh, “Experimental comparison of representation methods and distance measures for time series data”, Data Mining and Knowledge Discovery, vol.26, no.2, pp. 275–309, 2013.
  • P.A. Jaskowiak, R.J. Campello, and I.G. Costa, “Proximity measures for clustering gene expression microarray data: a validation methodology and a comparative analysis”, IEEE/ACM Trans Comput Biol Bioinform., vol.10, no.4, pp. 845-857, 2013.
  • D. Kinoshenko, V. Mashtalir, and V. Shlyakhov, “A partition metric for clustering features analysis”, International Journal “Information Theories and Applications”, vol.14, iss.3, pp.230-236, 2007.
  • S. Chu, E. Keogh, D. Hart, and M. Pazzani, “Iterative Deepening Dynamic Time Warping for Time Series”, Proc. 2nd SIAM International Conference on Data Mining (SDM-02), 2002.
  • N. Begum, L. Ulanova, J. Wang, and E. Keogh, “Accelerating dynamic time Warping Clustering with a Novel Admissible Pruning Strategy”, Proc. of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 49-58, 2015.
  • S. Salvador and P. Chan, “FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space”, KDD Workshop on Mining Temporal and Sequential Data, pp. 70–80, 2004.
  • R.J. Kate, “Using dynamic time warping distances as features for improved time series classification”, Data Mining and Knowledge Discovery, pp. 1-30, 2015.
  • D.F. Silva and E.A.P.A.B. Batista, “Speeding up all-pairwise dynamic time warping matrix calculation”, http://sites.labic.icmc.usp.br/prunedDTW/, 2015.
  • D.J. Berndt and S. Clifford, “Using Dynamic Time Warping to Find Patterns in Time Series”, Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining (AAAIWS'94), pp.359-370, 1994.
  • E.J. Keogh and M.J. Pazzani, “Scaling up Dynamic Time Warping for Datamining Applications”, Proc. of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 285-289, 2000.
  • E.J. Keogh and M.J. Pazzani, “Derivative Dynamic Time Warping”, Proc. of the First SIAM International Conference on Data Mining (SDM'2001), 2001.
  • T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh, “Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping”, Proc. of the 18th ACM SIGKDD International Conference on Knowledge discovery and data mining (KDD’12), pp. 262-270, 2012.
  • S. Mashtalir, V. Mashtalir, and M. Stolbovyi, “Video Shot Boundary Detection Via Sequential Clustering”, International Journal “Information Theories and Applications”, Vol.24, No.1, pp.50-59, 2017.
  • C. Faloutsos, M. Ranganathan, and Y. Manolopoulos, “Fast subsequence matching in time-series databases”, Proc. ACM SIGMOD International Conference on Management of Data, 1994.
  • Zh. Hu, S.V. Mashtalir, O.K. Tyshchenko, M.I. Stolbovyi, “Video Shots’ Matching via Various Length of Multidimensional Time Sequences”, International Journal of Intelligent Systems and Applications (IJISA), Vol.9, No.11, pp.10-16, 2017.
  • I.V. Nikiforov, “Sequential Detection of Changes in Stochastic Process”, IFAC Proceedings Volumes, vol.25, iss.15, pp.11-19, 1992.
  • B. Zhang, M. Hsu, and U. Dayal, “K-Harmonic Means -A Spatial Clustering Algorithm with Boosting”, In: Roddick J.F., Hornsby K. (eds) Temporal, Spatial, and Spatio-Temporal Data Mining. Lecture Notes in Computer Science, vol. 2007, pp.31-45, 2001.
  • W.-C. Yeh, Y. Jiang, Y.-F. Chen, and Z. Chen, “Correction: A New Soft Computing Method for K-Harmonic Means Clustering”, PLoS ONE 12(1), 2017. https://doi.org/10.1371/journal.pone.0169707.
  • N. Chinchor, “MUC-4 Evaluation Metrics”, Proc. of the Fourth Message Understanding Conference, pp. 22–29, 1992.
Еще
Статья научная