El agrupamiento de enlaces completos es uno de varios métodos de agrupamiento jerárquico aglomerativo . Al comienzo del proceso, cada elemento está 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. El método también se conoce como agrupación de vecinos más lejanos . El resultado de la agrupación se puede visualizar como un dendrograma , que muestra la secuencia de fusión de la agrupación y la distancia a la que tuvo lugar cada fusión. [1] [2] [3]
Procedimiento de agrupación
En cada paso, se combinan los dos grupos separados por la distancia más corta. La definición de "distancia más corta" es lo que diferencia entre los diferentes métodos de agrupamiento aglomerativo. En la agrupación de enlaces completos, el vínculo entre dos agrupaciones contiene todos los pares de elementos, y la distancia entre las agrupaciones es igual a la distancia entre los dos elementos (uno en cada agrupación) que están más alejados entre sí. El más corto de estos enlaces que permanece en cualquier paso provoca la fusión de los dos clústeres cuyos elementos están involucrados.
Matemáticamente, la función de vinculación completa - la distancia entre racimos y - se describe mediante la siguiente expresión:
dónde
- es la distancia entre elementos y ;
- y son dos conjuntos de elementos (clústeres).
Algoritmos
Esquema 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. Lala matriz de proximidad D contiene todas las distancias d ( i , j ). A las agrupaciones se les asignan los números de secuencia 0,1, ......, ( n - 1) y L ( k ) es el nivel de la k-ésima agrupación. Un grupo con el número de secuencia m se denota ( m ) y la proximidad entre los grupos ( r ) y ( s ) se denota d [( r ), ( s )].
El algoritmo completo de agrupación en clústeres de vinculación consta 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.
Esquema óptimamente eficiente
El algoritmo explicado anteriormente es fácil de entender pero complejo. . En mayo de 1976, D. Defays propuso un algoritmo óptimamente eficiente de solo complejidadconocido como CLINK (publicado en 1977) [4] inspirado en el algoritmo similar SLINK para la agrupación de un solo enlace .
Ejemplo de trabajo
El 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 (). [5] [6]
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 pequeño de , entonces unimos 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 reteniendo la distancia máxima 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
Ahora reiteramos los tres pasos anteriores, comenzando desde la nueva matriz de distancias :
(a, b) | C | D | mi | |
---|---|---|---|---|
(a, b) | 0 | 30 | 34 | 23 |
C | 30 | 0 | 28 | 39 |
D | 34 | 28 | 0 | 43 |
mi | 23 | 39 | 43 | 0 |
Aquí, es el valor más bajo de , entonces nos unimos al clúster 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 , 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 una fila y una columna debido a la agrupación de con :
Tercer paso
- Tercer agrupamiento
Reiteramos de nuevo los tres pasos anteriores, partiendo de la matriz de distancias actualizada .
((a, b), e) | C | D | |
---|---|---|---|
((a, b), e) | 0 | 39 | 43 |
C | 39 | 0 | 28 |
D | 43 | 28 | 0 |
Aquí, es el valor más pequeño de , entonces unimos elementos y .
- Estimación de la longitud de la tercera rama
Dejar denotar el nodo al que y ahora están conectados. Las ramas que se unen y a luego tener longitudes ( ver el dendrograma final )
- Actualización de la matriz de la tercera distancia
Hay una sola entrada para actualizar:
Último paso
El final matriz es:
((a, b), e) | (CD) | |
---|---|---|
((a, b), e) | 0 | 43 |
(CD) | 43 | 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 las dos longitudes de rama restantes:
El dendrograma de ligamiento completo
El dendrograma ahora está completo. Es ultramétrico porque todas las puntas ( a ) son equidistantes de :
Por tanto, el dendrograma tiene sus raíces en , su nodo más profundo.
Comparación con otros vínculos
Los esquemas de vinculación alternativos incluyen la agrupación de vínculos únicos y la agrupación de vínculos promedio : implementar un vínculo diferente en el algoritmo ingenuo es simplemente una cuestión de usar una fórmula diferente para calcular las distancias entre grupos en el cálculo inicial de la matriz de proximidad y en el paso 4 de lo anterior algoritmo. Sin embargo, no se dispone de un algoritmo de eficacia óptima para enlaces arbitrarios. La fórmula que debe ajustarse se ha resaltado con texto en negrita.
La agrupación de enlaces completa evita un inconveniente del método de enlace único alternativo : el llamado fenómeno de encadenamiento , donde los grupos formados a través de la agrupación de enlaces únicos pueden forzarse juntos debido a que los elementos individuales están cerca unos de otros, aunque muchos de los elementos de cada grupo pueden estar muy distantes entre sí. El enlace completo tiende a encontrar grupos compactos de diámetros aproximadamente iguales. [7]
Agrupación de un solo enlace . | Agrupación de enlaces completos. | Agrupación de enlaces promedio: WPGMA . | Agrupación de enlaces promedio: UPGMA . |
Ver también
Referencias
- ^ Sorensen T (1948). "Un método para establecer grupos de igual amplitud en sociología vegetal basado en la similitud de especies y su aplicación a los análisis de la vegetación en los comunes daneses". Biologiske Skrifter . 5 : 1–34.
- ^ Legendre P, Legendre L (1998). Ecología numérica (Segunda edición inglesa). pag. 853.
- ^ Everitt BS, Landau S , Leese M (2001). Análisis de conglomerados (Cuarta ed.). Londres: Arnold. ISBN 0-340-76119-9.
- ^ Defays D (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 .
- ^ 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 .
- ^ Everitt, Landau y Leese (2001), págs. 62-64.
Otras lecturas
- Späth H (1980). Algoritmos de análisis de conglomerados . Chichester: Ellis Horwood.