Agrupamiento por ligamiento completo

Método de agrupamiento jerárquico aglomerativo

La agrupación por ligamiento completo es uno de los diversos métodos de agrupación jerárquica aglomerativa . Al comienzo del proceso, 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 estando en el mismo grupo. El método también se conoce como agrupación por vecinos más lejanos . El resultado de la agrupación se puede visualizar como un dendrograma , que muestra la secuencia de fusión de grupos y la distancia a la que tuvo lugar cada fusión. ^{[1] [2] [3]}

Procedimiento de agrupamiento

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 el agrupamiento por ligamiento completo, el vínculo entre dos grupos contiene todos los pares de elementos, y la distancia entre grupos es igual a la distancia entre esos dos elementos (uno en cada grupo) que están más alejados entre sí. El más corto de estos vínculos que permanece en cualquier paso provoca la fusión de los dos grupos cuyos elementos están involucrados.

Matemáticamente, la función de enlace completa —la distancia entre los conglomerados y — se describe mediante la siguiente expresión: ${\displaystyle D(X,Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle D(X,Y)=\max _{x\in X,y\in Y}d(x,y)}$

dónde

• ${\displaystyle d(x,y)}$es la distancia entre los elementos y  ; ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$
• ${\displaystyle X}$y son dos conjuntos de elementos (clústeres). ${\displaystyle Y}$

Algoritmos

Esquema ingenuo

El siguiente algoritmo es un esquema aglomerativo que borra filas y columnas en una matriz de proximidad a medida que los clústeres antiguos se fusionan con los nuevos. La matriz de proximidad D contiene todas las distancias d ( i , j ). A los clústeres se les asignan números de secuencia 0,1,......, ( n  − 1) y L ( k ) es el nivel del késimo clúster. Un clúster con número de secuencia m se denota ( m ) y la proximidad entre los clústeres ( r ) y ( s ) se denota d [( r ),( s )]. ${\displaystyle N\times N}$

El algoritmo de agrupamiento por vinculación completo consta de los siguientes pasos:

1. Comience con la agrupación disjunta que tiene nivel y número de secuencia . ${\displaystyle L(0)=0}$ ${\displaystyle m=0}$
2. Encuentre el par de clústeres más similar en el agrupamiento actual, digamos el par , de acuerdo a dónde está el máximo en todos los pares de clústeres en el agrupamiento actual. ${\displaystyle (r),(s)}$ ${\displaystyle d[(r),(s)]=\max d[(i),(j)]}$
3. Incrementar el número de secuencia: . Fusionar los clústeres y en un solo clúster para formar el siguiente clúster . Establecer el nivel de este clúster en ${\displaystyle m=m+1}$ ${\displaystyle (r)}$ ${\displaystyle (s)}$ ${\displaystyle m}$ ${\displaystyle L(m)=d[(r),(s)]}$
4. Actualice la matriz de proximidad, , eliminando las filas y columnas correspondientes a los clústeres y y agregando una fila y una columna correspondientes al clúster recién formado. La proximidad entre el nuevo clúster, denotado , y un clúster anterior se define como . ${\displaystyle D}$ ${\displaystyle (r)}$ ${\displaystyle (s)}$ ${\displaystyle (r,s)}$ ${\displaystyle (k)}$ ${\displaystyle d[(r,s),(k)]=\max\{d[(k),(r)],d[(k),(s)]\}}$
5. Si todos los objetos están en un clúster, deténgase. De lo contrario, vaya al paso 2.

Esquema de eficiencia óptima

El algoritmo explicado anteriormente es fácil de entender pero complejo . En mayo de 1976, D. Defays propuso un algoritmo óptimamente eficiente de solo complejidad conocido como CLINK (publicado en 1977) ^[4] inspirado en el algoritmo similar SLINK para agrupamiento de enlace único . ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2})}$

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]} ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

Primer paso

• Primer agrupamiento

Supongamos que tenemos cinco elementos y la siguiente matriz de distancias por pares entre ellos: ${\displaystyle (a,b,c,d,e)}$ ${\displaystyle D_{1}}$

En este ejemplo, es el valor más pequeño de , por lo que unimos los elementos y . ${\displaystyle D_{1}(a,b)=17}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

• Estimación de la longitud de la primera rama

Sea el nodo al que y están conectados ahora. La configuración garantiza que los elementos y sean equidistantes de . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que unen y a tienen entonces longitudes ( ver el dendrograma final ) ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$

• Primera actualización de la matriz de distancias

A continuación, procedemos a actualizar la matriz de proximidad inicial en una nueva matriz de proximidad (ver a continuación), reducida en tamaño en una fila y una columna debido a la agrupación de con . Los valores en negrita corresponden a las nuevas distancias, calculadas conservando la distancia máxima entre cada elemento del primer grupo y cada uno de los elementos restantes: ${\displaystyle D_{1}}$ ${\displaystyle D_{2}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$

${\displaystyle D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30}$

${\displaystyle D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34}$

${\displaystyle D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23}$

Los valores en cursiva no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en el primer grupo. ${\displaystyle D_{2}}$

Segundo paso

• Segundo agrupamiento

Ahora reiteramos los tres pasos anteriores, partiendo de la nueva matriz de distancias  : ${\displaystyle D_{2}}$

Aquí está el valor más bajo de , por lo que unimos el clúster con el elemento . ${\displaystyle D_{2}((a,b),e)=23}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$

• Estimación de la longitud de la segunda rama

Sea el nodo al que y están conectados ahora. Debido a la restricción de ultrametricidad, las ramas que unen o a , y a , son iguales y tienen la siguiente longitud total: ${\displaystyle v}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle v}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle \delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5}$

