📊 statistics

Cluster and then Embed: A Modular Approach for Visualization

Cet article propose un cadre de visualisation modulaire et transparent qui améliore les méthodes telles que t-SNE et UMAP en regroupant séquentiellement les données, en intégrant chaque groupe individuellement, puis en les alignant pour préserver à la fois la structure locale et la géométrie globale.

Auteurs originaux : Elizabeth Coda, Ery Arias-Castro, Gal Mishne

Publié 2026-07-13

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Elizabeth Coda, Ery Arias-Castro, Gal Mishne

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous ayez une boîte géante et désordonnée de sculptures LEGO en 3D. Certaines sont de minuscules châteaux complexes ; d'autres sont des villes tentaculaires et plates. Votre objectif est de prendre des photos de toutes ces sculptures et de les disposer sur une table plate en 2D afin de voir comment elles se rapportent les unes aux autres.

Le problème ? Si vous écrasez toute la boîte sur la table d'un seul coup, les villes plates se font broyer, et les châteaux se chevauchent pour former un énorme amas confus. C'est le « problème de l'encombrement » qui frappe les outils populaires comme t-SNE et UMAP. Ils sont excellents pour préserver les détails minuscules de chaque château, mais ils déforment souvent la carte, faisant en sorte que des châteaux éloignés semblent être juste à côté les uns des autres.

Entrez dans la méthode Cluster+Embed (C+E), une nouvelle approche proposée par Elizabeth Coda, Ery Arias-Castro et Gal Mishne. Considérez cette méthode non pas comme un unique appareil photo magique, mais comme une chaîne de montage en trois étapes qui traite vos données comme une collection de quartiers distincts.

Étape 1 : Le tri des quartiers

D'abord, la méthode ne tente pas de photographier toute la boîte à la fois. Au lieu de cela, elle agit comme un bibliothécaire super organisé qui trie les sculptures LEGO en tas séparés selon leur forme. Si vous avez un tas de châteaux et un tas de villes, ils sont séparés dans des bacs différents. Les auteurs notent que vous pouvez utiliser n'importe quelle méthode de tri (comme les algorithmes populaires Leiden ou DBSCAN), mais la clé est que vous définissez les groupes avant de prendre la photo.

Étape 2 : Les photos individuelles

Ensuite, la méthode prend une photo de chaque tas individuellement. Parce que le bibliothécaire ne regarde qu'un seul tas de châteaux à la fois, il peut disposer les châteaux parfaitement pour montrer leurs détails complexes sans se soucier de l'interférence des villes. Cette étape utilise des outils standards (comme PCA ou TriMap) pour aplatir uniquement ce groupe spécifique. Le résultat ? Une photo cristalline et de haute qualité des châteaux, et une autre photo, tout aussi claire, des villes.

Étape 3 : La carte globale

C'est ici que réside l'astuce. Maintenant, vous avez une pile de photos parfaites et séparées. L'étape finale consiste à scotcher ces photos sur un grand mur pour créer une grande carte. Mais au lieu de les coller de manière aléatoire, la méthode utilise une « transformation rigide » — imaginez que vous preniez une photo entière du tas de châteaux et que vous la fassiez glisser, la fassiez pivoter ou la retourniez, mais sans jamais étirer ou écraser la photo elle-même.

