• 15 heures
  • Difficile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Mis à jour le 01/02/2019

Découvrez une variété qui conserve la structure globale

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Une première famille de méthodes de réduction dimensionnelles non-linéaire est celle des méthodes dites globales. Comme je l’ai expliqué dans le chapitre précédent, cette famille permet de traiter le jeu de données avec un focus sur les distances entre les paires de points, qu’ils soient distants ou proches.

MDS (Multidimensional Scaling)

MDS (Multidimensional Scaling) est une méthode de réduction dimensionnelle qui utilise les distances entre les points. C’est encore une méthode qui vous aidera à expliquer les similarités et dissimilarités observées dans votre jeu de données, en les représentant dans un espace géométrique de dimension inférieure à celle de l’espace initial

Intuition du fonctionnement

Pour cela, le MDS s’intéresse à la matrice $\(D_{ij}\)$ de distances entre les points. A la différence de l’analyse en composantes principales qui traite uniquement la matrice de variance-covariance (corrélation) entre les variables, MDS permet d’utiliser n’importe quel type de mesure de similarité comme “distance” (dont la distance euclidienne bien sûr 😉).

A l’aide de cette matrice de distances D, une procédure MDS va essayer de réarranger les observations dans un espace de dimension inférieure (2 en général pour la visualisation) pour se rapprocher au mieux des distances dans l’espace d’origine.

Comme d’habitude dans les algorithmes de machine learning, il faut minimiser une fonction objectif (ou fonction de coût) héhé. Dans notre cas présent, l’objectif est de minimiser l’erreur entre les distances approximées dans l’espace de dimension inférieure, et les distances réelles dans l’espace de départ. 

$\[Cost = \sum_{i<j}(d_{ij}-\hat{d_{ij}})^2\\ d_{ij} = ||x_i - x_j||^2\\ \hat{d_{ij}} = ||y_i - y_j||^2\]$

 

L’objectif est de retrouver les vecteurs $\(y_i\)$ dans l’équation ci-dessus qui formeront les points de notre nouvelle visualisation.

Ces manipulations m’ont l’air assez linéaires, non?

Bien vu effectivement 😛 En effectuant cette MDS de base avec les distances euclidiennes (appelée MDS métrique) on est équivalent aux résultats d’une ACP linéaire, sous sa forme duale. Ca veut dire deux choses. La première c’est que l’ACP conserve les propriétés de distances ce qui est une bonne choses. La seconde, c’est que MDS est un algorithme linéaire...

En réalité, la non-linéarité va apparaître en modifiant notre définition de la mesure utilisée pour le calcul des distances, pour la généraliser à des fonction monotones (constamment croissantes ou décroissantes), même si ce ne sont pas des mesures au sens formel du terme (qui respectent l’inégalité triangulaire). On est alors dans la famille de méthodes MDS non-métriques.

Scikit par exemple, implémente une régression monotonique, qui conserve l’ordre des points, en conservant les inégalités des valeurs dans la matrice D. Par exemple, si $\(D_{ij} < D_{ef} \)$ alors le plongement doit conserver l’inégalité $\(\hat{d}_{ij} < \hat{d}_{ef}\)$

Pour cela, il suffit de spécifier metric=False  dans la fonction de scikit  sklearn.manifold.MDS

Une extension : Isomap

Imaginez que je veuille trouver la distance sur un globe qui sépare Paris de Los Angeles. Je ne vais pas utiliser la distance euclidienne directement, ce serait une erreur. Je vais plutôt considérer la Terre comme une variété et calculer la distance sur sa surface

Intuitivement, une sous-variété se rapproche d’un espace linéaire quand on s’intéresse au voisinage d’un point. Par exemple pour cette distance, si je m’intéresse à une ville proche de Paris, je pourrais considérer une ligne droite qui les sépare, donc une distance euclidienne.

Maintenant, si j’effectue cette approximation de ville en ville jusqu’à Los Angeles, j’aurais une bonne approximation de la “vraie” distance qui sépare les deux villes.

Ainsi, l’algorithme Isomap a été créé dans l’objectif de favoriser encore plus la structure locale ainsi que la capture de la non-linéarité de la variété sous-jacente au phénomène, qui reste difficile à détecter à l’aide d’un MDS. Isomap a été imaginée avec le type d’approximation que je viens d’effectuer pour estimer la distance Paris-Los Angeles

Il fonctionne en trois étapes :

1. Créer un graphe de voisins (Neighbourhood Graph). Plusieurs méthodes sont possibles. On peut simplement dire que les K voisins les plus proches sont connectés. Ou bien que tous les points dont la distance est inférieure à $\(\epsilon\)$ sont connectés.

2. Calculer la distance géodésique entre chaque paire de points. La définition de distance géodésique utilisée ici est le chemin le plus court dans le graphe, pondéré par la distance entre les points. Il y a des algorithmes pour effectuer ce calcul de manière efficace.

3. Appliquer l’algorithme du MDS à cette matrice de distances géodésique.

L'exemple célèbre du swissroll sur lequel est appliqué l'algorithme de l'isomap. La 3ème image montre en rouge la distance géodésique finale
L'exemple célèbre du swissroll sur lequel est appliqué l'algorithme de l'isomap. La 3ème image montre en rouge la distance géodésique finale

Résumé

L’algorithme Isomap est une méthode pratique lorsqu’on veut conserver la structure géométrique globale du phénomène, à petite et à grande échelle. C'est un des algorithmes à tester lorsqu'on est face à un problème non-linéaire à explorer.

Exemple de certificat de réussite
Exemple de certificat de réussite