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$ – EngrStudent Aug 10 '18 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 '18 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 '18 at 15:38
  • $\begingroup$ Wouldn't this be as simple as just minimizing the between cluster sum of squares rather than the within cluster sum of squares as clustering typically does? $\endgroup$ – astel Aug 10 '18 at 17:20
  • $\begingroup$ astel: well, is it still convex? Usually the opposite problem is not, and thus won't converge nicely; but you'll rather be stuck with quite bad answers after initialization. $\endgroup$ – Anony-Mousse Aug 10 '18 at 18:29

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, privacy policy and cookie policy

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