Laplacian Eigenmaps : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Les Laplacian Eigenmaps (cartes propres laplaciennes) constituent l’une des méthodes les plus élégantes de réduction de dimensionalité non linéaire. Introduites par Belkin et Niyogi en 2001, elles reposent sur un principe fondamental : préserver la structure locale des données en les projetant dans un espace de plus faible dimension tout en maintenant les points voisins proches les uns des autres.

Contrairement à l’ACP qui cherche à maximiser la variance globale, ou à Isomap qui préserve les distances géodésiques globales, les Laplacian Eigenmaps se concentrent exclusivement sur la préservation de la proximité locale. Cette approche repose sur la théorie spectrale des graphes et la géométrie riemannienne, ce qui en fait un outil puissant pour l’exploration de variétés de haute dimension.

Dans cet article, nous explorerons en profondeur le principe mathématique des Laplacian Eigenmaps, l’intuition géométrique sous-jacente, et nous fournirons une implémentation Python complète avec scikit-learn.

Principe mathématique

Le fonctionnement des Laplacian Eigenmaps se décompose en quatre étapes fondamentales.

Étape 1 : Construction du graphe de voisinage

On dispose d’un ensemble de n points de données X = {x₁, x₂, …, xₙ} dans un espace ℝᴰ. La première étape consiste à construire un graphe pondéré G = (V, E) où chaque sommet vᵢ correspond à un point xᵢ.

Pour établir les arêtes, on utilise généralement la méthode des k plus proches voisins (k-PPV) : chaque point xᵢ est connecté à ses k voisins les plus proches selon une métrique euclidienne. On note N(i) l’ensemble des indices des k plus proches voisins de xᵢ.

Étape 2 : Pondération des arêtes

Une fois les connexions définies, on attribue à chaque arête un poids wᵢⱼ qui mesure la similarité entre les points xᵢ et xⱼ. Le schéma de pondération le plus courant utilise un noyau gaussien :

wᵢⱼ = exp(-‖xᵢ - xⱼ‖² / t)   si j ∈ N(i) ou i ∈ N(j)
wᵢⱼ = 0                       sinon

où t est un paramètre d’échelle (température) qui contrôle la décroissance du poids en fonction de la distance. Plus t est grand, plus le noyau est large et plus les points éloignés ont encore une influence notable. Plus t est petit, plus seuls les très proches voisins ont un poids significatif.

Une alternative simple consiste à utiliser des poids binaires : wᵢⱼ = 1 si les points sont connectés, 0 sinon (affinité “nearest_neighbors” dans scikit-learn).

Étape 3 : Construction de la matrice laplacienne

On définit ensuite la matrice de degré D, qui est une matrice diagonale dont chaque élément diagonal vaut :

Dᵢᵢ = Σⱼ wᵢⱼ

La matrice laplacienne (ou laplacien du graphe) est alors définie par :

L = D - W

où W est la matrice de poids (matrice d’adjacence pondérée). Cette matrice L possède des propriétés mathématiques remarquables : elle est symétrique, semi-définie positive, et ses valeurs propres sont réelles et positives ou nulles.

Il existe également la version normalisée du laplacien, notée L_sym = I – D⁻¹⁄² W D⁻¹⁄², qui présente de meilleures propriétés numériques et qui est celle utilisée par défaut dans la plupart des implémentations pratiques.

Étape 4 : Minimisation et problème aux valeurs propres

L’objectif fondamental des Laplacian Eigenmaps est de trouver une représentation de faible dimension Y = {y₁, y₂, …, yₙ} dans ℝᵈ (où d ≪ D) qui préserve au maximum les relations de voisinage.

La fonction à minimiser est la suivante :

min Σᵢⱼ ‖yᵢ - yⱼ‖² × wᵢⱼ

Cette expression se réécrit de manière élégante sous forme matricielle :

min yᵀ L y

sous les contraintes de normalisation yᵀ D y = 1 et yᵀ D 1 = 0 (pour éviter la solution triviale).

