4

I have n points in R^3 that I want to cover with k ellipsoids or cylinders (I don't really care; whichever is easier). I want to approximately minimize the union of the volumes. Let's say n is tens of thousands and k is a handful. Development time (i.e. simplicity) is more important than runtime.

Obviously I can run k-means and use perfect balls for my ellipsoids. Or I can run k-means, then use minimum enclosing ellipsoids per cluster rather than covering with balls, though in the worst case that's no better. I've seen talk of handling anisotropy with k-means but the links I saw seemed to think I had a tensor in hand; I don't, I just know the data will be a union of ellipsoids. Any suggestions?

[Edit: There's a couple votes for fitting a mixture of multivariate Gaussians, which seems like a viable thing to try. Firing up an EM code to do that won't minimize the volume of the union, but of course k-means doesn't minimize volume either.]

3 Answers 3

3

So you likely know k-means is NP-hard, and this problem is even more general (harder). Because you want to do ellipsoids it might make a lot of sense to fit a mixture of k multivariate gaussian distributions. You would probably want to try and find a maximum likelihood solution, which is a non-convex optimization, but at least it's easy to formulate and there is likely code available.

Other than that you're likely to have to write your own heuristic search algorithm from scratch, this is just a huge undertaking.

1
  • NP-hard doesn't scare me; I only want an approximation, and my data is not made of gadgets. Or if it is I can just blame the user. EM to compute a mixture of Gaussians doesn't really minimize what I'm trying to minimize. It might work well though, so I'll try it -- k-means doesn't minimize it either.
    – bhudson
    Oct 25, 2011 at 18:44
1

I did something similar with multi-variate gaussians using this method. The authors use kurtosis as the split measure, and I found it to be a satisfactory method for my application, clustering points obtained from a laser range finder (i.e. computer vision).

1
  • Thanks. I hadn't gotten to worrying about automating the choice of k but this might do the trick.
    – bhudson
    Oct 25, 2011 at 18:39
0

If the ellipsoids can overlap a lot, then methods like k-means that try to assign points to single clusters won't work very well. Part of each ellipsoid has to fit the surface of your object, but the rest may be inside it, don't-cares. That is, covering algorithms seem to me quite different from clustering / splitting algorithms; unions are not splits.

Gaussian mixtures with lots of overlaps ? No idea, but see the picture and code on Numerical Recipes p. 845.

Coverings are hard even in 2d, see find-near-minimal-covering-set-of-discs-on-a-2-d-plane.

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.