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.

[ToTo13]

Bonsoir,

regarde donc sur weka pour tester quelle méthode donne les meilleurs résultats dans ton cas.

[Jonnyd]

Salut,
J'ai étudié l'algorithme ce week-end, et voilà ce que j'en ai retenu :
On détermine des centroides en testant toutes les combinaisons de points pouvant être ces centroides et en y affectant le reste de points en testant la distance point - centroide, la distance la plus petite déterminant cette affectation. On retient la combinaison de centroide lorsque les moyennes des distances points-centroides est la plus proche.
Ce que je n'ai pas vraiment compris, c'est comment on détermine les centroides?
Si on teste toutes les combinaisons, j'ai peur que ce soit beaucoup trop long (et assez difficile à coder, étant donné qu'il faudrait garder en mémoire chaque essai pour trouver le meilleur). Par exemple, pour un cas de 700points et de 4 nuages de points, je devrais tester toutes les combinaisons de 4 parmi 700, en calculant à chaque fois toutes les distances entre les 696points restants et les quatre centroides, puis enregistrer toutes ces informations (je vous laisse imaginer la taille du tableau...).
Enfin bref, j'imagine que j'ai du passer à coté de quelque chose...
Merci d'avance,
Jonnyd

[Aleph69]

Tu n'as rien compris du tout.
http://math.unice.fr/~ahrens/teaching/mpb2/COURS8.pdf
http://www.lodyc.jussieu.fr/~bslod/CAH.pdf
http://perso.univ-rennes1.fr/jian-fe...-classif-4.pdf
http://thames.cs.rhul.ac.uk/~bcs/CAD...-2-191-198.pdf
http://iml.univ-mrs.fr/~reboul/ADD4-MAB.pdf

[Jonnyd]

Yep j'avais pas vu l'étape du centre de gravité.

[Jonnyd]

Salut,
J'ai coder un algo des k-means en C++ qui me donne d'excellents resultats quand je connais a l'avance le nombre de nuages de point a determiner, mais je ne vois pas comment faire pour reutiliser mon algo quand je ne connais pas le nombre de nuage de point.
J'avais pense a tester successivement differentes valeurs, mais je ne trouve pas de parametre qui me permette de dire "Ah oui, c'est clairement mieux avec sept nuages qu'avec huit".
Enfin bref, si qqn avait une idee ce serait assez cool.
Merci d'avance.

[Aleph69]

Bonjour,
je t'ai déjà donné la réponse : il faut faire un k-means en choisissant un nombre relativement élevé de clusters puis appliquer une cah aux clusters trouvés pour les regrouper en un nombre naturel de clusters. Enfin, relancer un k-means en partant des clusters trouvés par la CAH. C'est ce qu'on appelle une approche hybride et tu dois pouvoir trouver des informations dessus avec google très certainement.

[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.