2
$\begingroup$

In this simplified example, I have five variables for each individual. The data is normalized, with mean 0 and sd 1 in each variable.

I would like to divide this data into two groups with equal size and I'd like the mean for each variable to be as close to zero as possible (because since data is normalized, this would mean that the groups are as similar as possible).

I don't know any theory about that kind of problem. My only solution so far would be to randomly divide them millions of times, and selecting the one with smaller distance between the means of each group.

Could you point me to what kind of theory should I read to face this problem in a more optimal way?

One example of data like this in R would be:

set.seed(123)
A <- matrix(runif(100), 20, 5)
A <- scale(A) #normalize
rownames(A) <- letters[1:20]
colnames(A) <- paste0("x",1:5)
$\endgroup$
  • $\begingroup$ Is there some larger context for doing this splitting? (For example splitting data into train/test sets.) $\endgroup$ – GeoMatt22 Sep 6 '16 at 18:36
  • $\begingroup$ It is a train/test division, but in my specific case I need both groups with equal size $\endgroup$ – tmilrandom Sep 6 '16 at 18:37
  • $\begingroup$ OK. As far as I know, the standard in that case is to do a random split of the data, but then repeat the split-data/train-model/test-model cycle many times, to get statistics over different possible splits (i.e. multiple rounds of 2-fold cross validation). Meaning, the results from any one split tend to not be very reliable (even if the split is "optimal" in some sense). $\endgroup$ – GeoMatt22 Sep 6 '16 at 18:43
  • $\begingroup$ Is the (about) same mean is the only aim or do you want to match each observation with some most similar to it another observation within the data? $\endgroup$ – ttnphns Sep 7 '16 at 8:42
  • $\begingroup$ Relevant domains possibly are (see wikipedia) partition problem and subset sum proplem. $\endgroup$ – ttnphns Sep 7 '16 at 9:29
1
$\begingroup$

Please see this question and answer to a very similar question:

https://stackoverflow.com/a/39338999/1060350

Here, there was a requirement that nearby pairs of points should be formed and put into separate groups (avoid the term cluster when they aren't regular clusters). But this should even further improve your requirement.

A similar, surprising, heuristic for your aim of attempting to have 0 mean is this:

  1. Sort points by the distance from the center (here 0).
  2. Choose the farthest point $x$ in this list, and the point $y$ which minimizes $||x+y||_2$
  3. Assign both randomly to cluster A or B
  4. Repeat 2 (only), but assign them to the other cluster.
  5. If there are more than 3 points remaining, go back to 2
  6. Assign the remaining points according to your size constraints and use them to slightly improve the means to your liking.

This is only a heuristic - it will not find the optimum solution - but probsbly the problem is NP or exponential, so you can't afford to search for the optimum.

Above greedy approach should find a decent solution, because it tries to identify the hardest points first, then chooses the best counterbalance each.

If you need better results, you can modify step 3 to not choose at random, but instead assign points to clusters as to minimize how much the cluster center deviates from 0. This could also be used in step 2: instead of minimizing $||x+y||_2$ you could minimize $||C+x+y||_2$ where C are all the objects already in the cluster. These tweaks make the code slightly more complicated, but require not much computational overhead.

$\endgroup$

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.