Discussion :

[Jonnyd]

Bonjour,

A partir de coordonnées diverses de points dans un repère en 2D, je dois arriver à les rassembler en nuage de point distinct (couleurs différentes à l'affichage).

J'aimerais savoir si vous connaissiez un algorithme / une méthode mathématique pour y arriver?

J'avais pensé à un parcours des points de proche en proche, avec une distance fixée à l'avance qui définirait l'appartenance ou non au même nuage, mais cette méthode me parait très coûteuse en calcul et pas très rigoureuse mathématiquement parlant.

Merci d'avance.
Cordialement,
Jonnyd

[PRomu@ld]

Il y a de nombreuses approches, tout dépend de ce que tu connais ou pas de ces nuages de points. La méthode la plus simple est sans doute la méthode des k-means (et toutes leurs dérivées) Ce problème a été abordé un très grand nombre de fois sur le forum. N'hésite pas à faire une recherche avec ce terme et à poser d'éventuelles questions sur des points que je ne comprendrais pas ou pour d'autres approches.

[Aleph69]

Bonjour,

pour compléter la réponse de PRomu@ld, l'alternative classique à la méthode des k-means et à ses variantes est la classification ascendante hiérarchique (CAH). Mathématiquement, elle revient à minimiser la distance des points au centre de leur groupe (variance intra-classe) et à maximiser la distance entre les groupes (variance inter-classe).

Si tu connais le nombre de groupes, c'est bien d'utiliser k-means. Sinon, si le nombre de points est peu élevé, c'est mieux d'utiliser la CAH qui va trouver "automatiquement" le nombre de groupes. Enfin, si le nombre de groupes est inconnu et le nombre de points grand, il faut recourir à une approche hybride en 3 étapes :

1. lancer k-means avec un nombre relativement élevé de groupes
2. lancer une CAH sur les centres des groupes trouvés et récupérer le nombre de groupes
3. relancer le k-means avec le nombre de groupes trouvé à l'étape 2.

[Jonnyd]

Je ne connais que les coordonnées des points, je vais donc me renseigner sur la méthode "hybride". En tout cas merci de votre aide.

[Jonnyd]

Vous n'auriez pas un lien complet à me passer sinon? Je ne trouve que des tp ou des exercices utilisant la méthode des k-means, pas d'explication en profondeur..

[PRomu@ld]

Même si la page est plutôt hideuse tu as toujours ça :

http://people.revoledu.com/kardi/tut...ean/index.html

La page wikipedia fonctionnera tout aussi bien.

[souviron34]

J'avais pensé à un parcours des points de proche en proche, avec une distance fixée à l'avance qui définirait l'appartenance ou non au même nuage, mais cette méthode me parait très coûteuse en calcul et pas très rigoureuse mathématiquement parlant.

Cela dépend si tu dois faire un regroupement relatif ou un regroupement absolu...

Pour les regroupements relatifs, effectivement les solutions qu'on t'a donné sont celles à utiliser..

Pour des regrupements absolus (tu connais la distance de séparation minimale), ton idée marche parfaitement, et est même en O(N logN) si elle est bien codée.. Et elle est rigoureuse mathématiquement, mais dans ce cas-là seulement : on a une contrainte qui est la distance minimale...

[Jonnyd]

J'ai finit mon projet, merci pour votre aide.