Group n points in k clusters of equal size [duplicate]

by

Try this k-means variation:

Initialization:

  • choose k centers from the dataset at random, or even better using kmeans++ strategy
  • for each point, compute the distance to its nearest cluster center, and build a heap for this
  • draw points from the heap, and assign them to the nearest cluster, unless the cluster is already overfull. If so, compute the next nearest cluster center and reinsert into the heap

In the end, you should have a paritioning that satisfies your requirements of the +-1 same number of objects per cluster (make sure the last few clusters also have the right number. The first m clusters should have ceil objects, the remainder exactly floor objects.)
Note that using a heap ensures the clusters remain convex: if they were no longer convex, there would have been a better swap candidate.

Iteration step:

Requisites: a list for each cluster with “swap proposals” (objects that would prefer to be in a different cluster).

E step: compute the updated cluster centers as in regular k-means

M step: Iterating through all points (either just one, or all in one batch)

Compute nearest cluster center to object / all cluster centers that are closer than the current clusters. If it is a different cluster:

  • If the other cluster is smaller than the current cluster, just move it to the new cluster
  • If there is a swap proposal from the other cluster (or any cluster with a lower distance), swap the two element cluster assignments (if there is more than one offer, choose the one with the largest improvement)
  • otherwise, indicate a swap proposal for the other cluster

The cluster sizes remain invariant (+- the ceil/floor difference), an objects are only moved from one cluster to another as long as it results in an improvement of the estimation. It should therefore converge at some point like k-means. It might be a bit slower (i.e. more iterations) though.

I do not know if this has been published or implemented before. It’s just what I would try (if I would try k-means. there are much better clustering algorithms.)

More Related Contents:

  1. K-means algorithm variation with equal cluster size
  2. Unsupervised clustering with unknown number of clusters
  3. Clustering Algorithm for Mapping Application
  4. Algorithm to beat Strassen’s Algorithm
  5. HSL to RGB color conversion
  6. What exactly does big Ө notation represent?
  7. Select k random elements from a list whose elements have weights
  8. How are ssl certificates verified?
  9. How to find the intersection point between a line and a rectangle?
  10. What is the difference between tree depth and height?
  11. Finding the median of an unsorted array
  12. How to estimate download time remaining (accurately)?
  13. Sorting in linear time? [closed]
  14. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  15. median of three values strategy
  16. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  17. Fastest algorithm for circle shift N sized array for M position
  18. Lights out game algorithm
  19. How does this work? Weird Towers of Hanoi Solution
  20. JavaScript: Calculate the nth root of a number
  21. Maximum Contiguous Subsequence Sum of At Least Length L
  22. The intersection of all combinations of n sets
  23. How does lucene index documents?
  24. How to efficiently calculate a row in pascal’s triangle?
  25. A Good and SIMPLE Measure of Randomness
  26. Image similarity comparison
  27. How do I find the Excel column name that corresponds to a given integer? [duplicate]
  28. What is the algorithm that opencv uses for finding contours?
  29. Find XOR of all numbers in a given range
  30. Best algorithm for matching colours.

Leave a Comment