Agrupamiento de enlace único

Método de agrupamiento jerárquico aglomerativo

En estadística , la agrupación por enlace simple es uno de los diversos métodos de agrupación jerárquica . Se basa en agrupar los clústeres de abajo a arriba (agrupación aglomerativa), combinando en cada paso dos clústeres que contienen el par de elementos más cercano que aún no pertenecen al mismo clúster.

Este método tiende a producir cúmulos largos y delgados en los que los elementos cercanos del mismo cúmulo tienen distancias pequeñas, pero los elementos en extremos opuestos de un cúmulo pueden estar mucho más alejados entre sí que dos elementos de otros cúmulos. Para algunas clases de datos, esto puede generar dificultades a la hora de definir clases que podrían subdividir los datos de manera útil. ^[1] Sin embargo, es popular en astronomía para analizar cúmulos de galaxias , que a menudo pueden involucrar largas cadenas de materia; en esta aplicación, también se lo conoce como el algoritmo de amigos de amigos. ^[2]

Descripción general de los métodos de agrupamiento aglomerativo

Al principio del proceso de agrupamiento aglomerativo, 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. En cada paso, se combinan los dos grupos separados por la distancia más corta. La función utilizada para determinar la distancia entre dos grupos, conocida como función de enlace , es lo que diferencia los métodos de agrupamiento aglomerativo.

En el agrupamiento de enlace simple, la distancia entre dos grupos está determinada por un único par de elementos: aquellos dos elementos (uno en cada grupo) que están más cerca uno del otro. La distancia más corta de estas distancias por pares que permanece en cualquier paso hace que los dos grupos cuyos elementos están involucrados se fusionen. El método también se conoce como agrupamiento por vecino más cercano . El resultado del agrupamiento se puede visualizar como un dendrograma , que muestra la secuencia en la que se fusionaron los grupos y la distancia a la que tuvo lugar cada fusión. ^[3]

Matemáticamente, la función de enlace – la distancia D ( X , Y ) entre los conglomerados X e Y – se describe mediante la expresión

${\displaystyle D(X,Y)=\min _{x\in X,y\in Y}d(x,y),}$

donde X e Y son dos conjuntos de elementos considerados como clústeres, y d ( x , y ) denota la distancia entre los dos elementos x e y .

Algoritmo 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 contiene todas las distancias . A los clústeres se les asignan números de secuencia y es el nivel del clúster -ésimo. Un clúster con número de secuencia m se denota ( m ) y la proximidad entre clústeres y se denota . ${\displaystyle N\times N}$ ${\displaystyle D}$ ${\displaystyle d(i,j)}$ ${\displaystyle 0,1,\ldots ,n-1}$ ${\displaystyle L(k)}$ ${\displaystyle k}$ ${\displaystyle (r)}$ ${\displaystyle (s)}$ ${\displaystyle d[(r),(s)]}$

El algoritmo de enlace único se compone de los siguientes pasos:

1. Comience con la agrupación disjunta que tiene nivel y número de secuencia . ${\displaystyle L(0)=0}$ ${\displaystyle m=0}$
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ínimo en todos los pares de clústeres en el agrupamiento actual. ${\displaystyle (r),(s)}$ ${\displaystyle d[(r),(s)]=\min d[(i),(j)]}$
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 ${\displaystyle m=m+1}$ ${\displaystyle (r)}$ ${\displaystyle (s)}$ ${\displaystyle m}$ ${\displaystyle L(m)=d[(r),(s)]}$
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 como y un clúster anterior se define como . ${\displaystyle D}$ ${\displaystyle (r)}$ ${\displaystyle (s)}$ ${\displaystyle (r,s)}$ ${\displaystyle (k)}$ ${\displaystyle d[(r,s),(k)]=\min\{d[(k),(r)],d[(k),(s)]\}}$
5. Si todos los objetos están en un clúster, deténgase. De lo contrario, vaya al paso 2.

Ejemplo de trabajo

Este ejemplo práctico 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 ( ). ^{[4] [5]} ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

Primer paso

• Primer agrupamiento

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

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

• Estimación de la longitud de la primera rama

Sea u el nodo al que ahora están conectados a y b . La configuración garantiza que los elementos a y b sean equidistantes de u . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que unen a y b con u tienen entonces longitudes ( ver el dendrograma final ) ${\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2}$ ${\displaystyle \delta (a,u)=\delta (b,u)=17/2=8.5}$

