Outlier/anomaly detection on histograms

Question

So, the idea is that I have many histograms, each one representing results for something. So, I have histogram_1 for object_1, histogram_2 for object_2,...,histogram_20 for object_20. How can throw out an outlier histogram? I mean, I am searching for an entirely outlier histogram here in comparison to the mainstream of the other histograms, not the outliers number inside a histogram.

Answer 1

Outlier or anomaly detection methods always rely on some notion of distance between the "data points" to be subjected to the detection algorithm. So your first step needs to be to decide on a distance metric between your "data points" - which in your case are your histograms.

There are various ways of doing this. If your histograms all contain the same number of points, and all have the same breaks, you can simply take the average of the squared difference in bin counts. If the breaks are the same, but the counts differ, you can normalize first. Alternatively, you can use the Earth Mover's Distance, which is a general distance between distributions - you can estimate this even on the raw data, before binning into histograms.

Once you have a distance matrix between your histograms, one way forward would be to cluster your histograms, e.g., with a DBSCAN method, which explicitly allows for treating some data points (i.e., histograms) as "noise". You would need to fiddle around with the tuning parameters until you get results you are comfortable with. They will depend on the bumpiness and bin counts of your histograms.

As an example, here are 20 histograms, which one is the outlier?

Our approach correctly identifies the one at the bottom right as "noise", i.e., as an outlier.

R code:

library(dbscan)

set.seed(1)
n_obs <- 2e3
sims <- cbind(replicate(19,runif(n_obs)),rbeta(n_obs,2,2))
histograms <- matrix(NA,nrow=20,ncol=10)
opar <- par(mfrow=c(4,5),las=1,mai=c(.3,.3,0,0))
for ( ii in 1:20 ) {
    histograms[ii,] <- hist(sims[,ii],xlab="",ylab="",
        breaks=seq(0,1,by=0.1),main="")$counts
}

distances <- matrix(NA,20,20)
for ( xx in 1:20 ) {
    for ( yy in 1:20 ) {
        distances[xx,yy] <- mean((histograms[xx,]-histograms[yy,])^2)
    }
}

clustering <- dbscan(distances,eps=10000,minPts=2)
clustering$cluster

Alternatively, since you have no more than 20 histograms, you could use an "inter-ocular trauma test for significance". Something like that might be a good idea for calibrating the clustering-based approach above, in any case.