2
$\begingroup$

I am given $n$ points in 2D.(Each of say approximately equal weight). I want to partition it into $m$ clusters ($m$ can be anything and it is input by the user) in such a way that the center of mass of each cluster is "far" from center of mass of all other clusters. What is a good heuristic approach (it should also be quick and easy to implement) for this? My current approach is to set up a binary tree at each step. What I am doing now is that the line I choose to separate cluster at each step which maximizes the moment of inertia of the set of points in the cluster I am splitting. Any suggestion welcome!

$\endgroup$
2
$\begingroup$

You might want to look at this survey paper on clustering methods:

http://cchen1.csie.ntust.edu.tw:8080/students/2011/Survey%20of%20clustering%20algorithms.pdf

$\endgroup$
3
$\begingroup$

The keyword is "clustering" as mentioned in Moron's answer. Any problem of this type will be NP-complete. In practice, K-means is not bad in its runtime or (depending very much on the application) its results. Like the simplex algorithm for linear programming, it can take exponential time in the worst case, but its practical complexity is much lower. The worst-case bound was proven only very recently.

Also, partitioning a graph is a different problem. Here you are partitioning a set of points and distances are used but not any graph structure.

(added:)

Here is the smoothed analysis. K-means has polynomial runtime when averaged over (Gaussian) random perturbations of the input, which is not surprising considering the practical efficiency:

http://arxiv.org/abs/0904.1113

$\endgroup$
  • $\begingroup$ Thanks Moron and T.. . Yes I know it is NP-complete. I want a efficient heuristic algorithm though. Could you point me to algorithms which are almost linear complexity? (like \mathcal{O}(N \log^{\alpha}N). Thanks for immediate replies. $\endgroup$ – user17762 Nov 18 '10 at 17:26
2
$\begingroup$

You might find K-Means Clustering (and related) helpful.

This is one of the classic machine learning problems, you should find plenty of literature on this.

$\endgroup$

Your Answer

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