具有相同簇大小的K均值算法变化 [英] K-means algorithm variation with equal cluster size

问题描述

我正在寻找最快的算法，用于将地图上的点分成相同大小的组，按距离。 k-means聚类算法看起来很直观而有希望，但并不产生相同大小的组。

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?

另请参见：组在相同大小的k个群集中的n个点

推荐答案

：应用劳埃德算法获得 k 质心。通过数组中相关联的集群的大小降序来对质心进行排序。对于 i = 1到 k -1，以最小的距离推送集群 i 中的数据点到任何其他质心j （ i j ≤ k ）关闭到 j 并重新计算质心（但不要重新计算集群），直到集群大小为 n / k 。

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.

这种后处理步骤的复杂性是O（ k ² n lg n ）。

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

这篇关于具有相同簇大小的K均值算法变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！