Agrupación jerárquica

Método estadístico de análisis que busca construir una jerarquía de clusters.

En minería de datos y estadística , el clustering jerárquico (también llamado análisis de clusters jerárquico o HCA ) es un método de análisis de clusters que busca construir una jerarquía de clusters. Las estrategias de agrupamiento jerárquico generalmente se dividen en dos categorías:

• Aglomerativo : Este es un enfoque " de abajo hacia arriba ": cada observación comienza en su propio grupo y los pares de grupos se fusionan a medida que uno asciende en la jerarquía.
• Divisivo : este es 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 desciende en la jerarquía.

En general, las fusiones y escisiones se determinan de forma codiciosa . Los resultados del agrupamiento jerárquico ^[1] generalmente se presentan en un dendrograma .

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í no son necesarias: lo único que se utiliza es una matriz de distancias . Por otro lado, excepto en el caso especial de distancia de enlace único, no se puede garantizar que ninguno de los algoritmos (excepto la búsqueda exhaustiva en ) encuentre la solución óptima. ${\displaystyle {\mathcal {O}}(2^{n})}$

Complejidad

El algoritmo estándar para la agrupación aglomerativa jerárquica (HAC) tiene una complejidad temporal y requiere memoria, lo que lo hace demasiado lento incluso para conjuntos de datos medianos. Sin embargo, para algunos casos especiales, se conocen métodos de aglomeración eficientes óptimos (de complejidad): SLINK ^[2] para agrupación de enlace único y CLINK ^[3] para agrupación de enlace completo . Con un montón , el tiempo de ejecución del caso general se puede reducir a , una mejora en el límite antes mencionado 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. Existen métodos que utilizan quadtrees que demuestran el tiempo total de ejecución con espacio. ^[4] ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle \Omega (n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n^{2}\log n)}$ ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle {\mathcal {O}}(n^{2})}$ ${\displaystyle {\mathcal {O}}(n)}$

La agrupación divisiva con una búsqueda exhaustiva es , pero es común utilizar heurísticas más rápidas para elegir divisiones, como k -means . ${\displaystyle {\mathcal {O}}(2^{n})}$

Vinculación del clúster

Para decidir qué conglomerados deben combinarse (para aglomerativo) o dónde debe dividirse un conglomerado (para divisivo), 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 distancia apropiada d , como la distancia euclidiana, entre observaciones individuales del conjunto de datos, y un criterio de vinculación, que especifica la disimilitud de los conjuntos en función de las distancias por pares. de observaciones en los conjuntos. La elección de la métrica y del vínculo puede tener un impacto importante en el resultado de la agrupación, donde la métrica de nivel inferior determina qué objetos son más similares , mientras que el criterio de vinculación influye en la forma de los grupos. Por ejemplo, el enlace completo tiende a producir grupos más esféricos que el enlace simple.

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 y una distancia d son: ^{[5] [6]}

Algunos de estos sólo pueden recalcularse de forma recursiva (WPGMA, WPGMC), para muchos un cálculo recursivo con ecuaciones de Lance-Williams es más eficiente, mientras que para otros (Mini-Max, Hausdorff, Medoid) las distancias deben calcularse con las ecuaciones más lentas. fórmula completa. Otros criterios de vinculación incluyen:

• La probabilidad de que los grupos candidatos se generen a partir de la misma función de distribución (vínculo V).
• El producto de los grados de entrada y de salida en un gráfico de k vecinos más cercanos (vínculo de grados de gráfico). ^[15]
• El incremento de algún descriptor de grupo (es decir, una cantidad definida para medir la calidad de un grupo) después de fusionar dos grupos. ^{[16] [17] [18]}

Ejemplo de agrupación aglomerativa

Datos sin procesar

Por ejemplo, supongamos que estos datos se van a agrupar y la distancia euclidiana es la métrica de distancia .

El dendrograma de agrupamiento jerárquico sería:

Representación tradicional

Cortar el árbol a una altura determinada dará como resultado un agrupamiento de partición con una precisión seleccionada. En este ejemplo, cortar después de la segunda fila (desde arriba) del dendrograma producirá grupos {a} {bc} {de} {f}. Cortar después de la tercera fila producirá grupos {a} {bc} {def}, que es un grupo más grueso, con un número menor pero grupos más grandes.

Este método construye la jerarquía a partir de elementos individuales fusionando grupos progresivamente. 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. Normalmente queremos tomar los dos elementos más cercanos, según la distancia elegida.

Opcionalmente, también se puede construir una matriz de distancias 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 los grupos 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. En la página de agrupamiento de enlace único se describe un algoritmo de agrupamiento aglomerativo simple ; se puede adaptar fácilmente a diferentes tipos de vinculación (ver más abajo).

