I am working on building a real-time system for processing and aggregating somewhat sparse and irregular survey measurements (ranges from 0-100, usually on the order of 20-100 measurements). I am looking for a way to remove the noise and smooth out this data so our end users can see the overall trend. The main constraint of the problem is that the data needs to be normalized online — past measurements cannot change as a user should be able to reference historical data. Are there any good algorithms to do this? I was thinking about a simple moving average, but it tends to be pretty volatile if an outlier enters/exits the averaging window. Thanks so much!
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Try a median filter: for each data point, take a window about that data point of a size you will need to experiment with, and let the new value for that data point be the median of all the points in the window. This is very robust to outliers, since medians are robust to outliers. It also has the virtue that, if your windows always include an odd number of data points, the result consists entirely of actual data points. They may shift about slightly from left to right or vice versa, but never farther than your window size. I think you will find that this filter crunches noise down very effectively.
One note: on the edges, you will need to have lop-sided windows, most likely. That shouldn't be too much of a problem - I'd still recommend having some algorithm ensure that every window has an odd number of data points in it.
One implementation detail is important: when you start replacing data points with medians of data points, don't allow the new median values to influence subsequent windows. Keep calculating medians based on the original data only.
answered Oct 20, 2021 at 17:57
-
$\begingroup$ Hey Adrian, thanks for the answer. I am a little confused on how this would work on the edges (which it is always going to be as we receive new data). The median (unless the window was of size 1 or 2), wouldn't incorporate that new data, right? Am I misunderstanding? $\endgroup$ Commented Oct 20, 2021 at 18:19
-
$\begingroup$ We still do want to incorporate all of the data points - they should have some effect, but it shouldn't be as pronounced in completely changing the value. Does that make sense? $\endgroup$ Commented Oct 20, 2021 at 18:20
-
$\begingroup$ First comment: on the edges, your window would have to be one-sided. So, for the first data point, you would examine the first 11 data points, say, and use the median of those as your first point. For the last data point, your window would have to look back in a similar fashion. Second comment: any filter you use will change the data somehow. And all the data points in my proposal are having an effect in choosing medians. It's true that the largest data point you have can be increased as much as you want without changing anything. But that's only because it was already the largest. $\endgroup$ Commented Oct 20, 2021 at 18:29
-
$\begingroup$ Understood. The only issue with the median approach is that it reduces the amount of data points we have (which are already quite irregular and sparse). It would be great if there was some methodology that did something similar to the median filter, but we didn't end up losing data. $\endgroup$ Commented Oct 20, 2021 at 21:26
-
$\begingroup$ Amrit: Look, you're asking to smooth the data, which by definition means altering it. But you want to do that without "losing data"? That's a contradiction right there - impossible by definition. Any smoothing algorithm is going to lose data - that's a 100% guarantee. Just consider an outlier: you would want your smoothing to change that point, right? What you really ought to be doing is improving your data rate! You haven't mentioned over what timescale your 100 measurements are taken, but increasing your data rate can only help, if it's at all possible. $\endgroup$ Commented Oct 20, 2021 at 21:42