2

I have a stream of integer data and want to perform some statistical analysis on it. I want to calculate the mean and the standard deviation of it. So far it isn't hard, but keep in mind that I am talking about streams of data, I'd prefer not to store all of the data. There exists both an algorithm for the mean and the deviation to keep the stored data at a minimum - I'd refer to Wikipedia in this matter.

But the problem now is that some of the data will be completely absurd in regards to the rest of the data. For example I will receive

1 2 2134 7 -2 14 // 2134 is out of line and junk, don't calculate with it

I know in what ranges my values will likely be, but only relative to their average value. So I'd like to know if there is a good approach to tackle these kind of noises.

It is even more annoying, as the junk data will most likely be the first to arrive and not in line with the mean value of the rest of the sequence so I can't precalculate the mean value. An example would be something like

1111 1564 13 1645 12 -4 37 90 ...

The junk makes < 5% of the data, so at least there isn't much noise, but I have to keep it out of my calculation.


To distinguish between real and junk data, I know that the real data lies in a bounded interval around the mean value - scaled to the example above, it would be something like +-200. "Groups" of junk data can behave in the same way, only that their mean value differs by at least 1 times the length of the interval from the mean value of the real data.

At the beginning, without any data, I have no idea what the mean value of the real data might be.

I can replay a limited amount/small fraction of data only by first saving it to memory.


Is there a good algorithm that occupies as little as possible space and works when applied iteratively to a sequence?

  • 2
    How do you determine what is noise and what is good data? – Adam Zuckerman Aug 6 '15 at 17:54
  • @AdamZuckerman The data lies in an intervall within a bounded range from the overall mean value of all relevant data. This range is - speaking relatively to the example about +-200. The junk however, separated into several groups, they all have about the same value range to their mean value – WorldSEnder Aug 6 '15 at 17:56
  • So, at the beginning of the sequence, if you have an excessive number (lets say 9000), you have no way of knowing if that is valid or not until after receiving many more data points? – Adam Zuckerman Aug 6 '15 at 18:02
  • 3
    What you need is a Moving Average, a Standard Deviation and a bit of statistical analysis. You should be able to calculate how many points you need to have in your buffer to get a 99% confidence level in identifying your outlying data points. I'd be surprised if it is more than about twenty. Or, y'know, you can just tweak your algorithm until you get the results you expect. – Robert Harvey Aug 6 '15 at 18:44
  • 1
    @WorldSEnder can you replay the data? I.e. would it be possible to perform an initial pass to analyze the data in order to determine what the good and bad values are. Then process it a second time to do the actual calculations, discarding outlier values as determined by the criteria established in the first pass? – user22815 Aug 6 '15 at 20:04
3

Signal processing is a huge topic, and a lot depends on your application, but a good start for your research would be a Kalman filter. It's recursive, so it doesn't require storing the entire history, and is commonly used for tasks like filtering outliers out of a sensor signal.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.