Algorithme pour "grouper" les valeurs les plus proches

[sierramike]

Bonjour à tous,

Mes connaissances en Math pèchent certainement pour m'aider à résoudre mon besoin !

J'effectue des mesures analogiques (en l’occurrence je mesure des délais en microsecondes), et je me retrouve avec une liste de valeurs, dans lesquelles je dois reconnaître des valeurs (probablement des bits, mais il pourrait y avoir plus de 2 "valeurs absolues" possibles.

Par exemple, j'ai une liste telle que ci-dessous :
340
336
328
348
1060
1072
332
1024
340
1048
352
1082
342

A partir de cette liste, je cherche à isoler les valeurs proches entre elles, grosso modo identifier qu'il y a là dedans 2 "groupes" de valeurs :
340, 336, 328, 348, 332, 340, 352, 342
et
1060, 1072, 1024, 1048, 1082

A partir de là je saurai comment aller plus loin.

Comment faire pour faire ce type de détection ? Sachant qu'à priori, je n'ai aucune idée de ce que je vais mesurer, il y aura peut être 3 ou 4 groupes de valeurs, et peut être qu'une prochaine fois les "groupes" seront plus proches, par exemple 700-750 et 900-950.

J'ai pensé à l'algorithme des plus proches voisins mais apparemment ça n'est pas le bon, car il impose de déjà savoir ce qu'on cherche ...

Avez-vous des pistes à m'indiquer ?

Merci !
-----

[Jack]

Pourquoi ne pas trier l'ensemble des échantillons, mesurer l'écart moyen d'un échantillon à son suivant, continuer jusqu'à ce que l'écart diffère radicalement de l'écart moyen: on a alors isolé un groupe et on relance le processus à partir de ce nouveau groupe.

[sierramike]

Merci pour ton aide, je commençais à partir sur quelque chose du même goût, mais sans trier (créer mes groupes et les adapter (borne min/max) au fil de la lecture).

Mais c'est surtout le "diffère radicalement" qui m'ennuie, c'est sur cette partie précisément que je ne sais pas comment la traiter. Ca voudrait dire qu'il faut toujours injecter dans l'algorithme une "tolérance" permettant de définir un seuil au delà duquel on ne fait plus partie du groupe ? Je cherchais justement un algo qui devine automatiquement cette valeur en fonction de ce qu'il rencontre.

[Jack]

Pourquoi ne pas définir des seuils pour isoler les groupes. Si les groupes sont aussi marqués que dans l'échantillon du premier message, ca ne devrait pas poser de problèmes insurmontables.

Il doit peut-être exister des outils de traitements statistiques pour traiter ce genre de problème, mais cela sort du champ de mes compétences.

[A voir en vidéo sur Futura]

[Paraboloide_Hyperbolique]

Bonsoir,

Regardez peut-être du côté de l'algorithme de Lloyd... https://en.wikipedia.org/wiki/Lloyd%27s_algorithm

[phuphus]

Bonsoir,

Pourquoi ne pas définir des seuils pour isoler les groupes. Si les groupes sont aussi marqués que dans l'échantillon du premier message, ca ne devrait pas poser de problèmes insurmontables.

Il doit peut-être exister des outils de traitements statistiques pour traiter ce genre de problème, mais cela sort du champ de mes compétences.

Par exemple avec un cladogramme, il suffit ensuite de déplacer une limite pour naturellement créer le nombre de groupes souhaités.

[cherbe]

J'effectue des mesures analogiques (en l’occurrence je mesure des délais en microsecondes), et je me retrouve avec une liste de valeurs, dans lesquelles je dois reconnaître des valeurs (probablement des bits, mais il pourrait y avoir plus de 2 "valeurs absolues" possibles.
Par exemple, j'ai une liste telle que ci-dessous :
340
336
328
348
1060
1072
332
1024
340
1048
352
1082
342

Bonjour
La solution "propre", c'est de se tourner vers les outils statistiques de classification.
Voici une solution certainement pas très orthodoxe pour un statisticien mais simple à mettre en œuvre et qui fonctionne pour ce jeu de données.
Tu trie par ordre croissant ;
tu calcule la moyenne générale ;
tu fais le calcul suivant pour chaque donnée du tableau : donnée-moyenne
la 1ère valeur négative rencontrée est la 1ère valeur du second groupe. Son rang (position dans le tableau) est le rang discriminant.

[Jack]

et s'il y a plus de 2 groupes?

[cherbe]

et s'il y a plus de 2 groupes?

