Class Angular Distortion Index for Dimensionality Reduction

1. Énoncé du problème

Les techniques de réduction de dimensionnalité (DR) (par exemple, t-SNE, UMAP, PCA) sont essentielles pour visualiser des données de haute dimension. Cependant, une limitation critique dans l'évaluation actuelle de la DR est la représentation trompeuse des relations entre les clusters.

• Le problème central : Bien que de nombreuses méthodes de DR réussissent à séparer les clusters (en les rendant distincts sous forme de « blobs »), elles déforment souvent les relations géométriques globales entre ces clusters. Par exemple, des structures imbriquées, des variétés courbes ou des clusters entrelacés peuvent être aplatis ou réarrangés de manière arbitraire dans la projection.
• Limites des métriques existantes : Les métriques de qualité actuelles échouent à capturer ces distorsions car elles reposent sur des hypothèses erronées :
  • Hypothèse de séparabilité : Des métriques comme le score de silhouette et l'indice de Davies-Bouldin supposent que les clusters sont compacts, globulaires et bien séparés. Elles récompensent les projections qui créent des « blobs » compacts et isolés, même si cela détruit la véritable structure topologique (par exemple, transformer des sphères imbriquées en cercles séparés).
  • Biais des centroïdes : Des métriques comme la fiabilité et la continuité des étiquettes (Label-T&C) reposent sur les centroïdes des clusters. Si les clusters se chevauchent ou sont imbriqués (les centroïdes coïncident), ces métriques échouent à distinguer une projection fidèle d'une projection aléatoire.
  • Point par point vs niveau de cluster : La plupart des métriques évaluent les distances point à point ou par paires, manquant ainsi les relations géométriques d'ordre supérieur entre des groupes de points.

2. Méthodologie : Indice de distorsion angulaire des classes (CADI)

Les auteurs proposent le CADI, une nouvelle métrique conçue pour évaluer la préservation des relations géométriques inter-clusters en utilisant des angles internes.

Concept de base

Au lieu de mesurer les distances entre les centroïdes ou les points individuels, le CADI mesure les angles internes formés par des triplets de points où le point de référence appartient à une classe, et les deux autres points appartiennent à une classe différente.

• Intuition : En observant comment un cluster $C_b$ « apparaît » du point de vue d'un point du cluster $C_a$ (via l'angle $\angle jik$), la métrique capture la forme et l'orientation relative des clusters.
• Différentiabilité : Parce qu'il repose sur la similarité cosinus des angles, le CADI est différentiable, ce qui permet de l'utiliser comme fonction de perte pour l'optimisation.

Définition mathématique

Étant donné un ensemble de données $X$ et une projection $Y$, avec une partition de classes $C$ :
$$\text{CADI}(X, Y, C) = \frac{1}{T} \sum_{i \in C_a, j,k \in C_b, j \neq k} \left( \cos(\theta_X(j,i,k)) - \cos(\theta_Y(j,i,k)) \right)^2$$
Où :

• $i$ est un point de référence dans la classe $C_a$.
• $j, k$ sont des points dans une classe différente $C_b$.
• $\theta$ représente l'angle interne en $i$ formé par les vecteurs vers $j$ et $k$.
• $T$ est le nombre total de triplets échantillonnés.
• Objectif : Minimiser le CADI (plus proche de 0 est mieux).

Implémentation pratique

• Échantillonnage : Le calcul de la somme complète est en $O(n^3)$. Les auteurs démontrent que l'échantillonnage de $k = O(n)$ triplets (spécifiquement $40n$) produit des résultats stables avec une variance négligeable, rendant la métrique évolutive.
• Invariance : Le CADI est invariant par translation, rotation et mise à l'échelle uniforme, car il repose uniquement sur les angles.
• AngleEmbedding : Les auteurs introduisent un nouvel algorithme de DR, AngleEmbedding, qui utilise le CADI comme fonction de perte optimisée via un réseau neuronal paramétrique (réseau feedforward) pour générer des projections qui préservent spécifiquement les relations angulaires inter-classes.

3. Contributions clés

