Cours - Quantification vectorielle, cartes de Kohonen

Ce chapitre correspond à 3 séances de cours.

[Diapositives du cours 1]

[Diapositives du cours 2]

[Diapositives du cours 3]

(cette page sera complétée avec les explications détaillées)

Introduction

Généralités

Les cartes topologiques ou auto-organisatrices font partie de la famille des modèles dits à «apprentissage non supervisé», c’est-à-dire qui s’appliquent sur des données dont on connaît le domaine sur lequel porte le recueil statistique, mais pour lesquelles les connaissances a priori ne sont pas totalement organisées. Par exemple, on peut avoir un recueil d’analyses médicales et ne pas avoir le diagnostique donné par le médecin (malade ou pas malade). On peut cependant vouloir regrouper les patients qui semblent avoir des analyses «semblables ou similaires».

Le but premier des cartes auto organisatrices est descriptif : les données étudiées ici sont des observations. Pour les analyser, on cherche à en comprendre la structure.

Les cartes topologiques ont été introduites pour la première fois par Kohonen qui cherchait à représenter des données multidimensionnelles et de grande taille. Pour y parvenir, Kohonen cherche à partitionner, par apprentissage, les données en groupements «similaires» dont la structure de voisinage peut être matérialisée et visualisable par un espace discret de faible dimension (1, 2 ou 3D) appelé «carte topologique».

Une observation est affectée à un groupe qui est localisé en un nœud de la carte. Les observations semblables ont la même projection, par contre, plus des observations sont dissemblables, plus elles seront associées à des groupes spatialement éloignés sur la carte. La distance entre les groupes est de ce fait directement calculable sur la carte. Les cartes auto-organisatrices rendent ainsi possible la comparaison des groupes qu’elles produisent.

Comme pour d’autres techniques de classification automatique (k-moyennes, \(\cdots\)), il s’agit donc de regrouper des données «similaires», mais la notion d’ordre topologique est un apport supplémentaire permis par les réseaux de neurones à apprentissage non supervisé : les distances entre observations sont directement visibles sur a carte.

Quantification Vectorielle

Notations et Définitions

Nous noterons
\({\mathcal D}\) : l’espace des données d’observation (notées \(z\)) supposées réelles et de dimension multiple (n).
\({\mathcal A}\) : un ensemble d’observations de taille \(N\) disponible pour l’apprentissage.
\[{\mathcal A}=\{{\mathbf z}_{i}, \; i=1,\ldots,N\}\]
\[{\mathcal A} \subset {\mathcal D} \subset {\mathcal R}^{n} | :math:`{\mathcal A}` est supposé statistiquement représentatif de :math:`{\mathcal D}`.\]

Les méthodes que nous allons présenter cherchent à réduire l’information contenu dans \({\mathcal D}\) :

  • en la résumant sous la forme d’un ensemble \({\bf\mathcal W}\) de \(p\) vecteurs de \({\mathcal D}\) appelés référents.

    \[{\mathcal W}=\{{\mathbf w}_{c}; c=1, \ldots ,p \}\]
  • en définissant une fonction d’affectation \(\mathbf \chi\) qui est une application de \({\mathcal D}\) dans l’ensemble des indices \(\{ 1, \ldots ,p \}\)

    \[\chi : {\mathcal D} \rightarrow \{1,2, \ldots,p \}\]

    Cette fonction d’affectation permet de réaliser une partition \(\mathcal P= \{P_{1},\ldots ,P_{c}, \ldots,P_{p} \}\) de \(\mathcal D\) en \(p\) sous ensembles, \(P_{c}= \{\mathbf{z}\in {\mathcal D} / \; \chi( \mathbf{z})=c \}\).

    Nous noterons \({\mathcal A}_{c} =P_{c} \cap {\mathcal A}\), le sous-ensemble des éléments de \({\mathcal A}\) d’indice \(c\), et \(n_{c}\) le nombre d’observations de \(\mathcal A\) qui appartiennent à \(P_{c}\) .

La figure suivante (voir Fig. 144) montre le principe général de la modélisation.

Principe général de la modélisation

Fig. 144 Principe général de la modélisation

  • Chaque observation \(\mathbf{z}\) est affectée à un indice \(c\) (parmi \(p\)) au moyen de la fonction d’affectation \(\chi\)

  • Cet indice permet de définir le référent \(\mathbf{w}_{c}\) qui est le représentant du sous ensemble des observations de \(P_{c}\) .

La connaissance de l’ensemble des vecteurs référents \({\bf\mathcal W}\) et de la fonction d’affectation \(\mathbf \chi\) détermine ce que l’on appelle une quantification vectorielle.


Il existe différentes méthodes de quantification vectorielle dont on rappelle qu’elles consistent à déterminer les référents \(\mathbf{w}\) représentant des partitions de l’espace des observations, et la fonction \(\chi\) utilisée pour associer une observation \({\mathbf z}\) à son référent. Dans l’exposé qui suit nous n’aborderons que les cartes topologiques auto-organisatrices. Le sigle SOM parfois utilisé se rapporte à la dénomination anglaise, il signifie «Self Organizing Map».
Pour chacune de ces méthodes, il s’agira de minimiser une fonction de coût qui sera différente selon la méthode employée. Une caractéristique est commune à ces méthodes qui est que chaque itération procède en 2 étapes :
  • Une étape d’affectation qui redéfinit la fonction \(\chi\).

  • Une étape de minimisation qui permet de déterminer les référents.

L’algorithme des k-moyennes (ou k-means) est important pour la suite du cours car il est à la base des cartes topologiques qui ajoutent une contrainte supplémentaire sur un ordre topologique des référents permettant ainsi une interprétation relative entre référents. La méthode des k-moyennes (avec les notations introduites ici) détermine l’ensemble des vecteurs référents \({\mathcal W}\) et la fonction d’affectation \(\chi\) en minimisant la fonction de coût \({\mathcal I}\)(\({\mathcal W}\),\(\chi\)) qui représente la somme des inerties locales euclidiennes.

