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

A continuación se presenta un resumen técnico detallado del artículo "Agrupamiento K-mediano espacial disperso para datos de alta dimensión" de Zhao, Zhuang y Feng.

1. Planteamiento del Problema

El artículo aborda los desafíos del agrupamiento de datos de alta dimensión ($p \gg n$) caracterizados por dos dificultades específicas:

1. Distribuciones de colas pesadas y valores atípicos: Los métodos clásicos como K-medias se basan en la media aritmética y la pérdida euclidiana al cuadrado, lo que los hace altamente sensibles a valores atípicos y ruido de colas pesadas (por ejemplo, distribuciones $t$ multivariadas).
2. Variables irrelevantes: En configuraciones de alta dimensión, una gran proporción de características a menudo no porta información discriminante de los grupos. Incluir estas variables de "ruido" diluye la señal de agrupamiento, causando degradación del rendimiento incluso en métodos robustos si tratan todas las dimensiones por igual.

Los métodos de agrupamiento disperso existentes (por ejemplo, K-medias dispersas) suelen utilizar contracción continua (regularización L1) para reducir el peso de las características irrelevantes, lo que puede no producir una exclusión explícita de características y puede ser difícil de ajustar en entornos robustos. Además, los métodos robustos estándar (como K-medias) a menudo carecen de equivarianza bajo rotación, fallando en respetar la geometría elíptica subyacente de los grupos.

2. Metodología

Los autores proponen un marco unificado llamado Agrupamiento K-mediano espacial disperso, que integra la estimación robusta de centros con la selección explícita de características. El marco consta de dos algoritmos complementarios:

A. Concepto Central: Mediana Espacial

En lugar de la media aritmética (K-medias) o las medianas coordenada a coordenada (K-medias), el método utiliza la mediana espacial (mediana geométrica) como centro del grupo.

• Definición: La mediana espacial $m$ minimiza la suma de las distancias euclidianas: $m = \arg\min \sum \|x_i - m\|_2$.
• Ventaja: Es equivariante bajo rotación (respeta la geometría multivariada) y robusta frente a colas pesadas porque la función de pérdida crece linealmente en lugar de cuadráticamente.

B. Algoritmo 1: SM–SSCM (Agrupamiento por Mediana Espacial con Matriz de Covarianza de Signo Espacial Común)

Esta variante aborda las escalas heterogéneas y la dependencia de características sin exclusión explícita de características.

• Paso de Asignación: En lugar de la distancia euclidiana estándar, utiliza una métrica tipo Mahalanobis construida a partir de una Matriz de Covarianza de Signo Espacial (SSCM) común.
• Estimación de SSCM: La matriz de dispersión se estima utilizando los signos espaciales ($u_i = r_i / \|r_i\|$) de los residuos, regularizada con un parámetro de cresta para garantizar la invertibilidad.
• Beneficio: Esto adapta la métrica de distancia a la estructura de correlación y escala de los datos, mejorando la precisión de la asignación en alta dimensión.

C. Algoritmo 2: Sparse–SM (Agrupamiento K-mediano Espacial Disperso)

Esta variante aborda el régimen $p \gg n$ con variables irrelevantes introduciendo exclusión de características por umbralización dura.

• Puntuación de Separación: En cada iteración, se calcula una puntuación $s_j$ para cada característica $j$ basada en la dispersión de los centros de grupo a lo largo de esa coordenada: $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$.
• Exclusión Dura: Las características con puntuaciones por debajo de un umbral $\tau$ son completamente excluidas del paso de asignación. Esto crea un conjunto explícito de variables activas ($S(\tau)$) en lugar de reducir los pesos de forma continua.
• Ajuste (Criterio de Brecha): El umbral $\tau$ se selecciona automáticamente utilizando un estadístico de Brecha basado en permutaciones. El algoritmo compara la separación entre grupos observada contra una distribución de referencia generada permutando columnas (destruyendo la estructura de grupos mientras se preservan las distribuciones marginales). Se selecciona el $\tau$ que maximiza la Brecha.

D. Propiedades Teóricas

