我正在寻找最快的算法,通过距离将地图上的点分组为相同大小的组.在K-均值聚类算法看起来简单的和有希望的,但不会产生同样大小的组.
是否存在此算法的变体或不同的算法,允许所有群集的成员数相等？
另请参见:对具有相同大小的k个簇中的n个点进行分组
可能重复:
具有相等簇大小的K均值算法变化
编辑:像casperOne指出,这个问题是重复的.无论如何,这是一个更普遍的问题,涵盖这一个:https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points
我的要求
在一个项目中,我需要将n个点(x,y)分组为相同大小的k个簇(n/k).其中x和y是双浮点数,n的范围可以是100到10000,k的范围是2到100.在算法运行之前k也是已知的.
我的实验
我开始使用http://en.wikipedia.org/wiki/K-means_clustering算法来解决这个问题,该算法非常快速地生成大致相同大小的k个簇.
但我的问题是,K-means产生大小相同的簇,我需要簇的大小完全相同(或者更精确:我需要它们的大小介于地板之间(n/k)和ceil(n/k)).
在你向我指出之前,是的,我在这里尝试了第一个答案K-means算法变化具有相同的簇大小,这听起来是个好主意.
主要思想是通过K-means对集群产生的数组进行后处理.从最大的集群到最小的集群.我们通过将额外的点移动到其他最近的集群来减少具有超过n/k成员的集群的大小.单独留下已经减少的集群.
这是我实现的伪代码:
n is the number of point
k is the number of cluster
m = n / k (the ideal cluster size)
c is the array of cluster after K-means
c' = c sorted by size in descending order
for each cluster i in c' where i = 1 to k - 1
n = size of cluster i - m (the number …