La résolution de ce problème d’optimisation conduit à un problème aux valeurs propres généralisé :

L y = λ D y

Les d plus petites valeurs propres non nulles et leurs vecteurs propres associés donnent directement la représentation en dimension d. Le vecteur propre associé à la plus petite valeur propre (λ = 0) est ignoré car il est constant, tandis que les d vecteurs propres suivants forment les coordonnées des points dans l’espace projeté.

Intuition géométrique : le modèle du ressort

Pour bien comprendre l’idée derrière les Laplacian Eigenmaps, imaginez la situation suivante.

Vous disposez d’un grand nombre de villes sur une carte très détaillée, en trois dimensions, avec des montagnes et des vallées. Votre objectif est de replacer toutes ces villes sur une surface plate (en deux dimensions) de manière à ce que les villes qui sont proches géographiquement restent proches sur la carte plate.

Maintenant, visualisez chaque lien du graphe de voisinage comme un ressort mécanique :

• Les villes très proches sont reliées par des ressorts courts qui exercent une forte traction.
• Les villes moins proches mais toujours voisines sont reliées par des ressorts plus longs et plus souples.
• Les villes éloignées n’ont aucun ressort les reliant.

Quand vous relâchez ce système de ressorts, il se stabilise dans une configuration où :

• les villes connectées par des ressorts forts (très proches) restent effectivement proches les unes des autres ;
• les villes sans connexion directe peuvent se retrouver n’importe où — il n’y a pas de contrainte sur leur position relative.

C’est exactement ce que font les Laplacian Eigenmaps. La minimisation de yᵀLy revient à trouver la configuration d’équilibre de ce système de ressorts, où chaque lien pondéré tire les points connectés pour les rapprocher proportionnellement à leur poids.

Là où les Laplacian Eigenmaps se distinguent d’autres approches, c’est qu’elles n’imposent aucune contrainte sur les points éloignés. Contrairement à l’Isomap qui cherche à préserver les distances globales, ou à l’ACP qui maximise la variance totale, cette méthode se concentre exclusivement sur ce qui se passe localement. Cela permet de révéler la structure intrinsèque de la variété sous-jacente, même quand celle-ci est fortement courbée ou enroulée dans l’espace de grande dimension.

Implémentation Python

L’implémentation des Laplacian Eigenmaps est disponible dans scikit-learn via la classe SpectralEmbedding, qui réalise exactement l’algorithme décrit ci-dessus avec un laplacien normalisé.

Exemple de base avec le Swiss Roll

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import SpectralEmbedding

# Générer les données Swiss Roll
n_samples = 1500
X, color = make_swiss_roll(n_samples, noise=0.1, random_state=42)

# Réduction de dimension avec Laplacian Eigenmaps
embedding = SpectralEmbedding(
    n_components=2,
    affinity="rbf",
    n_neighbors=15,
    gamma=0.5,
    random_state=42
)
X_embedded = embedding.fit_transform(X)

# Visualisation
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# Données originales (projection 3D vers 2D pour la visualisation)
axes[0].scatter(X[:, 0], X[:, 2], c=color, cmap="viridis", s=10)
axes[0].set_title("Données originales (Swiss Roll)")
axes[0].set_xlabel("x₁")
axes[0].set_ylabel("x₃")

# Données après Laplacian Eigenmaps
axes[1].scatter(X_embedded[:, 0], X_embedded[:, 1], c=color, cmap="viridis", s=10)
axes[1].set_title("Après Laplacian Eigenmaps (2D)")
axes[1].set_xlabel("Composante 1")
axes[1].set_ylabel("Composante 2")

plt.tight_layout()
plt.savefig("laplacian_eigenmaps_swiss_roll.png", dpi=150)
plt.show()

Impact du nombre de voisins (n_neighbors)

Le choix de k (le nombre de plus proches voisins) est crucial :

# Comparaison de différentes valeurs de n_neighbors
k_values = [5, 15, 50]

fig, axes = plt.subplots(1, 3, figsize=(18, 5))