El artículo establece la consistencia del agrupamiento y la consistencia de la selección de características para los métodos propuestos bajo un modelo elíptico de mezcla con colas sub-Weibull o polinómicas.

• Consistencia: A medida que $n \to \infty$, el algoritmo recupera la partición verdadera y el conjunto verdadero de características informativas con una probabilidad que tiende a 1, siempre que la separación de la señal sea suficientemente fuerte en relación con el nivel de ruido.
• Robustez: Los límites teóricos muestran que la mediana espacial y la métrica SSCM mantienen la estabilidad incluso bajo contaminación de colas pesadas.

3. Contribuciones Clave

1. Marco Robusto: Desarrollo de un marco de agrupamiento basado en particiones utilizando medianas espaciales, que ofrece una robustez superior frente a colas pesadas y valores atípicos en comparación con los métodos basados en medias o medianas coordenada a coordenada.
2. Selección Explícita de Características: Introducción de un mecanismo de umbralización dura que produce conjuntos interpretables y exactos de variables retenidas y excluidas, evitando la ambigüedad de la contracción continua.
3. Ajuste Basado en Datos: Propuesta de un criterio de Brecha basado en permutaciones diseñado específicamente para seleccionar el umbral de dispersión en entornos robustos y de alta dimensión.
4. Garantías Teóricas: Demostración de la consistencia tanto para la partición de agrupamiento como para la recuperación del soporte (selección de características) bajo modelos elípticos generales con colas pesadas.

4. Resultados Experimentales

Los autores evaluaron los métodos frente a K-medias, K-medias, K-medias dispersas y K-medias dispersas utilizando simulaciones y datos reales.

• Estudios de Simulación:
  • Colas Pesadas y Contaminación: Bajo distribuciones $t$ multivariadas y mezclas gaussianas contaminadas, Sparse–SM y SM–SSCM superaron significativamente a las líneas base no robustas. Sparse–SM logró el mayor Índice Rand Ajustado (ARI) en entornos contaminados.
  • Alta Dimensión: A medida que aumentaba la dimensión $p$ (hasta 400), los métodos no dispersos se deterioraron rápidamente. Sparse–SM mantuvo una alta estabilidad y precisión, demostrando la necesidad de la exclusión de características.
  • Tipos de Valores Atípicos: El método mostró una resiliencia particular contra la contaminación a nivel de celda (corrupción de entradas individuales), donde superó consistentemente a los competidores.
• Aplicaciones con Datos Reales:
  • Datos de Proteínas de Ratones: En un conjunto de datos de niveles de expresión de proteínas, los métodos propuestos lograron un ARI más alto y una mayor estabilidad a través de las ejecuciones en comparación con los métodos clásicos.
  • Conjuntos de Datos de Referencia: Probados en 8 conjuntos de datos UCI/KEEL (por ejemplo, Iris, Wine, WDBC). Los métodos propuestos fueron competitivos o superiores, con SM–SSCM destacando en conjuntos de datos con correlaciones complejas y Sparse–SM obteniendo el mejor rendimiento donde la dispersión de características fue beneficiosa.

5. Significado

Este artículo proporciona un avance crítico para el análisis de datos moderno donde los conjuntos de datos son tanto de alta dimensión como propensos a valores atípicos.

• Impacto Práctico: Ofrece un algoritmo iterativo computacionalmente eficiente que no requiere solucionadores de optimización complejos (a diferencia de algunos enfoques de verosimilitud penalizada) pero proporciona una selección rigurosa de características.
• Perspectiva Teórica: Cierra la brecha entre estadística robusta (signos/medianas espaciales) y aprendizaje disperso, demostrando que la umbralización dura puede ser consistente incluso en presencia de ruido de colas pesadas.
• Aplicabilidad: El método es particularmente valioso en campos como la genómica, las finanzas y el análisis de imágenes, donde los datos a menudo exhiben colas pesadas, correlaciones complejas y una alta proporción de variables de ruido.

En resumen, el Agrupamiento K-mediano espacial disperso ofrece una solución robusta, interpretable y teóricamente sólida para el agrupamiento de datos de alta dimensión, manejando eficazmente los desafíos duales de ruido/valores atípicos y características irrelevantes.