Scribd Logo
Importer

Bienvenue sur Scribd !

  • 134 vues

    Cartes Topologiques

    Transféré par

    abbouamine
    Le document présente les cartes topologiques auto-organisatrices de Kohonen pour la quantification vectorielle de données. Il décrit le principe des cartes topologiques, la fonction de voisinage et l'algorithme d'apprentissage pour minimiser une fonction de coût en respectant la topologie.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Cartes Topologiques

    Transféré par

    abbouamine
    134 vues12 pages
    Le document présente les cartes topologiques auto-organisatrices de Kohonen pour la quantification vectorielle de données. Il décrit le principe des cartes topologiques, la fonction de voisinage et l'algorithme d'apprentissage pour minimiser une fonction de coût en respectant la topologie.

    Description originale:

    Intelligence artificielle

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente les cartes topologiques auto-organisatrices de Kohonen pour la quantification vectorielle de données. Il décrit le principe des cartes topologiques, la fonction de voisinage et l'algorithme d'apprentissage pour minimiser une fonction de coût en respectant la topologie.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    134 vues12 pages

    Cartes Topologiques

    Transféré par

    abbouamine
    Le document présente les cartes topologiques auto-organisatrices de Kohonen pour la quantification vectorielle de données. Il décrit le principe des cartes topologiques, la fonction de voisinage et l'algorithme d'apprentissage pour minimiser une fonction de coût en respectant la topologie.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 12

    CARTES TOPOLOGIQUES

    1ère séance

    Introduction
    • Modèles à apprentissage non supervisé
    → Regrouper les patients qui semblent avoir des analyses médicales semblables
    → Identifier les différents types de consommateurs (comportement d’achats)
    • But : analyser des données d’observation par leur structures.
    • Kohonen : Représentation de données multidimensionnelles de grande taille.
    ⋄ Projection de partitions
    → selon une structure de voisinage en dimension 1, 2 ou 3
    ⋄ Ordre topologique
    → les distances entre observations sont directement visibles sur la carte

    RCP208 1 2017-2018
    Quantification Vectorielle
    D : espace des données d’observation (notées z) de dimension n.
    A : ensemble d’apprentissage A = {zi , i = 1, . . . , N }
    On a : A ⊂ D ⊂ Rn

    Réduire l’information de D :
    • En la résumant par un ensemble de p référents
    W = {wc ; c = 1, ..., p}
    • En réalisant une partition de D en p sous-ensembles par l’intermédiaire
    d’une fonction d’affectation χ χ
    χ : D → {1, 2, . . . , p} ensemble des indices

    P = {P1 , P2 , . . . , Pp } observation z 1 2 . . . c . . . p
    Pc = {z ∈ D/χ(z) = c} référent wχ (z)= w
    c

    espace des observations et des référents

    RCP208 2 2017-2018
    Différentes Méthode de Quantification Vectorielle
    ⇓
    Différentes détermination de W et χ
    • Méthode des K-moyennes
    • Cartes topologiques auto-organisatrice de Kohonen (SOM)
    • Cartes topologiques probabilistes (PRSOM)
    • ...

    + Chaque méthode correspond à la minimisation


    d’une fonction de coût spécifique
    + Algorithme en 2 étapes :
    - Affectation −→ fonction χ
    - Minimisation −→ référents W

    RCP208 3 2017-2018
    Méthode des k-moyennes
    ∑
    • Inertie intra-groupes : Ic = ∥zi − wc ∥2
    zi ∈A

    • Minimiser la somme des inerties locales par rapport à χ et W


    ∑
    I(W, χ) = Ic
    c
    Soit, pour faire ressortir χ:
    ∑ ∑ ∑
    I(W, χ) = Ic = ∥zi − wc ∥2
    c c zi ∈A
    χ(zi )=c

    • L’inertie Ic représente l’erreur de quantification obtenue si l’on remplace chaque


    observation de Pc par son référent wc

    • Minimisation itérative de l’inertie qui fixe alternativement la partition (χ) puis


    recalcule W
    RCP208 4 2017-2018
    Minimisation de l’inertie I(W, χ)
    • Phase d’affectation
    Pour un ensemble W de référents fixe, la minimisation de I par rapport à χ
    s’obtient en affectant chaque observation z au référent wc selon la nouvelle
    fonction d’affectation χ
    2
    χ(z) = arg min ∥z − wr ∥ (1)
    r

    • Phase de minimisation
    La fonction χ est fixée. La fonction I(W,χ) est quadratique et convexe par
    rapport à W. Le minimum global est atteint pour :
    ∑
    ∂I
    ∂W
    = ∂I
    [ ∂w , ∂I
    1 ∂w2
    , · · · , ∂I T
    ∂wp
    ] =0 ⇒ ∀c, (zi − wc ) = 0
    zi ∈Pc
    ⇓
    ∑
    zi
    zi ∈Ac
    Les p nouveaux référents −→ wc = nc
    (2)

    RCP208 5 2017-2018
    Algorithme des k-moyennes
    1. Initialisation
    - t=0 : indice d’itération
    - fixer le nombre maximum d’itérations : Niter
    - choisir les p référents initiaux (en général d’une manière aléatoire) : Wt

    2. Etape de minimisation itérative t (à partir de 1),


    (à l’itération t, l’ensemble des référents W t−1 de l’étape précédente est connu)
    • Phase d’affectation : mise à jour de la fonction d’affectation χt associée à
    W t−1 : on affecte chaque observation z au référent le plus proche (1).
    • Phase de minimisation : calcul des nouveaux référents W t en appliquant
    l’équation (2).
    3. Répéter l’étape itérative jusqu’à atteindre t > Niter itérations ou une
    stabilisation de I.

    RCP208 6 2017-2018
    Sensibilité aux conditions initiales

    RCP208 7 2017-2018
    Comportement de l’algorithme des k-moyennes
    en fonctions des densités sous-jacentes

    (a) Données simulées selon deux distributions gaussiennes de matrice de


    variance-covariance différentes.
    (b) Référents et partition obtenue à la convergence avec 2 référents
    (c) Avec 5 référents

    RCP208 8 2017-2018
    Carte topologique

    • L’ensemble des indices est maintenant ordonné


    • Il s’agit d’un espace discret (C ) de faible dimension
    à des fins de visualisation (1-D, 2-D).
    • C ensemble de neurones connectés
    par une structure de graphe non-orienté
    muni d’une distance discrète δ sur C
    et d’une structure de voisinage :

    Vc (d) = {r ∈ C, δ(c, r) ≤ d}
    ↓
    Voisinage d’ordre d

    δ(c, r) = longueur du plus court chemin


    entre c et r sur le graphe

    RCP208 9 2017-2018
    Quantification par la carte
    • Chaque neurone c de C est associé à un vecteur référent wc de l’espace des données D
    • L’apprentissage approxime la densité sous-jacente des données tout en cherchant à
    respecter une contrainte de conservation de la topologie de la carte C
    • Deux neurones c et r ”voisins” par rapport à la topologie discrète de la carte C sont
    associés à deux vecteurs référents wc et wr ”proches” dans l’espace des données D.
    + NOTION DE CONSERVATION DE LA TOPOLOGIE

    Les indices des référents


    sont ordonée par la topologie

    RCP208 10 2017-2018
    Fonction de Voisinage

    RCP208 11 2017-2018
    Apprentissage
    Apprentissage de la carte = minimisation d’une fonction de coût
    ∑ ∑ 2
    T
    Jsom (χ, W) = K T (δ(c, χ(zi ))∥zi − wc ∥
    zi ∈A c∈C

    La valeur de T détermine la taille du voisinage


    VcT = {r ∈ C/K T (δ(c, r)) > α}
    Remarque : T=0 ⇒ fonction de coût des K-moyennes

    Le seuil α gère l’ordre des valeurs significatives prises en compte par le calcul.

    Chaque observation z calcul une distance généralisée à l’ensemble des neurones de


    la carte par l’intermédiaire de la fonction K T
    ∑ 2
    T
    d (zi , wχ(zi ) ) = KT (δ(c, χ(zi ))∥zi − wc ∥
    c∈C

    RCP208 12 2017-2018

    Vous aimerez peut-être aussi