UMAP
Uniform Manifold Approximation and Projection — fondements topologiques, graphe de voisinage flou, plus rapide et plus fidèle que t-SNE pour la structure globale.
1. Fondements théoriques
UMAP repose sur la théorie de la topologie algébrique et la géométrie de Riemann. L'hypothèse centrale : les données sont échantillonnées uniformément sur une variété de Riemann localement connexe. UMAP construit une représentation de cette variété sous forme de graphe simpicial flou, puis optimise un graphe similaire en basse dimension.
2. Algorithme UMAP
Construire le graphe de voisinage flou (haute dim.)
Pour chaque point \(x_i\), calculer les k plus proches voisins. Pour chaque paire \((i,j)\), calculer la probabilité de connexion :
Symétriser le graphe
Combiner les probabilités directionnelles pour obtenir un graphe non-orienté : \(w_{ij} = v_{ij} + v_{ji} - v_{ij} \cdot v_{ji}\) (union floue).
Optimiser le graphe basse dimension
Initialiser une représentation basse dimension (ex : par ACP spectrale). Minimiser la divergence entre les deux graphes par descente de gradient stochastique.
3. Les fonctions de similarité
d(xᵢ,xⱼ) : distance entre xᵢ et son voisin xⱼ ·
ρᵢ : distance au plus proche voisin de xᵢ (normalisation locale)σᵢ : paramètre de lissage calibré pour assurer la connectivitéInterprétation : chaque point a sa propre métrique locale — les zones denses et rares sont traitées uniformément.
Dans l'espace réduit, UMAP utilise une famille de courbes paramétrée par \(a\) et \(b\) (déterminés par \(min\_dist\)) :
a, b : paramètres déterminés par \(min\_dist\) (taille minimale des clusters) ·
Pour \(a=1, b=1\) on retrouve la distribution de Student de t-SNE.\(min\_dist\) élevé → clusters plus étalés · \(min\_dist\) faible → clusters très serrés
4. Fonction de coût
Deux termes : attractif (\(w_{ij}\) élevé → rapprocher) et répulsif (\(1-w_{ij}\) élevé → éloigner).
Minimisée par descente de gradient stochastique (SGD) avec negative sampling.
5. Paramètres d'UMAP
Nombre de voisins locaux. Analogue à la perplexité de t-SNE.
Petit → structure très locale · Grand → structure globale préservée
Distance minimale entre points dans l'espace réduit.
Faible → clusters serrés · Élevé → points plus étalés, structure globale visible
6. UMAP vs t-SNE — les différences clés
t-SNE (perplexité = 15)
Clusters serrés, distances inter-clusters non fiables
UMAP (n_neighbors = 15)
Structure locale ET globale préservée
7. Tableau comparatif — toutes les méthodes
Récapitulatif ACP / ISOMAP / LLE / t-SNE / UMAP
📌 À retenir / À l'examen
- UMAP = graphe de voisinage flou haute dim. → optimisation vers graphe flou basse dim.
- Similarité haute dim. : \(v_{ij} = \exp(-(d(x_i,x_j)-\rho_i)/\sigma_i)\) — métrique locale par point
- Similarité basse dim. : \(w_{ij}^{low} = 1/(1+a\|y_i-y_j\|^{2b})\)
- Coût : entropie croisée binaire entre les deux graphes (attractif + répulsif)
- Avantage sur t-SNE : préserve la structure globale, plus rapide, peut projeter de nouveaux points
- Paramètres : \(n\_neighbors\) (comme perplexité) et \(min\_dist\) (compacité des clusters)
- Différence fondamentale t-SNE/UMAP : t-SNE = distances probabilistes · UMAP = topologie fuzzy