我在 R^3 中有 n 个点，我想用 k 个椭球体或圆柱体覆盖(我真的不在乎；以更容易的为准)。我想大约最小化卷的联合。假设 n 是数万，k 是少数。开发时间(即简单性)比运行时更重要。
显然我可以运行 k-means 并为我的椭球使用完美的球。或者我可以运行 k-means，然后在每个集群中使用最小的封闭椭球，而不是用球覆盖，尽管在最坏的情况下也没有更好。我见过用 k-means 处理各向异性的讨论，但我看到的链接似乎认为我手头有张量；我不知道，我只知道数据将是椭球体的并集。有什么建议么？
[编辑:有几票赞成拟合多元高斯的混合物，这似乎是一个可行的尝试。启动一个 EM 代码来做到这一点不会最小化联合的体积，但当然 k-means 也不会最小化体积。]
最佳答案
所以你可能知道 k-means 是 NP-hard，这个问题更普遍(更难)。因为你想做椭圆体，所以拟合 k 个多元高斯分布的混合可能很有意义。您可能想尝试找到最大似然解决方案，这是一种非凸优化，但至少它很容易制定并且可能有可用的代码。
除此之外，您可能必须从头开始编写自己的启发式搜索算法，这只是一项艰巨的任务。
关于statistics - 椭圆体的 k 均值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7880156/