for i, k in enumerate(k_values):
    embed = SpectralEmbedding(
        n_components=2,
        affinity="rbf",
        n_neighbors=k,
        gamma=1.0,
        random_state=42
    )
    X_emb = embed.fit_transform(X)

    axes[i].scatter(X_emb[:, 0], X_emb[:, 1], c=color, cmap="viridis", s=10)
    axes[i].set_title(f"n_neighbors = {k}")
    axes[i].set_xlabel("Composante 1")
    axes[i].set_ylabel("Composante 2")

plt.tight_layout()
plt.savefig("comparison_n_neighbors.png", dpi=150)
plt.show()

Avec un k trop petit (par exemple k = 5), le graphe risque d’être fragmenté en plusieurs composantes connexes, et chaque composante sera projetée indépendamment, ce qui peut produire des regroupements artificiels.

Avec un k trop grand (par exemple k = 50), le graphe devient trop dense et perd son caractère local : la méthode se rapproche alors d’une ACP et perd son pouvoir de dépliage de la variété.

La valeur optimale se situe généralement entre 10 et 30, selon la densité et la complexité des données.

Impact du type d’affinité (affinity)

# Comparaison des types d'affinité
affinities = ["rbf", "nearest_neighbors"]

fig, axes = plt.subplots(1, 2, figsize=(14, 5))

for i, aff in enumerate(affinities):
    embed = SpectralEmbedding(
        n_components=2,
        affinity=aff,
        n_neighbors=15,
        gamma=1.0,
        random_state=42
    )
    X_emb = embed.fit_transform(X)

    axes[i].scatter(X_emb[:, 0], X_emb[:, 1], c=color, cmap="viridis", s=10)
    axes[i].set_title(f"Affinité : {aff}")

plt.tight_layout()
plt.savefig("comparison_affinity.png", dpi=150)
plt.show()

L’affinité “rbf” (Radial Basis Function) utilise le noyau gaussien avec un paramètre gamma qui remplace le paramètre t de la formule wᵢⱼ = exp(-γ‖xᵢ – xⱼ‖²). L’affinité “nearest_neighbors” utilise des poids binaires (wᵢⱼ = 1 pour les voisins connectés), ce qui est plus simple mais parfois moins nuancé que le noyau gaussien.

Hyperparamètres

Voici les hyperparamètres clés de SpectralEmbedding dans scikit-learn :

Conseils de réglage

• n_components : commencez par 2 ou 3 pour la visualisation. Pour des tâches en aval (clustering, classification), testez des valeurs entre 5 et 50.
• n_neighbors : la valeur par défaut (5) est souvent trop faible. Essayez 10–30. Une règle empirique est de choisir k ≈ √n.
• gamma : la valeur automatique (médiane) fonctionne bien dans la plupart des cas. Diminuez gamma pour élargir le noyau (plus de connexions significatives), augmentez-le pour le resserrer.
• eigen_solver : pour les petits jeux de données (< 1000 points), laissez le choix automatique. Pour les grands jeux de données avec des matrices creuses, “arpack” est le plus efficace.

Avantages et limites

Avantages

1. Préservation exceptionnelle de la structure locale : les points voisins dans l’espace d’origine restent proches dans l’espace réduit, ce qui est idéal pour le clustering et la détection de communautés.
2. Fondation théorique solide : les Laplacian Eigenmaps sont intimement liées au laplacien de Laplace-Beltrami sur des variétés riemanniennes. Quand le nombre de points tend vers l’infini, les vecteurs propres convergent vers les fonctions propres du laplacien de la variété sous-jacente.
3. Extraction de structure non linéaire : contrairement à l’ACP qui ne capture que les relations linéaires, cette méthode déplie efficacement les variétés courbées.
4. Bonne performance en clustering : la matrice obtenue après embedding est particulièrement bien structurée pour les algorithmes de clustering comme k-means (c’est d’ailleurs le fondement du clustering spectral).
5. Pas de problème de “short-circuit” : contrairement à Isomap qui peut souffrir de raccourcis dans le calcul des distances géodésiques, les Laplacian Eigenmaps sont robustes à ces artefacts car elles ne calculent pas de chemins les plus courts.

