IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

barycentre sur n dimensions?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut 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

  2. #2
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    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....

  3. #3
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    ok voici le lien vers le fil en question :

    http://www.developpez.net/forums/sho...d.php?t=468351

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Giansolo Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    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 ...
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  6. #6
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    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.

  7. #7
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 77
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Par défaut
    Merci pour ces explications.
    Par ailleurs, j'avais aussi cru reconnaitre la définition de cette bonne vieille 'variance'.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  8. #8
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  9. #9
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    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...

  10. #10
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  11. #11
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    Citation Envoyé par Giansolo Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  12. #12
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  13. #13
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut 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

  14. #14
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  15. #15
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut Mince. Une interro et j'ai pas révisé !
    Citation Envoyé par Giansolo Voir le message
    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.

    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)
    ? 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

    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 ???
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.
    Images attachées Images attachées   

  17. #17
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Par défaut
    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.

    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. [Excel] Figer les volets sur 3 "dimensions"
    Par ancel17 dans le forum Excel
    Réponses: 5
    Dernier message: 11/12/2013, 11h25
  2. Réponses: 1
    Dernier message: 15/07/2008, 20h54
  3. Réponses: 2
    Dernier message: 08/07/2008, 11h28
  4. Conseil sur les dimensions d'un mapping
    Par Asmod_D dans le forum Ogre
    Réponses: 3
    Dernier message: 05/07/2008, 23h52
  5. Facteur d'échelle sur les dimensions d'un graphique en 3D
    Par Ptit oui-oui dans le forum MATLAB
    Réponses: 2
    Dernier message: 28/11/2007, 17h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo