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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.