Rand index

Given a set of $n$ elements $S\; =\; \backslash \{o\_1,\; \backslash ldots,\; o\_n\backslash \}$ and two partitions of $S$ to compare, $X\; =\; \backslash \{X\_1,\; \backslash ldots,\; X\_r\backslash \}$, a partition of S into r subsets, and $Y\; =\; \backslash \{Y\_1,\; \backslash ldots,\; Y\_s\backslash \}$, a partition of S into s subsets, define the following:

• $a$, the number of pairs of elements in $S$ that are in the same subset in $X$ and in the same subset in $Y$
• $b$, the number of pairs of elements in $S$ that are in different subsets in $X$ and in different subsets in $Y$
• $c$, the number of pairs of elements in $S$ that are in the same subset in $X$ and in different subsets in $Y$
• $d$, the number of pairs of elements in $S$ that are in different subsets in $X$ and in the same subset in $Y$

The Rand index, $R$, is:{{Cite journal

| doi = 10.1007/BF01908075

| author = Lawrence Hubert and Phipps Arabie

| title = Comparing partitions

| journal = Journal of Classification

| volume = 2

|issue=1

| pages = 193–218

| year = 1985

}}

:$R\; =\; \backslash frac\{a+b\}\{a+b+c+d\}\; =\; \backslash frac\{a+b\}\{\{n\; \backslash choose\; 2\; \}\}$

Intuitively, $a\; +\; b$ can be considered as the number of agreements between $X$ and $Y$ and $c\; +\; d$ as the number of disagreements between $X$ and $Y$.

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 $X$ and $Y$

will agree on a randomly chosen pair.

$\{n\; \backslash choose\; 2\; \}$ is calculated as $n(n-1)/2$.

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:

::$$

RI = \frac {TP + TN} {TP + FP + FN + TN}

:where $TP$ is the number of true positives, $TN$ is the number of true negatives, $FP$ is the number of false positives, and $FN$ is the number of false negatives.

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:

• $a\; =\; |S^\{*\}|$, where $S^\{*\}\; =\; \backslash \{\; (o\_\{i\},\; o\_\{j\})\; \backslash mid\; o\_\{i\},\; o\_\{j\}\; \backslash in\; X\_\{k\},\; o\_\{i\},\; o\_\{j\}\; \backslash in\; Y\_\{l\}\backslash \}$
• $b\; =\; |S^\{*\}|$, where $S^\{*\}\; =\; \backslash \{\; (o\_\{i\},\; o\_\{j\})\; \backslash mid\; o\_\{i\}\; \backslash in\; X\_\{k\_\{1\}\},\; o\_\{j\}\; \backslash in\; X\_\{k\_\{2\}\},\; o\_\{i\}\; \backslash in\; Y\_\{l\_\{1\}\},\; o\_\{j\}\; \backslash in\; Y\_\{l\_\{2\}\}\backslash \}$
• $c\; =\; |S^\{*\}|$, where $S^\{*\}\; =\; \backslash \{\; (o\_\{i\},\; o\_\{j\})\; \backslash mid\; o\_\{i\},\; o\_\{j\}\; \backslash in\; X\_\{k\},\; o\_\{i\}\; \backslash in\; Y\_\{l\_\{1\}\},\; o\_\{j\}\; \backslash in\; Y\_\{l\_\{2\}\}\backslash \}$
• $d\; =\; |S^\{*\}|$, where $S^\{*\}\; =\; \backslash \{\; (o\_\{i\},\; o\_\{j\})\; \backslash mid\; o\_\{i\}\; \backslash in\; X\_\{k\_\{1\}\},\; o\_\{j\}\; \backslash in\; X\_\{k\_\{2\}\},\; o\_\{i\},\; o\_\{j\}\; \backslash in\; Y\_\{l\}\backslash \}$

for some $1\; \backslash leq\; i,j\; \backslash leq\; n,\; i\; \backslash neq\; j,\; 1\; \backslash leq\; k,\; k\_\{1\},\; k\_\{2\}\; \backslash leq\; r,\; k\_\{1\}\; \backslash neq\; k\_\{2\},\; 1\; \backslash leq\; l,\; l\_\{1\},l\_\{2\}\; \backslash leq\; s,\; l\_\{1\}\; \backslash neq\; l\_\{2\}$

