algorithm - 等簇大小的 K-means 算法变体

Question

我正在寻找最快的算法来按距离将 map 上的点分组为大小相等的组。 k-means clustering algorithm看起来简单而有前途，但不会产生同等规模的群体。

是否有此算法的变体或不同的算法允许所有集群的成员数量相等？

See also: Group n points in k clusters of equal size

Answer 1

这可能会奏效:应用 Lloyd's algorithm得到 k 个质心。通过数组中相关簇的大小降序对质心进行排序。对于 i = 1 到 k-1，将集群 i 中的数据点推送到任何其他质心 j (i <j ≤ k) 到j 并重新计算质心i(但不要重新计算集群)直到集群大小为 n/k。

此后处理步骤的复杂度为 O(k² n lg n)。