56
$\begingroup$

Given two histograms, how do we assess whether they are similar or not?

Is it sufficient to simply look at the two histograms? The simple one to one mapping has the problem that if a histogram is slightly different and slightly shifted then we'll not get the desired result.

Any suggestions?

$\endgroup$
7
  • 6
    $\begingroup$ What does "similar" mean? The chi-squared test and the KS test, for example, test whether two histograms are close to identical. But "similar" might mean "have the same shape," ignoring any differences of location and/or scale. Could you clarify your intent? $\endgroup$
    – whuber
    Feb 21, 2011 at 14:32
  • $\begingroup$ In addition to the $\chi^2$ test, you may want to produce a Bihistogram (itl.nist.gov/div898/handbook/eda/section3/bihistog.htm) From the handbook: "It is a graphical alternative to the two-sample t-test. The bihistogram can be more powerful than the t-test in that all of the distributional features (location, scale, skewness, outliers) are evident on a single plot." $\endgroup$
    – Tavrock
    Nov 7, 2020 at 21:49
  • 1
    $\begingroup$ @just The KS test does not work with tied values, which is what you have with histograms. (I'm unsure what you might mean by a "discrete" histogram.) I was sloppy in my first comment by using "histogram" where I should have written "empirical distribution." See stats.stackexchange.com/a/7410/919 (one of the answers in this thread). $\endgroup$
    – whuber
    Jul 27, 2022 at 16:28
  • 1
    $\begingroup$ @just The left plot is a frequency bar plot. The right plot shows the graph of a (probability) density function, or PDF. Neither is a true histogram, although it would be reasonable to think of the PDF as a kind of "continuous histogram," and in that light I can understand why you might have specified "discrete." $\endgroup$
    – whuber
    Jul 27, 2022 at 16:30
  • 1
    $\begingroup$ Yes, but you get the idea, the discrete histogram is with "bars", and the continuous histogram with all the values in a continuous "function"... $\endgroup$ Jul 27, 2022 at 16:32

5 Answers 5

11
$\begingroup$

A recent paper that may be worth reading is:

Cao, Y. Petzold, L. Accuracy limitations and the measurement of errors in the stochastic simulation of chemically reacting systems, 2006.

Although this paper's focus is on comparing stochastic simulation algorithms, essentially the main idea is how to compare two histogram.

You can access the pdf from the author's webpage.

$\endgroup$
4
  • $\begingroup$ Hi, its nice paper, thanx for giving pdf link.. I'll surely go through this paper.. $\endgroup$
    – Mew 3.4
    Feb 20, 2011 at 3:52
  • 29
    $\begingroup$ Instead of providing a reference it would be good if you'd summarize the main points of the paper. Links die, so in the future your answer could become useless for non-subscribers of this journal (and the vast majority of human population is the non-subscribers). $\endgroup$
    – Tim
    May 8, 2015 at 7:16
  • 2
    $\begingroup$ The link doesn't work ... $\endgroup$ May 11, 2021 at 16:12
  • 1
    $\begingroup$ @kjetilbhalvorsen The link works for me and redirects to this: sciencedirect.com/science/article/pii/… $\endgroup$
    – mkt
    May 11, 2021 at 18:31
61
$\begingroup$

There are plenty of distance measures between two histograms. You can read a good categorization of these measures in:

K. Meshgi, and S. Ishii, “Expanding Histogram of Colors with Gridding to Improve Tracking Accuracy,” in Proc. of MVA’15, Tokyo, Japan, May 2015.

The most popular distance functions are listed here for your convenience:

  • $L_0$ or Hellinger Distance

    $D_{L0} = \sum\limits_{i} h_1(i) \neq h_2(i) $

  • $L_1$, Manhattan, or City Block Distance

    $D_{L1} = \sum_{i}\lvert h_1(i) - h_2(i) \rvert $

  • $L=2$ or Euclidean Distance

    $D_{L2} = \sqrt{\sum_{i}\left( h_1(i) - h_2(i) \right) ^2 }$

  • L$_{\infty}$ or Chybyshev Distance

    $D_{L\infty} = \max_{i}\lvert h_1(i) - h_2(i) \rvert $

  • L$_p$ or Fractional Distance (part of Minkowski distance family)

    $D_{Lp} = \left(\sum\limits_{i}\lvert h_1(i) - h_2(i) \rvert ^p \right)^{1/p}$ and $0<p<1$

  • Histogram Intersection

    $D_{\cap} = 1 - \frac{\sum_{i} \left(\min(h_1(i),h_2(i) \right)}{\min\left(\vert h_1(i)\vert,\vert h_2(i) \vert \right)}$

  • Cosine Distance

    $D_{CO} = 1 - \sum_i h_1(i)h2_(i)$

  • Canberra Distance

    $D_{CB} = \sum_i \frac{\lvert h_1(i)-h_2(i) \rvert}{\min\left( \lvert h_1(i)\rvert,\lvert h_2(i)\rvert \right)}$

  • Pearson's Correlation Coefficient

    $ D_{CR} = \frac{\sum_i \left(h_1(i)- \frac{1}{n} \right)\left(h_2(i)- \frac{1}{n} \right)}{\sqrt{\sum_i \left(h_1(i)- \frac{1}{n} \right)^2\sum_i \left(h_2(i)- \frac{1}{n} \right)^2}} $

  • Kolmogorov-Smirnov Divergance

    $ D_{KS} = \max_{i}\lvert h_1(i) - h_2(i) \rvert $

  • Match Distance

    $D_{MA} = \sum\limits_{i}\lvert h_1(i) - h_2(i) \rvert $

  • Cramer-von Mises Distance

    $D_{CM} = \sum\limits_{i}\left( h_1(i) - h_2(i) \right)^2$

  • $\chi^2$ Statistics

    $D_{\chi^2} = \sum_i \frac{\left(h_1(i) - h_2(i)\right)^2}{h_1(i) + h_2(i)}$

  • Bhattacharyya Distance

    $ D_{BH} = \sqrt{1-\sum_i \sqrt{h_1(i)h_2(i)}} $ & hellinger

  • Squared Chord

    $ D_{SC} = \sum_i\left(\sqrt{h_1(i)}-\sqrt{h_2(i)}\right)^2 $

  • Kullback-Liebler Divergance

    $D_{KL} = \sum_i h_1(i)\log\frac{h_1(i)}{m(i)}$

  • Jefferey Divergence

    $D_{JD} = \sum_i \left(h_1(i)\log\frac{h_1(i)}{m(i)}+h_2(i)\log\frac{h_2(i)}{m(i)}\right)$

  • Earth Mover's Distance (this is the first member of Transportation distances that embed binning information $A$ into the distance, for more information please refer to the above mentioned paper or Wikipedia entry.

    $ D_{EM} = \frac{\min_{f_{ij}}\sum_{i,j}f_{ij}A_{ij}}{sum_{i,j}f_{ij}}$
    $ \sum_j f_{ij} \leq h_1(i) , \sum_j f_{ij} \leq h_2(j) , \sum_{i,j} f_{ij} = \min\left( \sum_i h_1(i) \sum_j h_2(j) \right) $ and $f_{ij}$ represents the flow from $i$ to $j$

  • Quadratic Distance

    $D_{QU} = \sqrt{\sum_{i,j} A_{ij}\left(h_1(i) - h_2(j)\right)^2}$

  • Quadratic-Chi Distance

    $D_{QC} = \sqrt{\sum_{i,j} A_{ij}\left(\frac{h_1(i) - h_2(i)}{\left(\sum_c A_{ci}\left(h_1(c)+h_2(c)\right)\right)^m}\right)\left(\frac{h_1(j) - h_2(j)}{\left(\sum_c A_{cj}\left(h_1(c)+h_2(c)\right)\right)^m}\right)}$ and $\frac{0}{0} \equiv 0$

A Matlab implementation of some of these distances is available from my GitHub repository. Also, you can search for people like Yossi Rubner, Ofir Pele, Marco Cuturi, and Haibin Ling for more state-of-the-art distances.

Update: Alternative explanation for the distances appears here and there in the literature, so I list them here for sake of completeness.

  • Canberra distance (another version)

    $D_{CB}=\sum_i \frac{|h_1(i)-h_2(i)|}{|h_1(i)|+|h_2(i)|}$

  • Bray-Curtis Dissimilarity, Sorensen Distance (since the sum of histograms are equal to one, it equals to $D_{L0}$)

    $D_{BC} = 1 - \frac{2 \sum_i h_1(i) = h_2(i)}{\sum_i h_1(i) + \sum_i h_2(i)}$

  • Jaccard Distance (i.e. intersection over union, another version)

    $D_{IOU} = 1 - \frac{\sum_i \min(h_1(i),h_2(i))}{\sum_i \max(h_1(i),h_2(i))}$

$\endgroup$
8
  • $\begingroup$ Welcome to our site! Thank you for this contribution. $\endgroup$
    – whuber
    May 8, 2015 at 14:26
  • $\begingroup$ Here is the paper link: mva-org.jp/Proceedings/2015USB/papers/14-15.pdf $\endgroup$
    – neves
    Apr 16, 2017 at 17:23
  • $\begingroup$ Thanks, a list is wonderful, while it doesn't allow to create a comparison operator for histogram, e.g. to say that hist1 < hist2 $\endgroup$
    – olha
    Aug 13, 2019 at 17:46
  • 1
    $\begingroup$ Your KS divergence is implemented in code as $$D_{KS} = max_{i}\lvert \sum_i h_1(i) - \sum_i h_2(i) \rvert$$ This seems inconsistent with the equation you have above. Am I missing something? $\endgroup$ Jan 3, 2020 at 4:33
  • 2
    $\begingroup$ I guess it is a mistake in my code. I will look into this. Thank you for pointing it out $\endgroup$ Jan 4, 2020 at 21:39
30
$\begingroup$

The standard answer to this question is the chi-squared test. The KS test is for unbinned data, not binned data. (If you have the unbinned data, then by all means use a KS-style test, but if you only have the histogram, the KS test is not appropriate.)

$\endgroup$
4
  • 1
    $\begingroup$ You are correct that the KS test is not appropriate for histograms when it is understood as a hypothesis test about the distribution of the underlying data, but I see no reason why the KS statistic wouldn't work well as a measure of sameness of any two histograms. $\endgroup$
    – whuber
    Feb 21, 2011 at 14:34
  • 2
    $\begingroup$ An explanation of why the Kolmogorov-Smirnov test is not appropriate with binned data would be useful. $\endgroup$
    – naught101
    Aug 7, 2012 at 6:56
  • 1
    $\begingroup$ This may not be as useful in image processing as in statistical fit assessment. Often in image processing, a histogram of data is used as a descriptor for a region of an image, and the goal is for a distance between histograms to reflect the distance between image patches. Little, or possibly nothing at all, may be known about the general population statistics of the underlying image data used to get the histogram. For example, the underlying population statistics when using histograms of oriented gradients would differ considerably based on the actual content of the images. $\endgroup$
    – ely
    Aug 17, 2015 at 19:33
  • 2
    $\begingroup$ naught101's question was answered by Stochtastic: stats.stackexchange.com/a/108523/37373 $\endgroup$
    – Lapis
    Aug 22, 2015 at 10:33
11
$\begingroup$

You're looking for the Kolmogorov-Smirnov test. Don't forget to divide the bar heights by the sum of all observations of each histogram.

Note that the KS-test is also reporting a difference if e.g. the means of the distributions are shifted relative to one another. If translation of the histogram along the x-axis is not meaningful in your application, you may want to subtract the mean from each histogram first.

$\endgroup$
1
  • 3
    $\begingroup$ Subtracting the mean changes the null distribution of the KS statistic. @David Wright raises a valid objection to the application of the KS test to histograms anyway. $\endgroup$
    – whuber
    Feb 21, 2011 at 14:36
10
$\begingroup$

As David's answer points out, the chi-squared test is necessary for binned data as the KS test assumes continuous distributions. Regarding why the KS test is inappropriate (naught101's comment), there has been some discussion of the issue in the applied statistics literature that is worth raising here.

An amusing exchange began with the claim (García-Berthou and Alcaraz, 2004) that one third of Nature papers contain statistical errors. However, a subsequent paper (Jeng, 2006, "Error in statistical tests of error in statistical tests" -- perhaps my all-time favorite paper title) showed that Garcia-Berthou and Alcaraz (2005) used KS tests on discrete data, leading to their reporting inaccurate p-values in their meta-study. The Jeng (2006) paper provides a nice discussion of the issue, even showing that one can modify the KS test to work for discrete data. In this specific case, the distinction boils down to the difference between a uniform distribution of the trailing digit on [0,9], $$ P(x) = \frac{1}{9},\ (0 \leq x \leq 9) $$ (in the incorrect KS test) and a comb distribution of delta functions, $$ P(x) = \frac{1}{10}\sum_{j=0}^9 \delta(x-j) $$ (in the correct, modified form). As a result of the original error, Garcia-Berthou and Alcaraz (2004) incorrectly rejected the null, while the chi-squared and modified KS test do not. In any case, the chi-squared test is the standard choice in this scenario, even if KS can be modified to work here.

$\endgroup$

Your Answer

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

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