Восстановление многомерных временных рядов на основе выявления поведенческих шаблонов и применения автоэнкодеров

Алексей Артемьевич Юртин

Аннотация


В настоящее время в широком спектре предметных областей актуальной является задача восстановления пропущенных точек или блоков значений временных рядов. В статье представлен метод SAETI (Snippet-based Autoencoder for Time-series Imputation) для восстановления пропусков в многомерных временных рядах, который основан на совместном применении нейросетевых моделей-автоэнкодеров и аналитического поиска во временном ряде поведенческих шаблонов (сниппетов). Восстановление многомерной подпоследовательности, содержащей пропуски, выполняется посредством двух следующих нейросетевых моделей. Распознаватель получает на вход подпоследовательность, в которой пропуски предварительно заменены на нули, и для каждого измерения определяет соответствующий сниппет. Реконструктор принимает на вход подпоследовательность и набор сниппетов, полученных Распознавателем, и заменяет пропуски на правдоподобные синтетические значения. Реконструктор реализован как совокупность двух следующих моделей: Энкодер, формирующий скрытое состояние для совокупности входной подпоследовательности и распознанных сниппетов; Декодер, получающий на вход скрытое состояние, который восстанавливает исходную подпоследовательность. Представлено детальное описание архитектур вышеперечисленных моделей. Результаты экспериментов над реальными временными рядами из различных предметных областей показывают, что SAETI в среднем опережает передовые аналоги по точности восстановления и показывает лучшие результаты в случае, когда восстанавливаются данные, отражающие активность некоего субъекта.

Ключевые слова


временной ряд; восстановление пропущенных значений; автоэнкодер; поведенческие шаблоны (сниппеты) временного ряда; нейронные сети

Полный текст:

PDF

Литература


Kumar S., Tiwari P., Zymbler M.L. Internet of Things is a revolutionary approach for future technology enhancement: a review // J. Big Data. 2019. Vol. 6. P. 111. DOI: 10.1186/S40537-019-0268-2.

Gratius N., Wang Z., Hwang M.Y., et al. Digital Twin Technologies for Autonomous Environmental Control and Life Support Systems // J. Aerosp. Inf. Syst. 2024. Vol. 21, no. 4. P. 332–347. DOI: 10.2514/1.I011320.

Zhou Z., Tang W., Li M., et al. A Novel Hybrid Intelligent SOPDEL Model with Comprehensive Data Preprocessing for Long-Time-Series Climate Prediction // Remote. Sens. 2023. Vol. 15, no. 7. P. 1951. DOI: 10.3390/RS15071951.

Majumdar S., Laha A.K. Clustering and classification of time series using topological data analysis with applications to finance // Expert Syst. Appl. 2020. Vol. 162. P. 113868. DOI: 10.1016/J.ESWA.2020.113868.

Yen N.Y., Chang J., Liao J., Yong Y. Analysis of interpolation algorithms for the missing values in IoT time series: a case of air quality in Taiwan // J. Supercomput. 2020. Vol. 76, no. 8. P. 6475–6500. DOI: 10.1007/S11227-019-02991-7.

Khayati M., Arous I., Tymchenko Z., Cudr'e-Mauroux P. ORBITS: Online Recovery of Missing Values in Multiple Time Series Streams // Proc. VLDB Endow. 2020. Vol. 14, no. 3. P. 294–306. DOI: 10.5555/3430915.3442429.

Khayati M., Lerner A., Tymchenko Z., Cudr'e-Mauroux P. Mind the Gap: An Experimental Evaluation of Imputation of Missing Values Techniques in Time Series // Proc. VLDB Endow. 2020. Vol. 13, no. 5. P. 768–782. DOI: 10.14778/3377369.3377383.

Fang C., Wang C. Time Series Data Imputation: A Survey on Deep Learning Approaches // CoRR. 2020. Vol. abs/2011.11347. arXiv: 2011.11347. URL: https://arxiv.org/abs/2011.11347.

Wang J., Du W., Cao W., et al. Deep Learning for Multivariate Time Series Imputation: A Survey // CoRR. 2024. Vol. abs/2402.04059. DOI: 10.48550/ARXIV.2402.04059. arXiv: 2402.04059.

Imani S., Madrid F., Ding W., et al. Introducing time series snippets: A new primitive for summarizing long time series // Data Min. Knowl. Discov. 2020. Vol. 34, no. 6. P. 1713–1743. DOI: 10.1007/s10618-020-00702-y.

Цымблер М.Л., Юртин А.А. Восстановление пропущенных значений временного ряда на основе совместного применения аналитических алгоритмов и нейронных сетей // Вычислительные методы и программирование. 2023. Т. 24, № 3. C. 243–259. DOI: 10.26089/NumMet.v24r318.

