📊 statistics

Sparse $K$ -spatial-median clustering for high-dimensional data

Cet article propose un cadre de regroupement robuste pour les données de haute dimension présentant des queues lourdes et des variables non pertinentes, qui remplace les mises à jour de moyennes du K-means par des médianes spatiales, intègre une métrique d'affectation flexible et utilise un mécanisme automatisé d'exclusion rigide des caractéristiques afin d'atteindre une précision et une stabilité supérieures.

Auteurs originaux : Ping Zhao, Dan Zhuang, Long Feng

Publié 2026-05-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ping Zhao, Dan Zhuang, Long Feng

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 essayez d'organiser une bibliothèque massive et chaotique où les livres sont dispersés sur des milliers d'étagères. Certaines étagères sont remplies de livres qui appartiennent réellement ensemble (les « clusters »), mais la plupart des étagères ne sont que remplies de bruit aléatoire, de vieux reçus ou de pages blanches (les « variables non pertinentes »). De plus, la bibliothèque est un peu désordonnée : certains livres sont lourds et à queue lourde (comme des encyclopédies qui pourraient écraser une balance), et d'autres sont simplement des valeurs aberrantes jetées par accident.

C'est le problème que les auteurs, Ping Zhao, Dan Zhuang et Long Feng, tentent de résoudre. Ils ont créé une nouvelle méthode de regroupement de données appelée regroupement K-spatial-médiane parcimonieux.

Voici comment leur méthode fonctionne, décomposée en concepts et analogies simples :

1. Le problème de l'ancienne méthode (K-Means)

La façon la plus courante de regrouper des choses s'appelle K-means. Imaginez K-means comme un bibliothécaire qui tente de trouver le livre « moyen » sur une étagère pour représenter ce groupe.

Le défaut : Si un livre est une encyclopédie géante et lourde (une valeur aberrante) ou si l'étagère est remplie de déchets aléatoires (variables non pertinentes), la « moyenne » est entraînée hors de sa trajectoire. Le bibliothécaire finit par regrouper les choses incorrectement parce que le bruit noie le signal.
Le piège de la haute dimension : Dans les données modernes, vous pourriez avoir 1 000 caractéristiques (étagères) mais seulement 100 livres (points de données). Si 900 de ces étagères ne sont que du bruit, K-means devient complètement confus, tentant de trouver des modèles dans la statique.

2. Le nouveau centre : la « médiane spatiale »

Au lieu de trouver la « moyenne » (qui est facilement influencée par des valeurs aberrantes lourdes), les auteurs utilisent une médiane spatiale.

L'analogie : Imaginez un groupe de personnes debout dans un champ. La position « moyenne » est le centre de gravité mathématique. Si une personne géante entre en courant et se tient loin, le centre de gravité se déplace vers elle.
La médiane spatiale : C'est l'endroit où, si vous vous teniez là, la distance totale vers tout le monde serait la plus petite. C'est comme trouver le « cœur » du groupe. Même si quelques fous aberrants courent partout, le cœur du groupe reste en place. Cela rend la méthode robuste (résistante) aux queues lourdes et aux données désordonnées.

3. La partie « parcimonieuse » : ignorer le bruit

Les auteurs ont réalisé que même un « chercheur de cœur » résistant se confond si on lui demande d'écouter 1 000 voix différentes, dont 900 ne sont que de la statique.