Limites

1. Choix des hyperparamètres sensible : le nombre de voisins et le paramètre gamma du noyau influencent fortement le résultat. Un mauvais choix peut produire des embeddings de mauvaise qualité.
2. Pas de fonction de projection explicite : comme t-SNE et UMAP, les Laplacian Eigenmaps ne fournissent pas de fonction f(x) pour projeter de nouveaux points. Il faut reconstruire le graphe ou utiliser des techniques d’extension nyström.
3. Complexité computationnelle : la construction du graphe est en O(n² × D) sans structure accélératrice, et la diagonalisation du laplacien est en O(n³) dans le pire cas (bien que les solveurs itératifs réduisent cela à O(kn²) pour k vecteurs propres).
4. Sensibilité au bruit : les points aberrants peuvent créer des connexions trompeuses qui distordent l’embedding. Un prétraitement (filtrage, débruitage) est recommandé.
5. Dépendance à la connectivité du graphe : si le graphe n’est pas connexe (ce qui peut arriver avec un k trop petit), chaque composante est traitée indépendamment, ce qui peut produire un embedding fragmenté.

4 cas d’usage concrets

Cas d’usage 1 : Visualisation de données génomiques

En bioinformatique, les données d’expression génique comportent des milliers de gènes (dimensions) mesurés sur des centaines d’échantillons. Les Laplacian Eigenmaps permettent de visualiser ces données en 2D tout en préservant les regroupements biologiques naturels. Les cellules de même type ou les échantillons de mêmes conditions expérimentales forment naturellement des clusters dans l’espace réduit.

# Exemple conceptuel avec des données génomiques simulées
from sklearn.manifold import SpectralEmbedding
import numpy as np

# Simulation : 200 échantillons, 5000 gènes
np.random.seed(42)
X_genes = np.vstack([
    np.random.randn(50, 5000) + 1,   # Type cellulaire A
    np.random.randn(50, 5000) - 1,   # Type cellulaire B
    np.random.randn(50, 5000),        # Type cellulaire C
    np.random.randn(50, 5000) + 0.5  # Type cellulaire D
])

embed = SpectralEmbedding(n_components=2, affinity="rbf",
                          gamma=0.01, n_neighbors=10, random_state=42)
X_gene_emb = embed.fit_transform(X_genes)

Cas d’usage 2 : Détection de communautés dans les réseaux sociaux

Les Laplacian Eigenmaps sont au cœur du clustering spectral, utilisé pour détecter des communautés dans les réseaux sociaux. En projetant les nœuds du graphe dans un espace de faible dimension (via les vecteurs propres du laplacien), on peut ensuite appliquer un algorithme comme k-means pour identifier des groupes de nœuds fortement interconnectés.

Cas d’usage 3 : Traitement d’images et reconnaissance visuelle

En vision par ordinateur, les Laplacian Eigenmaps sont employés pour la réduction de dimension d’images avant classification. Par exemple, pour la reconnaissance de visages, chaque image est un vecteur de très haute dimension (pixels). L’embedding spectral révèle la structure non linéaire de l’espace des visages (variations d’éclairage, de pose, d’expression) bien mieux qu’une ACP classique.

Cas d’usage 4 : Analyse de documents et fouille de textes

Dans le domaine du traitement automatique du langage naturel, les documents sont représentés comme des vecteurs dans un espace de très grande dimension (sac de mots, TF-IDF, embeddings). Les Laplacian Eigenmaps permettent de préserver les relations sémantiques locales : des documents traitant de sujets similaires restent proches après projection, ce qui facilite la découverte de thèmes et la catégorisation automatique.

Voir aussi

• Optimisez Votre Code Python: Trouver le Sous-segment à Somme Maximale/Minimale
• Comment Calculer le Reste d’une Division Polynomiale en Python: Guide Pratique pour Les Développeurs