¿Qué es la agrupación jerárquica?

La agrupación en clústeres es una técnica de aprendizaje automático no supervisado que se utiliza en el análisis de datos para detectar y agrupar objetos similares. El análisis de clústeres jerárquicos (HCA), o clústeres jerárquicos, agrupa objetos en una jerarquía de clústeres sin imponer un orden lineal dentro de ellos. Muchas disciplinas, como la biología, el análisis de imágenes y las ciencias sociales, utilizan métodos de agrupación jerárquica para Explorar y reconocer clúster en conjuntos de datos. Los casos de uso incluyen la categorización de poblaciones en investigación clínica, la segmentación de clientes y la detección de comunidades de nodos en modelos de red.

Hay dos tipos de clústeres jerárquicos:

- Enfoque aglomerativo o de abajo hacia arriba¹ que fusiona repetidamente grupos en otros más grandes hasta que surge un solo clúster.

- Enfoque divisivo o descendente que² comienza con todos los datos en un solo clúster y continúa dividiendo clústeres sucesivos hasta que todos los clústeres son singletons.

El análisis de clúster jerárquico tiene altos costos computacionales. Si bien el uso de un montón puede reducir el tiempo de cálculo, aumentan los requisitos de memoria. Tanto el tipo de agrupamiento divisivo como el aglomerativo son "codiciosos", lo que significa que el algoritmo decide qué clústeres fusionar o dividir al hacer la elección localmente óptima en cada etapa del proceso. También es posible aplicar un criterio de parada, en el que el algoritmo detiene la aglomeración o la división de clústeres cuando alcanza un número predeterminado de clústeres.

A menudo se utiliza un diagrama en forma de árbol llamado dendrograma³ para visualizar la jerarquía de los clústeres. Muestra el orden en que se fusionaron o dividieron los clústeres y muestra la similitud o distancia entre los puntos de datos. Los dendogramas también pueden entenderse como una lista anidada de listas⁴ con atributos.

Los algoritmos de agrupamiento jerárquico utilizan el concepto de matriz de disimilitud para decidir qué clústeres fusionar o dividir. La disimilitud es la distancia entre dos puntos de datos medida por un método de vinculación elegido. Los valores en una matriz de disimilitud expresan:

- La distancia⁵, una distancia euclidiana como ejemplo, entre puntos individuales en un conjunto

- Un criterio de agrupación por vínculos, que especifica la disimilitud como una función de las distancias entre pares de puntos a través de conjuntos.

Exploremos los métodos de vinculación de distancia euclidiana más comunes. Ejemplos de otras métricas de distancia que se pueden utilizar incluyen la distancia de Minkowski, Hamming, Mahalanobis, Hausdorf y Manhattan. Tenga en cuenta que cada método de vinculación genera diferentes clústeres a partir del mismo conjunto de datos. La selección del método de agrupación en clústeres de vinculación adecuado depende de factores como el tipo de datos que se agrupan, la densidad de los datos, la forma del clúster y si hay valores atípicos o ruido en el conjunto de datos.

El método de enlace único analiza las distancias por pares entre los elementos de dos clúster y luego utiliza la distancia mínima entre los clúster. El método min maneja bien las formas de clúster no elípticas, pero se verá afectado por el ruido y los valores atípicos. Tiene una limitación conocida como efecto de encadenamiento6. Unos pocos puntos que crean un puente entre un par de clústeres pueden dar como resultado que los dos clústeres se fusionen en uno solo. Los criterios mínimos de vinculación se pueden representar como:

 mina∈A,b∈Bd(a,b)

donde A y B son dos conjuntos de observaciones y d es una función de distancia.

Las distancias de los clústeres también se pueden calcular en función de los puntos que están más alejados entre sí. El método max es menos sensible que el método min al ruido y los valores atípicos, pero usarlo puede sesgar los resultados cuando hay cúmulos globulares o grandes. El enlace máximo a menudo produce más clústeres esféricos que el enlace mínimo. El enlace máximo se puede representar en la fórmula:

 maxa∈A,b∈Bd(a,b)

donde A y B son dos conjuntos de observaciones y d es la distancia.

Estos métodos, introducidos por Sokal y Michener⁷ , definen la distancia entre clústeres como la distancia promedio entre pares en todos los pares de puntos de los clústeres. El algoritmo puede ser el método de grupo de pares no ponderados con media aritmética (UPGMA) o el método de grupo de pares ponderados con media aritmética (WPGMA). El significado de "no ponderado" aquí es que todas las distancias contribuyen por igual a cada promedio.

