K-means algorithm variation with equal cluster size

algorithm map cluster-analysis k-means
pixelistik picture pixelistik · Mar 27, 2011 · Viewed 39.5k times · Source

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?

See also: Group n points in k clusters of equal size

Answer

Fred Foo picture Fred Foo · Mar 27, 2011

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).

Related questions

Looking for a good world map generation algorithm

I'm working on a Civilization-like game and I'm looking for a good algorithm for generating Earth-like world maps. I've experimented with a few alternatives, but haven't hit on a real winner yet. One option is to generate a heightmap using …

Read More
Fast algorithm to find the x closest points to a given point on a plane

I would like to find a fast algorithm in order to find the x closest points to a given point on a plane. We are actually dealing with not too many points (between 1,000 and 100,000), but I need the x closest …

Read More
What's the best depth map generation algorithm?

I'm into a 2D-to-3D application project and I'm looking for a method to produce the depth map of a single input image, without other external informations. I know that's a sort of "artificial intelligence" mattern but maybe an efficient …

Read More