How to measure clustering quality when true clusters are known?

Question

Say that we have a set of objects X. These objects are partitioned into several clusters. Two objects $x_i$ and $x_j$ belong to the same cluster iff $a_i = a_j$, where $a_i$ and $a_j$ - cluster labels of objects $x_i$ and $x_j$. Clustering given by those labels $a_i$ is considered to be "true" clustering.

Now we use clustering algorithm on objects X. This algorithm knows nothing of the "true" clusters. For each object $x_i$ algorithm produces a label $b_i$. If $b_i = b_j$ then algorithm predicted that objects $x_i$ and $x_j$ belong to the same cluster. If $b_i \ne b_j$, algorithm predicted that those objects belong to different clusters.

The question is: how to measure how "close" the clustering made by algorithm is to the "true" clustering? In other words, how to say how "good" the clustering algorithm performed compared to some known "true" clustering?

Right now I am using the classification metrics: for each pair of objects $x_i$ and $x_j$ we know if they really belong to the same cluster (in this case we say that it is pair of "class 1") or they belong to different clusters (pair of "class 0"). We also know what algorithm predicted this pair to be ("class 0" or "class 1"). Knowing that, we are able to calculate precision, recall and F1 score for pairs of "class 0" and "class 1".

Are there any other good ways to measure performance of clustering algorithm when we know the "true" clustering?

Answer 1

Consider a clustering as a prediction algorithm. But instead of predicting $a_i$ (which it can't) you apply it on pairs, and predict whether $a_i=a_j$ or $a_i\neq a_j$.

Now you can compute various statistics, such as precision (how many pairs are put together correctly) and recall (how many pairs are recalled)... that is the key idea of all the pair counting measures, such as ARI, which you find in literature.