Li L., McCann J., Pollard N.S., Faloutsos C. DynaMMo: mining and summarization of coevolving sequences with missing values // Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28 - July 1, 2009 / ed. by J.F.E. IV, F. Fogelman-Souli'e, P.A. Flach, M.J. Zaki. ACM, 2009. P. 507–516. DOI: 10.1145/1557019.1557078.

Khayati M., Cudré-Mauroux P., Böhlen M.H. Scalable recovery of missing blocks in time series with high and low cross-correlations // Knowl. Inf. Syst. 2020. Vol. 62, no. 6. P. 2257–2280. DOI: 10.1007/S10115-019-01421-7.

Mazumder R., Hastie T., Tibshirani R. Spectral Regularization Algorithms for Learning Large Incomplete Matrices // J. Mach. Learn. Res. 2010. Vol. 11. P. 2287–2322. DOI: 10.5555/1756006.1859931.

Cao W., Wang D., Li J., et al. BRITS: Bidirectional Recurrent Imputation for Time Series // Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montreal, Canada /ed. by S. Bengio, H.M. Wallach, H. Larochelle, et al. 2018. P. 6776–6786. URL: https://proceedings.neurips.cc/paper/2018/hash/734e6bfcd358e25ac1db0a4241b95651-Abstract.html.

Yoon J., Zame W.R., Schaar M. van der. Estimating Missing Data in Temporal Data Streams Using Multi-Directional Recurrent Neural Networks // IEEE Trans. Biomed. Eng. 2019. Vol. 66, no. 5. P. 1477–1490. DOI: 10.1109/TBME.2018.2874712.

Luo Y., Zhang Y., Cai X., Yuan X. E2GAN: End-to-End Generative Adversarial Network for Multivariate Time Series Imputation // Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 / ed.by S. Kraus. ijcai.org, 2019. P. 3094–3100. DOI: 10.24963/IJCAI.2019/429.

Wu Z., Ma C., Shi X., et al. BRNN-GAN: Generative Adversarial Networks with Bi-directional Recurrent Neural Networks for Multivariate Time Series Imputation // 27th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2021, Beijing, China, December 14-16, 2021. IEEE, 2021. P. 217–224. DOI: 10.1109/ICPADS53394. 2021.00033.

Du W., C^ot'e D., Liu Y. SAITS: Self-attention-based imputation for time series // Expert Syst. Appl. 2023. Vol. 219. P. 119619. DOI: 10.1016/J.ESWA.2023.119619.

Oh E., Kim T., Ji Y., Khyalia S. STING: Self-attention based Time-series Imputation Networks using GAN // IEEE International Conference on Data Mining, ICDM 2021, Auckland, New Zealand, December 7-10, 2021 / ed. by J. Bailey, P. Miettinen, Y.S. Koh, et al. IEEE, 2021. P. 1264–1269. DOI: 10.1109/ICDM51629.2021.00155.

Liu Y., Yu R., Zheng S., et al. NAOMI: Non-Autoregressive Multiresolution Sequence Imputation // Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada / ed. by H.M. Wallach, H. Larochelle, A. Beygelzimer, et al. 2019. P. 11236–11246. URL: https://proceedings.neurips.cc/paper/2019/hash/50c1f44e426560f3f2cdcb3e19e39903-Abstract.html.

Fortuin V., Baranchuk D., Rätsch G., Mandt S. GP-VAE: Deep Probabilistic Time Series Imputation // The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy]. Vol. 108 / ed. by S. Chiappa, R. Calandra. PMLR, 2020. P. 1651–1661. Proceedings of Machine Learning Research. URL: http://proceedings.mlr.press/v108/fortuin20a.html.

Kingma D.P., Welling M. Auto-Encoding Variational Bayes // CoRR. 2013. Vol. abs/1312.6114. URL: https://api.semanticscholar.org/CorpusID:216078090.

Roberts S.J., Osborne M.A., Ebden M., et al. Gaussian processes for time-series modelling // Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2013. Vol. 371. URL: https://api.semanticscholar.org/CorpusID: 556194.

Gharghabi S., Imani S., Bagnall A.J., et al. An ultra-fast time series distance measure to allow data mining in more complex real-world deployments // Data Min. Knowl. Discov. 2020. Vol. 34, no. 4. P. 1104–1135. DOI: 10.1007/s10618-020-00695-8.

Benschoten A.V., Ouyang A., Bischoff F., Marrs T. MPA: a novel cross-language API for time series analysis // Journal of Open Source Software. 2020. Vol. 5, no. 49. P. 2179. DOI: 10.21105/joss.02179.

Hochreiter S. The Vanishing Gradient Problem During Learning Recurrent Neural Nets and Problem Solutions // Int. J. Uncertain. Fuzziness Knowl. Based Syst. 1998. Vol. 6, no. 2. P. 107–116. DOI: 10.1142/S0218488598000094.

