Hierarchical topological clustering

Este artículo propone un algoritmo de agrupamiento topológico jerárquico aplicable con cualquier métrica de distancia, capaz de identificar clústeres de formas arbitrarias y valores atípicos en diversos tipos de datos donde otros métodos fallan.

Lo esencial

El "Detective de Formas": Cómo encontrar lo importante en un mar de caos

Imagina que estás en una fiesta enorme y ruidosa. Hay cientos de personas hablando, música a todo volumen y gente moviéndose por todos lados. De repente, quieres identificar dos cosas:

1. Los grupos de amigos: Esas personas que están juntas, riendo y formando un círculo cerrado.
2. Los "personajes especiales": Esa persona que está sola en una esquina, pero que no es un error, sino alguien importante (como un invitado de honor o alguien que está observando algo crucial).

El problema es que, en los datos reales (como en la medicina o la economía), la "fiesta" es un caos total. Los grupos no siempre son círculos perfectos; a veces son líneas largas, curvas o formas extrañas. Los métodos tradicionales de computación suelen fallar porque intentan meter a todo el mundo en "círculos" o "cuadrados" predefinidos. Si un grupo de amigos está formando una fila larga, el método tradicional dirá: "Esto no es un grupo, son personas sueltas".

Aquí es donde entra el nuevo algoritmo de Ana Carpio y Gema Duro: el Clustering Topológico Jerárquico (HTC).

1. La analogía de la "Niebla que se disipa"

Para entender cómo funciona su método, imagina que los datos son puntos en un mapa cubiertos por una niebla espesa.

El algoritmo empieza con la niebla muy densa: cada punto es una isla solitaria. Poco a poco, la niebla empieza a disiparse (esto es lo que los científicos llaman "aumentar el parámetro de filtración"). A medida que la niebla baja, los puntos que están cerca empiezan a "tocarse" y forman puentes.

• Si dos puntos se tocan, forman un pequeño grupo.
• Si esos grupos se tocan entre sí, forman una comunidad.
• Lo mágico: El algoritmo no busca formas geométricas perfectas. No le importa si el grupo parece una estrella, un rizo o una serpiente; si hay un "camino" de puntos que los conecta, el algoritmo dice: "¡Esto es un grupo!".

2. ¿Por qué es mejor que lo que ya existe?

Imagina que intentas agrupar nubes de colores usando solo reglas de "distancia al centro". Si una nube tiene forma de media luna, el método viejo intentará cortarla por la mitad para hacer dos círculos. El método de Carpio y Duro, en cambio, es como un escáner de formas: reconoce la media luna como una sola unidad porque entiende su "topología" (su estructura de conexión).

Además, tiene un superpoder: detecta a los "rebeldes con causa" (outliers).
En estadística, un "outlier" suele ser visto como un error, como un ruido molesto. Pero este algoritmo sabe distinguir entre un error aleatorio y un dato que es "especialmente solitario". Si un punto tarda muchísimo tiempo en unirse al grupo principal a medida que la niebla baja, el algoritmo te dice: "Ojo, este punto es un caso especial, no lo ignores".

3. ¿Para qué sirve esto en la vida real? (Los ejemplos del estudio)

Los autores probaron su "detective de formas" en tres escenarios fascinantes:

• En la lucha contra el cáncer: Analizaron cómo las células cancerosas invaden el tejido sano. El algoritmo pudo ver no solo la frontera principal, sino también "islas" de células cancerosas que se habían desprendido y estaban viajando por el tejido sano. Los métodos viejos no veían esas islas; este método sí.
• En la calidad de las imágenes: Imagina que estás comprimiendo fotos para que pesen menos. El algoritmo puede detectar automáticamente cuándo una foto ha perdido demasiada calidad o cuándo se le ha colado una línea negra que no debería estar ahí, separándolas de las fotos "buenas".
• En la economía mundial: Al mirar el comercio entre España y Europa, el algoritmo pudo identificar rápidamente quiénes son los socios comerciales "gigantes" (los que se mantienen aislados por su enorme volumen) y quiénes son los países con muy poco intercambio, creando un mapa jerárquico de la importancia económica.

En resumen

Este trabajo nos da una nueva "lupa" para mirar los datos. En lugar de obligar a la realidad a encajar en formas simples, este algoritmo se adapta a la forma real de la realidad, permitiéndonos encontrar patrones ocultos y personajes importantes en medio del ruido.

Resumen técnico

1. El Problema

El análisis de agrupamiento (clustering) tradicional busca categorizar objetos según su afinidad, pero enfrenta desafíos críticos ante la presencia de ruido y valores atípicos (outliers). El problema central que aborda este estudio es que muchos algoritmos estándar (como K-means o DBSCAN) tienen limitaciones estructurales:

