En estadística , la agrupación en clústeres de enlace único es uno de los varios métodos de agrupación jerárquica . Se basa en agrupar grupos de forma ascendente (agrupación aglomerativa), en cada paso combinando dos grupos que contienen el par de elementos más cercano que aún no pertenecen al mismo grupo que el otro.
Un inconveniente de este método es que tiende a producir grupos largos y delgados en los que los elementos cercanos del mismo grupo tienen distancias pequeñas, pero los elementos en los extremos opuestos de un grupo pueden estar mucho más lejos entre sí que dos elementos de otros grupos. Esto puede ocasionar dificultades en la definición de clases que podrían subdividir los datos de manera útil. [1]
Descripción general de los métodos de agrupamiento aglomerativo
Al comienzo del proceso de agrupamiento aglomerativo, cada elemento se encuentra en un grupo propio. Luego, los grupos se combinan secuencialmente en grupos más grandes, hasta que todos los elementos terminan en el mismo grupo. En cada paso, se combinan los dos grupos separados por la distancia más corta. La función utilizada para determinar la distancia entre dos conglomerados, conocida como función de enlace , es lo que diferencia los métodos de agrupamiento aglomerativo.
En la agrupación de un solo enlace, la distancia entre dos grupos está determinada por un solo par de elementos: esos dos elementos (uno en cada grupo) que están más cerca el uno del otro. La más corta de estas distancias por pares que permanecen en cualquier paso hace que los dos grupos cuyos elementos están involucrados se fusionen. El método también se conoce como agrupación de vecinos más cercanos . El resultado de la agrupación se puede visualizar como un dendrograma , que muestra la secuencia en la que se fusionaron las agrupaciones y la distancia a la que tuvo lugar cada fusión. [2]
Matemáticamente, la función de enlace, la distancia D ( X , Y ) entre los grupos X e Y , se describe mediante la expresión
donde X y Y son dos conjuntos de elementos considerados como racimos, y d ( x , Y ) denota la distancia entre los dos elementos de x y y .
Algoritmo ingenuo
El siguiente algoritmo es un esquema de aglomeración que borra filas y columnas en una matriz de proximidad a medida que los grupos antiguos se fusionan con otros nuevos. La matriz de proximidad contiene todas las distancias . A las agrupaciones se les asignan números de secuencia y es el nivel del -th agrupación. Un grupo con número de secuencia m se denota ( m ) y la proximidad entre grupos y se denota .
El algoritmo de enlace único se compone de los siguientes pasos:
- Comience con la agrupación disjunta que tiene nivel y número de secuencia .
- Encuentre el par de clústeres más similar en el clúster actual, digamos par , de acuerdo a donde el mínimo es sobre todos los pares de clústeres en el clúster actual.
- Incrementar el número de secuencia: . Fusionar clústeres y en un solo clúster para formar el siguiente clúster . Establezca el nivel de este agrupamiento en
- Actualizar la matriz de proximidad, , eliminando las filas y columnas correspondientes a los clústeres y y agregar una fila y una columna correspondientes al grupo recién formado. La proximidad entre el nuevo clúster, denotado y viejo racimo Se define como .
- Si todos los objetos están en un grupo, deténgase. De lo contrario, vaya al paso 2.
Ejemplo de trabajo
Este ejemplo de trabajo se basa en una matriz de distancia genética JC69 calculada a partir de la alineación de la secuencia de ARN ribosómico 5S de cinco bacterias: Bacillus subtilis (), Bacillus stearothermophilus (), Lactobacillus viridescens (), Acholeplasma modicum () y Micrococcus luteus (). [3] [4]
Primer paso
- Primera agrupación
Supongamos que tenemos cinco elementos y la siguiente matriz de distancias por pares entre ellos:
a | B | C | D | mi | |
---|---|---|---|---|---|
a | 0 | 17 | 21 | 31 | 23 |
B | 17 | 0 | 30 | 34 | 21 |
C | 21 | 30 | 0 | 28 | 39 |
D | 31 | 34 | 28 | 0 | 43 |
mi | 23 | 21 | 39 | 43 | 0 |
En este ejemplo, es el valor más bajo de , entonces agrupamos elementos y .
- Estimación de la longitud de la primera rama
Dejar denotar el nodo al que y ahora están conectados. Configuración asegura que los elementos y son equidistantes de . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que se unen y a luego tener longitudes ( ver el dendrograma final )
- Actualización de la primera matriz de distancias
Luego procedemos a actualizar la matriz de proximidad inicial en una nueva matriz de proximidad (ver más abajo), reducido en tamaño en una fila y una columna debido a la agrupación de con . Valores audaces encorresponden a las nuevas distancias, calculadas conservando la distancia mínima entre cada elemento del primer grupo y cada uno de los elementos restantes:
Valores en cursiva en no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en el primer grupo.
Segundo paso
- Segundo agrupamiento
Reiteramos ahora las tres acciones anteriores, partiendo de la nueva matriz de distancias :
(a, b) | C | D | mi | |
---|---|---|---|---|
(a, b) | 0 | 21 | 31 | 21 |
C | 21 | 0 | 28 | 39 |
D | 31 | 28 | 0 | 43 |
mi | 21 | 39 | 43 | 0 |
Aquí, y son los valores más bajos de , entonces nos unimos al clúster con elemento y con elemento .
- Estimación de la longitud de la segunda rama
Dejar denotar el nodo al que , y ahora están conectados. Debido a la restricción de ultrametricidad, las ramas que se unen o a , y a , y también a son iguales y tienen la siguiente longitud total:
Deducimos la longitud de la rama que falta: ( ver el dendrograma final )
- Actualización de la segunda matriz de distancia
Luego procedemos a actualizar el matriz en una nueva matriz de distancia (ver más abajo), reducido en tamaño en dos filas y dos columnas debido a la agrupación de con y con :
Último paso
El final matriz es:
((a, b), c, e) | D | |
---|---|---|
((a, b), c, e) | 0 | 28 |
D | 28 | 0 |
Entonces nos unimos a grupos y .
Dejar denotar el nodo (raíz) al que y ahora están conectados. Las ramas que se unen y a luego tener longitudes:
Deducimos la longitud restante de la rama:
El dendrograma de enlace único
El dendrograma ahora está completo. Es ultramétrico porque todas las puntas (, , , , y ) son equidistantes de :
Por tanto, el dendrograma tiene sus raíces en , su nodo más profundo.
Otros vínculos
El algoritmo ingenuo para la agrupación en clústeres de enlace único es esencialmente el mismo que el algoritmo de Kruskal para árboles de expansión mínimos . Sin embargo, en la agrupación de un solo enlace, el orden en el que se forman las agrupaciones es importante, mientras que para los árboles de expansión mínima lo que importa es el conjunto de pares de puntos que forman las distancias elegidas por el algoritmo.
Los esquemas de vinculación alternativos incluyen agrupación de vinculación completa , agrupación de vinculación promedio ( UPGMA y WPGMA ) y el método de Ward . En el algoritmo ingenuo para la agrupación aglomerativa, la implementación de un esquema de enlace diferente puede lograrse simplemente usando una fórmula diferente para calcular las distancias entre grupos en el algoritmo. La fórmula que debe ajustarse se ha resaltado con texto en negrita en la descripción del algoritmo anterior. Sin embargo, algoritmos más eficientes como el que se describe a continuación no se generalizan a todos los esquemas de vinculación de la misma manera.
Agrupación de un solo enlace | Agrupación de enlaces completos | Agrupación de enlaces promedio: WPGMA | Agrupación de enlaces promedio: UPGMA |
Algoritmos más rápidos
El algoritmo ingenuo para la agrupación en clústeres de enlace único es fácil de entender pero lento, con complejidad de tiempo. . [5] En 1973, R. Sibson propuso un algoritmo con complejidad de tiempo y complejidad espacial (ambos óptimos) conocidos como SLINK. El algoritmo slink representa un agrupamiento en un conjunto deelementos numerados por dos funciones. Ambas funciones se determinan al encontrar el grupo más pequeño que contiene ambos elementos y al menos un artículo con un número mayor. La primera función,, elemento de mapas al elemento con el número más grande del grupo . La segunda función,, elemento de mapas a la distancia asociada con la creación del clúster . El almacenamiento de estas funciones en dos matrices que asignan cada número de elemento a su valor de función ocupa espacio, y esta información es suficiente para determinar la agrupación en sí. Como muestra Sibson, cuando se agrega un nuevo elemento al conjunto de elementos, las funciones actualizadas que representan el nuevo agrupamiento de enlace único para el conjunto aumentado, representado de la misma manera, se pueden construir a partir del antiguo agrupamiento en el tiempo.. Luego, el algoritmo SLINK recorre los elementos, uno por uno, y los agrega a la representación del agrupamiento. [6] [7]
Un algoritmo alternativo, que se ejecuta en los mismos límites óptimos de tiempo y espacio, se basa en la equivalencia entre el algoritmo ingenuo y el algoritmo de Kruskal para árboles de expansión mínimos. En lugar de usar el algoritmo de Kruskal, se puede usar el algoritmo de Prim , en una variación sin montones binarios que lleva tiempo y espacio para construir el árbol de expansión mínimo (pero no el agrupamiento) de los elementos y distancias dados. Luego, la aplicación del algoritmo de Kruskal al gráfico disperso formado por los bordes del árbol de expansión mínimo produce el agrupamiento en sí mismo en un tiempo adicional. y espacio . [8]
Ver también
Referencias
- ^ Everitt B (2011). Análisis de conglomerados . Chichester, West Sussex, Reino Unido: Wiley. ISBN 9780470749913.
- ^ Legendre P, Legendre L (1998). Ecología numérica . Desarrollos en Modelización Ambiental. 20 (Segunda edición en inglés). Amsterdam: Elsevier.
- ^ Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosómico 5S, 5.8S y 4.5S publicadas" . Investigación de ácidos nucleicos . 14 Supl (Supl): r1-59. doi : 10.1093 / nar / 14.suppl.r1 . PMC 341310 . PMID 2422630 .
- ^ Olsen GJ (1988). "Análisis filogenético mediante ARN ribosómico". Métodos en enzimología . 164 : 793–812. doi : 10.1016 / s0076-6879 (88) 64084-5 . PMID 3241556 .
- ^ Murtagh F, Contreras P (2012). "Algoritmos para la agrupación jerárquica: una descripción general". Revisiones interdisciplinarias de Wiley: minería de datos y descubrimiento de conocimientos . Biblioteca en línea de Wiley. 2 (1): 86–97. doi : 10.1002 / widm.53 .
- ^ Sibson R (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 .
- ^ Gan G (2007). Agrupación de datos: teoría, algoritmos y aplicaciones . Filadelfia, Pensilvania Alexandria, Virginia: SIAM, Asociación Estadounidense de Estadística de la Sociedad de Matemáticas Industriales y Aplicadas. ISBN 9780898716238.
- ^ Gower JC, Ross GJ (1969). "Árboles de expansión mínimos y análisis de conglomerados de enlace único". Revista de la Sociedad Real de Estadística, Serie C . 18 (1): 54–64. doi : 10.2307 / 2346439 . JSTOR 2346439 . Señor 0242315 ..
enlaces externos
- Enlaces utilizados en Matlab