# Clusters with bounded diameter

In my application, I want to have clusters whose diameters are bounded by some fixed number. Also, the number of clusters in the data is unknown and, therefore, the clusters must be discovered without a 'k' parameter.

What method should I use?

Hierarchical clustering, with complete linkage will find clusters with a maximum pairwise distance i.e. diameter.

You need two parameters:

1. Distance function
2. Maximum distance = height where to cut the tree
• I'm looking for an algorithm where I can provide the maximum diameter a cluster can have. Still, thanks. Sep 1, 2016 at 15:55
• Did you even read what I wrote? The maximum distance is a diameter. Sep 1, 2016 at 15:56
• Ok, I didn't get that bit I guess. Could you please elaborate? This and also that I need an algorithm that is a bit more robust to noise. Sep 1, 2016 at 15:57
• Not much to elaborate here. Just try it. Sep 1, 2016 at 15:58
• I mean what if I need the diameter to be 6.3? What would the height be then? Sep 1, 2016 at 16:00

Start with Hierarchical clustering. That will give you an hierarchical grouping of the datapoint, matching each one to the closest to it. One of the benefits of such clustering is that you can decide afterwards what is the number of clusters (k) that you want and then get the actual clusters.

In your case there is and additional constraint of the diameter. Hence, you should verify that the maximal distance between the items in the cluster is bellow your bound. Since that in hierarchical clustering we match the closest items first, when you divide into clusters you should check that the distance between the current item and the rest of the items in the clusters is bellow your bound.

You can doing that while building the hierarchy, saving computation time. However, you can also do it after the hierarchy was constructed and this way use libraries that already implemented these algorithms and you will only need to add the diameter bound on your own.

• Could you point me to a package that offers this implementation? Sep 4, 2016 at 10:02
• scikit-learn.org/stable/modules/…
– DaL
Sep 4, 2016 at 10:30