• Primera actualización de la matriz de distancias

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

${\displaystyle {\begin{array}{lllllll}D_{2}((a,b),c)&=&\min(D_{1}(a,c),D_{1}(b,c))&=&\min(21,30)&=&21\\D_{2}((a,b),d)&=&\min(D_{1}(a,d),D_{1}(b,d))&=&\min(31,34)&=&31\\D_{2}((a,b),e)&=&\min(D_{1}(a,e),D_{1}(b,e))&=&\min(23,21)&=&21\end{array}}}$

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. ${\displaystyle D_{2}}$

Segundo paso

• Segundo agrupamiento

Reiteramos ahora las tres acciones anteriores, partiendo de la nueva matriz de distancias  : ${\displaystyle D_{2}}$

Aquí, y son los valores más bajos de , por lo que unimos el clúster con el elemento c y con el elemento e . ${\displaystyle D_{2}((a,b),c)=21}$ ${\displaystyle D_{2}((a,b),e)=21}$ ${\displaystyle D_{2}}$ ${\displaystyle (a,b)}$

• Estimación de la longitud de la segunda rama

Sea v el nodo al que ahora están conectados , c y e . Debido a la restricción de ultrametricidad, las ramas que unen a o b con v , y c con v , y también e con v son iguales y tienen la siguiente longitud total: ${\displaystyle (a,b)}$

${\displaystyle \delta (a,v)=\delta (b,v)=\delta (c,v)=\delta (e,v)=21/2=10.5}$

Deducimos la longitud de la rama faltante:

${\displaystyle \delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2}$( ver el dendrograma final )

• Segunda actualización de la matriz de distancias

Luego procedemos a actualizar la matriz en una nueva matriz de distancia (ver a continuación), reducida en tamaño en dos filas y dos columnas debido a la agrupación de con c y con e  : ${\displaystyle D_{2}}$ ${\displaystyle D_{3}}$ ${\displaystyle (a,b)}$

${\displaystyle D_{3}(((a,b),c,e),d)=\min(D_{2}((a,b),d),D_{2}(c,d),D_{2}(e,d))=\min(31,28,43)=28}$

Paso final

La matriz final es: ${\displaystyle D_{3}}$

Así que unimos clústeres y . ${\displaystyle ((a,b),c,e)}$ ${\displaystyle d}$

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

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

Deducimos la longitud de la rama restante:

${\displaystyle \delta (v,r)=\delta (a,r)-\delta (a,v)=\delta (b,r)-\delta (b,v)=\delta (c,r)-\delta (c,v)=\delta (e,r)-\delta (e,v)=14-10.5=3.5}$

El dendrograma de enlace único

Datos del dendrograma de ligamiento único 5S

El dendrograma ya está completo. Es ultramétrico porque todas las puntas ( , , , y ) son equidistantes de  : ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle e}$ ${\displaystyle d}$ ${\displaystyle r}$

${\displaystyle \delta (a,r)=\delta (b,r)=\delta (c,r)=\delta (e,r)=\delta (d,r)=14}$

Por lo tanto, el dendrograma tiene su raíz en , su nodo más profundo. ${\displaystyle r}$

Otros vínculos

El algoritmo ingenuo para el agrupamiento por ligamiento simple es esencialmente el mismo que el algoritmo de Kruskal para árboles de expansión mínima . Sin embargo, en el agrupamiento por ligamiento simple, el orden en el que se forman los grupos es importante, mientras que para los árboles de expansión mínima lo que importa es el conjunto de pares de puntos que forman las distancias elegidas por el algoritmo.

Los esquemas de enlace alternativos incluyen el agrupamiento por enlace completo , el agrupamiento por enlace promedio ( UPGMA y WPGMA ) y el método de Ward . En el algoritmo ingenuo para el agrupamiento aglomerativo, la implementación de un esquema de enlace diferente se puede lograr simplemente utilizando una fórmula diferente para calcular las distancias entre grupos en el algoritmo. La fórmula que se debe ajustar se ha resaltado utilizando texto en negrita en la descripción del algoritmo anterior. Sin embargo, los algoritmos más eficientes como el que se describe a continuación no se generalizan a todos los esquemas de enlace de la misma manera.

Algoritmos más rápidos

