Fast algorithm for cleaning highly noisy measurement data from outliers, based on the search for the optimal solution with the minimum number of rejected measurement data

Igor V. Bezmenov; Igor V. Bezmenov

doi:10.3934/mina.2024005

Metascience in Aerospace

2024, Volume 1, Issue 1: 110-129. doi: 10.3934/mina.2024005

Previous Article Next Article

Research article

Fast algorithm for cleaning highly noisy measurement data from outliers, based on the search for the optimal solution with the minimum number of rejected measurement data

Igor V. Bezmenov ^,

Russian Metrological Institute of Technical Physics and Radio Engineering, Mendeleevo, Moscow Region, Russia

Received: 27 October 2023 Revised: 19 December 2023 Accepted: 21 December 2023 Published: 26 December 2023

In this article, I discuss the problem of automatic detection of coarse measurements (outliers) in the time series of measurement data generated by technical devices. Solving this problem is of great importance to improve the accuracy of estimates of various physical quantities obtained in solving many applications in which the input data is observations. Since outliers adversely affect the accuracy of final results, they must be detected and removed from further calculations at the stage of data preprocessing and analysis. This can be done in various ways, since the concept of outliers does not have a strict definition in statistics. The author of the article previously formulated the problem of finding the optimal solution that satisfies the condition of maximizing the amount of measuring data that remained after removal of outliers and proposed a robust algorithm for finding such a solution. The complexity of this algorithm is estimated of the order of magnitude $ (N+{N}_{out}^{2}) $, where N is the number of source data and N_out is the number of outliers detected. For highly noisy data, the number of outliers can be extremely large, for example, comparable to N. In this case, it will take about N² arithmetic operations to find the optimal solution using the algorithm developed earlier. I propose a new algorithm for finding the optimal solution, requiring the order of NlogN arithmetic operations, regardless of the number of outliers detected. The efficiency of the algorithm is manifested when cleaning from outliers large amounts of highly noisy measuring data containing a great many of outliers. The algorithm can be used for automated cleaning from outliers of observation data in information and measuring systems, in systems with artificial intelligence, as well as when solving various scientific, applied managerial and other problems using modern computer systems in order to obtain promptly the most accurate final result.
- information and measuring systems,
- time series,
- data pre-processing,
- outliers,
- data cleaning from outliers,
- optimal solution
Citation: Igor V. Bezmenov. Fast algorithm for cleaning highly noisy measurement data from outliers, based on the search for the optimal solution with the minimum number of rejected measurement data[J]. Metascience in Aerospace, 2024, 1(1): 110-129. doi: 10.3934/mina.2024005

Related Papers:

Abstract

In this article, I discuss the problem of automatic detection of coarse measurements (outliers) in the time series of measurement data generated by technical devices. Solving this problem is of great importance to improve the accuracy of estimates of various physical quantities obtained in solving many applications in which the input data is observations. Since outliers adversely affect the accuracy of final results, they must be detected and removed from further calculations at the stage of data preprocessing and analysis. This can be done in various ways, since the concept of outliers does not have a strict definition in statistics. The author of the article previously formulated the problem of finding the optimal solution that satisfies the condition of maximizing the amount of measuring data that remained after removal of outliers and proposed a robust algorithm for finding such a solution. The complexity of this algorithm is estimated of the order of magnitude $ (N+{N}_{out}^{2}) $, where N is the number of source data and N_out is the number of outliers detected. For highly noisy data, the number of outliers can be extremely large, for example, comparable to N. In this case, it will take about N² arithmetic operations to find the optimal solution using the algorithm developed earlier. I propose a new algorithm for finding the optimal solution, requiring the order of NlogN arithmetic operations, regardless of the number of outliers detected. The efficiency of the algorithm is manifested when cleaning from outliers large amounts of highly noisy measuring data containing a great many of outliers. The algorithm can be used for automated cleaning from outliers of observation data in information and measuring systems, in systems with artificial intelligence, as well as when solving various scientific, applied managerial and other problems using modern computer systems in order to obtain promptly the most accurate final result.

References