\[{\mathcal I ( W, \chi)}=\displaystyle\sum_{\displaystyle c}{\displaystyle\mathcal I}_{\displaystyle c} =\displaystyle\sum_{\displaystyle{\mathbf{z}_{i} \in \mathcal A}_{c}}{\Vert \mathbf z_{i}-\mathbf w_{c } \Vert}^{2} = \displaystyle\sum_{\displaystyle c}\sum_{{\displaystyle\mathbf{z}_{i} \in \mathcal A} \atop {\displaystyle\chi(\mathbf{z}_{i}) = c}} {\Vert \mathbf z_{i}-\mathbf w_{c } \Vert}^{2}\]

Cartes Topologiques ou Auto-organisatrices

On rappelle que le but des cartes topologiques (ou auto-organisatrices) est d’étudier des données d’observation en effectuant de la classification automatique. Comme nous le verrons, les algorithmes des cartes topologiques permettent de projeter les données sur un espace de faible dimension tout en révélant les structures internes des dites données. Les cartes topologiques ont été introduites pour la première fois par T. Kohonen.

Comme l’algorithme des k-moyennes, auquel on fait souvent référence, les algorithmes des cartes topologiques sont des méthodes de quantification vectorielle.

Présentation-définition

Kohonen propose de projeter l’espace des données \({\mathcal D}\) sur un espace de faible dimension; en général 1, 2 ou 3D. Cet espace appelé Carte, que nous notons \({\mathcal C}\), est constitué d’un ensemble de neurones interconnectés selon une structure de graphe non orienté. Comme nous le montrons ici, la structure du graphe peut avoir des formes variées. Nous montrons ici un exemple en forme de plan(voir Fig. 145), suivi d’un exemple en forme de cylindre (voir Fig. 146), ou encore en forme de tore (voir Fig. 147) (extrait de la som-tool-box de Kohonen).

Forme de plan

Fig. 145 Forme de plan

Forme de cylindre

Fig. 146 Forme de cylindre

Forme de tore

Fig. 147 Forme de tore

Pour notre part, nous illustrerons nos propos sur la structure la plus communément utilisée qui est une grille 2D (en forme de plan). Nous montrons ici (voir Fig. 148) un exemple de carte 2D (carte topologique à deux dimensions) constituée de 10x10 neurones; chaque point de la figure représente un neurone.

Carte 2D constituée de :math:`10 \times 10` neurones

Fig. 148 Carte 2D constituée de \(10 \times 10\) neurones

La structure de la carte induit une distance discrète \(\delta\) sur \(\mathcal C\) de sorte que pour toute paire de neurone (\(c,r\)), la distance \(\delta (c,r)\) est définie comme étant la longueur du plus court chemin entre \(c\) et \(r\) sur le graphe de \(\mathcal C\). Cela détermine une topologie discrète de la carte.
Par exemple la distance \(\delta (c,c1)\) (voir Fig. 149) vaut 6 (le plus court chemin en rouge), celle entre \(c\) et \(c2\) (voir Fig. 150) est de 4 (le plus court chemin en rouge). Il existe bien sûr plusieurs plus courts chemins possibles.
Distance entre c et c1 : :math:`\delta (c,c1)` = 6

Fig. 149 Distance entre c et c1 : \(\delta (c,c1)\) = 6

Distance entre c et c2 : :math:`\delta (c,c2)`\ =4

Fig. 150 Distance entre c et c2 : \(\delta (c,c2)\)=4

Ceci permet de définir la notion de voisinage d’ordre \(\mathbf d\) de \(c\) comme étant le sous-ensemble des neurones \(r\) dont la distance avec \(c\) (c’est-à-dire \(\delta (c,r)\)) est inférieure ou égale à \(d\).

\[V_{c}(d)=\{ r\in \mathcal C, \delta (c,r)\le d \}\]

On montre sur la figure suivante (Voir Fig. 151) \(V_{c}(1)\), \(V_{c}(2)\) et \(V_{c}(3)\) qui sont les voisinages du neurone \(c\) d’ordre 1, 2 et 3.

Voisinages du neurone c d’ordre 1, 2 et 3.

Fig. 151 Voisinages du neurone c d’ordre 1, 2 et 3.

Quantification vectorielle par carte

Comme pour l’algorithme des k-moyennes, la quantification vectorielle consiste à définir une fonction \(\chi\) qui permet d’associer à chaque observation un vecteur référent \({\mathbf w}_{c}\) de l’espace des données \({\mathcal D}\), mais, cette fois, avec une carte topologique; l’indice \(c\) correspond à un neurone qui a une position particulière sur la carte (voir Fig. 152).

Principe général de la modélisation par carte.

Fig. 152 Principe général de la modélisation par carte.

Cela introduit, pour l’algorithme d’apprentissage, une contrainte supplémentaire puisqu’il devra respecter la topologie de la carte. En effet, cette topologie impose que 2 neurones, \(c\) et \(r\), voisins par rapport à la topologie discrète de la carte soient associés à 2 vecteurs référents \({\mathbf w}_{c}\) et \({\mathbf w}_{r}\) qui soient proches selon la distance euclidienne sur \({\mathcal D}\); c’est la notion de conservation de la topologie.

Le but qu’on se donne en introduisant une contrainte par rapport à une topologique est de permettre une meilleure interprétation des données. En effet, la contrainte amenée par la topologie de la carte va induire une organisation spatiale des référents ce qui permettra une interprétation des positions relatives des groupes de données similaires associés à chacun de ces référents. Cela constitue un apport supplémentaire permis par les réseaux de neurones à apprentissage non supervisé.

Fonction de voisinage

Pour l’apprentissage, on aura donc besoin d’une fonction de coût qui, comme pour les k-moyennes, tienne compte de l’inertie intra de la partition de \({\mathcal D}\), mais qui devra respecter de plus la conservation de la topologie de la carte. Ce double objectif est réalisé en ajoutant, dans la fonction de coût, un terme spécifique de fonctions de voisinage calculé à partir de la distance \(\delta\) définie sur la carte.

