Cluster Analysis with Resampling for Validation and Exploration (CARVE)

Résumé Technique : CARVE (Cluster Analysis with Resampling for Validation and Exploration)

Problématique

Le partitionnement de données (clustering) est une technique d'apprentissage non supervisé fondamentale utilisée pour diviser les données en groupes similaires dans divers domaines scientifiques, notamment la génomique, les neurosciences et les sciences sociales. Cependant, les résultats du partitionnement sont notoirement sensibles aux choix méthodologiques, incluant l'algorithme spécifique, les étapes de prétraitement et le nombre de clusters ($k$). De petites variations dans ces choix peuvent conduire à des regroupements qualitativement différents, entraînant des affirmations scientifiques non reproductibles.

La validation de pointe actuelle repose largement sur des indices de validation du partitionnement (CVI) tels que le coefficient de Silhouette, l'indice de Davies–Bouldin et le score de Calinski–Harabasz. Ces indices résument la qualité du partitionnement via des hypothèses géométriques (ex: compacité, formes sphériques et distributions de densité spécifiques). Les auteurs soutiennent que ces hypothèses échouent fréquemment dans la recherche biomédicale, où les données présentent souvent des distributions à queues lourdes, une haute dimensionnalité et des structures non linéaires. Par conséquent, les CVI échouent souvent à identifier des solutions appropriées, menant à un sur-partitionnement ou un sous-partitionnement systématique. De plus, les alternatives existantes basées sur le rééchantillonnage (se concentrant sur la stabilité et la généralisabilité) sont dispersées entre des outils spécialisés et non unifiés, manquant d'un cadre logiciel cohérent pour une comparaison systématique.

Méthodologie

Le document présente CARVE (Cluster Analysis with Resampling for Validation and Exploration), un cadre unifié qui évalue les solutions de partitionnement en se basant sur la stabilité et la généralisabilité plutôt que sur des hypothèses géométriques.

Algorithme Central :
Pour une grille spécifiée par l'utilisateur d'algorithmes de partitionnement et d'hyperparamètres (incluant $k$), CARVE effectue $B$ itérations de rééchantillonnage :

1. Sous-échantillonnage : Deux sous-échantillons indépendants ($P_1, P_2$) de taille $\lfloor \rho n \rfloor$ sont tirés, ainsi qu'un ensemble de test réservé ($P_{test}$).
2. Partitionnement : La méthode de partitionnement candidate $f(\cdot, \theta)$ est appliquée à $P_1$, $P_2$ et $P_{test}$.
3. Métrique de Stabilité ($S^{(b)}$) : L'indice de Rand ajusté (ARI) est calculé entre les partitions de $P_1$ et $P_2$ sur leur intersection. Cela mesure la robustesse du regroupement sous la perturbation des données.
4. Métrique de Généralisabilité ($G^{(b)}$) : Un classificateur (par défaut : Forêt Aléatoire) est entraîné sur $P_1$ en utilisant ses étiquettes de cluster. Le classificateur prédit les étiquettes pour $P_{test}$, et l'ARI entre ces prédictions et le partitionnement réel de $P_{test}$ est calculé. Cela mesure si la structure apprise sur un sous-ensemble est transférable aux données non vues.
5. Agrégation : Les métriques sont agrégées à travers les itérations pour produire des moyennes, des erreurs types et des intervalles de confiance. Une matrice de consensus est également construite à partir des fréquences de co-partitionnement pour dériver des diagnostics au niveau de l'échantillon et du cluster (ex: indice de Gini, entropie croisée, proportion de clusters ambigus).

Règles de Sélection :
Pour sélectionner le $k$ et la méthode optimaux, CARVE emploie trois règles de sélection :

• Règle du Max : Sélectionne le $k$ qui maximise la métrique.
• Règle du 1-SE : Sélectionne le plus grand $k$ dont le score se situe à l'intérieur d'une erreur type de l'écart par rapport au maximum (un principe emprunté à l'apprentissage supervisé).
• Règle des Quantiles : Sélectionne le plus grand $k$ dont le score se situe à l'intérieur des 95 % centraux de la distribution des scores observés au $k$ maximisant.

Diagnostics Multi-niveaux :
CARVE fournit des diagnostics à trois granularités :

