How to compare labels from clustering analysis and original ones?

Question

I was asked to run a clustering analysis to assess the validity of labels for a manually labelled dataset.

I can simply save the actual labels (4 classes: 0, 1, 2, 3) and run clustering analysis (let's say python sklearn AgglomerativeClustering) on the rest of the data, specifying to get 4 clusters. Now I want to compare labels obtained from clustering and the original ones (manually labelled) to check if the manual labelling worked well.

The problem is that "cluster labels" have arbitrary values assigned by the clustering algorithm, for example, all samples labelled as 0 could have been labelled as 1, 2 or 3 and vice versa. They could also be A, B, C, D, or blue, green, red, yellow, they just need to be 4 distinct groups (clusters).

Now, how can I run the comparison? I would need a method to "convert" cluster label values to the original ones, hence cluster label 0 corresponds to original label 0? or original label 1 or 2 or 3? Once this issue is solved, I should be able to compare the two labels, count the number of matches between cluster and original labels, see how many samples were wrongly labelled, and share them with the experts.

I would like to use the AgglomerativeClustering algorithm for this task, but any other algorithm would be fine, even if I think that I would always face this issue, as clustering is an unsupervised learning method.

Answer 1

A common approach is to consider all pairs of points and count for each pair whether the two points are assigned to the same cluster or to different clusters. This yields four numbers:

• a = #SS = number of pairs in the same cluster in both clustering
• b = #SD = number of pairs which are in one clustering in the same and in the other in different clusters
• c = #DS = in analogy to b
• d = #DD = number of pairs which are in different clusters in both clusterings

From these numbers, different indices can be computed, e.g. the Rand-Index: $$R = \frac{a+d}{a+b+c+d}$$ As the number $d$ is typically quite large, the Rand-Index tends to be close to one, even when the clusterings are considerably different. A more reasonable index is thus the Jaccard-Index: $$J = \frac{a}{a+b+c}$$ There are other ways to define clustering similarity indices, e.g. by means of precision and recall. See the following articles for an overview:

D. Pfitzner, R. Leibbrandt, D. Powers: "Characterization and evaluation of similarity measures for pairs of clusterings." Knowledge and Information Systems 19(3), pp. 361-394 (2009)

E. Amigó, J. Gonzalo, J. Artiles, F. Verdejo: "A comparison of extrinsic clustering evaluation metrics based on formal constraints." Information retrieval 12(4), pp. 461-486 (2009)