Extending TCLUST to higher dimensions

Resumen Técnico: Extensión de TCLUST a Dimensiones Superiores mediante tHDDC

Planteamiento del Problema
Los valores atípicos (outliers) distorsionan significativamente los resultados de los métodos de agrupamiento estándar, lo que a menudo conduce a particiones poco fiables donde se fusionan clusters significativos o se detectan clusters espurios. Aunque se han desarrollado técnicas de agrupamiento robustas basadas en el recorte (trimming), como TCLUST (Clustering Recortado), estas enfrentan limitaciones severas en entornos de alta dimensionalidad. A medida que la dimensionalidad $p$ aumenta, TCLUST tiene dificultades debido a dos factores principales: la complejidad computacional de estimar un gran número de parámetros asociados con estructuras de covarianza completas, y la dificultad de inicializar el algoritmo de manera efectiva. Por el contrario, enfoques alternativos como el Agrupamiento Lineal Robusto (RLG), que asumen que los clusters se encuentran cerca de subespacios de menor dimensión, ofrecen una reducción de la dimensionalidad pero sufren de supuestos simplificadores, tales como errores ortogonales isotrópicos y dificultades para manejar subespacios que se intersectan.

Metodología: El Enfoque tHDDC
Para abordar estas limitaciones, los autores proponen tHDDC (Clustering de Datos de Alta Dimensionalidad Recortado), un método que unifica la robustez de TCLUST con el modelado de subespacios de HDDC (Clustering de Datos de Alta Dimensionalidad).

• Marco del Modelo: tHDDC asume que los datos surgen de una mezcla de $G$ componentes gaussianos. A diferencia de TCLUST, que estima matrices de covarianza completas, tHDDC adopta una estructura parsimoniosa donde cada cluster $g$ está concentrado alrededor de un subespacio afín $B_g$ de dimensión intrínseca $q_g$ (donde $q_g < p$).
• Estructura de Covarianza: La matriz de dispersión $\Sigma_g$ para cada cluster se descompone en un subespacio específico $B_g$ (generado por los $q_g$ autovectores correspondientes a los autovalores más grandes $\lambda_{g1}, \dots, \lambda_{gq_g}$) y un complemento ortogonal $B_g^\perp$. En $B_g^\perp$, la varianza es modelada por un único parámetro común $\lambda_g$. Esto reduce significativamente el número de parámetros en comparación con la estimación de la covarianza completa.
• Recorte y Restricciones: El método incorpora un nivel de recorte $\alpha$ para excluir las observaciones más atípicas. Para asegurar la consistencia matemática y prevenir soluciones degeneradas, se imponen dos restricciones de la razón de autovalores:
  1. Una restricción $c_1$ sobre la razón de los autovalores más grandes dentro de los subespacios.
  2. Una restricción $c_2$ sobre la razón de los autovalores más pequeños (la varianza de ruido común $\lambda_g$) a través de los clusters.
• Algoritmo: Los autores presentan un algoritmo factible basado en "pasos de concentración" (C-steps), una adaptación del algoritmo EM. El procedimiento involucra:
  1. Inicialización Aleatoria: Selección de pequeños subconjuntos de observaciones para inicializar los parámetros del subespacio.
  2. Pasos C (C-steps): Actualización iterativa de los pesos de membresía (recortando las observaciones de menor verosimilitud), actualización de las medias de los clusters y actualización de los parámetros del subespacio.
  3. Truncamiento de Autovalores: Se introduce un procedimiento específico para aplicar las restricciones de autovalores ($c_1, c_2$) después de cada actualización, extendiendo los métodos de truncamiento utilizados en TCLUST.
  4. Estimación de la Dimensión Intrínseca: Se integra un procedimiento basado en el criterio de Cattell para estimar automáticamente las dimensiones intrínsecas $q_g$, utilizando una penalización por complejidad para evitar el sobreajuste.

Contribuciones Clave

1. Extensión Teórica: El artículo establece la existencia y consistencia de los estimadores de tHDDC bajo condiciones moderadas, demostrando que el maximizador de la población existe incluso para distribuciones de cola pesada, siempre que se utilice un nivel de recorte estrictamente positivo.
2. Innovación Algorítmica: Se desarrolla un nuevo algoritmo de pasos C que maneja la parametrización parsimoniosa específica de HDDC mientras integra el recorte robusto y las restricciones de autovalores de TCLUST. Esto incluye un novedoso mecanismo de truncamiento de autovalores para satisfacer las restricciones duales ($c_1, c_2$).
3. Selección Automática de Dimensión: Los autores proponen un método para determinar automáticamente las dimensiones intrínsecas $q_g$ de los subespacios, reduciendo la necesidad de especificación manual y mitigando el riesgo de sobreajuste mediante un criterio de verosimilitud penalizado por complejidad.
4. Herramientas de Diagnóstico: El artículo introduce herramientas de diagnóstico gráfico, incluyendo distancias de puntuación (score distances) y distancias ortogonales, para evaluar la adecuación de los clusters y detectar anomalías, así como "factores discriminantes" para evaluar la fiabilidad de las asignaciones de clusters y las decisiones de recorte.

Resultados

• Estudio de Simulación: Experimentos con datos sintéticos en 200 dimensiones ($p=200$) con grados variables de solapamiento de clusters y orientación de subespacios muestran que tHDDC logra una precisión de clasificación casi perfecta en todos los escenarios. En contraste, TCLUST se desempeña pobremente en altas dimensiones, y RLG falla cuando los subespacios se intersectan. Además, tHDDC es aproximadamente de 2.5 a 3 veces más rápido computacionalmente que TCLUST bajo condiciones comparables.
• Aplicación a Datos Reales: El método se aplicó a un conjunto de datos de dígitos escritos a mano (USPS358) contaminados con outliers artificiales y reales. tHDDC logró un error de clasificación de aproximadamente el 7% (en datos no recortados), superando significativamente a TCLUST (error > 38%) y al HDDC no robusto (error > 39%). El análisis identificó y eliminó con éxito los outliers artificiales mientras preservaba la estructura de los clusters de dígitos.

Significancia y Reivindicaciones
El artículo afirma que tHDDC proporciona una solución robusta y computacionalmente eficiente para el agrupamiento en entornos de dimensionalidad moderadamente alta donde los métodos tradicionales como TCLUST fallan debido a la explosión de parámetros y la sensibilidad de la inicialización. Al combinar los supuestos de subespacio de HDDC con el recorte robusto de TCLUST, el método ofrece una alternativa menos simplista a RLG, capaz de manejar subespacios que se intersectan y errores no isotrópicos. Los autores enfatizan que la metodología es particularmente valiosa para conjuntos de datos con estructuras de clusters desconocidas y contaminación, ofreciendo tanto una mejor precisión como un costo computacional reducido en comparación con las técnicas existentes de agrupamiento robusto en alta dimensionalidad. Se señala que el trabajo futuro incluirá extensiones de datos funcionales y estrategias de recorte por celda (cellwise).