Anomaly detection: what algorithm to use?

Question

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.

Any advice is highly appreciated.

[Edit] 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.

Answer 1

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.

Answer 2

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.