UPGMA está representado por la fórmula

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

donde *A* y *B* son dos conjuntos de observaciones y *d* es la distancia.

WPGMA está representado por la fórmula

 d(i∪j,k)=d(i,k)+d(j,k)2

donde i y j son los clústeres más cercanos que se combinan en cada paso para formar un nuevo clúster de la unión de i y j. Luego podemos calcular la distancia a otro clúster k, que es la media aritmética de las distancias promedio entre los puntos de datos en k e i y k y j.

Aquí, usamos la distancia entre los centros de los clústeres o centroides. La distancia entre centroides se calcula mediante una función de distancia:

∥μA-μB∥2

donde μ_A es el centroide de A y μ_B es el centroide de B.

Joe H. Ward introdujo el método^{8 del aumento} mínimo de la suma de cuadrados (MISSQ) en la década de 1960. Cada punto de datos comienza en su propio clúster. Este enfoque significa que la suma de cuadrados entre los puntos de datos es inicialmente cero y luego aumenta a medida que fusionamos los clústeres. El método de Ward minimiza la suma de las distancias al cuadrado de los puntos desde los centros de los clústeres a medida que se fusionan. El método de Ward es una buena opción para variables cuantitativas⁹ y se ve menos afectado por el ruido o los valores atípicos. Se puede representar como:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

donde la media de A y la media de B son los centroides de A y B respectivamente, y x es un punto de datos que pertenece a la unión de A y B

El método de varianza mínima de Ward se puede refinar utilizando un algoritmo de Lance-Williams. Estos algoritmos utilizan una fórmula recursiva para actualizar las distancias de los clústeres y encontrar el par de clústeres más cercano óptimo para fusionar.

En el agrupamiento jerárquico aglomerativo, también conocido como anidamiento aglomerativo (AGNES), cada punto de datos comienza como un clúster. El algoritmo utiliza un criterio de agrupamiento de vinculación seleccionado basado en una matriz de disimilitud para decidir qué par de clústeres unir. El algoritmo sube la jerarquía y sigue emparejando clústeres hasta que todo se haya vinculado, creando una serie jerárquica de clústeres anidados. En términos generales, los pasos de clustering aglomerativo¹⁰ son:

1. Calcular la matriz de disimilitud empleando una métrica de distancia particular.

2. Asignar cada punto de datos a un clúster.

3. Fusionar los clústeres en función de un criterio de vinculación para la similitud entre clústeres.

4. Actualizar la matriz de distancias.

5. Repetir los pasos 3 y 4 hasta que quede un solo clúster o se cumpla cualquier criterio de detención.

Los principios detrás de la agrupación jerárquica divisiva fueron desarrollados por Macnaughton-Smith y otros¹¹ en 1964 y explorar más a fondo por Kaufman y Rousseeuw con su algoritmo DIANA (Divisive ANAlysis clúster)¹² en 1990. La agrupación divisiva utiliza el enfoque opuesto a la agrupación aglomerativa. Todos los puntos de datos comienzan en un único clúster que se divide repetidamente en más clústeres. La división se produce hasta que todos los clústeres restantes son singletons o se cumple un criterio de detención, como un número predefinido de clústeres. Los métodos divisivos son mejores para identificar grandes clústeres¹³ y pueden ser más precisos que los métodos aglomerativos porque el algoritmo considera toda la distribución del conjunto de datos desde el inicio del proceso.

Para mejorar la eficiencia, los métodos divisivos utilizan algoritmos de agrupamiento plano, como k-means, para dividir el conjunto de datos en clústeres. El número de clústeres debe especificarse por adelantado. El algoritmo k-means divide los clústeres minimizando la suma de cuadrados dentro del clúster entre los puntos del centroide. Esto se conoce como el criterio de inercia14. Los pasos de agrupamiento divisivo¹⁵ son:

1. Comience con todos los puntos de datos para un conjunto de datos de tamaño N (d1, d2, d3... dN) en un clúster.

2. Divida el clúster en dos clústeres diferentes o heterogéneos utilizando un método de agrupación plana como el algoritmo de medias k.

3. Repita el paso 2, eligiendo el mejor clúster para dividir y eliminando los valores atípicos del clúster menos cohesivo después de cada Iterations.

4. Deténgase cuando cada ejemplo esté en su propio clúster único; de lo contrario, repita el paso 3.

Los resultados de los clústeres suelen presentarse en un dendograma (estructura de árbol binario). El eje x en el dendrograma representa los puntos de datos y el eje y, o la altura de las líneas, muestra qué tan separados estaban los clústeres cuando sefusionaron.