The Rand index can also be viewed through the prism of binary classification accuracy over the pairs of elements in $S$. The two class labels are "$o\_\{i\}$ and $o\_\{j\}$ are in the same subset in $X$ and $Y$" and "$o\_\{i\}$ and $o\_\{j\}$ are in different subsets in $X$ and $Y$".

In that setting, $a$ is the number of pairs correctly labeled as belonging to the same subset (true positives), and $b$ 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.{{Cite conference

| author = Nguyen Xuan Vinh, Julien Epps and James Bailey

| title = Information Theoretic Measures for Clustering Comparison: Is a Correction for Chance Necessary?

| book-title = ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning

| year = 2009

| pages = 1073–1080

| url=http://www.jmlr.org/papers/volume11/vinh10a/vinh10a.pdf

| publisher = ACM

}}[http://www.ima.umn.edu/~iwen/REU/10.pdf PDF].

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)For a different approach which similarly employs permutations for creating counterfactual resamples, see permutation test. 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.{{Cite journal |author=Alexander J Gates and Yong-Yeol Ahn |year=2017 |title=The Impact of Random Models on Clustering Similarity |url=http://www.jmlr.org/papers/volume18/17-039/17-039.pdf |journal=Journal of Machine Learning Research |volume=18 |pages=1–28|arxiv=1701.06508 }}

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.{{Cite web |title=Comparing Clusterings - An Overview |url=https://i11www.iti.kit.edu/extra/publications/ww-cco-06.pdf}}

Given a set {{mvar|S}} of {{mvar|n}} elements, and two groupings or partitions (e.g. clusterings) of these elements, namely $X\; =\; \backslash \{\; X\_1,\; X\_2,\; \backslash ldots\; ,\; X\_r\; \backslash \}$ and $Y\; =\; \backslash \{\; Y\_1,\; Y\_2,\; \backslash ldots\; ,\; Y\_s\; \backslash \}$, the overlap between {{mvar|X}} and {{mvar|Y}} can be summarized in a contingency table $\backslash left[n\_\{ij\}\backslash right]$ where each entry $n\_\{ij\}$ denotes the number of objects in common between $X\_i$ and $Y\_j$ : $n\_\{ij\}=|X\_i\; \backslash cap\; Y\_j|$.

: $\backslash begin\{array\}\{c|cccc|c\}$

{{} \atop X}\!\diagdown\!^Y &

Y_1&

Y_2&

\cdots&

Y_s&

\text{sums}

\\

\hline

X_1&

n_{11}&

n_{12}&

\cdots&

n_{1s}&

a_1

\\

X_2&

n_{21}&

n_{22}&

\cdots&

n_{2s}&

a_2

\\

\vdots&

\vdots&

\vdots&

\ddots&

\vdots&

\vdots

\\

X_r&

n_{r1}&

n_{r2}&

\cdots&

n_{rs}&

a_r

\\

\hline

\text{sums}&

b_1&

b_2&

\cdots&

b_s&

\end{array}

The original Adjusted Rand Index using the Permutation Model is

:$ARI\; =\; \backslash frac\{\; \backslash left.\; \backslash sum\_\{ij\}\; \backslash binom\{n\_\{ij\}\}\{2\}\; -\; \backslash left[\backslash sum\_i\; \backslash binom\{a\_i\}\{2\}\; \backslash sum\_j\; \backslash binom\{b\_j\}\{2\}\backslash right]\; \backslash right/\; \backslash binom\{n\}\{2\}\; \}\{\; \backslash left.\; \backslash frac\{1\}\{2\}\; \backslash left[\backslash sum\_i\; \backslash binom\{a\_i\}\{2\}\; +\; \backslash sum\_j\; \backslash binom\{b\_j\}\{2\}\backslash right]\; -\; \backslash left[\backslash sum\_i\; \backslash binom\{a\_i\}\{2\}\; \backslash sum\_j\; \backslash binom\{b\_j\}\{2\}\backslash right]\; \backslash right/\; \backslash binom\{n\}\{2\}\; \}$

where $n\_\{ij\},\; a\_i,\; b\_j$ are values from the contingency table.

• Simple matching coefficient

{{Reflist}}

• [https://github.com/bjoern-andres/partition-comparison C++ implementation with MATLAB mex files]

{{Machine learning evaluation metrics}}

Category:Summary statistics for contingency tables

Category:Clustering criteria