title: Group n points in k clusters of equal size
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/5452576/k-means-algorithm-variation-with-equal-cluster-size">K-means algorithm variation with equal cluster size</a>  </p>
  </blockquote>
  
  
  
  <p>EDIT: like casperOne point it out to me this question is a duplicate. Anyways here is a more generalized question that cover this one: <a href="https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points">https://stats.stackexchange.com/questions/8744/clustering-procedure-where-each-cluster-has-an-equal-number-of-points</a></p>
  
  <p><strong>My requirements</strong></p>
  
  <p>In a project I need to group n points (x,y) in k clusters of equal size (n / k). Where x and y are double floating numbers, n can range from 100 to 10000 and k can range from 2 to 100. Also k is known before the algorithm runs.</p>
  
  <p><strong>My experimentations</strong></p>
  
  <p>I started to resolve the problem by using the <a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="noreferrer">http://en.wikipedia.org/wiki/K-means_clustering</a> algorithm, which work great and fast to produce exactly k clusters of roughly the same size.</p>
  
  <p>But my problem is this, K-means produce clusters of roughly the same size, where I need the clusters to be exactly the same size (or to be more precise: I need them to have a size between floor(n / k) and ceil(n / k)).</p>
  
  <p>Before you point it out to me, yes I tried the first answer here <a href="https://stackoverflow.com/questions/5452576/k-means-algorithm-variation-with-equal-cluster-size">K-means algorithm variation with equal cluster size</a>, which sounds like a good idea.</p>
  
  <p>The main idea is to post process the array of cluster produce by K-means. From the biggest cluster up to the smallest. We reduce the size of the clusters that have more than n / k members by moving extra points to an other nearest cluster. Leaving alone the clusters that are already reduced.</p>
  
  <p>Here is the pseudo code I implemented:</p>
  
  <pre><code>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 &gt; i
          move point p from cluster i to cluster j
      end loop
      recalculate centroids
  end for each
  </code></pre>
  
  <p>The problem with this algorithm is that near the end of the process (when i come close to k), we have to choose a cluster j in c' (where j > i because we need to leave alone the clusters already processed), but this cluster j we found can be far from cluster i, thus breaking the concept of cluster.</p>
  
  <p><strong>My question</strong></p>
  
  <p>Is there a post K-means algorithm or a K-means variant that can meet my requirements, or am I wrong from the beginning and I need to find an other clustering algorithm?</p>
  
  <p>PS: I do not mind to implement the solution myself, but it would be great if I can use a library, and ideally in JAVA.</p>