LLE (Locally Linear Embedding) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le LLE (Locally Linear Embedding) est un algorithme de réduction de dimensionalité non linéaire appartenant à la famille des méthodes de manifold learning. Développé par Sam Roweis et Lawrence Saul en 2000, cet algorithme repose sur une idée élégante : chaque point de données peut être reconstruit comme une combinaison linéaire de ses plus proches voisins, et cette relation de reconstruction locale doit être préservée dans l’espace de faible dimension. Contrairement à l’Analyse en Composantes Principales (ACP) qui projette globalement les données sur des axes de variance maximale, le LLE apprend une représentation intrinsèque en préservant la géométrie locale du manifold. Il est particulièrement efficace pour des données structurées en variétés non linéaires, comme le célèbre Swiss roll. Dans ce guide, nous explorons le principe mathématique du LLE locally linear embedding, son implémentation en Python avec scikit-learn, ses variantes et ses cas d’usage concrets.

Principe mathématique du LLE

L’algorithme Locally Linear Embedding se déroule en trois étapes fondamentales. Il s’agit d’une méthode en deux phases de calcul suivie d’une étape de résolution propre.

Étape 1 : Identification des voisins et calcul des poids de reconstruction

Pour chaque point $\mathbf{x}i$ de l’ensemble de données (où $i = 1, \ldots, N$), on identifie ses $k$ plus proches voisins selon une métrique euclidienne. Ensuite, on calcule les poids $W_i$ à partir de ses voisins, en résolvant le problème d’optimisation suivant :}$ qui reconstruisent le point $\mathbf{x

$$\min_{W} \sum_{i=1}^{N} \left| \mathbf{x}i – \sum_j \right|^2$$}(i)} W_{ij} \mathbf{x

sous les contraintes :

• $W_{ij} = 0$ si $j \notin \mathcal{N}(i)$ (le point $j$ n’est pas voisin de $i$)
• $\sum_{j} W_{ij} = 1$ pour chaque $i$ (les poids somment à 1)

Cette contrainte de somme unitaire garantit que la reconstruction est invariante par translation : si on décale tous les points d’un même vecteur, les poids optimaux ne changent pas. C’est cette propriété qui rend le LLE si puissant pour capturer la structure locale.

Mathématiquement, pour chaque point $\mathbf{x}i$, on résout un problème des moindres carrés contraint. Soit $C_k)$ la matrice de Gram locale (matrice des produits scalaires centrés), alors les poids optimaux s’obtiennent en résolvant le système linéaire :} = (\mathbf{x}_i – \mathbf{x}_j)^\top (\mathbf{x}_i – \mathbf{x

$$\sum_{k} C_{jk} W_{ik} = \lambda \quad \forall j$$

avec régularisation si nécessaire pour assurer la non-singularité.

Étape 2 : Calcul de l’embedding de faible dimension

Une fois la matrice des poids $W$ fixée (elle encode entièrement la géométrie locale), on cherche la matrice $Y \in \mathbb{R}^{N \times d}$ (où $d \ll D$ est la dimensionalité cible) qui minimise :

$$\Phi(Y) = \sum_{i=1}^{N} \left| \mathbf{y}i – \sum_j \right|^2$$}^{N} W_{ij} \mathbf{y

Ce critère peut se réécrire de manière compacte. En définissant $M = (I – W)^\top (I – W)$, où $I$ est la matrice identité et $W$ la matrice complète des poids, on obtient :

$$\Phi(Y) = \mathrm{tr}(Y^\top M Y)$$

La minimisation de ce critère sous les contraintes de centrage ($\sum_i \mathbf{y}_i = 0$) et de normalisation covariance ($\frac{1}{N} Y^\top Y = I_d$) se résout par diagonalisation de la matrice $M$. Les $d$ vecteurs propres associés aux $d$ plus petites valeurs propres non nulles de $M$ forment les coordonnées de l’embedding souhaité.

La matrice $M$ est de taille $N \times N$ et est généralement creuse (sparse) puisque chaque ligne de $W$ n’a que $k$ entrées non nulles. Cette structure creuse permet d’utiliser des algorithmes de diagonalisation efficaces (comme eigsh de SciPy) qui ne nécessitent pas de stocker $M$ en mémoire dense.

Étape 3 : Résultat

L’embedding final $Y$ préserve les relations de reconstruction locale : si deux points avaient une forte relation de voisinage dans l’espace original, cette relation se retrouve dans l’espace réduit. C’est ce qui donne au LLE locally linear embedding sa capacité à dérouler des structures courbes complexes.

Intuition derrière le LLE

L’intuition centrale du Locally Linear Embedding est à la fois simple et profonde. Imaginez que vous ayez une feuille de papier pliée en forme de rouleau suisse (Swiss roll). Chaque point de cette feuille connaît ses voisins immédiats. Si vous demandez à chaque point : « Comment te reconstruis-tu à partir de tes voisins les plus proches ? », chaque point répondra avec un ensemble de poids précis.

Le point-clé : cette reconstruction locale est invariante aux transformations globales du manifold. Qu’on déplie la feuille, qu’on la plie différemment, qu’on la tourne dans l’espace — les relations de voisinage local ne changent pas. Les poids $W_{ij}$ restent les mêmes.

Le LLE exploite cette invariance. Il calcule d’abord les poids localement (en supposant que le voisinage est approximativement plat, comme un petit morceau de plan tangent). Puis il cherche un arrangement global en faible dimension qui respecte exactement ces mêmes poids de reconstruction. Le résultat : un déploiement naturel du manifold qui préserve la topologie locale.

Cette approche contraste fortement avec les méthodes globales comme l’ACP : là où l’ACP écrase toute la structure sur des axes linéaires, le LLE respecte la courbure intrinsèque des données. Et contrairement à des méthodes basées sur les distances géodésiques comme Isomap, le LLE travaille directement avec des relations linéaires, ce qui le rend plus robuste au bruit dans certains cas.

Implémentation Python avec scikit-learn

La bibliothèque scikit-learn fournit une implémentation complète du LLE locally linear embedding via la classe LocallyLinearEmbedding du module manifold. Voici comment l’utiliser.

Exemple de base avec le Swiss roll

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

# Générer les données Swiss roll
X, color = datasets.make_swiss_roll(n_samples=1500, noise=0.05, random_state=42)

# Appliquer le LLE standard
lle = manifold.LocallyLinearEmbedding(
    n_neighbors=12,
    n_components=2,
    method='standard',
    random_state=42
)
X_r = lle.fit_transform(X)

# Visualisation
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
axes[0].scatter(X[:, 0], X[:, 2], c=color, cmap='viridis', s=10)
axes[0].set_title('Swiss roll 3D original')
axes[1].scatter(X_r[:, 0], X_r[:, 1], c=color, cmap='viridis', s=10)
axes[1].set_title('Projection LLE 2D')
plt.tight_layout()
plt.show()

Avec les bons paramètres, le LLE déroule magnifiquement le Swiss roll, révélant la structure rectangulaire sous-jacente. La couleur, qui encode la position le long du rouleau, se retrouve comme un gradient linéaire dans l’embedding 2D — preuve que la topologie intrinsèque a été préservée.

Variantes du LLE

scikit-learn propose plusieurs variantes du LLE, chacune adressant des faiblesses spécifiques de la méthode standard :

LLE Standard

lle_standard = manifold.LocallyLinearEmbedding(
    n_neighbors=12, n_components=2, method='standard', random_state=42
)
X_r = lle_standard.fit_transform(X)

C’est la méthode originale de Roweis et Saul (2000). Elle peut souffrir de problèmes de régularisation lorsque les voisins sont colinéaires ou lorsque $k$ est trop proche de la dimensionalité des données.

LLE Modifié (Modified LLE)

lle_modified = manifold.LocallyLinearEmbedding(
    n_neighbors=12, n_components=2, method='modified', random_state=42
)
X_r = lle_modified.fit_transform(X)

Le Modified LLE corrige le problème de régularisation du LLE standard en utilisant une matrice de covariance locale modifiée. Il est particulièrement utile quand le LLE standard produit des artefacts ou des résultats instables.

Hessian LLE (HLLE)

lle_hessian = manifold.LocallyLinearEmbedding(
    n_neighbors=20, n_components=2, method='hessian', random_state=42
)
X_r = lle_hessian.fit_transform(X)

Le Hessian LLE, proposé par Donoho et Grimes (2003), utilise l’opérateur de Hessian local plutôt que la simple reconstruction pondérée. Il peut produire de meilleurs résultats sur des manifolds très courbés, mais nécessite plus de voisins (typiquement $k \geq d(d+1)/2 + 1$ où $d$ est la dimensionalité cible).

LLE LTSA (Local Tangent Space Alignment)

lle_ltsa = manifold.LocallyLinearEmbedding(
    n_neighbors=12, n_components=2, method='ltsa', random_state=42
)
X_r = lle_ltsa.fit_transform(X)

Le LTSA (proposé par Zhang et Zha, 2004) aligne les espaces tangents locaux plutôt que de minimiser directement l’erreur de reconstruction. Il offre souvent une meilleure stabilité numérique.

Impact du nombre de voisins (n_neighbors)

Le paramètre n_neighbors est le plus critique du LLE :

• Trop peu de voisins ($k < 5$) : les poids de reconstruction sont instables, le graphe de voisinage peut devenir disconnected, et l’embedding présente des artefacts.
• Valeur modérée ($k \approx 10$-$20$) : c’est généralement la plage idéale. Le voisinage est assez grand pour une estimation stable des poids, mais assez petit pour rester local.
• Trop de voisins ($k > D$ ou $k \approx N$) : les relations deviennent globales et le LLE tend vers une solution proche de l’ACP, perdant son avantage non linéaire.

import numpy as np
from sklearn import datasets, manifold

X, color = datasets.make_swiss_roll(n_samples=1500, noise=0.05, random_state=42)

# Explorer l'impact de n_neighbors
fig, axes = plt.subplots(1, 4, figsize=(20, 5))
neighbors_list = [5, 12, 25, 50]

for ax, k in zip(axes, neighbors_list):
    lle = manifold.LocallyLinearEmbedding(n_neighbors=k, n_components=2,
                                           method='standard', random_state=42)
    X_r = lle.fit_transform(X)
    ax.scatter(X_r[:, 0], X_r[:, 1], c=color, cmap='viridis', s=10)
    ax.set_title(f'n_neighbors = {k}')
    ax.axis('off')

plt.tight_layout()
plt.show()

Hyperparamètres du LLE

Voici la liste complète des hyperparamètres de LocallyLinearEmbedding dans scikit-learn :

Conseils pratiques pour le réglage

1. Commencez avec n_neighbors=12 et method='standard' — c’est un bon point de départ pour la plupart des jeux de données.
2. Si le résultat semble bruité — augmentez reg à 0.01 ou 0.1, ou passez à method='modified'.
3. Si l’embedding est fragmenté — augmentez n_neighbors pour connecter les composantes.
4. Si l’embedding ressemble à une projection linéaire — réduisez n_neighbors pour renforcer la focalisation locale.

Avantages et Limites du LLE

Avantages du Locally Linear Embedding

• Préservation de la géométrie locale : Le LLE excelle à capturer la structure intrinsèque des données en manifold, contrairement aux méthodes linéaires.
• Pas d’hypothèse sur la distribution : Contrairement à l’ACP qui suppose une structure gaussienne, le LLE ne fait aucune hypothèse probabiliste sur les données.
• Un seul hyperparamètre critique : En pratique, seul n_neighbors a un impact majeur sur le résultat, ce qui simplifie le réglage.
• Pas de minimum local : Contrairement au t-SNE ou à certaines méthodes basées sur l’optimisation itérative, le LLE résout un problème propre (diagonalisation) avec une solution globale unique.
• Efficace sur des données de taille modérée : Pour $N < 10\,000$, le LLE est rapide et donne d’excellents résultats.

Limites du LLE

• Scalabilité : La diagonalisation de la matrice $M \in \mathbb{R}^{N \times N}$ coûte $O(N^3)$ dans le pire cas. Pour de très grands jeux de données ($N > 50\,000$), le LLE devient impraticable.
• Sensibilité au bruit : Si les données contiennent du bruit significatif, la reconstruction locale peut être dégradée, entraînant des poids instables.
• Nouveaux points (out-of-sample) : Le LLE standard ne fournit pas de fonction de mapping explicite. Pour projeter de nouvelles données, il faut ré-appliquer l’algorithme complet ou utiliser des techniques d’approximation.
• Manifolds non uniformément échantillonnés : Les zones de forte densité reçoivent plus de poids dans la reconstruction, ce qui peut créer des distorsions. Le LTSA ou le HLLE peuvent partiellement corriger ce problème.
• Choix de n_neighbors : Un mauvais choix peut totalement détruire la qualité de l’embedding. Il n’existe pas de règle universelle pour le déterminer.

4 Cas d’usage concrets du LLE

1. Visualisation de données de forme complexe

Le cas d’usage le plus classique : visualiser des données en haute dimension qui reposent sur un manifold non linéaire. Par exemple, des images de visages sous différents angles et éclairages forment un manifold de faible dimension intrinsèque. Le LLE peut réduire ces images en 2D ou 3D tout en préservant la continuité des variations (angle d’éclairage, orientation du visage).

from sklearn import datasets, manifold
from sklearn.decomposition import PCA

# Réduction initiale par ACP pour passer en-dessous de 100 dimensions
pca = PCA(n_components=50, random_state=42)
X_pca = pca.fit_transform(X)

# Puis LLE pour la visualisation 2D
lle = manifold.LocallyLinearEmbedding(n_neighbors=15, n_components=2,
                                       random_state=42)
X_2d = lle.fit_transform(X_pca)

2. Analyse de données spectroscopiques et médicales

En spectroscopie infrarouge, chaque échantillon génère un spectre de plusieurs milliers de points. Ces spectres résident sur un manifold de faible dimension déterminé par les concentrations des composants chimiques et les conditions physiques. Le LLE peut révéler des clusters correspondant à différents états pathologiques ou compositions chimiques, souvent avec une meilleure séparation que l’ACP.

3. Traitement du langage et embeddings de documents

Bien que moins courant que le t-SNE ou l’UMAP pour la visualisation NLP, le LLE peut être appliqué à des embeddings de mots ou de documents (Word2Vec, BERT, TF-IDF). Pour des corpus de taille modérée, le Modified LLE produit souvent des visualisations 2D où les documents thématiquement proches forment des clusters cohérents, tout en préservant les relations inter-cluster.

4. Analyse de données génomiques et protéomiques

Les données d’expression génique (RNA-seq, microarrays) présentent souvent une structure de manifold correspondant aux voies biologiques actives. Le LLE est utilisé pour identifier des sous-populations cellulaires dans des données de cytométrie de masse ou de single-cell RNA-seq. L’avantage du LLE sur l’ACP ici est sa capacité à capturer les relations non linéaires entre gènes, révélant des transitions cellulaires continues plutôt que des séparations brusques.

Conclusion

Le LLE locally linear embedding reste une méthode fondamentale du manifold learning. Son principe — reconstruire localement puis préserver globalement — est élégant et mathématiquement propre. Bien que des méthodes plus récentes comme l’UMAP soient devenues plus populaires pour leur scalabilité et leur robustesse, le LLE conserve sa place dans la boîte à outils du praticien, particulièrement pour l’exploration de données de taille modérée où la fidélité de la structure locale est primordiale. Sa compréhension approfondie est également un excellent tremplin pour saisir les méthodes de réduction de dimensionalité non linéaire plus avancées.

Voir aussi

• Maîtrisez les Périodes de Pisano en Python : Guide Complet pour Développeurs
• Windows | Ajouter Git aux variables d’environnement