Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

Resumen Técnico: Agrupamiento de Centros Locales Basado en Profundidad (DLCC)

Declaración del Problema
El análisis de agrupamiento (clustering) es fundamental para la ciencia de datos, sin embargo, los métodos existentes a menudo luchan con la diversidad de las distribuciones de datos del mundo real. Los enfoques tradicionales generalmente se dividen en dos categorías, cada una con limitaciones específicas:

• Métodos basados en centros (p. ej., k-means) asumen un único punto representativo por grupo y formas esféricas, lo que los hace sensibles a los valores atípicos (outliers) y a la inicialización, además de fallar al modelar geometrías no convexas.
• Métodos basados en densidad (p. ej., DBSCAN, Mean Shift) manejan formas arbitrarias pero dependen de la estimación de la densidad o de umbrales fijos, lo que puede resultar inestable en espacios de alta dimensión o cuando los grupos tienen densidades variables.
• Los métodos basados en grafos a menudo enfrentan prohibiciones computacionales en datos a gran escala o permanecen sensibles a la elección de la métrica de distancia.

Una limitación central en todos estos paradigmas es la definición de "exemplares" (puntos representativos). La mayoría de los métodos vinculan los ejemplares a criterios de distancia o densidad que pueden no generalizarse a través de diferentes dimensionalidades y geometrías. Además, aunque la profundidad estadística de los datos ofrece un orden robusto de centro hacia afuera de los datos multivariantes, históricamente se ha utilizado solo como una herramienta auxiliar (por ejemplo, para la inicialización) en lugar de como el mecanismo principal para identificar la estructura local y la multimodalidad. Las funciones de profundidad estándar también fallan al capturar directamente las características multimodales.

Metodología: El Marco DLCC
El artículo propone el Agrupamiento de Centros Locales Basado en Profundidad (DLCC), un marco que aprovecha la profundidad de los datos estadísticos para definir centros locales y construir medidas de similitud sin depender de métricas de distancia globales o estimaciones de densidad.

1. Matriz de Similitud Basada en la Profundidad:
   En lugar de utilizar la distancia euclidiana, DLCC construye una matriz de similitud $S$ basada en la Profundidad Espacial (SD). Para localizar el concepto de profundidad, el método define un conjunto de datos reflejado $X_{Ri}$ para cada observación $x_i$, que consiste en la muestra original $X$ y la reflexión de todos los puntos a través de $x_i$. Dado que $x_i$ es el centro de simetría para $X_{Ri}$, su profundidad es máxima (1). La profundidad de cualquier otro punto $x_j$ relativo a $X_{Ri}$, denotada como $D(x_j | X_{Ri})$, sirve como una medida de similitud entre $x_j$ y $x_i$.

   • Eficiencia: Los autores introducen una implementación basada en matrices para calcular estas profundidades de manera eficiente, reduciendo los cálculos redundantes mediante la precomputación de sumas de vectores unitarios y normas, aunque la complejidad teórica sigue siendo $O(n^3)$.

2. Identificación de Centros Locales:
   Para cada punto $x_i$, se define un vecindario $N_i$ de tamaño $s$ mediante sus $s-1$ vecinos más cercanos basados en la similitud de profundidad. Dentro de cada vecindario, se identifica el punto con el rango local más alto (el punto más profundo) como un centro local.

   • Filtrado: No todos los centros locales son útiles. El método filtra los candidatos basándose en dos criterios: (1) el centro debe ser central dentro de su vecindario (rango $\le 2$), y (2) debe aparecer con frecuencia en diferentes vecindarios (frecuencia $f > 1$). Se utiliza un criterio de estabilidad, la Profundidad Promedio Inducida por Vecindarios (AND), para seleccionar centros robustos adicionales.

