# Detect if an incoming value in streaming data is an outlier

I am reading a sensor that gives data. Sometimes some data is false. I can store some samples before and I would like to detect a glitch on the fly.

Process :

• Values are integers (distances in centimeters)
• I get distances from a sensor (~ 200Hz)
• The distance read is not always correct, and have outliers
• There can be up to 10% outliers
• Typical values are [100;2000]
• The standard deviation is about 2
• The process is dynamic up to 150/s
• The measurements follow a gaussian curve (if static)
• Typical outliers are [0;20] U [950;1200]

I need to filter the measurements on the fly to be sure to get at least 100Hz.

I first thought of a Kalman filter, it would be working well if I didnt have the outliers. Indeed, there is no correlation between those and the true value (Communication problems/or bug). The outliers do not carry data at all.

I would like to filter outliers before passing data into the Kalman filter and get more precise values.

Is there a simple way to implement it on a microcontroller? I do not need the solution done in C, I can implement it. What I need is inspiration! :D

• Possibly worth looking at outliers, or time-series, or control-chart but you'll need to explain in more detail for this question to be answered. Nov 26, 2015 at 16:16
• "Is there a simple way to implement it on a microcontroller?": are you really looking for a statistical answer, or a electronics implementation? Nov 28, 2015 at 17:12
• I can implement it myself, I am sure the algorithms exists but I do not know where to look. The aim is to implement it anyway. Nov 28, 2015 at 17:59
• Please edit your post so that people can give you an answer. Nov 28, 2015 at 18:32
• I understand you would like to get rid of the outliers then apply a kalman filter. Your question is specific, however you are not specifying your final goal (bigger picture). Sometimes things can be worked around depending on the task. Dec 18, 2015 at 2:33

## 2 Answers

I believe this article is quite similar to what you are trying to accomplish. They are able to reconstruct the signal without removing the outliers before it is transmitted. You might not have to follow the entire approach.

Here's one idea: Think compression. What doesn't compress well is a possible outlier candidate (although not necessarily). There are many compression algorithms out there. I would look into compressed sensing and random projections, these methods are fast. If the 'buffer' doesn't compress well that means it contains an outlier. For "Doesn't compress well" you require a measurement relative to a near optimal compression. For this you need to compute some stats over large amounts of data.

Random projections should be easy to implement, although don't solve your problem entirely, you still have to find the outliers. Plenty of methods, one of the most popular one is LOF. I believe it is possible to implent it as an online method as well. This one is specifically designed for streaming data.

• Thanks for thoses methods, I will implement it later since I finally did a simple prediction on the value, then compare the incoming value with the predicted one. Dec 19, 2015 at 9:37

An outlier is a statistical term for any data value that seems to be out of place with respect to the rest of the data. Formally, given user-defined parameters p and D, and a distance function F, an object O in a dataset T is said to be a distance-based outlier if at least fraction p of the objects in T lie greater than distance D from O.

I would recommend that you check out the following paper by Bay and Schwabacher: http://stephenbay.net/papers/outliers.kdd03.pdf

Moreover, here is a nice compiled list of some additional papers that might be of interest to you: http://www.cs.ubc.ca/nest/dbsl/outliers.html