1

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

Alejandro Tolcachier
  • 1,938
Mauro
  • 111
  • you have an example of what it can't be, but do you have an example of what it can be? I don't understand what you're trying to do. – Patrick Da Silva Jul 18 '11 at 08:45
  • Sorry, it was a typo. I edit it now! – Mauro Jul 18 '11 at 08:51
  • I removed the model-theory tag, as it is intended to refer to this. – t.b. Jul 18 '11 at 09:47
  • I don't understand your example. It might clarify the question if you explain why A & B and C & D would be grouped together. Also the description under "Input Data" could use some clarification/explication. – joriki Jul 18 '11 at 09:55
  • Yeah, it's still unclear. Can you give more examples or give us an idea of what does those measures mean and how does the group gets chosen? I know that's almost actually your question, but we don't understand what you want to find (at least me and joriki!) – Patrick Da Silva Jul 18 '11 at 09:59
  • Hope last edit clarifies. Thanks for your kind remarks and ask if something is still unclear – Mauro Jul 18 '11 at 10:14
  • Thanks Theo! Sorry for misunderstanding – Mauro Jul 18 '11 at 10:29
  • You haven't specified how a group consisting of more than two persons contributes to the "overall friendship level". – joriki Jul 18 '11 at 10:37
  • "logic does not change" doesn't make sense -- you hadn't defined the calculation of the friendship level for more than two persons, and there was no unique generalization to more than two persons, so there's nothing that could be said to have changed or not. (For instance, the friendship level could have been defined as the product or the average of all pairwise friendship levels within the group instead of the sum). – joriki Jul 18 '11 at 11:19
  • Sorry Jokiri, but you comment is offensive. This is a Q&A website and I can edit the question as per your comments. And I'll be more than happy to define more. Just 2 comments: first I haven't defined calculation as it is the measure used and not the algorithm, that is the true scope of the question; I hope you agree on the fact that the 2 issues can be addressed separately. Second, I think it was pretty clear I was using sums. In any case, I REALLY appreciate your suggestion of products. Regards – Mauro Jul 18 '11 at 11:32
  • @Mauro: I understand neither why you think it was clear that you were using sums within groups, nor why you find my comment offensive. I was making a factual statement about the content, not about you as a person. – joriki Jul 18 '11 at 11:53
  • @Mauro Our sister SE site would be a good place to start: http://stats.stackexchange.com/questions/tagged/clustering – whuber Jul 18 '11 at 17:31

0 Answers0