La solution : Ils ont introduit une règle de seuillage dur (Hard-Thresholding).
L'analogie : Imaginez que le bibliothécaire demande à chaque étagère : « Es-tu importante pour trier ces livres ? » Si la contribution d'une étagère est faible (en dessous d'un certain score), le bibliothécaire dit : « Non, tu es du bruit », et ignore complètement cette étagère pour le reste du processus de tri.
Pourquoi « dur » ? Contrairement à d'autres méthodes qui « baissent simplement le volume » sur les mauvaises étagères (réduction continue), cette méthode coupe le volume complètement. C'est un interrupteur binaire : Marche ou Arrêt. Cela donne une liste claire des caractéristiques qui comptent réellement.

4. La métrique « intelligente » : voir la forme

Parfois, les groupes ne sont pas des cercles parfaits ; ils sont étirés comme des ovales (ellipses) parce que les variables sont connectées.

L'innovation : Les auteurs ont créé une règle spéciale (une métrique de Covariance de signe spatial) qui étire ou écrase l'espace pour correspondre à la forme des données.
L'analogie : Si vous essayez de trier des personnes par taille et poids, et que ces deux choses sont liées, une règle standard pourrait manquer le modèle. Cette nouvelle règle s'ajuste elle-même à la « forme » du groupe, garantissant que la distance est mesurée correctement même si les données sont étirées ou corrélées.

5. Le régleur automatique : la statistique « Gap »

Comment savoir combien d'étagères ignorer ? Si vous en ignorez trop, vous perdez le signal. Trop peu, et vous gardez le bruit.

La solution : Ils utilisent un Critère d'écart basé sur les permutations (Permutation-based Gap Criterion).
L'analogie : Imaginez que vous essayez de trouver un modèle dans une foule. Pour savoir si le modèle est réel, vous mélangez la foule au hasard (permutation) afin que personne ne se tienne à côté de ses amis. Vous comparez l'« ordre » de la vraie foule au « chaos » de la foule mélangée. Le point où la vraie foule semble significativement plus organisée que la foule mélangée est votre « Écart ». Cela indique à l'ordinateur exactement où tracer la ligne entre « signal » et « bruit » sans qu'un humain ait besoin de deviner.

Que ont-ils découvert ?

Les auteurs ont testé cette méthode de deux manières :

Simulations : Ils ont créé de fausses données avec des queues lourdes (valeurs aberrantes désordonnées) et beaucoup de bruit. Leur méthode a constamment trouvé les bons groupes mieux que l'ancien K-means ou d'autres méthodes « parcimonieuses », surtout lorsque les données étaient sales ou que les dimensions étaient énormes.
Données réelles : Ils l'ont essayée sur un ensemble de données concernant les protéines de souris (distinguant les souris témoins des souris avec le syndrome de Down) et plusieurs ensembles de données de référence standard.
- Résultat : Leur méthode était souvent la plus précise et la plus stable. Elle a mieux géré la nature désordonnée et de haute dimension des données protéiques que les classiques.

En résumé

L'article propose une façon plus résistante et plus intelligente de regrouper les données.

Il utilise un centre robuste (Médiane spatiale) qui ne panique pas lorsque des valeurs aberrantes apparaissent.
Il utilise une règle intelligente qui s'adapte à la forme des données.
Il utilise un filtre strict (Seuillage dur) pour jeter complètement les variables non pertinentes, plutôt que de simplement les atténuer.
Il utilise un juge automatique (Statistique Gap) pour décider exactement combien de bruit jeter.

Le résultat est un outil de regroupement qui fonctionne bien même lorsque les données sont de haute dimension, désordonnées et pleines d'informations non pertinentes.

1. Énoncé du problème

L'article aborde les défis du clustering de données de haute dimension ( $p \gg n$ ) caractérisées par deux difficultés spécifiques :

Distributions à queues lourdes et valeurs aberrantes : Les méthodes classiques comme K-means reposent sur la moyenne arithmétique et la perte euclidienne quadratique, ce qui les rend très sensibles aux valeurs aberrantes et au bruit à queues lourdes (par exemple, les distributions $t$ multivariées).
Variables non pertinentes : Dans des contextes de haute dimension, une grande proportion de caractéristiques ne porte souvent aucune information discriminante pour les clusters. L'inclusion de ces variables « bruit » dilue le signal de clustering, entraînant une dégradation des performances même pour des méthodes robustes si elles traitent toutes les dimensions de manière égale.

Les méthodes de clustering parcimonieux existantes (par exemple, Sparse K-means) utilisent souvent un rétrécissement continu (régularisation L1) pour réduire le poids des caractéristiques non pertinentes, ce qui peut ne pas aboutir à une exclusion explicite des caractéristiques et peut être difficile à régler dans des contextes robustes. De plus, les méthodes robustes standard (comme K-medians) manquent souvent d'équivariance par rotation, ne respectant pas la géométrie elliptique sous-jacente des clusters.

2. Méthodologie

Les auteurs proposent un cadre unifié appelé Sparse K-spatial-median clustering, qui intègre une estimation robuste des centres avec une sélection explicite de caractéristiques. Le cadre comprend deux algorithmes complémentaires :

A. Concept de base : Médiane spatiale

Au lieu de la moyenne arithmétique (K-means) ou des médianes coordonnées (K-medians), la méthode utilise la médiane spatiale (médiane géométrique) comme centre de cluster.

Définition : La médiane spatiale $m$ minimise la somme des distances euclidiennes : $m = \arg\min \sum \|x_i - m\|_2$ .
Avantage : Elle est équivariante par rotation (respecte la géométrie multivariée) et robuste aux queues lourdes car la fonction de perte croît linéairement plutôt que quadratiquement.

B. Algorithme 1 : SM–SSCM (Clustering par médiane spatiale avec matrice de covariance commune des signes spatiaux)

Cette variante adresse les échelles hétérogènes et la dépendance des caractéristiques sans exclusion explicite de caractéristiques.

Étape d'affectation : Au lieu de la distance euclidienne standard, elle utilise une métrique de type Mahalanobis construite à partir d'une matrice de covariance commune des signes spatiaux (SSCM).
Estimation SSCM : La matrice de dispersion est estimée à l'aide des signes spatiaux ( $u_i = r_i / \|r_i\|$ ) des résidus, régularisée par un paramètre de ridge pour assurer l'inversibilité.
Bénéfice : Cela adapte la métrique de distance à la structure de corrélation et à l'échelle des données, améliorant la précision de l'affectation en haute dimension.

C. Algorithme 2 : Sparse–SM (Clustering parcimonieux par médiane spatiale)

Cette variante adresse le régime $p \gg n$ avec des variables non pertinentes en introduisant une exclusion de caractéristiques par seuillage dur.

Score de séparation : À chaque itération, un score $s_j$ est calculé pour chaque caractéristique $j$ basé sur la dispersion des centres de cluster le long de cette coordonnée : $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$ .
Exclusion dure : Les caractéristiques dont les scores sont inférieurs à un seuil $\tau$ sont complètement exclues de l'étape d'affectation. Cela crée un ensemble explicite de variables actives ( $S(\tau)$ ) plutôt que de réduire continûment les poids.
Réglage (Critère Gap) : Le seuil $\tau$ est sélectionné automatiquement à l'aide d'une statistique Gap basée sur des permutations. L'algorithme compare la séparation inter-clusters observée à une distribution de référence générée en permutant les colonnes (détruisant la structure des clusters tout en préservant les distributions marginales). Le $\tau$ maximisant le Gap est sélectionné.

D. Propriétés théoriques

L'article établit la consistance du clustering et la consistance de la sélection de caractéristiques pour les méthodes proposées sous un modèle de mélange elliptique avec des queues sous-Weibull ou polynomiales.

Consistance : Lorsque $n \to \infty$ , l'algorithme récupère la partition vraie et l'ensemble vrai de caractéristiques informatives avec une probabilité tendant vers 1, à condition que la séparation du signal soit suffisamment forte par rapport au niveau de bruit.
Robustesse : Les bornes théoriques montrent que la médiane spatiale et la métrique SSCM maintiennent la stabilité même sous contamination à queues lourdes.

3. Contributions clés

Cadre robuste : Développement d'un cadre de clustering basé sur la partition utilisant des médianes spatiales, offrant une robustesse supérieure aux queues lourdes et aux valeurs aberrantes par rapport aux méthodes basées sur la moyenne ou les médianes coordonnées.
Sélection explicite de caractéristiques : Introduction d'un mécanisme de seuillage dur qui produit des ensembles interprétables et exacts de variables conservées et exclues, évitant l'ambiguïté du rétrécissement continu.
Réglage piloté par les données : Proposition d'un critère Gap basé sur des permutations spécifiquement conçu pour sélectionner le seuil de parcimonie dans des contextes robustes et de haute dimension.
Garanties théoriques : Preuve de consistance pour la partition de clustering et la récupération du support (sélection de caractéristiques) sous des modèles elliptiques généraux à queues lourdes.

4. Résultats expérimentaux

Les auteurs ont évalué les méthodes par rapport à K-means, K-medians, Sparse K-means et Sparse K-medians en utilisant des simulations et des données réelles.

Études de simulation :
- Queues lourdes et contamination : Sous des distributions $t$ multivariées et des mélanges gaussiens contaminés, Sparse–SM et SM–SSCM ont nettement surpassé les références non robustes. Sparse–SM a obtenu le plus haut indice de Rand ajusté (ARI) dans des contextes contaminés.
- Haute dimension : À mesure que la dimension $p$ augmentait (jusqu'à 400), les méthodes non parcimonieuses se sont rapidement détériorées. Sparse–SM a maintenu une stabilité et une précision élevées, démontrant la nécessité de l'exclusion de caractéristiques.
- Types de valeurs aberrantes : La méthode a montré une résilience particulière contre la contamination cellulaire (corruption d'entrées individuelles), où elle a constamment surpassé ses concurrents.
Applications sur données réelles :
- Données de protéines de souris : Sur un ensemble de données de niveaux d'expression de protéines, les méthodes proposées ont atteint un ARI plus élevé et une plus grande stabilité au cours des exécutions par rapport aux méthodes classiques.
- Ensembles de données de référence : Testé sur 8 ensembles de données UCI/KEEL (par exemple, Iris, Wine, WDBC). Les méthodes proposées étaient compétitives ou supérieures, SM–SSCM excellant dans les ensembles de données avec des corrélations complexes et Sparse–SM performant le mieux là où la parcimonie des caractéristiques était bénéfique.

5. Importance

Cet article apporte une avancée critique pour l'analyse de données moderne où les ensembles de données sont à la fois de haute dimension et sujets aux valeurs aberrantes.

Impact pratique : Il offre un algorithme itératif efficace sur le plan computationnel qui ne nécessite pas de solveurs d'optimisation complexes (contrairement à certaines approches de vraisemblance pénalisée) mais fournit une sélection de caractéristiques rigoureuse.
Perspective théorique : Il comble le fossé entre les statistiques robustes (signes/médianes spatiales) et l'apprentissage parcimonieux, prouvant que le seuillage dur peut être consistant même en présence de bruit à queues lourdes.
Applicabilité : La méthode est particulièrement précieuse dans des domaines tels que la génomique, la finance et l'analyse d'images, où les données présentent souvent des queues lourdes, des corrélations complexes et un ratio élevé de variables de bruit.

En résumé, le Sparse K-spatial-median clustering offre une solution robuste, interprétable et théoriquement fondée pour le clustering de données de haute dimension, gérant efficacement les défis doubles du bruit/valeurs aberrantes et des caractéristiques non pertinentes.