7
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ It strongly depends on how you define the outlier, or how it differs from the rest. Is it different because of the distribution, the value of its values or is it something different? $\endgroup$ Commented Jul 22, 2022 at 14:45
  • $\begingroup$ @just_learning I don't understand the question, why don't you just pool all the data together and use a box plot? $\endgroup$
    – deps_stats
    Commented Jul 22, 2022 at 15:02
  • 4
    $\begingroup$ @deps_stats: I think OP wants to detect abnormal histograms among a sample of 20 different histograms, not abnormal data points. $\endgroup$ Commented Jul 22, 2022 at 15:13
  • 1
    $\begingroup$ got it! Two more questions, are all histograms defined over the same support? and, are the bin widths equal in all histograms? Those might be critical $\endgroup$
    – deps_stats
    Commented Jul 22, 2022 at 15:26
  • 1
    $\begingroup$ What is the relevance of the histograms? You can compute distances between empirical distributions (in terms of the Komogorov-Smirnov statistics) without binning the distributions in a histogram. Many CV posts explain that binning a continuous distribution means loss of power. $\endgroup$
    – dipetkov
    Commented Jul 23, 2022 at 17:13

1 Answer 1

7
$\begingroup$

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?

histograms

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.

$\endgroup$
17
  • 1
    $\begingroup$ You can use the test statistic of the two-sample K-S test as a distance measure between each pair of histograms, instead of the squared difference in bin counts I used above or the EMD. Then you can again use DBSCAN or similar. $\endgroup$ Commented Jul 23, 2022 at 8:44
  • 1
    $\begingroup$ You shouldn't use the Kolmogorov-Smirnov statistics as a distance measure between histograms as K-S makes sense for continuous distributions only. And histograms are definitely not continuous. $\endgroup$
    – dipetkov
    Commented Jul 23, 2022 at 17:50
  • 1
    $\begingroup$ @dipetkov: good point. I should have written that you can use the K-S statistic for a measure of distance of the underlying data, before binning them into histograms, analogously to the EMD. $\endgroup$ Commented Jul 23, 2022 at 17:51
  • 1
    $\begingroup$ This is exactly what's bothering me with this question -- the OP hasn't said why the histograms in the first place. Is there a good reason to bin the samples and then compute distances? Maybe the OP will explain. $\endgroup$
    – dipetkov
    Commented Jul 23, 2022 at 17:54
  • 1
    $\begingroup$ If you have access to the original data (before they were binned into histograms), you could calculate distances between those, as @dipetkov and I are suggesting. Taking means per image may also be possible. The distribution/histogram approach would detect a different kind of "outlier" (e.g., same mean as other images, but different distribution). What works best will depend on your context. $\endgroup$ Commented Jul 24, 2022 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.