algorithm - k=2 的 Kmeans 算法给出相等的簇大小输出

Question

我正在使用修改后的 Lloyd 算法在 k=2 的 kmeans 中获得相等的簇大小输出。以下是伪代码:

- Randomly choose 2 points as initialization for the 2 clusters (denoted as c1, c2)
- Repeat below steps until convergence
    - Sort all points xi according to ascending values of ||xi-c1|| - ||xi-c2||, i.e. differences in distances to the first and the second cluster
    - Put top 50% points in cluster 1 , others in cluster 2
    - Recalculate centroids as average of the allocated points (as usual in Lloyd's)

现在，根据经验，上述算法对我来说工作正常:

1. 它给出了平衡的集群
2. 它总是降低目标

以前有文献提出或分析过这样的算法吗？我可以得到一些引用吗？

Answer 1

这里解释了一个更通用的多于 2 个集群的版本:

https://elki-project.github.io/tutorial/same-size_k_means

我在文献中多次看到具有各种大小限制的 k-means，但我手边没有任何引用资料。我不相信这一点:强制集群具有相同的大小与寻找最小二乘最佳近似值恕我直言的 k-means 想法相矛盾，因为这意味着故意选择更差的近似值。