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
    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.2011-07-18
  • 0
    Sorry, it was a typo. I edit it now!2011-07-18
  • 0
    I removed the model-theory tag, as it is intended to refer to [this](http://en.wikipedia.org/wiki/Model_theory).2011-07-18
  • 0
    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.2011-07-18
  • 0
    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!)2011-07-18
  • 0
    Hope last edit clarifies. Thanks for your kind remarks and ask if something is still unclear2011-07-18
  • 0
    Thanks Theo! Sorry for misunderstanding2011-07-18
  • 0
    You haven't specified how a group consisting of more than two persons contributes to the "overall friendship level".2011-07-18
  • 0
    "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).2011-07-18
  • 0
    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. Regards2011-07-18
  • 0
    @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.2011-07-18
  • 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