Module 3 · Page 1/4

ISOMAP

Geodesic Isometric Mapping — préserver les distances géodésiques sur une variété non-linéaire via un graphe de voisinage.

1. Pourquoi ISOMAP ?

Le problème

L'ACP mesure des distances euclidiennes dans l'espace ambiant. Si les données vivent sur une variété courbe (ex : un rouleau de papier déplié, une sphère), la distance euclidienne "coupe à travers" la variété et ne reflète pas la vraie proximité le long de la surface. ISOMAP utilise les distances géodésiques — les plus courts chemins sur la variété elle-même.

▶ Distance euclidienne vs géodésique

Distance euclidienne (ACP)

Distance géodésique (ISOMAP)

Sur une variété courbe, la distance euclidienne (ligne droite) ne suit pas la surface. La géodésique suit la courbe — c'est la vraie distance "sur" la variété.

2. Algorithme ISOMAP — étapes

Construire le graphe de voisinage

Pour chaque point \(x_i\), trouver ses \(k\) plus proches voisins (ou tous les points dans un rayon \(\epsilon\)). Relier les voisins par des arêtes pondérées par la distance euclidienne locale \(d_E(x_i, x_j)\).

Calculer les distances géodésiques

Appliquer l'algorithme de Floyd-Warshall ou Dijkstra pour trouver le plus court chemin entre chaque paire de points dans le graphe. La matrice \(D_G\) contient toutes les distances géodésiques approximées.

Appliquer le MDS classique

Appliquer la Mise à l'Échelle Multidimensionnelle (MDS) sur la matrice \(D_G^2\) pour trouver une représentation en basse dimension qui préserve ces distances. MDS diagonalise une matrice centrée de \(D_G^2\).

3. La formule du MDS (étape 3 en détail)

Centrage de la matrice de distances

On construit la matrice \(B\) à partir de la matrice des distances géodésiques au carré \(D_G^2\) en la centrant :

\[ B = -\frac{1}{2} H D_G^2 H \qquad \text{avec} \quad H = I - \frac{1}{n}\mathbf{1}\mathbf{1}^T \]

H : matrice de centrage (\(n \times n\)) · D²G : matrice des distances géodésiques au carré · B : matrice de Gram centrée
Puis on diagonalise \(B = V \Lambda V^T\) et on obtient les coordonnées : \(Y = V_q \Lambda_q^{1/2}\) (les \(q\) premières composantes)

4. Paramètres et choix

Paramètre k (k-plus proches voisins)

k trop petit : graphe disconnecté, géodésiques non calculables entre certains points.
k trop grand : les arêtes "coupent" à travers la variété, on perd la géométrie locale.

Paramètre ε (rayon)

Alternative à k : connecter tous les points dans un rayon \(\epsilon\). Même problème : trop petit = graphe disconnecté, trop grand = raccourcis incorrects.

▶ Effet du paramètre k sur le graphe de voisinage

k = 3

Les arêtes vertes connectent chaque point à ses k plus proches voisins. Observe comment k affecte la connectivité du graphe et les "raccourcis" indésirables.

—

5. Limites d'ISOMAP

Limites connues

Topologie non convexe : si la variété a des "trous" ou n'est pas convexe, les géodésiques passent par des zones vides et sont incorrectes.
Coût quadratique : Floyd-Warshall est \(O(n^3)\) — difficile pour de grands datasets.
Graphe disconnecté : si k est trop petit, impossible de calculer des géodésiques entre toutes les paires.

ISOMAP vs ACP

ACPDistance euclidienne globale — coupe à travers la variétéISOMAP : distance géodésique — suit la variété

ACPProjection linéaire — hyperplan optimalISOMAP : MDS sur distances géodésiques — non-linéaire

ACPPas de paramètre à réglerISOMAP : k (ou ε) à choisir avec soin

ACPToujours applicableISOMAP : échoue si variété non convexe ou graphe disconnecté

📌 À retenir / À l'examen

ISOMAP = ACP sur distances géodésiques (pas euclidiennes)
3 étapes : graphe de voisinage → plus courts chemins (Dijkstra/Floyd-Warshall) → MDS
Formule MDS : \(B = -\frac{1}{2}HD_G^2 H\) puis diagonalisation de \(B\)
Paramètre \(k\) : voisins trop peu = graphe disconnecté; trop = raccourcis incorrects
Préserve la structure géodésique globale de la variété
Limite : topologie non convexe, coût \(O(n^3)\)

🧠 Quiz de validation

Quelle est la différence fondamentale entre la distance utilisée par l'ACP et celle utilisée par ISOMAP ?

Dans ISOMAP, à quoi sert l'algorithme de Floyd-Warshall (ou Dijkstra) ?

Quelle formule permet de passer de la matrice de distances géodésiques à une représentation factorielle dans ISOMAP ?

← Module NL LLE →