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

La agrupación en clústeres es una técnica de machine learning 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 patrones 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 agrupamiento 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 haciendo 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 enlace por distancia euclidiana más comunes. Algunos ejemplos de otras métricas de distancia que pueden emplear son las distancias de Minkowski, Hamming, Mahalanobis, Hausdorf y Manhattan. Tenga en cuenta que cada método de vinculación genera clusters diferentes a partir del mismo conjunto de datos. La selección del método de agrupación por vínculos adecuado depende de factores como el tipo de datos que se van a agrupar, la densidad de los datos, la forma de los conglomerados 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 grupos y luego utiliza la distancia mínima entre los grupos. 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 encadenamiento⁶. 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 de 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 está inicialmente en cero, luego aumenta a medida que fusionamos 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 las 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 clustering 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 clustering de enlace seleccionado basado en una matriz de disimilitud para decidir qué par de clústeres unir. El algoritmo asciende en la jerarquía y sigue emparejando clústeres hasta que todo ha sido enlazado, creando una serie jerárquica de clústeres anidados. A grandes rasgos, los pasos del 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 del clustering jerárquico divisivo fueron desarrollados por Macnaughton-Smith y otros¹¹ en 1964 y explorados más a fondo por Kaufman y Rousseeuw con su algoritmo DIANA (Divisive ANAlysis clustering)¹² en 1990. El clustering divisivo utiliza el enfoque opuesto al clustering aglomerativo. Todos los puntos de datos se inician 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 hasta que se cumple un criterio de parada, 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 medias k para dividir el conjunto de datos en clústeres. El número de clústeres debe especificarse por adelantado. El algoritmo de medias k divide los clústeres minimizando la suma de cuadrados dentro del clúster entre los puntos centroides. Esto se conoce como criterio de inercia¹⁴. 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 del clúster se presentan típicamente en un dendrograma (estructura de árbol binario). El eje xen el dendrograma representa los puntos de datos y el ejey, o la altura de las líneas, muestra qué tan separados estaban los clústeres cuando se fusionaron

Puede utilizar un dendrograma para decidir cuántos clústeres¹⁶ habrá en su modelo de clustering final. Una estrategia consiste en identificar el punto de corte natural en el árbol en el que las ramas disminuyen y se alargan. Alternativamente, el número de clústeres viene dado por el número de líneas verticales que se cruzan 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 el modelo de agrupamiento. En el siguiente ejemplo, la línea horizontal H2 selecciona cuatro clústeres. H2 no es capaz de moverse hacia arriba y hacia abajo hasta H1 antes de cortar otras líneas horizontales. Este escenario muestra que la opción de dos clústeres (H1) es probablemente más adecuada para el modelo de agrupación en clústeres.

Un modelo de clustering robusto¹⁷ crea clústeres con una alta similitud intraclase y una baja similitud interclase. Sin embargo, puede ser difícil definir la calidad de los clústeres, y su selección de criterios de vinculación y números de clústeres puede afectar significativamente sus resultados. Por lo tanto, al crear un modelo de clustering, 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. El clustering jerárquico ayuda a categorizar poblaciones mixtas en grupos más homogéneos²⁰ utilizando, por ejemplo, criterios de diagnóstico, respuestas fisiológicas o mutaciones en el ADN. También se puede aplicar a 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 AgglomerativeCluster²¹ (consulte también los ejemplos de clustering aglomerativo²² en sklearn) y SciPy proporciona una función para trazar los dendrogramas²³. Los paquetes como dendextend²⁴ mejoran la funcionalidad de los dendrogramas de R, mejoran el análisis de sensibilidad y le permiten comparar y manipular diferentes dendrogramas. Para obtener una experiencia práctica, consulte nuestros tutoriales paso a paso: cómo implementar el clustering jerárquico en Python y cómo implementar el clustering jerárquico en R.