2
$\begingroup$

Given two constraints:

  • The maximum distance d an element can lie from a cluster centroid (or medoid)
  • The maximum number of elements n in one cluster

Is it possible to find the minimum number of clusters which would contain all elements in a region?

One brute-force approach would be to place each element in its own cluster and methodically decreasing the number of clusters, but I feel like there has to be a more graceful solution.

I'm rather new to cluster analysis, so any references would be greatly appreciated!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

Beware that such problems can easily be np-hard. Then finding the minimum may be infeasible. You may still be able to find a good approximation.

In your case, the problem encompasses the set cover problem. All possible clusters that do not violate your constraints form the sets, and finding the minimum then is the set cover problem, which is known to be np-hard.

Improve this answer
$\endgroup$
3
  • $\begingroup$ In this case, I want to use these two initial conditions to approximate a minimum value for 'k' in a k-means or k-medoids algorithm. You suggest first finding all possible clusters, then computing the minimum number a la set cover problem. For your approach, what would be the best clustering method to do so? $\endgroup$
    – sophistry
    Commented Jun 18, 2015 at 18:41
  • $\begingroup$ I'm not suggesting to do that. This is just the outline of a proof that your problem is np-hard, so you may want to relax the constraints and search for an approximation. Just like k-means does: finding the true minimum is too expensive. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jun 18, 2015 at 18:49
  • $\begingroup$ Ended up using a heuristic algorithm that checks distance and max cluster elements after each k-means cycle. It's computationally expensive, but gets the job done for now. $\endgroup$
    – sophistry
    Commented Jun 26, 2015 at 20:15
1
$\begingroup$

If you can express your constraints as linear ones, there is an effective way to solve your problems, at least with a $k$-means objective.

For instance, your second constraint (enforcing a maximum number of elements in a cluster) can be expressed linearly, and then you can optimize the $k$-means energy by calling a LP-solver with your constraints. This is basically what is done in Constrained K-Means Clustering. Authors prove that it converges monotically toward a local minimum (alike the (standard) Lloyds-heuristic).

Improve this answer
$\endgroup$
2
  • $\begingroup$ k-means will usually not find the global minimum. It's not that easy to solve things exactly and efficiently, as k-means already is NP-hard. Also, k-means needs to know k beforehand, he wants to minimize the number of clusters. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jun 17, 2015 at 21:58
  • $\begingroup$ Yes, k-means is NP-hard. But, keep in mind, that it is a result for solving the minimization in general. Some cases can be solved exactly in polynomial-time, for instance the 1D-case, under stability conditions, or can be approximated arbitrarily well with PTAS on coresets. $\endgroup$
    – mic
    Commented Jun 18, 2015 at 9:40

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.