Discussion :

[olibara]

Bonjour

Je suis confronté au problème suivant et je cherche un algorythme permetant de traiter cela


Je dispose d'un nombre N de points et leurs coordonées XY disposé aléatoirement sur un plan

De dois creer G groupes ayant un maximum de M points chacun

Chaque groupe doit evidement etre constitué en assemblant les points ayant la meilleure proximité

Donc Hypothese :

100 points XY
Maximum 3 groupes
Maximum 40 points par groupe

Comment aborder cela ?

Merci de vos suggestions

[dourouc05]

Tu peux regarder du côté de l'algorithme des k moyennes, c'est assez facile à implémenter (https://en.wikipedia.org/wiki/K-means_clustering). Par contre, il ne peut rien faire pour la taille maximale d'un groupe, mais la discussion est arrivée il n'y a pas si longtemps sur les forums (tu peux construire un petit truc par-dessus pour t'assurer que ça marche ; pour les détails…).

[olibara]

Merci Dourouc05 et cher compatriote

J'avais le pressentiment de devoir passer par du Delaunay ou du Voronoi
Et tu me conforte donc dans l'idée que c'est la bonne piste

Cela étant je ne suis pas pratiquant je dois donc me faire un peu la main
L'objectif est de traduire ca en cSharp pour faire le boulot

Si j'ai bien compris l'exemple, il partitionne selon le nombre de groupe
Donc dans mon cas je devrais le cas échéant muter un certain nombre de points d'un groupe a l'autre en fonction de la densité et la proximité

[dourouc05]

M'est avis que tu cherches à faire bien compliqué. Vu le nombre de points, a priori, pas besoin d'aller aussi loin. Simplement partir de centres (prendre des points au hasard pour commencer) qui définissent des groupes, assigner chaque point au groupe dont le centre est le plus proche, recalculer les centres comme la moyenne des points du groupe, itérer. Et peut-être réassigner des points à un autre groupe pour la contrainte de quarante points par groupe, ça sera un peu plus inventif.

Ça sera beaucoup plus facile à implémenter qu'une triangulation du genre (et tu trouveras facilement des implémentations existantes, au besoin).

[tbc92]

L'un des problèmes si on choisit 3 centres au hasard, c'est qu'on biaise pas mal les résultats. En caricaturant, si les 3 centres choisis sont tous les 3 très voisins l'un de l'autre, et tous les 3 très excentrés, on arrive à n'importe quoi.

Un algorithme (un peu coûteux) est la méthode de la CAH (Classification hiérarchique ascendante).
- On calcule toutes les distances 2 à 2.
- On prend le couple de points avec la distance minimale, et on associe ces 2 points. Et on a un nouvel élément qui est ce couple de points. On recalcule donc la distance entre ce couple de points et les 98 autres points... A ce niveau là, on a 2 ou 3 choix qui peuvent donner des résultats différents. On peut dire que la distance entre un couple de points AB et un point C est au choix min ( Dist(AC), Dist(BC) ), ou bien Moyenne( Dist(AC), Dist(BC) ) ... ou bien d'autres formules envisageables.
- Et on répète l'opération autant de fois que nécessaire pour avoir les 3 groupes voulus. en associant à chaque fois les 2 éléments avec la distance minimale (un élément étant soit un individu isolé, soit un groupe)
- Et si on veut, on peut ajouter des contraintes pour qu'aucun groupe ne dépasse 40 individus.

[olibara]

Merci Dourouc05
Merci tbc92

tbc92 tu a raison sur le choix at random des trois point de départ et c'est la Remarque que je voulais faire a dourouc05
Maintenant il est sans doute possible de poser des contraintes pour mieux determiner le choix de ces trois points


Mais dans les deux proposition je me demande si on ne va tomber dans un problème classique d'affectation ou a force d'itérer "bêtement" sur les choix les meilleurs le resultat sera une répartition asser hétérogène et mal balancée

Je vais bientot me lancer sur le coding a partir d'un échantillon et voir ce que ca donne