1. Nouvelle métrique (CADI) : Une métrique de qualité au niveau du cluster qui va au-delà des hypothèses de « globalité » et de « séparabilité » des métriques existantes. Elle cible spécifiquement la préservation de structures complexes comme les clusters imbriqués, courbes ou entrelacés.
2. Démonstration des modes de défaillance : Le papier fournit des preuves extensives que les métriques existantes (Silhouette, Label-T&C, etc.) classent souvent les projections aléatoires ou les projections « blobs » plus haut que les projections qui préservent fidèlement une topologie complexe.
3. Algorithme AngleEmbedding : Une technique de DR supervisée novatrice qui optimise le CADI, prouvant que la métrique peut être utilisée efficacement pour piloter la génération de projections de haute fidélité.
4. Évaluation comparative complète : Évaluation sur plus de 20 ensembles de données synthétiques et réels (incluant des sphères imbriquées, des anneaux, des données d'expression génique et des données textuelles) comparant le CADI à 8 autres métriques et 8 algorithmes de DR.

4. Résultats

L'évaluation met en évidence des écarts significatifs entre le CADI et les métriques existantes :

• Données synthétiques (Sphères imbriquées et Anneaux) :
  • Scénario : Les données consistent en 5 sphères imbriquées ou une chaîne d'anneaux enchaînés.
  • Métriques existantes : Le score de silhouette et le Label-T&C classent souvent t-SNE ou UMAP (qui brisent les anneaux en blobs séparés ou dispersent les sphères) comme les meilleurs, ou même classent hautement les projections aléatoires car les centroïdes se chevauchent.
  • CADI : Identifie correctement AngleEmbedding et PCA (qui préservent l'ordre linéaire ou imbriqué) comme les meilleurs, attribuant les pires scores aux méthodes qui détruisent la topologie.
• Données réelles (Foie, USPS, TREC) :
  • Données sur le foie : Les cellules cancéreuses (HCC) présentent une variance plus élevée que les cellules saines. t-SNE crée des blobs de taille égale et séparés, masquant cette variance. Le CADI récompense AngleEmbedding et PCA, qui montrent correctement le cluster HCC comme plus étalé.
  • USPS (Chiffres) : Les tailles des clusters varient considérablement selon le chiffre. t-SNE force des clusters de taille égale. Le CADI récompense les projections où les tailles des clusters reflètent la véritable distribution des données (préservée par AngleEmbedding).
  • Corrélation : Le CADI montre une faible corrélation avec les autres métriques (par exemple, la corrélation de Spearman avec la silhouette est d'environ 0,24), confirmant qu'il mesure un aspect distinct de la qualité de la projection.
• Réglage des hyperparamètres : Le CADI a été utilisé avec succès pour guider la sélection des hyperparamètres de UMAP, identifiant des configurations qui préservent mieux la structure globale même lorsque l'inspection visuelle est ambiguë.

5. Importance et conclusion

• Changement de paradigme : Le papier soutient que pour les tâches impliquant l'analyse des relations entre les clusters (par exemple, comprendre la hiérarchie, l'imbrication ou la topologie globale), les métriques actuelles axées sur la « séparabilité » sont trompeuses. Le CADI offre une alternative nécessaire pour évaluer la fidélité structurelle.
• Sélection d'outils : Les auteurs clarifient les cas d'usage appropriés :
  • Utilisez t-SNE/UMAP si l'objectif est simplement d'identifier le nombre de clusters ou pour une exploration initiale.
  • Utilisez CADI/AngleEmbedding si l'objectif est de comprendre comment les clusters se relaient, leurs positions relatives et leurs formes géométriques.
• Travaux futurs : Les auteurs suggèrent d'étendre AngleEmbedding aux espaces non euclidiens (sphères, hyperboloïdes) et d'approfondir l'analyse théorique de l'agrégation des erreurs angulaires.

En résumé, le CADI comble une lacune critique dans l'évaluation de la réduction de dimensionnalité en quantifiant la distorsion de la géométrie inter-cluster, fournissant un guide plus fiable pour les analystes travaillant avec des structures de données complexes et non globulaires.