k-means算法中的椭球形聚类

Question

我在R^3中有n个点，想用k个椭圆或圆柱体（我不在乎哪个更简单）将它们覆盖。我希望尽量减小这些图形的并集的体积。假设n是成千上万的数量级而k很少。对于我们来说，开发时间（即简单性）比运行时间更重要。

显然，我可以运行 k-means 算法并使用完美的球来代替我的椭圆体。或者我可以运行 k-means，然后使用每个聚类的最小外接椭圆体而不是用球来覆盖，但在最坏的情况下，这并没有更好。我看到过有关使用 k-means 处理异性的讨论，但我看到的链接似乎认为我手头拥有张量；但实际上，我只知道数据将是一组椭圆体的并集。有什么建议吗？

[编辑：有一些建议使用多元高斯混合模型进行拟合，这似乎是一个可行的尝试。启动 EM 代码来执行此操作不会最小化并集的体积，但是当然k-means算法也不能最小化体积。]

- bhudson

Answer 1

你可能知道k-means是NP-hard问题，而这个问题甚至更加一般化（更难）。 因为你想要使用椭圆体，所以拟合k个多元高斯分布的混合模型可能会很有意义。 你可能希望尝试找到最大似然解，这是一个非凸优化问题，但至少易于表述，而且可能有可用的代码。

除此之外，你可能需要从头编写自己的启发式搜索算法，这只是一个巨大的任务。

- fairidox

---

NP-hard并不吓到我；我只想要一个近似值，而且我的数据不是由小玩意儿组成的。如果是的话，我可以怪用户。使用EM算法计算高斯混合物并不能真正最小化我想要最小化的东西。虽然它可能效果很好，所以我会尝试一下——k-means也无法最小化它。 - bhudson

Answer 2

我曾使用这种方法来处理多元高斯分布的问题。作者使用峰度作为分裂度量，我发现这对我的应用程序来说是一种令人满意的方法，可以将从激光测距仪（即计算机视觉）获得的点进行聚类。

- Throwback1986

---

谢谢。我还没有开始担心自动选择k的问题，但这可能会解决问题。 - bhudson

Answer 3

如果椭球体有很大的重叠部分， 那么像k-means这样试图将点分配到单个聚类中心的方法 效果不会很好。 每个椭球体的一部分必须适合于对象的表面， 但其余部分可能在其中，不关心。 也就是说，覆盖算法与聚类/分裂算法似乎非常不同； 并集不是分裂。

高斯混合物有很多重叠吗？ 我不知道，但可以看看Numerical Recipes p. 845上的图片和代码。

即使在二维平面上，覆盖问题也很难解决，可以参考 find-near-minimal-covering-set-of-discs-on-a-2-d-plane。

- denis