Agrupamiento por enlazamiento completo

El agrupamiento por enlazamiento completo es uno de varios métodos de agrupamiento jerárquico. Al principio del proceso, cada elemento es, en sí mismo, un cluster o grupo. Estos grupos son luego combinados en forma secuencial en grupos más grandes hasta que todos los elementos acaban siendo parte de un mismo grupo. Este método también es conocido como agrupamiento del vecino más lejano. El resultado del agrupamiento puede ser visualizado en forma de dendrograma, el cual muestra la secuencia de fusión de los grupos y la distancia a la que cada fusión tuvo lugar.​​​

Procedimiento de agrupamiento

En cada paso, se combinan los dos grupos separados por la distancia más corta. La definición que se use de 'la distancia más corta' es lo que diferencia a los varios métodos de agrupamiento. En el agrupamiento por enlazamiento completo, el enlace entre dos grupos contiene todos los elementos emparejados, y la distancia entre los grupos es igual a la distancia entre los dos elementos (uno en cada grupo) que estén lo más alejado de cada uno. El enlace más corto que quede en cada paso provoca la fusión de los dos grupos cuyos elementos estén involucrados.

Matemáticamente, la función de enlazamiento completo — es decir, la distancia $D(X,Y)$ entre los grupos $X$ y $Y$ — está descrito por la siguiente expresión: $D(X,Y)=\max _{x\in X,y\in Y}d(x,y)$

Dónde

• $d(x,y)$ es la distancia entre los elementos $x\in X$ y $y\in Y$;
• $X$ y $Y$ son dos conjuntos de elementos (grupos).

Algoritmos

Esquema Inocente o Ingenuo

El siguiente algoritmo es un esquema aglomerativo, el cual borra las filas y columnas de una matriz de proximidad cuando los antiguos grupos se fusionan en nuevo grupos. La matriz de proximidad D ($N\times N$) contiene todas las distancias d(i,j). En el agrupamiento se asignan números en orden secuencial 0,1,......, (n − 1) y L(k) es el nivel del k-ésimo agrupamiento. Un grupo con número de secuencia m se escribe como (m) y la proximidad entre los grupos (r) y (s) se escribe d[(r),(s)].

El algoritmo completo de la agrupación por enlazamiento completo consta de los siguientes pasos:

1. Se empieza sin ningún grupo, por lo tanto con un nivel de agrupamiento $L(0)=0$ y un número de secuencia $m=0$.
2. Se encuentra el par de grupos más similar en el actual nivel de agrupamiento, es decir, el par $(r),(s)$ que cumpla con $d[(r),(s)]=\min d[(i),(j)]$, que es el valor mínimo que se pueda encontrar en cualquiera de los pares de grupos en el actual nivel de agrupamiento.
3. Se aumenta el número de secuencia: .$m=m+1$. Se fusionan los grupos $(r)$ y $(s)$en un solo grupo para formar el próximo agrupamiento $m$. Poner el nivel de este agrupamiento como $L(m)=d[(r),(s)]$
4. Actualizar la matriz de proximidad $D$, eliminando las filas y columnas que correspondían a los grupos $(r)$ y $(s)$ y se agrega una nueva fila y una nueva columna que corresponde al reciente grupo formado. La proximidad entre el nuevo grupo, $(r,s)$ y el antiguo grupo $(k)$ se define como $d[(r),(s)]=\max\{d[(k),(r)],d[(k),(s)]\}$.
5. Si todos los objetos hacen parte de un solo grupo, parar. Sino, seguir en el paso 2.

Esquema eficiente optimizado

El algoritmo explicado arriba es fácil de entender pero su complejidad es $O(n^{3})$. En mayo de 1976, D. Defays propuso un algoritmo eficiente optimizado cuya complejidad es solamente de $O(n^{2})$, conocido como CLINK (publicado 1977)​ y se inspiró en el algoritmo SLINK usado en el agrupamiento por enlace único.

Ejemplo

Este ejemplo está basado en una matriz de distancia genética JC69 calculada a partir de la secuencia del ARN ribosomal 5S de alineamiento de cinco bacterias: Bacilo subtilis ($a$), Bacilo stearothermophilus ($b$), Lactobacillus viridescens ($c$), Acholeplasma modicum ($d$), y Micrococcus luteus ($e$).​​

Primer paso

• Primer agrupamiento

Supongamos que tenemos cinco elementos$(a,b,c,d,e)$ y la matriz $D_{1}$con distancias emparejadas entre cada elemento:

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

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

• Estimación de la longitud de la primera rama

Digamos que $u$ representa el nodo al cual $a$ y $b$ ahora están conectados. Estableciendo que $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ asegura que los elementos $a$ y $b$ son equidistantes de $u$. Lo cual corresponde a lo esperado por la hipótesis de la ultrametricidad. Por lo tanto, las ramas que unen a $a$ y $b$ con $u$ tienen una longitud igual a $\delta (a,u)=\delta (b,u)=17/2=8.5$ (ver el dendograma al final)

• Actualización de la primera distancia en la matriz

