Distance measures-based information technology for identifying similar data series
| Назва | Distance measures-based information technology for identifying similar data series |
| Назва англійською | Distance measures-based information technology for identifying similar data series |
| Автори | Anastasiia Baturinets |
| Принадлежність | Oles Honchar Dnipro National University, Dnipro, Ukraine |
| Бібліографічний опис | Distance measures-based information technology for identifying similar data series / Anastasiia Baturinets // Scientific Journal of TNTU. — Tern.: TNTU, 2022. — Vol 105. — No 1. — P. 128–140. |
| Bibliographic description: | Baturinets A. (2022) Distance measures-based information technology for identifying similar data series. Scientific Journal of TNTU (Tern.), vol 105, no 1, pp. 128–140. |
| DOI: | https://doi.org/10.33108/visnyk_tntu2022.01.128 |
| УДК | 004.67:519.25 |
| Ключові слова | distance measures, similarity of numerical series, LCS, DTW, TSD, similarity of data series, hydrology. |
The aim of the work is to develop and implement a technology for identifying similar series, and to test on series of data represented by hydrological samples. The subject of the study is the methods and approaches for identifying similar series. The object of the study is the process of identifying similar series, which are represented by certain indicators. The task is to propose and implement distance measures, where one of them takes into consideration the similarity between the values of the series and their relationship, and another is based on a weighted Euclidean distance taking into account the need to actualize the values that are the most important under certain conditions of the task; to implement a technology to find similar series represented by certain indicators values; to obtain a more resilient solution, to implement a procedure for determining a set of similar series based on the results obtained for each individual distance; the results should be analyzed and the conclusions have to be drawn dealing with practical application of the technology. The following methods were used: statistical analysis methods, methods for calculating distances, and similarity between data series. The following results were obtained: the technology for similar data series detection has been implemented; two distance measures were proposed and described as a part of the technology implemented; a procedure for determining a set of similar rows was implemented that was based on the obtained distances calculation. The scientific novelty of the research under discussion involves: Euclidean weighted distance was described and applied taking into account the actuality of data series values; a new measure of distance has been described and applied that allows both the degree of similarity between the values of the series and their correlation to be taken into account, as well as a technique has been developed for determining similar series from a set of selected distance measures. The practical importance of the developed and implemented technology consists in the following possibilities application to data series of different applied fields: conducting an assessment and identifying some similar series, in particular as an intermediate step in the analysis; in addition, the proposed distance measures improve the quality of identifying similar data series. In our further research, we plan to investigate the possibilities of lengthening the data series and filling in the gaps with values from other series defined as similar ones. | |
| ISSN: | 2522-4433 |
| Перелік літератури |
1. Liao T. W., Clustering of time series data – A survey, Pattern Recognit. Vol. 38. No. 11. Nov. 2005. P. 1857–1874.
2. Saxena A., et. al. A review of clustering techniques and developments. Neurocomputing, 267, 2017. P. 664-681. URL: https://doi.org/10.1016/j.neucom.2017.06.053.
3. Zhu X., Li Y., Wang J., Zheng T., Fu J. Automatic Recommendation of a Distance Measure for Clustering Algorithms. ACM Transactions on Knowledge Discovery from Data (TKDD), 15 (1). 2020. P. 1–22. Doi:10.1007/978-81-322-1665-0_17.
4. Savchuk T. O. Viznachennya evklidovoyi vidstani mizh nadzvichaynimi situatsiyami na zaliznichnomu transporti pid chas klasternogo analizu, Naukovi pratsi Vinnitskogo natsionalnogo tehnichnogo universitetu. – Seriya “Informatsiyni tehnologiyi ta komp’yuterna tehnika”. 2010. No. 3. 2010.
5. Keogh E. J., Pazzani M. J. Derivative dynamic time warping. In Proceedings of the 2001 SIAM international conference on data mining. Society for Industrial and Applied Mathematics. 2001. April. P. 1–11.
6. Dau H. A., Silva D. F., Petitjean F. et al. Optimizing dynamic time warping’s window width for time series data mining applications. Data Mining and Knowledge Discovery 32. 2018. P. 1074–1120. URL: https://doi.org/10.1007/s10618-018-0565-y.
7. Raida V., Svoboda P., Rupp M. Modified dynamic time warping with a reference path for alignment of repeated drive-tests. In 2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall) IEEE. 2020. P. 1–6. Doi:10.1109/VTC2020-Fall49728.2020.9348487.
8. Senin P. Dynamic time warping algorithm review. Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 2008, 23 p.
9. Kate R. J. Using dynamic time warping distances as features for improved time series classification. Data Mining and Knowledge Discovery, 30 (2). 2016. P. 283–312. Doi:10.1007/s10618-015-0418-x.
10. Hu Z., Mashtalir S. V., Tyshchenko O. K., Stolbovyi M. I. Clustering matrix sequences based on the iterative dynamic time deformation procedure. International Journal of Intelligent Systems and Applications,10 (7). 2018. P. 66–73. Doi:10.5815/ijisa.2018.07.07.
11. Hunt J.W., Szymanski T. G. A fast algorithm for computing longest common subsequences. Communications of the ACM. Vol. 20. No. 5. 1977. P. 350–353.
12. Hirschberg, Daniel S. Algorithms for the longest common subsequence problem. Journal of the ACM (JACM) 24.4. 1977. P. 664–675.
13. Wan, Qingguo, et al. A fast heuristic search algorithm for finding the longest common subsequence of multiple strings. Twenty-Fourth AAAI Conference on Artificial Intelligence. 2010. P. 1287–1292.
14. Wang Q., Dmitry K., Shang Y. Efficient dominant point algorithms for the multiple longest common subsequence (MLCS) problem. Twenty-First International Joint Conference on Artificial Intelligence. 2009. P.1494–1499.
15. Korkin D., Wang Q. Shang Y. An efficient parallel algorithm for the multiple longest common subsequence (MLCS) problem. 37th International Conference on Parallel Processing. IEEE, 2008. P. 354–363.
16. Wang X., Mueen A., Ding H., Trajcevski G., Scheuermann P., Keogh E. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 26 (2). 2013. P. 275–309. Doi: 10.1007/s10618-012-0250-5.
17. Hryhorovych V. Analiz metryk dlia intelektualnykh informatsiinykh system, Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Informatsiini systemy ta merezhi”. 2021. 9. P. 96–111. URL: https:// doi.org/10.23939/sisn2021.09.096
18. Baturinets А., Antonenko S. Longest common subsewuence in the problem of determining the similarity of hydrological data series, Deutsche Internationale Zeitschrift für zeitgenössische Wissenschaft. 2021. No. 18. P. 62–64.
|
| References: |
1. Liao T. W., Clustering of time series data – A survey, Pattern Recognit. Vol. 38. No. 11. Nov. 2005. P. 1857–1874.
2. Saxena A., et. al. A review of clustering techniques and developments. Neurocomputing, 267, 2017. P. 664-681. URL: https://doi.org/10.1016/j.neucom.2017.06.053.
3. Zhu X., Li Y., Wang J., Zheng T., Fu J. Automatic Recommendation of a Distance Measure for Clustering Algorithms. ACM Transactions on Knowledge Discovery from Data (TKDD), 15 (1). 2020. P. 1–22. Doi:10.1007/978-81-322-1665-0_17.
4. Savchuk T. O. Viznachennya evklidovoyi vidstani mizh nadzvichaynimi situatsiyami na zaliznichnomu transporti pid chas klasternogo analizu, Naukovi pratsi Vinnitskogo natsionalnogo tehnichnogo universitetu. – Seriya “Informatsiyni tehnologiyi ta komp’yuterna tehnika”. 2010. No. 3. 2010.
5. Keogh E. J., Pazzani M. J. Derivative dynamic time warping. In Proceedings of the 2001 SIAM international conference on data mining. Society for Industrial and Applied Mathematics. 2001. April. P. 1–11.
6. Dau H. A., Silva D. F., Petitjean F. et al. Optimizing dynamic time warping’s window width for time series data mining applications. Data Mining and Knowledge Discovery 32. 2018. P. 1074–1120. URL: https://doi.org/10.1007/s10618-018-0565-y.
7. Raida V., Svoboda P., Rupp M. Modified dynamic time warping with a reference path for alignment of repeated drive-tests. In 2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall) IEEE. 2020. P. 1–6. Doi:10.1109/VTC2020-Fall49728.2020.9348487.
8. Senin P. Dynamic time warping algorithm review. Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 2008, 23 p.
9. Kate R. J. Using dynamic time warping distances as features for improved time series classification. Data Mining and Knowledge Discovery, 30 (2). 2016. P. 283–312. Doi:10.1007/s10618-015-0418-x.
10. Hu Z., Mashtalir S. V., Tyshchenko O. K., Stolbovyi M. I. Clustering matrix sequences based on the iterative dynamic time deformation procedure. International Journal of Intelligent Systems and Applications,10 (7). 2018. P. 66–73. Doi:10.5815/ijisa.2018.07.07.
11. Hunt J.W., Szymanski T. G. A fast algorithm for computing longest common subsequences. Communications of the ACM. Vol. 20. No. 5. 1977. P. 350–353.
12. Hirschberg, Daniel S. Algorithms for the longest common subsequence problem. Journal of the ACM (JACM) 24.4. 1977. P. 664–675.
13. Wan, Qingguo, et al. A fast heuristic search algorithm for finding the longest common subsequence of multiple strings. Twenty-Fourth AAAI Conference on Artificial Intelligence. 2010. P. 1287–1292.
14. Wang Q., Dmitry K., Shang Y. Efficient dominant point algorithms for the multiple longest common subsequence (MLCS) problem. Twenty-First International Joint Conference on Artificial Intelligence. 2009. P.1494–1499.
15. Korkin D., Wang Q. Shang Y. An efficient parallel algorithm for the multiple longest common subsequence (MLCS) problem. 37th International Conference on Parallel Processing. IEEE, 2008. P. 354–363.
16. Wang X., Mueen A., Ding H., Trajcevski G., Scheuermann P., Keogh E. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 26 (2). 2013. P. 275–309. Doi: 10.1007/s10618-012-0250-5.
17. Hryhorovych V. Analiz metryk dlia intelektualnykh informatsiinykh system, Visnyk Natsionalnoho universytetu “Lvivska politekhnika” “Informatsiini systemy ta merezhi”. 2021. 9. P. 96–111. URL: https:// doi.org/10.23939/sisn2021.09.096
18. Baturinets А., Antonenko S. Longest common subsewuence in the problem of determining the similarity of hydrological data series, Deutsche Internationale Zeitschrift für zeitgenössische Wissenschaft. 2021. No. 18. P. 62–64.
|
| Завантажити |  |