18
$\begingroup$

We have a daemon that reads in data from some sensors, and among the things it calculates (besides simply just reporting the state) is the average time it takes for the sensors to change from one value to another. It keeps a running average of 64 datapoints, and assumes that runtime is fairly constant.

Unfortunately, as demonstrated by the below graph, the input data isn't the most pristine:

(Each line represents a different set of data; the x-axis doesn't really mean anything besides a vague historical time axis).

My obvious solution for dealing with this would be to create a histogram of the data and then pick the mode. However, I was wondering if there were other methods that would yield better performance or would be more suited for operation with a running average. Some quick Wikipedia searches suggest algorithms for detecting outliers may be also suitable. Simplicity is a plus, since the daemon is written in C.

Edit: I scoped out Wikipedia and came up with these various techniques:

  • Chauvenet's criterion: using the mean and standard deviation, calculate the probability a particular datapoint would happen, and then exclude it if the probability is actually that bad is less than 50%. While this seems to be well suited for correcting a running average on the fly, I'm not quite convinced of its efficacy: it seems with large data-sets it would not want to discard datapoints.

  • Grubbs' test: Another method that uses difference from the mean to standard deviation, and has some expression for when the hypothesis of "no outliers" is rejected

  • Cook's distance: Measures the influence a datapoint has on a least squares regression; our application would probably reject it if it exceeded 1

  • Truncated mean: Discard the low end and the high end, and then take the mean as normal

Anyone have any specific experience and can comment on these statistical techniques?

Also, some comments about the physical situation: we're measuring the average time until completion of a mechanical washing machine, so its runtime should be fairly constant. I'm not sure if it actually has a normal distribution.

Edit 2: Another interesting question: when the daemon is bootstrapping, as in, doesn't have any previous data to analyze, how should it deal with incoming data? Simply not do any outlier pruning?

Edit 3: One more thing... if the hardware does change such that the runtimes do become different, is it worth it to make the algorithm sufficiently robust such that it won't discard these new runtimes, I should I just remember to flush the cache when that happens?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ During bootstrapping provide 64 data points to seed the running average. $\endgroup$
    – ojblass
    Apr 12, 2009 at 7:47
  • 1
    $\begingroup$ But what would those 64 data points be? It might not be good to assume a priori that the machine would run in X time. $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 7:48
  • $\begingroup$ Grubbs' test is superior to the other methods because it is computationally cheaper to determine regression coefficients than to sort and rank data. $\endgroup$
    – ojblass
    Apr 12, 2009 at 7:49
  • $\begingroup$ The system has to know that it is being calibrated and bootstrapping itself. Typical techniques are to seed the first values with the initial value plus or minus ten percent. When the second value arrives the seeded values are the first and second values interleaved. $\endgroup$
    – ojblass
    Apr 12, 2009 at 7:53
  • $\begingroup$ Interesting! I agree that I probably want to avoid sorting data, which would make implementing a truncated mean difficult. $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 7:53

7 Answers 7

Reset to default
13
$\begingroup$

If that example graph you have is typical, then any of the criteria you list will work. Most of those statistical methods are for riding the edge of errors right at the fuzzy level of "is this really an error?" But your problem looks wildly simple.. your errors are not just a couple standard deviations from the norm, they're 20+. This is good news for you.

So, use the simplest heuristic. Always accept the first 5 points or so in order to prevent a startup spike from ruining your computation. Maintain mean and standard deviation. If your data point falls 5 standard deviations outside the norm, then discard it and repeat the previous data point as a filler.

If you know your typical data behavior in advance you may not even need to compute mean and standard deviation, you can hardwire absolute "reject" limits. This is actually better in that an initial error won't blow up your detector.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Excellent! One thing though; although we do know the typical behavior, it is possible that the hardware will get switched out, so I feel that an adaptable program would be preferred. $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 8:04
  • 1
    $\begingroup$ Even if it does need to be adaptable, put some EXTREME limits in there anyway. If a hardware glitch gives you 1e280 as a value, or NaN or +Inf, you may want to filter those out regardless. $\endgroup$
    – SPWorley
    Apr 12, 2009 at 8:22
5
$\begingroup$

The definition of what constitutes an abnormal value must scale to the data itself. The classic method of doing this is to calculate the z score of each of the data points and throwing out any values greater than 3 z scores from the average. The z score can be found by taking the difference between the data point and the average and dividing by the standard deviation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How well would this method work for the pathological blue line case? $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 7:45
  • $\begingroup$ The pathological blue line case has a high standard deviation. It would take a significant outlying value to get rejected. $\endgroup$
    – ojblass
    Apr 12, 2009 at 7:56
4
$\begingroup$

I would compute a running median (robust alternative to mean) and a running mad (robust alternative to sd), remove everything that more than 5 mad's away from the median

https://ec.europa.eu/eurostat/documents/1001617/4398385/S4P1-MIRROROUTLIERDETECTION-LIAPIS.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ One thing to keep in mind is the computational complexity of the running median: The naive implementation requires a sort each time a new data point is added. In any case, all previous data points (at least in a certain window) have to be stored. $\endgroup$
    – moi
    Jun 7, 2022 at 0:54
3
$\begingroup$

Another solution is to use the harmonic mean.

Your case is very similar to the example discussed in

http://economistatlarge.com/finance/applied-finance/differences-arithmetic-geometric-harmonic-means

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dude, harmonic mean FTW! People should really take a look into this one! $\endgroup$
    – JohnTortugo
    Oct 20, 2015 at 18:50
1
$\begingroup$

You need to have some idea of expected variation or distribution, if you want to be able to exclude certain (higher) instances of variation as erroneous. For instance, if you can approximate the distribution of the "average times" result to a normal (Gaussian) distribution, then you can do what ojblass suggested and exclude those results that exhibit a variation that is greater than some multiple of the standard deviation (which can be calculated on the fly alongside your running average). If you wanted to exclude results that have a 99.75 (or so) percent chance of being erroneous, exclude those that vary more than 3 standard deviations from the mean. If you only want 95% certainty, exclude those that vary more than 2 standard deviations and so on.

I'm sure a little bit of googling for "standard deviation" or "gaussian distribution" will help you. Of course, this assumes that you expect a normal distribution of results. You might not. In which case, the first step would be to guess at what distribution you expect.

Improve this answer
$\endgroup$
-1
$\begingroup$

Maybe a good method would be to ignore any results that are more than some defined value outside the current running average?

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, but how do you say what this "defined value" is? $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 7:30
  • $\begingroup$ I expect that would come from an examination of the data based on the actual results $\endgroup$
    – 1800 INFORMATION
    Apr 12, 2009 at 7:38
  • $\begingroup$ I really would like to avoid hard-coding something like that in the program $\endgroup$
    – Edward Z. Yang
    Apr 12, 2009 at 7:41
  • $\begingroup$ It could be a configuration parameter? $\endgroup$
    – 1800 INFORMATION
    Apr 12, 2009 at 9:45
-1
$\begingroup$

The naive (and possibly best) answer to the bootstrapping question is "Accept the first N values without filtering." Choose N to be as large as possible while still allowing the setup time to be "short" in your application. In this case, you might consider using the window width (64 samples) for N.

Then I would go with some kind of mean and sigma based filter.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.