Agrupación jerárquica

La agrupación jerárquica (también algoritmos de agrupación de gráficos y análisis de agrupación jerárquica ) es un conjunto de algoritmos de ordenación de datos destinados a crear una jerarquía ( árbol ) de agrupaciones anidadas. Hay dos clases de métodos de agrupamiento jerárquico:

Métodos aglomerativos ( eng. aglomerative ): se crean nuevos grupos combinando grupos más pequeños y, por lo tanto, se crea un árbol desde las hojas hasta el tronco;
Métodos divisivos o divisionales ( ing. divisivo ): se crean nuevos grupos dividiendo los grupos más grandes en otros más pequeños y, por lo tanto, se crea un árbol desde el tronco hasta las hojas.

Los algoritmos de agrupamiento jerárquico asumen que el conjunto de objetos analizado se caracteriza por un cierto grado de conectividad. Según el número de características, a veces se distinguen métodos de clasificación monotéticos y politéticos . Como la mayoría de las formas visuales de representar dependencias, los gráficos pierden visibilidad rápidamente a medida que aumenta la cantidad de clústeres. Hay una serie de programas especializados para la construcción de gráficos .

Dendograma

Un dendograma se suele entender como un árbol construido a partir de una matriz de medidas de proximidad. El dendrograma le permite representar la relación entre los objetos de un conjunto dado [1] . La creación de un dendrograma requiere una matriz de similitud (o diferencia ) que determina el nivel de similitud entre pares de conglomerados. Los métodos aglomerativos son los más utilizados.

Para construir una matriz de similitud (diferencia), es necesario establecer una medida de distancia entre dos conglomerados. Los métodos más utilizados para determinar la distancia ( estrategias de clasificación en inglés ) [2] :

El método de enlace único también se conoce como el "método del vecino más cercano" . Se supone que la distancia entre dos conglomerados es igual a la distancia mínima entre dos elementos de diferentes conglomerados: , donde es la distancia entre elementos y pertenecientes a conglomerados y ${\displaystyle \min \,\{\,d(a,b):a\en A,\,b\en B\,\))$ ${\ estilo de visualización d (a, b)}$ $a$ $b$ $A$ $B$
El método de enlace completo también seconoce como el método del vecino lejano . Se supone que la distancia entre dos conglomerados es igual a la distancia máxima entre dos elementos de diferentes conglomerados:; ${\displaystyle \max \,\{\,d(a,b):a\en A,\,b\en B\,\))$
Método de par -grupo usando la media aritmética :
- Sin ponderar ( UPGMA en inglés ). Se supone que la distancia entre dos conglomerados es igual a la distancia promedio entre los elementos de estos conglomerados: , donde es la distancia entre los elementos y pertenecientes a los conglomerados y , y y son las cardinalidades de los conglomerados. ${1 \over {|A|\cdot |B|}}\sum _{a\in A}\sum _{b\in B}d(a,b)$ ${\ estilo de visualización d (a, b)}$ $a$ $b$ $A$ $B$ $|A|$ $|B|$
- Ponderado ( inglés WPGMA ).
Método del centroide ( método inglés de grupos de pares que utiliza el promedio del centroide ):
- No ponderado ( inglés UPGMC ). Se supone que la distancia entre los cúmulos es igual a la distancia entre sus centroides (centros de masa) [3] : , donde y son los centroides y . $\|c_{A}-c_{B}\|$ $California}$ $c_{B}$ $A$ $B$
- Ponderado ( inglés WPGMC ).
método de Ward ._ _ A diferencia de otros métodos de análisis de conglomerados, aquí se utilizan los métodos de análisis de dispersión para estimar las distancias entre conglomerados. Como distancia entre conglomerados, tomamos el incremento en la suma de las distancias al cuadrado de los objetos al centro del conglomerado, obtenido como resultado de su unión [4] : . En cada paso del algoritmo, se combinan dos grupos que conducen al aumento mínimo de la varianza. Este método se utiliza para problemas con clústeres poco espaciados. ${\displaystyle \Delta =\sum _{i}{(x_{i}-{\bar {x)))^{2}}-\sum _{x_{i}\in A}(x_{i} -{\bar {a)))^{2}-\sum _{x_{i}\in B}(x_{i}-{\bar {b)))^{2))$

Para los tres primeros métodos, existe una fórmula general propuesta por A. N. Kolmogorov para medidas de similitud [5] :

K_{\eta }([i,j],k)=\left[{\frac {(n_{i}K(i,k)^{\eta }+(n_{j}K(j,k) ^{\eta })}{n_{i}+n_{j}}}\right]^{{\frac {1}{\eta }}},-{\mathcal {1}}\leqslant \eta \ leqslant +{\mathcal {1}}

donde es un grupo de dos objetos (clusters) y ; — el objeto (grupo) con el que se busca la similitud del grupo especificado; es el número de elementos en el grupo ; es el número de elementos en el grupo . Para distancias existe una fórmula similar de Lance-Williams [6] . $[yo]$ $i$ $j$ $k$ $n_{yo}$ $i$ $Nueva Jersey}$ $j$

