我在 R^3 中有 n 个点，我想用 k 个椭圆体或圆柱体来覆盖（我真的不在乎；以更容易的为准）。我想大约最小化卷的并集。假设 n 是数万，k 是少数。开发时间（即简单性）比运行时间更重要。
显然，我可以运行 k-means 并为我的椭球使用完美的球。或者我可以运行 k-means，然后使用每个簇的最小封闭椭球而不是用球覆盖，尽管在最坏的情况下也好不到哪里去。我见过用 k-means 处理各向异性的讨论，但我看到的链接似乎认为我手头有张量；我不知道，我只知道数据将是椭球体的联合。有什么建议么？
[编辑：有几票赞成混合多元高斯，这似乎是一个可行的尝试。启动一个 EM 代码来做到这一点不会最小化联合的体积，但当然 k-means 也不会最小化体积。]
所以你可能知道 k-means 是 NP 难的，而且这个问题更普遍（更难）。因为你想做椭球体，所以拟合 k 个多元高斯分布的混合可能很有意义。您可能想尝试找到一个最大似然解决方案，这是一种非凸优化，但至少它很容易制定并且可能有可用的代码。
除了您可能必须从头开始编写自己的启发式搜索算法之外，这只是一项艰巨的任务。
我使用这种方法对多元高斯做了类似的事情。作者使用峰度作为分割度量，我发现它对我的应用来说是一种令人满意的方法，即从激光测距仪（即计算机视觉）获得的聚类点。
如果椭球可以重叠很多，那么像 k-means 这样尝试将点分配给单个集群的方法将不会很好地工作。每个椭球的一部分必须适合您的对象的表面，但其余部分可能在其中，不在乎。也就是说，覆盖算法在我看来与聚类/分裂算法有很大不同；工会不是分裂。
有很多重叠的高斯混合？不知道，但请参阅数字食谱 p 上的图片和代码。845 .
即使在 2d 中也很难覆盖，请参阅 find-near-minimal-covering-set-of-discs-on-a-2-d-plane。