Supongamos que hemos fusionado los dos elementos más cercanos byc , ahora tenemos los siguientes grupos { a } , { b , c }, { d }, { e } y { f }, y queremos fusionarlos más. Para hacer eso, necesitamos tomar la distancia entre {a} y {bc} y, por lo tanto, definir la distancia entre dos grupos. Por lo general, la distancia entre dos grupos es una de las siguientes: ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

• La distancia máxima entre elementos de cada grupo (también llamada agrupación de enlace completo ):

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• La distancia mínima entre elementos de cada grupo (también llamada agrupación de enlace único ):

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• La distancia media entre elementos de cada grupo (también llamada agrupación de enlace promedio, utilizada, por ejemplo, en UPGMA ):

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$

• La suma de toda la varianza intra-grupo.
• El aumento de la varianza del 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 (vínculo V).

En caso de distancias mínimas empatadas, se elige un par aleatoriamente, pudiendo así generar varios dendrogramas estructuralmente diferentes. Alternativamente, todos los pares vinculados pueden unirse al mismo tiempo, generando un dendrograma único. ^[19]

Siempre se puede decidir detener la agrupación cuando hay un número suficientemente pequeño de agrupaciones (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 uno puede detener la agrupación cuando los conglomerados están demasiado separados para fusionarse (criterio de distancia). Sin embargo, este no es el caso, por ejemplo, del enlace centroide donde pueden ocurrir las llamadas inversiones ^{[20] (inversiones, desviaciones de la ultrametricidad).}

Agrupación divisiva

El principio básico de la agrupación divisiva se publicó como el algoritmo DIANA (divisive ANAlysis clustering). ^[21] Inicialmente, todos los datos están en el mismo grupo y el grupo más grande se divide hasta que cada objeto está separado. Como existen formas de dividir cada grupo, se necesitan heurísticas. DIANA elige el objeto con la disimilitud promedio máxima y luego mueve todos los objetos a este grupo que son más similares al nuevo grupo que al resto. ${\displaystyle O(2^{n})}$

Informalmente, DIANA no es tanto un proceso de "división" sino de "vaciamiento": en cada iteración, se elige un grupo existente (por ejemplo, el grupo inicial de todo el conjunto de datos) para formar un nuevo grupo dentro de él. Los objetos se mueven progresivamente a este grupo anidado y vacían el grupo existente. Al final, todo lo que queda dentro de un grupo son grupos anidados que crecieron allí, sin que éste posea ningún objeto suelto por sí mismo.

Formalmente DIANA opera en los siguientes pasos:

1. Sea el conjunto de todos los índices de objetos y el conjunto de todos los grupos formados hasta el momento. ${\displaystyle C_{0}=\{1\dots n\}}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {C}}=\{C_{0}\}}$
2. Repita lo siguiente hasta : ${\displaystyle |{\mathcal {C}}|=n}$
   1. Encuentre el grupo actual con 2 o más objetos que tenga el diámetro más grande: ${\displaystyle C_{*}=\arg \max _{C\in {\mathcal {C}}}\max _{i_{1},i_{2}\in C}\delta (i_{1},i_{2})}$
   2. Encuentre el objeto en este grupo con la mayor diferencia con el resto del grupo: ${\displaystyle i^{*}=\arg \max _{i\in C_{*}}{\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)}$
   3. Saque de su antiguo grupo y colóquelo en un nuevo grupo disidente . ${\displaystyle i^{*}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{\textrm {new}}=\{i^{*}\}}$
   4. Mientras no esté vacío, siga migrando objetos para agregarlos a . Para elegir qué objetos migrar, no solo considere la disimilitud con respecto a , sino también ajuste la disimilitud con el grupo disidente: deje donde definimos y luego deje de iterar cuando o migre . ${\displaystyle C_{*}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle C_{*}}$ ${\displaystyle i^{*}=\arg \max _{i\in C}D(i)}$ ${\displaystyle D(i)={\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)-{\frac {1}{|C_{\textrm {new}}|}}\sum _{j\in C_{\textrm {new}}}\delta (i,j)}$ ${\displaystyle D(i^{*})<0}$ ${\displaystyle i^{*}}$
   5. Añadir .​ ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle {\mathcal {C}}}$

Intuitivamente, lo anterior mide con qué fuerza un objeto quiere abandonar su grupo actual, pero se atenúa cuando el objeto tampoco encajaría en el grupo disidente. Es probable que estos objetos eventualmente formen su propio grupo disidente. ${\displaystyle D(i)}$

El dendrograma de DIANA se puede construir dejando que el grupo disidente sea hijo del grupo ahuecado cada vez. Esto construye un árbol con su raíz y grupos únicos de un solo objeto como sus hojas. ${\displaystyle C_{\textrm {new}}}$ ${\displaystyle C_{*}}$ ${\displaystyle C_{0}}$ ${\displaystyle n}$

