barycentre sur n dimensions?

Version imprimable

23/01/2008, 16h45
Giansolo

barycentre sur n dimensions?

Bonjour à tous,

Je me pose la question suivante:

J'ai un ensemble de n descripteurs pour m mesures et je souhaiterais au final calculer la 'distance' de chaque mesure au 'centre' des n descripteurs afin de trouver quels sont les mesures atypiques.

Je ne sais pas trop à quelle méthode recourir pour le moment, mais je me demandais si calculer le barycentre en n dimensions des n descripteurs puis la distance euclidienne des descripteurs de chaque mesure à ce centre serait une bonne idée? Ainsi les descripteurs "loin" serait atypiques (si les descripteurs sont suffisamment pertinents).

Ensuite une visualisation consisterait à faire une PCA sur les 2 ou 3 descripteurs les plus explicatifs, et à les visualiser...

J'imagine qu'il existe sans doute des méthodes plus adaptées à ce genre de problèmatique, peut-être pouvez vous me suggerer quelque chose?

Merci!
Gian
23/01/2008, 17h56
souviron34

ooppss pas tres clair...

Qu'entends-tu par descripteur ?

La solution (voir dans Traitements d'image une discussion sur RGB) n'est PAS la distance minimale au barycentre, mais les points qui minimisent CHACUNE des distances....
23/01/2008, 19h09
souviron34

ok voici le lien vers le fil en question :

http://www.developpez.net/forums/sho...d.php?t=468351
23/01/2008, 20h32
pseudocode

Citation:

Envoyé par Giansolo

Je ne sais pas trop à quelle méthode recourir pour le moment, mais je me demandais si calculer le barycentre en n dimensions des n descripteurs puis la distance euclidienne des descripteurs de chaque mesure à ce centre serait une bonne idée? Ainsi les descripteurs "loin" serait atypiques (si les descripteurs sont suffisamment pertinents).

Si tu as un point atypique a l'infini (ou assimilé) ton barycentre ne sera pas au centre de la distribution. Et donc tes calculs de distances seront faussés.

Mais l'idée est bonne. Il suffit d'une légère amélioration: la methode "mean shift" pour trouver le centre de la distribution. ;)
23/01/2008, 22h03
Zavonen

Je pense être compétent sur les problèmes de barycentres quelque soit la dimension, mais je ne comprends malheureusement rien au vocabulaire employé.
'Descripteur' ?????
'PCA' ????
'Les plus représentatifs' ??? de quoi ...
23/01/2008, 22h46
PRomu@ld

Le domaine ici est la reconnaissance de formes.

Un descripteur, dans le domaine de la RDF ça correspond généralement à une mesure. Tu as différents descripteurs (géométriques, surfaciques, colorimétriques, statistiques, ...) qui te permettent de caractériser tes formes.

PCA, c'est plutôt ACP : Analyse en composantes principales. Ca permet de passer d'un système de représentation à N dimensions à un système à P dimensions (avec P <= N), tout en minimisant les pertes dues à ce changement de représentation. Ca permet de travailler sur moins de données en entrée (et surtout sur celles qui sont significatives).

