La agrupación jerárquica, también conocida como análisis de agrupación jerárquica (HCA, por sus siglas en inglés), es un método de análisis de conglomerados en minería de datos y estadística que busca construir una jerarquía de agrupaciones. A diferencia de los métodos de partición como k-means, que requieren que el número de agrupaciones se especifique de antemano, la agrupación jerárquica produce una estructura anidada que puede cortarse a cualquier nivel para obtener diferentes números de agrupaciones. Los resultados se presentan típicamente en un dendrograma, un diagrama en forma de árbol que ilustra la secuencia de fusiones o divisiones. Este enfoque se utiliza ampliamente en campos como la biología, las ciencias sociales y el aprendizaje automático para el análisis exploratorio de datos.
La principal ventaja de la agrupación jerárquica es su flexibilidad: se puede usar cualquier medida válida de distancia, y no se requieren las observaciones en sí, solo una matriz de distancias. Sin embargo, excepto en el caso especial de la distancia de enlace único, ninguno de los algoritmos puede garantizar la solución óptima sin una búsqueda exhaustiva, que tiene una complejidad temporal de O(2^n).
Estrategias Aglomerativas y Divisivas
Las estrategias de agrupación jerárquica generalmente se dividen en dos categorías: aglomerativa y divisiva. La agrupación aglomerativa, a menudo denominada enfoque "de abajo hacia arriba", comienza con cada punto de datos como una agrupación individual. En cada paso, el algoritmo fusiona las dos agrupaciones más similares basándose en una métrica de distancia elegida (por ejemplo, la distancia euclidiana) y un criterio de enlace (por ejemplo, enlace simple, enlace completo). Este proceso continúa hasta que todos los puntos de datos se combinan en una sola agrupación o se cumple un criterio de parada. Los métodos aglomerativos son más comunes debido a su simplicidad y eficiencia computacional para conjuntos de datos de tamaño pequeño a mediano.
La agrupación divisiva, conocida como un enfoque "de arriba hacia abajo", comienza con todos los puntos de datos en un solo clúster y divide recursivamente el clúster en otros más pequeños. En cada paso, se selecciona un clúster y se divide en dos o más subconjuntos, a menudo utilizando un criterio como la maximización de la distancia entre los clústeres resultantes. Los métodos diVisivos son menos comunes, pero pueden ser útiles cuando el objetivo es identificar primero clústeres grandes y difunidades. En general, las fusiones y divisiones se determinan de manera avariciosa, lo que significa que se toman decisiones óptimas localmente en cada paso sin considerar la estructura global.
Complejidad y Algoritmos
El algoritmo estándar para la agrupación aglomerativa jerárquica (HAC) tiene una complejidad temporal de O(n log n) y requiere Ω(n^2) de memoria, lo que lo hace demasiado lento incluso para conjuntos de datos medianos. Sin embargo, para algunos casos especiales, se conocen métodos eficientes óptimos de complejidad O(n log n) para la agrupación aglomerativa: SLINK para el enlace simple y CLINK para el enlace completo. Con la heurística de un heap, el tiempo de ejecución del caso general se puede reducir a O(n log n) en lugar de O(n log n), a costa de mayores requisitos de memoria. En muchos casos, los overheads de memoria de este enfoque son demasiado grandes para que sea aplicable en la práctica. Existen métodos que utilizan cuadrupletes que demuestran un tiempo total de ejecución de O(n log n) con espacio O(n).
La agrupación divisorial con una búsqueda exhaustiva es O(2^n), pero es común usar heurísticas más rápidas para elegir las divisiones, como k-means. Estas heurísticas permiten la optimalidad por la viabilidad computacional, lo que permite que los métodos divisorales se apliquen a conjuntos de datos más grandes.
Métricas de Distancia
mientras que el criterio de enlace determina cómo se calcula la distancia entre grupos de observaciones, la métrica de distancia subyacente determina cómo se mide la distancia entre observaciones individuales. Debido a que la agrupación jerárquica permite cualquier medida válida de distancia, el método de elección se guía por la naturaleza de los datos y puede tener un efecto significativo en la agrupación resultante.
La distancia euclidiana es la métrica más utilizada para los datos numéricos continuos. Corresponde a la distancia en línea recta entre dos puntos de un espacio euclidiano y es la opción predeterminada en la mayoría del software estadístico. La distancia de Manhattan (también denominada distancia de bloques o L1) suma las diferencias absolutas entre las características. A veces se prefiere cuando las características se miden en diferentes escalas o cuando los datos tienen valores atípicos, ya que es menos sensible a los desvíos grandes que la distancia euclidiana. La distancia coseno mide la disimilitud angular entre dos vectores no nulos y se usa comúnmente en el análisis de textos y en entornos de altísima dimensión.
Criterios de Vinculación
El criterio de enlace determina cómo se calcula la distancia entre dos grupos a partir de las distancias entre sus miembros individuales. El enlace simple (o del vecino más cercano) obtiene la distancia mínima entre dos puntos de los dos clústeres, lo que tiende a producir agrupaciones alargadas y en cadena. El enlace completo (o del vecino más lejano) usa la distancia máxima, lo que distancia en la construcción de agrupaciones compactas y esféricas. El enlace promedio usa la distancia media entre todos los pares de puntos, que ofrece un compromiso entre ambas opciones. El método de Ward minimiza la varianza intragrupal total, lo que lo hace popular para datos continuos. La elección del criterio de enlace puede modificar drásticamente la forma e interpretación del dendrograma resultante.
Aplicaciones y Limitaciones
Agrupación jerárquica se utiliza en múltiples dominios. En biología, se usa para construir árboles filogenéticos sobre la base de la similitud genética. En marketing, ayuda a segmentar clientes en grupos con comportamientos similares. En el análisis de imágenes, puede agrupar píxeles o características. En la inteligencia artificial, la agrupación jerárquica se usa frecuentemente como una técnica de aprendizaje no supervisado para análisis exploratorio de datos y como paso previo al procesamiento con otros algoritmos.
Pese a sus ventajas, la agrupación jerárquica tiene sus limitaciones. La naturaleza avarazón de los algoritmos significa que una vez que se realiza una fusión o división, esta no puede revertirse, lo que puede llevar a resultados no óptimos. La complejidad computacional del método estándar restringe su uso a conjuntos de datos de tamaño moderado, aunque existen implementaciones optimizadas para criterios de enlace específicos. Además, la interpretación del dendrograma puede ser subjetiva, y la elección de métrica de distancia y criterio de enlace requiere conocimiento del dominio.