Chung J., Gulcehre C., Cho K., Bengio Y. Gated Feedback Recurrent Neural Networks // Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015. Vol. 37 / ed. by F.R. Bach, D.M. Blei. JMLR.org, 2015. P. 2067–2075. JMLR Workshop and Conference Proceedings. URL: http://proceedings.mlr.press/v37/chung15.html.

Guo Y., Li S., Lerman G. The effect of Leaky ReLUs on the training and generalization of overparameterized networks // International Conference on Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain. Vol. 238 / ed. by S. Dasgupta, S. Mandt, Y. Li. PMLR, 2024. P. 4393–4401. Proceedings of Machine Learning Research. URL: https://proceedings.mlr.press/v238/guo24c.html.

Dumoulin V., Visin F. A guide to convolution arithmetic for deep learning // CoRR. 2016. Vol. abs/1603.07285. arXiv: 1603.07285. URL: http://arxiv.org/abs/1603.07285.

Биленко Р.В., Долганина Н.Ю., Иванова Е.В., Рекачинский А.И. Высокопроизводительные вычислительные ресурсы Южно-Уральского государственного университет // Вычислительные методы и программирование. 2022. Т. 11, № 1. C. 15–30. DOI: 10.14529/cmse220102.

Bundesamt für Umwelt – Swiss Federal Office for the Environment. Accessed: 2023-09-03. https://www.hydrodaten.admin.ch/.

Lozano A.C., Li H., Niculescu-Mizil A., et al. Spatial-temporal causal modeling for climate change attribution // Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, France, June 28 - July 1, 2009 / ed. by J.F.E. IV, F. Fogelman-Souli'e, P.A. Flach, M.J. Zaki. ACM, 2009. P. 587–596. DOI: 10.1145/1557019.1557086.

Lefebvre A. MAREL Carnot data and metadata from Coriolis Data Centre. SEANOE. 2015. Accessed: 2023-09-03 DOI: 10.17882/39754.

MeteoSwiss: Federal Office of Meteorology and Climatology. 2023. Accessed: 2023-09-03. https://www.meteoswiss.admin.ch/services-and-publications/service/open-government-data.html.

Weather Station Saaleaue, Max Planck Institute for Biogeochemistry, Germany. Accessed: 2023-09-03. https://www.bgc-jena.mpg.de/wetter/weather_data.html.

Trindade A. Electricity Load Diagrams 2011–2014. 2015. DOI: 10.24432/C58C86. UCI Machine Learning Repository.

Laña I., Olabarrieta I., Vélez M., Ser J.D. On the imputation of missing data for road traffic forecasting: New insights and novel techniques // Transportation Research Part C: Emerging Technologies. 2018. Vol. 90. P. 18–33. DOI: 10.1016/j.trc.2018.02.021.

Mutschler C., Ziekow H., Jerzak Z. The DEBS 2013 grand challenge // The 7th ACM International Conference on Distributed Event-Based Systems, DEBS '13, Arlington, TX, USA, June 29 - July 03, 2013 / ed. by S. Chakravarthy, S.D. Urban, P.R. Pietzuch, E.A. Rundensteiner. ACM, 2013. P. 289–294. DOI: 10.1145/2488222.2488283.

Minor B.D., Doppa J.R., Cook D.J. Learning Activity Predictors from Sensor Data: Algorithms, Evaluation, and Applications // IEEE Trans. Knowl. Data Eng. 2017. Vol. 29, no. 12. P. 2744–2757. DOI: 10.1109/TKDE.2017.2750669.

Shu X., Porikli F., Ahuja N. Robust Orthonormal Subspace Learning: Efficient Recovery of Corrupted Low-Rank Matrices // 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014. IEEE Computer Society, 2014. P. 3874–3881. DOI: 10.1109/CVPR.2014.495.

Balzano L., Chi Y., Lu Y.M. Streaming PCA and Subspace Tracking: The Missing Data Case // Proc. IEEE. 2018. Vol. 106, no. 8. P. 1293–1310. DOI: 10.1109/JPROC.2018.2847041.

Troyanskaya O.G., Cantor M.N., Sherlock G., et al. Missing value estimation methods for DNA microarrays // Bioinform. 2001. Vol. 17, no. 6. P. 520–525. DOI: 10.1093/BIOINFORMATICS/17.6.520.

Cai J., Cand`es E.J., Shen Z. A Singular Value Thresholding Algorithm for Matrix Completion // SIAM J. Optim. 2010. Vol. 20, no. 4. P. 1956–1982. DOI: 10.1137/080738970.

Mei J., Castro Y. de, Goude Y., H'ebrail G. Nonnegative Matrix Factorization for Time Series Recovery From a Few Temporal Aggregates // Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. Vol. 70 / ed. by D. Precup, Y.W. Teh. PMLR, 2017. P. 2382–2390. Proceedings of Machine Learning Research. URL: http://proceedings.mlr.press/v70/mei17a.html.




DOI: http://dx.doi.org/10.14529/cmse240203