Rand index

Measure of similarity between two data clusterings

The Rand index 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. The Rand index is the accuracy of determining if a link belongs within a cluster or not.

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).

The adjusted Rand index is the corrected for chance version of the Rand index. 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. 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.

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 : .