En la minería de datos y las estadísticas , la agrupación jerárquica (también llamada análisis de agrupamiento jerárquico o HCA ) es un método de análisis de agrupaciones que busca construir una jerarquía de agrupaciones. Las estrategias para la agrupación jerárquica generalmente se dividen en dos tipos: [1]
- Aglomerativo : se trata de un enfoque "de abajo hacia arriba ": cada observación comienza en su propio grupo y los pares de grupos se fusionan a medida que se asciende en la jerarquía.
- Divisivo : se trata de un enfoque "de arriba hacia abajo ": todas las observaciones comienzan en un grupo y las divisiones se realizan de forma recursiva a medida que uno se mueve hacia abajo en la jerarquía.
En general, las fusiones y divisiones se determinan de manera codiciosa . Los resultados de la agrupación jerárquica [2] generalmente se presentan en un dendrograma .
El algoritmo estándar para la agrupación aglomerativa jerárquica (HAC) tiene una complejidad temporal de y requiere memoria, lo que lo hace demasiado lento incluso para conjuntos de datos medianos. Sin embargo, para algunos casos especiales, los métodos de aglomeración eficientes óptimos (de complejidad) son conocidos: SLINK [3] para un solo enlace y CLINK [4] para un agrupamiento de enlace completo . Con un montón , el tiempo de ejecución del caso general se puede reducir a, una mejora en el citado límite de , a costa de aumentar aún más los requisitos de memoria. En muchos casos, la sobrecarga de memoria de este enfoque es demasiado grande para que sea prácticamente utilizable.
A excepción del caso especial de enlace único, ninguno de los algoritmos (excepto la búsqueda exhaustiva en ) se puede garantizar que encontrará la solución óptima.
El agrupamiento divisivo con una búsqueda exhaustiva es , pero es común usar heurísticas más rápidas para elegir divisiones, como k-medias.
Disimilitud de clúster
Para decidir qué grupos deben combinarse (para aglomeración) o dónde debe dividirse un grupo (para divisiones), se requiere una medida de disimilitud entre conjuntos de observaciones. En la mayoría de los métodos de agrupamiento jerárquico, esto se logra mediante el uso de una métrica apropiada (una medida de distancia entre pares de observaciones) y un criterio de vinculación que especifica la disimilitud de conjuntos en función de las distancias por pares de observaciones en los conjuntos.
Métrico
La elección de una métrica adecuada influirá en la forma de los grupos, ya que algunos elementos pueden estar relativamente más cerca entre sí en una métrica que en otra. Por ejemplo, en dos dimensiones, bajo la métrica de distancia de Manhattan, la distancia entre el origen (0,0) y (0.5, 0.5) es la misma que la distancia entre el origen y (0, 1), mientras que bajo la distancia euclidiana métrica la última es estrictamente mayor.
Algunas métricas de uso común para la agrupación jerárquica son: [5]
Nombres | Fórmula |
---|---|
distancia euclidiana | |
Distancia euclidiana al cuadrado | |
Distancia de Manhattan | |
Distancia máxima | |
Distancia de Mahalanobis | donde S es la matriz de covarianza |
Para texto u otros datos no numéricos, a menudo se utilizan métricas como la distancia de Hamming o la distancia de Levenshtein .
Una revisión del análisis de conglomerados en la investigación de la psicología de la salud encontró que la medida de distancia más común en los estudios publicados en esa área de investigación es la distancia euclidiana o la distancia euclidiana al cuadrado. [ cita requerida ]
Criterios de vinculación
El criterio de vinculación determina la distancia entre conjuntos de observaciones en función de las distancias por pares entre observaciones.
Algunos criterios de vinculación comúnmente utilizados entre dos conjuntos de observaciones A y B son: [6] [7]
Nombres | Fórmula |
---|---|
Agrupación máxima o de vinculación completa | |
Agrupación mínima o de enlace único | |
Agrupación de enlaces promedio no ponderada (o UPGMA ) | |
Agrupación de enlaces promedio ponderada (o WPGMA ) | |
Agrupación de enlaces centroides, o UPGMC | dónde y son los centroides de los cúmulos s y t , respectivamente. |
Agrupación mínima de energía |
donde d es la métrica elegida. Otros criterios de vinculación incluyen:
- La suma de toda la varianza intragrupo.
- El aumento de la varianza para el grupo que se fusiona ( criterio de Ward ). [8]
- La probabilidad de que los grupos candidatos se generen a partir de la misma función de distribución (enlace V).
- El producto de grados de entrada y de salida en un gráfico de k vecino más cercano (enlace de grados de gráfico). [9]
- El incremento de algún descriptor de conglomerado (es decir, una cantidad definida para medir la calidad de un conglomerado) después de fusionar dos conglomerados. [10] [11] [12]
Discusión
La agrupación jerárquica tiene la clara ventaja de que se puede utilizar cualquier medida válida de distancia. De hecho, las observaciones en sí mismas no son necesarias: todo lo que se utiliza es una matriz de distancias.
Ejemplo de agrupamiento aglomerativo
Por ejemplo, suponga que estos datos deben agruparse y la distancia euclidiana es la métrica de distancia .
El dendrograma de agrupamiento jerárquico sería como tal:
Cortar el árbol a una altura determinada dará un agrupamiento de particiones con una precisión seleccionada. En este ejemplo, cortar después de la segunda fila (desde la parte superior) del dendrograma producirá los grupos {a} {bc} {de} {f}. Cortar después de la tercera fila producirá agrupaciones {a} {bc} {def}, que es una agrupación más gruesa, con un número menor pero agrupaciones más grandes.
Este método construye la jerarquía a partir de los elementos individuales fusionando grupos de forma progresiva. En nuestro ejemplo, tenemos seis elementos {a} {b} {c} {d} {e} y {f}. El primer paso es determinar qué elementos fusionar en un clúster. Por lo general, queremos tomar los dos elementos más cercanos, según la distancia elegida.
Opcionalmente, también se puede construir una matriz de distancia en esta etapa, donde el número en la i -ésima fila j -ésima columna es la distancia entre los elementos i -ésimo y j -ésimo. Luego, a medida que avanza la agrupación, las filas y columnas se fusionan a medida que se fusionan las agrupaciones y se actualizan las distancias. Esta es una forma común de implementar este tipo de agrupación en clústeres y tiene la ventaja de almacenar en caché las distancias entre los clústeres. Un algoritmo de agrupamiento aglomerativo simple se describe en la página de agrupamiento de un solo enlace ; se puede adaptar fácilmente a diferentes tipos de vínculos (ver más abajo).
Supongamos que hemos fusionado los dos elementos más cercanos b y c , ahora tenemos las siguientes agrupaciones { a }, { b , c }, { d }, { e } y { f }, y queremos unirlos más. Para hacer eso, necesitamos tomar la distancia entre {a} y {bc} y, por lo tanto, definir la distancia entre dos conglomerados. Por lo general, la distancia entre dos grupos. y es uno de los siguientes:
- La distancia máxima entre los elementos de cada clúster (también denominada agrupación de enlaces completos ):
- La distancia mínima entre los elementos de cada clúster (también llamado clúster de enlace único ):
- La distancia media entre los elementos de cada grupo (también llamado agrupamiento de enlace promedio, utilizado por ejemplo en UPGMA ):
- La suma de toda la varianza intragrupo.
- El aumento de la varianza para el grupo que se fusiona ( método de Ward [8] )
- La probabilidad de que los grupos candidatos se generen a partir de la misma función de distribución (enlace V).
En el caso de distancias mínimas vinculadas, se elige un par al azar, pudiendo generar varios dendrogramas estructuralmente diferentes. Alternativamente, todos los pares vinculados se pueden unir al mismo tiempo, generando un dendrograma único. [13]
Siempre se puede decidir dejar de agrupar cuando hay un número suficientemente pequeño de grupos (criterio de número). Algunos vínculos también pueden garantizar que la aglomeración se produzca a una distancia mayor entre los conglomerados que la aglomeración anterior, y luego se puede dejar de agrupar cuando los conglomerados están demasiado separados para fusionarse (criterio de distancia). Sin embargo, este no es el caso de, por ejemplo, el enlace centroide donde pueden ocurrir las llamadas reversiones [14] (inversiones, desviaciones de la ultrametricidad).
Agrupación divisiva
El principio básico de agrupamiento divisivo se publicó como el algoritmo DIANA (agrupamiento de análisis de análisis visual). [15] Inicialmente, todos los datos están en el mismo grupo, y el grupo más grande se divide hasta que cada objeto está separado. Porque existenformas de dividir cada grupo, se necesitan heurísticas. DIANA elige el objeto con la máxima disimilitud promedio y luego mueve todos los objetos a este grupo que son más similares al nuevo grupo que al resto.
Software
Implementaciones de código abierto
- ALGLIB implementa varios algoritmos de agrupamiento jerárquico (enlace único, enlace completo, Ward) en C ++ y C # con memoria O (n²) y tiempo de ejecución O (n³).
- ELKI incluye múltiples algoritmos de agrupamiento jerárquico, varias estrategias de vinculación y también incluye los eficientes algoritmos SLINK, [3] CLINK [4] y Anderberg, extracción de agrupamiento flexible de dendrogramas y varios otros algoritmos de análisis de agrupamiento .
- Octave , el análogo de GNU a MATLAB implementa la agrupación jerárquica en la función "vinculación".
- Orange , un paquete de software de minería de datos, incluye agrupamiento jerárquico con visualización interactiva de dendrogramas.
- R tiene muchos paquetes que proporcionan funciones para la agrupación jerárquica.
- SciPy implementa la agrupación jerárquica en Python, incluido el eficiente algoritmo SLINK.
- scikit-learn también implementa agrupaciones jerárquicas en Python.
- Weka incluye análisis de conglomerados jerárquicos.
Implementaciones comerciales
- MATLAB incluye análisis de conglomerados jerárquicos.
- SAS incluye análisis de conglomerados jerárquicos en PROC CLUSTER.
- Mathematica incluye un paquete de agrupamiento jerárquico.
- NCSS incluye análisis de conglomerados jerárquicos.
- SPSS incluye análisis de conglomerados jerárquicos.
- Qlucore Omics Explorer incluye análisis de conglomerados jerárquicos.
- Stata incluye análisis de conglomerados jerárquicos.
- CrimeStat incluye un algoritmo de clúster jerárquico vecino más cercano con una salida gráfica para un Sistema de Información Geográfica.
Ver también
- Partición de espacio binario
- Jerarquía de volumen delimitador
- Agrupación marrón
- Cladística
- Análisis de conglomerados
- Filogenética computacional
- Algoritmo de agrupación de datos CURE
- El objetivo de Dasgupta
- Dendrograma
- Determinar la cantidad de clústeres en un conjunto de datos
- Agrupación jerárquica de redes
- Hash sensible a la localidad
- Búsqueda de vecino más cercano
- Algoritmo de cadena del vecino más cercano
- Taxonomía numérica
- Algoritmo OPTICS
- Distancia estadística
- Homología persistente
Referencias
- ^ Rokach, Lior y Oded Maimon. "Métodos de agrupación". Manual de minería de datos y descubrimiento de conocimientos. Springer US, 2005. 321-352.
- ^ Frank Nielsen (2016). "Capítulo 8: Agrupación jerárquica" . Introducción a HPC con MPI para ciencia de datos . Saltador.
- ^ a b R. Sibson (1973). "SLINK: un algoritmo de eficiencia óptima para el método de clúster de enlace único" (PDF) . The Computer Journal . Sociedad Británica de Computación. 16 (1): 30–34. doi : 10.1093 / comjnl / 16.1.30 .
- ^ a b D. Defays (1977). "Un algoritmo eficiente para un método de enlace completo" . The Computer Journal . Sociedad Británica de Computación. 20 (4): 364–366. doi : 10.1093 / comjnl / 20.4.364 .
- ^ "El Procedimiento DISTANCIA: Medidas de Proximidad" . Guía del usuario de SAS / STAT 9.2 . Instituto SAS . Consultado el 26 de abril de 2009 .
- ^ "El procedimiento CLUSTER: métodos de agrupación" . Guía del usuario de SAS / STAT 9.2 . Instituto SAS . Consultado el 26 de abril de 2009 .
- ^ Székely, GJ; Rizzo, ML (2005). "Agrupación jerárquica a través de distancias conjuntas entre dentro y fuera: método de varianza mínima de extensión de Ward". Revista de clasificación . 22 (2): 151–183. doi : 10.1007 / s00357-005-0012-9 .
- ^ a b Ward, Joe H. (1963). "Agrupación jerárquica para optimizar una función objetivo". Revista de la Asociación Estadounidense de Estadística . 58 (301): 236–244. doi : 10.2307 / 2282967 . JSTOR 2282967 . Señor 0148188 .
- ^ Zhang, Wei; Wang, Xiaogang; Zhao, Deli; Tang, Xiaoou (2012). Fitzgibbon, Andrew; Lazebnik, Svetlana ; Perona, Pietro; Sato, Yoichi; Schmid, Cordelia (eds.). "Vinculación de grado de gráfico: agrupamiento aglomerativo en un gráfico dirigido". Visión por computadora - ECCV 2012 . Apuntes de conferencias en informática. Springer Berlín Heidelberg. 7572 : 428–441. arXiv : 1208.5092 . Código Bib : 2012arXiv1208.5092Z . doi : 10.1007 / 978-3-642-33718-5_31 . ISBN 9783642337185.Ver también: https://github.com/waynezhanghk/gacluster
- ^ Zhang, et al. "Agrupación aglomerativa a través de la integral de ruta incremental máxima". Reconocimiento de patrones (2013).
- ^ Zhao y Tang. “Ciclización de clústeres mediante la función zeta de un gráfico”. Avances en sistemas de procesamiento de información neuronal. 2008.
- ^ Ma, et al. "Segmentación de datos mixtos multivariados mediante codificación y compresión de datos con pérdida". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas, 29 (9) (2007): 1546-1562.
- ^ Fernández, Alberto; Gómez, Sergio (2008). "Resolver la no unicidad en la agrupación jerárquica aglomerativa mediante multidendrogramas". Revista de clasificación . 25 (1): 43–65. arXiv : cs / 0608049 . doi : 10.1007 / s00357-008-9004-x .
- ^ Legendre, P .; Legendre, L. (2003). Ecología numérica . Elsevier Science BV.
- ^ Kaufman, L. y Rousseeuw, PJ (1990). Encontrar grupos en los datos: una introducción al análisis de conglomerados. Una publicación de Wiley-Science John Wiley & Sons.
Otras lecturas
- Kaufman, L .; Rousseeuw, PJ (1990). Encontrar grupos en los datos: una introducción al análisis de conglomerados (1 ed.). Nueva York: John Wiley. ISBN 0-471-87876-6.
- Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2009). "14.3.12 Agrupación jerárquica" . Los elementos del aprendizaje estadístico (2ª ed.). Nueva York: Springer. págs. 520–528. ISBN 978-0-387-84857-0. Archivado desde el original (PDF) el 10 de noviembre de 2009 . Consultado el 20 de octubre de 2009 .