Deducimos la longitud de la rama faltante: ( ver el dendrograma final ) ${\displaystyle \delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3}$

• Segunda actualización de la matriz de distancias

Luego procedemos a actualizar la matriz en una nueva matriz de distancia (ver a continuación), reducida en tamaño por una fila y una columna debido a la agrupación de con  : ${\displaystyle D_{2}}$ ${\displaystyle D_{3}}$ ${\displaystyle (a,b)}$ ${\displaystyle e}$

${\displaystyle D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39}$

${\displaystyle D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43}$

Tercer paso

• Tercera agrupación

Reiteramos nuevamente los tres pasos anteriores, partiendo de la matriz de distancias actualizada . ${\displaystyle D_{3}}$

Aquí, es el valor más pequeño de , por lo que unimos los elementos y . ${\displaystyle D_{3}(c,d)=28}$ ${\displaystyle D_{3}}$ ${\displaystyle c}$ ${\displaystyle d}$

• Estimación de la longitud de la tercera rama

Sea el nodo al que están conectados y . Las ramas que unen y a tienen entonces longitudes ( ver el dendrograma final ) ${\displaystyle w}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle w}$ ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$

• Tercera actualización de la matriz de distancias

Hay una única entrada para actualizar: ${\displaystyle D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43}$

Paso final

La matriz final es: ${\displaystyle D_{4}}$

Así que unimos clústeres y . ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$

Sea el nodo (raíz) al que están conectados y . Las ramas que unen y a tienen entonces longitudes: ${\displaystyle r}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$ ${\displaystyle r}$

${\displaystyle \delta (((a,b),e),r)=\delta ((c,d),r)=43/2=21.5}$

Deducimos las dos longitudes de rama restantes:

${\displaystyle \delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=21.5-11.5=10}$

${\displaystyle \delta (w,r)=\delta ((c,d),r)-\delta (c,w)=21.5-14=7.5}$

El dendrograma de ligamiento completo

Datos del dendrograma 5S de WPGMA

El dendrograma ya está completo. Es ultramétrico porque todas las puntas ( a ) son equidistantes de  : ${\displaystyle a}$ ${\displaystyle e}$ ${\displaystyle r}$

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (e,r)=\delta (c,r)=\delta (d,r)=21.5}$

Por lo tanto, el dendrograma tiene su raíz en , su nodo más profundo. ${\displaystyle r}$

Comparación con otros vínculos

Los esquemas de vinculación alternativos incluyen la agrupación por vinculación simple y la agrupación por vinculación promedio ; implementar una vinculación 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 del algoritmo anterior. Sin embargo, no hay un algoritmo óptimamente eficiente disponible para vinculaciones arbitrarias. La fórmula que se debe ajustar se ha resaltado con texto en negrita.

La agrupación por ligamiento completo evita un inconveniente del método alternativo de ligamiento simple , el llamado fenómeno de encadenamiento , en el que los grupos formados mediante agrupamiento por ligamiento simple pueden verse forzados a unirse debido a que los elementos individuales están cerca unos de otros, aunque muchos de los elementos en cada grupo pueden estar muy distantes entre sí. El ligamiento completo tiende a encontrar grupos compactos de diámetros aproximadamente iguales. ^[7]

Véase también

• Análisis de conglomerados
• Agrupamiento jerárquico
• Reloj molecular
• Unión de vecinos
• Agrupamiento de enlace único
• UPGMA
• WPGMA

Referencias

1. 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 bienes comunes daneses". Biologiske Skrifter . 5 : 1–34.
2. Legendre P, Legendre L (1998). Ecología numérica (segunda edición en inglés). pág. 853.
3. Everitt BS, Landau S , Leese M (2001). Análisis de conglomerados (cuarta edición). Londres: Arnold. ISBN 0-340-76119-9.
4. Defays D (1977). "Un algoritmo eficiente para un método de enlace completo". The Computer Journal . 20 (4). British Computer Society: 364–366. doi :10.1093/comjnl/20.4.364.
5. Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosómico 5S, 5.8S y 4.5S publicadas". Nucleic Acids Research . 14 Suppl (Supl.): r1-59. doi :10.1093/nar/14.suppl.r1. PMC 341310 . PMID  2422630. 
6. Olsen GJ (1988). "Análisis filogenético utilizando ARN ribosómico". Ribosomas . Métodos en enzimología. Vol. 164. págs. 793–812. doi :10.1016/s0076-6879(88)64084-5. ISBN . 978-0-12-182065-7. PMID  3241556.
7. Everitt, Landau y Leese (2001), págs. 62-64.

Lectura adicional

• Späth H (1980). Algoritmos de análisis de conglomerados . Chichester: Ellis Horwood.