# Problem of "clustering" into most similar groups

I do not think that the following problem can be solved with k-means clustering. I am not sure though. Okay, let me describe the problem. I need to find a way or an algorithm that groups members of a given data set (of positive integers) so that the difference between group means is minimized (not maximized, as usual). There are two constraints:

1. The number of groups should not exceed log(N) base 2. N is the input array size. Let us assume that N = 16, always.

2. The size of the group should be at least log(N) base 2. Here it is 4.

Please see below example. Guidance toward a solution to this problem is appreciated.

   for input array = (12, 14, 16, 16, 18, 19, 20, 21, 24, 26, 27, 29, 29, 30, 31, 32)


One of the solutions could be the following:

set    group           mean
1   (12, 14, 31, 32)    22.25
2   (16, 16, 29, 30)    22.75
3   (18, 19, 27, 29)    23.25
4   (20, 21, 24, 26)    22.75

• Could you get to the same result by first clustering with k-means, then constructing your 'groups' by taking M points from each cluster?
– Nick
May 26, 2012 at 2:33
• @Nick. First I thought about this. But I am not sure how to select number of points and then how many combinations I should test. May 26, 2012 at 2:44