Software

Implementaciones de código abierto

Dendrograma de agrupamiento jerárquico del conjunto de datos Iris (usando R ). Fuente

"Agrupación jerárquica y visualización interactiva de dendrogramas en la suite de minería de datos Orange ".

• 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, ^[2] CLINK ^[3] y Anderberg, extracción de conglomerados flexible a partir de dendrogramas y varios otros algoritmos de análisis de conglomerados .
• Julia tiene una implementación dentro del paquete Clustering.jl. ^[22]
• Octave , el análogo GNU de MATLAB , implementa agrupamiento jerárquico en la función "vínculo".
• Orange , un paquete de software de minería de datos, incluye agrupación jerárquica con visualización interactiva de dendrogramas.
• R tiene funciones integradas ^[23] y paquetes que proporcionan funciones para agrupación jerárquica. ^{[24] [25] [26]}
• SciPy implementa agrupación jerárquica en Python, incluido el eficiente algoritmo SLINK.
• scikit-learn también implementa agrupación jerárquica 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 agrupación jerárquica.
• 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 del vecino más cercano con una salida gráfica para un Sistema de Información Geográfica.

Ver también

• Partición del espacio binario
• Jerarquía de volúmenes delimitadores
• 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 el número de grupos en un conjunto de datos
• Agrupación jerárquica de redes.
• Hashing sensible a la localidad
• Búsqueda de vecino más cercano
• Algoritmo de cadena del vecino más cercano
• Taxonomía numérica
• Algoritmo ÓPTICO
• Distancia estadística
• Homología persistente

Referencias

