Explorez vos données avec des algorithmes non supervisés

15 heures
Difficile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

Mis à jour le 08/01/2024

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

Une première famille de méthodes de réduction dimensionnelle non linéaires 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. À 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 😉).

À 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. Ça veut dire deux choses. La première, c’est que l’ACP conserve les propriétés de distances, ce qui est une bonne chose. 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 fonctions 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 sur un globe la distance 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 pourrai 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’aurai 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 globale 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é 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 (Neighborhood 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ésiques.

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 3e 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 échelles. C'est un des algorithmes à tester lorsqu'on est face à un problème non linéaire à explorer.