stringtranslate.com

Agrupamiento por ligamiento completo

La agrupación por ligamiento completo es uno de los diversos métodos de agrupación jerárquica aglomerativa . Al comienzo del proceso, cada elemento se encuentra en un grupo propio. 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 por vecinos más lejanos . El resultado de la agrupación se puede visualizar como un dendrograma , que muestra la secuencia de fusión de grupos y la distancia a la que tuvo lugar cada fusión. [1] [2] [3]

Procedimiento de agrupamiento

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 agrupamiento aglomerativo. En el agrupamiento por ligamiento completo, el vínculo entre dos grupos contiene todos los pares de elementos, y la distancia entre grupos es igual a la distancia entre esos 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 los conglomerados y — se describe mediante la siguiente expresión:

dónde

Algoritmos

Esquema ingenuo

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 los nuevos. 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 ( m ) y la proximidad entre los clústeres ( r ) y ( s ) se denota d [( r ),( s )].

El algoritmo de agrupamiento por vinculación completo consta de los siguientes pasos:

  1. Comience con la agrupación disjunta que tiene nivel y número de secuencia .
  2. Encuentre el par de clústeres más similar en el agrupamiento actual, digamos el par , de acuerdo a dónde está el máximo en todos los pares de clústeres en el agrupamiento actual.
  3. Incrementar el número de secuencia: . Fusionar los clústeres y en un solo clúster para formar el siguiente clúster . Establecer el nivel de este clúster en
  4. Actualice la matriz de proximidad, , eliminando las filas y columnas correspondientes a los clústeres y y agregando una fila y una columna correspondientes al clúster recién formado. La proximidad entre el nuevo clúster, denotado , y un clúster anterior se define como .
  5. Si todos los objetos están en un clúster, deténgase. De lo contrario, vaya al paso 2.

Esquema de eficiencia óptima

El algoritmo explicado anteriormente es fácil de entender pero complejo . En mayo de 1976, D. Defays propuso un algoritmo óptimamente eficiente de solo complejidad conocido como CLINK (publicado en 1977) [4] inspirado en el algoritmo similar SLINK para agrupamiento de enlace único .

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]

Primer paso

Supongamos que tenemos cinco elementos y la siguiente matriz de distancias por pares entre ellos:

En este ejemplo, es el valor más pequeño de , por lo que unimos los elementos y .

Sea el nodo al que y están conectados ahora. La configuración garantiza que los elementos y sean equidistantes de . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que unen y a tienen entonces longitudes ( ver el dendrograma final )

A continuación, procedemos a actualizar la matriz de proximidad inicial en una nueva matriz de proximidad (ver a continuación), reducida en tamaño en una fila y una columna debido a la agrupación de con . 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:

Los valores en cursiva no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en el primer grupo.

Segundo paso

Ahora reiteramos los tres pasos anteriores, partiendo de la nueva matriz de distancias  :

Aquí está el valor más bajo de , por lo que unimos el clúster con el elemento .

Sea el nodo al que y están conectados ahora. Debido a la restricción de ultrametricidad, las ramas que unen o a , y a , son iguales y tienen la siguiente longitud total:

Deducimos la longitud de la rama faltante: ( ver el dendrograma final )

Luego procedemos a actualizar la matriz en una nueva matriz de distancia (ver a continuación), reducida en tamaño por una fila y una columna debido a la agrupación de con  :

Tercer paso

Reiteramos nuevamente los tres pasos anteriores, partiendo de la matriz de distancias actualizada .

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

Sea el nodo al que están conectados y . Las ramas que unen y a tienen entonces longitudes ( ver el dendrograma final )

Hay una única entrada para actualizar:

Paso final

La matriz final es:

Así que unimos clústeres y .

Sea el nodo (raíz) al que están conectados y . Las ramas que unen y a tienen entonces longitudes:

Deducimos las dos longitudes de rama restantes:

El dendrograma de ligamiento completo

Datos del dendrograma 5S de WPGMA
Datos del dendrograma 5S de WPGMA

El dendrograma ya está completo. Es ultramétrico porque todas las puntas ( a ) son equidistantes de  :

Por lo tanto, el dendrograma tiene su raíz en , su nodo más profundo.

Comparación con otros vínculos

Los esquemas de vinculación alternativos incluyen la agrupación por vinculación simple y la agrupación por vinculación promedio ; implementar una vinculación 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 del algoritmo anterior. Sin embargo, no hay un algoritmo óptimamente eficiente disponible para vinculaciones arbitrarias. La fórmula que se debe ajustar se ha resaltado con texto en negrita.

La agrupación por ligamiento completo evita un inconveniente del método alternativo de ligamiento simple , el llamado fenómeno de encadenamiento , en el que los grupos formados mediante agrupamiento por ligamiento simple pueden verse forzados a unirse debido a que los elementos individuales están cerca unos de otros, aunque muchos de los elementos en cada grupo pueden estar muy distantes entre sí. El ligamiento completo tiende a encontrar grupos compactos de diámetros aproximadamente iguales. [7]

Véase también

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". Biologiske Skrifter . 5 : 1–34.
  2. ^ Legendre P, Legendre L (1998). Ecología numérica (segunda edición en inglés). pág. 853.
  3. ^ Everitt BS, Landau S , Leese M (2001). Análisis de conglomerados (cuarta edición). Londres: Arnold. ISBN 0-340-76119-9.
  4. ^ Defays D (1977). "Un algoritmo eficiente para un método de enlace completo". The Computer Journal . 20 (4). British Computer Society: 364–366. doi :10.1093/comjnl/20.4.364.
  5. ^ Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosómico 5S, 5.8S y 4.5S publicadas". Nucleic Acids Research . 14 Suppl (Supl.): r1-59. doi :10.1093/nar/14.suppl.r1. PMC 341310 . PMID  2422630. 
  6. ^ Olsen GJ (1988). "Análisis filogenético utilizando 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.

Lectura adicional