🤖 machine learning

Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

Este artículo demuestra que, a diferencia del agrupamiento plano que está limitado por el Teorema de Imposibilidad de Kleinberg, el agrupamiento jerárquico puede satisfacer simultáneamente los axiomas de riqueza, consistencia e invariancia de escala a través de la existencia de incontablemente muchos métodos admisibles que comparten un esqueleto estructural común a pesar de su diversidad.

Autores originales: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Publicado 2026-09-11

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo de la ciencia de datos, existe una tarea fundamental llamada agrupamiento (clustering). Imagine que tiene una colección de artículos —quizás una mezcla de frutas, un grupo de personas o un conjunto de documentos— y quiere clasificarlos en grupos significativos basados en qué tan similares son entre sí. Usted no tiene una etiqueta que le diga qué manzana es cuál; solo tiene una medida de qué tan diferente es cada artículo de todos los demás. El objetivo es dejar que los datos hablen por sí mismos y revelen su estructura oculta. Durante décadas, los investigadores han intentado definir la forma perfecta de hacer este ordenamiento. Han propuesto un conjunto de reglas básicas que cualquier buen método de clasificación debería seguir. Una regla es que el método no debe importar las unidades de medida; ya sea que mida la distancia en metros o en millas, los grupos deben permanecer iguales. Otra regla es que el método debe ser lo suficientemente flexible como para encontrar cualquier agrupación posible si los datos son adecuados para ello. Una tercera regla es que, si usted hace que los elementos dentro de un grupo sean más similares entre sí y hace que los elementos entre grupos sean más diferentes, el método no debería decidir repentinamente separar ese grupo.

Durante mucho tiempo, se creyó que ningún método único podía satisfacer estas tres reglas al mismo tiempo. Un famoso resultado en el campo demostró que, si se le obliga a dividir sus datos en una sola capa plana de grupos —como clasificar una baraja de cartas en un solo montón de palos—, inevitablemente tendrá que romper una de las reglas. Podría tener que ignorar la escala de los datos, o podría tener que ignorar ciertas agrupaciones válidas, o podría tener que ser inestable cuando los datos cambian ligeramente. Esto creó una sensación de limitación, como si la naturaleza misma de clasificar datos en grupos planos fuera defectuosa. Pero, ¿y si la solución no fuera forzar los datos en una sola capa, sino dejar que se desplieguen en un árbol? ¿Qué pasaría si, en lugar de solo decir "estos son los grupos", pudiera decir "estos son los grupos, y dentro de esos grupos, hay grupos más pequeños, y dentro de esos, otros aún más pequeños"? Esta es la idea del agrupamiento jerárquico, donde el resultado es una estructura anidada en lugar de una lista plana.

Un equipo de investigadores de la École Polytechnique Fédérale de Lausanne y la Université Gustave Eiffel ha demostrado ahora que este enfoque jerárquico lo cambia todo. Tomaron las tres reglas estrictas que hacían imposible el agrupamiento plano y preguntaron si estas podrían satisfacerse si el resultado fuera una jerarquía. La respuesta es un sí definitivo. Demostraron que no hay solo una forma de hacer esto, sino un número incontablemente grande de métodos que pueden satisfacer las tres reglas simultáneamente. De hecho, descubrieron que el espacio de estos métodos válidos es increíblemente vasto y diverso. Es tan grande que ni siquiera puede enumerarlos todos, y dentro de esta vasta colección, existen muchos métodos que son fundamentalmente incompatibles entre sí. No puede simplemente elegir el "mejor" que lo haga todo perfectamente, porque ningún método único es el ganador definitivo que perfecciona a todos los demás.

Los investigadores no solo demostraron que estos métodos existen; construyeron varios de ellos para mostrar cómo funcionan. Observaron formas comunes de clasificar datos, como el método que siempre fusiona los dos artículos más cercanos primero. Encontraron que una versión específica de este método, que permite fusionar más de dos grupos a la vez cuando están igualmente cerca, funciona perfectamente. También inventaron nuevos métodos basados en qué tan bien separados están los grupos. Un método busca grupos donde los artículos dentro de ellos están mucho más cerca entre sí de lo que están de cualquier cosa fuera de ellos. Otro busca un tipo de separación ligeramente diferente. Demostraron que estos métodos son todos válidos, pero producen resultados distintos. Algunos métodos son muy estrictos y solo encuentran los grupos más obvios y bien separados. Otros son más permisivos y encuentran muchas conexiones más sutiles.