El algoritmo ingenuo para el agrupamiento de enlace simple es fácil de entender pero lento, con complejidad temporal . ^[6] En 1973, R. Sibson propuso un algoritmo con complejidad temporal y complejidad espacial (ambas óptimas) conocido como SLINK. El algoritmo slink representa un agrupamiento en un conjunto de elementos numerados por dos funciones. Estas funciones se determinan al encontrar el grupo más pequeño que contiene tanto elemento  como al menos un elemento con un número mayor. La primera función, , asigna elemento  al elemento con el número más grande en el grupo . La segunda función, , asigna elemento  a la distancia asociada con la creación del grupo . Almacenar estas funciones en dos matrices que asignan cada número de elemento a su valor de función requiere espacio , y esta información es suficiente para determinar el agrupamiento en sí. Como muestra Sibson, cuando se agrega un nuevo elemento al conjunto de elementos, las funciones actualizadas que representan el nuevo agrupamiento de enlace simple para el conjunto aumentado, representado de la misma manera, se pueden construir a partir del agrupamiento anterior en el tiempo . Luego, el algoritmo SLINK recorre los elementos, uno por uno, y los agrega a la representación del agrupamiento. ^{[7] [8]} ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle i}$ ${\displaystyle \pi }$ ${\displaystyle i}$ ${\displaystyle C}$ ${\displaystyle \lambda }$ ${\displaystyle i}$ ${\displaystyle C}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

Un algoritmo alternativo, que se ejecuta en los mismos límites óptimos de tiempo y espacio, se basa en la equivalencia entre el algoritmo ingenuo y el algoritmo de Kruskal para árboles de expansión mínima. En lugar de utilizar el algoritmo de Kruskal, se puede utilizar el algoritmo de Prim , en una variación sin montículos binarios que requiere tiempo y espacio para construir el árbol de expansión mínima (pero no la agrupación) de los elementos y distancias dados. Luego, la aplicación del algoritmo de Kruskal al gráfico disperso formado por los bordes del árbol de expansión mínima produce la agrupación en sí misma en un tiempo y espacio adicionales . ^[9] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$

Véase también

• Análisis de conglomerados
• Agrupamiento por ligamiento completo
• Agrupamiento jerárquico
• Reloj molecular
• Unión de vecinos
• UPGMA
• WPGMA

Referencias

1. Everitt B (2011). Análisis de conglomerados . Chichester, West Sussex, Reino Unido: Wiley. ISBN  9780470749913.
2. Feigelson, Eric (2012). "Clasificación en astronomía: pasado y presente". En Way, Michael J.; Scargle, Jeffrey D.; Ali, Kamal M.; Srivastava, Ashok N. (eds.). Avances en aprendizaje automático y minería de datos para astronomía . Chapman y Hall/CRC. págs. 3–10. Código Bibliográfico :2012amld.book....3F. doi :10.1201/b11822-7.
3. Legendre P, Legendre L (1998). Ecología numérica . Desarrollos en modelado ambiental. Vol. 20 (segunda edición en inglés). Ámsterdam: Elsevier.
4. 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. 
5. Olsen GJ (1988). "Análisis filogenético utilizando ARN ribosómico". En Noller HF Jr, Moldave K (eds.). 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.
6. Murtagh F, Contreras P (2012). "Algoritmos para agrupamiento jerárquico: una descripción general". Wiley Interdisciplinary Reviews: Minería de datos y descubrimiento de conocimiento . 2 (1). Wiley Online Library: 86–97. doi :10.1002/widm.53.
7. Sibson R (1973). "SLINK: un algoritmo óptimamente eficiente para el método de clúster de un solo enlace" (PDF) . The Computer Journal . 16 (1). British Computer Society: 30–34. doi : 10.1093/comjnl/16.1.30 .
8. Gan G (2007). Agrupamiento de datos: teoría, algoritmos y aplicaciones . Filadelfia, Pensilvania. Alejandría, Virginia: SIAM, Sociedad de Matemática Industrial y Aplicada, Asociación Estadística Estadounidense. ISBN  9780898716238.
9. Gower JC, Ross GJ (1969). "Árboles de expansión mínima y análisis de conglomerados de enlace simple". Revista de la Royal Statistical Society, Serie C. 18 ( 1): 54–64. doi :10.2307/2346439. JSTOR  2346439. MR  0242315..

Enlaces externos

• Enlaces utilizados en Matlab