Les fonctions de voisinage que nous noterons K, définissent des zones d’influence autour de chaque neurone \(c\). Les fonctions de voisinage sont paramétrées par un terme de température noté \(\mathbf T\) qui est déterminant dans l’importance de l’influence entre les neurones. L’influence ou degré de voisinage entre deux neurones \(c\) et \(r\) sera donc calculée par une fonction \(\mathbf{K}^{\mathbf{T}}(\mathbf{\delta} (c,r))\). En général, ces fonctions sont symétriques, positives et tendent à l’infini vers 0.

Nous proposons ici 2 types de fonction \(\mathbf{K}\) paramétrées par un terme de température \(\mathbf{T}\)

  • Pour le premier exemple on montre une fonction de voisinage à seuil (voir Fig. 153).

    Fonction de voisinage à seuil

    Fig. 153 Fonction de voisinage à seuil

    Pour ce type de fonction, tous les neurones inclus dans le voisinage définit par la température \(\mathbf{T}\) ont la même influence, et tous les neurones qui sont à l’extérieur de ce voisinage n’en ont aucune.

    \[\begin{split}K^{T}(\delta) = \left\{\begin{array}{ll} 1 \;\;\; si \;\; \delta \le T\\ 0 \;\;\; sinon \end{array} \right.\end{split}\]

    Le voisinage d’un neurone \(c\) est défini par l’ensemble des neurones \(r\) dont la distance sur la carte \(\delta(c,r)\) est inférieure ou égale au paramètre de température :

    \[V_{c}^T=\{ r\in {\mathcal C} \; / \; \delta(c,r)) \le T \}\]
  • Dans le deuxième exemple, la fonction \(\mathbf{K}\) est de type gaussien. Nous indiquons 2 exemples d’expressions possibles pour ce type de fonction :

    \[K^T(\delta)=\mbox{exp}\left (\frac{- \left | \delta \right |}{T} \right ) \;\;\; et \;\;\; K^T(\delta)=\mbox{exp}\left ( \frac{\delta^{2}}{-T^{2}} \right )\]

    Sur les courbes (voir Fig. 154), on peut voir que plus \(T\) est grand, plus l’influence des neurones proches est importante.

    Fonction de voisinage de type gaussien

    Fig. 154 Fonction de voisinage de type gaussien

    Pour ce type de fonction on peut aussi faire intervenir un paramètre supplémentaire que nous notons \(\alpha\) pour limiter la zone d’influence. Le voisinage d’un neurone \(c\) se définit alors par l’ensemble des neurones \(r\) pour lesquels la fonction \(K^T(\delta(c,r))\) est supérieure à ce paramètre \(\alpha\) : \(V_{c}^{T}=\{ r\in {\mathcal C} \; / \; K^{T}(\delta (c,r))> \alpha \}\) (Voir Fig. 155)

    Limiter la zone d’influence avec :math:`\alpha`

    Fig. 155 Limiter la zone d’influence avec \(\alpha\)

Sur le plan du vocabulaire, les expressions, «taille du voisinage», « zone d’influence» ou «voisinage significatif» se rapportent à la même notion.

Nous présentons encore ici (voir Fig. 156) les courbes associées à deux fonctions \(\mathbf{K}\) pour différentes valeurs du paramètre \(\mathbf{T}\). L’abscisse représente la distance sur la carte qui correspond, on le rappelle, au plus court chemin sur le graphe. L’ordonnée, qui correspond à la valeur de la fonction \(\mathbf{K}\), donne le degré de voisinage entre 2 neurones \(c1\) et \(c2\). Les différentes courbes représentent la fonction \(\mathbf{K}\) pour différentes valeurs du paramètre \(\mathbf{T}\) : du haut vers le bas, \(\mathbf{T}\) prend les valeurs de 10 (\(T_{10}=10\)) à 1 (\(T_{1}=1\)). Dans les 2 cas, on remarque bien qu’avec une plus faible valeur de T, un degré de voisinage moindre sera obtenu; ce comportement étant davantage marqué d’une part selon la distance mais aussi selon la fonction choisie.

Courbes associées à 2 fonctions :math:`\mathbf{K}`

Fig. 156 Courbes associées à 2 fonctions \(\mathbf{K}\)

Apprentissage des cartes topologiques

Le but des algorithmes d’apprentissage des cartes auto-organisatrices est de pouvoir projeter les données de façon à en révéler la structure en formant des sous-ensembles suffisamment compacts. Pour y parvenir on procède en minimisant une fonction de coût qui respecte l’ordre topologique induit par la carte. La fonction de coût utilisée est notée \(J_{som}^{T}\), c’est l’expression donnée ici (46)

(46)\[ {J_{som}^{T}(\chi,\mathcal W})=\displaystyle\sum_{\mathbf{z}_{i}\in {\mathcal A}}\sum_{c \in C} K^{T}(\delta (c,\chi (\mathbf{z}_{i}))) {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2} \label{eqJSOM}\]

Cette expression remplace la fonction d’inertie \(\mathcal{I}\) des k-moyennes. On rappelle que l’acronyme «som» signifie «self organizing map».

Dans cette expression :

  • \(\chi\) représente une fonction d’affectation

  • \(\mathcal W\) représente l’ensemble des \(p\) vecteurs référents qui forment la carte.

  • L’expression \(\chi (\mathbf{z}_{i})\) représente le neurone particulier de la carte \(\mathcal C\) qui est affecté à l’observation \(\mathbf{z}_{i}\)

  • L’expression \(\delta (c,\chi (\mathbf{z}_{i}))\) représente la distance sur la carte \(\mathcal C\) entre un neurone \(c\) quelconque et le neurone \(\chi (\mathbf{z}_{i})\) affecté à l’observation \(\mathbf{z}_{i}\).

L’expression (46) est donc une extension de l’inertie des k-moyennes dans laquelle la distance euclidienne entre une observation \(\mathbf z_{i}\) à son référent \(\mathbf w_{\chi (\mathbf{z}_{i})}\) est remplacée par une mesure que nous appelons «distance généralisée» notée \(\mathbf{d^{T}}\) (47) qui fait intervenir tous les neurones de la carte :

