Об одном методе восстановления пропущенных значений потокового временного ряда в режиме реального времени

Михаил Леонидович Цымблер, Вячеслав Александрович Полонский, Алексей Артемьевич Юртин

Аннотация


Проблема восстановления пропущенных значений потокового временного ряда в режиме реального времени возникает в широком спектре практических приложений цифровой индустрии и интернета вещей. В статье предложен новый метод восстановления на основе совместного применения технологий интеллектуального анализа временных рядов и искусственных нейронных сетей. Метод предполагает три этапа восстановления: предварительная обработка данных, распознавание и реконструкция. Предварительная обработка предполагает однократную предварительную подготовку обучающих выборок данных. Распознавание и реконструкция реализуются с помощью нейронных сетей, обучаемых на указанных выборках. Предварительной обработке подвергается заранее сохраненный фрагмент потокового временного ряда без пропусков, в котором выполняется поиск набора типичных подпоследовательностей (сниппетов). Распознавание реализуется с помощью сверточной нейронной сети, на вход которой подается вектор из элементов временного ряда, предшествующих пропуску. Распознаватель выдает сниппет, на который более всего похожа входная подпоследовательность. Реконструкция реализуется с помощью рекуррентной нейронной сети, на вход которой подается конкатенация вывода распознавателя и вектора элементов ряда, предшествующих пропуску. Реконструктор выдает восстановленное значение. Представлены результаты экспериментов, показывающих высокую точность восстановления и преимущество предложенного метода перед аналогами.

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


временной ряд; восстановление пропущенных значений; режим реального времени; сверточная нейронная сеть, рекуррентная нейронная сеть; типичные подпоследовательности

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

PDF

Литература


Kumar S., Tiwari P., Zymbler M. 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.

Xu L.D., Duan L. Big Data for cyber physical systems in Industry 4.0: A survey. Enterp. Inf. Syst. 2019. Vol. 13, no. 2. P. 148–169. DOI: 10.1080/17517575.2018.1442934.

Zymbler M.L., Kraeva Y.A., Latypova E.A. et al. Cleaning sensor data in intelligent heating control system. Bulletin of the South Ural State University. Series: Computational Mathematics and Computational Mathematics and Software Engineering. 2021. Vol. 10, no. 3. P. 16–36. (in Russian) DOI: 10.14529/cmse210302.

Ivanov S.A., Nikolskaya K.Y., Radchenko G.I. et al. Digital twin of a city: concept overview. Bulletin of the South Ural State University. Series: Computational Mathematics and Computational Mathematics and Software Engineering. 2020. Vol. 9, no. 4. P. 5–23. (in Russian) DOI: 10.14529/cmse200401.

Epishev V.V., Isaev A.P., Miniakhmetov R.M. et al. Physiological data mining system for elite sports. Bulletin of the South Ural State University. Computational Mathematics and Software Engineering. 2013. Vol. 2, no. 1. P. 44–54. (in Russian) DOI: 10.14529/cmse130105.

Abdullaev S.M., Lenskaya O.Y., Gayazova A.O. et al. Short-range forecasting algorithms using radar data: translation estimate and life-cycle composite display. Bulletin of the South Ural State University. Series: Computational Mathematics and Computational Mathematics and Software Engineering. 2014. Vol. 3, no. 1. P. 17–32. (in Russian) DOI: 10.14529/cmse140102.

Dyshaev M.M., Sokolinskaya I.M. Representation of trading signals based on the Kaufman’s Adaptive Moving Average in the form of a system of linear inequalities. Bulletin of the South Ural State University. Series: Computational Mathematics and Computational Mathematics and Software Engineering. 2013. Vol. 2, no. 4. P. 103–108. (in Russian) DOI: 10.14529/cmse130408.

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.

Sande I.G. Hot-deck imputation procedures. Incomplete data in sample surveys. 1983. Vol. 3. P. 339–349.

Batista G.E.A.P.A., Monard M.C. An Analysis of Four Missing Data Treatment Methods for Supervised Learning. Appl. Artif. Intell. 2003. Vol. 17, no. 5-6. P. 519–533. DOI: 10.1080/713827181.

de Carvalho Jr. O.A., Guimarães R.F., Gomes R.A.T., da Silva N.C. Time series interpolation. IEEE International Geoscience & Remote Sensing Symposium, IGARSS 2007, Barcelona, Spain, July 23–28, 2007. Proceedings. IEEE, 2007. P. 1959–1961. DOI: 10.1109/IGARSS.2007.4423211.

Yi B., Sidiropoulos N.D., Johnson T. et al. Online Data Mining for Co-Evolving Time Sequences. Proceedings of the 16th International Conference on Data Engineering, San Diego, California, USA, February 28 – March 3, 2000 / Ed. by Lomet D.B., Weikum G. IEEE Computer Society, 2000. P. 13–22. DOI: 10.1109/ICDE.2000.839383.

