Wikipedia / Rand index
Wikipedia / Rand index
The Rand index or Rand measure (named after William M. Rand) in statistics, and in particular in data clustering, is a similarity measure between two clusterings. It compares all pairs of elements and counts how often the two clusterings agree: either both place a pair in the same cluster, or both place the pair in different clusters. 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.
The adjusted Rand index (ARI) is a version of the Rand index corrected for the similarity expected by chance. It is commonly used to compare a clustering algorithm's output with a reference clustering, such as known class labels or a ground-truth partition.
Rand index
Definition
Given a set elements and two partitions, a partition of S into r, a partition of S into s subsets, define the following:
that are in the same and in the same
that are in different and in different
that are in the same and in different
that are in different and in the same
, is:
.
Since the denominator is the total number of pairs, the Rand index represents the frequency of occurrence will agree on a randomly chosen pair.
The number of all possible unordered pairs, the binomial coefficient.
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:
is the number of true negatives is the number of false positives is the number of false negatives.
Relationship with classification accuracy
The Rand index can also be viewed through the prism of binary classification".
is the number of pairs correctly labeled as belonging to the same subset (true positives is the number of pairs correctly labeled as belonging to different subsets (true negatives).
Adjusted Rand index
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.
The contingency table
Given a set of elements, and two groupings or partitions (e.g., the overlap between and .
Definition
The original adjusted Rand index using the permutation model is
are values from the contingency table.
See also
Notes
For a different approach which similarly employs permutations for creating counterfactual resamples, see permutation test.
References
External links