Pléyades correlativas

Ampliamente utilizado en geobotánica y floristería . A menudo se denominan pléyades de correlación [7] [8] [9] [10] .

Un caso especial es el método conocido como método de construcción de árboles óptimos (dendritas) , que fue propuesto por el matemático de la escuela de Lviv Hugo Steinhaus [11] , posteriormente el método fue desarrollado por matemáticos de la escuela taxonómica de Wroclaw [12] . Las dendritas tampoco deben formar ciclos. Puede usar parcialmente arcos dirigidos de gráficos usando medidas de inclusión adicionales (medidas de similitud asimétrica).

Diagrama de Czekanowski

El método de "diagonalización" de la matriz de diferencias y la representación gráfica de grupos a lo largo de la diagonal principal de la matriz de diferencias (diagrama de Czekanowski) fue propuesto por primera vez por Jan Czekanowski en 1909 [13] . Aquí hay una descripción de la metodología:

La esencia de este método radica en el hecho de que la amplitud total de los valores de similitud obtenidos se divide en varias clases, y luego en la matriz de valores de similitud, estos valores se reemplazan por un sombreado que es diferente para cada clase, y generalmente se usa un sombreado más oscuro para las clases de mayor similitud. Luego, al cambiar el orden de las descripciones en la tabla, se aseguran de que haya más descripciones similares a continuación [14]

Pongamos un ejemplo hipotético de obtención del diagrama anterior. La base del método es la construcción de una matriz de clausura transitiva [15] .

Para construir una matriz de cierre transitiva, tomemos una matriz de similitud simple y multiplíquela por sí misma:

K^{{(2)}}(i,j)=máx(mín(K(i,1),K(1,j)),...,mín(K(i,q),K(q ,j)))

donde es el elemento en la intersección de la -ésima fila y la -ésima columna en la nueva (segunda) matriz obtenida después de la primera iteración; es el número total de filas (columnas) de la matriz de similitud. Este procedimiento debe continuarse hasta que la matriz se vuelva idempotente (es decir, autosimilar): , donde n es el número de iteraciones. $K(i, j)$ $i$ $j$ $q$ $K^{{(n)}}(i,j)=K^{{(n-1)}}(i,j)$

A continuación, transformamos la matriz de tal manera que los valores numéricos cercanos estén cerca. Si a cada valor numérico se le asigna un color o tono de color (como en nuestro caso), obtenemos el clásico diagrama de Czekanowski. Tradicionalmente, un color más oscuro corresponde a una mayor similitud, y un color más claro corresponde a una menor. En esto es similar al mapa de calor para la matriz de distancia .

Véase también

Fuentes y notas

↑ Zhambyu M. Correspondencias y análisis de conglomerados jerárquicos. — M.: Finanzas y estadísticas, 1988. — 345 p.
↑ Clasificación y clúster. ed. J. Wen Raizina. M.: Mir, 1980. 390 p.
↑ Sneath PHA, Sokal RR Taxonomía numérica: Los principios y prácticas de la clasificación numérica. - San-Francisco: Freeman, 1973. - 573 p.
↑ Ward JH Agrupación jerárquica para optimizar una función objetivo // J. de la Asociación Estadounidense de Estadística, 1963. - 236 p.
↑ Aivazyan S. A., Buchstaber V. M., Enyukov I. S., Meshalkin L. D. Estadística aplicada: Clasificación y reducción de dimensionalidad. - M .: Finanzas y estadísticas, 1989. - 607 p.
↑ Lance GN, Willams WT Una teoría general de las estrategias de clasificación de clasificación. 1. Sistemas jerárquicos // Comp. J. 1967. No. 9. P. 373-380.
↑ von Terentjev PV Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia) // Biometrika. 1931. Nº 23(1-2). pág. 23-51.
↑ Terentiev P.V. Método de correlación pléyades // Vestn. LGU. N° 9. 1959. S. 35-43.
↑ Terentiev P. V. Mayor desarrollo del método de correlación de las pléyades // Aplicación de métodos matemáticos en biología. T. 1. L.: 1960. S. 42-58.
↑ Vyhandu L.K. Sobre el estudio de sistemas biológicos de atributos múltiples // Aplicación de métodos matemáticos en biología. L.: asunto. 3. 1964. S. 19-22.
↑ Steinhaus G. Caleidoscopio matemático. — M.: Nauka, 1981. — 160 p.
↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropopol. 1951. T. 17. S. 193-211.
↑ Czekanowski J. Zur diferencial Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. antropopol. 1909. Bd 40. S. 44-47.
↑ Vasilevich V.I. Métodos estadísticos en geobotánica. - L.: Nauka, 1969. - 232 p.
↑ Tamura S., Hiquchi S., Tanaka K. Clasificación de patrones basada en relación difusa // Transacción IEEE sobre sistemas, hombre y cibernética, 1971, SMC 1, n.º 1, págs. 61-67.

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG