statistics - 椭圆体的 k 均值

Question

我在 R^3 中有 n 个点，我想用 k 个椭球体或圆柱体覆盖它们(我不在乎；以更容易的为准)。我想大约最小化卷的并集。假设 n 是数万，k 是少数。开发时间(即简单性)比运行时更重要。

显然我可以运行 k-means 并为我的椭球体使用完美的球。或者我可以运行 k 均值，然后使用每个簇的最小封闭椭球体，而不是用球覆盖，尽管在最坏的情况下这也好不了多少。我见过关于用 k 均值处理各向异性的讨论，但我看到的链接似乎认为我手头有一个张量；我不知道，我只知道数据将是椭球体的并集。有什么建议吗？

[编辑:有几票支持拟合多元高斯的混合，这似乎是一个可行的尝试。启动 EM 代码来执行此操作不会最小化联合的体积，但当然 k 均值也不会最小化体积。]

Answer 1

所以你可能知道 k-means 是 NP 难的，而且这个问题更普遍(更难)。因为您想要制作椭球体，所以拟合 k 个多元高斯分布的混合可能很有意义。您可能想尝试找到最大似然解，这是一种非凸优化，但至少它很容易制定并且可能有可用的代码。

除此之外，您可能必须从头开始编写自己的启发式搜索算法，这只是一项艰巨的任务。