L'objectif est de positionner ces tas de sorte que la distance entre le « tas de châteaux » et le « tas de villes » sur le mur corresponde à la distance qu'ils avaient dans la boîte d'origine. Pour résoudre le problème de l'encombrement (où il n'y a pas assez de place sur le mur pour tout le monde), la méthode introduit un « bouton de réglage de l'échelle » (appelé $\alpha$ ). Si les tas sont trop proches et risquent de se chevaucher, les auteurs suggèrent de tourner ce bouton pour repousser doucement les tas, créant juste assez d'espace pour que chacun soit vu clairement sans déformer les détails internes des photos.

Ce à quoi cette méthode dit « Non »

Les auteurs sont très clairs sur ce qu'ils combattent. Ils soutiennent l'idée qu'un outil unique et tout-en-un (comme t-SNE ou UMAP) ne peut pas parfaitement accomplir deux choses contradictoires à la fois : préserver parfaitement les petits détails locaux et maintenir l'exactitude des distances globales. Ils montrent que si t-SNE est excellent pour séparer les clusters, il déforme souvent la « carte » à tel point que l'on ne peut pas se fier aux distances entre les groupes. Ils excluent également explicitement l'idée que l'on puisse simplement forcer un arbre hiérarchique sur une carte sans un processus structuré ; leur méthode est un pipeline délibéré, transparent et en trois étapes, et non une boîte noire.

À quel point sont-ils sûrs d'eux ?

Les auteurs ne prétendent pas que c'est une solution miracle qui résout tout pour toujours. Au lieu de cela, ils présentent des preuves solides issues de simulations et de données réelles.

Sur les données synthétiques : Ils ont testé leur méthode sur un modèle de mélange gaussien à 10 dimensions avec 5 000 points. Dans ces simulations, ils ont montré qu'avec un facteur d'échelle de $\alpha = 2$ , leur méthode évitait le chevauchement qui affectait les autres méthodes, créant un anneau de clusters qui ressemblait beaucoup à t-SNE, mais obtenu via un processus transparent et contrôlable.
Sur les données réelles : Ils ont appliqué cela à trois ensembles de données réelles :
1. MNIST (Chiffres manuscrits) : Un ensemble de 60 000 images. Ici, C+E a réussi à séparer les chiffres en groupes (comme les quatre et les neuf étant proches) et a mieux préservé la structure globale que t-SNE, qui avait tendance à espacer tout le monde de manière égale.
2. Organoïdes cérébraux humains : Un ensemble de 20 272 cellules. La méthode a révélé une « trajectoire de développement » claire (un chemin de croissance au fil du temps) qui était visible dans leur carte, mais qui était plus « discrète » et moins continue dans t-SNE et UMAP.
3. Cortex de souris : Un ensemble de 23 822 cellules. Ici, C+E a révélé une structure « du grossier au fin » (de grands groupes se décomposant en plus petits) que d'autres méthodes avaient manquée.

Les auteurs admettent qu'il existe un compromis. Bien que C+E soit excellent pour préserver les distances globales et les formes locales, il peine parfois à égaler la capacité de t-SNE à maintenir parfaitement les plus proches voisins (rappel kNN) pour de petites valeurs de $k$ . Ils suggèrent que cela est dû au fait que t-SNE possède une façon mystérieuse de diviser les données en de minuscules fragments que C+E ne reproduit pas. Cependant, ils soutiennent que pour une visualisation qui est à la fois transparente et fidèle à la forme globale des données, C+E est une alternative hautement compétitive et beaucoup plus compréhensible.

En résumé, l'article suggère qu'en décomposant le problème en « tri, aplatissement, puis alignement », nous pouvons obtenir une carte qui ne ment pas sur l'emplacement des choses, même si cela nécessite quelques étapes supplémentaires pour y parvenir.

Résumé technique : Cluster and then Embed : Une approche modulaire pour la visualisation

Problématique

Les méthodes de réduction de dimensionnalité, en particulier t-SNE et UMAP, sont largement utilisées pour visualiser des données de haute dimension possédant des structures de grappes (clusters) latentes. Bien que ces méthodes regroupent efficacement les points de données et préservent l'information locale, elles sont connues pour déformer la géométrie globale des données sous-jacentes. Plus précisément, elles échouent souvent à préserver les positions relatives, les distances et les tailles de différents clusters. Cette limitation découle du « problème de l'encombrement » (crowding problem), où les espaces de plongement de faible dimension manquent de capacité pour accommoder tous les points aux échelles de distance originales de haute dimension, entraînant l'effondrement des points distants et le chevauchement de clusters distincts. Les méthodes existantes imposent souvent un compromis entre la préservation de la structure locale (séparation des clusters) et la préservation des distances globales.

Méthodologie : Le cadre Cluster+Embed (C+E)

Les auteurs proposent un cadre modulaire en trois étapes appelé Cluster+Embed (C+E) pour répondre au compromis entre fidélité locale et globale. L'approche découple le partitionnement (clustering), le plongement local et l'alignement global, permettant à l'analyste de choisir des algorithmes spécifiques pour chaque étape en fonction de ses objectifs de visualisation.

Étape 1 : Partitionnement (Clustering)

Les données $\{x_i\}_{i=1}^n$ sont d'abord partitionnées en $\kappa$ clusters ( $C_1, \dots, C_\kappa$ ) en utilisant n'importe quel algorithme de partitionnement choisi (par exemple, Leiden, DBSCAN, k-means). Cette étape révèle explicitement la structure de grappes présente dans les données. Les points identifiés comme du bruit peuvent être écartés à ce stade.

Étape 2 : Plongement de cluster individuel

Chaque cluster $C_l$ est plongé séparément dans un espace de faible dimension (typiquement $\mathbb{R}^2$ ) en utilisant une méthode de plongement choisie (par exemple, PCA, Isomap, TriMap).

Raisonnement : Le plongement individuel des clusters réduit la distorsion par rapport au plongement de l'ensemble du jeu de données, car le « problème de l'encombrement » est atténué au sein de sous-ensembles localisés plus restreints.
Mise à l'échelle : Si la méthode de plongement repose sur des informations ordinales, un facteur d'échelle $\gamma_l$ est appliqué à chaque cluster pour minimiser la perte quadratique entre les distances plongées et les dissimilarités originales.

Étape 3 : Alignement global

Les clusters plongés sont alignés dans un plongement global unique en utilisant uniquement des transformations rigides (translations, rotations et réflexions). L'objectif est de positionner les clusters les uns par rapport aux autres de manière à ce que les dissimilarités par paires entre les points de différents clusters soient préservées aussi fidèlement que possible.

Optimisation : L'alignement minimise une fonction de stress (stress de Kruskal) définie comme :
$\min_{T_1, \dots, T_\kappa} \sum_{1 \le i < j \le \kappa} \sum_{l \in C_i} \sum_{m \in C_j} (\delta_{lm} - \|T_i(y_l) - T_j(y_m)\|)^2$
où $\delta_{lm}$ est la dissimilarité originale et $T$ représente les transformations rigides.
Atténuation de l'encombrement via l'échelle ( $\alpha$ ) : Pour éviter le chevauchement dans la visualisation finale, les auteurs introduisent un paramètre de réglage $\alpha \ge 1$ $α \geq 1$ . La distance cible entre les clusters est mise à l'échelle par $\alpha \delta_{lm}$ $α δ_{l m}$ . Cela gonfle efficacement l'espace entre les clusters dans la carte de faible dimension, évitant ainsi le problème de l'encombrement.
- $\alpha$ peut être ajusté manuellement ou automatiquement. Une heuristique automatique est proposée : $\alpha = \max(1, \frac{\kappa \tau}{2\pi \Delta})$ , où $\tau$ est le diamètre moyen des clusters et $\Delta$ est la distance moyenne inter-clusters.

Principales contributions

Cadre modulaire : Le papier introduit une approche modulaire et transparente où le partitionnement, le plongement et l'alignement sont des étapes distinctes. Cela permet aux utilisateurs de choisir des algorithmes spécifiques pour chaque étape afin de cibler des propriétés de visualisation particulières (par exemple, utiliser TriMap pour le rappel kNN ou PCA pour la préservation des distances).
Contrôle explicite de la géométrie globale : Contra�à t-SNE et UMAP, qui gèrent de manière implicite et souvent opaque la structure globale via une dynamique de forces dirigées, C+E optimise explicitement la préservation des distances inter-clusters via un alignement rigide.
Solution au problème de l'encombrement : La méthode traite le problème de l'encombrement non pas en modifiant le noyau (comme le fait t-SNE avec le noyau de Cauchy) mais en mettant explicitement à l'échelle les distances inter-clusters via le paramètre $\alpha$ , garantissant que les clusters distincts ne se chevauchent pas tout en maintenant leur organisation relative.
Transparence : L'approche est plus interprétable qu'une méthode de bout en bout car la préservation de la structure locale (au sein des clusters) et de la structure globale (entre les clusters) est gérée par des mécanismes séparés et contrôlables.

Résultats expérimentaux

Les auteurs ont évalué C+E sur des jeux de données synthétiques et réels (MNIST, données d'organoïdes cérébraux humains, données de cortex de souris) par rapport à des bases incluant t-SNE, UMAP, PCA, Isomap, PHATE et TriMap.

Jeu de formes synthétiques : C+E a atteint des métriques locales parfaites (récupérant les configurations exactes des clusters) et a maintenu l'orientation globale, tandis que t-SNE et UMAP introduisaient une distorsion locale significative.
MNIST : C+E a réussi à séparer les clusters et à les organiser en groupements significatifs (par exemple, regrouper les chiffres similaires). Alors que t-SNE présentait un rappel kNN supérieur pour de petits $k$ , C+E a surpassé t-SNE et UMAP sur les métriques globales (préservation des classes et des distances inter-clusters).
Données d'organoïdes cérébraux humains : Les plongements C+E ont révélé une trajectoire de développement temporelle claire et des regroupements de types cellulaires distincts. Il a préservé les métriques globales de manière comparable ou supérieure à PCA et L-Isomap, tout en offrant une meilleure structure locale et moins d'effondrement que t-SNE ou UMAP.
Données de cortex de souris : C+E a révélé une structure de grossier à fin (séparant les neurones inhibiteurs/excitateurs et les non-neurones) qui n'était pas présente dans les autres méthodes. Bien que l'échelle de l'embedding ait été gonflée (menant à un stress normalisé plus élevé), les métriques globales invariantes d'échelle ont favorisé C+E par rapport à UMAP et t-SNE.

Signification et affirmations

Le papier affirme que C+E offre une alternative compétitive aux méthodes de visualisation existantes en trouvant un équilibre entre un plongement local fidèle et une organisation globale fidèle.

Gestion du compromis : La méthode reconnaît le compromis inhérent entre la préservation locale et globale mais fournit un mécanisme (le paramètre $\alpha$ ) pour gérer explicitement ce compromis.
Flexibilité : Le cadre permet aux utilisateurs de prioriser des métriques spécifiques (par exemple, le rappel kNN via TriMap ou la préservation des distances via PCA) sans sacrifier l'arrangement global des clusters.
Limites : Les auteurs notent modestement que t-SNE reste l'état de l'art pour maximiser le rappel kNN pour de petits $k$ . Ils suggèrent que le rappel kNN de C+E peut être amélioré en augmentant $\alpha$ ou en créant plus de clusters, bien que cela risque d'introduer de faux clusters. La complexité computationnelle de l'étape d'alignement est quadratique par rapport au nombre de points, bien que des stratégies de sous-échantillonnage soient employées pour l'atténuer.

En conclusion, les auteurs soutiennent que C+E fournit une approche plus transparente et contrôlable pour visualiser des données regroupées, préservant à la fois la géométrie interne des clusters et le positionnement relatif des clusters eux-mêmes, ce qui est souvent perdu dans les techniques populaires de réduction de dimensionnalité non linéaires.