ВОССТАНОВЛЕНИЕ МНОГОМЕРНЫХ ВРЕМЕННЫХ РЯДОВ НА ОСНОВЕ ВЫЯВЛЕНИЯ ПОВЕДЕНЧЕСКИХ ШАБЛОНОВ И ПРИМЕНЕНИЯ АВТОЭНКОДЕРОВ (2024)
В настоящее время в широком спектре предметных областей актуальной является задача восстановления пропущенных точек или блоков значений временных рядов. В статье представлен метод SAETI (Snippet-based Autoencoder for Time-series Imputation) для восстановления пропусков в многомерных временных рядах, который основан на совместном применении нейросетевых моделей-автоэнкодеров и аналитического поиска во временном ряде поведенческих шаблонов (сниппетов). Восстановление многомерной подпоследовательности, содержащей пропуски, выполняется посредством двух следующих нейросетевых моделей. Распознаватель получает на вход подпоследовательность, в которой пропуски предварительно заменены на нули, и для каждого измерения определяет соответствующий сниппет. Реконструктор принимает на вход подпоследовательность и набор сниппетов, полученных Распознавателем, и заменяет пропуски на правдоподобные синтетические значения. Реконструктор реализован как совокупность двух следующих моделей: Энкодер, формирующий скрытое состояние для совокупности входной подпоследовательности и распознанных сниппетов; Декодер, получающий на вход скрытое состояние, который восстанавливает исходную подпоследовательность. Представлено детальное описание архитектур вышеперечисленных моделей. Результаты экспериментов над реальными временными рядами из различных предметных областей показывают, что SAETI в среднем опережает передовые аналоги по точности восстановления и показывает лучшие результаты в случае, когда восстанавливаются данные, отражающие активность некоего субъекта.
Идентификаторы и классификаторы
- УДК
- 004.048. на реализацию искусственного интеллекта
519.254. Вычислительная обработка данных, алгоритмы - eLIBRARY ID
- 67910939
В настоящее время в широком спектре приложений возникает задача обработки временных рядов, содержащих пропущенные значения ввиду аппаратно-программных сбоев и человеческого фактора: Интернет вещей [1], управление системами жизнеобеспечения [2], моделирование климата [3] и финансы [4] и др. В подобных приложениях во временных рядах требуется заменить пропуски на синтетические значения, близкие к исходным, чтобы сохранить целостность данных и минимизировать искажения результатов их интеллектуального анализа. Арсенал подходов к решению задачи восстановления пропусков во временных рядах, разработанных научным сообществом, чрезвычайно широк и включает в себя статистические методы [5], аналитические алгоритмы [6, 7] и интенсивно развивающиеся в настоящее время нейросетевые модели [8, 9].
Список литературы
- 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 EDN: HEOOCC
- 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 EDN: PDARDK
- 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 EDN: NXNSYM
- 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 EDN: XPNZXL
- Khayati M., Arous I., Tymchenko Z., Cudré-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é-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. 10.48550/ARXIV.2402.04059. arXiv: 2402.04059. DOI: 10.48550/ARXIV.2402.04059.arXiv
-
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 EDN: BZXTCW -
Цымблер М.Л., Юртин А.А. Восстановление пропущенных значений временного ряда на основе совместного применения аналитических алгоритмов и нейронных сетей // Вычислительные методы и программирование. 2023. Т. 24, № 3. C. 243-259. DOI: 10.26089/NumMet.v24r318 EDN: BJZYCZ -
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é, 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 EDN: DEDPVQ -
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 EDN: OCIROT -
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, Montréal, Canada / ed. by S. Bengio, H.M. Wallach, H. Larochelle, et al. 2018. P. 6776-6786. URL: https://proceedings.neurips.cc/paper/2018/hash 734e6bfcd358e25ac1db0a4241b95651Abstract.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 Bidirectional 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ôté 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 EDN: ZZESPV -
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 EDN: ORIMXO -
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 EDN: ESDZQL -
Chung J., Gül\c cehre C\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 EDN: OLCPUG -
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é, 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. 10.24432/C58C86. UCI Machine Learning Repository. DOI: 10.24432/C58C86.UCIMachineLearningRepository -
Laña I., Olabarrieta I., Vélez M., Del Ser J. 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. 10.1109/JPROC. 2018.2847041. 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 EDN: ILFJTR -
Cai J., Candès 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 EDN: XXCDSQ -
Mei J., Castro Y. de, Goude Y., Hébrail 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.
Выпуск
Другие статьи выпуска
При исполнении параллельных программ, основанных на парадигме параллелизма задач, требуется решать ряд проблем, таких как выбор порядка запуска задач с учетом зависимостей между ними, распределение данных и задач по параллельным процессам, балансировка нагрузки на ресурсы. Эти проблемы относятся к области системного параллельного программирования, и их решение, как правило, обеспечивается специальной исполнительной системой. От качества решения этих проблем, а также от структуры и свойств прикладного алгоритма, лежащего в основе параллельной программы, зависит получаемая производительность. Если производительность программы недостаточна, то требуется ее оптимизация, а для этого нужно знать те причины («узкие места»), которые ограничивают ее производительность. Для определения узких мест программы обычно применяется профилирование, т.е. сбор некоторых характеристик исполнения, которые могут указать на источник проблемы. Однако обычные широко используемые средства профилирования параллельных программ не позволяют дать ответ в требуемых понятиях из-за сложности анализа асинхронного исполнения множества задач, а также из-за неспособности выделить в исполняющейся программе прикладную (множество задач) и системную (исполнительная система) компоненты. Поэтому для таких программ требуется разработка новых методов профилирования и анализа. В статье рассматривается проблема получения «понятных» характеристик выполнения параллельных программ на основе параллелизма задач для анализа производительности и оптимизации. Предлагается количественно оценить степень влияния следующих факторов: нехватка работы (Starvation), передача данных (Latency), накладные расходы (Overhead) и конфликт при доступе к общим ресурсам (Waiting for contention resolution). Представлен алгоритм получения соответствующих характеристик для системы фрагментированного программирования LuNA, а также способ их анализа для оптимизации LuNA-программ. Корректность подхода продемонстрирована на ряде синтетических экспериментов. Показано применение подхода к анализу «реальной» программы численного моделирования.
В статье предлагается новый метод распознавания строений на спутниковых снимках. Представленный метод является гибридным, он основан на алгоритме исключения областей и методе жука. Алгоритм исключения областей представляет собой хорошо известный и эффективный способ сегментации изображения на регионы схожих пикселей по различным признакам: цвет, текстура, яркость, форма и т.д. Метод жука - классический метод контурного анализа, выполняющий последовательное вычерчивание границы между объектом и фоном. В рамках работы предлагаемого алгоритма сначала метод исключения областей выделяет потенциальные области, в которых могут находиться строения и устраняет нежелательные элементы на изображении (растительность, водные поверхности и дороги), которые могут быть ложно распознаны как строения. Далее модифицированный метод жука определяет местоположение и контуры строений. На финальном этапе среди обнаруженных объектов выявляются искусственно созданные объекты, у которых имеется объем. Для реализации проверки объектов на искусственное происхождение и объемность разработаны собственные методы. Представленный алгоритм распознавания показывает хорошую точность распознавания и не требует обучающей выборки. В статье описывается программная реализация предлагаемого метода. Демонстрируются результаты вычислительных экспериментов по оцениванию эффективности метода и сравнению с тремя известными алгоритмами распознавания.
В работе предложен метод семантической сегментации облаков точек в виде рельефа местности с использованием мультимодальной архитектуры сверточной нейронной сети на основе регулярного динамического взвешенного графа, которая позволяет получать точное решение задачи семантической сегментации, используя комбинацию геометрических и цветовых признаков точек. Метод может быть эффективно использован для разреженных, зашумленных, неоднородных и невыпуклых облаков точек. В работе было проведено компьютерное моделирование известных методов для семантической сегментации 3D данных с использованием эталонной коллекции данных ModelNet 40 и набора данных археологических памятников бронзового века Южного Зауралья, а именно данных, полученных в результате тахеометрической съемки комплекса археологических памятников в долине реки Синташта с использованием тахеометра Trimble 3300. Был проведен сравнительный анализ предложенного метода и современных методов 3D семантической сегментации с разными комбинациями входных признаков облаков точек, также в работе исследовано влияние на точность семантической сегментации способа формирования облака точек: в первом случае исследовалось облако точек из эталонного набора данных во втором случае применены варианты с использованием 3D регистрации на основе алгоритма ICP (iterative closest point).
В статье представлен метод уменьшения ошибки реконструкции изображения для рентгеновской компьютерной томографии путем применения вейвлет-фильтрации зашумленных проекционных данных. Вейвлет-преобразование и основанное на нем вейвлет-фильтрация одномерных сигналов дает возможность определять конкретное место соответствия частотной и временной (в данном случае пространственной по координате детекторов) области. Это позволяет однозначно определять переход из частотной области в пространственную и обратно. Для фильтрации проекционных данных используется вейвлет-преобразование, которое дает возможность через коэффициенты, определяющие масштабирующие функции и функции вейвлетов определять в частотной и пространственной области место шума в зашумленном сигнале и осуществлять выделение не зашумленного сигнала путем назначения порогов фильтрации на вышеуказанные коэффициенты. Для усиления фильтрующих свойств вейвлет-преобразования предложено разбивать проекционные данные на интервалы, для каждого из которых определяются свои коэффициенты. Вейвлет-фильтрация проводится с использованием вейвлетов Добеши. Результаты исследований были подтверждены математическим моделированием зашумленных проекционных данных, их вейвлет-фильтрации и реконструкции по ним тестового томографического изображения. Математическая модель тестового объекта исследования и разработанный авторами программный реконструктор томографического изображения позволили осуществлять моделирование прямой (получение проекционных данных по тестовому объекту), обратной (получение тестового томографического изображения по проекционным данным объекта) задач томографии и осуществлять сравнительный анализ качества реконструкции изображения с «идеальными» и зашумленными проекционными данными.
Издательство
- Издательство
- ЮУрГУ
- Регион
- Россия, Челябинск
- Почтовый адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- Юр. адрес
- 454080, Уральский федеральный округ, Челябинская область, г. Челябинск, просп. В.И. Ленина, д. 76
- ФИО
- Александр Рудольфович Вагнер (Ректор)
- E-mail адрес
- admin@susu.ru
- Контактный телефон
- +7 (351) 2635882
- Сайт
- https://www.susu.ru