Puede usar un dendrograma para decidir cuántos clústeres¹⁶ habrá en su modelo de agrupamiento final. Una estrategia es identificar el punto de corte natural en el árbol donde las ramas disminuyen y se alargan. Alternativamente, el número de clústeres viene dado por el número de líneas verticales cruzadas cuando una línea horizontal corta el dendrograma.

En la imagen de ejemplo que se muestra aquí, la línea horizontal H1 corta dos líneas verticales. Esto muestra que hay dos clústeres en este punto del proceso: un clúster con los puntos 5, 8 y 2 y un clúster con los puntos restantes. Cuanto más se pueda mover la línea horizontal hacia arriba o hacia abajo sin cortar otras líneas horizontales en el dendrograma, mejor será la selección de este número de clústeres para su modelo de agrupamiento. En el siguiente ejemplo, la línea horizontal H2 selecciona cuatro clústeres. H2 no puede moverse hacia arriba y hacia abajo tanto como H1 antes de cortar otras líneas horizontales. Este escenario muestra que la opción de dos clústeres (H1) es probablemente más apropiada para su modelo de agrupación en clústeres.

Un modelo de agrupamiento robusto¹⁷ crea clústeres con alta similitud intraclase y baja similitud interclase. Sin embargo, puede ser difícil definir la calidad del clúster, y su selección de criterios de vinculación y números de clúster puede afectar significativamente sus resultados. Por lo tanto, al crear un modelo de agrupación en clústeres, pruebe diferentes opciones y seleccione las que mejor le ayuden a explorar y revelar patrones en el conjunto de datos para su consideración futura. Los factores a considerar¹⁸ incluyen:

- El número de clústeres que son prácticos o lógicos para el conjunto de datos (dado el tamaño del conjunto de datos, las formas del clúster, el ruido, etc.)

- Estadísticas, como los valores medio, máximo y mínimo para cada clúster

- La mejor métrica de disimilitud o criterio de vinculación a aplicar

- El impacto de cualquier valor atípico o variable de resultado

- Cualquier conocimiento específico sobre un dominio o conjunto de datos

Otros métodos para ayudar a determinar el número óptimo de clústeres¹⁹ incluyen:

- El método del codo, donde se grafica la suma de cuadrados dentro del clúster contra el número de clústeres y se determina el "codo" (el punto donde el gráfico se nivela)

- Estadística de brechas, donde se compara la suma real de cuadrados dentro del clúster con la suma esperada dentro del clúster de cuadrados para una distribución de referencia nula e identifica la brecha más grande.

El clustering jerárquico proporciona a los científicos de datos conocimientos sobre la estructura y las relaciones dentro de los conjuntos de datos y se puede aplicar en varios casos de uso.

El clustering jerárquico puede ayudar a analizar tendencias y segmentar los datos de los clientes; por ejemplo, agrupándolos por elección de producto, demografía, comportamiento de compra, perfil de riesgo o interacciones con las redes sociales.

Las cohortes de pacientes para la investigación clínica pueden llegar a miles. La agrupación jerárquica ayuda a categorizar poblaciones mixtas en grupos más homogéneos²⁰ utilizando, por ejemplo, criterios de diagnóstico, respuestas fisiológicas o mutaciones de ADN. También se puede aplicar para agrupar especies por características biológicas para comprender el desarrollo evolutivo.

El clustering jerárquico se utiliza en aplicaciones de reconocimiento de texto basadas en imágenes para agrupar caracteres escritos a mano por su forma. También se utiliza para almacenar y recuperar información utilizando ciertos criterios o para categorizar los resultados de búsqueda.

Tanto Python como el lenguaje de programación R se utilizan ampliamente en la ciencia de datos. Python es flexible y puede manejar un amplio espectro de tareas. Alternativamente, R está diseñado específicamente para computación estadística y proporciona opciones ricas para visualizar su análisis de clústeres jerárquicos.

Python proporciona la función AglomerativeClúster²¹ (consulte también los ejemplos de agrupamiento aglomerativo²² en sklearn), y SciPy proporciona una función para trazar dendrogramas23. Paquetes como dendextend²⁴ mejoran la funcionalidad del dendrograma de R, mejorando el análisis de sensibilidad y permitiéndole comparar y manipular diferentes dendrogramas. Para una experiencia práctica, consulte nuestros tutoriales paso a paso: cómo implementar la agrupación en clústeres jerárquica en Python y cómo implementar la agrupación en clústeres jerárquica en R.