Discussion :

[ploup]

Bonjour,

Travaillant actuellement sur un projet englobant du traitement de signal sonore. Je réalise une acquisition sonore à laquelle j'applique une fenetre de hamming ainsi qu'une FFT afin de pouvoir sortir les points correspondant au impulsions que j'aurai donné avec un percuteur sur un objet.

Jusqu'a là pas de problème sauf que je dois pouvoir implement un auto-calibrage pour cela il faut que je trouve un algorithme me permettant de separer 3 populations contenues dans un nuage de points.

Mes ces 3 populations sont très proches , j'ai donc penser a trouver les barycentre de chaque population , les relies par une droite et prendre la mediatrice. Mais malheuresement les résultats n'etaient pas concluant.

J'ai abordé le pb de la même façon en ponderant mes poids mais les résultats n'etaient pas encore assez concluant.

Je suis passé aussi par l'élaboration de cercle pour chaques populations mais toujours pas satisfaisant.

A l'heure actuelle je seche un peu , avez vous d'autres idées qui me permettrait de séparer ces populations ?

[Zavonen]

Mes ces 3 populations sont très proches , j'ai donc penser a trouver les barycentre de chaque population , les relies par une droite et prendre la mediatrice. Mais malheuresement les résultats n'etaient pas concluant.

Relier 3 points par une droite...
Comment se peut-ce ?

[ploup]

j'ai applique cette methode pour les populations prise deux à deux .

[pseudocode]

Et un banal k-means, ca ne marche pas ?

[souviron34]

j'ai fait un algo qui fait ca..

L'hypothese sous-jacente est qu'on a une "distance de separation" minimum (un point est "dans le meme nuage" que tel autre si sa distance est < seuil).

2 manieres :

Maniere 1 :

• Projeter les points suivant une direction (faire un histogramme).
• Isoler les "paquets", eliminer les pics < 2 points.
• Pour chaque "paquet" de l'histo, flagger les points
• Pour chaque paquet ainsi flagge, faire l'histo dans l'autre dimension.
• Re-iterer le processus (isolation, elimination, flaggage)
• Eventuellement faire une 3 ieme passe, avec un angle de 45 degres.

On a la les points de chaque nuage flagges separement.



Maniere 2 :

• Faire un tri des points dans une direction (x par exemple) (qsort)
• Explorer le tableau 1 a 1 :
  

  Code :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  Si la distance en x > distance minimum
         nouveau nuage.
  Sinon
         Si la distance en y > distance minimum
              appartient a un autre
         fin si
  fin si

Evidemment beaucoup plus rapide (O(5*N) en gros pour beaucoup de points, avec optimisation)

Je pourrais t'envoyer ca par MP, mais pas aujourdhui...

[ploup]

Re-Bonjour,
Peut etre me suis-je mal exprimé dans mon premier post , dans le nuage de points je connais chaque points , et je sais à quelle population appartient les points mais pour mon auto-calibrage je dois pouvoir separer ces populations par des frontières et c'est là que je seche.

La methode des K-Means permet de separer un nuage en k classe homogène or ici je sais que j'ai 3 classe et je connais les points qui les compose .Mais je ne sais pas trouver la frontière les séparant.

Des que je serais chez moi je vous uploaderai un graphique ca aidera pour la comprehension

[pseudocode]

La methode des K-Means permet de separer un nuage en k classe homogène or ici je sais que j'ai 3 classe et je connais les points qui les compose .Mais je ne sais pas trouver la frontière les séparant.

Ah, ok. J'avais pas compris. En fait, tu cherches les courbes d'isodistance entre les populations. Le probleme ca va etre de créer ta propre distance.

[souviron34]

elles s'interpenetrent ou non, ces populations ? adjacentes ?

[ToTo13]

Bonjour,

petit détail, les Kmeans ne fournissent pas des populations homogènes au sens du cardinal de la population.
Mais si tu veux les lignes de séparations, tu peux tenter la chose suivante :
- Un K-means pour retrouver tes trois populations.
- Trouver les barycentre de chaque population.
- Calculer un diagramme de Voronoi sur les barycentre, ce qui te donnera les cellules de chaque population.
Tu auras sans doute quelques points en dehors de la bonne cellules, mais le résultat sera plutôt très bon dans l'ensemble.

Si tu veux une séparation plus précise, regardes du coté de la méthode "Partial Least Square".
Si tu souhaites un classement parfait (prôche de 100%) tu peux tenter d'utiliser des réseaux de neurones.

En gros, je ne sais pas quel type d'application tu souhaites exactement, mais cela ressemble beaucoup à du classement (classification en anglais). Donc intéresse toi aux méthode de classement (classification) et d'analyse de données (data mining).

[souviron34]

c'est vrai que l'on se sait pas trop quel est le vrai problème...

Je ré-itère :

Si les "patches" dans les nuages sont déjà identifiés (points flaggés comme appartenant à telle ou telle catégorie), il suffit de déterminer le polugone définissant le périmètre (concave) de ces points.

On a ensuite une série de polygones, dont on peut calculer les distances les uns aux autres...

Mais c'est peut-être complètement à côté de ce qui est recherché... ??

[Matthieu Brucher]

Si on n'a pas besoin de connaître exactement la droite, on peut utiliser une classification bayesienne (un champ de gaussiennes et on prend la classe la plus vraisemblable) ou des SVM.

[pseudocode]

Je me répete mais toutes les methodes cités necessitent de definir une distance entre 2 populations: distance moyenne, distance au plus court, distance au plus long, distance de Mahalanobis, ...

[ploup]

Bonjour,
Tout d'abord désolé de ne pas avoir repondu plus tôt , merci de vos réponses déjà , je vous ai mis en fichier joint un graphique représentant mes 3 populations. Avec la methode ou je calcule le barycentre de chaque populations et ensuite je trace la mediatrice de la droite liant 2 barycentre l'un a autre j'arrive bien a separer ma population rouge et bleu.

Mais en ce qui concerne les populations bleues et vertes ca devient plus embetant.
Je vais me renseigner un peu sur toutes les solutions citées et j'espere que ce graphique va pouvoir vous aider.

[Matthieu Brucher]

Faut que tu trouves des paramètres plus dicrimants que ceux que tu as, même le rouge est difficile à extraire.

[ToTo13]

Bonjour,

effectivement, les variables descriptives de ton modèle ne décrivent quasiment rien, elles sont vraiment insuffisante.
Aucun des algorithmes proposés ci-dessus ne fonctionnera, je pense même qu'il va être quasiment impossible de trouver un algorithme qui sépare tes populations avec ce que tu nous montres là.

[souviron34]

effectivement.....

même à l'oeil (et pourtant le cerveau est un bon calculateur) on ne distingue pas....

je suppose que ton x est inchangeable.... (quoique, son échelle peut-être ??)

Réfléchis à ton y..