# Anomaly detection: what algorithm to use?

Context: I'm developing a system that analyzes clinical data to filter out implausible data that might be typos.

What I did so far:

To quantify the plausibility, my attempt so far was to normalize the data and then compute a plausibility value for point p based on its distance to known data points in set D (= the training set):

$$\text{plausibility}(p)=\sum_{q\in D}\text{Gauss}(\text{distance}(p,q))$$

With that quantification, I can then select a threshold that separates the plausible data from the implausible data. I'm using python/numpy.

My problems:

1. This algorithm cannot detect independent dimensions. Ideally, I could put anything I know about the record into the algorithm and let it find out by itself that dimension X does not influence the plausibility of the record.
2. The algorithm doesn't really work for discrete values like booleans or select inputs. They could be mapped on continuous values, but it is counter-intuitive that Select 1 is closer to Select 2 than to Select 3.

Question:

What sort of algorithms should I look into for this task? There seems to be a ton of options including nearest neighbour based, clustering based and statistical approaches. Also, I have trouble finding papers that deal with anomaly detection of this complexity.

 Example:

Suppose the data consisted of the Height of a Person, Weight of a Person and Timestamp - so it's 3D-Data. Weight and Height are correlated, but the timestamp is completely independent. If I just consider the euclidean distances, I would have to choose a small threshold to fit most of my cross validation data. Ideally, the algorithm would just ignore the timestamp dimension, because it is irrelevant to determine whether a record is plausible, because the timestamp does not correlate with the other dimensions in any way. Any timestamp is plausible.

On the other hand, one could make up examples where the timestamp does matter. For example it could be that value Y for feature X is plausible when measured before a certain date, but not after a certain date.

• Please see my response to stats.stackexchange.com/questions/97946/changepoints-in-r as it treats this vexing ( to some ! ) question. May 16, 2014 at 14:19
• Would stats.stackexchange.com/questions/213 be the sort of thing you are looking for?
– whuber
May 16, 2014 at 14:35
• I doubt you can make this work for booleans. May 16, 2014 at 14:54
• @whuber I'm not sure, it doesn't seem to cover how irrelevant dimensions can be ignored. May 16, 2014 at 16:09
• By the way, I'm also struggling to find a formalization for the approach I described. If I knew the formal term, it would also help me with my research. Maybe there is a variation to this algorithm that addresses at least the independent/irrelevant dimension issue. May 16, 2014 at 16:12

A typical formulation of Anomaly Detection is to find the mean and variance for each of $$m$$ features of non anomalous data and if $$x$$ is a vector of those features having components $$x_i$$ then define the probability $$p(x)$$ of a combination of features as

$$p(x) = \prod_{i=1}^m{p(x_i;\mu_i,\sigma_i^2})$$

where each $$x_i$$ is gaussian distributed: $$x_i \sim \mathcal{N(\mu_i,\sigma_i^2)}$$

an anomaly occurs whenever $$p(x) < \epsilon$$

The distribution of each $$x_i$$ does not need to actually be normal, but it is better if it is at least normal-like. But the features you use are arbitrary; they can be taken directly from the raw data or computed, so for example if you think that a feature $$x_i$$ is better modeled using $$log$$ then set the feature to $$log(x_i)$$ rather than $$x_i$$.

This appears to be very similar to what you are doing already if you take $$q = \mu$$.

### Determining $$\epsilon$$

The algorithm is fit to negative examples (non-anomalies). But $$\epsilon$$ is determined from the cross-validation set, and is typically selected as the value that provides the best $$F1$$ score

$$F1 = {2*Precision*Recall\over Precision + Recall}$$

But to compute F1 you need to know what is anomalous and what is not; that is true positives are when the system predicts an anomaly and it actually is an anomaly, false positives are predicted anomalies that actually aren't and so on. So unless you have that, then you may have to fall back to guesswork.

### The problem of correlated features

The above has a drawback though if the features are correlated. If they are then the above computation can fail to flag something as anomalous that actually is. A fix for this is using the multivariate gaussian for $$m$$ features where $$\Sigma$$ is the covariance matrix.

$$p(x)= {1\over (2\pi)^{m\over 2}(\det\Sigma)^{1/2}}e^{-{1\over2}(x-\mu)^T\Sigma^{-1}(x - \mu)}$$

Same thing goes for finding $$\epsilon$$ and this approach also has a drawback which is you must calculate the inverse of $$\Sigma$$. So there must be at least as many samples as features and if the number of features is large the process will be computationally intensive, and you must guard agains linearly dependent features. Keep those caveats in mind, but it appears for you to not be a problem.

• I have tried this approach already, including the multivariate gaussian distribution. Indeed, unrelated features are not much of a problem with this approach. What I found was that this approach is not suitable for complex models. For example, if I had a 2D dataset with features F1, F2 where it happens to be the case that roughly F2 = F1^3, the multivariate gaussian distribution will only draw an ellipse around the data and model the data very roughly. That's why I went for the approach described in the question (where there's not one q but many qs). May 21, 2014 at 7:10
• So, is there a way to take the multivariate gaussian approach and apply it to capture more complex data models? For example, could mixture models help me in this case? I've read a bit about those in my research, but didn't fully understand how to apply them yet. May 21, 2014 at 7:18
• @Georg Hmm I wonder if your problem is not a problem of complex models, but complex data and too simplistic models. Or in other words under-fitting. In the case above, what happens if instead of using $(F1,F2)$ you use $(F1,F2^{1/3})$? The features can be either taken from the data or computed. May 21, 2014 at 7:44
• Yes, underfitting is what I mean. And yes, that would work, but I want to have the algorithm detect that automatically. I can't manually modify the features, it should work for any case. May 21, 2014 at 7:51
• Here's an example: The two plots display data for height (x axis) and weight (y axis) (Sorry for the German captions ;) ). The first plot shows the result of the multivariate gaussian approach, the second of the approach described in the question. In both cases, the threshold was chosen such that 97% of the CV data is considered plausible. The second approach is able to better capture the complexity of the data. 1: dl.dropboxusercontent.com/u/26034024/anomaly/gauss.png 2: dl.dropboxusercontent.com/u/26034024/anomaly/distance.png May 21, 2014 at 8:01

I almost finished the project where I needed to solve these problems and I would like to share my solution, in case anyone has the same problems.

First of all, the approach I described is very similar to a Kernel Density Estimation. So, that was good to know for research...

Independent Features

Independent features can be filtered out by measuring its Correlation Coefficient. I compared all features by pair and measured the correlation. Then, I took the maximum absolute correlation coefficient of each feature as the scaling factor. That way, features that do not correlate with any other are multiplied by a value close to 0 and thus their effect on the Euclidean distance $||x_1 - x_2||$ (a.k.a. $distance(x_1, x_2)$) is negligible.

Be warned: the correlation coefficient can only measure linear correlations. See the linked wiki page for details. If the correlation in the data can be approximated linearly, this works fine. If not, you should have a look at the last page of this paper and see if you can use their measurement of correlation to come up with a scaling factor.

Discrete values

I used the described algorithm only for continuos values. Discrete values were used to filter the training set. So if I have the height and weight of a person and I know that she's female, I will only look at samples from other females to check for an anomaly.