(47)\[d^{T} (\mathbf{z}_{i}, \mathbf w_{\chi (\mathbf{z}_{i})}) = \sum_{c \in C} K^{T}(\delta (c,\chi (\mathbf{z}_{i}))) {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2} \label{eqDistanceGeneralisee}\]

Donc

\[{J_{som}^{T}(\chi,\mathcal W}) =\displaystyle\sum_{\mathbf{z}_{i}\in {\mathcal A}} \underbrace{\color{black} \displaystyle\sum_{c \in C} K^{T}(\delta (c,\chi (\mathbf{z}_{i}))) {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2}}_{\displaystyle d^{T}(z_{i}, \mathbf w_{\chi (\mathbf{z}_{i})})} = \displaystyle\sum_{\mathbf{z}_{i}\in{\mathcal A}} d^{T} (\mathbf{z}_{i}, \mathbf w_{\chi (\mathbf{z}_{i})})\]

Grâce à cette fonction, la contrainte de voisinage introduite par la topologie de la carte pourra être d’autant plus forte que 2 neurones sont proches sur la carte, mais elle peut également se faire sentir même faiblement pour des neurones éloignés.

Lorsque la valeur de la température \(\mathbf{T}\) est suffisamment petite, la fonction \(J_{som}^{T}\) coïncide avec la fonction \(\mathcal{I}\)(\({\mathcal W}\),\(\chi\)) des k-moyennes. Cela apparait mieux si l’on réécrit la fonction \(J_{som}^{T}\) en partitionnant l’ensemble \(\mathcal{A}\) (chaque observation \(\mathbf{z}\) appartient à un sous ensemble \(\mathcal{A}_{r}\) et un seul donc la somme totale sur l’ensemble \(\mathcal{A}\) est la même que la somme des sommes partielles sur les sous ensembles de la partition : \(\mathcal{A}_{1},\ldots, \mathcal{A}_{r},\ldots, \mathcal{A}_{p}\)).

\[{J_{som}^{T}(\chi,\mathcal W})=\displaystyle\sum_{r\in{\mathcal C}}\displaystyle\sum_{\mathbf{z}_{i}\in {\mathcal A_{r}}} \sum_{c \in C} K^{T}(\delta (c,r)) {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2}\]

On peut alors (plus facilement) remarquer que lorsque \(\mathbf{T}\) est suffisamment petite, la fonction \(K^{T}\) prend une valeur significative lorsque \(c=r\) et zéro (ou presque) pour toutes les autres valeurs de \(c\). Ainsi, la somme sur \(c\) n’a plus lieu d’être, seul \(\mathbf w_{r}\) subsiste dans la formule. On retrouve alors explicitement l’expression de l’inertie des k- moyennes :

\[{J_{som}^{T}(\chi,\mathcal W})=\displaystyle\sum_{r\in{\mathcal C}}\displaystyle\sum_{\mathbf{z}_{i}\in {\mathcal A_{r}}} {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2}\]

Par comparaison, on voit bien que là où l’on utilisait la norme euclidienne pour les k-moyennes on utilise maintenant la «distance généralisée».

Illustration de la distance généralisée

La «distance généralisée» \(d^{T} (\mathbf{z}_{i}, \mathbf w_{r})\) est une mesure entre une observation \(\mathbf z_{i}\) et un référent \(\mathbf w_{r}\). Elle prend en compte, avec une pondération, tous les autres référents \(\mathbf w_{c}\). Cette quantité est donc une somme pondérée de la distance euclidienne au carrée entre l’observation \(\mathbf z_{i}\) et ces référents \(\mathbf w_{c}\) voisins.

(48)\[d^{T} (\mathbf{z}_{i}, \mathbf w_{r}) = \displaystyle\sum_{c \in C} K^{T}(\delta (c,r)) {\Vert \mathbf z_{i}-\mathbf w_{c} \Vert}^{2} \label{eqDistanceGeneralisee2}\]

La pondération est apportée à chaque fois par la fonction de voisinage \(K^{T}\) appliquée sur la distance sur la carte entre le neurone c et le neurone r. De ce fait, cette quantité se compose de 2 termes dont l’un se rapporte à l’espace \({\mathcal D}\), et l’autre à la carte \({\mathcal C}\).

Nous avons illustré cette distance pour 2 observations \(\mathbf z_{i}\) différentes en utilisant une carte réduite.

  • Cas 1 : on prend comme indice r le neurone 5.

  • Cas 2 : on prend comme indice r le neurone 3.

Illustration de la distance généralisée

Fig. 157 Illustration de la distance généralisée

Nous avons tracé des lignes entre \(\mathbf z_{i}\) et les \(\mathbf w_{c}\) que nous avons étiquetées par la distance sur la carte. Ces lignes sont d’autant plus épaisses que le neurone de \(\mathbf w_{c}\) et le neurone r sont proches sur la carte, et d’autant plus longue que l’écart entre les 2 termes \(\mathbf z_{i}\) et \(\mathbf w_{c}\) est important. D’une certaine manière, on peut dire que, ensemble, ces lignes représentent la «distance généralisée». Dans ces deux exemples, tous les neurones sont inclus dans le voisinage, ce qui montre la portée globale de l’expression ([eqDistanceGeneralisee2]), mais un paramètre de température T peut permettre de restreindre le voisinage en excluant, par exemple, tous les neurones c tel que \(\delta (c,r) >T\); ainsi si T=3 alors la ligne reliant \(\mathbf z_{i}\) et \(\mathbf w_{7}\) sur la figure en bas à droite (illustration avec r=3) disparaîtrait.

Algorithme d’optimisation totale (version batch)

A ceci près que la fonction de coût est différente, on retrouve le formalisme des nuées dynamiques de la méthode des k-moyennes; et comme pour cette dernière, on procède par itérations successives, chaque itération enchaînant la phase qui affecte l’ensemble des observations \(\mathbf z_{i}\) aux référents, puis celle de minimisation qui recalcule les référents. Ici aussi, quand T a une valeur fixe, la convergence vers un minimum local de la fonction de coût peut être démontrée.