• K-means: Falla al identificar clústeres no convexos (de formas arbitrarias) porque siempre asigna puntos al centro más cercano.
• DBSCAN: Aunque detecta formas arbitrarias, requiere la elección manual de umbrales de densidad ($\epsilon$ y $M_p$), lo cual es una tarea no trivial y a menudo arbitraria.
• Clustering Jerárquico estándar: Puede ser subóptimo y sensible a la elección de la función de enlace (linkage).
• Limitación de la TDA actual: Muchos métodos de Análisis de Datos Topológicos (TDA) agrupan conjuntos de datos comparando sus diagramas de persistencia, pero no agrupan los elementos individuales de un conjunto basándose en sus características topológicas básicas.

2. Metodología: El Algoritmo HTC

Los autores proponen el Hierarchical Topological Clustering (HTC), un algoritmo basado en la homología persistente (específicamente en la homología de orden cero, $H_0$).

Fundamentos teóricos:

• Filtración de Vietoris-Rips: El algoritmo construye una secuencia anidada de complejos simpliciales. A medida que aumenta un parámetro de distancia ($r$), los puntos se conectan mediante aristas, formando componentes conectados.
• Persistencia: El método utiliza la idea de que las características que "persisten" a través de múltiples escalas de $r$ representan estructuras reales de los datos, mientras que las que desaparecen rápido son ruido.

Proceso del algoritmo:

1. Selección de métrica: Se elige una distancia $d$ (Euclidiana, Wasserstein, Fermat, etc.).
2. Construcción de la jerarquía: Se genera una cuadrícula de valores de filtración desde $r=0$ hasta el diámetro del conjunto de datos.
3. Evolución de componentes: Para cada valor de $r$, se identifican los componentes conectados (clústeres). A medida que $r$ crece, los clústeres se fusionan.
4. Identificación de outliers: Los puntos o grupos que tardan más en fusionarse con el clúster principal se identifican automáticamente como valores atípicos persistentes.

3. Contribuciones Clave

• Flexibilidad de métrica: El algoritmo puede implementarse con cualquier elección de distancia, permitiendo aplicaciones en dominios muy distintos (imágenes, genética, economía).
• Detección automática de outliers: A diferencia de otros métodos, el HTC no requiere parámetros "a ciegas" para distinguir entre ruido y valores atípicos significativos; la jerarquía resultante permite inferir la importancia de estos mediante su persistencia.
• Capacidad de forma arbitraria: Al basarse en la conectividad topológica, puede identificar clústeres de cualquier geometría sin asumir convexidad.
• Complementariedad con el Barcode: El método proporciona información sobre qué elementos pertenecen a cada clúster, algo que el diagrama de persistencia (barcode) por sí solo no hace.

4. Resultados y Aplicaciones

El estudio demuestra la eficacia del HTC en cuatro escenarios distintos:

• Interfaces fragmentadas (Biología): En el estudio de la invasión de células cancerosas en tejido sano, el HTC logró distinguir la interfaz principal y las "islas" de células malignas migrantes. Métodos como K-means y DBSCAN fallaron en capturar esta interpretación geométrica.
• Procesamiento de Imágenes (Control de Calidad): Utilizando la distancia de Wasserstein, el HTC identificó automáticamente imágenes con defectos (líneas extrañas) y con baja resolución (excesiva compresión), separándolas de las imágenes originales y de las comprimidas correctamente.
• Datos Económicos (Comercio Internacional): Aplicado a datos de exportación/importación de España en la UE, el algoritmo identificó de forma natural a los socios comerciales dominantes (como Francia o Alemania) como outliers persistentes, separándolos del resto de países con bajo volumen de comercio.
• Datos Genéticos (Cáncer de Mama): Al analizar la expresión de ARNm, el HTC identificó genes específicos (como CCNE1 o CDKN2A) que permanecen aislados durante más tiempo en la jerarquía, coincidiendo con genes conocidos por su relevancia en la progresión del cáncer.

5. Significancia

La importancia de este trabajo radica en su capacidad para ofrecer una interpretación geométrica y estructural clara de los datos. Mientras que los métodos tradicionales a menudo fuerzan una estructura sobre los datos (como la circularidad de K-means), el HTC permite que la topología de los datos dicte la estructura de los clústeres. Esto lo convierte en una herramienta poderosa para la ciencia de datos donde los valores atípicos no son errores, sino elementos de alto valor informativo (como mutaciones genéticas o anomalías económicas).