Linkage - Create Even Sized Clusters?

Question

I want to cluster some data points into a given number of clusters according to their nearest neighbour, but with a preference towards even sized clusters when there are multiple pairs with the same distance.

I have tried using linkage from fastcluster (scipy.cluster.hierarchy behaves the same) to cluster according to the distance matrix (I have pairwise distances, but objects to cluster have no co-ordinates), but with a uniform distance matrix it merges the first two items together, then the third into the same cluster and so forth, generating one big cluster and lots of single items.

I am using a custom bit of code to parse the output matrix from linkage and form the k clusters. I've tried different method and metric parameters, but without a strong understanding of them, and with no luck.

I am happy to consider alternative clustering methods, provided I can specify k, need only pairwise distance/similarity, and it favours even clustering. I understand that I cannot have perfectly even clusters (nor do I want to), but I do want as even as possible distribution when things are otherwise equal.

There is a Jupyter notebook with a small example case here: https://nbviewer.jupyter.org/gist/TomAnthony/9b813d68ece7ce1f4daa394df963499c

Thanks!

Answer 1

If you desire almost even sized partitions, I would be reluctant to call this "clustering". Because this implies largely ignoring the structure of the data set, in favor of breaking it into even sized partitions.

Ties should rarely happen, unless you have a very low data resolution. If this makes a difference, then you probably have data issues.

A simple workaround to try is shuffle your data and keep the most even result. But that is quite slow.

It's fairly easy to modify AGNES to prefer merging smaller clusters when distances are tied. You simply need a second criterion, cluster size. But I doubt it will make a difference.

You can try k-means with even sized clusters, available in the "tutorial" package of ELKI (I use the github version, built from source). It works and will find a local optimum, but because of the size constraints results are often rather "unintuitive" (and there probably often is no "intuitive" solution with clusters of the same size)