5
$\begingroup$

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
$\endgroup$
2
  • 1
    $\begingroup$ Could you get to the same result by first clustering with k-means, then constructing your 'groups' by taking M points from each cluster? $\endgroup$
    – Nick
    May 26, 2012 at 2:33
  • $\begingroup$ @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. $\endgroup$
    – samarasa
    May 26, 2012 at 2:44

2 Answers 2

4
$\begingroup$

This is not really clustering. It reminds me of the classic bin packing problem, which unfortunately is NP-hard.

https://en.wikipedia.org/wiki/Bin_packing_problem

Seriously, avoid the term "cluster". Cluster usually refers to "similar" objects, here they are very dissimilar.

A classic strategy would be to first compute the optimal mean (= mean of all data). Then use a greedy strategy to build groups reasonably close to this mean, e.g. by combining high and low values. Then finally, try to optimize the result by moving or swapping objects to improve the target criterion until convergence. You could even try a genetic algorithm for this.

$\endgroup$
0
1
$\begingroup$

Here's one not tested idea how to adapt K-means algo to try to solve your task. You may know that the majority of standard K-means clustering implementations include the so called running means option. Under this option, on each iteration the cluster centre is being updated (recalculated) immediately after a point is assigned to that cluster (rather than after all points were assigned to their closest clusters, as in typical mode). If you use running means in conjunction with such modification of the algo that a point is assigned to the farthest (rather than the nearest) cluster, the centre, then cluster centres are expected to converge during the whole process, and you end with clusters which are maximally superposed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.