Ca marche pô !
Mais la question initiale portait sur 2 groupes seulement.
(belle pirouette n'est-ce pas ?)

[sierramike]

Salut cherbe,

Merci pour ton explication mais je me cite :

Sachant qu'à priori, je n'ai aucune idée de ce que je vais mesurer, il y aura peut être 3 ou 4 groupes de valeurs, et peut être qu'une prochaine fois les "groupes" seront plus proches, par exemple 700-750 et 900-950.

Sinon merci également aux autres pour vos suggestions, je vais essayer de comprendre l'algorithme de Lloyd-Max, je sens qu'il va me falloir un peu d'aspirine pour le faire passer vu ce que j'ai lu sur Wikipedia !!!

Je regarderai aussi le cladogramme, pour comprendre.

Pour l'instant j'ai implémenté mon algorithme des "groupes", en définissant une tolérance de 10%, et c'est bon, j'identifie bien mes groupes, mais dans ma quête de perfection je vais quand même regarder les algos suggérés !

[Jack]

Ca marche pô !
Mais la question initiale portait sur 2 groupes seulement.
(belle pirouette n'est-ce pas ?)

yes it is.

[Paraboloide_Hyperbolique]

Sinon merci également aux autres pour vos suggestions, je vais essayer de comprendre l'algorithme de Lloyd-Max, je sens qu'il va me falloir un peu d'aspirine pour le faire passer vu ce que j'ai lu sur Wikipedia !!!

L'algorithme de Lloyd n'est pas très compliqué (surtout en une dimension). En gros:

1. Pour n groupes, initialiser n points (les "centroïdes").
2. Pour chaque centroïde c_i, identifier et associer les points de données qui sont plus proches de c_i que de tout autre c_j.
3. Déplacer chaque centroïde c_i à la valeur moyenne des points de données qui lui sont associés.
4. Recommencer à partir de (2) jusqu'à convergence.

Bien sûr, le diable se cache dans les détails...

[sierramike]

Merci pour cette explication, pour les n points à initialiser, comment les choisir ? De manière aléatoire ?

[cherbe]

L'algorithme de Lloyd n'est pas très compliqué (surtout en une dimension). En gros:

1. Pour n groupes, initialiser n points (les "centroïdes").
2. Pour chaque centroïde c_i, identifier et associer les points de données qui sont plus proches de c_i que de tout autre c_j.
3. Déplacer chaque centroïde c_i à la valeur moyenne des points de données qui lui sont associés.
4. Recommencer à partir de (2) jusqu'à convergence.

Je comprends les grandes lignes mais est-ce automatisable ?
J'avais tenté une approche avec la moyenne mobile par groupes de trois valeurs. En partant des petits nombres vers les plus grands, ça marche bien pour le 1er groupe qui se distingue du reste avant l'observation 1024.
Seulement, la différence entre les moyennes mobiles des 3 grandes valeurs suivantes est telle qu'un classement automatique risque de faire 3 groupes pour ces 3 valeurs.

valeurs   moy mobile
328	
332	
336	    332
340	    336
340	    339
342	    341
348	    343
352	    347
1024	    575
1048	    808
1060	   1044
1072	   1060
1082	   1071

[phuphus]

Bonsoir,

petite correction : le terme générique pour "cladogramme" (qui est plutôt dédié à la classification du vivant) est "dendogramme". La méthode que tu cherches est décrite ici :
http://fr.wikipedia.org/wiki/Regroupement_hiérarchique

Regarde aussi le texte juste en dessous du dendogramme ici, qui illustre bien la capacité de l'ACH à regrouper en "classes" :
http://www.jybaudot.fr/Analdonnees/cah.html
Le nombre de classes n'est déterminé que par la position du trait en pointillés horizontal sur le lien précédent : c'est toi qui choisis. Sur la figure présentée, le trait sépare les "individus" de départ en 3 groupes. Tu le mets un poil plus haut, et tu as deux groupes. L'ordonnée du trait pointillé représente justement la distance limite que tu te fixes pour séparer tes groupes.

[sierramike]

L'algo que j'ai réalisé pour l'instant est le suivant :

- Soit L une liste de groupes
- Pour chaque élément e d'entrée

- Pour chaque groupe g de L

- Si e est compris entre g.Minimum et g.Maximum :

- incrémenter g.Compteur
- intégrer e à g.Moyenne (Nouvelle moyenne = Ancienne moyenne * (Compteur / (Compteur + 1)) + e / (Compteur + 1))
- g.Minimum = Min(g.Minimum, e - tolerance)
- g.Maximum = Max(g.Maximum, e + tolerance)

- Si e ne correspond à aucun groupe :

- créer un nouveau groupe g et l'ajouter à L
- g.Moyenne = e
- g.Minimum = e - tolerance
- g.Maximum = e + tolerance

En calant ma tolérance à 10% j'obtiens bien mes groupes bien comme il faut ... Mais, rien ne me dit que ma tolérance à 10% marchera avec tous les échantillons de données qui pourraient se présenter ...

[minushabens]

L'algorithme de Lloyd n'est pas très compliqué (surtout en une dimension). En gros:

1. Pour n groupes, initialiser n points (les "centroïdes").
2. Pour chaque centroïde c_i, identifier et associer les points de données qui sont plus proches de c_i que de tout autre c_j.
3. Déplacer chaque centroïde c_i à la valeur moyenne des points de données qui lui sont associés.
4. Recommencer à partir de (2) jusqu'à convergence.

Bien sûr, le diable se cache dans les détails...

pourquoi appelles-tu cela algorithme de Lloyd? C'est juste un algorithme de type EM, d'ailleurs plus connu en France sous le nom de "nuées dynamiques" et associé à Edwin Diday.

[Paraboloide_Hyperbolique]

Merci pour cette explication, pour les n points à initialiser, comment les choisir ? De manière aléatoire ?

Comme je le disais, "le diable se cache dans les détails". Un de ses détails est justement de trouver une "bonne" initialisation (un autre est le choix du critère d'arrêt).
Une initialisation aléatoire est une possibilité.

Pourquoi appelles-tu cela algorithme de Lloyd? C'est juste un algorithme de type EM, d'ailleurs plus connu en France sous le nom de "nuées dynamiques" et associé à Edwin Diday.

Parce que c'est sous ce nom que cet algorithme m'a été présenté durant mes études. Vu sa nature simpliste, il se peut qu'il est été (re)-découvert plusieurs fois dans différents contextes et, dès-lors, porter des noms différents.