Discussion :

[webtheque]

Bonjour à tous,

Je cherche à faire un algo. pour répartir une liste de contacts dans des groupes hétérogènes.
En gros, il doit y avoir des femmes et des hommes dans chaque groupe.
Des français, des allemands, ...
Des fonction1, des fonction2, ...

Voici un exemple des informations sur les contacts :

>> Paul DUPOND (M, Français, BU1, Fonction1, France, 37)
>> Marta CLAUDIA (F, Espagnol, BU2, Fonction3, Espagne, 27)
>> Laura MARTIN (F, Français, BU3, Fonction2, Russie, 27)
>> Bruno BALAR (M, Italien, BU1, Fonction2, Italie, 24)
>> Marie JEANNE (F, Français, BU1, Fonction1, France, 44)
>> Pierre DURAND (M, Allemand, BU2, Fonction2, Allemagne, 34)
>> Carl MARAM (M, Anglais, BU3, Fonction3, Espagne, 32)
>> Yves JEAN (M, Espagnol, BU1, Fonction2, Espagne, 42)
>> Isabelle YEUXBLEU (F, Français, BU1, Fonction1, France, 21)
>> Marc ROSSET (M, Allemand, BU2, Fonction2, France, 26)
>> Yuri JORK (M, Allemand, BU2, Fonction2, Allemagne, 23)
>> Claude BERTRAN (M, Anglais, BU1, Fonction1, France, 25)

A partir de cette liste je voudrai créer 3 groupes de 4 contacts.

Comment est-ce que vous vous y prendriez :

[FrancisSourd]

Il s'agit d'un problème de partitionnement d'ensemble (c'est un problème en général difficile à résoudre, NP-complet en fait).

On peut d'abord définir une fonction pour évaluer la qualité d'une partition en groupe. Je définirai cet évaluateur ainsi
Pour chaque critère, soit N(critère) le nombre de valeurs qui peuvent être prises. Par exemple N(sexe)=2 car il y a deux sexes, N(function)=3, N(BU)=3....
Ensuite pour chaque groupe g d'une partition possible, on peut calculer N(g,critère) qui est le nombre de critères différents réunis dans le groupe g. La qualité de la partition est la somme sur tous les groupes et tous les critères des ratios N(g,critère)/N(critère) (ou mieux des ratios (N(g,critère)-1)/(N(critère)-1) ). Le but est alors d'obtenir une partition avec la meilleure évaluation possible.

Pour cela, on part d'une partition arbitraire des contacts et on calcule sont évaluation. Ensuite, on essaie d'échanger deux contacts qui se trouvent dans deux groupes différents. Si l'évaluation est meilleure on garde la nouvelle solution sinon, on continue en essayant d'échanger deux autres contact. L'algo s'arrête quand tout échange n'améliore pas la solution courante. La solution trouvée n'est pas forcément la meilleure possible mais au moins, elle ne peut pas être "trivialement" améliorée par un simple échange.

Il est aussi possible de trouver la meilleure partition possible (vis-à-vis du critère choisi pour l'évaluation des partitions) en énumérant toutes les partitions possibles mais cela prend en général énormément de temps de calcul (plusieurs années ou siècles dès qu'il y a plusieurs centaines de contacts).

[webtheque]

Ok, je comprends un peu la logique et je trouve çà génial !!

Mais je ne comprends pas tout...

on peut calculer N(g,critère) qui est le nombre de critères différents réunis dans le groupe g

Que veux-tu dire par ceci ?
Car j'ai toujours 6 critères quelquesoit les groupes :
Genre, Nationalité, BU, Fonction, Pays et Age

Le but est alors d'obtenir une partition avec la meilleure évaluation possible.

Comment sait on ensuite quelle est la meilleure évaluation ?
Le résultat est le plus proche de zéro ?

Merci pour ton aide qui m'est très précieux.

[FrancisSourd]

on peut calculer N(g,critère) qui est le nombre de critères différents réunis dans le groupe g

Que veux-tu dire par ceci ?

Effectivement N(g,critère) n'est pas le nombre de critères. C'est le nombre de valeurs différentes pour le critère donné.
Par exemple, si g contient au moins un homme et une femme, on aura
N(g, sexe)=2 (2 sexes différents)
S'il n'y a que des hommes, on a N(g,sexe) = 1.
S'il contient 2 anglais, un français et un allemand, on pose
N(g, nationalité)= 3 (nbre de nationalités différentes).

Ainsi, pour l'évaluation, s'il y a au moins une homme et une femme, on a
N(g,sexe)-1/N(sexe) = (2-1)/(2-1) = 1 (très bien)
S'il n'y a que des hommes
N(g,sexe)-1/N(sexe) = (1-1)/(2-1) = 0 (très mal)
Pour l'exemple des nationalités, cela donne
N(g, nationalité)-1 / (N(nationalité)-1) = (3-1)/N(nationalité)-1)
Remarque qu'un groupe de 4 contacts contient au plus 4 nationalités différentes même si ton panel contient plus de 4 nationalités. On peut donc fixeer N(Nationalité)=4, ce qui donne 2/3=0.67 pour le groupe g.
Donc pour chaque critère, on a une valeur entre 0 et 1.

Comme tu as si critère, ton évaluation vaudra au plus 6 (ce qui correspond au meilleur panel possible). Tu peux aussi pondérer tes critères si certains sont plus importants que d'autre.

Pour l'âge, il faut sans doute faire des classes d'âges (<20ans, 20/30 ans, ...) ou alors utiliser des statistiques (variance des âges, moyenne des écarts entre chaque paire d'âges).

[webtheque]

tout est plus clair maintenant.

A+