[1]	Dach R, Beutler G, Hugentobler U, et al. (2003) Time Transfer Using GPS Carrier Phase: Error Propagation and Results. J Geodesy 77: 1–14. https://doi.org/10.1007/s00190-002-0296-z doi: 10.1007/s00190-002-0296-z
[2]	Donchenko SI, Blinov IY, Norets IB, et al. (2020) Characteristics of the Long-Term Instability of the New-Generation Hydrogen Frequency and Time Standards. Meas Tech 63: 34–37. https://doi.org/10.1007/s11018-020-01746-8 doi: 10.1007/s11018-020-01746-8
[3]	Perov AI, Kharisov VN (2010) GLONASS: Principles of Construction and Functioning, Moscow, Radiotekhnika, 4. (In Russ.)
[4]	Pasynok SL (2020) Increase in the Determination Accuracy of the Earth's Rotation Parameters by Combining the Results of Various Types of Measurements in the Main Metrological Center of the State Service of Time, Frequency, and Earth's Rotation Parameters Evaluation. Meas Tech 63: 38–44. https://doi.org/10.1007/s11018-020-01747-7 doi: 10.1007/s11018-020-01747-7
[5]	International GNSS Service, available from: http://www.igs.org/network.
[6]	Dach R, Lutz S, Walser P, et al. (2015) Bernese GNSS Software Version 5.2. Astronomical Institute, University of Bern, Bern Open Publishing. https://doi.org/10.7892/boris.72297
[7]	Mehlstäubler TE, Grosche G, Lisdat C, et al. (2018) Atomic Clocks for Geodesy. Rep Prog Phys 81: 064401. https://doi.org/10.1088/1361-6633/aab409 doi: 10.1088/1361-6633/aab409
[8]	Levine J (2008) A Review of Time and Frequency Transfer Methods. Metrologia 45: S162–S174. available from: https://iopscience.iop.org/article/10.1088/0026-1394/45/6/S22.
[9]	Karaush AA (2022) Automatic System for Remote Time-Scale Comparison and Prediction Using Carrier-Phase Measurements of the Global Navigation Satellite Systems. Meas Tech 65: 660–665. https://doi.org/10.1007/s11018-023-02136-6 doi: 10.1007/s11018-023-02136-6
[10]	Riley WJ (2008) Handbook of Frequency Stability Analysis. National Institute of Standards and Technology. https://doi.org/10.6028/nist.sp.1065
[11]	Bezmenov IV, Ignatenko Yu I, Pasynok SL (2022) New Methods for Achieving Advanced Accuracy in Time and Coordinate Measurements. Trudy IAA RAS 60: 12–20. https://doi.org/10.32876/ApplAstron.60.12-20 doi: 10.32876/ApplAstron.60.12-20
[12]	Blazquez-Garcia A, Conde A, Mori U, et al. (2021) A Review on Outlier/Anomaly Detection in Time Series Data. ACM Comput Surv 54: 1–33. https://doi.org/10.1145/3444690 doi: 10.1145/3444690
[13]	Bezmenov IV, Naumov AV, Pasynok SL (2018) An Effective Algorithm for Elimination of Outliers from Data Measurements of Global Navigation Satellite Systems. Meas Tech 61: 878–884. https://doi.org/10.1007/s11018-018-1518-y doi: 10.1007/s11018-018-1518-y
[14]	Bezmenov IV (2021) Effective Algorithms for Detection Outliers and Cycle Slip Repair in GNSS Data Measurements, In: Satellite Systems: Design, Modeling, Simulation and Analysis, Nguyen, London, UK, IntechOpen, 177–209. https://doi.org/10.5772/intechopen.92658
[15]	Bezmenov IV (2023) Method of Cleaning Outliers from Measurement Data: Search for the Optimal Solution with the Minimum Number of Rejected Measured Data. Meas Tech 66: 14–23. https://doi.org/10.1007/s11018-023-02184-y doi: 10.1007/s11018-023-02184-y
[16]	Bezmenov IV, Drozdov AE, Pasynok SL (2022) A Strategy for Finding Outliers in Noisy Data Series Including an Unknown Trend. Meas Tech 65: 339–345. https://doi.org/10.1007/s11018-022-02085-6 doi: 10.1007/s11018-022-02085-6
[17]	Katajainen J, Träff JL (1997) A meticulous analysis of mergesort programs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds) Algorithms and Complexity. CIAC. Lecture Notes in Computer Science, 1203. Springer, https://doi.org/10.1007/3-540-62592-5_74

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)