Paulhus J., Kohler M. Interpolation of missing precipitation records. Monthly Weather Review. 1952. Vol. 80, no. 8. P. 129–133. DOI: 10.1175/1520-0493(1952)080<0129:IOMPR>2.0.CO;2.

Box G.E., Jenkins G.M., Reinsel G.C., Ljung G.M. Time Series Analysis: Forecasting and Control, 5th Edition. John Wiley & Sons, 2015. 712 p.

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.

Khayati M., Böhlen M.H. REBOM: Recovery of Blocks of Missing Values in Time Series. Proceedings of the 18th International Conference on Management of Data, COMAD 2012, Pune, India / Ed. by Sahasrabuddhe C., Abbadi A.E., Murthy K., Bhattacharya A. Computer Society of India, 2012. P. 44–55. URL: http://comad.in/comad2012/pdf/khayati.pdf.

Khayati M., Böhlen M.H., Gamper J. Memory-efficient centroid decomposition for long time series. IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 – April 4, 2014 / Ed. by Cruz I.F., Ferrari E., Tao Y. et al. IEEE Computer Society, 2014. P. 100–111. DOI: 10.1109/ICDE.2014.6816643.

Papadimitriou S., Sun J., Faloutsos C., Yu P.S. Dimensionality Reduction and Filtering on Time Series Sensor Streams. Managing and Mining Sensor Data / Ed. by Aggarwal C.C. Springer, 2013. P. 103–141. DOI: 10.1007/978-1-4614-6309-2_5.

Pearson K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine. 1901. Vol. 2. P. 559–572. DOI: 10.1080/14786440109462720.

Wellenzohn K., Böhlen M.H., Dignös A. et al. Continuous Imputation of Missing Values in Streams of Pattern-Determining Time Series. Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21–24, 2017 / Ed. by Markl V., Orlando S., Mitschang B. et al. OpenProceedings.org, 2017. P. 330–341. DOI: 10.5441/002/edbt.2017.30.

Hsu H., Yang A.C., Lu M. KNN-DTW Based Missing Value Imputation for Microarray Time Series Data. J. Comput. 2011. Vol. 6, no. 3. P. 418–425. DOI: 10.4304/jcp.6.3.418-425.

Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series. Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical Report WS-94-03 / Ed. by Fayyad U.M., Uthurusamy R. AAAI Press, 1994. P. 359–370.

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, Montr´eal, Canada, December 3–8, 2018 / Ed. by Bengio S., Wallach H.M., Larochelle H. et al. 2018. P. 6776–6786. URL: https://proceedings.neurips.cc/paper/2018/hash/734e6bfcd358e25ac1db0a4241b95651-Abstract.html.

Guo Z., Wan Y., Ye H. A data imputation method for multivariate time series based on generative adversarial network. Neurocomputing. 2019. Vol. 360. P. 185–197. DOI: 10.1016/j.neucom.2019.06.007.

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.

Reingold E., Nievergelt J., Deo N. Combinatorial Algorithms: Theory and Practice. Prentice Hall, 1977. 433 p.

Cho K., van Merrienboer B., Gülçehre Ç. et al. Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, Doha, Qatar, October 25–29, 2014, A meeting of SIGDAT, a Special Interest Group of the ACL / Ed. by Moschitti A., Pang B., Daelemans W. ACL, 2014. P. 1724–1734. DOI: 10.3115/v1/d14-1179.

Hochreiter S., Bengio Y., Frasconi P., Schmidhuber J. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies. A Field Guide to Dynamical Recurrent Neural Networks / Ed. by Kremer S., Kolen J. Wiley-IEEE Press, 2001. P. 237–243. DOI: 10.1109/9780470544037.ch14.

Reiss A., Stricker D. Introducing a New Benchmarked Dataset for Activity Monitoring. 16th International Symposium onWearable Computers, ISWC 2012, Newcastle, United Kingdom, June 18–22, 2012. IEEE Computer Society, 2012. P. 108–109. DOI: 10.1109/ISWC.2012.13.

Candanedo L., Feldheim V., Deramaix D. Data driven prediction models of energy use of appliances in a low-energy house. Energy and Buildings. 2017. Vol. 140. P. 81–97. DOI: 10.1016/j.enbuild.2017.01.083.

Individual household electric power consumption data set. UCI Machine Learning Repository. URL: https://archive.ics.uci.edu/ml/datasets/individual+household+electric+power+consumption (accessed: 03.09.2021).

Moritz S., Bartz-Beielstein T. imputeTS: Time Series Missing Value Imputation in R. R Journal. 2017. Vol. 9, no. 1. P. 207. DOI: 10.32614/rj-2017-009.




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