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


  • 1
    $\begingroup$ You wish simultaneously two almost incompatible things: nearest neighbour link and (approximately) same sized clusters. In real situations with not very much separated clusters you have no chance to succeed at that. $\endgroup$
    – ttnphns
    Jul 30, 2017 at 21:06

1 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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.