Usuario:Waco527/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 si 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)$$d[(r),(s)]=\min d[(i),(j)]$$(r),(s)$$(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 unico.

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

Segundo paso

• Segundo clustering

[[Categoría:Algoritmos de clustering de datos]] [[Categoría:Bioinformática]] [[Categoría:Filogenética computacional]]