Agrupación jerárquica en R - enlace de centroides - problema con las alturas de los dendrogramas

Question

Tengo un problema de comprensión del algoritmo de agrupación jerárquica, especialmente del método de vinculación de centroides. He leído muchos artículos con la descripción y parece ser bastante fácil, pero no puedo entender los resultados en valores reales.

Tengo un conjunto de muestras como este:

test_list <- list( uno = c(1), dos = c(2), seis = c(6), once = c(11), dieciséis = c(16) )

Puedo generar un cluster usando esta función:

test_dendrogram <- tsclust(test_list, tipo = "jerárquico", distancia = "L1", control = hierarchical_control(method = "centroid" ) )

El dendrograma tiene este aspecto:

La lista de alturas es: 1.000000 4.250000 5.000000 8.138889

Entiendo que los resultados son los siguientes:

1 = 2 - 1

5 = 16 - 11

4,25 = 6-((2+1)/2 + 2)/2 <- en este paso tenemos que sustituir 1 por el centroide 1 y 2 = 1,5 y calcular el centroide que significa la media aritmética.

Pero no tengo ni idea de cómo calcular 8,13. Hice el mismo ejercicio con los métodos de enlace simple, medio y completo y los resultados son evidentes.

Answer 1

Explicación de los cálculos realizados en la agrupación jerárquica de centros

Your data: 5 points in 1D feature space:
a   1 
b   2 
c   6 
d  11 
e  16

Calcule las distancias euclidianas al cuadrado (porque el método del centroide lo necesita) y realice la agrupación aglomerativa (realizada en SPSS).

En el dengrograma, las distancias calculadas entre los clusters que se fusionan en los pasos se reescalan numéricamente en el rango 1-25, sin embargo, en la tabla del historial de aglomeración se muestran tal cual (llamados "coeficientes").

Ahora vamos a trazar los cálculos realizados.

Paso 1. Encuentra la distancia mínima y une estos dos puntos. Se trata de a y b (es decir, los puntos 1 y 2 del programa de aglomeración) y la distancia (euclidiana al cuadrado) es $1$ . BIEN. Etiquete el cluster (a+b) 1 (el menor entre las etiquetas 1 y 2) y elimine el cluster 2, es decir, el punto b, de la matriz. Ahora actualiza las distancias cuadradas entre el clúster 1 (es decir, los puntos a+b) y cualquier otro punto/clúster. Esto se hace a través de la fórmula de Lance-Williams, que en el caso del método de vinculación del centroide se convierte en esto:

$D_{(pq)r} = \frac{N_p}{N_{pq}} D_{pr} + \frac{N_q}{N_{pq}} D_{qr} - \frac{N_pN_q}{N_{pq}^2} D_{pq}$

donde $D_{(pq)r}$ es la distancia del nuevo clúster "pq" (recién fusionado de los subclústeres "p" y "q") y todos los demás clústeres "r", $N$ con subíndice es el número de puntos de un cluster.

Así, después de la fusión en el paso 1, calculamos la distancia entre (a+b) y, digamos, d, como

$D_{(ab)d} = \frac{1}{2} 100 + \frac{1}{2} 81 - \frac{1 \cdot 1}{2^2} 1 = 90.25$ .

Al calcular la distancia entre (a+b) y cualquier otro clúster, la matriz de distancia actualizada es

       ab     c      d      e
ab     .00  20.25  90.25 210.25
c    20.25    .00  25.00 100.00
d    90.25  25.00    .00  25.00
e   210.25 100.00  25.00    .00

Paso 2. Encuentra la distancia mínima en él. Es la distancia entre el clúster (a+b) y el clúster (punto) c (alias 3 en el programa de agl.). Fusiona los dos clusters, (ab+c) y, mediante la fórmula, actualiza las distancias entre éste y todos los demás (antes, elimina la fila y la columna c). Por ejemplo, la distancia entre (ab+c) y d será:

$D_{((ab)c)d} = \frac{2}{3} 90.25 + \frac{1}{3} 25 - \frac{2 \cdot 1}{3^2} 20.25 = 64$

y toda la matriz de distancia actualizada

       abc    d      e
abc    .00  64.00 169.00
 d   64.00    .00  25.00
 e  169.00  25.00    .00

Paso 3. etc. igualmente. Los dos clusters a fusionar serán d y e cuya distancia = $25$ es actualmente el menos.

Recuerde que los cálculos se realizan en al cuadrado distancias euclidianas (en el método del centroide). Por supuesto, puede tomar la raíz del cálculo $D$ s en cada paso si se desea (razonablemente) trazar el dendrograma reflejando las distancias no cuadradas entre clusters. Simplemente tome la raíz cuadrada de los "coeficientes" en el programa de aglomeración anterior y eso será sus distancias no cuadradas para el dendrograma. En mi dendrograma mostrado arriba, se trazaron las distancias al cuadrado.