A pesar de esta diversidad salvaje, los investigadores descubrieron un orden oculto. Aunque los métodos no están de acuerdo en los detalles más finos, todos coinciden en las estructuras más obvias y bien separadas. Si toma dos métodos válidos cualesquiera y observa los grupos en los que ambos coinciden, encontrará un esqueleto común de grupos muy claros y distintos. Esto significa que, mientras los métodos pueden diferir en cómo manejan el terreno intermedio y desordenado de los datos, todos respetan la misma base sólida. Los investigadores también exploraron qué sucede si se añade una cuarta regla: que si los datos ya tienen una estructura perfecta de tipo árbol integrada en ellos, el método debe encontrar ese árbol exacto. Incluso con este requisito más estricto, la vasta diversidad de métodos permanece, pero ahora hay un único método, el más grueso, que sirve como punto de partida para todos los demás.

Este trabajo redefine nuestra comprensión de cómo podemos organizar los datos. Muestra que la imposibilidad de satisfacer todos nuestros deseos para un método de clasificación no es un defecto fundamental del universo, sino una limitación de forzar los datos en una sola capa plana. Al permitir que los datos cuenten una historia de grupos anidados, podemos tener un poco de todo. Podemos tener un método que sea invariante a la escala, flexible y estable, todo al mismo tiempo. Los investigadores también demostraron que estos métodos son robustos ante las formas comunes en que preprocesamos nuestros datos, como cambiar las unidades o transformar los números antes de clasificarlos. Esto sugiere que el marco no es solo una curiosidad matemática, sino una herramienta práctica que puede usarse en procesos del mundo real. El estudio nos deja con la imagen de un paisaje lleno de innumerables formas válidas de clasificar el mundo, todas ellas coincidiendo en las características más importantes, pero ofreciendo una rica variedad de perspectivas sobre los detalles.

Resumen Técnico: El agrupamiento jerárquico puede satisfacer conjuntamente la riqueza, la consistencia y la invarianza de escala

Planteamiento del problema
El agrupamiento (clustering) carece de una definición de "clúster" universalmente aceptada, una dificultad formalizada por el Teorema de Imposibilidad de Kleinberg (Kleinberg, 2002). Este teorema demuestra que ningún método de agrupamiento plano (que mapea disimilitudes a una única partición) puede satisfacer simultáneamente tres axiomas naturales: invarianza de escala (independencia de las unidades de medida), riqueza (la capacidad de producir cualquier partición posible dado un insumo apropiado) y consistencia (la propiedad de que el fortalecimiento de las similitudes intra-clúster y el debilitamiento de las similitudes inter-clúster no debería alterar la partición resultante). La tensión surge porque la consistencia permite la creación de nuevas subestructuras dentro de un clúster, lo cual un agrupamiento plano no puede expresar sin violar el axioma.

Este artículo investiga si esta imposibilidad persiste cuando el resultado es una jerarquía (una familia anidada de clústeres) en lugar de una partición plana. Los autores se preguntan si los análogos jerárquicos de los axiomas de Kleinberg pueden satisfacerse conjuntamente.

Metodología y definiciones
Los autores definen un método de agrupamiento jerárquico como un mapa $T$ de un conjunto de funciones de disimilitud $D(X)$ al conjunto de jerarquías $T(X)$ , donde una jerarquía es una familia laminar de clústeres que contiene el conjunto completo $X$ y todos los singletes. Formulan cuatro axiomas para el agrupamiento jerárquico:

Invarianza de escala: $T(\beta d) = T(d)$ para cualquier factor de escala $\beta > 0$ .
Riqueza de partición: Para cada partición $\mathcal{C}$ de $X$ , existe una disimilitud $d$ tal que $\mathcal{C} \subseteq T(d)$ . (Nota: La jerarquía debe contener la partición como un subconjunto de sus clústeres).
Consistencia de partición: Si una partición $\mathcal{C}$ está contenida en $T(d)$ , y $d'$ es un fortalecimiento de $d$ respecto a $\mathcal{C}$ (las distancias intra-clúster disminuyen, las distancias inter-clúster aumentan), entonces $\mathcal{C} \subseteq T(d')$ .
Invarianza de permutación: El resultado depende únicamente de la estructura de disimilitud, no del etiquetado de los puntos.

Un método que satisface los cuatro se denomina admisible. Los autores también consideran una condición más fuerte, la exactitud en ultramétricas, que requiere que si el insumo es una ultramétrica, el método recupere la jerarquía canónica asociada a esa ultramétrica.

Contribuciones clave y resultados

1. Lograbilidad de la admisibilidad
Contrario al entorno de agrupamiento plano, los autores demuestran que existen métodos jerárquicos admisibles. De hecho, existen incontablemente muchos tales métodos.