On décrit ici les 2 phases qui réalisent la minimisation de la fonction de coût \(J_{som}^{T}\) pour une valeur de T fixée.

  • Phase d’affectation
    La phase d’affectation minimise la fonction \(J_{som}^{T}(\chi,{\mathcal W})\) par rapport à la fonction d’affectation \(\chi\); l’ensemble des référents \({\mathcal W}\) restant constant et égal à la valeur calculée précédemment. Les relations ([eqJSOM]) et ([eqDistanceGeneralisee2]) montrent que l’affectation qui minimise \(J_{som}^{T}\) pour \({\mathcal W}\) fixé est celle qui est définie par l’expression suivante :
    (49)\[{\chi^{T} (\mathbf{z})=\displaystyle\arg\min_{r\in C} \sum_{c \in C} K^{T}(\delta (c,r)) {\Vert \mathbf z -\mathbf w_{c} \Vert}^{2}}=\displaystyle\arg\min_{r\in C} d^{T}(\mathbf z, \mathbf w_{r}) \label{eqPhaseAffectationTconstant}\]

    Chaque observation \(\mathbf z\) est affectée au référent \({\mathbf w}_{r}\) pour lequel la «distance généralisée» \(d^{T}(\mathbf z,{\mathbf w}_{r})\) (48) est la plus petite. Cette phase permet donc de définir une nouvelle partition de l’ensemble des données \(\mathcal{D}\).

  • Phase de minimisation
    Pour la phase dite de minimisation, il s’agit maintenant de minimiser \(J_{som}^{T}\) par rapport à l’ensemble des référents de \({\mathcal W}\) en gardant la fonction \(\chi\) telle qu’elle vient d’être calculée par la phase précédente. La fonction \(J_{som}^{T}\) étant convexe par rapport aux paramètres \({\mathcal W}\), la minimisation est obtenue pour la valeur qui annule la dérivée formulée par l’expression suivante :
    (50)\[\mathbf w_{c}^{T} = \frac{\displaystyle\sum_{r\in C}K^{T}(\delta (c,r)) \mathbf Z_{r}}{\displaystyle\sum_{r\in C}K^{T}(\delta (c,r)) n_{r}} \label{eqPhaseMinimisationTconstant}\]
    \(n_{r}\) : le nombre d’observations de l’ensemble d’apprentissage affectées au neurone r
    \(Z_{r}\) : la somme de toutes les observations affectées au neurone r (\(\sum_{\mathbf{z}_{i} \in \mathcal{A}; \; \chi (\mathbf{z}_{i})=r} \mathbf{z}_{i}\)).

    Cette phase permet donc de définir les nouveaux référents \({\mathbf w}_{c}\).

L’algorithme «nuées dynamique» des cartes topologiques pour une valeur de T fixée se résume alors comme suit :

  1. Phase d’initialisation : t=0
    Choisir la structure et la taille de la carte, les référents initiaux (\({\mathcal W}^{0}\)) et le nombre maximum d’itérations (\(N_{iter}\)).
  2. Etape de minimisation itérative t. (à partir de t=1)

    • Phase d’affectation: mise à jour de la fonction d’affectation \(\chi^{t}\) qui consiste à associer chaque observation \(\mathbf{z}\) à un référent de \({\mathcal W}^{t-1}\) selon l’expression (49)

    • Phase de minimisation : calcul des nouveaux référents \({\mathcal W}^{t}\), associés à \(\chi^{t}\), en appliquant la formule (50)

  3. Répéter l’étape de minimisation itérative jusqu’à atteindre \(N_{iter}\) itérations ou une stabilisation de la fonction \(J_{som}^{T}\).

La figure suivante montre les cartes obtenues pour quelques valeurs distinctes de T sur un exemple très simple. On a représenté simultanément sur la même figure les observations en bleu et les référents en rouge. Les liens entre les référents sont représentés en vert.

Déroulement de l’algorithme nuées dynamiques à T fixé.

Fig. 158 Déroulement de l’algorithme nuées dynamiques à T fixé.

Algorithmes de minimisation à valeur de T décroissante

Lorsqu’on utilisait une valeur de T fixée, on s’est aperçu, qu’une valeur élevée de T favorisait la formation d’un ordre de la carte mais que cette dernière ne parvenait pas à se déployer sur l’ensemble des données; à contrario, une petite valeur de T permettait le déploiement de la carte sur les données, mais la carte obtenue n’était pas nécessairement bien ordonnée (voir la figure précédente).

Pour répondre à cet antagonisme, la procédure utilisée consiste à initialiser la température T à une valeur élevée, favorisant ainsi l’apparition de l’ordre, puis à la faire décroitre progressivement au cours des itérations de minimisation permettant à la carte de recouvrir peu à peu la distribution réelle des observations.
Les paramètres déterminants de cette méthode sont :
  • l’intervalle de variation de T, c’est-à-dire la valeur initiale de T notée Tmax, et sa valeur finale Tmin,

  • le nombre d’itérations de minimisation,

  • la manière dont le paramètre T décroit dans l’intervalle \([ \mathbf{Tmax}, \mathbf{Tmin} ]\) au cours des itérations.

Selon le réglage de ces paramètres, l’algorithme d’optimisation peut aboutir à des résultats différents; ce que nous montrerons par la suite.

L’algorithme d’optimisation totale des cartes topologiques se résume comme suit :

Algorithme d’optimisation totale

Fig. 159 Algorithme d’optimisation totale

Dans la phase d’initialisation, on déclare un indice d’itération t dont on fixe un nombre maximum, on définit un nombre p de référents initialisés en général de façon aléatoire, de plus, on choisit les bornes Tmin et Tmax de l’intervalle de température.

