Python K-Means 聚类和最大距离

Question

首先我想说的是，我对聚类技术的了解非常有限，请不要太严厉地批评我。

我有一组相当大的 3D 点（大约 8,000 个） - 想象一下 X、Y、Z 三元组，其中 Z 坐标代表地下地球中的一个点（负）。我想使用绝对最小数量的簇对这些点进行聚类，并具有以下约束：

1. 使用最少数量的簇
2. 所有点都应该包含在聚类中，这意味着任何点至少应该属于一个聚类
3. 任何点与簇质心（在Z=0处移动，在地球表面）之间的最大距离不应超过某个固定距离d。

我正在考虑使用 scikit-learn k-means 方法，通过迭代增加簇的数量，然后对于数据集中的所有点计算该点与簇质心（在 Z=0 处）之间的距离是否小于提供具体距离。

当然，我愿意接受更好/更有效的建议 - 例如，集群不需要像 k-means 返回的那样是循环的。它们可以是椭圆形或其他任何形状，只要满足上述约束即可。

我欢迎任何建议，谢谢您的见解。

Answer 1

使用层次聚类。

联动完整。

找到真正的最小覆盖是 NP 难的。所以你不想这样做。但这应该在“仅仅”O(n3) 中产生相当好的近似值。