Agrupación de enlace único

Método de agrupamiento jerárquico aglomerativo

En estadística , la agrupación de vínculo único es uno de varios métodos de agrupación jerárquica . Se basa en agrupar clusters de abajo hacia arriba (clustering aglomerativo), combinando en cada paso dos clusters que contienen el par de elementos más cercano que aún no pertenecen al mismo cluster entre sí.

Este método tiende a producir grupos largos y delgados en los que los elementos cercanos del mismo grupo tienen distancias pequeñas, pero los elementos en los extremos opuestos de un grupo pueden estar mucho más lejos entre sí que dos elementos de otros grupos. 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 algoritmo de amigos de amigos. ^[2]

Descripción general de los métodos de agrupación aglomerativa

Al comienzo del proceso de agrupamiento aglomerativo, cada elemento forma 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 conglomerados, conocida como función de enlace , es lo que diferencia los métodos de agrupamiento aglomerativo.

En la agrupación 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 más corta de estas distancias por pares que permanecen en cualquier paso hace que los dos grupos cuyos elementos están involucrados se fusionen. El método también se conoce como agrupación de vecinos más cercanos . El resultado de la agrupación 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 grupos 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 cualesquiera 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 grupos antiguos se fusionan en otros nuevos. La matriz de proximidad contiene todas las distancias . A las agrupaciones se les asignan números de secuencia y es el nivel de la agrupación -ésima. Un grupo con número de secuencia m se denota ( m ) y la proximidad entre grupos 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 conglomerados más similar en la agrupación actual, digamos par , según dónde esté el mínimo sobre todos los pares de conglomerados en la agrupación actual. ${\displaystyle (r),(s)}$ ${\displaystyle d[(r),(s)]=\min d[(i),(j)]}$
3. Incrementar el número de secuencia: . Fusione grupos en un solo grupo para formar el siguiente grupo . Establezca el nivel de esta agrupación 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 grupos y agregando una fila y una columna correspondientes al grupo recién formado. La proximidad entre el nuevo grupo, indicado y un grupo antiguo, 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 grupo, deténgase. De lo contrario, vaya al paso 2.

Ejemplo de trabajo

Este 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 ribosomal 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

• Primera agrupación

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 estén equidistantes de u . Esto corresponde a la expectativa de la hipótesis de ultrametricidad . Las ramas que unen a y b con u tienen 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

Luego 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 manteniendo 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 que no participan en el primer grupo. ${\displaystyle D_{2}}$

Segundo paso

• Segunda agrupación

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

Aquí, y están los valores más bajos de , por lo que unimos el grupo 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 cy 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 que falta:

${\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 distancias (ver más abajo), 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}$

Último paso

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

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

Denotemos el nodo (raíz) al que ahora están conectados. Las ramas que se unen y para luego tener 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 restante de la rama:

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

Datos del dendrograma de enlace único 5S

El dendrograma ya está completo. Es ultramétrico porque todas las puntas ( , , , y ) están 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 tanto, el dendrograma tiene su raíz en , su nodo más profundo. ${\displaystyle r}$

Otros vínculos

El algoritmo ingenuo para la agrupación de enlace único es esencialmente el mismo que el algoritmo de Kruskal para árboles de expansión mínima . Sin embargo, en la agrupación de enlace único, el orden en el que se forman las agrupaciones es importante, mientras que para los árboles de expansión mínima lo que importa es el conjunto de pares de puntos que forman distancias elegidas por el algoritmo.

Los esquemas de vinculación alternativos incluyen agrupación de vinculación completa , agrupación de vinculación promedio ( UPGMA y WPGMA ) y el método de Ward . En el algoritmo ingenuo para la agrupación aglomerativa, se puede implementar un esquema de vinculación diferente simplemente usando una fórmula diferente para calcular las distancias entre agrupaciones en el algoritmo. La fórmula que se debe ajustar se ha resaltado con texto en negrita en la descripción del algoritmo anterior. Sin embargo, algoritmos más eficientes como el que se describe a continuación no se generalizan a todos los esquemas de vinculación de la misma manera.

Algoritmos más rápidos

El algoritmo ingenuo para la agrupación en clústeres de enlace único es fácil de entender pero lento y con complejidad temporal . ^[6] En 1973, R. Sibson propuso un algoritmo con complejidad temporal y complejidad espacial (ambas óptimas) conocido como SLINK. El algoritmo de enlace representa una agrupación de un conjunto de elementos numerados mediante dos funciones. Ambas funciones se determinan encontrando el grupo más pequeño que contenga tanto un elemento  como al menos un elemento con un número mayor. La primera función, asigna el elemento al  elemento con el número más grande del grupo . La segunda función, asigna el 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 la agrupación 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 único para el conjunto aumentado, representado de la misma manera, se pueden construir a partir del antiguo agrupamiento en el tiempo . Luego, el algoritmo SLINK recorre los elementos, uno por uno, agregándolos a la representación de la agrupación. ^{[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 montones binarios que requiere tiempo y espacio para construir el árbol de expansión mínimo (pero no el agrupamiento) de los elementos y distancias dados. Luego, aplicar el algoritmo de Kruskal al gráfico disperso formado por los bordes del árbol de expansión mínima produce el agrupamiento en sí en un tiempo y espacio adicionales . ^[9] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$

Ver también

• Análisis de conglomerados
• Agrupación de vínculos completos
• Agrupación jerárquica
• 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 Camino, 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 Bib : 2012amld.book....3F. doi :10.1201/b11822-7.
3. Legendre P, Legendre L (1998). Ecología Numérica . Desarrollos en modelización ambiental. vol. 20 (Segunda edición en inglés). Ámsterdam: Elsevier.
4. Erdmann VA, Wolters J (1986). "Colección de secuencias de ARN ribosomal 5S, 5.8S y 4.5S publicadas". Investigación de ácidos nucleicos . 14 Suplemento (Suplemento): r1-59. doi :10.1093/nar/14.suppl.r1. PMC 341310 . PMID  2422630. 
5. Olsen GJ (1988). "Análisis filogenético mediante 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. PMID  3241556.
6. Murtagh F, Contreras P (2012). "Algoritmos para agrupación jerárquica: una descripción general". Revisiones interdisciplinarias de Wiley: minería de datos y descubrimiento de conocimientos . 2 (1). Biblioteca en línea Wiley: 86–97. doi :10.1002/widm.53.
7. Sibson R (1973). "SLINK: un algoritmo óptimamente eficiente para el método de clúster de enlace único" (PDF) . La revista informática . 16 (1). Sociedad Británica de Computación: 30–34. doi : 10.1093/comjnl/16.1.30 .
8. Gan G (2007). Agrupación de datos: teoría, algoritmos y aplicaciones . Filadelfia, Pa. Alexandria, Va: SIAM, Asociación Estadounidense de Estadística de la Sociedad de Matemáticas Industriales y Aplicadas. ISBN  9780898716238.
9. Gower JC, Ross GJ (1969). "Árboles de expansión mínima y análisis de conglomerados de enlace único". Revista de la Royal Statistical Society, Serie C. 18 (1): 54–64. doi :10.2307/2346439. JSTOR  2346439. SEÑOR  0242315..

enlaces externos

• Enlaces utilizados en Matlab