1
$\begingroup$

I am searching for a consolidated model to group n items in x groups. Do you know how to find on the web some resources on the above subject?

In my idea it can be something like: I have 4 persons and 2 groups of 2 persons each. The "friendship" level can be set on a range from 10 to -10

   A  B  C  D A  X  9  0 -1 B  9  X  5 -5  C  0  5  X  0 D -1 -5  0  X 

would group A&B (friendship level 9) and C&D (friendship level 0) because it maximize the overall friendship level respecting the constraint over groups (9 + 0 = 9 best possible choice).

To sum up

Input Data:

  • n items with measures associated (with must and mustn't group with...)

  • x groups (each with its own size i.e. group1 -> 5 items, group2 --> 15 and so on)

Output data:

  • Best or sub optimal choice(s)

So a most complex example can be:

I have 16 persons to divide as:

  • Group 1: 2 persons
  • Group 2: 2 persons
  • Group 3: 4 persons
  • Group 4: 8 persons

You have the same friendship level, but in my idea I would add or a side-logic for forcing grouping and ungrouping or use a fake level (say 10k or -10k) to enforce the same behaviour.

EDIT @Joriki: for groups of more than 2 persons logic does not change, meaning that if AB=5, BC=2, AC = -1, friendship level is 6 (=5+2+(-1))

EDIT2: In my example I was using sums, but every suggestion is welcome. Joriki pointed out the use of products. I think it is a good idea indeed but then negative values won't be used any longer.

Any hint on a model / algorithm that can be adapted to the above case?

Thx

  • 0
    @Mauro Our sister SE site would be a good place to start: http://stats.stackexchange.com/questions/tagged/clustering2011-07-18

0 Answers 0