Procedemos a actualizar la matriz de proximidad inicial $D_{1}$ en una nueva matriz de proximidad $D_{2}$ (ver abajo), donde se eliminó una fila y una columna debido al agrupamiento de $a$ con $b$. Los valores en negrilla en la matriz $D_{2}$ corresponden a las nuevas distancias, calculadas al mantener la máxima distancia entre cada elemento del primer grupo $(a,b)$ y cada uno de los elementos restantes:

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

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

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

Los valores en cursiva en la matriz  no son afectados por la actualización de la matriz ya que corresponden a distancias entre elementos que no están involucrados con el primer agrupamiento

Segundo paso

• Segundo clustering

Ahora se repiten los tres pasos anteriores a partir de la nueva distancia $D_{2}$ en la matriz:

	(a,b)	c	d	e
(a,b)	0	30	34	23
c	30	0	28	39
d	34	28	0	43
e	23	39	43	0

Aquí, $D_{2}((a,b),e)=23$ es el valor más pequeño de $D_{2}$ , así que unimos al grupo $(a,b)$ con el elemento $e$.

• Estimación de la longitud de la segunda rama

Digamos que $v$ representa el nodo al cual $(a,b)$ y $e$ ahora están conectados. Debido a limitaciones de la ultrametricidad, las ramas que unen a $a$ o a $b$ a con $v$, y a $e$ con $v$ son iguales tienen la siguiente longitud total: $\delta (a,v)=\delta (b,v)=\delta (e,v)=23/2=11.5$

Deducimos la longitud de rama que falta de la siguiente manera: $\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3$ (ver el dendograma al final)

• Actualización de la segunda distancia en la matriz

Procedemos a actualizar la matriz $D_{2}$ a una nueva matriz de distancia $D_{3}$ (ver abajo), donde se eliminó una fila y una columna debido al agrupamiento de $(a,b)$ con $e$:

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

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

Tercer paso

• Tercer agrupamiento

Otra vez repetimos los tres pasos anteriores, empezando con la actualización de matriz de distancia $D_{3}$.

	((a,b),e)	c	d
((a,b),e)	0	39	43
c	39	0	28
d	43	28	0

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

• Estimación de la longitud de la tercera rama

Digamos que $w$ representa al nodo al que ${\textstyle c}$ y ${\textstyle d}$ ahora están conectados. Las ramas que unen a ${\textstyle c}$ y ${\textstyle d}$ con $w$ tiene ahora una distancia igual a: $\delta (c,w)=\delta (d,w)=28/2=14$ (ver el dendograma final)

• Actualización de la tercera distancia de la matriz

Hay solo un valor para actualizar:$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 $D_{4}$ es:

	((a,b),e)	(c,d)
((a,b),e)	0	43
(c,d)	43	0

Así que, unimos los grupos $((a,b),e)$ y $(c,d)$.

Digamos que $r$, (la raíz) sea el nodo al cual $((a,b),e)$ y $(c,d)$ ahora están conectadas. Las ramas que enlazan a $((a,b),e)$ y $(c,d)$ con $r$, tendrían las siguientes distancias:

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

Deducimos las longitudes de las ramas restantes:

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

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

El dendograma de enlazamiento completo

WPGMA Dendrogram 5S dato

El dendrograma ya está completo. Es ultramétrico porque todas las líneas (${\textstyle a}$ hasta ${\textstyle e}$) son equidistantes de $r$:

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

Por lo tanto, el dendrograma esta anidado por $r$, su nodo más profundo.

Comparación con otras conexiones

Dentro de los esquemas alternativos de enlazaminto se incluyen el agrupamiento por enlace simple y el agrupamientos por enlace promedio, para implementar otra forma de enlazar los grupos en el algoritmo sencillo, solamente se usa una fórmula diferente para calcular las distancias entre cada grupo en el computo inicial de la matriz de proximidad en el paso 4 del algoritmo usado en la parte superior. Sin embargo, no existe un algoritmo óptimamente eficiente para enlazamientos arbitrarios. la fórmula que se debe ajustar esta resaltada en negrillas (paso 4).

El agrupamiento por enlazamiento completo evita problemas encontrardos en el método de agrupamiento simple, como el fenómeno de encadenamiento, en el cual se puede forzar a los grupos formados por agrupamiento de enlace simple debido a elementos individuales que están muy cerca los unos de los otros, aunque varios elementos de cada grupo puedan estar muy separados entre ellos. El enlazamiento completo tiende a formar grupos de diámetros aproximadamente iguales.​

Comparación de dendrogramas obtenido bajo diferente métodos de agrupamiento para la misma matriz de distancia.

Agrupamiento simple.	Agrupamiento por enlazamiento completo	Agrupamiento por enlazamiento promedio: WPGMA.	Agrupamiento por enlazamiento promedio: UPGMA.

Véase también

• Análisis de grupo
• Agrupamiento Jerárquico
• Reloj molecular
• Método de unión de vecinos
• Agrupación simple
• UPGMA
• WPGMA

Lecturas adicionales

• Cluster Analysis Algorithms. Chichester: Ellis Horwood. 1980. 

• Datos: Q5156437