Nous entrons ensuite dans la partie itérative de l’algorithme qui comporte :

  • La détermination de la température T selon l’ntervalle donné et une fonction de décroissance. Cette variable T sera celle qui sera utilisée par les deux phases qui suivent.

  • La phase d’affectation, ou partitionnement, correspond à la mise à jour de la fonction \(\chi (c)\), qui consiste à associer chaque observation \(\mathbf z\) au référent de \({\mathbf w}_{c}^{t-1}\) qui lui est le plus proche, au sens de la «distance généralisée», conformément à l’expression (49).

  • La phase de minimisation qui fait évoluer les référents en les recalculant par l’application de la formule (50) obtenue en calculant le zéro de la dérivée de la fonction \(J_{som}^{T}\) par rapport à \({\mathbf W}\).

Nous montrons ici deux exemples de fonction de décroissance (\(f_{dec}\)) de T avec Tmin=1, Tmax=10, et Niter=100.

Exemple de fonctions de décroissance de T

Fig. 160 Exemple de fonctions de décroissance de T

(1) \(T = T_{max} - (T_{max} - T_{min}) \displaystyle\frac{t-1}{N_{iter} -1}\)
(2) \(T = T_{max} \left(\displaystyle\frac{T_{min}}{T_{max}}\right)^{\displaystyle\frac{t-1}{N_{iter} -1}}\)

La première est une fonction linéaire, sa décroissance est donc constante en t, la seconde est convexe, elle présente une décroissance plus marquée au début qu’à la fin où elle est plus douce.

Algorithme de Kohonen (version stochastique)

L’algorithme présenté initialement par Kohonen est une version stochastique de l’optimisation des cartes topologiques. On peut remarquer que lors de la phase de minimisation, il n’est pas obligatoire de trouver le minimum global de \(J_{som}^{T}({\mathcal W},\chi)\) pour \(\chi\) fixée, il suffit de faire décroître sa valeur. Il est donc possible de remplacer la relation (50) par une méthode de descente de gradient telle qu’elle est exprimée par la relation (51) indiquée ici, dans laquelle la dérivée se calcule avec l’expression (52), et le paramètre \(\mu^{t}\) est le pas de gradient à l’itération t.

(51)\[{\mathbf w}_{c}^{t} = {\mathbf w}_{c}^{t-1} - \mu^{t} \displaystyle\frac{\partial J^{T}_{som}}{\partial {\mathbf w}_{c}^{t-1}} \label{eqPhaseMinimisationStochastique1}\]
(52)\[\displaystyle\frac{\partial J^{T}_{som}}{\partial {\mathbf w}_{c}^{t-1}} = 2\displaystyle\sum_{{\mathbf z}_{i} \in A}K^{T}(\delta (c,\chi({\mathbf z}_{i})))({\mathbf z}_{i}-{\mathbf w}_{c}^{t-1}) \label{eqPhaseMinimisationStochastique2}\]

La contribution d’une seule observation \(\mathbf z_{i}\) à la correction de \({\mathbf w}_{c}\) est représentée par le terme de la somme : \(2K^{T}(\delta (c,\chi({\mathbf z}_{i})))({\mathbf z}_{i}-{\mathbf w}_{c}^{t-1})\).

Le caractère stochastique de l’algorithme provient de ce que les traitements itératifs ne sont effectués que pour une observation \(\mathbf z_{i}\) à la fois.

L’affectation \(\chi\) n’est déterminée à chaque itération que pour une seule observation \(\mathbf z_{i}\) (en générale, choisie d’une manière aléatoire). La fonction \(\chi\) utilisée par Kohonen est celle des k-moyennes.

(53)\[\chi({\mathbf z}_{i}) = \displaystyle\arg\min_{c} \, {\Vert \mathbf z_{i}-\mathbf w_{c } \Vert}^{2} = r \label{eqPhaseAffectationStochastique}\]

A chaque présentation d’une observation \(\mathbf z_{i}\) , tous les référents seront alors recalculés en fonction du neurone \(r\) (sélectionné par la fonction d’affectation ci-dessus) en utilisant l’expression (54) qui découle des formules (51) et (52) du gradient stochastique. Ce dernier point constitue la différence majeure avec l’algorithme des k-moyennes.

(54)\[{\mathbf w}_{c}^{t} = {\mathbf w}_{c}^{t-1} - 2 \mu^{t} K^{T} (\delta (c,r))({\mathbf z}_{i}-{\mathbf w}_{c}^{t-1}) \label{eqPhaseMinimisationStochastique3}\]

L’algorithme proposé initialement par Kohonen (version stochastique) se résume comme suit :

  1. Initialisation
    t=0 : indice d’itération
    \(N_{iter}\) : nombre maximum d’itérations
    Choisir la structure et la taille p de la carte
    Choisir les \(p\) référents initiaux (en général d’une manière aléatoire) : \({\mathcal W}^{0}\)
    Choisir les bornes de l’intervalle de température \(T_{min}\) et \(T_{max}\)
  2. Etape de minimisation itérative t. (à partir de t=1; \({\mathcal W}^{t-1}\) est donc connu)
    L’ensemble des référents \({\mathcal W}^{t-1}\) de l’étape précédente est connu
    • Choisir une observation \(z_{i}\)

    • Calculer la nouvelle valeur de T à utiliser par les phases d’affectation et de minimisation qui suivent, grâce à une fonction de décroissance : \(T=f_{dec}(t, N_{iter}, T_{min}, T_{max})\)

    • Phase d’affectation : associer l’observation \(z_{i}\) au neurone \(r=\chi^{t}(z_{i})\) définie par l’expression (53)

    • Phase de minimisation : calcul de l’ensemble des nouveaux référents \({\mathcal W}^{t}\) en appliquant la formule (54). Chaque référent \(w_{c}\) est modifié en fonction de sa distance au au neurone \(r\) sélectionné à la phase d’affectation.

  3. Répéter l’étape de minimisation itérative jusqu’à atteindre \(N_{iter}\) itérations
    ou une stabilisation de la fonction \(J_{som}^{T}\).