• Global : Scores de stabilité et de généralisabilité globaux sur l'ensemble du jeu de données.
• Cluster : Identification des clusters spécifiques qui sont stables ou ambigus.
• Échantillon : Identification des échantillons individuels ayant une appartenance incertaine (échantillons douteux).

Contributions Clés

1. Cadre Unifié : CARVE est le premier package open-source (disponible en Python et R) évaluant conjointement plusieurs algorithmes de partitionnement et hyperparamètres en utilisant à la fois des métriques de stabilité et de généralisabilité au sein d'un flux de travail unique.
2. Validation Agnostique au Modèle : En s'appuyant sur le rééchantillonnage plutôt que sur des hypothèses géométriques, CARVE est robuste aux données non sphériques, à queues lourdes et de haute dimensionnalité courantes en génomique.
3. Sélection Fondée sur des Principes : Le papier propose et valide l'utilisation de la règle du 1-SE appliquée aux métriques de stabilité comme stratégie de sélection par défaut, laquelle surpasse souvent la simple maximisation ou la sélection basée sur les CVI.
4. Implémentation Logicielle : CARVE offre une API Python compatible avec scikit-learn et une interface R compatible avec les flux de travail Seurat et SingleCellExperiment, facilitant l'intégration dans les pipelines existants.

Résultats

Les auteurs ont évalué CARVE sur six benchmarks synthétiques et deux études de cas biomédicales réelles.

Benchmarks Synthétiques :
À travers des mélanges gausiens isotropes, des mélanges $t$ à queues lourdes, des mélanges avec des caractéristiques de nuisance et des variétés non linéaires (Swiss rolls, cercles, lunes), CARVE a systématiquement récupéré des partitionnements proches de l'optimum là où les CVI classiques se dégradaient significativement.

• Dans les contextes à queues lourdes et non linéaires, les CVI (particulièrement le Gap statistic, Calinski–Harabasz et Davies–Bouldin) ont souvent échoué à identifier le vrai $k$ ou ont sélectionné des solutions avec un faible ARI par rapport à la vérité terrain.
• La métrique de stabilité de CARVE avec la règle du 1-SE a été le performeur le plus constant à travers toutes les tâches.

Études de Cas :

1. scRNA-seq par gouttelettes (Klein et al.) : CARVE a identifié une solution à 4 clusters correspondant à quatre stades de différenciation distincts de cellules souches embryonnaires de souris. En revanche, les CVI (Silhouette, CH, DB) ont sélectionné une solution à 2 clusters qui effondre les stades biologiques distincts, manquant la progression transcriptionnelle continue.
2. Cytométrie de masse (Levine et al.) : CARVE a sélectionné une solution à 10 clusters qui a récupéré des structures de populations de la moelle osseuse très fines (séparant les cellules T CD4+, T CD8+ et NK). Les CVI ont sélectionné une solution à 7 clusters qui fusionne ces populations distinctes. La solution sélectionnée par CARVE a atteint un ARI significativement plus élevé par rapport aux étiquettes manuelles rapportées comparativement à toutes les solutions sélectionnées par les CVI.

Signification et Revendications

Le papier affirme que CARVE comble une lacune critique dans la reproductibilité de l'apprentissage non supervisé. En s'éloignant des hypothèses géométriques pour se tourner vers la stabilité et la généralisabilité par rééchantillonnage, CARVE fournit une base plus fiable pour la découverte scientifique dans les données biomédicales complexes.

Les auteurs soulignent que si la stabilité est une condition nécessaire pour des découvertes fondées sur les données dignes de confiance, elle n'est pas suffisante en soi ; la généralisabilité est requise pour garantir que les informations s'étendent au-delà de l'échantillon spécifique. Les diagnostics multi-niveaux de CARVE permettent non seulement de sélectionner un modèle, mais aussi d'identifier quels clusters ou échantillons spécifiques sont robustes et lesquels sont douteux, empêissant ainsi l'interprétation erronée d'artefacts comme étant des signaux biologiques. Le papier conclut que CARVE offre une voie pratique pour améliorer la confiance et la réplicabilité des résultats de partitionnement en biologie computationnelle et au-delà.