Chemostat

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,\dots ,o_n\}$ and two partitions of $S$ to compare, $X=\{X_1,\dots ,X_r\}$, a partition of S into r subsets, and $Y=\{Y_1,\dots ,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}{(\genfrac{}{}{0ex}{}{n}{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=\left|S^{*}\right|$, where $S^{*}=\{(o_i,o_j)|o_i,o_j\in X_k,o_i,o_j\in Y_l\}$

• $b=\left|S^{*}\right|$, 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=\left|S^{*}\right|$, 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=\left|S^{*}\right|$, 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\le i,j\le n,i\ne j,1\le k,k_1,k_2\le r,k_1\ne k_2,1\le l,l_1,l_2\le s,l_1\ne 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,\dots ,X_r\}$ and $Y=\{Y_1,Y_2,\dots ,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$	$\dots$	$Y_s$	Sums
$X_1$	$n_{11}$	$n_{12}$	$\dots$	$n_{1s}$	$a_1$
$X_2$	$n_{21}$	$n_{22}$	$\dots$	$n_{2s}$	$a_2$
$⋮$	$⋮$	$⋮$	$\ddots$	$⋮$	$⋮$
$X_r$	$n_{r1}$	$n_{r2}$	$\dots$	$n_{rs}$	$a_r$
Sums	$b_1$	$b_2$	$\dots$	$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}(\genfrac{}{}{0ex}{}{n_{ij}}{2})-[\sum _i(\genfrac{}{}{0ex}{}{a_i}{2})\sum _j(\genfrac{}{}{0ex}{}{b_j}{2})]/(\genfrac{}{}{0ex}{}{n}{2})}{\frac{1}{2}[\sum _i(\genfrac{}{}{0ex}{}{a_i}{2})+\sum _j(\genfrac{}{}{0ex}{}{b_j}{2})]-[\sum _i(\genfrac{}{}{0ex}{}{a_i}{2})\sum _j(\genfrac{}{}{0ex}{}{b_j}{2})]/(\genfrac{}{}{0ex}{}{n}{2})}$
where $n_{ij},a_i,b_j$ are values from the contingency table.

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

External links

• C++ implementation with MATLAB mex files