3. Estrategias de Agrupación:
   Los centros locales filtrados se agrupan en clústeres utilizando dos estrategias distintas para manejar diferentes geometrías de datos:

   • Estrategia Min: Agrupa los centros de forma conservadora basándose en el solapamiento mutuo de los vecindarios. Esto es adecuado para clústeres convexos equilibrados, bien separados o superpuestos.
   • Estrategia Max: Agrupa los centros mediante cadenas de conectividad donde la similitud del vecindario supera un umbral $\delta$. Esta estrategia está diseñada para estructuras no convexas y tamaños de clúster altamente desequilibrados. Incluye un mecanismo para segregar regiones "en todas partes no convexas" (p. ej., espirales) mediante la identificación de centros locales aislados.

4. Formación de Clústeres y Clasificación:
   Una vez que los grupos de centros locales se forman, se crean clústeres temporales utilizando los vecinos únicos de cada grupo. Los puntos se asignan puntuaciones basadas en su similitud con los centros del grupo frente a otros grupos. Los puntos ambiguos o no asignados se clasifican entonces utilizando clasificadores integrados (k-Nearest Neighbors o Random Forests) entrenados con las etiquetas de los clústeres temporales, asegurando una asignación robusta sin necesidad de ajustes adicionales de hiperparámetros.

Contribuciones Clave

• Marco Novedoso: DLCC es el primer método que coloca la profundidad de los datos en el núcleo tanto de la identificación de ejemplares como de la construcción de la similitud, abordando directamente la multimodalidad.
• Computación Eficiente: El artículo desarrolla una implementación basada en matrices para construir matrices de similitud de profundidad bajo la profundidad espacial, acelerando significativamente el cálculo en comparación con las implementaciones ingenuas.
• Agrupación Flexible: El enfoque de doble estrategia (Min/Max) permite que el marco se adapte a diferentes formas de clúster (convexos vs. no convexos) y distribuciones de densidad.
• Evaluación Exhaustiva: Los autores proporcionan un procedimiento completo de extremo a extremo, incluyendo directrices para la selección de parámetros (usando el índice CVDD y visualización) y evaluaciones empíricas extensas.

Resultados Experimentales
Los autores evaluaron DLCC en 12 conjuntos de datos sintéticos y 13 referencias del mundo real (incluyendo datos de imágenes de alta dimensión y microarrays).

• Desempeño: DLCC logró una recuperación perfecta en 7 conjuntos de datos sintéticos y se posicionó consistentemente en los tres primeros lugares en todas las referencias del mundo real. Demostró un desempeño superior en el manejo de formas no convexas, densidades variables y desequilibrio de clases en comparación con competidores como LW-k-means, EKM, R-MDPC y ACLR.
• Limitaciones Observadas: El método tuvo dificultades con estructuras "tipo variedad" (manifold-like) donde los vecindarios locales son inherentemente no convexos (p. ej., el conjunto de datos "Atom" y las estructuras de espiral en "Blend"). En estos casos, la suposición de que los centros locales residen en vecindarios aproximadamente convexos falló.
• Escalabilidad: Aunque es efectivo para conjuntos de datos de hasta $\sim 10^4$ observaciones, la complejidad $O(n^3)$ de la construcción de la matriz de similitud sigue siendo un cuello de botella para datos de escala muy grande.

Significado y Reivindicaciones
El artículo afirma que DLCC ofrece una alternativa flexible a los métodos de agrupamiento tradicionales al superar las suposiciones rígidas de los métodos basados en centros y la inestabilidad de los métodos basados en densidad en altas dimensiones. Al utilizar la profundidad de los datos para definir la geometría local, DLCC mejora las capacidades de análisis de datos en una amplia gama de escenarios sin requerir un número predefinido de clústeres o suposiciones distributivas estrictas. Los autores posicionan a DLCC como una herramienta robusta para el análisis exploratorio de datos, particularmente donde las formas de los clústeres son complejas o desconocidas, reconociendo al mismo tiempo que se necesita trabajo futuro para mejorar la escalabilidad y automatizar la selección de parámetros.