In the literature of community detection there are various measures bases on principles from information theory (Normalized mutual information, variation of information) that are used to compare partitions. I wonder why KL-divergence is not popular for comparison while it compares two probabilistic distributions similar to clusters.


The OP has phrased their question in terms of 'popularity.' This may not be the right way to think about the use of KL divergence wrt clustering. In point of fact, KL metrics are used in information-theoretic and complexity based cluster algorithms but evaluating the 'popularity' of such routines would be difficult.

Permutation distribution clustering is one such routine. PDC is described in several papers. Here is a link to the PDC R module which contains a description of the use of KL divergence ... https://cran.r-project.org/web/packages/pdc/pdc.pdf

Then there's Eamonn Keogh's SAX and iSAX routines which are similar to PDC but may well be more 'popular' ... http://www.cs.ucr.edu/~eamonn/SAX.htm


KL divergence assumes that you know which cluster is which label. But what if the number of clusters and classes is not the same? A good clustering may need to split a class into two parts, if the data has such a structure. Plus, KL is asymmetric.

NMI is closely related, but as it compares every cluster to every label, you don't have the problem of mapping clusters to classes.

  • $\begingroup$ What if we know the ground truth and use KL to compare estimated structure with ground truth. Moreover we can take symmetric version KL(a,b)/2+KL(b,a)/2 ? $\endgroup$ – Karen Mkhitaryan Jan 18 '18 at 8:08
  • $\begingroup$ Ground truth is "iris setosa" etc. KMeans labels them 1,2,3 - what do you do? $\endgroup$ – Anony-Mousse Jan 18 '18 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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