0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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
| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm looking for an algorithm where I can provide the maximum diameter a cluster can have. Still, thanks. $\endgroup$ – Sairaam Venkatraman Sep 1 '16 at 15:55
  • $\begingroup$ Did you even read what I wrote? The maximum distance is a diameter. $\endgroup$ – Has QUIT--Anony-Mousse Sep 1 '16 at 15:56
  • $\begingroup$ 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. $\endgroup$ – Sairaam Venkatraman Sep 1 '16 at 15:57
  • $\begingroup$ Not much to elaborate here. Just try it. $\endgroup$ – Has QUIT--Anony-Mousse Sep 1 '16 at 15:58
  • $\begingroup$ I mean what if I need the diameter to be 6.3? What would the height be then? $\endgroup$ – Sairaam Venkatraman Sep 1 '16 at 16:00
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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