On y retrouve la même initialisation que pour l’algorithme d’optimisation total, et la même prise en compte de la décroissance du paramètre de tempèrature T. Chaque itération de la boucle de minimisation, ne concerne qu’une seule observation \(\mathbf z_{i}\) à la fois. Celle-ci est généralement choisie de manière aléatoire. Pour la phase d’affectation on utilise l’expression (53) appliquée à l’observation \(\mathbf z_{i}\) ce qui définit le neurone \({\mathbf r}\) gagnant. On peut alors passer à la phase de minimisation de tous les référents \({\mathbf w}_{c}\) par l’application de la formule (54) dans laquelle on utilisera les distances sur la carte au neurone \({\mathbf r}\) sélectionné à l’étape d’affectation.

Déroulement de l’algorithme en deux phases

La fonction de coût minimisée par l’algorithme des cartes topologiques, qui dépend de la valeur de T, peut être décomposée en 2 termes :

Décomposition de :math:`J_{som}` en 2 termes.

Fig. 161 Décomposition de \(J_{som}\) en 2 termes.

La minimisation du premier terme permet de rapprocher les 2 sous-ensembles liés à 2 neurones voisins sur la carte afin de conserver l’ordre topologique. En effet, si 2 neurones \(c\) et \(r\) sont proches sur la carte, \(\delta(c,r)\) est alors petit, et dans ce cas \(K^{T}(\delta(c,r))\) est grand. La minimisation du premier terme aura pour effet de réduire davantage le terme qui le multiplie :

\[\displaystyle \left [ \sum_{\mathbf z_{i}\in P_{r}}\|\mathbf z_{i} - \mathbf w_{c}\|^2 + \sum_{\mathbf z_{i}\in P_{c}}\|\mathbf z_{i} - \mathbf w_{r}\|^2 \right ]\]

La minimisation du second terme correspond à la minimisation de la fonction utilisée par l’algorithme des k-moyennes.

Puisque l’apprentissage des cartes topologiques fait décroître le paramètre \(T\) dans un intervalle, la convergence vers la solution peut se décomposer en deux phases :

  • La première phase correspond aux grandes valeurs de \(T\). Dans ce cas, c’est le premier terme qui est prépondérant et l’algorithme a tendance à assurer la conservation de l’ordre topologique (l’ordre topologique se forme). Plus la valeur de \(T\) diminue, plus la carte se déploie (voir les 2 figures suivantes).

    Phase 1 : l’ordre topologique se forme.

    Fig. 162 Phase 1 : l’ordre topologique se forme.

  • La deuxième phase a lieu pour les petites valeurs de \(T\). Dans ce cas, c’est le deuxième terme qui est prépondérant et l’algorithme commence à se rapprocher de l’algorithme des k-moyennes. A la fin de l’algorithme, quand la valeur de \(T\) devient plus petite, les référents se répartissent plus finement sur les données (voir la figure suivante).

    Les référents se répartissent plus finement sur les données

    Fig. 163 Les référents se répartissent plus finement sur les données

Un exemple simplifié

Le but de l’exemple que nous présentons maintenant est de montrer et de faire comprendre plus intuitivement comment fonctionne un algorithme d’apprentissage d’une carte topologique.

On dispose d’un ensemble de 625 données uniformément réparties qui sont représentées par les points bleus sur la figure de gauche. On veut représenter ces données à l’aide d’une carte topologique unidimensionnelle comportant 10 neurones c1 à c10.
Les référents sont pour leur part, initialisés de manière aléatoire au centre des données; ils sont représentés par les points rouges sur la figure de gauche.
Carte 1D et données uniformément réparties.

Fig. 164 Carte 1D et données uniformément réparties.

Nous avons effectué un zoom (voir la figure suivante) sur les référents initiaux que nous avons accompagnés de l’indice du neurone auquel chaque référent est associé. Les traits bleus qui relient les référents représentent les contraintes de voisinage apportée par la carte. On peut donc voir ici que dans l’espace des données, les référents sont liés les uns aux autres selon l’ordre induit par la carte.

Carte 1D : zoom sur les référents initiaux

Fig. 165 Carte 1D : zoom sur les référents initiaux

Nous avons lancé un apprentissage avec \(T_{max}=10\) et \(T_{min} =0.1\), et nous avons obtenu l’état final tel qu’il apparaît maintenant sur la figure suivante.

Carte 1D : à la fin de l’apprentissage

Fig. 166 Carte 1D : à la fin de l’apprentissage

En faisant décroître T pendant la convergence vers la solution, on peut différencier deux comportements de l’algorithme pendant son exécution. Avec de grandes valeurs de T en début du processus de minimisation, l’algorithme à tendance à assurer la conservation de l’ordre topologique en permettant aux vecteurs référents de s’agencer globalement selon cet ordre. Lorsque la température T parvient à de petites valeurs, on se rapproche peu à peu des conditions de l’algorithme des k-moyennes qui permettent aux référents de se répartir sur les données; le comportement de l’algorithme devient alors de plus en plus local.

Comme on l’a indiqué, le résultat obtenu dépend des paramètres de température. Ceci veut dire que, avec d’autres valeurs de \(T_{max}\) et \(T_{min}\), on peut aboutir, comme vont le montrer les exemples à suivre, à un état final différent.

Nous poursuivons la présentation d’exemples avec les mêmes données uniformément réparties que précédemment, mais en utilisant cette fois 100 référents dans des situations différentes puisque nous utilisons deux topologies différentes; d’abord une carte 1D puis une carte 2D de 10x10 neurones. Dans chaque situation, les référents ont la même initialisation aléatoire au centre des données. Nous utilisons aussi des intervalles de température différents en jouant sur la valeur de Tmin (voir les figures suivantes).

Carte 1D, carte 2D et données uniformément réparties.

Fig. 167 Carte 1D, carte 2D et données uniformément réparties.

A chaque fois, on voit, d’une part, qu’une température initiale élevée favorise une bonne organisation de la carte; et d’autre part, que les référents se répartissent plus finement sur les données lorsque la température finale devient plus faible. Les données étant ici équiréparties, on peut remarquer que les référents sont à peu près équidistants les uns des autres. Ceci est propre à cette distribution, ce qui n’est évidemment pas généralisable.

