Agrupación jerárquica - Hierarchical clustering

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías Limpieza de datos AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

En minería de datos y estadísticas , la agrupación jerárquica (también llamada análisis de agrupación jerárquica o HCA ) es un método de análisis de agrupación que busca construir una jerarquía de agrupaciones. Las estrategias para la agrupación jerárquica generalmente se dividen en dos tipos:

• 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 generalmente se presentan en un dendrograma .

El algoritmo estándar para la agrupación en clústeres de aglomeración jerárquica (HAC) tiene una complejidad de tiempo 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 aglomerativos óptimos eficientes (de complejidad ): SLINK para un solo enlace y CLINK para la agrupación de enlaces completos . Con un montón , el tiempo de ejecución del caso general se puede reducir a una mejora del límite mencionado anteriormente , 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. ${\ 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})}$

Excepto en el caso especial del enlace único, no se puede garantizar que ninguno de los algoritmos (excepto la búsqueda exhaustiva ) encuentre la solución óptima. ${\ Displaystyle {\ mathcal {O}} (2 ^ {n})}$

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

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:

Nombres	Fórmula
distancia euclidiana	${\ Displaystyle \ | ab \ | _ {2} = {\ sqrt {\ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}}}$
Distancia euclidiana al cuadrado	${\ Displaystyle \ | ab \ | _ {2} ^ {2} = \ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}$
Distancia de Manhattan (o manzana)	${\ Displaystyle \ | ab \ | _ {1} = \ sum _ {i} | a_ {i} -b_ {i} |}$
Distancia máxima (o distancia de Chebyshev)	${\ Displaystyle \ | ab \ | _ {\ infty} = \ max _ {i} | a_ {i} -b_ {i} |}$
Distancia de Mahalanobis	${\ Displaystyle {\ sqrt {(ab) ^ {\ top} S ^ {- 1} (ab)}}}$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 .

Las distancias euclidiana y de Manhattan son los casos especiales de distancia de Minkowski generalizada con p = 1 (para Manhattan) yp = 2 (para euclidiana).

Existen varias otras medidas de disimilitud. En particular, distancias basadas en correlación: distancias de correlación de Pearson, coseno de Eisen, Spearman, Kendall, que se utilizan ampliamente para análisis de datos de expresión génica. La distancia basada en la correlación se define restando el coeficiente de correlación de 1. Hablando estrictamente, las distancias basadas en la correlación no pueden usarse como métricas, mientras que la raíz cuadrada de la misma puede serlo.

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.

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:

Nombres	Fórmula
Agrupación máxima o de vinculación completa	${\ Displaystyle \ max \, \ {\, d (a, b): a \ en A, \, b \ en B \, \}.}$
Agrupación mínima o de enlace único	${\ Displaystyle \ min \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$
Agrupación de enlaces promedio no ponderada (o UPGMA )	${\ Displaystyle {\ frac {1} {| A | \ cdot | B |}} \ sum _ {a \ in A} \ sum _ {b \ in B} d (a, b).}$
Agrupación de enlaces promedio ponderada (o WPGMA )	${\ Displaystyle d (i \ cup j, k) = {\ frac {d (i, k) + d (j, k)} {2}}.}$
Agrupación de enlaces centroides, o UPGMC	${\ Displaystyle \ | c_ {s} -c_ {t} \ |}$donde y son los centroides de los conglomerados s y t , respectivamente. ${\ Displaystyle c_ {s}}$${\ Displaystyle c_ {t}}$
Agrupación mínima de energía	${\ Displaystyle {\ frac {2} {nm}} \ sum _ {i, j = 1} ^ {n, m} \ | a_ {i} -b_ {j} \ | _ {2} - {\ frac {1} {n ^ {2}}} \ sum _ {i, j = 1} ^ {n} \ | a_ {i} -a_ {j} \ | _ {2} - {\ frac {1} { m ^ {2}}} \ sum _ {i, j = 1} ^ {m} \ | b_ {i} -b_ {j} \ | _ {2}}$

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 ).
• 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).
• 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.

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

Datos brutos

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:

Representación tradicional

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 clústeres y es uno de los siguientes: ${\ Displaystyle {\ mathcal {A}}}$${\ Displaystyle {\ mathcal {B}}}$

• La distancia máxima entre los elementos de cada clúster (también denominada agrupación de enlaces completos ):

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

• La distancia mínima entre los elementos de cada clúster (también llamado clúster de enlace único ):

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

• La distancia media entre los elementos de cada grupo (también llamado agrupamiento de enlace promedio, utilizado 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 intragrupo.
• El aumento de la varianza para el grupo que se fusiona ( método de Ward )
• 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.

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 (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). Inicialmente, todos los datos están en el mismo grupo y el grupo más grande se divide hasta que cada objeto está separado. Debido a que existen formas 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. ${\ Displaystyle O (2 ^ {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 de 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 agrupación jerárquica, varias estrategias de vinculación y también incluye los algoritmos eficientes SLINK, CLINK y Anderberg, extracción de agrupaciones flexible de dendrogramas y varios otros algoritmos de análisis de agrupaciones .
• 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

Referencias

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–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 .