Ir al contenido

Agrupamiento por enlazamiento completo

De Wikipedia, la enciclopedia libre

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.[1][2][3]

Procedimiento de agrupamiento

[editar]

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 entre los grupos y — está descrito por la siguiente expresión:

Dónde

  • es la distancia entre los elementos y ;
  • y son dos conjuntos de elementos (grupos).

Algoritmos

[editar]

Esquema Inocente o Ingenuo

[editar]

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 () 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 y un número de secuencia .
  2. Se encuentra el par de grupos más similar en el actual nivel de agrupamiento, es decir, el par que cumpla con , 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: .. Se fusionan los grupos y en un solo grupo para formar el próximo agrupamiento . Poner el nivel de este agrupamiento como
  4. Actualizar la matriz de proximidad , eliminando las filas y columnas que correspondían a los grupos y y se agrega una nueva fila y una nueva columna que corresponde al reciente grupo formado. La proximidad entre el nuevo grupo, y el antiguo grupo se define como .
  5. Si todos los objetos hacen parte de un solo grupo, parar. Sino, seguir en el paso 2.

Esquema eficiente optimizado

[editar]

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

Ejemplo

[editar]

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 (), Bacilo stearothermophilus (), Lactobacillus viridescens (), Acholeplasma modicum (), y Micrococcus luteus ().[5][6]

Primer paso

[editar]
  • Primer agrupamiento

Supongamos que tenemos cinco elementos y la matriz 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, es el valor más pequeño de , así que unimos elementos y .

  • Estimación de la longitud de la primera rama

Digamos que representa el nodo al cual y ahora están conectados. Estableciendo que asegura que los elementos y son equidistantes de . Lo cual corresponde a lo esperado por la hipótesis de la ultrametricidad. Por lo tanto, las ramas que unen a y con tienen una longitud igual a (ver el dendograma al final)

  • Actualización de la primera distancia en la matriz

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

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

[editar]
  • Segundo clustering

Ahora se repiten los tres pasos anteriores a partir de la nueva distancia 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í, es el valor más pequeño de , así que unimos al grupo con el elemento .

  • Estimación de la longitud de la segunda rama

Digamos que representa el nodo al cual y ahora están conectados. Debido a limitaciones de la ultrametricidad, las ramas que unen a o a a con , y a con son iguales tienen la siguiente longitud total:

Deducimos la longitud de rama que falta de la siguiente manera: (ver el dendograma al final)

  • Actualización de la segunda distancia en la matriz

Procedemos a actualizar la matriz a una nueva matriz de distancia (ver abajo), donde se eliminó una fila y una columna debido al agrupamiento de con :

Tercer paso

[editar]
  • Tercer agrupamiento

Otra vez repetimos los tres pasos anteriores, empezando con la actualización de matriz de distancia .

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

Aquí, es el valor más pequeño de , así que unimos los elementos y .

  • Estimación de la longitud de la tercera rama

Digamos que representa al nodo al que y ahora están conectados. Las ramas que unen a y con tiene ahora una distancia igual a: (ver el dendograma final)

  • Actualización de la tercera distancia de la matriz

Hay solo un valor para actualizar:

Paso final

[editar]

La matriz final es:

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

Así que, unimos los grupos y .

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

Deducimos las longitudes de las ramas restantes:

El dendograma de enlazamiento completo

[editar]
WPGMA Dendrogram 5S dato
WPGMA Dendrogram 5S dato

El dendrograma ya está completo. Es ultramétrico porque todas las líneas ( hasta ) son equidistantes de :

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

Comparación con otras conexiones

[editar]

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.[7]

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

[editar]

Referencias

[editar]
  1. «A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons.». Biologiske Skrifter 5: 1-34. 1948. 
  2. Numerical Ecology (Second English edición). 1998. p. 853. 
  3. Everitt, Brian S.; Landau, Sabine; Leese, Morven (2001). Cluster Analysis (Fourth edición). London: Arnold. ISBN 0-340-76119-9. 
  4. «An efficient algorithm for a complete link method». The Computer Journal (British Computer Society) 20 (4): 364-366. 1977. doi:10.1093/comjnl/20.4.364. 
  5. «Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences». Nucleic Acids Research. 14 Suppl (Suppl): r1-59. 1986. PMC 341310. PMID 2422630. doi:10.1093/nar/14.suppl.r1. 
  6. «Phylogenetic analysis using ribosomal RNA». Methods in Enzymology 164: 793-812. 1988. PMID 3241556. doi:10.1016/s0076-6879(88)64084-5. 
  7. Everitt, Landau and Leese (2001), pp. 62-64.

Lecturas adicionales

[editar]
  • Cluster Analysis Algorithms. Chichester: Ellis Horwood. 1980.