Pie*_*ger 22 algorithm cluster-analysis k-means
可能重复:
具有相等簇大小的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 of point to move)
loop n times
find a point p in cluster i with minimal distance to a cluster j in c' where j > i
move point p from cluster i to cluster j
end loop
recalculate centroids
end for each
这个算法的问题是在接近结束的过程中(当我接近k时),我们必须在c'中选择一个簇j(其中j> i因为我们需要单独留下已经处理过的簇),但是我们发现这个集群j可以远离集群i,从而打破了集群的概念.
我的问题
是否有K-means算法或K-means变体可以满足我的要求,或者我从一开始就错了,我需要找到其他的聚类算法？
PS:我不介意自己实现解决方案,但如果我可以使用库,理想情况下在JAVA中会很棒.
尝试以下k均值变体：
初始化：
k从数据集中随机选择中心，或者使用kmeans ++策略更好地选择中心最后，您应该进行分区，以满足每个群集+ -1个相同数量的对象的要求（确保最后几个群集也具有正确的数量。第一个m群集应该具有ceil对象，其余的完全是floor对象。）请注意，使用堆可确保群集保持凸形：如果它们不再是凸形的，则将有更好的交换候选者。
迭代步骤：
必要条件：每个群集的列表，其中包含“交换提案”（希望放在其他群集中的对象）。
E步骤：按照常规k均值计算更新的聚类中心
M步：遍历所有点（仅一批或全部一批）
计算距对象最近的群集中心/比当前群集更近的所有群集中心。如果是其他群集：
聚类大小保持不变（+-天花板/地板差），对象仅从一个聚类移动到另一聚类，只要它能改善估计值即可。因此，它应该在某点收敛，例如k均值。不过，它可能会更慢（即更多迭代）。
我不知道它是否已经发布或实施过。这就是我会尝试的方法（如果我会尝试k-means。会有更好的聚类算法。）
作为该主题的专家，我曾经需要想出一个简单的算法来对地图上的位置进行聚类，其中每个点都需要成为聚类的一部分，并且聚类以多种方式绑定（不仅仅是大小（即点计数），但也有一些取决于不同因素的其他措施）。
通过首先找到“困难”点，然后从那里增长簇，我得到了最好的结果。“困难”点是难以到达的点，例如因为它们单独位于总区域的郊区，或者因为它们比其他点更有助于达到另一个簇边界条件。这有助于生长整齐排列的簇，留下很少的孤独者和相应的手工来放置它们。
如果您当前的算法通常会最后找到这些难点，这可能会对您有所帮助。