Construcciones explícitas: El artículo construye varios métodos admisibles:
- Vínculo simple no binario ( $T_{SL}$ ): A diferencia del vínculo simple binario estándar, la variante no binaria (que fusiona todos los clústeres empatados simultáneamente) es admisible.
- Métodos de separación: Dos familias de métodos, $T_{glob}^\eta$ y $T_{loc}^\eta$ , basados en márgenes de separación globales y locales. Estos definen clústeres donde las disimilitudes internas son suficientemente pequeñas en comparación con las externas.
- Clústeres estables de Bryant-Berry ( $T_{stable}$ ): Un método basado en criterios de estabilidad combinatoria, junto con sus variantes de transformación de potencia $T_{stable}^{(p)}$ .
Imposibilidad para otros vínculos: Se demuestra que las variantes no binarias de los vínculos de completitud (complete linkage), promedio (average), Ward, centroide y mediana violan al menos un axioma.

2. Análisis estructural de los métodos admisibles
El conjunto de métodos admisibles, denotado como $H_{\alpha_{adm}}(X)$ , se analiza bajo el orden de refinamiento ( $T_1 \sqsubseteq T_2$ si $T_1(d) \subseteq T_2(d)$ para todo $d$ ).

Diversidad: El conjunto forma un conjunto parcialmente ordenado (poset) con altura, anchura y celularidad incontables.
Sin elemento máximo: No existe un único método admisible "más fino" que refine a todos los demás.
Incompatibilidad: Existen incontablemente muchos elementos máximos incompatibles entre sí (métodos que no pueden ser refinados conjuntamente por ningún otro método admisible). Específicamente, la familia $\{T_{stable}^{(p)} : p > 0\}$ forma una fuerte antichaina ascendente.
Columna vertebral común: A pesar de esta diversidad, los axiomas imponen una estructura común no trivial. Todo método admisible refina una jerarquía de clústeres suficientemente bien separados ( $T_{glob}^\eta$ para algún margen $\eta$ ). Además, cualquier colección finita de métodos admisibles comparte una columna vertebral común.
Sin elemento mínimo: El método trivial (que devuelve solo los singletes y la raíz) es el ínfimo en el espacio de todos los métodos jerárquicos, pero no es admisible porque falla en la riqueza de partición. Por lo tanto, la clase admisible no tiene un elemento mínimo.

3. Admisibilidad fuerte y ultramétricas
Cuando se añade el axioma de exactitud en ultramétricas, la clase se vuelve fuertemente admisible ( $H_{\alpha_{adm}^+}(X)$ ).

Esta clase sigue siendo incontable y retiene la diversidad de los elementos máximos.
Crucialmente, a diferencia de la clase admisible canónica, la clase fuertemente admisible tiene un elemento mínimo: $T_{glob}$ (el método con la secuencia de márgenes $\eta = \mathbf{1}$ ). Esto proporciona un método más grueso para la clase fuertemente admisible.

4. Preprocesamiento y composición
El artículo estudia las transformaciones de preprocesamiento $\mu: D(X) \to D(X)$ aplicadas antes del agrupamiento.

Condiciones de preservación: Los autores derivan condiciones generales bajo las cuales una transformación preserva los axiomas (por ejemplo, la escala conmuta con $\mu$ , los fortalecimientos mapean a fortalecimientos).
Ejemplos:
- Camino minimax (Ultramétrica subdominante): La transformación $B^*$ que mapea una disimilitud a su ultramétrica subdominante preserva la invarianza de escala, la invarianza de permutación y la exactitud ultramétrica. Esto conduce a la factorización $T_{SL} = T_{glob} \circ B^*$ , mostrando que el vínculo simple es una composición de una transformación ultramétrica y un método de separación.
- PCA y HDBSCAN: El artículo analiza el preprocesamiento de PCA y de alcanzabilidad mutua (mutual-reachability), mostrando que preservan la invarianza de escala y de permutación, pero generalmente fallan en preservar la riqueza o la consistencia.

Significado
El artículo demuestra que la imposibilidad fundamental de satisfacer los axiomas de Kleinberg es un artefacto de restringir el resultado a particiones planas. Al pasar a salidas jerárquicas, los axiomas se vuelven conjuntamente satisfactibles, abriendo la puerta a un vasto paisaje de métodos admisibles.

El trabajo revela que, si bien el espacio de métodos admisibles es extremadamente diverso (careciendo de una solución única óptima), no es carente de estructura. Los axiomas imponen una columna vertebral "conservadora" de clústeres bien separados que todos los métodos admisibles deben respetar, mientras permiten la libertad en cómo se resuelven las estructuras más finas. Esto proporciona un marco conceptual para entender los compromisos en el agrupamiento jerárquico y sugiere que la elección de un método específico dentro de la clase admisible depende del equilibrio deseado entre la sensibilidad al ruido y la granularidad de la salida, en lugar de una violación de los principios axiomáticos fundamentales.

Los autores señalan que este marco conecta con el trabajo previo de Carlsson y Mémoli (2010) y Ackerman y Ben-David (2016), pero difiere al centrarse en jerarquías no ponderadas y al retener la fuerza total del axioma de consistencia de Kleinberg, resultando en una clase de métodos más amplia y diversa en lugar de una caracterización de un único algoritmo.

Más como este