Nous montrons de nouveau ici, de manière plus accrue, l’importance de l’intervalle de température T sur un nouveau jeu de 300 données simulées qui ont été constituées selon quatre gaussiennes qui se recouvrent partiellement deux à deux (voir les figures suivantes).

Importance de l’intervalle de température T

Fig. 168 Importance de l’intervalle de température T

Les figures présentées correspondent à la carte topologique obtenue à la fin des itérations de minimisation. Pour les figures 1 et 2 on a choisit une température constante, c’est-à-dire, qu’on a positionné Tmin et Tmax à la même valeur de 6,5 pour l’une et 1 pour l’autre. Pour la première (Figure 1), on voit une organisation rapide de la carte qui ne parvient cependant pas se développer sur l’ensemble des données. Pour la seconde (Figure 2), on voit que la carte investit l’ensemble des données mais de manière un peu irrégulière. Ceci est du à une température trop petite.
Pour les figures suivantes on fait jouer la décroissance de la température T.
  • Pour la figure 3, Tmax=3 et Tmin=1 : la carte se tord et se froisse

  • Pour la figure 4, Tmax=1.1 et Tmin=1e-10 : la carte se tord et se froisse également

  • Pour la figure 5, Tmax=5 et Tmin=0.01 : la carte se froisse

  • Pour la figure 6, Tmax=5 et Tmin=1 : la carte se déploie de façon ordonné sur l’ensemble des données

Ces expériences nous montre que l’ordre topologique obtenu est très sensible à l’ensemble des paramètres qui interviennent dans l’algorithme.

Qualité de la carte

Il n’existe malheureusement pas de règle qui nous assure que l’ordre obtenu est parfaitement adéquat. Certains indicateurs de qualité sont cependant proposés comme l’erreur de quantification (ou mesure de résolution) définie par la distance moyenne des données à leurs référents, ou une mesure de la préservation de la topologie (ou erreur topographique) qui correspond à la proportion des données pour lesquelles les 2 référents les plus proches ne correspondent pas à des unités adjacentes sur la carte. Ces indicateurs sont d’une interprétation délicate, et une démarche empirique de validation reste recommandée avant d’interpréter et d’utiliser les résultats définitivement.

Nous donnons ici, à titre indicatif ces indicateurs pour les exemples présentés précédemment. Sur chacune des figures, qui rappelle l’exemple, on a noté en bleu à gauche l’erreur de quantification, et en violet à droite, l’erreur topographique.

Erreur de quantification et erreur topographique

Fig. 169 Erreur de quantification et erreur topographique

Concernant les données uniformes, il apparaît clairement que le meilleur résultat est celui de la figure (1.d) obtenu avec une carte 2D, puisque les 2 erreurs sont minimales. Pour les données gaussiennes, on peut être amené à hésiter entre les figures (2.c) et (2.f).

Il est a noté que les meilleurs résultats peuvent être obtenus avec un nombre de neurones sur dimensionné par rapport aux données, mais cependant, cette situation extrême ne permet alors pas de réduire l’information qui est l’un des buts de la quantification par carte.

Classification et carte topologique

L’auto-organisation que nous venons d’effectuer, ne nous permet cependant pas de résoudre directement un problème de classification; elle permet simplement d’affecter une observation à un sous-ensemble d’une partition, représenté par un référent, indépendamment de toute notion de classe. Il peut être utile de se servir de cette quantification vectorielle comme point de départ pour obtenir un classifieur.

Puisque chaque sous-ensemble de données est associé à un référent, le problème de classification se résume à celui de l’étiquetage de chaque neurone à l’une des classes. Il faut donc introduire une seconde étape consistant à étiqueter tous les neurones de la carte. Nous allons présenter 2 méthodes de classification, la première est une classification par données expertisées la seconde est une classification ascendante hiérarchique (CAH).

La classification par données expertisées repose sur les connaissances d’un expert qui est capable de constituer un ensemble de données, du même problème, qu’il aura «labellisées» (ou «étiquetées») selon Q classes qu’il a définit. On appelle dans la suite ensemble «expert» cet ensemble.

Comme on le sait maintenant, à l’issu de l’apprentissage, chaque observation \({\mathbf z}_{i}\) est affectée à un neurone c selon la fonction d’affectation : \(c = \chi({\mathbf z}_{i})\). On projette alors l’ensemble expert, chaque neurone c en récupére une partie.
Le neurone c est donc associé au sous-ensemble \(P_{c}\) constitué, pour partie, des données labélisées qui lui on été affectées. Dès lors, pour déterminer la classe du neurone c, on peut procéder à un vote majoritaire qui consiste à attribuer au neurone c la classe qui apparaît le plus souvent parmi le sous-ensemble \(P_{c}\). Le grand nombre de données étiquetées garantit dans ce cas la qualité du classifieur (voir la figure suivante).
Classification par données expertisées

Fig. 170 Classification par données expertisées

Remarques

  • Les neurones qui représentent les observations situées aux frontières des différentes classes peuvent être mal étiquetés.

  • Il se peut que des neurones n’aient capté aucune donnée étiquetée : les zones de l’espace des observations relatives à ces neurones sont alors mal connues.

  • Notez qu’il est possible de demander à un expert du domaine d’étiqueter un neurone (donc un sous ensemble d’observations) grâce aux caractéristiques de ce dernier.

  • Si le nombre d’observations étiquetées est trop petit, cette méthode d’étiquetage est mal adaptée. le vote majoritaire peut introduire un nombre important d’erreurs.

Sous l’hypothèse d’un bon ordre topologique, il est très probable que deux neurones voisins représentent des données de même classe. Dans ce cas, il est possible d’envisager une autre approche en regroupant les neurones dans la carte. On cherche alors à obtenir une partition plus grossière, l’étiquetage n’intervient qu’après cette première phase de regroupement des neurones. Si on ne dispose d’aucune donnée étiquetée, on peut faire apparaître des groupes cohérents en utilisant la classification ascendante hiérarchique (sur les référents ou neurones). Le résultat de la classification devra ensuite être soumis à interprétation.

CAH sur les neurones

Fig. 171 CAH sur les neurones