# External cluster evaluation for a varying number of cluster

There are many external clustering indices like (Adjusted) mutual information, (Adjusted) Rand index, and many more. However, they are not very good at comparing clusterings where the number of clusters is not the same.

For example, if I take one cluster and split it into two new ones, a comparison would yield a low score.

To evaluate the clustering in my case, this operation should not affect the score a lot. Also according to [1], none of the compared cluster evaluation indices utilize optimal pairing, only greedy methods, to find the cluster matches (solve the linear assignment problem).

So my question is: Are there any methods to calculate a matching score between two clusterings where the number of clusters differ and clusters are not only paired but also optimally matched in a 1:n (or even n:m) way? The computation complexity doesn't matter to me very much.

Using an example with NMI:

>>> normalized_mutual_info_score([0, 0, 1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 0, 0, 3, 3], average_method='arithmetic')
0.8571428571428573
>>> normalized_mutual_info_score([0, 0, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 0, 0, 0, 3, 3, 3], average_method='arithmetic')
0.8204614780379502
>>> normalized_mutual_info_score([0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2], [1, 1, 2, 2, 0, 0, 0, 0, 3, 3, 3, 3], average_method='arithmetic')
0.7896900821428475


The scores get progressively worse for an increasingly larger split cluster.

[1] Mohammad Rezaei, Pasi Fränti. Set Matching Measures for External Cluster Validity.

Most measures such as (Adjusted,Normalized) Rand index / normalized mutual information do perform an optimal n:m-like comparison by design.

They avoid having to make the assumption that cluster A in one clustering is cluster X in the other; instead they look at the resulting object pairs instead. Methods that rely on "set matching" are very uncommon because of this reason. It appears to mostly be classification people that think you should be using the precision and recall of a 1:1 matching, because that is the measure they always use.

In the Rand index, Mutual Information, etc. moving a single element from a cluster into a small second cluster reduces the quality roughly by 1/n initially; and once the resulting cluster starts becoming larger even less than that (until eventually when most elements have moved, the index starts I proving again). That is not what I would call inappropriately worse, nor "not very good at comparing clusters of different sizes". I think you should provide examples for your claim.

I am not convinced by the Rezaei paper. On one hand, they seem to assume that behavior must be linear in their synthetic data change (Rand index would often be linear; it's the desirable adjustment for chance that produces the non-linearity, and his can we'll be used as an argument that the measure should not be linear). Second, they seem to require that every cluster must have equal weight, so increasing the size of a "perfectly found" cluster must not affect the outcome. Here, again, I beg to disagree. Cluster influence should depend on the number of objects in the cluster. From the "cluster size imbalance" plot my take is that once you add a lot of 1-element clusters, the proposed PSI measure starts looking much worse, because it cannot deal with such noise.

• Sorry, I didn't ask the question correctly before. I meant to compare clusterings with a different number of clusters, not different number of objects within a cluster. I added an example where I compare 3 clusters to 4 clusters. And the score gets worse for larger cluster sizes which suggests, that NMI doesn't see any relationship between the original cluster and the two smaller clusters it was split into. Commented Aug 26, 2019 at 7:50
• The change affects an increasingly large part of the data set, doesn't it? It's not "constant". In your first data set, 50% is affected by the change, in the third row it's 2/3 of the data set - so the score should be lower. Commented Aug 26, 2019 at 17:54
• Or in terms of editing, in the first example you need to relabel 2/8 objects to get an equivalent result, then 3/10 and 4/12. In this sense the rate of mislabeled objects increased from 1/4 to 1/3. But as said above, it's a question of the viewpoint: do you value each cluster equally (independent of size), or is a cluster with twice as many objects twice as important (or equally, is every object equally important). You can find cars for either position, although I argue that weighting each instance will usually be preferable. Commented Aug 26, 2019 at 18:08
• Yes, the score should depend on the size. However I would like the matching method to recognize that the elements from that one cluster should be assigned to two clusters, so that none of the elements are actually counted as misclassified. To give an example: In the first data set this cluster could be "news", in the second one the two clusters could be "political news" and "entertainment news" or something like that. In that case the elements are just clustered into finer categories in the second case, but not wrongly. Commented Aug 27, 2019 at 1:18
• It's a legitimate idea, but unfortunately that doesn't just work. Otherwise the result 1 2 3 4 5 6 7 8 is a perfect solution (it just split everything into absurdly detailed subtopics, didn't it?) What you likely want is some kind of edit distance, where a split is a cheap edit (I think the common edit distances would count relabeled instances, so you'll need to roll your own). Commented Aug 27, 2019 at 6:04