Isomap : Guide complet — Principes, Exemples et Implémentation Python
Résumé
Isomap (Isometric Mapping) est un algorithme de réduction de dimensionalité non linéaire introduit par Joshua Tenenbaum, Vin de Silva et John Langford en 2000. Contrairement à l’Analyse en Composantes Principales (ACP) qui projette les données sur des sous-espaces linéaires, Isomap préserve la géométrie intrinsèque des variétés non linéaires en estimant les distances géodésiques le long de la structure des données. Cette approche permet de découvrir la véritable dimensionalité des données tout en respectant leur courbure naturelle. Isomap se situe dans la famille des méthodes de manifold learning et constitue une étape fondamentale entre les techniques linéaires classiques et les approches modernes comme t-SNE et UMAP.
Principe mathématique de l’algorithme Isomap
L’algorithme Isomap repose sur trois étapes fondamentales qui transforment des données haute dimensionalité en un embedding basse dimensionalité tout en préservant la géométrie globale du manifold.
Étape 1 : Construction du graphe des k plus proches voisins
La première étape consiste à construire un graphe de voisinage où chaque point de données est un sommet. On relie deux sommets par une arête si l’un des deux points figure parmi les k plus proches voisins de l’autre. Le poids de chaque arête correspond à la distance euclidienne entre les deux points connectés.
Formellement, pour un ensemble de données X = {x₁, x₂, …, xₙ} ⊂ ℝᴰ, on construit un graphe G = (V, E) où :
– V = {1, 2, …, n} représente l’ensemble des sommets
– (i, j) ∈ E si xⱼ ∈ Nₖ(xᵢ) ou xᵢ ∈ Nₖ(xⱼ), où Nₖ(xᵢ) désigne l’ensemble des k plus proches voisins de xᵢ
– Le poids de l’arête wᵢⱼ = ||xᵢ – xⱼ||₂ (distance euclidienne)
Il existe deux variantes principales pour déterminer les voisinages : la méthode des k plus proches voisins (k-NN) où k est un paramètre fixe, et la méthode ε-voisinage où l’on relie tous les points séparés par une distance inférieure à un seuil ε. La première approche est la plus couramment utilisée en pratique grâce à son contrôle direct sur la connectivité du graphe.
Étape 2 : Calcul des distances géodésiques par plus court chemin
C’est ici que réside l’innovation centrale d’Isomap. Au lieu d’utiliser les distances euclidiennes directes entre points (qui traversent l’espace ambiant), Isomap estime les distances géodésiques — c’est-à-dire les distances le long de la surface courbe du manifold.
Pour calculer ces distances géodésiques, Isomap utilise l’algorithme de Dijkstra (ou alternativement l’algorithme de Floyd-Warshall) sur le graphe construit à l’étape précédente. L’algorithme de Dijkstra calcule le plus court chemin entre un nœud source et tous les autres nœuds du graphe, en considérant la somme des poids des arêtes traversées.
La matrice des distances géodésiques Dᴳ est de taille n × n, où Dᴳᵢⱼ représente la longueur du plus court chemin entre les sommets i et j dans le graphe. Si deux sommets ne sont pas connectés (graphe non connexe), la distance est définie comme infinie.
L’algorithme de Floyd-Warshall offre une alternative : il calcule simultanément les plus courts chemins entre toutes les paires de sommets, avec une complexité en O(n³). Dijkstra, appliqué n fois (une fois par source), atteint une complexité en O(n · (m + n log n)) avec une file de priorité, où m est le nombre d’arêtes. En pratique, Isomap utilise généralement Floyd-Warshall pour sa simplicité d’implémentation, bien que Dijkstra soit plus efficace pour les grands jeux de données.
Étape 3 : MDS classique sur la matrice des distances géodésiques
La dernière étape applique l’algorithme de Multidimensional Scaling (MDS) classique à la matrice des distances géodésiques Dᴳ. Le MDS classique procède comme suit :
- On transforme la matrice des distances géodésiques en une matrice de similarité via le double centrage : B = -½ · J · Dᴳ² · J, où J = I – (1/n)·1·1ᵀ est la matrice de centrage.
- On effectue une décomposition en valeurs propres de la matrice B : B = VΛVᵀ.
- On sélectionne les d plus grandes valeurs propres λ₁ ≥ λ₂ ≥ … ≥ λ_d > 0 et leurs vecteurs propres correspondants v₁, v₂, …, v_d.
- L’embedding final en dimension d est obtenu par : Y = V_d · Λ_d^(½), où V_d contient les d vecteurs propres et Λ_d est la matrice diagonale des d valeurs propres.
Le résultat est une représentation en basse dimensionalité où les distances euclidiennes entre points approximent au mieux les distances géodésiques du manifold original.
Intuition : pourquoi Isomap change tout
Imaginez que vous souhaitiez mesurer la distance entre deux villes. La distance euclidienne, c’est la distance à vol d’oiseau : un trait droit sur une carte, qui traverse montagnes, rivières et bâtiments comme s’ils n’existaient pas. La distance géodésique, c’est la distance en suivant les routes : on respecte le relief, les contours, la structure réelle du terrain.
Isomap fait exactement cela pour vos données. Prenons l’exemple classique du Swiss roll (rouleau suisse) : imaginez une feuille de papier enroulée en spirale dans l’espace tridimensionnel. Deux points peuvent être très proches dans l’espace ambiant (à vol d’oiseau, ils se touchent presque) tout en étant très éloignés l’un de l’autre si l’on parcourt la surface du papier. L’ACP, qui ne voit que des droites, écraserait le rouleau et mélangerait des points qui sont en réalité très éloignés sur la variété. Isomap, lui, « déroule » le rouleau en suivant sa surface, préservant la véritable structure des données.
Cette intuition est fondamentale : Isomap ne projette pas les données — il les déroule. Il respecte la topologie du manifold au lieu de l’aplatir bêtement dans un sous-espace linéaire.
Implémentation Python avec scikit-learn
Exemple de base avec le Swiss roll
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.manifold import Isomap
from sklearn.decomposition import PCA
# Générer le dataset Swiss roll (300 points)
X, color = datasets.make_swiss_roll(n_samples=300, noise=0.1, random_state=42)
# Appliquer Isomap avec 12 voisins et 2 composantes
isomap = Isomap(n_neighbors=12, n_components=2)
X_isomap = isomap.fit_transform(X)
# Visualisation
fig, axes = plt.subplots(1, 3, figsize=(15, 4))
# Vue 3D du Swiss roll original
ax = axes[0]
ax.scatter(X[:, 0], X[:, 2], c=color, cmap='viridis')
ax.set_title('Swiss Roll original (3D)')
ax.set_xlabel('X')
ax.set_ylabel('Z')
# Résultat Isomap
ax = axes[1]
ax.scatter(X_isomap[:, 0], X_isomap[:, 1], c=color, cmap='viridis')
ax.set_title(f'Isomap (n_neighbors=12)')
ax.set_xlabel('Composante 1')
ax.set_ylabel('Composante 2')
# Comparaison avec PCA
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)
ax = axes[2]
ax.scatter(X_pca[:, 0], X_pca[:, 1], c=color, cmap='viridis')
ax.set_title('PCA (2 composantes)')
ax.set_xlabel('CP1')
ax.set_ylabel('CP2')
plt.tight_layout()
plt.savefig('isomap_vs_pca.png', dpi=150)
plt.show()
Comparaison détaillée : Isomap vs PCA
La différence entre Isomap et PCA est radicale sur des données non linéaires. Le PCA projette les données sur les directions de plus grande variance — il écrase le Swiss roll comme une crêpe, perdant toute la structure en spirale. Isomap, en revanche, déroule progressivement la spirale et retrouve la structure rectangulaire sous-jacente.
On peut quantifier cette différence en mesurant la corrélation entre les distances originales (géodésiques pour Isomap, euclidiennes pour PCA) et les distances dans l’embedding :
from scipy.spatial.distance import pdist
from scipy.stats import spearmanr
# Distances dans l'espace original (géodésiques pour Isomap)
dist_orig = isomap.dist_matrix_
dist_isomap_2d = pdist(X_isomap)
# Corrélation de Spearman pour le PCA
dist_pca_2d = pdist(X_pca)
rho_pca, _ = spearmanr(dist_orig.ravel(), pdist(X).r())
rho_isomap, _ = spearmanr(dist_orig.ravel(), dist_isomap_2d)
print(f"Corrélation PCA : {rho_pca:.3f}")
print(f"Corrélation Isomap : {rho_isomap:.3f}")
En pratique, on observe typiquement une corrélation nettement supérieure pour Isomap sur le Swiss roll, confirmant qu’il préserve mieux la structure géométrique intrinsèque.
Impact du paramètre n_neighbors
Le choix de n_neighbors est crucial et mérite une attention particulière :
- Trop petit (k < 5) : le graphe devient fragmenté, avec de nombreux sous-graphes non connectés. Les distances géodésiques deviennent infinies entre composantes déconnectées, et l’algorithme échoue.
- Juste (k ≈ 10-20) : le graphe est bien connecté, les chemins géodésiques suivent raisonnablement la surface du manifold. C’est la zone idéale.
- Trop grand (k > 50) : le graphe devient trop dense, les arêtes créent des « raccourcis » à travers les trous du manifold, et les distances géodésiques se confondent avec les distances euclidiennes — on perd l’avantage non linéaire.
# Étudier l'impact de n_neighbors
fig, axes = plt.subplots(2, 3, figsize=(15, 10))
for i, k in enumerate([5, 8, 12, 20, 50, 100]):
ax = axes[i // 3, i % 3]
try:
iso = Isomap(n_neighbors=k, n_components=2)
X_emb = iso.fit_transform(X)
ax.scatter(X_emb[:, 0], X_emb[:, 1], c=color, cmap='viridis')
ax.set_title(f'n_neighbors={k}')
except Exception as e:
ax.text(0.5, 0.5, f'Erreur: {str(e)[:50]}',
ha='center', va='center', transform=ax.transAxes)
plt.tight_layout()
plt.savefig('isomap_neighbors_impact.png', dpi=150)
plt.show()
Impact du paramètre n_components
Le paramètre n_components détermine la dimensionalité de l’embedding de sortie. Contrairement au PCA où l’on examine le pourcentage de variance expliquée, avec Isomap on peut s’appuyer sur les valeurs propres du MDS pour choisir la dimension intrinsèque :
iso_full = Isomap(n_neighbors=12, n_components=min(X.shape[0]-1, 10))
iso_full.fit(X)
# Examiner les valeurs propres
eigenvalues = iso_full.eigenvalues_
plt.figure(figsize=(8, 4))
plt.bar(range(len(eigenvalues)), np.abs(eigenvalues), color='steelblue')
plt.xlabel('Composante')
plt.ylabel('Valeur propre')
plt.title('Spectre des valeurs propres — Isomap')
plt.tight_layout()
plt.savefig('isomap_eigenvalues.png', dpi=150)
plt.show()
Les valeurs propres qui chutent brutalement indiquent la dimensionalité intrinsèque du manifold. Pour le Swiss roll, on attend un décrochement après la deuxième composante, confirmant que la dimensionalité intrinsèque est de 2 (une surface bidimensionnelle enroulée dans ℝ³).
Hyperparamètres d’Isomap en détail
n_neighbors
Le nombre de voisins utilisés pour construire le graphe. C’est l’hyperparamètre le plus important et le plus sensible. Valeurs typiques : 5 à 30. Il n’existe pas de règle universelle — un balayage systématique avec validation visuelle ou quantitative est recommandé. Certains praticiens recommandent de choisir k tel que le graphe soit à la limite de la connexité (le plus petit k garantissant un graphe connexe).
n_components
La dimensionalité de la projection. Correspond au nombre de dimensions de l’embedding de sortie. Pour de la visualisation, on fixe généralement n_components=2 ou 3. Pour du prétraitement avant classification, on peut choisir une valeur plus élevée basée sur l’analyse du spectre des valeurs propres.
eigen_solver
L’algorithme utilisé pour le calcul des valeurs propres de la matrice de similarité :
– ‘auto’ (par défaut) : sélection automatique entre ‘arpack’ et ‘dense’ selon la taille des données
– ‘arpack’ : utilise la décomposition ARPACK, efficace pour les grandes matrices creuses
– ‘dense’ : décomposition complète en valeurs propres, plus précise mais gourmande en mémoire
path_method
L’algorithme de calcul des plus courts chemins :
– ‘auto’ (par défaut) : sélection automatique
– ‘FW’ : algorithme de Floyd-Warshall, complexité O(n³), adapté aux données de taille modérée
– ‘D’ : algorithme de Dijkstra, complexité O(n · (m + n log n)), plus efficace pour les grands jeux de données avec des graphes peu denses
neighbors_algorithm
L’algorithme utilisé pour la recherche des plus proches voisins :
– ‘auto’ : sélection automatique
– ‘ball_tree’ : arbre de Boule, efficace pour les données de dimensionalité modérée
– ‘kd_tree’ : arbre k-d, performant en faible dimensionalité
– ‘brute’ : recherche exhaustive, fiable quelle que soit la dimensionalité mais coûteux
Avantages et limites d’Isomap
Avantages
- Préservation de la géométrie globale : Contrairement à t-SNE qui ne préserve que la structure locale, Isomap capture la structure géométrique globale du manifold grâce aux distances géodésiques.
- Pas d’hypothèse linéaire : Fonctionne sur des variétés courbes où PCA échoue complètement.
- Algorithme déterministe : Aucun caractère aléatoire, les résultats sont parfaitement reproductibles.
- Interprétation claire : Le principe des trois étapes est mathématiquement transparent et facile à expliquer.
- Estimation de la dimensionalité intrinsèque : Le spectre des valeurs propres fournit une indication naturelle de la vraie dimensionalité des données.
Limites
- Sensibilité au paramètre n_neighbors : Un mauvais choix peut fragmenter le graphe ou créer des raccourcis artefactuels.
- Coût computationnel élevé : Le calcul des plus courts chemins (Floyd-Warshall en O(n³)) et la décomposition en valeurs propres rendent Isomap peu adapté aux très grands jeux de données (n > 10 000).
- Sensibilité au bruit et aux outliers : Les points aberrants peuvent créer des arêtes parasites dans le graphe de voisinages, faussant les distances géodésiques.
- Échec sur les manifolds à topologie complexe : Isomap suppose que le manifold est homéomorphe à un sous-espace convexe. Les structures avec des trous (comme un tore) peuvent poser problème.
- Pas d’embedding pour de nouvelles données : Isomap est une méthode transductive — il n’existe pas de fonction de projection directe pour des points non vus durant l’entraînement.
4 cas d’usage concrets d’Isomap
1. Analyse d’images de visages
Le jeu de données classique des visages sous différentes poses et éclairages forme un manifold non linéaire. Chaque dimension intrinsèque correspond à un facteur de variation : angle de rotation, intensité lumineuse, expression faciale. Isomap permet de retrouver ces facteurs en déroulant le manifold d’images, révélant que les visages varient selon seulement 2 ou 3 dimensions intrinsèques malgré la dimensionalité apparente de milliers de pixels.
2. Réduction de dimensionalité en bioinformatique
L’analyse de données de séquençage génomique (RNA-seq) produit des matrices de dizaines de milliers de gènes. Les cellules suivent des trajectoires de différenciation qui forment des manifolds courbes dans cet espace de grande dimension. Isomap peut révéler la structure de ces trajectoires de développement cellulaire, identifiant les états intermédiaires de différenciation que PCA manquerait.
3. Traitement du langage naturel
Les embeddings de mots (comme Word2Vec ou GloVe) vivent dans des espaces de 300 dimensions où la structure sémantique est non linéaire. Isomap peut projeter ces embeddings en 2D pour la visualisation, en préservant les relations sémantiques globales. Les mots similaires restent proches, et les axes de l’embedding peuvent révéler des directions sémantiques interprétables (genre, intensité, temporalité).
4. Robotique et navigation
En robotique mobile, les perceptions d’un robot (images de caméra, lectures de capteurs) forment un manifold dont la dimensionalité intrinsèque correspond aux degrés de liberté du robot dans son environnement. Isomap peut extraire cette structure latente, permettant au robot de se localiser et de planifier des trajectoires dans l’espace des perceptions plutôt que dans l’espace physique direct.
Voir aussi
- Python : Apprendre à utiliser pandas
- Créer des Ellipses Croisées en Python : Guide Complet pour la Visualisation et la Manipulation