Pour répondre au PO, je pense que tu pourrais calculer la variance (ou l'écart type) de chacune de tes mesures. Ensuite, si la distance d'une mesure est très loin du centre de ta classe (et surtout de manière bien supérieure à l'écart type de cette mesure), tu peux dire qu'elle est atypique.
24/01/2008, 02h23
Zavonen

Merci pour ces explications.
Par ailleurs, j'avais aussi cru reconnaitre la définition de cette bonne vieille 'variance'.
24/01/2008, 07h40
Matthieu Brucher

Si les descripteurs sont un peu loufoques, tu n'es pas dans un espace euclidien et dans ce cas, tu ne pourras pas trouver ceque tu cherches. Regarde sur ma page perso mes articles anglais à ce sujet.
24/01/2008, 14h29
Giansolo

eh bien eh bien!
merci pour toutes ces réponses...

Après relecture attentive de tout les replys au topic, je vais peut-être éclaircir ma problématique.

Je cherche à caractériser certaines données biologiques atypiques (sans rentrer dans les détails). L'idée est d'introduire un ensemble de n descripteur pour chaque donnée; des descripteurs que nous estimons pertinents de "l'atypicité" de ces données.
Par exemple les données atypiques auront des valeurs de descripteurs très différents de la valeurs des descripteurs des autres données. Ces données sont caractérisées par le fait qu'elles sont "loin" des autres descripteurs.
Je précise ceci est vrai pour l'ensemble de nos descripteurs.

Etant donné le grand nombre de m données (donc de n*m descripteurs) dont nous disposons, nous pensons qu'en utilisant 3 descripteurs qu'on représenterait en 3D (l'espace des descripteurs en quelques sorte), on observerait un nuage avec beaucoup de données représentées au centre, et quelques une très éloignées du centre (noyau?) du nuage.

Je cherche donc à trouver les valeurs qui sont en dehors de l'enveloppe du nuage contenant XX% des données. Sauf que je travaille en dimension n.

Ceci dit, peut-etre qu'il pourrait-être intéressant de faire du "mean shift" sur les n descripteurs... ? il faut que je regarde plus en détail comment ca fonctionne...
24/01/2008, 14h33
Matthieu Brucher

Rien ne sert de réduire les données, il faut partir correctement. Ce que je veux dire par là, c'est que des descripteurs ne sont pas dans un espace euclidien et donc que tu vas devoir utiliser des techniques comme le mean-shift pour tenter de contourner ce problème.
Utilise tes données correctement.
24/01/2008, 15h21
pseudocode

Citation:

Envoyé par Giansolo

Ceci dit, peut-etre qu'il pourrait-être intéressant de faire du "mean shift" sur les n descripteurs... ? il faut que je regarde plus en détail comment ca fonctionne...

C'est le principe qu'on utilise pour faire de la segmentation d'image (google: "Robust Analysis of Feature Spaces"). Dans ton cas la partie "segmentation" n'a pas d'interet, mais le principe de l'etude des distributions reste valide.

La difference c'est que tu recherches les "features" isolées, alors que pour la segmentation on cherche à regrouper les "features" proches.
24/01/2008, 15h28
ToTo13

Bonjour,

et si tu commencais par étudier la pertinence de tes descripteurs ?
- Commencer par regarder la distribution de chaque descritpeurs. Cela te donnera déjà une liste de ce que l'on appelle les "OutLiers".
- Ensuite regarder le ChiSquare de chacun des descripteurs afin de voir s'il est pertinent pour ton problème.
30/01/2008, 16h23
Giansolo

Mean shift

J'ai eut le temps de regarder un peu l'algorithme mean shift, et d'après ce que j'ai compris, cet algorithme permet d'évoluer un minimum local (un mode) d'un nuage de points dans n dimensions à l'aide du nombre de points contenus dans l'hypersphère.

Il faut évaluer un vecteur mean shift, à partir d'une fonction noyau (par exemple noyau d'Epanechnikov) et effectuer l'algo suivant:
(1): on prend un point x du nuage,
(2): calcul du vecteur mean shift(x)
(3): x = x + mean shift(x)
(4): -> (2)

on recalcule itérativement le vecteur du mean shift(x) (départ aléatoire) qui nous fournit la bonne direction (gradient contenu dans le mean shift) vers le minimum local.En gros, sauf erreur, je pense que ca marche comme ca.

Cette méthode à l'air parfaitement adaptée a mon problème pour trouver le centre du nuage, quelques questions cependant:

1- quel noyeau choisir? j'ai vu des choses sur les noyau adaptatifs, mais je n'ai pas encore eut le temps de jeter un oeil dedans, si vous pouviez m'aiguiller sur le sujet, ca pourrait m'être grandement utile.

2- Ok je comprends le principe en 2 dimensions, mais comment généraliser en n dimensions? (je travaille avec une matrice de descripteurs n*m),

3- J'ai l'impression que la fonction est récursive, le gradient du vecteur mean shift étant le gradient estimé de la fonction de densité du nuage qui fait appel au vecteur mean shift (?) je dois me planter quelque part...

merci pour les informations que vous pourrez apporter et qui pourront m'éclairer un peu plus sur le sujet...

Gian
30/01/2008, 16h35
Matthieu Brucher

La densité du nuage ne dépend pas du mean-shift. Le principe est que tu as un champ de noyaux (gaussiens en général) et d'après tes données, tu recherches le point le plus haut proche de toi.

Mais comme dit, vu que tu as des données dans un espace de très grande dimension, tu ferais mieux... de les compresser.
30/01/2008, 16h45
pseudocode

Mince. Une interro et j'ai pas révisé !

Citation:

Envoyé par Giansolo

1- quel noyeau choisir? j'ai vu des choses sur les noyau adaptatifs, mais je n'ai pas encore eut le temps de jeter un oeil dedans, si vous pouviez m'aiguiller sur le sujet, ca pourrait m'être grandement utile.

Ça dépend des caractéristiques que tu as choisi pour construire ton espace. Le plus simple c'est de considérer que les caractéristiques ne sont pas corrélées et d'étudier les n distributions séparément.

Citation:

2- Ok je comprends le principe en 2 dimensions, mais comment généraliser en n dimensions? (je travaille avec une matrice de descripteurs n*m)

:koi: ? Bah le principe ne dépend pas de la dimension:

1. choisir un point P (au pif)
2. calculer le barycentre des points au voisinage de P
3. Déplacer P vers le barycentre
4. retour au 2 jusqu'a convergence

Citation:

3- J'ai l'impression que la fonction est récursive, le gradient du vecteur mean shift étant le gradient estimé de la fonction de densité du nuage qui fait appel au vecteur mean shift (?) je dois me planter quelque part...

hum... itérative oui, mais recursive ???

2 pièce(s) jointe(s)

Mean shift

Voilà j'ai implémenté l'algorithme Mean Shift en matlab de manière simple pour comprendre comment ca marche, et ca à l'air de bien fonctionner en 2d, en 3d et à priori en nd.

Je poste le détail ici:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 %MEAN SHIFT---------- %initialization: H = 10; Threshold = 1; %1 - prend un point au hasard: Xcenter = XX(ceil(rand()*n),:); XOldcenter = 0; while(dist_(Xcenter,XOldcenter) > Threshold) XOldcenter = Xcenter; %points in the hyperball %(whose distance from the center X is less than R (H)) k=1; for i=1:length(XX) %for all dims: vec_dis = dist_(Xcenter, XX(i,:)); %Belong to the cluster?: vecto < H? if(vec_dis < H) clustered(k) = i; k = k+1; end; end; %2 - calcul du vecteur Mh, pour les points appartenants au cluster: Mh = mean(XX(clustered,:)) - Xcenter; %3 - Move the center of the hypersphere : x <- x + Mh(x) Xcenter = Xcenter + Mh; %DEBUG VISU: plot(X,Y,'r+'); hold on; plot(Xcenter(:,1),Xcenter(:,2),'b*'); for k = 1:length(clustered) plot(XX(clustered(k),1),XX(clustered(k),2),'kx'); end; hold off; pause; end;
dist_ calcul la distance euclidienne en n dim.
Le noyau est un noyau d'Epanechnikov, donc
Mh = moyenne(des points appartenant à l'hypersphère) - centre de la sphère
et bonus, c'est en franglais.

Quelques question restantes :
1 - Toujours au niveau des noyaux, je pense que mes descripteurs (et donc mes dimensions sont corrélées), dois-je choisir un noyau plus adapté?
2 - Comment choisir le rayon de l'hypersphère? j'ai cru lire qu'il dépendait de la taille du nuage, du coup je pense que je vais normaliser tout les descripteurs pour avoir quelque chose de plus correct.

Je joins la première et la dernière étape de l'algo pour une projection 2d avec des X,Y pris dans une loi normale.

31/01/2008, 23h35
pseudocode

Citation:

Envoyé par Giansolo;29092711 - Toujours au niveau des noyaux, je pense que mes descripteurs (et donc mes dimensions sont corrélées), dois-je choisir un noyau plus adapté?[/QUOTE

Tu peux essayer de faire une ACP sur tous tes descripteurs pour, à la fois garder les principaux et aussi réduire la corrélation.

Citation:

2 - Comment choisir le rayon de l'hypersphère? j'ai cru lire qu'il dépendait de la taille du nuage, du coup je pense que je vais normaliser tout les descripteurs pour avoir quelque chose de plus correct.

En image (2D) on calcule la racide de la trace de la matrice de covariance. En dimension N, l'equivalent serait le produit des ecart-types dans chaque dimension. Ensuite le rayon est proportionnel a cette grandeur (0.2 a 0.5 fois pour les images).

Je joins la première et la dernière étape de l'algo pour une projection 2d avec des X,Y pris dans une loi normale.