# What's the purity of random clustering?

Purity is defined as $\mbox{purity}( \Omega,\mathbb{C} ) = \frac{1}{N} \sum_k \max_j \vert\omega_k \cap c_j\vert$

where $\Omega = \{ \omega_1, \omega_2, \ldots, \omega_K \}$is the set of clusters and $\mathbb{C} = \{ c_1,c_2,\ldots,c_J \}$ is the set of classes.

If we assign points randomly to cluster, what is the expected purity?

The answer is important, so we can make sense of the purity by itself when evaluating a clustering method.

Yes, information-based metrics are easier to understand in this context, but purity is very popular.

Let's assume the size of the class is the same. In that case,

$\vert\omega_k \cap c_j\vert = \frac{N}{\vert\mathbb{C}\vert} \frac{1}{\vert\mathbb{C}\vert}$

where the first term is the expected size of a cluster $k$, and the second is the expected proportion of them to be in class $j$. Then,

$\max_j \vert\omega_k \cap c_j\vert = \frac{N}{\vert\mathbb{C}\vert} \frac{1}{\vert\mathbb{C}\vert}$

as all sets have the expected same size, that does not depends on $j$. Finally,

$\mbox{purity}(\Omega,\mathbb{C}) = \frac{1}{N} \vert \Omega \vert \frac{N}{\vert\mathbb{C}\vert^2} = \frac{\vert \Omega \vert}{\vert\mathbb{C}\vert^2}$

Further, if the number of classes and clusters is the same, then

$\mbox{purity}(\Omega,\mathbb{C}) = \frac{1}{\vert\mathbb{C}\vert}$

So, if the expected purity became relevant if the number of classes is small.

If $\Omega$ grows, keeping $\mathbb{C}$ fixed, then random clustering gets easier. Beware of $\Omega$ growing too much, as this argument would stop making sense.