¿Qué es el clustering jerárquico?

El clustering es una técnica de machine learning no supervisada utilizada en el análisis de datos para detectar y agrupar objetos similares. El análisis de clúster jerárquico (HCA), o clustering jerárquico, 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 clustering jerárquico 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 clustering jerárquico:

- Enfoque aglomerativo o ascendente¹ que fusiona repetidamente los clústeres en otros más grandes hasta que surge un solo clúster.

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

El análisis de clustering jerárquico tiene altos costes computacionales. Aunque el uso de un montón puede reducir el tiempo de cálculo, aumentan los requisitos de memoria. Tanto el tipo de clustering 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 el que se han fusionado o dividido 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 clustering 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 de una matriz de disimilitud expresan:

- La distancia⁵, una distancia euclidiana por ejemplo, entre puntos individuales de un conjunto

- Un criterio de clustering de enlace, que especifica la disimilitud como función de las distancias por pares de puntos entre conjuntos.

Exploremos los métodos de enlace de distancia euclidiana más comunes. Entre los ejemplos de otras métricas de distancia que se pueden utilizar se incluyen la distancia de Minkowski, Hamming, Mahalanobis, Hausdorf y Manhattan. Tenga en cuenta que cada método de enlace genera diferentes clústeres a partir del mismo conjunto de datos. La selección del método de clustering de enlace 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ústeres y, a continuación, utiliza la distancia mínima entre los clústeres. El método mínimo 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 hacer que los dos clústeres se fusionen en uno. Los criterios de vinculación mínimos 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 máximo es menos sensible que el método mínimo al ruido y a los valores atípicos, pero su uso puede sesgar los resultados cuando hay cúmulos globulares o grandes. El enlace máximo suele producir más clústeres esféricos que el enlace mínimo. El enlace máximo se puede representar con 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 media 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í supone que todas las distancias contribuyen por igual a cada promedio.

UPGMA está representada 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. A continuación, podemos calcular la distancia a otro clúster k, que es la media aritmética de las distancias medias entre los puntos de datos en k e i y k y j.

Aquí, utilizamos la distancia entre los centros de los clústeres o centroides. La distancia entre centroides se calcula utilizando 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 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 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 sube la jerarquía y sigue emparejando clústeres hasta que todo se ha 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 utilizando 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 enlace para la similitud entre clústeres.

4. Actualizar la matriz de distancias.

5. Repetir los pasos 3 y 4 hasta que quede un único clúster o se cumpla cualquier criterio de parada.

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 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 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 clustering 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 el criterio de inercia¹⁴. Los pasos de clustering divisivo¹⁵ son:

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

2. Dividir el clúster en dos clústeres diferentes o heterogéneos utilizando un método de clustering plano como el algoritmo de medias k.

3. Repetir el paso 2, elegir el mejor clúster para dividir y eliminar los valores atípicos del clúster menos cohesivo después de cada iteración.

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

Los resultados de los clústeres suelen presentarse en un dendrograma (estructura de árbol binario). El eje x del dendrograma representa los puntos de datos y el eje y, o la altura de las líneas, muestra la distancia entre 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 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 clustering. 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 clustering.

Un modelo de clúster robusto¹⁷ crea clústers 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 enlace 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. Entre los factores que se deben considerar ¹⁸ se incluyen:

- La cantidad de clústeres que son prácticos o lógicos para el conjunto de datos (tamaño del conjunto de datos dado, formas de los clústeres, ruido, etc.)

- Estadísticas, como los valores medios, máximos y mínimos de cada clúster

- La mejor métrica de disimilitud o criterio de enlace a aplicar

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

- Algún conocimiento de dominio o conjunto de datos específico

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 brecha, en la que se compara la suma de cuadrados real dentro del clúster con la suma de cuadrados esperada dentro del clúster 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 los medios 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 para agrupar especies según sus características biológicas con el fin de 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 gestionar un amplio espectro de tareas. Como alternativa, R está diseñado específicamente para la computación estadística y proporciona opciones enriquecidas para visualizar su análisis de clustering jerárquico.

Python proporciona la función AgglomerativeCluster²¹ (véanse también los ejemplos de clusterings aglomerativos ²² en sklearn), y SciPy proporciona una función para trazar dendrogramas²³. 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 clustering jerárquico en Python y cómo implementar clustering clúster jerárquico en R.