Online outlier detection

Question

I want to process automatically-segmented microscopy images to detect faulty images and/or faulty segmentations, as a part of a high-throughput imaging pipeline. There's a host of parameters that can be computed for each raw image and segmentation, and that become "extreme" when the image is defective. For example, a bubble in the image will result in anomalies such as an enormous size in one of the detected "cells", or an anomalously low cell count for the entire field. I am looking for an efficient way to detect these anomalous cases. Ideally, I would prefer a method that has the following properties (roughly in order of desirability):

1. does not require predefined absolute thresholds (although predefined percentages are OK);

2. does not require having all the data in memory, or even having seen all the data; it'd be OK for the method to be adaptive, and update its criteria as it sees more data; (obviously, with some small probability, anomalies may happen before the system has seen enough data, and will be missed, etc.)

3. is parallelizable: e.g. in a first round, many nodes working in parallel produce intermediate candidate anomalies, which then undergo one second round of selection after the first round is complete.

The anomalies I'm looking for are not subtle. They are the kind that are plainly obvious if one looks at a histogram of the data. But the volume of data in question, and the ultimate goal of performing this anomaly detection in real time as the images are being generated, precludes any solution that would require inspection of histograms by a human evaluator.

Thanks!

Answer 1

Have you considered something like a one-class classifier?

You would need a training set of known-good images, which are used to train up a classifier that tries to distinguish between "images like your training set" and everything else. There's a thesis by David Tax that probably has more information than you actually require on the topic, but might be a good place to start.

Other than requiring a training set, it seems like it would meet your requirements:

• Parameters are learned from the data (no ad-hockery here)

• Once you've got the model, there's no need to keep the data in memory.

• Similarly, the trained classifier could be run on as many nodes as you've got.

Depending on your application, you might be able to train up a serviceable classifier once and reuse it for different types of specimens/dyes/stains/florophores/etc. Alternately, you might be able to get users to manually rate some of the first batch of each run--I imagine a human could check at least 5-8 examples/minute with a good interface.

Answer 2

See http://scholar.google.com/scholar?q=stream+outlier+detection

A couple of established methods such as LOF have been adopted to a streaming context. There are also of course methods that update histograms in a streaming way and thus flag obvious one-dimensional outliers. That could actually be sufficient for you?

Answer 3

There are many possible approaches, but it is hard to know what may be best in your situation without more information.

It sounds like, for each image, you receive a feature vector, which is an element of $\mathbb{R}^n$. If that's the case, here are a handful of candidate solutions:

• Store the feature vectors of all prior images, along with their classification, on disk. Periodically (say, once a day) train a learning algorithm on this data, and use the resulting algorithm to classify new images. Disk space is cheap; this solution might be a pragmatic and effective to convert an offline learning algorithm into one that can be used in your online setting.

• Store the feature vectors of a random sample of 1,000 (or 1,000,000) prior images, along with their classification. Periodically train a learning algorithm on this subsample.

  Note that you can efficiently update this subsample in an online fashion using standard tricks. This is only interesting if there is some reason why it is hard to store all of the feature vectors of all prior images (which seems hard to imagine, for me, but who knows).

• For each of the $n$ vectors, keep track of the running average and standard deviation of the non-defective images seen so far. Then, when you receive a new image, if any of its features is at least $c$ standard deviations beyond the mean for that feature, classify it as defective, otherwise classify it as non-defective. You can choose $c$ based upon $n$ and the desired tradeoff between false positives and false negatives.

  In other words, you maintain a $n$-vector $\mu$ of means, and a $n$-vector $\sigma$ of standard deviations, where $\mu_i$ is the mean of the $i$th feature vector and $\sigma_i$ is the standard deviation of that feature. When you receive a new feature vector $x$, you check whether $|x_i - \mu_i| \ge c \sigma_i$ for any $i$. If not, you classify it as non-defective and you update $\mu$ and $\sigma$.

  This approach assumes that each parameter from a non-defective image has a Gaussian distribution, and that the parameters are independent. Those assumptions may be optimistic. There are many more sophisticated variants of this scheme which will eliminate the need for these assumptions or improve performance; this is just a simple example to give you an idea.

In general, you could look at online algorithms and streaming algorithms.

Answer 4

From what I understand from your question, you receive a sequence of vectors in $R^n$ and you'd like to flag the current vector as being an outlier given all the vectors you've seen thus far. (I am assuming that the image parameters are the elements of the vector.)

If the outliers are pretty obvious, a simple trick that would work is the following. Construct a locality sensitive hash function from your vectors. (A simple randomized hash like which side of a set of random hyperplanes the the vector falls on might work. This would yield a boolean vector as the hash value.) Now as you receive vectors, you compute the hash value of the vector and store the hash value (the boolean vector in the case of hyperplanes) and the counts in a dictionary. You also store the total number of vectors seen thus far. At any given time you can flag a given vector as being an outlier if the total number of vectors that collide with it in the hash are less than than a predefined percentage of the total.

You can view this as building a histogram in an incremental fashion. But since the data is not univariate we use the hashing trick to make it behave like it.