How to measure clustering quality when true clusters are known?

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?

• Those classification metrics are called, within cluster analysis field, external clustering criterions (stats.stackexchange.com/a/195481/3277, pt. 4). In the linked page, pay also attention to a series of links I've given under the Question there. You might want to read the stuff behind those links. – ttnphns Nov 11 '16 at 8:23
• Thanks very much, great answer there. I will definitely check out the links. – kreo Nov 11 '16 at 19:09

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