ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА РЕЗЮМИРУЮЩИХ ШАБЛОНОВ ВРЕМЕННОГО РЯДА НА ОСНОВЕ КОНЦЕПЦИИ КАНОНИЧЕСКИХ ПРИЗНАКОВ

В статье представлен новый параллельный алгоритм поиска резюмирующих шаблонов временного ряда PDSS (Parallel Discovery of Semantic Snippets) на основе концепции канонических признаков САТСН22 (CAnonical Time-series CHaracteristics). Резюмирующие шаблоны набор подпоследовательностей (непрерывных промежутков) временного ряда, которые отражают виды деятельности рассматриваемого объекта и позволяют выполнить разметку временного ряда. Разработанный алгоритм поиска резюмирующих шаблонов предполагает четыре этана: вычисление профилей признаков подпоследовательностей временного ряда, нормализацию признаков, вычисление матрицы расстояний и поиск шаблонов. PDSS позволяет выполнять поиск резюмирующих шаблонов и разметку временных рядов из различных предметных областей, в том числе для многомерных временных рядов. Результаты экспериментов показывают, что предложенный алгоритм в среднем опережает передовые аналоги на порядок и выполняет разметку в среднем на 33 % точнее (но мере F1).

Список литературы

1.  Volkov I., Radchenko G., Tchernvkh A. Digital Twins, Internet of Things and Mobile Medicine: A Review of Current Platforms to Support Smart Healthcare // Programming and Computer Software 2021. Vol. 47, N 8. P. 578-590. DOI: http://dx.doi.org/10.1134/ S036176882108028410.1134/S0361768821080284.
2.  Liu Y. Scalable Multivariate Time-Series Models for Climate Informatics // Computing in Science к Engineering. 2015. Vol. 17, N 6. P. 19-26. DOI: http://dx.doi.org/10.1109/MCSE.2015. 12610.1109/MCSE.2015.126.
3.  Arruda H. М., Bavaresco R. S., Kunst R. et.al. Data Science Methods and Tools for Industry 4.0: A Systematic Literature Review and Taxonomy //Sensors. 2023. Vol. 23, N 11. P. 5010. DOI: http://dx.doi.org/10.3390/S2311501010.3390/S23115010.
4.  Kumar S., Tiwari P., Zvmbler M. Internet of Things is a revolutionary approach for future technology enhancement: a review // Journal of Big Data. 2019. Vol. 6, N 1. DOI: http://dx.doi. org/10.1186/s40537-019-0268-210.1186/s40537-019-0268-2.
5.  Imani S., Madrid F., Ding W., Crouter S., and Keogh E. Matrix Profile XIII: Time Series Snippets: A New Primitive for Time Series Data Mining // 2018 IEEE International Conference on Big Knowledge, ICBK 2018. Nov. 17-18, 2018, Singapore. P. 382-389. DOI: http://dx.doi.org/10. 1109/ICBK. 2018.0005810.1109/ICBK.2018.00058.
6.  Gharghabi S., Imani S., Bagnall A., Darvishzadeh A., and Keogh E. An ultra-fast time series distance measure to allow data mining in more complex real-world deployments // Data Mining and Knowledge Discovery. 2020. Vol. 34, N 4. P. 1104-1135. DOI: http://dx.doi.org/10.1007/sl0618-020-00695-810.1007/sl0618-020-00695-8.
7.  Lubba С. H., Sethi S. S., Knaute P. et. al. catch22: CAnonical Time-series CHaracteristics: Selected through highly comparative time-series analysis // Data Mining and Knowledge Discovery. 2019. Vol. 33, N 6. P. 1821-1852. DOI: http://dx.doi.org/10.1007/sl0618-019-00647- xl0.1007/sl0618-019-00647-x.
8.  Mueen A., Keogh E., Zhu Q., Cash S., and Westover B. Exact Discovery of Time Series Motifs// Proceedings of the 2009 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics. SDM 2009. Apr. 30-Mav 2, 2009, Sparks, Nevada, USA. DOI: http://dx.doi. org/10.1137/1.9781611972795.4110.1137/1.9781611972795.41.
9.  Zvmbler M. L., Kraeva Y. A. Discovery of Time Series Motifs on Intel Manv-Core Systems // Lobachevskii Journal of Mathematics. 2019. Vol. 40, N 12. P. 2124-2132. DOI: http://dx.doi.org/ 10.1134/S199508021912014X10.1134/S199508021912014X.
10.  Narang A., Bhattacherjee S. Parallel Exact Time Series Motif Discovery // Euro-Par 2010 - Parallel Processing. Springer Berlin Heidelberg, 2010. Aug. 31-Sep. 3, 2010, Ischia, Italy. P. 304-315. DOI: http://dx.doi.org/10.1007/978-3-642-15291-7_2810.1007/978-3-642-15291-7l28.
11.  Цымблер М.Л., Краева Я. А. Параллельный алгоритм поиска лейтмотивов временного ряда для графического процессора // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2020. Т. 9, Vs 3. DOI: http: //dx.doi .org/10.14529/cmse20030210.14529/cmse200302.
12.  Ye L., Keogh E. https://doi.org/10.1145/1557019.1557122Time series shapelets: a new primitive for data mining // Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. KDD09. June 28-Julv 1, 2009, Paris, France. P. 947-956. DOI: http://dx.doi.org/10.1145/1557019.155712210.1145/1557019.1557122.
13.  Indvk P., Koudas N., Muthukrishnan S. Identifying Representative Trends in Massive Time Series Data Sets Using Sketches // Proceedings of the 26th International Conference on Very Large Data Bases. VLDB ’00. Sep. 10-14, Cairo, Egypt. P. 363-372.
14.  Ermshaus A., Schafer P., Leser U. ClaSP: parameter-free time series segmentation // Data Mining and Knowledge Discovery. 2023. Vol. 37, N 3. P. 1262-1300. DOI: http://dx.doi.org/10. 1007/sl0618-023-00923-xl0.1007/sl0618-023-00923-x.
15.  Gharghabi S., Yeh C., Ding Y. et.al. Domain agnostic online semantic segmentation for multidimensional time series // Data Mining and Knowledge Discovery. 2018. Vol. 33, N 1. P. 96-130. DOI: http://dx.doi.org/10.1007/sl0618-018-0589-310.1007/sl0618-018-0589-3.
16.  Yeh C., Zhu Y., Ulanova L. et. al. Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets // 2016 IEEE 16th International Conference on Data Mining. ICDM 2016. Dec. 12-15, 2016, Barcelona, Spain. P. 1317-1322. DOI: http://dx.doi.org/10.1109/ICDM.2016.017910.1109/ICDM.2016.0179.
17.  Jin X., Han J. К-Means Clustering // Encyclopedia of Machine Learning. Springer US, 2011. P. 563-564. DOI: http://dx.doi.Org/10.1007/978-0-387-30164-8_425l0.1007/978-0-387- 30164-8^425.
18.  Truong C., Oudre L., Vavatis N. Selective review of offline change point 1 detection methods // Signal Processing. 2020. Vol. 167. P. 107299. DOI: http://dx.doi.Org/10.1016/j.sigpro.2019. 10729910.1016/j.sigpro.2019.107299.
19.  Zhou W., Chan Y. E., Foo C. S. et. al. High-Resolution Digital Phenotypes From Consumer Wearables and Their Applications in Machine Learning of Cardiometabolic Risk Markers: Cohort Study // Journal of Medical Internet Research. 2022. Vol. 24, N 7. P. e34669. DOI: http://dx.doi. org/10.2196/3466910.2196/34669.
20.  Diraco G., Siciliano P., Leone A. Behavioral Change Prediction from Physiological Signals Using Deep Learned Features // Sensors. 2022. Vol. 22, N 9. P. 3468. DOI: http://dx.doi.org/10.3390/ s2209346810.3390/s22093468.
21.  Gamberini A., Abdallah I. Active trailing edge flap system fault detection via machine learning // Wind Energy Science. 2024. Vol. 9, N 1. P. 181-201. DOI: http://dx.doi.org/10.5194/ wes-9-181-202410.5194/wes-9-181-2024.
22.  Tafazoli S., Lu Y., Wu R., Srinivas T. et. al. C22MP: the marriage of catch22 and the matrix profile creates a fast, efficient and interpretable anomaly detector // https://doi.org/10.1007/ S10115-024-02107-5 Knowledge and Information Systems. 2024. Vol. 66, N 8. P. 4789-4823. DOI: http: //dx. doi . org/10.1007/sl0115-024-02107-510.1007/sl0115-024-02107-5.
23.  N. Satish, M. Harris, and M. Garland. Designing efficient sorting algorithms for manycore GPUs // Proceedings of the 2009 IEEE International Symposium on Parallel к Distributed Processing. IEEE Comput. Soc. Press. IPDPS ’09. May 23-29, Rome, Italy. P. 1-10. DOI: http://dx.doi.org/ 10.1109/IPDPS. 2009.516100510.1109/IPDPS.2009.5161005.
24.  Wang X., Wirth A., Wang L. Structure-Based Statistical Features and Multivariate Time Series Clustering // Seventh IEEE International Conference on Data Mining. ICDM 2007. Oct. 28-31, 2007, Omaha, Nebraska, USA. P. 351-360. DOI: http://dx.doi.org/10.1109/ICDM.2007. 10310.1109/ICDM.2007.103.
25.  NVIDIA: cuFFT API reference. [El. Res.]: http://www.cs.fit.edu/~pkc/nasa/ data/http://www.cs.fit.edu/ ркс/nasa/data/. Access date: 2025-07-20.
26.  Биленко P. В., Долганина Н.Ю., Иванова E.B., Рекачинский А. И. Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университета // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. 2022. Т. 11, № 1. DOI: http://dx.doi.org/10.14529/cmse22010210.14529/cmse220102.
27.  Zymbler М., Goglachev A. Fast Summarization of Long Time Series with Graphics Processor // Mathematics. 2022. Vol. 10, N 10. P. 1781. DOI: http://dx.doi.org/10.3390/ mathl010178110.3390/mathl0101781.
28.  Reiss A., Strieker D. Introducing a New Benchmarked Dataset for Activity Monitoring // 2012 16th International Symposium on Wearable Computers. ISWC 2012. June 18-22, 2012. DOI: http: //dx. doi . org/10.1109/ISWC. 2012.1310.1109/ISWC.2012.13.
29.  Harris M. Optimizing parallel reduction in CUDA // NVIDIA Developer Technol. 2007. Vol. 2, N 4. P. 70.