1. Nielsen, Frank (2016). "8. Agrupación jerárquica". Introducción a HPC con MPI para Ciencia de Datos. Saltador. págs. 195-211. ISBN 978-3-319-21903-5.
2. R. Sibson (1973). "SLINK: un algoritmo óptimamente eficiente para el método de clúster de enlace único" (PDF) . La revista informática . Sociedad Británica de Computación. 16 (1): 30–34. doi : 10.1093/comjnl/16.1.30 .
3. D. Defays (1977). "Un algoritmo eficiente para un método de enlace completo". La revista informática . Sociedad Británica de Computación. 20 (4): 364–6. doi : 10.1093/comjnl/20.4.364.
4. Eppstein, David (31 de diciembre de 2001). "Agrupación jerárquica rápida y otras aplicaciones de pares dinámicos más cercanos". Revista ACM de algorítmica experimental . 5 : 1–es. arXiv : cs/9912014 . doi :10.1145/351827.351829. ISSN  1084-6654.
5. "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 .
6. Székely, GJ; Rizzo, ML (2005). "Agrupación jerárquica a través de distancias conjuntas entre distancias: ampliación del método de variación mínima de Ward". Revista de Clasificación . 22 (2): 151–183. doi :10.1007/s00357-005-0012-9. S2CID  206960007.
7. Fernández, Alberto; Gómez, Sergio (2020). "Vínculo versátil: una familia de estrategias de conservación de espacio para agrupaciones jerárquicas aglomerativas". Revista de Clasificación . 37 (3): 584–597. arXiv : 1906.09222 . doi :10.1007/s00357-019-09339-z. S2CID  195317052.
8. 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.
9. Podani, János (1989), Mucina, L.; Dale, MB (eds.), "Nuevos métodos de agrupamiento combinatorio", Sintaxonomía numérica , Dordrecht: Springer Países Bajos, págs. 61–77, doi :10.1007/978-94-009-2432-1_5, ISBN 978-94-009-2432-1, consultado el 4 de noviembre de 2022
10. Ao, SI; Sí, K.; Ng, M.; Cheung, D.; Fong, P.-Y.; Melhado, I.; Sham, PC (7 de diciembre de 2004). "CLUSTAG: agrupación jerárquica y métodos gráficos para seleccionar SNP de etiquetas". Bioinformática . 21 (8): 1735-1736. doi : 10.1093/bioinformática/bti201 . ISSN  1367-4803. PMID  15585525.
11. Basalto, Nicolás; Bellotti, Roberto; De Carlo, Francisco; Facchi, Paolo; Pantaleo, Ester; Pascazio, Saverio (15 de junio de 2007). "Agrupación de Hausdorff de series temporales financieras". Physica A: Mecánica estadística y sus aplicaciones . 379 (2): 635–644. arXiv : física/0504014 . Código Bib : 2007PhyA..379..635B. doi :10.1016/j.physa.2007.01.011. ISSN  0378-4371. S2CID  27093582.
12. Schubert, Erich (2021). HACAM: agrupación aglomerativa jerárquica alrededor de medoides y sus limitaciones (PDF) . LWDA'21: Lernen, Wissen, Daten, Analysen del 1 al 3 de septiembre de 2021, Múnich, Alemania. págs. 191-204 - vía CEUR-WS.
13. Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). Agrupación de medoides jerárquica y no jerárquica mediante medidas de similitud asimétricas. 2016 Octava Conferencia Internacional Conjunta sobre Computación Suave y Sistemas Inteligentes (SCIS) y 17º Simposio Internacional sobre Sistemas Inteligentes Avanzados (ISIS). págs. 400–403. doi :10.1109/SCIS-ISIS.2016.0091.
14. Señor, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Reducción del desorden visual mediante proyección basada en jerarquía de datos etiquetados de alta dimensión (PDF) . Interfaz gráfica. Interfaz gráfica . doi : 10.20380/gi2016.14 . Consultado el 4 de noviembre de 2022 .
15. Zhang, Wei; Wang, Xiaogang; Zhao, Deli; Tang, Xiaoou (2012). "Vínculo de grados de gráfico: agrupación aglomerativa en un gráfico dirigido". En Fitzgibbon, Andrés; Lazebnik, Svetlana ; Perona, Pietro; Sato, Yoichi; Schmid, Cordelia (eds.). Visión por Computador – ECCV 2012 . Apuntes de conferencias sobre informática. vol. 7572. Springer Berlín Heidelberg. págs. 428–441. arXiv : 1208.5092 . Código Bib : 2012arXiv1208.5092Z. doi :10.1007/978-3-642-33718-5_31. ISBN 9783642337185. S2CID  14751.Ver también: https://github.com/waynezhanghk/gacluster
16. Zhang, W.; Zhao, D.; Wang, X. (2013). "Agrupación aglomerativa mediante integral de ruta incremental máxima". Reconocimiento de patrones . 46 (11): 3056–65. Código Bib : 2013PatRe..46.3056Z. CiteSeerX 10.1.1.719.5355 . doi :10.1016/j.patcog.2013.04.013. 
17. Zhao, D.; Tang, X. (2008). "Ciclar grupos mediante la función zeta de un gráfico". NIPS'08: Actas de la 21ª Conferencia Internacional sobre Sistemas de Procesamiento de Información Neural . Curran. págs. 1953–60. CiteSeerX 10.1.1.945.1649 . ISBN  9781605609492.
18. Mamá, Y.; Derksen, H.; Hong, W.; Wright, J. (2007). "Segmentación de datos mixtos multivariados mediante compresión y codificación de datos con pérdida". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 29 (9): 1546–62. doi :10.1109/TPAMI.2007.1085. hdl : 2142/99597 . PMID  17627043. S2CID  4591894.
19. Fernández, Alberto; Gómez, Sergio (2008). "Resolver la no unicidad en agrupaciones jerárquicas aglomerativas utilizando multidendrogramas". Revista de Clasificación . 25 (1): 43–65. arXiv : cs/0608049 . doi :10.1007/s00357-008-9004-x. S2CID  434036.
20. Legendre, P.; Legendre, LFJ (2012). "Análisis de conglomerados §8.6 Reversiones". Ecología Numérica . Desarrollos en modelización ambiental. vol. 24 (3ª ed.). Elsevier. págs. 376–7. ISBN 978-0-444-53868-0.
21. Kaufman, L.; Rousseeuw, PJ (2009) [1990]. "6. Análisis Divisivo (Programa DIANA)". Encontrar grupos en datos: una introducción al análisis de conglomerados . Wiley. págs. 253–279. ISBN 978-0-470-31748-8.
22. "Agrupación jerárquica · Clustering.jl". juliastats.org . Consultado el 28 de febrero de 2022 .
23. "función hclust - RDocumentación". www.rdocumentation.org . Consultado el 7 de junio de 2022 .
24. Galili, Tal; Benjamín, Yoav; Simpson, Gavin; Jefferis, Gregory (28 de octubre de 2021), dendextend: Ampliación de la funcionalidad de 'dendrograma' en R , consultado el 7 de junio de 2022
25. Paradis, Emmanuel; et al. "simio: análisis de filogenética y evolución" . Consultado el 28 de diciembre de 2022 .
26. Fernández, Alberto; Gómez, Sergio (2021-09-12). "mdendro: agrupación jerárquica aglomerativa extendida" . Consultado el 28 de diciembre de 2022 .

Otras lecturas

• Kaufman, L.; Rousseeuw, PJ (1990). Encontrar grupos en 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–8. ISBN 978-0-387-84857-0. Archivado desde el original (PDF) el 10 de noviembre de 2009 . Consultado el 20 de octubre de 2009 .