Agrupación de vínculos completos

Método de agrupamiento jerárquico aglomerativo

La agrupación de enlaces completos es uno de varios métodos de agrupación jerárquica aglomerativa . Al comienzo del proceso, cada elemento está en su propio grupo. 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 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 los grupos 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 agrupación aglomerativa. En la agrupación de vínculos completos, el vínculo entre dos grupos contiene todos los pares de elementos, y la distancia entre los grupos es igual a la distancia entre los 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 grupos 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 elementos y  ; ${\displaystyle x\in X}$ ${\displaystyle y\in Y}$
• ${\displaystyle X}$y son dos conjuntos de elementos (clusters). ${\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 grupos antiguos se fusionan en otros nuevos. La matriz de proximidad D contiene todas las distancias d ( i , j ). A las agrupaciones se les asignan números de secuencia 0,1,......, ( n  − 1) y L ( k ) es el nivel de la k-ésima agrupación. Un grupo con número de secuencia m se denota ( m ) y la proximidad entre los grupos ( r ) y ( s ) se denota d [( r ), ( s )]. ${\displaystyle N\times N}$

El algoritmo completo de agrupamiento de enlaces 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 conglomerados más similar en la agrupación actual, digamos par , según dónde esté el máximo sobre todos los pares de conglomerados en la agrupación actual. ${\displaystyle (r),(s)}$ ${\displaystyle d[(r),(s)]=\max d[(i),(j)]}$
3. Incrementar el número de secuencia: . Fusione grupos en un solo grupo para formar el siguiente grupo . Establezca el nivel de esta agrupación 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 grupos y agregando una fila y una columna correspondientes al grupo recién formado. La proximidad entre el nuevo grupo, denominado , y un grupo antiguo 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 grupo, deténgase. De lo contrario, vaya al paso 2.

Esquema óptimamente eficiente

El algoritmo explicado anteriormente es fácil de entender pero de complejidad . En mayo de 1976, D. Defays propuso un algoritmo óptimamente eficiente de única complejidad conocido como CLINK (publicado en 1977) ^[4] inspirado en el algoritmo similar SLINK para agrupación en clústeres 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

• Primera agrupación

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 elementos y . ${\displaystyle D_{1}(a,b)=17}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

• Estimación de la longitud de la primera rama.

Denotemos el nodo al que y ahora están conectados. La configuración garantiza que los elementos y estén equidistantes de . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que se unen y para luego tener longitudes ( ver 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

Luego procedemos a actualizar la matriz de proximidad inicial en una nueva matriz de proximidad (ver más abajo), reducida en tamaño en una fila y una columna debido a la agrupación de with . 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 que no participan en el primer grupo. ${\displaystyle D_{2}}$

Segundo paso

• Segunda agrupación

Reiteramos ahora 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.

Denotemos el nodo al que y ahora están conectados. 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 que falta: ( 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 distancias (ver más abajo), reducida en tamaño en 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

Volvemos a reiterar los tres pasos anteriores, partiendo de la matriz de distancias actualizada . ${\displaystyle D_{3}}$

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

• Estimación de la longitud de la tercera rama.

Denotemos el nodo al que y ahora están conectados. Las ramas que se unen y para luego tener longitudes ( ver 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}$

Último paso

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

Entonces unimos grupos y . ${\displaystyle ((a,b),e)}$ ${\displaystyle (c,d)}$

Denotemos el nodo (raíz) al que ahora están conectados. Las ramas que se unen y para luego tener 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 enlace completo

Datos del dendrograma 5S de WPGMA

El dendrograma ya está completo. Es ultramétrico porque todas las puntas ( a ) están 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 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 agrupación de vinculación única y agrupación de vinculación 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 óptimamente eficiente para enlaces arbitrarios. La fórmula que debe ajustarse se ha resaltado en negrita.

La agrupación de enlaces completos evita un inconveniente del método alternativo de enlace único : el llamado fenómeno de encadenamiento , donde los grupos formados mediante agrupación de enlaces únicos pueden verse obligados a unirse debido a que los elementos individuales están cerca unos de otros, a pesar de que 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]

Ver también

• Análisis de conglomerados
• Agrupación jerárquica
• reloj molecular
• Unión de vecinos
• Agrupación 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". Biólogo Skrifter . 5 : 1–34.
2. Legendre P, Legendre L (1998). Ecología numérica (Segunda edición en inglés). pag. 853.
3. Everitt BS, Landau S , Leese M (2001). Análisis de conglomerados (Cuarta ed.). Londres: Arnold. ISBN 0-340-76119-9.
4. Defays D (1977). "Un algoritmo eficiente para un método de enlace completo". La revista informática . 20 (4). Sociedad Británica de Computación: 364–366. doi : 10.1093/comjnl/20.4.364.
5. Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosomal 5S, 5.8S y 4.5S publicadas". Investigación de ácidos nucleicos . 14 Suplemento (Suplemento): r1-59. doi :10.1093/nar/14.suppl.r1. PMC 341310 . PMID  2422630. 
6. Olsen GJ (1988). "Análisis filogenético mediante 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.

Otras lecturas

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