59
Réduction de dimension pour l’exploration de données de grande dimension Sylvain Lespinats LIMA, CEA Mail: [email protected] Web: http://sy.lespi.free.fr/recherche/indexFR.html CEA, LIST, Multisensor Intelligence and Machine Learning Laboratory. F-91191 Gif-sur-Yvette, France. Séminaire APPRENTEO Jeudi 29 octobre 2009

Réduction de dimension pour l’exploration de données de ...sebag/Slides/Apprenteo/Lespinats09.pdf · Réduction de dimension pour l’exploration de données de grande dimension

Embed Size (px)

Citation preview

  • Rduction de dimension pour lexploration de donnes de grande dimension

    Sylvain Lespinats

    LIMA, CEA

    Mail: [email protected]: http://sy.lespi.free.fr/recherche/indexFR.html

    CEA, LIST, Multisensor Intelligence and

    Machine Learning Laboratory. F-91191

    Gif-sur-Yvette, France.

    Sminaire APPRENTEO

    Jeudi 29 octobre 2009

  • I. Gographie dun jeu de donnes

    II. Rduction de dimension partir des distances

    III. Evaluations des mappings

    IV. Rduction de dimension partir des rangs de voisinage

  • I. Gographie dun jeu de donnes

    III. Evaluations des mappings

    IV. Rduction de dimension partir des rangs de voisinage

    II. Rduction de dimension partir des distances

  • individus

    variables

    2D

    Organisation spatiale de ces donnes ?

    YX

    0.40130.9302

    -1.03460.2147

    0.2747-0.9722

    -0.076-0.9614

    -0.95240.3142

    0.0901-1.1365

    0.07800.9912

    -0.98640.0438

    0.87540.4251

    0.22960.9831

    0.9635-0.4061

    0.8788-0.3675

    0.8893-0.3076

    -0.6417-0.7666

    0.8115-0.5487

    0.7996-0.4557

    -1.0132-0.2359

    1.07750.0574

    -0.46970.8561

    -0.83550.6113

  • 0 1-1

    0

    1

    -1

    2D

    Organisation spatiale de ces donnes ?individus

    variables

    YX

    0.40130.9302

    -1.03460.2147

    0.2747-0.9722

    -0.076-0.9614

    -0.95240.3142

    0.0901-1.1365

    0.07800.9912

    -0.98640.0438

    0.87540.4251

    0.22960.9831

    0.9635-0.4061

    0.8788-0.3675

    0.8893-0.3076

    -0.6417-0.7666

    0.8115-0.5487

    0.7996-0.4557

    -1.0132-0.2359

    1.07750.0574

    -0.46970.8561

    -0.83550.6113

  • ZYX

    0.57950.26450.6657 0.40130.9302

    -0.34480.6246-0.4100-1.03460.2147

    -0.4146-0.6234-0.34870.2747-0.9722

    0.1135-0.4427-0.5187-0.076-0.9614

    -0.46460.6333-0.3191-0.95240.3142

    -0.1589-0.6133-0.52320.0901-1.1365

    0.12010.45660.53460.07800.9912

    -0.06710.5151-0.4713-0.98640.0438

    0.5778-0.22520.65030.87540.4251

    0.35040.37680.60630.22960.9831

    -0.6074-0.68480.27870.9635-0.4061

    -0.5014-0.62310.25560.8788-0.3675

    -0.4246-0.59840.29090.8893-0.3076

    0.7637-0.0624-0.7041-0.6417-0.7666

    -0.6913-0.68010.13140.8115-0.5487

    -0.5656-0.62760.17190.7996-0.4557

    0.37100.3886-0.6245-1.0132-0.2359

    0.0960-0.51000.56741.07750.0574

    -0.62420.66290.1932-0.46970.8561

    -0.79290.7234-0.1121-0.83550.6113

    individus

    variables

    5D

    ?

    Organisation spatiale de ces donnes ?

  • 5D

    Organisation spatiale de ces donnes ?

    ZYX

    0.57950.26450.6657 0.40130.9302

    -0.34480.6246-0.4100-1.03460.2147

    -0.4146-0.6234-0.34870.2747-0.9722

    0.1135-0.4427-0.5187-0.076-0.9614

    -0.46460.6333-0.3191-0.95240.3142

    -0.1589-0.6133-0.52320.0901-1.1365

    0.12010.45660.53460.07800.9912

    -0.06710.5151-0.4713-0.98640.0438

    0.5778-0.22520.65030.87540.4251

    0.35040.37680.60630.22960.9831

    -0.6074-0.68480.27870.9635-0.4061

    -0.5014-0.62310.25560.8788-0.3675

    -0.4246-0.59840.29090.8893-0.3076

    0.7637-0.0624-0.7041-0.6417-0.7666

    -0.6913-0.68010.13140.8115-0.5487

    -0.5656-0.62760.17190.7996-0.4557

    0.37100.3886-0.6245-1.0132-0.2359

    0.0960-0.51000.56741.07750.0574

    -0.62420.66290.1932-0.46970.8561

    -0.79290.7234-0.1121-0.83550.6113

    individus

    variables

  • Une carte pour exprimer la "gographie" des donnes

  • Projection linaire ou non-linaire

    linaire non-linaire

  • Multi Dimensional Scaling: usages

    Visualisation des donnes de plus de 3 dimensions.

    Visualisation de donnes issues despace non-euclidien.

    Plongement de donnes dans un espace vectoriel.

    Prtraitement (pour contourner le flau de la dimension).

  • Visualisation des donnes de plus de 3 dimensions.

    Visualisation de donnes issues despace non-euclidien.

    Plongement de donnes dans un espace vectoriel.

    Prtraitement (pour contourner le flau de la dimension).

    Multi Dimensional Scaling: usages

    Digression: le flau de la dimension

    1) Dsertification de lespace

    2) Dcroissance du volume de la boule unit

    3) Dpeuplement du centre des hyper-volumes

    4) Concentration de la mesure

  • Visualisation des donnes de plus de 3 dimensions.

    Visualisation de donnes issues despace non-euclidien.

    Plongement de donnes dans un espace vectoriel.

    Prtraitement (pour contourner le flau de la dimension).

    Multi Dimensional Scaling: usages

    Digression: le flau de la dimension

    1) Dsertification de lespace

    2) Dcroissance du volume de la boule unit

    3) Dpeuplement du centre des hyper-volumes

    4) Concentration de la mesure

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

  • I. Gographie dun jeu de donnes

    II. Rduction de dimension partir des distances

    III. Evaluations des mappings

    IV. Rduction de dimension partir des rangs de voisinage

  • les MultiDimensional ScalingsACP, ACC, Isomap, Sammons mapping, LLE,

    MDS :

    Une mthode possible :

    "Projection" (souvent non-linaire) qui

    prserve les distances entre objets (en

    avantageant les distances courtes).

    On connat les distances entre objets.

    On cherche une configuration de points

    dans lespace de reprsentation qui

    prserve "au mieux" ces distances.

  • Donnes dorigine(3D)

    mapping 2D (Analyse en composantes principales)

    mapping 2D (Analyse en composantes curvilignes)

    dij = distance observe

    entre i et j

    ij = output distance dans la

    reprsentation

    Dfauts:"faux-voisinages" et "dchirements"

  • Donnes dorigine(3D)

    mapping 2D (Analyse en composantes principales)

    mapping 2D (Analyse en composantes curvilignes)

    Faux voisinage

    dij = distance observe

    entre i et j

    ij = output distance dans la

    reprsentation

    dij grand et ij petit

    Dfauts:"faux-voisinages" et "dchirements"

  • Donnes dorigine(3D)

    mapping 2D (Analyse en composantes principales)

    mapping 2D (Analyse en composantes curvilignes)

    Faux voisinage

    dchirement

    dij grand et ij petit dij petit et ij grand

    dij = distance observe

    entre i et j

    ij = output distance dans la

    reprsentation

    Dfauts:"faux-voisinages" et "dchirements"

  • ( ) ( )ijij

    ji

    ijij oudfd =,

    2

    f(x) est grand si x est petit.

    Pour que ij se

    rapproche de dij. Poids pour donner lavantage

    la prservation des voisinages

    MDS: Fonctions de cout

  • ( ) ( )ij

    ji

    ijij dfd =,

    2 (Sammons mapping)

    J.W. Sammon, 1969.

    MDS: Fonctions de cout

  • ( ) ( )ij

    ji

    ijij dfd =,

    2 (Sammons mapping)

    Hypothse 1, dchirement :dij petit et ij grand.

    MDS: Fonctions de cout

  • ( ) ( )ij

    ji

    ijij dfd =,

    2 (Sammons mapping)

    Hypothse 1, dchirement :dij petit et ij grand.

    (dij ij)2 grand et f(dij) grand

    Fortement pnalis.

    MDS: Fonctions de cout

  • ( ) ( )ij

    ji

    ijij dfd =,

    2 (Sammons mapping)

    Hypothse 1, dchirement :dij petit et ij grand.

    (dij ij)2 grand et f(dij) grand

    Fortement pnalis.

    Hypothse 2, faux voisinage :dij grand et ij petit.

    (dij ij)2 grand et f(dij) petit

    Faiblement pnalis.

    MDS: Fonctions de cout

  • ( ) ( )ij

    ji

    ijij fd =,

    2 (analyse en composantes

    curviligne)

    Faux voisinage Fortement pnalis.

    Dchirement Faiblement pnalis.

    P. Demartines P. et J. Hrault , 1997.

    MDS: Fonctions de cout

  • Originalits:

    1) Elle pnalise les 2 types derreurs ("faux voisinages" ET

    "dchirements").

    2) Elle est adapte aux caractristiques des donnes de grande

    dimension (concentration de la mesure).

    S.L., M. Verleysen, A. Giron et B. Fertil, 2007.

    DD-HDS: Data-Driven High Dimensional Scaling

  • ( ) ( )ijij

    ji

    ijij oudfd =,

    2

    1) Pnalisation des "faux voisinages" OU des "dchirements".

    DD-HDS: Data-Driven High Dimensional Scaling

  • ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    ( )( )ijijdf ,min

    DD-HDS: Data-Driven High Dimensional Scaling

    1) Pnalisation des "faux voisinages" ET des "dchirements".

  • 1) Pnalisation des "faux voisinages" ET des "dchirements".

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    2) Risques dus au flau de la dimension.

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

    ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    ( )( )ijijdf ,min

    DD-HDS: Data-Driven High Dimensional Scaling

  • 1) Pnalisation des "faux voisinages" ET des "dchirements".

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    2) Risques dus au flau de la dimension.

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

    ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    ( )( )ijijdf ,min

    DD-HDS: Data-Driven High Dimensional Scaling

  • 1) Pnalisation des "faux voisinages" ET des "dchirements".

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    2) Risques dus au flau de la dimension.

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

    ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    ( )( )ijijdf ,min

    DD-HDS: Data-Driven High Dimensional Scaling

  • 1) Pnalisation des "faux voisinages" ET des "dchirements".

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    2) Risques dus au flau de la dimension.

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

    ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    ( )( )ijijdf ,min

    DD-HDS: Data-Driven High Dimensional Scaling

  • 1) Pnalisation des "faux voisinages" ET des "dchirements".

    On relche les contraintes si les distances longues dans

    lespace dorigine ET dans lespace de reprsentation

    ( ) ( )ijij

    ji

    ijij oudfd =,

    2( ) ( )ijij

    ji

    ijij oudfd =,

    2

    ( )( )ijijdf ,min

    2) Risques dus au flau de la dimension.

    0

    500

    1000

    1500

    2000

    2500

    0 5 10 15 20 25

    dim = 1

    dim = 2 dim = 5dim = 10

    dim = 20dim = 50

    dim = 200

    DD-HDS: Data-Driven High Dimensional Scaling

  • Donnes 3D

    Exemple de projection : le cube ouvert

  • Donnes 3DACP

    Isomap

    LLE

    CCASammonsmapping

    Exemple de projection : le cube ouvert

  • Donnes 3DACP

    Isomap

    LLE

    CCASammonsmapping

    DD-HDS

    Exemple de projection : le cube ouvert

  • I. Gographie dun jeu de donnes

    III. Evaluations des mappings

    IV. Rduction de dimension partir des rangs de voisinage

    II. Rduction de dimension partir des distances

  • Les dfauts dun planisphre

  • dchirements

    Les dfauts dun planisphre

  • dchirements

    Les dfauts dun planisphre

  • 1) Analyse globale.

    2) Evaluation locale du niveau derreur.

    3) Etudes des proximits selon un point de vue.

    Analyse des dfauts: une stratgie en 3 tapes

  • Y a-t-il des dfaut dans une carte: le diagramme de Shepard

    Permet de

    visualiser la

    qualit dune

    reprsentation

    ij

    dij

  • ij

    dij

    Permet de

    visualiser la

    qualit dune

    reprsentation

    Y a-t-il des dfaut dans une carte: le diagramme de Shepard

    dchirements

    faux voisinages

  • Donnes 3DACP

    Isomap

    LLE

    CCASammonsmapping

    DD-HDS

    Exemple de projection : le cube ouvert

  • Exemple de projection : le cube ouvert

    Isomap

    LLE

    SammonsmappingCCA

    ACPDonnes 3D

    DD-HDS

  • Isomap

    LLE

    SammonsmappingCCA

    ACPDonnes 3D

    DD-HDS

    0.75 0.8 0.85 0.9 0.95 10.985

    0.99

    0.995

    1

    ACP

    CCA

    DD-HDS

    Isomap

    LLE

    Sammonsmapping

    Trustworthiness

    Continuity

    J. Venna J. et S. Kaski, 2001.

    Exemple de projection : le cube ouvert

  • Indices quantifiant les faux voisinages et dchirements

    ( ) ( )ij

    ji

    ijij dfd =,

    2

    ( ) ( )ij

    ji

    ijij fd =,

    2

    Sensible aux dchirements

    Sensible aux faux-voisinages

    Ils peuvent tre mesurs localement

    ( ) ( )ijj

    ijiji dfd =2 ( ) ( )ij

    j

    ijiji fd =2

  • Isomap

    Sammonsmapping

    DD-HDS

    CCA

    ACP

    LLE

    Exemple de projection : le cube ouvert

  • ACP

    Isomap

    LLE

    Sammonsmapping

    DD-HDS

    CCA

    Fortes erreurs

    Faibles erreurs

    S.L. et M. Aupetit, 2009.

    Exemple de projection : le cube ouvert

  • ACP

    Isomap

    LLE

    Sammonsmapping

    DD-HDS

    CCA

    Fortes erreurs

    Faibles erreurs

    S.L. et M. Aupetit, 2009.

    Exemple de projection : le cube ouvert

  • M. Aupetit, 2007.

    Niveau de gris : distance de la rfrence aux autres donnes.

    Proximits selon un point de vue

  • 1) Analyse globale.

    2) Evaluation locale du niveau derreur.

    3) Etudes des proximits selon un point de vue.

    Analyse des dfauts: une stratgie en 3 tapes

  • I. Gographie dun jeu de donnes

    III. Evaluations des mappings

    IV. Rduction de dimension partir des rangs de voisinage

    II. Rduction de dimension partir des distances

  • Nous constatons que sur certains jeux de donnes complexes,

    les MDS expriment mal certaines relations entre donnes.

    Exemple de donnes: 10D, 4 classes

    gnres par des tirages gaussiens

    centrs sur les sommets dune

    pyramide rgulire (variance plus

    leve sur une dimension).

    Grande dimension Anisotropie -

    Classes gale distance les unes des

    autres - Distances intra-classes et

    inter-classes du mme ordre de

    grandeur.

    Limites des MDS

  • ACP DD-HDS

    4 classes trs diffrencies que lon retrouve mal travers les MDS

    Limites des MDS

  • RankVisu : prservation des rangs de voisinage

    Rang 1 -> le plus proche voisin

    Rang 2 -> le 2eme plus proche voisin

    Objectif: prservation des rangs de voisinage en

    avantageant les petits rangs.

    S.L., B. Fertil, P. Villemain et J. Hrault, 2009.

  • DD-HDS

    ACP

    Chaque point est

    connect ses 5 plus

    proches voisins

    Les 4 groupes anisotropes

  • ACP

    RankVisu

    Les 4 groupes anisotropes

    Chaque point est

    connect ses 5 plus

    proches voisins

    DD-HDS

  • "Wine data"

    Groupe 1Groupe 2Groupe 3

    RankVisuDD-HDS

    mesures chimiques sur les vins de 3 producteurs

  • Exemple sur le "swiss roll"

    DD-HDS

    RankVisu

    Espace dorigine

  • Conclusion

    Les rductions de dimension permettent de dcouvrir

    lorganisation spatiale des donnes.

    Jai dtaill ici deux mthodes particulirement

    efficaces quand on est face des donnes de grande

    dimension.

    Lvaluation des rsultats est essentielle. Nous

    prconisons une procdure en 3 temps: valuation

    globale locale selon quelques points de vue.