I'm rather new to this field and maybe even using a bit naive terminology.

So I need to classify (cluster) some objects, but limiting each cluster in size, so for each cluster $C_i$,

$$\sum_{o \in C_i} m(o) \leq N$$

where $m(\cdot)$ is a some norm-like function.

In case the objects are on a euclidean plane, would be nice if also $\forall i \neq j, h(C_i) \cap j(C_j) = \emptyset $, where $h(\cdot)$ is a convex hull (though not strictly required)

Lots of thanks in advance for correcting my terminology, and links to both algorithm implementations and theory.

P.S. Without this limitation, we are more or less happy with DBSCAN results.

// Best regards, Sergei

  • $\begingroup$ Would it be reasonable to use k-means, increasing $k$ until the above constraint holds? I have no idea if this would give decent results, especially for your specific case (you likely won't get results comparable to those from DBSCAN); it's just the first idea that came to mind. Would also be very low-effort. $\endgroup$ – hexaflexagonal Jul 13 '16 at 18:49
  • $\begingroup$ I guess this idea applies more generally to any algorithm with a limited enough set of parameters that you can easily adjust and check your results. Of course, this would be less efficient than an algorithm designed to keep in mind a maximum "cluster mass"--and you'd need to develop some heuristics. I'm just not aware of any existing algorithms that do what you need (though my knowledge is likely as limited as yours, if not moreso). $\endgroup$ – hexaflexagonal Jul 13 '16 at 18:59

Your Answer

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

Browse other questions tagged or ask your own question.