Hispanopedia Wiki
Articulo de referencia

Agrupamiento de enlace simple

En estadística , el agrupamiento de enlace simple es uno de los diversos métodos de agrupamiento jerárquico . Se basa en agrupar clústeres de forma ascendente (agrupamiento aglo...

Hispanopedia WikiContenido en espanolLectura gratuita

En estadística , el agrupamiento de enlace simple es uno de los diversos métodos de agrupamiento jerárquico . Se basa en agrupar clústeres de forma ascendente (agrupamiento aglomerativo), combinando en cada paso dos clústeres que contienen el par de elementos más cercanos 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 lejos entre sí que dos elementos de otros cúmulos. Para ciertas clases de datos, esto puede generar dificultades para definir clases que permitan 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 conoce como el algoritmo de amigos de amigos. [ 2 ]

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

Al inicio del proceso de agrupamiento aglomerativo, cada elemento se encuentra en un clúster propio. Estos clústeres se combinan secuencialmente para formar clústeres más grandes, hasta que todos los elementos se encuentran en el mismo clúster. En cada paso, se combinan los dos clústeres separados por la menor distancia. La función utilizada para determinar la distancia entre dos clústeres, 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 clústeres se determina mediante un único par de elementos: aquellos dos elementos (uno en cada clúster) que están más cerca entre sí. La menor de estas distancias entre pares que permanece en cualquier paso provoca la fusión de los dos clústeres cuyos elementos están involucrados. Este método también se conoce como agrupamiento del vecino más cercano . El resultado del agrupamiento se puede visualizar como un dendrograma , que muestra la secuencia en la que se fusionaron los clústeres 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 clústeres X e Y– se describe mediante la expresión

D(incógnita,Y)=minincógnita∈incógnita,y∈Yd(incógnita,y),{\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 clústeres antiguos se fusionan con otros nuevos.norte×norte{\displaystyle N\times N}matriz de proximidadD{\displaystyle D}contiene todas las distanciasd(i,j){\displaystyle d(i,j)}A las agrupaciones se les asignan números de secuencia.0,1,…,norte−1{\displaystyle 0,1,\ldots ,n-1}yL(k){\displaystyle L(k)}es el nivel de lak{\displaystyle k}Agrupamiento -ésimo. Un clúster con número de secuencia m se denota ( m ) y la proximidad entre clústeres(r){\displaystyle (r)}y(s){\displaystyle (s)}se denotad[(r),(s)]{\displaystyle d[(r),(s)]}.

El algoritmo de enlace simple se compone de los siguientes pasos:

  1. Comience con la agrupación disjunta que tiene nivel L(0)=0{\displaystyle L(0)=0}y número de secuenciametro=0{\displaystyle m=0}.
  2. Encuentra el par de clústeres más similares en la agrupación actual, digamos el par(r),(s){\displaystyle (r),(s)}, de acuerdo ad[(r),(s)]=mind[(i),(j)]{\displaystyle d[(r),(s)]=\min d[(i),(j)]}donde el mínimo se encuentra sobre todos los pares de clústeres en la agrupación actual.
  3. Incrementar el número de secuencia:metro=metro+1{\displaystyle m=m+1}. Fusionar clústeres(r){\displaystyle (r)}y(s){\displaystyle (s)}en un único grupo para formar el siguiente grupometro{\displaystyle m}. Establezca el nivel de esta agrupación enL(metro)=d[(r),(s)]{\displaystyle L(m)=d[(r),(s)]}
  4. Actualizar la matriz de proximidad,D{\displaystyle D}, eliminando las filas y columnas correspondientes a los clústeres(r){\displaystyle (r)}y(s){\displaystyle (s)}y agregando una fila y una columna correspondientes al clúster recién formado. La proximidad entre el nuevo clúster, denotada(r,s){\displaystyle (r,s)}y un grupo antiguo(k){\displaystyle (k)}se define comod[(r,s),(k)]=min{d[(k),(r)],d[(k),(s)]}{\displaystyle d[(r,s),(k)]=\min\{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.

Ejemplo práctico

Este ejemplo práctico se basa en una matriz de distancia genética JC69 calculada a partir del alineamiento de secuencias de ARN ribosomal 5S de cinco bacterias: Bacillus subtilis (a{\displaystyle a}), Bacillus stearothermophilus (b{\displaystyle b}), Lactobacillus viridescens (do{\displaystyle c}), Acholeplasma modicum (d{\displaystyle d}), y Micrococcus luteus (mi{\displaystyle e}). [ 4 ] [ 5 ]

Primer paso

  • Primer agrupamiento

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

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

  • Estimación de la longitud de la primera rama

Sea u el nodo al que ahora están conectados a y b . Estableciendoδ(a,tú)=δ(b,tú)=D1(a,b)/2{\displaystyle \delta (a,u)=\delta (b,u)=D_{1}(a,b)/2} asegura 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 a u tienen entonces longitudes δ(a,tú)=δ(b,tú)=17/2=8.5{\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.D1{\displaystyle D_{1}}en una nueva matriz de proximidadD2{\displaystyle D_{2}}(ver abajo), reducido en tamaño por una fila y una columna debido a la agrupación de a con b . Valores en negrita enD2{\displaystyle D_{2}}corresponden a las nuevas distancias, calculadas conservando la distancia mínima entre cada elemento del primer clúster.(a,b){\displaystyle (a,b)}y cada uno de los elementos restantes:

D2((a,b),do)=min(D1(a,do),D1(b,do))=min(21,30)=21D2((a,b),d)=min(D1(a,d),D1(b,d))=min(31,34)=31D2((a,b),mi)=min(D1(a,mi),D1(b,mi))=min(23,21)=21{\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}}}

Valores en cursiva enD2{\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 paso

  • Segundo agrupamiento

Ahora reiteramos las tres acciones anteriores, partiendo de la nueva matriz de distancias.D2{\displaystyle D_{2}} :

Aquí,D2((a,b),do)=21{\displaystyle D_{2}((a,b),c)=21} y D2((a,b),mi)=21{\displaystyle D_{2}((a,b),e)=21} son los valores más bajos deD2{\displaystyle D_{2}}, así que nos unimos al clúster(a,b){\displaystyle (a,b)}con el elemento c y con el elemento e .

  • Estimación de la longitud de la segunda rama

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

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

Deducimos la longitud de la rama faltante:

δ(tú,v)=δ(do,v)−δ(a,tú)=δ(do,v)−δ(b,tú)=10.5−8.5=2{\displaystyle \delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2}( véase el dendrograma final )
  • Actualización de la segunda matriz de distancias

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

D3(((a,b),do,mi),d)=min(D2((a,b),d),D2(do,d),D2(mi,d))=min(31,28,43)=28{\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

El finalD3{\displaystyle D_{3}}La matriz es:

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

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

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

Deducimos la longitud restante de la rama:

δ(v,r)=δ(a,r)−δ(a,v)=δ(b,r)−δ(b,v)=δ(do,r)−δ(do,v)=δ(mi,r)−δ(mi,v)=14−10.5=3.5{\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

Dendrograma de enlace simple Datos 5S
Dendrograma de enlace simple Datos 5S

El dendrograma ya está completo. Es ultramétrico porque todas las puntas (a{\displaystyle a},b{\displaystyle b},do{\displaystyle c},mi{\displaystyle e}, yd{\displaystyle d}) están equidistantes der{\displaystyle r} :

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

Por lo tanto, el dendrograma está enraizado porr{\displaystyle r}, su nodo más profundo.

Otros vínculos

El algoritmo ingenuo para la agrupación por enlace simple es esencialmente el mismo que el algoritmo de Kruskal para árboles de expansión mínima . Sin embargo, en la agrupación por enlace simple, el orden en que se forman los clústeres 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.

Entre los esquemas de enlace alternativos se 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 puede lograrse simplemente utilizando una fórmula distinta para calcular las distancias entre clústeres. La fórmula que debe ajustarse se ha resaltado 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 la agrupación de enlace simple es fácil de entender pero lento, con complejidad temporal.O(norte3){\displaystyle O(n^{3})}. [ 6 ] En 1973, R. Sibson propuso un algoritmo con complejidad temporalO(norte2){\displaystyle O(n^{2})}y complejidad espacialO(norte){\displaystyle O(n)}(ambos óptimos) conocido como SLINK. El algoritmo slink representa una agrupación en un conjunto denorte{\displaystyle n}elementos numerados por dos funciones. Ambas funciones se determinan encontrando el grupo más pequeño.do{\displaystyle C}que contiene ambos elementos i{\displaystyle i}y al menos un elemento de mayor numeración. La primera función,π{\displaystyle \pi }, elemento de mapas i{\displaystyle i}al elemento de mayor número en el grupodo{\displaystyle C}. La segunda función,λ{\displaystyle \lambda }, elemento de mapas i{\displaystyle i}a la distancia asociada con la creación del clústerdo{\displaystyle C}Almacenar estas funciones en dos matrices que asignan cada número de elemento a su valor de función requiere espacio.O(norte){\displaystyle O(n)}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 la nueva agrupación de enlace simple para el conjunto aumentado, representadas de la misma manera, se pueden construir a partir de la agrupación anterior en el tiempoO(norte){\displaystyle O(n)}El algoritmo SLINK luego itera sobre los elementos, uno por uno, agregándolos a la representación del agrupamiento. [ 7 ] [ 8 ]

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 usar el algoritmo de Kruskal, se puede usar el algoritmo de Prim , en una variación sin montículos binarios que toma tiempoO(norte2){\displaystyle O(n^{2})}y espacioO(norte){\displaystyle O(n)}para construir el árbol de expansión mínima (pero no la agrupación) de los elementos y distancias dados. Luego, al aplicar el algoritmo de Kruskal al grafo disperso formado por las aristas del árbol de expansión mínima se produce la agrupación en sí misma en un tiempo adicional.O(norteregistro⁡norte){\displaystyle O(n\log n)}y espacioO(norte){\displaystyle O(n)}. [ 9 ]

Véase también

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 and Hall/CRC. pp. 3–10 . Bibcode : 2012amld.book....3F . doi : 10.1201/b11822-7 (inactivo el 12 de julio de 2025). {{cite book}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
  3. ↑ Legendre P, Legendre L (1998). Ecología numérica . Avances 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 ribosómico 5S, 5.8S y 4.5S publicadas" . Nucleic Acids Research . 14 Suppl (Suppl): 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. pp. 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 visión general". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery . 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 enlace único" (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, Pa. Alexandria, Va: SIAM, Society for Industrial and Applied Mathematics American Statistical Association. ISBN  9780898716238.
  9. ↑ Gower JC, Ross GJ (1969). "Árboles de expansión mínima y análisis de conglomerados de enlace simple". Journal of the Royal Statistical Society, Serie C. 18 ( 1): 54– 64. doi : 10.2307/2346439 . JSTOR 2346439. MR 0242315 .  .
  • Enlaces utilizados en Matlab