Rand index

Example clusterings for a dataset with thekMeans(left) andMean shift(right) algorithms. The calculated Adjusted Rand index for these two clusterings is$ARI\approx 0.94$

TheRand indexorRand measure(named after William M. Rand) instatistics,and in particular indata clustering,is a measure of the similarity between twodata clusterings.A form of the Rand index may be defined that is adjusted for the chance grouping of elements, this is theadjusted Rand index.The Rand index is theaccuracyof determining if a link belongs within a cluster or not.

Rand index

Definition

Given asetof$n$elements$S=\{o_{1},\ldots,o_{n}\}$and twopartitionsof$S$to compare,$X=\{X_{1},\ldots,X_{r}\}$,a partition ofSintorsubsets, and$Y=\{Y_{1},\ldots,Y_{s}\}$,a partition ofSintossubsets, define the following:

• $a$,the number of pairs of elements in$S$that are in thesamesubset in$X$and in thesamesubset in$Y$
• $b$,the number of pairs of elements in$S$that are indifferentsubsets in$X$and indifferentsubsets in$Y$
• $c$,the number of pairs of elements in$S$that are in thesamesubset in$X$and indifferentsubsets in$Y$
• $d$,the number of pairs of elements in$S$that are indifferentsubsets in$X$and in thesamesubset 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$.

Since the denominator is the total number of pairs, the Rand index represents thefrequency of occurrence of agreements over the total pairs, or the probability that$X$and$Y$ will agree on a randomly chosen pair.

${n \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 oftrue negatives,$FP$is the number offalse positives,and$FN$is the number offalse negatives.

Properties

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^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}$
• $b=|S^{*}|$,where$S^{*}=\{(o_{i},o_{j})\mid 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})\mid 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})\mid 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}$

Relationship with classification accuracy

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

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 inK-meansthe 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 setSofnelements, and two groupings or partitions (e.g.clusterings) of these elements, namely$X=\{X_{1},X_{2},\ldots,X_{r}\}$and$Y=\{Y_{1},Y_{2},\ldots,Y_{s}\}$,the overlap betweenXandYcan 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}|$.

${\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}}$

Definition

The original Adjusted Rand Index using the Permutation Model is

$ARI={\frac {\left.\sum _{ij}{\binom {n_{ij}}{2}}-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}{\left.{\frac {1}{2}}\left[\sum _{i}{\binom {a_{i}}{2}}+\sum _{j}{\binom {b_{j}}{2}}\right]-\left[\sum _{i}{\binom {a_{i}}{2}}\sum _{j}{\binom {b_{j}}{2}}\right]\right/{\binom {n}{2}}}}$

where$n_{ij},a_{i},b_{j}$are values from the contingency table.

See also

• Simple matching coefficient

External links

• C++ implementation with MATLAB mex files