La técnica de Agrupación Jerárquica es una de las técnicas de agrupación más populares en Machine Learning. Como ya lo hemos explicado anteriormente, la agrupación es la extracción de agrupaciones naturales de objetos de datos similares.
Hay un par de ideas generales que ocurren con bastante frecuencia con respecto a la agrupación:
- Los clústeres deben estar presentes de forma natural en los datos.
- El clustering o agrupamiento debe descubrir patrones ocultos en los datos.
- Los puntos de datos dentro del clúster deben ser similares.
- Los puntos de datos en dos grupos diferentes no deben ser similares.
La Agrupación Jerárquica se basa en el uso de estas técnicas de agrupación para encontrar una jerarquía de agrupaciones, donde esta jerarquía se asemeja a una estructura de árbol, llamada dendrograma.
En términos generales, hay dos maneras de agrupar los puntos de datos basados en la estructura y el funcionamiento algorítmico:
- Aglomerativo
- Divisivo
Expliquemos cada uno de ellos.
Agrupación Jerárquica Aglomerativa
En un enfoque aglomerativo o enfoque ascendente cada muestra se trata como un solo clúster y luego se fusionan, o aglomeran, sucesivamente pares de clústeres hasta que todos los clústeres se hayan fusionado en uno solo.
En esta técnica, inicialmente cada punto de datos se considera como un clúster individual. En cada iteración, los grupos similares se fusionan con otros grupos hasta que se forma un grupo o grupos K.
El algoritmo básico de algomeración es sencillo:
- Calcular la matriz de proximidad
- Dejar que cada punto de datos sea un clúster
- Repetir: fusionar los dos clústeres más cercanos y actualizar la matriz de proximidad
- Hasta que solo quede un único clúster
La operación clave es el cálculo de la proximidad de dos clústeres.
Para entender mejor, veamos una representación de la técnica de agrupamiento jerárquico aglomerativo. Digamos que tenemos seis puntos de datos: A, B, C, D, E, F.
Paso 1: en el paso inicial, calculamos la proximidad de individuales y consideramos los 6 puntos de datos como clústeres individuales.
Paso 2: los grupos similares se fusionan y se forman como un solo grupo. Consideremos que B, C y D, E son clústeres similares que se fusionan en el paso 2. Ahora nos quedamos con cuatro grupos que son: A, BC, DE, F.
Paso 3: calculamos nuevamente la proximidad de los nuevos clústeres y fusionamos los clústeres similares para formar nuevos clústeres: A, BC, DEF.
Paso 4: calcular la proximidad de los nuevos clústeres. Los clústeres DEF y DC son similares y se fusionaron para formar un nuevo clúster. Ahora nos quedan 2 clústeres: A, BCDEF.
Paso 5: finalmente, todos los clústeres se fusionan y forman un solo clúster.
La técnica de agrupamiento jerárquico puede ser visualizada usando un dendrograma. Un dendrograma es un diagrama en forma de árbol que registra las secuencias de fusiones o divisiones. Esto será explicado más adelante.
Agrupación Jerárquica Divisiva
En un agrupamiento divisivo o de arriba hacia abajo, un solo clúster de todas las muestras se divide recursivamente en dos clústeres al menos similares hasta que haya un clúster para cada observación.
En palabras sencillas, podemos decir que la agrupación jerárquica divisiva es exactamente lo opuesto a la agrupación jerárquica aglomerativa.
Esta técnica no se usa tanto que la anterior, por lo que solo daremos un resumen de cómo funciona la misma.
En la agrupación jerárquica divisiva, consideramos todos los puntos de datos como un único clúster y en cada iteración, separamos los puntos de datos del clúster que no son similares. Cada punto de datos que se separa se considera como un clúster individual. Al final, nos quedaremos con n grupos. A medida que dividimos los clústeres individuales en n clústeres, se le llama agrupamiento jerárquico divisiva.
La agrupación aglomerada es ampliamente utiliza en la industria y ese será el enfoque que explicaremos acá. La agrupación jerárquica divisiva será pan comido una vez que tengamos una vez que se entienda el tipo aglomerativo.
Agrupación Jerárquica
La operación clave en la agrupación jerárquica es combinar repetidamente los dos clústeres más cercanos en un clúster más grande.
Veamos a detalle su funcionamiento:
- Se comienza calculando la distancia entre cada par de puntos de observación y se almacena en una matriz de distancia.
- Luego se coloca cada punto en su propio grupo.
- Luego se comienza a fusionar los pares de puntos más cercanos en base a las distancias de la matriz de distancia y como resultado la cantidad de clústeres disminuye en 1.
- Luego se recompila la distancia entre el nuevo clúster y los antiguos y los almacena en una nueva matriz de distancia.
- Por último, repites los pasos 2 y 3 hasta que todos los clústeres se fusionan en uno solo.
Medidas de Vinculación
Como se puede observar, antes de cualquier agrupamiento es necesario determinar la matriz de proximidad, entre cada punto utilizando una función de distancia. Luego, la matriz se actualiza para mostrar la distancia entre cada clúster. Hay varias maneras de medir la vinculación entre los clústeres para decidir las reglas de clustering, a menudo se denominan métodos de vinculación o linkage methods.
Enlace completo
Calcula la distancia máxima entre clústeres antes de la fusión. Para cada par de clústeres, el algoritmo los calcula y fusiona para minimizar la distancia máxima entre los clústeres, en otras palabras, la distancia de los elementos más lejanos.
Enlace simple
La distancia entre dos grupos es la distancia más corta entre dos puntos de cada grupo. Calcula la distancia mínima entre los clústeres antes de la fusión. Este enlace se puede utilizar para detectar valores altos en tu conjunto de datos que pueden ser valores atípicos, ya que se fusionarán al final.
Enlace promedio
Es similar al enlace completo, pero en este caso, el algoritmo utiliza la distancia media entre los pares de clústeres.
Método del centroide
Encuentra el centroide del clúster 1 y el centroide del clúster 2, y luego calcula la distancia entre los dos antes de fusionarse.
Método de Ward
En este método se consideran todos los clústeres y el algoritmo calcula la suma de las distancias cuadradas dentro de los clústeres y las fusiona para minimizarlas. Desde un punto de vista estadística, el proceso de aglomeración conduce a una reducción de la varianza de cada clúster resultante.
La elección del método vinculación depende totalmente cada quien y no hay un método rápido y robusto que siempre dé buenos resultados. Diferentes métodos de vinculación conducen a diferentes clústering.
Medidas de Distancia o Similitud
Ya definimos los métodos de vinculación ahora se define las medidas de distancia a implementar. Las métricas más comunes son las siguientes.
Distancia Euclidiana
Es la distancia ordinaria en línea recta entre dos puntos en el espacio euclidiano. Con esta distancia, el espacio euclidiano se convierte en un espacio métrico.
Distancia Manhattan
Similar a la euclidiana, pero la distancia se calcula sumando el valor absoluto de la diferencia entre las dimensiones. Por ejemplo, la distancia de Manhattan implica moverse en línea recta, primero a lo lardo de un eje y luego junto con el otro.
Distancia del coseno
Reduce el ruido al tener en cuenta la forma de las variables, más que sus valores. Tiende a asociar observaciones que tienen las mismas variables máxima y mínima, independientemente de su valor efectivo.
Dendrograma
Los resultados de la Agrupación Jerárquica se pueden mostrar utilizando un dendrograma. El dendrograma puede ser interpretado como sigue:
En esta figura, al principio 4 y 6 se combinan en un grupo, por ejemplo, el grupo 1, ya que eran los más cercanos en distancia, seguidos por los puntos 1 y 2, por ejemplo, el grupo 2. Después de eso, 5 se fusionó en el mismo grupo 1 seguido de 3, resultando en dos grupos. Por fin los dos clústeres se fusionan en un solo clúster y aquí es donde se detiene el proceso de clustering.
La decisión del número de clústeres que pueden representar mejor a los diferentes grupos se puede elegir observando el dendrograma. La mejor elección del número de clústeres es el número de líneas verticales en el dendrograma cortadas por una línea horizontal que puede cruzar la distancia máxima verticalmente sin intersectar un clúster. En el caso anterior se situará entre las alturas 1,5 y 2,5. Si se hace el corte como se muestra, terminarás con solo dos clústeres.
Ten en cuenta que no es necesario hacer un corte solo en estos lugares, puedes elegir cualquier punto como punto de corte en función de cuántos clústeres desees. Por ejemplo, el corte por debajo de 1,5 y por encima de 1 te dará 3 clústeres.
Esta no es una regla exacta y fácil para decidir el número de clústeres. También puedes considerar graficar el método de la silueta, o el método del codo o cualquier otro que muestre la variación de error con el número de clústeres y tu decides elegir el valor de L donde el error es menor.
Desventajas de la Agrupación Jerárquica
- La Agrupación Jerárquica es computacionalmente costoso por lo tanto no se recomienda en grandes conjuntos de datos mientras que K significa usar tiempo lineal.
- Es sensible al ruido y a los valores atípicos.
- Tenemos que definir el número de clústeres como el algoritmo de Agrupamiento K Means.
La Agrupación Jerárquica es una técnica poderosa que te permite construir estructuras de árbol a partir de similitudes de datos. Ahora puedes ver cómo se relacionan los diferentes subgrupos entre sí, y cuán lejos están los puntos de datos.
Con esto finalizamos la explicación de este contenido. Ya debes entender cómo funciona el algoritmo de agrupamiento jerárquico, por lo tanto te dejo la siguiente pregunta, ¿Cuáles de las siguientes afirmaciones crees tú que sea cierta?
Opción 1: El algoritmo de Agrupamiento Jerárquico se divide en dos aglomerativo y divisivo, pero la más utilizada es el aglomerativo.
Respuecta Correcta.
Opción 2: En el algoritmo de Agrupamiento Jerárquico se deben definir el método de vinculación y medidas de distancia que se implementaran para determinar la proximidad de los puntos.
Respuesta Correcta.
Opción 3: Este es un algoritmo que se puede utilizar cuando se cuenta con grandes conjuntos de datos.
Respuesta Incorrecta. La Agrupación Jerárquica es computacionalmente costoso por lo tanto no se recomienda en grandes conjuntos de datos mientras que K significa usar tiempo lineal.
