K-means算法的变化与平等的簇大小

问题描述

我在找最快的算法在地图上分组分入同样大小的组，按距离。该 K-均值聚类算法看起来简单的和有希望的，但不会产生同样大小的组。

有没有这种算法的变化还是不同的，它允许成员对所有集群同等数量？

解决方案

这可能做的伎俩：适用劳氏算法获得的 K 的重心。排序的质心通过降它们相关联的簇的大小在数组中。对于我的= 1到的 K 的-1，推动数据点集群的我的与任何其他的质心的最小距离的Ĵ（我的＆LT; Ĵ的≤ K 的）关到的Ĵ的和重新计算质心的我的（但不重新计算集群），直到簇大小的 N / K 的。

在这个后处理步骤复杂度为O（ K 的²的 N 的LG的 N 的）。

I'm looking for the fastest algorithm for grouping points on a map into equally sized groups, by distance. The k-means clustering algorithm looks straightforward and promising, but does not produce equally sized groups.

Is there a variation of this algorithm or a different one that allows for an equal count of members for all clusters?

解决方案

This might do the trick: apply Lloyd's algorithm to get k centroids. Sort the centroids by descending size of their associated clusters in an array. For i = 1 through k-1, push the data points in cluster i with minimal distance to any other centroid j (i < j ≤ k) off to j and recompute the centroid i (but don't recompute the cluster) until the cluster size is n / k.

The complexity of this postprocessing step is O(k² n lg n).

这篇关于K-means算法的变化与平等的簇大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！