Agrupamiento por enlace completo

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 otros nuevos.${\displaystyle N\times N}$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 como ( m ) y la proximidad entre los clústeres ( r ) y ( s ) se denota como d [( r ),( s )].  

El algoritmo completo de agrupamiento por enlace consta de los siguientes pasos:

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

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

• Primer agrupamiento

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

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

• Estimación de la longitud de la primera rama

Dejar${\displaystyle u}$denota el nodo al que${\displaystyle a}$y${\displaystyle b}$Ahora están conectados. Configuración ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ asegura que los elementos${\displaystyle a}$y${\displaystyle b}$están equidistantes de${\displaystyle u}$Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que se unen${\displaystyle a}$y${\displaystyle b}$a${\displaystyle u}$entonces tienen longitudes ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$( véase el dendrograma final )

• Primera actualización de la matriz de distancias

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

${\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}$

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

• Segundo agrupamiento

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

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

• Estimación de la longitud de la segunda rama

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

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

• Actualización de la segunda matriz de distancias

Luego procedemos a actualizar el${\displaystyle D_{2}}$matriz en una nueva matriz de distancias${\displaystyle D_{3}}$(ver abajo), reducido en tamaño por una fila y una columna debido a la agrupación de${\displaystyle (a,b)}$con${\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 agrupamiento

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

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

• Estimación de la longitud de la tercera rama

Dejar${\displaystyle w}$denota el nodo al que${\displaystyle c}$y${\displaystyle d}$ahora están conectadas. Las ramas que se unen${\displaystyle c}$y${\displaystyle d}$a${\displaystyle w}$entonces tienen longitudes ${\displaystyle \delta (c,w)=\delta (d,w)=28/2=14}$( véase el dendrograma final )

• Tercera actualización de la matriz de distancias

Solo hay una 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}$

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

Entonces nos unimos a los clústeres${\displaystyle ((a,b),e)}$y${\displaystyle (c,d)}$.

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

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

Deducimos las longitudes de las dos ramas 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 ya está completo. Es ultramétrico porque todas las puntas (${\displaystyle a}$a${\displaystyle e}$) están equidistantes de${\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 está enraizado por${\displaystyle r}$, su nodo más profundo.