Rand index

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. From a mathematical standpoint, Rand index is related to the accuracy, but is applicable even when class labels are not used.

Rand index

Definition

Given a set of $n$ elements $S=\{o_{1},\ldots ,o_{n}\}$ and two partitions of $S$ to compare, $X=\{X_{1},\ldots ,X_{r}\}$, a partition of S into r subsets, and $Y=\{Y_{1},\ldots ,Y_{s}\}$, a partition of S into s subsets, define the following:

• $a$, the number of pairs of elements in $S$ that are in the same set in $X$ and in the same set in $Y$

• $b$, the number of pairs of elements in $S$ that are in different sets in $X$ and in different sets in $Y$

• $c$, the number of pairs of elements in $S$ that are in the same set in $X$ and in different sets in $Y$

• $d$, the number of pairs of elements in $S$ that are in different sets in $X$ and in the same set in $Y$

The Rand index, $R$, is:

$R={\frac {a+b}{a+b+c+d}}={\frac {a+b}{n \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$.

Properties

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

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

• $a=|S^{*}|$, where $S^{*}=\{(o_{i},o_{j})|o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}$

• $b=|S^{*}|$, where $S^{*}=\{(o_{i},o_{j})|o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}$

• $c=|S^{*}|$, where $S^{*}=\{(o_{i},o_{j})|o_{i},o_{j}\in X_{k},o_{i}\in Y_{l_{1}},o_{j}\in Y_{l_{2}}\}$

• $d=|S^{*}|$, where $S^{*}=\{(o_{i},o_{j})|o_{i}\in X_{k_{1}},o_{j}\in X_{k_{2}},o_{i},o_{j}\in Y_{l}\}$

for some $1\leq i,j\leq n,i\neq j,1\leq k,k_{1},k_{2}\leq r,k_{1}\neq k_{2},1\leq l,l_{1},l_{2}\leq s,l_{1}\neq l_{2}$

Adjusted Rand index

The adjusted Rand index is the corrected-for-chance version of the Rand index. 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 $S$ of $n$ elements, and two groupings (e.g. clusterings) of these points, namely $X=\{X_{1},X_{2},\ldots ,X_{r}\}$ and $Y=\{Y_{1},Y_{2},\ldots ,Y_{s}\}$, the overlap between $X$ and $Y$ can be summarized in a contingency table $\left[n_{ij}\right]$ where each entry $n_{ij}$ denotes the number of objects in common between $X_{i}$ and $Y_{j}$ : $n_{ij}=|X_{i}\cap Y_{j}|$.

X\Y	$Y_{1}$	$Y_{2}$	$\ldots$	$Y_{s}$	Sums
$X_{1}$	$n_{11}$	$n_{12}$	$\ldots$	$n_{1s}$	$a_{1}$
$X_{2}$	$n_{21}$	$n_{22}$	$\ldots$	$n_{2s}$	$a_{2}$
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\vdots$
$X_{r}$	$n_{r1}$	$n_{r2}$	$\ldots$	$n_{rs}$	$a_{r}$
Sums	$b_{1}$	$b_{2}$	$\ldots$	$b_{s}$

Definition

The adjusted form of the Rand Index, the Adjusted Rand Index, is $AdjustedIndex={\frac {Index-ExpectedIndex}{MaxIndex-ExpectedIndex}}$, more specifically
$ARI={\frac {\sum _{ij}{\binom {n_{ij}}{2}}-[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}]/{\binom {n}{2}}}{{\frac {1}{2}}[\sum _{i}{\binom {a_{i}}{2}}+\sum _{j}{\binom {b_{j}}{2}}]-[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}]/{\binom {n}{2}}}}$
where $n_{ij},a_{i},b_{j}$ are values from the contingency table.

External links

• C++ implementation with MATLAB mex files