Comparing Partitions Website

Getting started

Diversity

Pairwise agreement

Information theory

Other Coefficients

Calculations

Clustering and Contingency Tables

Let X be a set of N data points {x₁, x₂, x₃, ..., x_N}. Given two clusterings of X, namely A={A₁, A₂, A₃, ..., A_R} with R clusters and B={B₁, B₂, B₃, ..., B_C} with C clusters, the information on cluster overlap between A and B can be summarized in the form of a R×C contingency table (CT) as illustrated in Figure 1. Every element of X contributes to the cell of the corresponding clusters in both A and B.

Figure 1: Contingency table. n_ij denotes the number of elements that are common to clusters A_i and B_j.

Focusing on the pairwise agreement, the information in the CT can be further condensed in a mismatch matrix:

$a+b+c+d=\begin{pmatrix}N \\ 2\end{pmatrix}=\frac{N(N-1)}{2}=M$

Figure 2: Mismatch Matrix. a, b, c and d represent counts of unique entity pairs.

Explicit formulae for calculating a, b, c and d in the mismatch matrix can be constructed using entries in the CT (Hubert & Arabie, 1985):

$a=\frac{1}{2}\displaystyle\sum_{i=1}^{R}\sum_{j=1}^{C}n_{ij}(n_{ij}-1)$

$b=\frac{1}{2}\biggl[n^2+\displaystyle\sum_{i=1}^R\sum_{j=1}^Cn_{ij}^2-\biggl(\sum_{i=1}^Rn_{i\cdot}^2+\sum_{j=1}^Cn_{\cdot j}^2\biggr)\biggr]$

$c=\frac{1}{2}\biggl(\displaystyle\sum_{j=1}^Cn_{\cdot j}^2-\sum_{i=1}^R\sum_{j=1}^Cn_{ij}^2\biggr)$

$d=\frac{1}{2}\biggl(\displaystyle\sum_{i=1}^Rn_{i\cdot}^2-\sum_{i=1}^R\sum_{j=1}^Cn_{ij}^2\biggr)$

<< Previous: Test data sets Next: Simpson's ID >>

Share |