There is a lot of content about how to cluster, say, customers (k-means, EM clustering, etc.).

However, is there a way to reverse cluster customers? Meaning, let's say I have 20 customers, and want to divide them into two groups, such that those two groups are as similar to each other as possible. Is there an algorithm for that?

Here is more information about my specific situation: Each of 20 customers has five features associated with him or her. These customers vary along those five dimensions. I'd like the means of two (or three, etc.) groups to be as close to each other as possible. I could try to solve the problem by brute force by trying all combinations of customers, and see which grouping is best, but I'm sure there's a better way to do it.

  • 3
    $\begingroup$ When I think of "cluster" I think of taking an unknown initial mix and turning it into piles of similar things. The reverse of that is randomization. One problem with randomizing is that random is approximately random, but not exactly random. By that, I mean that there is structure to the randomness including but not limited to various random distributions, various weights, and changes that happen over time. There is an infinite number of ways to approach random reordering of sets. $\endgroup$ Aug 10, 2018 at 14:27
  • 2
    $\begingroup$ Perhaps cluster into sets of size 2, then randomly select one from each set for the first anti-cluster group and the other in the second group. I would stop there, but if you insisted then you could try to see if swapping some of these pairs around in some sense improved overall similarity between the two groups, at the risk of losing some of the benefits of randomisation $\endgroup$
    – Henry
    Aug 10, 2018 at 14:41
  • $\begingroup$ @Henry Or simply randomly select which member goes into each set? Or, if the groups are to be the same size use adaptive sampling to so ensure. Or randomly shuffle a vector of length $2\times\text{ group size}$ containing the valeus 1 and 2 and use that to assign elements to each group? $\endgroup$
    – Alexis
    Aug 10, 2018 at 15:38
  • 1
    $\begingroup$ @ttnphns, would you care to develop that into an answer? I think it might be useful for people. $\endgroup$ Aug 17, 2018 at 14:07
  • 1
    $\begingroup$ I meant develop it into something more than a one-line answer, @ttnphns ;-). What is the blossom algorithm? Why / how does it solve this problem? Etc. But it's fine if you don't want to; I'm not trying to pressure you. $\endgroup$ Aug 17, 2018 at 18:38

1 Answer 1


Formulate it as an optimization problem. Then use a solver.

Finding the best answer will likely be NP-hard, so you'll want to use a greedy heuristic and some incremental improvements to keep the running time okay.


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.