Rand index

The Rand index[1] or Rand measure (named after William M. Rand) in statistics, and in particular in data clustering, is a measure of the similarity between two data clusterings. A form of the Rand index may be defined that is adjusted for the chance grouping of elements, this is the adjusted Rand index. From a mathematical standpoint, Rand index is related to the accuracy, but is applicable even when class labels are not used.

Example clusterings for a dataset with the kMeans (left) and Mean shift (right) algorithms. The calculated Adjusted Rand index for these two clusterings is

Rand indexEdit

DefinitionEdit

Given a set of   elements   and two partitions of   to compare,  , a partition of S into r subsets, and  , a partition of S into s subsets, define the following:

  •  , the number of pairs of elements in   that are in the same subset in   and in the same subset in  
  •  , the number of pairs of elements in   that are in different subsets in   and in different subsets in  
  •  , the number of pairs of elements in   that are in the same subset in   and in different subsets in  
  •  , the number of pairs of elements in   that are in different subsets in   and in the same subset in  

The Rand index,  , is:[1][2]

 

Intuitively,   can be considered as the number of agreements between   and   and   as the number of disagreements between   and  .

Since the denominator is the total number of pairs, the Rand index represents the frequency of occurrence of agreements over the total pairs, or the probability that   and   will agree on a randomly chosen pair.

  is calculated as  .


Similarly, one can also view the Rand index as a measure of the percentage of correct decisions made by the algorithm. It can be computed using the following formula:

 
where   is the number of true positives,   is the number of true negatives,   is the number of false positives, and   is the number of false negatives.

PropertiesEdit

The Rand index has a value between 0 and 1, with 0 indicating that the two data clusterings do not agree on any pair of points and 1 indicating that the data clusterings are exactly the same.

In mathematical terms, a, b, c, d are defined as follows:

  •  , where  
  •  , where  
  •  , where  
  •  , where  

for some  

Relationship with classification accuracyEdit

The Rand index can also be viewed through the prism of binary classification accuracy over the pairs of elements in  . The two class labels are "  and   are in the same subset in   and  " and "  and   are in different subsets in   and  ".

In that setting,   is the number of pairs correctly labeled as belonging to the same subset (true positives), and   is the number of pairs correctly labeled as belonging to different subsets (true negatives).

Adjusted Rand indexEdit

The adjusted Rand index is the corrected-for-chance version of the Rand index.[1][2][3] Such a correction for chance establishes a baseline by using the expected similarity of all pair-wise comparisons between clusterings specified by a random model. Traditionally, the Rand Index was corrected using the Permutation Model for clusterings (the number and size of clusters within a clustering are fixed, and all random clusterings are generated by shuffling the elements between the fixed clusters). However, the premises of the permutation model are frequently violated; in many clustering scenarios, either the number of clusters or the size distribution of those clusters vary drastically. For example, consider that in K-means the number of clusters is fixed by the practitioner, but the sizes of those clusters are inferred from the data. Variations of the adjusted Rand Index account for different models of random clusterings.[4]

Though the Rand Index may only yield a value between 0 and +1, the adjusted Rand index can yield negative values if the index is less than the expected index.[5]

The contingency tableEdit

Given a set S of n elements, and two groupings or partitions (e.g. clusterings) of these elements, namely   and  , the overlap between X and Y can be summarized in a contingency table   where each entry   denotes the number of objects in common between   and   :  .

 

DefinitionEdit

The original Adjusted Rand Index using the Permutation Model is

 

where   are values from the contingency table.

See alsoEdit

ReferencesEdit

  1. ^ a b c W. M. Rand (1971). "Objective criteria for the evaluation of clustering methods". Journal of the American Statistical Association. American Statistical Association. 66 (336): 846–850. arXiv:1704.01036. doi:10.2307/2284239. JSTOR 2284239.
  2. ^ a b Lawrence Hubert and Phipps Arabie (1985). "Comparing partitions". Journal of Classification. 2 (1): 193–218. doi:10.1007/BF01908075.
  3. ^ Nguyen Xuan Vinh, Julien Epps and James Bailey (2009). "Information Theoretic Measures for Clustering Comparison: Is a Correction for Chance Necessary?" (PDF). ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning. ACM. pp. 1073–1080.PDF.
  4. ^ Alexander J Gates and Yong-Yeol Ahn (2017). "The Impact of Random Models on Clustering Similarity" (PDF). Journal of Machine Learning Research. 18: 1–28.PDF.
  5. ^ http://i11www.iti.uni-karlsruhe.de/extra/publications/ww-cco-06.pdf

External linksEdit